자동 병렬화

Automatic parallelization

자동병렬화, 자동병렬화 또는 자동병렬화는 공유메모리 멀티프로세서([1]SMP) 머신에서 여러 프로세서를 동시에 사용하기 위해 시퀀셜 코드를 멀티스레드 또는 벡터화된 코드로 변환하는 것을 말합니다.시퀀셜 프로그램의 완전 자동 병렬화는 복잡한 프로그램 분석이 필요하며, 최상의 접근법은 [2]컴파일 시 알려지지 않은 파라미터 값에 의존할 수 있기 때문에 어려운 과제입니다.

일반적으로 프로그램 실행 시간의 대부분은 어떤 형태의 루프 안에서 발생하기 때문에 자동평형화가 가장 중점을 두는 프로그래밍 제어 구조는 루프입니다.루프 병렬화에는 파이프라인 멀티스레딩과 사이클릭 멀티스레딩의 [3]두 가지 주요 접근법이 있습니다.예를 들어, 반복마다 100번의 연산을 적용하고 1000번의 반복을 실행하는 루프를 생각해 보겠습니다.이것은 100개의 열, 1000개의 행, 총 100,000개의 연산이 있는 그리드로 생각할 수 있습니다.순환 멀티스레딩은 각 행을 다른 스레드에 할당합니다.파이프라인 멀티스레딩은 각 열을 다른 스레드에 할당합니다.

자동 병렬화 기술

해석

이것은 스캐너가 입력 소스 파일을 읽어 모든 정적 및 외부 사용을 식별하는 첫 번째 단계입니다.파일 내의 각 행은 토큰으로 분리하기 위해 미리 정의된 패턴과 대조됩니다.이러한 토큰은 나중에 문법 엔진에서 사용할 파일에 저장됩니다.문법 엔진은 미리 정의된 규칙과 일치하는 토큰 패턴을 검사하여 코드 내의 변수, 루프, 제어문, 함수 등을 식별합니다.

분석하다

분석기는 동시에 실행할 수 있는 코드 섹션을 식별하는 데 사용됩니다.분석기는 스캐너 파서가 제공하는 정적 데이터 정보를 사용합니다.분석기는 먼저 완전히 독립적인 모든 기능을 찾아 개별 작업으로 표시합니다.그런 다음 분석기는 종속성이 있는 작업을 찾습니다.

스케쥴

스케줄러는 실행 및 시작 시간과 관련하여 모든 작업과 각 작업의 상호 종속성을 나열합니다.스케줄러는 사용하는 프로세서의 수 또는 애플리케이션의 총 실행 시간의 관점에서 최적의 스케줄을 작성합니다.

코드 생성

스케줄러는 모든 태스크와 해당 태스크가 실행되는 코어의 상세 목록과 실행 시간을 생성합니다.코드 생성기는 스케줄러가 실행하는 동안 읽을 코드에 특수 구성을 삽입합니다.이러한 구성은 스케줄러에게 특정 작업이 어떤 코어로 실행되는지 시작 및 종료 시간과 함께 지시합니다.

사이클릭 멀티스레딩

사이클릭 멀티스레딩 병렬화 컴파일러는 각 반복이 다른 프로세서 상에서 동시에 실행될 수 있도록 루프를 분할하려고 한다.

컴파일러 병렬화 분석

컴파일러는 보통 다음 사항을 확인하기 위해 실제 병렬화 전에 두 번의 분석을 수행합니다.

  • 루프를 평행하게 해도 안전합니까?이 질문에 답하려면 정확한 종속성 분석과 별칭 분석이 필요합니다.
  • 평행하게 하는 것이 가치가 있을까요?이 답변에는 프로그램 워크로드와 병렬 시스템의 용량을 신뢰할 수 있는 추정(모델링)해야 합니다.

컴파일러의 첫 번째 패스는 루프의 데이터 의존성 분석을 실행하여 루프의 각 반복이 다른 것과 독립적으로 실행될 수 있는지 여부를 판단합니다.데이터 의존성은 때때로 대처할 수 있지만 메시지 전달, 공유 메모리의 동기화 또는 기타 프로세서 통신 방법의 형태로 추가적인 오버헤드가 발생할 수 있습니다.

두 번째 패스는 병렬화 후의 코드의 이론적인 실행 시간과 코드의 순차적인 실행 시간을 비교하여 병렬화 노력을 정당화하려고 시도한다.다소 반직관적으로 코드는 병렬 실행의 이점을 항상 얻을 수 있는 것은 아닙니다.여러 프로세서를 사용할 경우 추가 오버헤드는 병렬화된 코드의 잠재적인 속도 향상을 잠식할 수 있습니다.

예

루프는 특정 호출에서 모든 반복을 동시에 실행할 수 있는 경우 DOALL이라고 불립니다.

아래의 Fortran 코드는 DOALL이며, 각 반복은 서로 독립적이고 배열의 최종 결과는 독립적이기 때문에 컴파일러에 의해 자동 병렬화될 수 있습니다.z다른 반복의 실행 순서에 관계없이 올바르게 됩니다. 

   하다i = 1, n      z(i) = x(i) + y(i)    끝내다

DOALL 루프를 가진 많은 병렬 문제가 있습니다.예를 들어, 레이트레이스 무비를 렌더링 할 때, 무비의 각 프레임을 독립적으로 렌더링 할 수 있고, 단일 프레임의 각 화소를 독립적으로 렌더링 할 수 있다.

한편, 다음 코드는 자동 병렬화할 수 없습니다. 왜냐하면 값은z(i)이전 반복의 결과에 따라 달라집니다.z(i - 1).

   하다i = 2, n      z(i) = z(i - 1)*2    끝내다

이것은 코드를 병렬화할 수 없다는 것을 의미하지 않습니다.실제로는 DOALL 루프와 동등합니다.

   하다i = 2, n      z(i) = z(1)*2**(i - 1)    끝내다

그러나 현재의 병렬화 컴파일러는 보통 이러한 병렬화를 자동으로 실행할 수 없기 때문에 이 코드가 우선 병렬화의 이점을 얻을 수 있을지는 의문입니다.

파이프라인 멀티스레딩

주요 기사: 소프트웨어 파이프라인화

파이프라인 멀티스레딩 병렬화 컴파일러는 루프 내의 연산 시퀀스를 일련의 코드 블록으로 분할하여 각 코드 블록이 다른 프로세서 상에서 동시에 실행되도록 시도한다.

이와 같이 비교적 독립된 코드 블록, 특히 파이프와 필터를 사용하는 시스템이 갖는 많은 병렬 문제가 있습니다.

예를 들어 라이브브로드캐스트TV를 제작할 때는 다음 작업을 1초에 여러 번 수행해야 합니다.

  1. 이미지 센서에서 원시 픽셀 데이터 프레임을 읽습니다.
  2. 원시 데이터에 대해 MPEG 모션 보정을 수행합니다.
  3. 엔트로피는 움직임 벡터와 다른 데이터를 압축합니다.
  4. 압축된 데이터를 패킷으로 분할합니다.
  5. 적절한 오류 수정을 추가하고 FFT를 실행하여 데이터 패킷을 COFDM 신호로 변환합니다.
  6. COFDM 신호를 TV 안테나로 전송합니다.

파이프라인 멀티스레딩 병렬화 컴파일러는 이들 6가지 조작을 각각 다른 프로세서(수축기 배열로 배열)에 할당하여 프로세서의 출력을 다음 프로세서로 전송하기 위한 적절한 코드를 삽입할 수 있습니다.

최근의 연구는 GPU와[4] 멀티코어[5] 시스템의 힘을 사용하여 런타임에 이러한 독립된 코드 블록(또는 단순히 루프의 독립된 반복)을 계산하는 데 초점을 맞추고 있습니다.액세스되는 메모리(직접 또는 간접)는 루프의 다른 반복에 대해 마킹할 수 있으며 의존성 검출에 대해 비교할 수 있습니다.이 정보를 이용하여 동일한 레벨에 속하는 반복이 서로 독립적이 되도록 반복을 그룹화하여 병렬로 실행할 수 있도록 한다.

애로

컴파일러 또는 툴에 의한 자동 병렬화는 다음과 같은 [6]이유로 매우 어렵습니다.

  • 의존성 분석은 컴파일 시 이러한 의존성을 검출하기 어렵기 때문에 간접 어드레싱, 포인터, 재귀 또는 간접 함수 호출을 사용하는 코드에 대해서는 어렵습니다.
  • 루프의 반복 횟수를 알 수 없습니다.
  • 메모리 할당, I/O 및 공유 변수 측면에서 글로벌 리소스에 대한 액세스는 조정하기가 어렵습니다.
  • 입력 의존적 간접을 사용하는 불규칙한 알고리즘은 컴파일 시간 분석 및 [7]최적화를 방해합니다.

회피책

완전 자동 병렬화의 본질적인 어려움으로 인해 병렬 프로그램을 보다 높은 품질로 얻기 위한 몇 가지 쉬운 접근법이 존재합니다.그 중 하나는 프로그래머가 프로그램에 힌트를 추가하여 분산 메모리 시스템의 HPF, 공유 메모리 시스템의 OpenMP 또는 OpenHMPP와 같은 컴파일러 병렬화를 안내하는 것입니다.또 다른 접근법은 프로그래머와 병렬화 도구/컴파일러 간의 인터랙티브 시스템을 구축하는 것입니다.대표적인 예로는 Vector Fabrics의 Pareon, SUIF Explorer(스탠포드 대학 중급 포맷 컴파일러), Polaris 컴파일러 및 ParaWise(공식적으로 CAPTools)가 있습니다.마지막으로 하드웨어가 지원하는 투기성 멀티스레딩도 있습니다.

컴파일러 및 도구 병렬화

다음 항목도 참조하십시오.자동 병렬화 도구

자동 병렬화를 위한 대부분의 연구 컴파일러는 Fortran 프로그램을 [citation needed]고려합니다. 왜냐하면 Fortran은 C와 같은 언어보다 앨리어싱에 대해 더 강력한 보증을 하기 때문입니다.대표적인 예는 다음과 같습니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Yehezkael, Rafael (2000). "Experiments in Separating Computational Algorithm from Program Distribution and Communication" (PDF). Applied Parallel Computing. New Paradigms for HPC in Industry and Academia. Lecture Notes in Computer Science. Vol. 1947. Springer Verlag. pp. 268–278. doi:10.1007/3-540-70734-4_32. ISBN 978-3-540-41729-3.
  2. ^ Fox, Geoffrey; Williams, Roy; Messina, Paul (1994). Parallel Computing Works!. Morgan Kaufmann. pp. 575, 593. ISBN 978-1-55860-253-3.
  3. ^ Campanoni, Simone; Jones, Timothy; Holloway, Glenn; Wei, Gu-Yeon; Brooks, David (2012). The HELIX Project: Overview and Directions.
  4. ^ Anantpur, J.; Govindarajan, R. "Runtime dependence computation and execution of loops on heterogeneous systems" (PDF). Archived from the original (PDF) on 6 October 2015. Retrieved 5 October 2015.
  5. ^ Zhuang, X.; Eichenberger, A. E.; Luo, Y.; O'Brien, Kathryn Kevin, Exploiting Parallelism with Dependence-Aware Scheduling
  6. ^ "Automatic parallelism and data dependency". Archived from the original on 14 July 2014.
  7. ^ Rünger, Gudula (2006). "Parallel Programming Models for Irregular Algorithms". Parallel Algorithms and Cluster Computing. Lecture Notes in Computational Science and Engineering. 52: 3–23. doi:10.1007/3-540-33541-2_1. ISBN 978-3-540-33539-9.

추가 정보

  • Pountain, 딕(1989년 12월)."병렬 프로그램, 제1부:구성 그의 철학자. Transpiler, 현재 개발 중에서 병렬 처리를 위해 글을 쓰고 소프트웨어 더 쉽게 만들 것이다".BYTE.Vol14, 안돼.13.맥그로힐사를 대신하여 서명함. 349–352.ISSN 0360-5280. 궤:/13960/t34188734.1월 6일 2022.Retrieved(NB. source-to-source 컴파일러 인풋과 함께link-to-channel 과제들 그것에 병렬 처리도 possib이 효율적 실행할 것이 구성 추가 등 출력으로 새로운 occam 소스 코드 파생되는 정상적인 occam 프로그램이 걸리는 pre-processor로서 일을 할 것을 동의어로 용어의 철학자. transpiler를 사용합니다.르 transpu의 네트워크에.ters)