민영화(컴퓨터 프로그래밍)
Privatization (computer programming)
민영화는 병렬 프로그램에서 서로 다른 스레드 간에 발생하는 의존성을 제거함으로써 병렬화를 가능하게 하는 공유 메모리 프로그래밍에서 사용되는 기술입니다.스레드 간의 의존성은 변수를 동시에 읽거나 쓰는 두 개 이상의 스레드에서 발생합니다.민영화는 각 스레드에 개인 복사본을 제공하기 때문에 스레드는 독립적으로 읽고 쓸 수 있고, 따라서 동시에 [1]쓸 수 있습니다.
각 병렬 알고리즘은 변수를 공유할지 아니면 비공개로 할지 지정합니다.변수가 공유된다고 선언되었지만 알고리즘에 의해 변수가 비공개로 요구되거나 [2]그 반대로 요구될 경우 구현 시 많은 오류가 발생할 수 있습니다.
기존에는 컴파일러를 병렬화하는 것은 스칼라 요소에만 민영화를 적용할 수 있었습니다.병렬 프로그램(루프 레벨의 병렬화)[3] 내에서 반복에 걸쳐 발생하는 병렬화를 이용하기 위해 어레이 변수 사유화도 실행할 수 있는 컴파일러의 필요성이 커졌습니다.오늘날 대부분의 컴파일러는 어레이의 개인화를 더 많은 기능과 함께 수행하여 병렬 프로그램의 전반적인 성능을 향상시킬 수 있습니다.예를 들어 Polaris 병렬화 [4]컴파일러가 있습니다.
묘사
공유 메모리 멀티프로세서는 "다른 명령 [4]스트림을 실행하는 여러 개의 독립된 프로세서로 구성된 컴퓨터 시스템"입니다.공유 메모리 프로그래밍 모델은 병렬 프로세서 [1]설계에 가장 널리 사용됩니다.이 프로그래밍 모델은 코드 조각 내에서 병렬 처리 가능성을 확인한 후 이러한 병렬 작업을 스레드에 매핑하는 것으로 시작합니다.
다음 단계는 병렬 프로그램에서 사용되는 변수의 범위를 결정하는 것으로, 이 모델의 주요 단계 중 하나이자 주요 관심사입니다.
가변 범위
모델의 다음 단계에서는 일반적으로 사용 가능한 프로세서보다 더 많은 태스크가 있기 때문에 태스크를 더 큰 태스크로 그룹화합니다.일반적으로 태스크가 할당되는 실행 스레드 수는 프로세서 수 이하로 선택되며 각 스레드는 고유한 [1]프로세서에 할당됩니다.
이 단계 직후에는 작업 내 변수 사용 현황 분석이 필요합니다.이 절차에서는 각 변수를 모두 공유할지 아니면 각 [1]스레드 간에 개인으로 공유할지 결정합니다.이 순서는 공유 메모리프로그래밍에 고유합니다(모든 변수가 프라이빗한 메시지 전달도 있습니다).[1]
이러한 동작에 따라 변수는 다음과 같이 분류됩니다.
- 읽기 전용: 변수가 모든 병렬 태스크에서만 읽히는 경우.
- Read/Write Non-conflicting: 변수가 하나의 작업만으로 읽기, 쓰기 또는 둘 다되는 경우.변수가 스칼라가 아닌 경우 다른 병렬 태스크에 의해 다른 요소를 읽고 쓸 수 있습니다.
- 읽기/쓰기 충돌: 변수가 작업에 의해 쓰여지고 다른 작업에 의해 읽힐 수 있는 경우.변수가 스칼라가 아닌 경우 다른 요소가 다른 병렬 태스크에 의해 읽혀지고 쓰입니다.
정의에서 알 수 있듯이 읽기/쓰기 충돌 변수는 서로 다른 실행 스레드 간의 종속성을 도입하여 프로그램의 자동 병렬화를 방지합니다.이러한 의존성을 제거하기 위해 사용되는 두 가지 주요 기술은 민영화와 축소이다.따라서 각 스레드에는 R/W Conflicting 변수의 복사본이 제공되어 해당 변수에서 작업하고 부분적인 결과를 생성합니다. 그런 다음 다른 스레드의 복사본과 결합하여 전역 [1]결과를 생성합니다.민영화와 유사한 또 다른 기술은 확장이라고 불리며, 스칼라 변수를 배열로 확장하여 각 스레드가 서로 다른 배열 [5]요소에 액세스하도록 합니다.확장할 변수가 배열인 경우 확장은 [6]배열에 다른 차원을 추가합니다.
민영화
의존관계(실행 중 서로 다른 스레드 간의 잠재적인 경합)는 병렬화를 방해하며 읽기/쓰기 충돌 변수가 있는 경우 이러한 경합이 발생합니다.이러한 갈등을 해소하는 방법 중 하나는 민영화이다.기본 원칙은 하나의 인스턴스를 공유하는 것이 아니라 각 스레드에 대한 변수의 개인 복사본을 만드는 것입니다.그러면 변수의 카테고리가 읽기/쓰기 충돌에서 읽기/쓰기 충돌 없음으로 변경됩니다.
읽기/쓰기 충돌 변수의 실제 로컬(프라이빗) 인스턴스는 컴파일 시 서로 다른 메모리 위치에 저장된 변수에 대해 메모리의 여러 영역을 할당하여 생성됩니다.공유 메모리 멀티프로세서의 아키텍처는 스레드가 주소 공간을 공유하기 때문에 도움이 됩니다.
변수를 민영화 가능한 것으로 설명할 수 있는 상황은 다음 두 가지가 있습니다.
- 원래 프로그램의 순차 순서에서 동일한 태스크가 변수를 읽기 전에 작성된 경우.이 경우 태스크가 공유가 아닌 개인 복사본에 쓴 경우 충돌/의존성이 제거됩니다.그 이유는 프로그램의 순차적 순서에 따라 값이 동일한 태스크에 의해 기록되고 동일한 변수에 액세스하는 다른 스레드에 의해 발생할 수 있는 충돌이 제거되기 때문입니다.§ 예 1을 참조해 주세요.
- 동일한 태스크에 의해 작성되기 전에 변수를 읽을 때.여기서의 차이는 태스크가 읽으려고 하는 값이 다른 태스크의 이전 컴퓨팅 단계에서 얻은 값이라는 것입니다.그러나 각 태스크가 자신의 개인 복사본에 기록될 경우 모든 태스크가 미리 알려진 값을 읽은 후 자신의 복사본에 올바른 값을 기록하므로 실행 중에 충돌 또는 종속성이 해결됩니다.§ 예 2를 참조해 주세요.
읽기/쓰기 충돌 변수는 병렬화를 방지하는 유일한 범주이므로 읽기 전용 및 읽기/쓰기 비 충돌 변수를 비공개로 명시적으로 선언할 필요가 없습니다.이렇게 해도 프로그램의 정확성에는 영향을 주지 않지만 불필요한 복사에 더 많은 메모리가 사용될 수 있습니다.
제한 사항
읽기/쓰기 충돌을 제거하기 위해 변수를 개인화할 수도 축소할 수도 없습니다.이 경우 읽기/쓰기 충돌 변수는 서로 다른 시점에 서로 다른 작업에 의해 업데이트되어야 합니다.§ 예 3을 참조해 주세요.
이 문제는 병렬의 범위를 변경하여 다른 병렬 영역을 탐색함으로써 해결할 수 있습니다.코드 재분석 후 일부 읽기/쓰기 충돌 변수가 읽기/쓰기 충돌 [1]없음으로 변경될 수 있으므로 좋은 결과를 얻을 수 있습니다.변수가 여전히 경합을 일으키는 경우 마지막 방법은 변수를 공유로 선언하고 상호 배제를 통해 액세스를 보호하는 것입니다.또한 변수에 대한 액세스가 지정된 순서로 이루어져야 정확한지 확인할 수 있는 경우 동기화를 제공합니다.
어레이
읽기/쓰기 충돌 변수는 스칼라 또는 배열, 매트릭스, 구조화 유형 등의 복합 유형일 수 있습니다.민영화는 두 가지 변수 모두에 적용할 수 있다.
스칼라 변수에 적용할 경우 스칼라는 [1]작기 때문에 스레드당 추가 개인 복사본을 만들 때 발생하는 추가 공간과 오버헤드는 상대적으로 작습니다.그러나 어레이, 매트릭스 또는 기타 복합 유형에 민영화를 적용하는 것은 훨씬 더 복잡합니다.
어레이를 다룰 때 컴파일러는 각 어레이 요소의 동작을 개별적으로 분석하여 읽고 쓰는 순서를 확인합니다.각 요소가 같은 반복으로 읽기 전에 작성되면 이 배열을 개인화할 수 있습니다.이를 위해 컴파일러는 어레이를 상세하게 분석하여 접근을 섹션으로 결합해야 합니다.또한 컴파일러는 어레이 요소를 조작하고 처리할 수 있도록 추가 기능을 가지고 있어야 합니다.예를 들어, 일부 배열 표현식은 심볼 용어를 가지고 있을 수 있습니다. 따라서 이러한 배열을 사유화하기 위해서는 컴파일러가 몇 가지 고급 심볼 조작 [5]함수를 가지고 있어야 합니다.
예
예 1
각 태스크가 변수를 읽기 전에 변수를 쓸 경우 변수를 개인화할 수 있습니다.이 경우 다른 스레드가 이 작업을 수행하는지 여부는 중요하지 않습니다.아래 코드에서 변수는x는 세 가지 변수 쌍을 스왑하는 데 사용됩니다.읽기 전에 반드시 쓰여져 있기 때문에, 민영화할 수 있습니다.
//순차 코드: x = a; a = b; b = x; x = c; c = d; d = x; x = e; e = f; b = x;
이 코드는 사유화하지 않으면 병렬화할 수 없습니다.x.와 함께x민영화된 것, 그것은 세 개의 다른 스레드로 실행될 수 있고, 각각은 각자의 개인 스레드를 가지고 있다.x:
//병렬 코드: //스레드 1: x[1] = a; a = b; // 스레드 2: x[2] = c; c = d; d = x[2]; // 스레드 3: x[3] = e; f = x[3];
예 2
민영화는 변수의 값이 사용되기 전에 미리 알고 있을 때 가능합니다. 다른 작업에 의해 쓰여지더라도 마찬가지입니다.다음 코드는 이를 나타냅니다.변수x각 태스크의 중간에 쓰여지지만 이 값은 프로그램 컴파일 시 계산될 수 있습니다.만드는 것으로xprivate 및 각 태스크의 시작 부분에서 이를 정의하면 코드를 병렬로 실행할 수 있습니다.
//순차 코드: x = 1; y = 3; x = 4; z = y/x; a = x 9; x = 3; b = a/x; c = x 1; x = 11; d = c/x;
위의 시퀀셜 코드를 병렬로 만들려면 코드 몇 줄을 추가해야 합니다.x민영화 가능:
//병렬 코드 //스레드 0: x[0] = 1; y = x[0] * 3; x[0] = 4; //스레드 1: x[1] = 4; a = 9; x[1] = 3; b = a/x[1] = 3; 2차 읽기
추가 코드 때문에 이 짧은 예에서는 실제로 속도가 크게 향상되지 않을 수 있습니다.그러나 실제 환경에서는 이 기법의 코드가 길수록 성능이 크게 향상될 수 있습니다.
예 3
민영화에 실패하는 것은 변수가 어떤 태스크에 쓰여지고 다른 태스크에서 읽혀지는 경우로, 값을 미리 알 수 없는 경우입니다.예를 들어 배열 요소의 합계가 있습니다.합계는 공유 변수이며 루프가 반복될 때마다 읽기/쓰기됩니다.
시퀀셜 코드에서는 정상적으로 동작합니다.그러나 반복이 각각 다른 스레드에서 수행되면 잘못된 합계가 계산됩니다.이 경우 민영화는 효과가 없다.그sum는 이전 반복의 값에 의존하기 때문에 비공개로 할 수 없습니다.
//순차 코드: 합 = 0; (i = 0; i < 100; i++) 합 += a[i];
이 문제는 루프 언롤링으로 부분적으로 해결할 수 있습니다.요소를 추가하는 순서는 중요하지 않기 때문에 루프는 임의의 수의 부품으로 분할할 수 있습니다.
끓여Thread 0:(i[0]=0;i[0]<>100;i[0]3+=)sum[0]+= a[나는 0-LSB-]해결을 위해 sum[0]=0;;//스레드로부터의 1:sum[1]=0;(i[1]=1;i[1]<>100;i[1]3+=)sum[1]+= a[나는 1-LSB-]해결을 위해;스레드로부터의 2//:sum[2]=0;(i[2]=2;i[2]<>100;i[2]3+=)sum[2]+= a[나는 2-LSB-]해결을 위해;//"마스터". wait_for_all(thread[0], thread[1], thread[2]), 합)sum[0]. +sum[1]+ 합계[2];
OpenMP
OpenMP는 공유 메모리를 사용한 멀티프로세서 프로그래밍을 지원하는 프로그래밍 언어입니다.따라서 읽기/쓰기 충돌 변수가 발생할 수 있습니다.이러한 경우 코드를 병렬로 실행할 수 있도록 민영화를 사용할 수 있습니다.
시퀀셜 코드를 지정하면:
do i = 10, N - 1 x = (b(i) + c(i)/2 b(i) = a(i + 1) + x endo
루프가 반복될 때마다x에 쓰이고 읽혀집니다.왜냐면x는 스칼라 변수일 뿐이며 루프는 다른 스레드로 덮어쓰기 때문에 병렬로 실행할 수 없습니다.b(i)올바른 [2]값이 항상 할당되는 것은 아닙니다.
민영화를 사용한 등가 병렬화된 코드는 다음과 같습니다.
!$omp parallel do shared(a, b) private(x) do i = 10, N - 1 x = (b(i) + c(i))/2 b(i) = a(i + 1) + x endo
왜냐면xprivate로 선언되어 각 스레드가 자체 복사본을 가져오고 종속성이 제거됩니다.[2]
다른 기술과의 비교
통상, 변수가 읽기/쓰기 경합하고 있는 경우는, 그 변수를 공유로 선언해, 상호 배제에 의해서 그 변수에의 액세스를 보호해, 필요에 따라서 동기를 제공합니다.상호 배제는 속도를 늦추기 때문에 이 기술은 가능한 한 피한다.
따라서 컴파일러나 프로그래머는 변수를 줄일 수 있는지 먼저 확인합니다.만약 그렇지 않다면, 다음 점검은 민영화이다.민영화는 시간과 공간을 교환하기 때문에 메모리가 제한되어 있을 때 상호 배제가 더 나은 선택이 될 수 있습니다.
감소와 비교하여 민영화는 한 가지 모델링 단계를 필요로 한다. 즉, 민영화 가능한 변수를 식별하기 위해 코드를 분석하는 것이다.한편, 감소에 필요한 두 단계는 감소 변수를 식별하고 감소 [7]연산자를 병렬화하는 것입니다.이 두 가지 기술을 각각 관찰함으로써 병렬 프로그램에 어떤 유형의 오버헤드가 추가되는지 쉽게 알 수 있습니다.절감은 계산 오버헤드를 증가시키고 사유화는 프로그램에서 [5]소비되는 메모리를 증가시킵니다.
확장에 비해 민영화는 메모리 오버헤드가 적다.민영화에 필요한 메모리 용량은 프로세서 수에 비례하지만 확장 시에는 반복 [5]횟수에 비례합니다.일반적으로 작업 수가 프로세서의 수보다 많기 때문에 확장에 필요한 메모리는 민영화보다 훨씬 큽니다.
병렬의 범위를 변경하여 다른 병렬 영역을 탐색할 수 있습니다.이렇게 하면 변수의 동작이 크게 변경될 수 있습니다.따라서 코드를 재분석하여 이 기술을 실행하면 읽기/쓰기 충돌 변수가 종종 [1]충돌하지 않음으로 변경될 수 있습니다.
「 」를 참조해 주세요.
레퍼런스
- ^ a b c d e f g h i Solihin, Yan (2015). Fundamentals of Parallel Multicore Architecture. Chapman and Hall/CRC. ISBN 978-1-4822-1118-4.[필요 페이지]
- ^ a b c Chandra, Rohit (2001). Penrose, Denise (ed.). Parallel Programming in OpenMP (PDF). Morgan Kaufmann. pp. 48, 74, 143. ISBN 978-1-55860-671-5.
- ^ Gupta, M. (1997-04-01). "On Privatization of Variables for Data-Parallel Execution". Parallel Processing Symposium, 1997. Proceedings., 11th International: 533–541. CiteSeerX 10.1.1.50.2508. doi:10.1109/IPPS.1997.580952. ISBN 978-0-8186-7793-9.
- ^ a b Ceze, Luis H. (2011-01-01). "Shared-Memory Multiprocessors". In Padua, David (ed.). Encyclopedia of Parallel Computing. Springer US. pp. 1810–1812. doi:10.1007/978-0-387-09766-4_142. ISBN 978-0-387-09765-7.
- ^ a b c d Padua, David (2011-01-01). "Parallelization, Automatic". In Padua, David (ed.). Encyclopedia of Parallel Computing. Springer US. pp. 1442–1450 – Paraphrased by Bruce Leasure. doi:10.1007/978-0-387-09766-4_197. ISBN 978-0-387-09765-7.
- ^ Tu, Peng; Padua, David (1993-08-12). "Automatic Array Privatization". In Banerjee, Utpal; Gelernter, David; Nicolau, Alex; Padua, David (eds.). Languages and Compilers for Parallel Computing. Lecture Notes in Computer Science. Springer Berlin Heidelberg. pp. 500–521. CiteSeerX 10.1.1.3.5746. doi:10.1007/3-540-57659-2_29. ISBN 978-3-540-57659-4.
- ^ Yu, Hao; Rauchwerger, Lawrence (2014-01-01). "Adaptive Reduction Parallelization Techniques". ACM International Conference on Supercomputing 25th Anniversary Volume. New York, NY, USA: ACM. pp. 311–322. doi:10.1145/2591635.2667180. ISBN 978-1-4503-2840-1.
