장벽(컴퓨터 과학)

Barrier (computer science)

병렬 컴퓨팅에서 장벽은 동기화 방법의 한 종류입니다.소스 코드의 스레드 또는 프로세스 그룹에 대한 장벽은 모든 스레드/프로세스가 이 장벽에 도달할 때까지 이 시점에서 정지해야 함을 의미합니다.

많은 집합 루틴과 지시 기반 병렬 언어에는 암묵적인 장벽이 있습니다.예를 들어 OpenMP를 사용한 Fortran의 병렬 실행 루프는 마지막 반복이 완료될 때까지 스레드 상에서 계속할 수 없습니다.이는 프로그램이 완료된 직후에 루프 결과에 의존하는 경우입니다.메시지 전달에 있어서, 글로벌한 통신(감축이나 산란 등)은, 장벽이 되는 경우가 있습니다.

동시 컴퓨팅에서는 장벽이 높아지거나 낮아지는 경우가 있습니다.래치라는 용어는 상승 상태에서 시작하여 하강 상태에서 다시 상승할 수 없는 장벽을 가리키는 데 사용되기도 한다.카운트다운 래치라는 용어는 미리 정해진 수의 스레드/프로세스가 도착하면 자동으로 내려가는 래치를 가리키는 데 사용되기도 합니다.

실행

기본 장벽에는 주로 두 가지 변수가 있으며, 하나는 장벽의 통과/정지 상태를 기록하고 다른 하나는 장벽에 진입한 총 스레드 수를 유지합니다.장벽 상태는 장벽에 들어오는 첫 번째 스레드에 의해 "정지"되도록 초기화되었습니다.스레드가 들어갈 때마다 장벽에 이미 있는 스레드 수에 따라 마지막 스레드만 장벽 상태를 "통과"로 설정하여 모든 스레드가 장벽 밖으로 나갈 수 있도록 합니다.한편, 들어오는 스레드가 마지막 스레드가 아닐 때는 장벽에 갇혀 장벽 상태가 '정지'에서 '통과'로 바뀌었는지 계속 테스트하고 장벽 상태가 '통과'로 바뀌어야 빠져나간다.다음 C 코드는 이 [1][2]절차를 보여줍니다. 

구조 barrier_type {     // 장벽에 진입한 프로세서 수     // 0으로 초기화     인트 도착 카운터;     // 장애물을 통과한 프로세서 수     // p로 초기화     인트 leave_counter(카운터);     인트 깃발;     표준::뮤텍스 잠그다; };  // p 프로세서의 장벽 무효 장벽(barrier_type* b, 인트 p) {     b->잠그다.잠그다();     한다면 (b->도착 카운터 == 0)     {         b->잠그다.언락();         하는 동안에 (b->leave_counter(카운터) != p); // 클리어하기 전에 모두 나갈 때까지 기다립니다.         b->잠그다.잠그다();         b->깃발 = 0; // first arriver가 플래그를 지웁니다.     }     b->도착 카운터++;     한다면 (b->도착 카운터 == p) // 마지막 도착자가 플래그를 설정합니다.     {         b->도착 카운터 = 0;         b->leave_counter(카운터) = 0;         b->깃발 = 1;     }     b->잠그다.언락();      하는 동안에 (b->깃발 == 0); // 플래그 대기     b->잠그다.잠그다();     b->leave_counter(카운터)++;     b->잠그다.언락(); }

잠재적인 문제는 다음과 같습니다.

  1. 모든 스레드가 pass/stop 글로벌 변수에 반복적으로 액세스하기 때문에 통신 트래픽이 다소 높아져 scalability가 저하됩니다.

이 문제는 스레드를 다시 그룹화하고 트리 장벽 결합과 같은 다단계 장벽을 사용하여 해결할 수 있습니다.또, 하드웨어의 실장에서는, scalability가 향상하는 메리트가 있습니다.

센스 역방향 집중 장벽

패스/스톱을 나타내기 위해 동일한 값을 사용하는 대신 순차 장벽은 패스/스톱 상태에 대해 반대 값을 사용합니다.예를 들어 장벽 1이 스레드 정지에 0을 사용하는 경우 장벽 2는 스레드 정지에 1을 사용하고 장벽 3은 스레드 정지에 0을 사용합니다.[3]다음 C코드가 [1][4][2]이를 나타냅니다. 

구조 barrier_type {     인트 계산대; // 0으로 초기화     인트 깃발; // 0으로 초기화     표준::뮤텍스 잠그다; };  인트 local_sense = 0; // 프로세서당 프라이빗  // p 프로세서의 장벽 무효 장벽(barrier_type* b, 인트 p) {     local_sense = 1 - local_sense;     b->잠그다.잠그다();     b->계산대++;     인트 오시다 = b->계산대;     한다면 (오시다 == p) // 마지막 도착자가 플래그를 설정합니다.     {         b->잠그다.언락();         b->계산대 = 0;         // 카운터로의 변경을 보증하는 메모리 펜스         // 플래그 변경 전에 표시됨         b->깃발 = local_sense;     }     또 다른     {         b->잠그다.언락();         하는 동안에 (b->깃발 != local_sense); // 플래그 대기     } }

트리 장벽의 조합

조합 트리 장벽은 모든 스레드가 동일한 [3]위치에서 회전하는 경우를 방지하여 확장성을 해결하기 위한 계층적 장벽 구현 방법입니다.

k-트리 장벽에서는 모든 스레드가 k개의 스레드의 하위 그룹으로 균등하게 분할되며 이러한 하위 그룹 내에서 1차 동기화가 수행됩니다.모든 서브그룹의 동기화가 완료되면 각 서브그룹의 첫 번째 스레드가 추가 동기화를 위해 두 번째 레벨로 들어갑니다.두 번째 레벨에서는 첫 번째 레벨과 마찬가지로 스레드가 k개의 스레드의 새로운 서브그룹을 형성하고 그룹 내에서 동기화하여 각 서브그룹에서1개의 스레드를 다음 레벨로 송신합니다.최종적으로 최종 레벨에서는 동기화할 서브그룹은 1개뿐입니다.최종 레벨 동기 후에 해제 신호가 상위 레벨로 전송되어 모든 스레드가 [4][5]장벽을 통과한다.

하드웨어 장벽 구현

하드웨어 장벽은 위의 기본 장벽 [1]모델을 구현하기 위해 하드웨어를 사용합니다.

가장 간단한 하드웨어 구현에서는 전용 와이어를 사용하여 신호를 전송하여 장벽을 구현합니다.이 전용 와이어는 OR/AND 연산을 수행하여 통과/블록 플래그 및 스레드 카운터 역할을 합니다.소형 시스템에서는 이러한 모델이 작동하며 통신 속도는 큰 문제가 되지 않습니다.대규모 멀티프로세서 시스템에서는 이러한 하드웨어 설계를 통해 장벽 구현의 지연 시간이 길어질 수 있습니다.프로세서 간의 네트워크 접속은 지연을 줄이기 위한 하나의 구현으로, 트리 [6]장벽 결합과 유사합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b c Solihin, Yan (2015-01-01). Fundamentals of Parallel Multicore Architecture (1st ed.). Chapman & Hall/CRC. ISBN 978-1482211184.
  2. ^ a b "Implementing Barriers". Carnegie Mellon University.
  3. ^ a b Culler, David (1998). Parallel Computer Architecture, A Hardware/Software Approach. ISBN 978-1558603431.
  4. ^ a b Nanjegowda, Ramachandra; Hernandez, Oscar; Chapman, Barbara; Jin, Haoqiang H. (2009-06-03). Müller, Matthias S.; Supinski, Bronis R. de; Chapman, Barbara M. (eds.). Evolving OpenMP in an Age of Extreme Parallelism. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 42–52. doi:10.1007/978-3-642-02303-3_4. ISBN 9783642022845.
  5. ^ Nikolopoulos, Dimitrios S.; Papatheodorou, Theodore S. (1999-01-01). A Quantitative Architectural Evaluation of Synchronization Algorithms and Disciplines on ccNUMA Systems: The Case of the SGI Origin2000. Proceedings of the 13th International Conference on Supercomputing. ICS '99. New York, NY, USA: ACM. pp. 319–328. doi:10.1145/305138.305209. ISBN 978-1581131642. S2CID 6097544.
  6. ^ N.R. 아디가 등BlueGene/L Supercomputer 개요하이 퍼포먼스 네트워킹 및 컴퓨팅에 관한 회의, 2002년.

외부 링크

"Parallel Programming with Barrier Synchronization". sourceallies.com. March 2012.