data 병렬화

Data parallelism
순차적 작업 실행과 데이터 병렬 작업 실행

데이터 병렬이란 병렬 컴퓨팅 환경에서 여러 프로세서를 병렬화하는 것입니다.데이터를 병렬로 작동하는 서로 다른 노드에 분산하는 데 초점을 맞춥니다.각 요소를 병렬로 작업함으로써 배열 및 매트릭스 같은 일반 데이터 구조에 적용할 수 있습니다.그것은 병렬의 또 다른 형태로서의 태스크 병렬과 대조된다.

n개의 요소 배열상의 데이터 병렬 작업을 모든 프로세서 간에 균등하게 분할할 수 있다.주어진 배열의 모든 요소를 합산하고 단일 추가 연산의 시간을 Ta 시간 단위로 가정합니다.시퀀셜 실행의 경우 배열의 모든 요소를 집약하기 때문에 프로세스에 걸리는 시간은 n×Ta 시간 단위입니다.한편, 이 작업을 4개의 프로세서에서 데이터 병렬 작업으로 실행하면 (n/4)×Ta + 머지 오버헤드 시간 단위로 시간이 단축됩니다.병렬 실행은 순차 실행보다 속도가 4 향상됩니다.한 가지 중요한 점은 데이터 참조의 인접성이 데이터 병렬 프로그래밍 모델의 성능을 평가하는 데 중요한 역할을 한다는 것입니다.데이터의 인접성은 캐시의 크기뿐만 아니라 프로그램에 의해 실행되는 메모리 액세스에 따라 달라집니다.

역사

데이터 병렬화 개념은 1960년대에 솔로몬 [1]기계의 개발로 시작되었다.벡터 프로세서라고도 불리는 Solomon 머신은 대규모 데이터 어레이(연속된 시간 단계로 여러 데이터에 대해 작동)에서 작업함으로써 수학적 연산의 성능을 가속화하기 위해 개발되었습니다.데이터 작업의 동시성은 단일 명령을 사용하여 동시에 여러 데이터에 대해 작동함으로써 악용되었습니다.이러한 프로세서를 '어레이 프로세서'[2]라고 부릅니다.1980년대에 이 용어는 C*와 같은 데이터 병렬 언어로 Connection Machine을 프로그래밍하기 위해 널리 사용되는 이 프로그래밍 스타일을 설명하기 위해 도입되었습니다.오늘날 데이터 병렬화는 하나의 명령을 사용하여 시공간에서 여러 데이터를 조작하는 기술을 모두 사용하는 GPU(그래픽 처리 장치)에서 가장 잘 볼 수 있습니다.

묘사

싱글 세트의 명령(SIMD)을 실행하는 멀티프로세서 시스템에서 각 프로세서가 다른 분산 데이터에 대해 동일한 태스크를 실행할 때 데이터 병렬화가 실현된다.경우에 따라서는 단일 실행 스레드가 모든 데이터에 대한 작업을 제어합니다.다른 경우에는 서로 다른 스레드가 동작을 제어하지만 동일한 코드를 실행합니다.

예를 들어, 예에서 설명한 대로 행렬 곱셈과 덧셈을 순차적으로 고려합니다.

예

아래는 두 행렬의 곱셈과 덧셈을 위한 순차적 의사 코드이며, 그 결과는 행렬에 저장됩니다.C곱셈을 위한 의사 코드는 두 행렬의 도트곱을 계산합니다.A,B결과를 출력 매트릭스에 저장합니다.C.

다음 프로그램을 순차적으로 실행했을 경우, 곱셈과 덧셈의 경우 O(3){ O {display style O(n양행의 행 길이와 열 길이를 각각 n) O( { O로 한다. 

// 행렬 곱셈 위해서 (i = 0; i < > row_length_a; i++) {       위해서 (k = 0; k < > column_length_B; k++)     {         합 = 0;         위해서 (j = 0; j < > column_length_a; j++)         {             합 += A[i][j] * B[j][k];         }         C[i][k] = 합;     } } 
// 어레이 추가 위해서 (i = 0; i < > n; i++) {     c[i] = a[i] + b[i]; }

상기 코드의 데이터 병렬화를 이용하여 계산이 루프에 의존하지 않기 때문에 보다 빠르게 실행할 수 있습니다.행렬 곱셈 코드의 병렬화는 OpenMP를 사용하여 이루어집니다.OpenMP 디렉티브인 "oMP parallel for"는 컴파일러가 for 루프의 코드를 병렬로 실행하도록 지시합니다.곱셈의 경우 행렬 A와 B를 각각 행과 열을 따라 블럭으로 나눌 수 있습니다.이를 통해 매트릭스 C의 모든 요소를 개별적으로 계산하여 작업을 병렬화할 수 있습니다.예를 들어 다음과 같습니다.m*k 프로세서를 사용하여 병렬로 실행할 경우 A[m x n] 도트 B [n x k는O ( m nk)가 아닌O () \ O ( )로 종료할 수 있습니다.

행렬 곱셈에서의 데이터 병렬화
// 병렬 행렬 곱셈 #schedule(dynamic, 1) collapse(2)에 대한 #schedulema omp 병렬 위해서 (i = 0; i < > row_length_a; i++){     위해서 (k = 0; k < > column_length_B; k++){         합 = 0;         위해서 (j = 0; j < > column_length_a; j++){             합 += A[i][j] * B[j][k];         }         C[i][k] = 합;     } }

행렬 크기가 계속 증가함에 따라 많은 프로세서가 필요하다는 것을 예에서 확인할 수 있습니다.실행 시간을 낮게 유지하는 것이 우선이지만 매트릭스 크기가 커짐에 따라 이러한 시스템의 복잡성 및 관련 비용 등 다른 제약에 직면하게 됩니다.따라서 시스템의 프로세서 수를 제한하더라도 동일한 원리를 적용하여 데이터를 더 큰 덩어리로 분할하여 두 [4]행렬의 곱을 계산할 수 있습니다.

데이터 병렬 구현에 어레이를 추가하는 경우, 중앙 처리 장치(CPU) A와 B가 2개 있는 보다 적당한 시스템을 가정해 보겠습니다.CPU A는 어레이의 상위 절반에서 모든 요소를 추가하고 CPU B는 어레이의 하위 절반에서 모든 요소를 추가할 수 있습니다.2개의 프로세서는 병렬로 동작하기 때문에 어레이 추가를 실행하는 작업은 1개의 CPU만을 사용하여 동일한 작업을 직렬로 수행하는 데 걸리는 시간의 1/2이 소요됩니다.

다음 프로그램은 의사 코드로 표현됩니다.이 프로그램은 임의의 조작을 적용합니다.foo어레이 내의 모든 요소에 대해d: 데이터 병렬 [nb 1]처리를 수행합니다. 

CPU = "a"이면 lower_limit : = 1 upper_limit : = round(d.length / 2) 그렇지 않으면 lower_limit : = round(d.length / 2) + 1 upper_limit : = d.length(i)를 1 doooo(d[i]로 설정합니다.

2개의 프로세서시스템에서 실행되는SPMD 시스템에서는 양쪽 CPU가 코드를 실행합니다.

데이터 병렬화는 처리(태스크 병렬화)가 아닌 데이터의 분산(병렬화) 특성을 강조합니다.대부분의 실제 프로그램은 태스크 병렬화와 데이터 병렬화 사이의 연속체 위에 있습니다.

병렬화를 위한 단계

시퀀셜 프로그램을 병렬화하는 프로세스는 4개의 개별 [5]단계로 나눌 수 있습니다.

유형 묘사
분해 프로그램은 태스크로 분류되며, 이는 이용 가능한 최소 동시성 단위입니다.
과제 태스크는 프로세스에 할당됩니다.
오케스트레이션 프로세스의 데이터 액세스, 통신 및 동기화.
매핑 프로세스는 프로세서에 바인드됩니다.

데이터 병렬화 vs. 태스크 병렬화

data 병렬화 태스크 병렬 처리
같은 데이터의 다른 서브셋에 대해서, 같은 조작이 실행됩니다. 동일한 데이터 또는 다른 데이터에 대해 다른 작업이 수행됩니다.
동기 연산 비동기 연산
모든 데이터 세트에서 작동하는 실행 스레드가 하나뿐이기 때문에 속도 향상은 더 중요합니다. 각 프로세서가 동일하거나 다른 데이터 세트에 대해 서로 다른 스레드 또는 프로세스를 실행하므로 속도가 느려집니다.
병렬화의 양은 입력 데이터 크기에 비례합니다. 병렬화의 양은 수행하는 독립 태스크의 수에 비례합니다.
멀티프로세서 시스템에서 최적의 부하 밸런싱을 실현하도록 설계되어 있습니다. 로드 밸런싱은 하드웨어의 가용성과 정적 및 동적 스케줄링 등의 스케줄링 알고리즘에 따라 달라집니다.

데이터 병렬화 vs. 모델 병렬화

data 병렬화 모델 병렬화
모든 스레드에 동일한 모델이 사용되지만 각 스레드에 주어진 데이터는 분할되고 공유됩니다. 모든 스레드에 동일한 데이터가 사용되며 모델은 스레드 간에 분할됩니다.
소규모 네트워크에서는 고속이지만 대규모 네트워크에서는 매우 느립니다.이는 대량의 데이터를 프로세서 간에 동시에 전송해야 하기 때문입니다. 소규모 네트워크에서는 느리고 대규모 네트워크에서는 빠릅니다.
데이터 병렬화는 어레이 및 매트릭스 계산 및 컨볼루션 뉴럴 네트워크에서 이상적으로 사용됩니다. 모델 병렬은 딥 러닝에서 응용 프로그램을 찾습니다.

[6]

혼합 데이터와 태스크 병렬 처리

데이터와 태스크의 병렬화는 동일한 애플리케이션에 대해 이들을 결합하여 동시에 구현할 수 있습니다.이를 혼합 데이터와 태스크 병렬이라고 합니다.혼합 병렬 처리에는 정교한 스케줄링 알고리즘과 소프트웨어 지원이 필요합니다.통신 속도가 느리고 프로세서 수가 [7]많을 때 가장 좋은 병렬 처리 방식입니다.

혼합 데이터와 태스크 병렬 처리에는 많은 응용 프로그램이 있습니다.특히 다음 응용 프로그램에서 사용됩니다.

  1. 혼합 데이터와 작업 병렬로 지구 기후 모델링에서 응용 프로그램을 찾습니다.대기와 해양을 나타내는 데이터 그리드를 작성함으로써 대규모 데이터 병렬연산을 실시하고 물리 프로세스의 기능 및 모델을 시뮬레이션하기 위해 태스크 병렬연산을 이용한다.
  2. 타이밍 기반 회로 시뮬레이션.데이터는 서로 다른 하위 회로 간에 분할되며 태스크의 조정을 통해 병렬화가 이루어집니다.

데이터 병렬 프로그래밍 환경

오늘날에는 다음과 같은 다양한 데이터 병렬 프로그래밍 환경을 사용할 수 있습니다.

  1. 메시지 전달 인터페이스:병렬 컴퓨터를 위한 크로스 플랫폼 메시지 전달 프로그래밍 인터페이스입니다.사용자가 C, C++ 및 Fortran에서 휴대용 메시지 전달 프로그램을 작성할 수 있도록 라이브러리 기능의 의미론을 정의합니다.
  2. Open Multi Processing[8] (Open MP): 멀티프로세서 시스템의 여러 플랫폼에서 공유 메모리 프로그래밍 모델을 지원하는 Application Programming Interface (API; 애플리케이션 프로그래밍 인터페이스)입니다.
  3. CUDA 및 오픈ACC: CUDA 및 OpenACC(각각)는 소프트웨어 엔지니어가 GPU의 컴퓨팅 유닛을 범용 처리에 사용할 수 있도록 설계된 병렬 컴퓨팅 API 플랫폼입니다.
  4. 스레딩 구성 요소 및 RaftLib:두 오픈 소스 프로그래밍 환경 모두 이기종 리소스 간에 C/C++ 환경에서 혼합된 데이터/태스크 병렬 처리를 가능하게 합니다.

적용들

데이터 병렬화는 물리학, 화학, 생물학, 재료 과학에서 신호 처리에 이르기까지 다양한 분야에서 응용되고 있습니다.과학은 분자역학,[9] 게놈 데이터의 배열 분석 및 기타 물리적 현상과 같은 모델을 시뮬레이션하기 위한 데이터 병렬화를 의미합니다.데이터 병렬 처리를 위한 신호 처리의 원동력은 비디오 인코딩, 이미지 및 그래픽 처리, 무선 통신입니다.

「 」를 참조해 주세요.

메모들

  1. ^ 일부 입력 데이터(예: 다음과 같은 경우)d.length1로 평가하여round0을 향한 반올림(이는 예에 불과하며 사용되는 반올림 유형에 대한 요구사항은 없습니다.)은 다음과 같습니다.lower_limit보다 크다upper_limit이 경우 루프가 즉시 종료되는 것으로 가정합니다(즉, 반복이 0이 됩니다).

레퍼런스

  1. ^ "The Solomon Computer".
  2. ^ "SIMD/Vector/GPU" (PDF). Retrieved 2016-09-07.
  3. ^ Hillis, W. Daniel and Steel, Guy L., 1986년 ACMDember 커뮤니케이션
  4. ^ Barney, Blaise. "Introduction to Parallel Computing". computing.llnl.gov. Retrieved 2016-09-07.
  5. ^ Solihin, Yan (2016). Fundamentals of Parallel Architecture. Boca Raton, FL: CRC Press. ISBN 978-1-4822-1118-4.
  6. ^ "How to Parallelize Deep Learning on GPUs Part 2/2: Model Parallelism". Tim Dettmers. 2014-11-09. Retrieved 2016-09-13.
  7. ^ "The Netlib" (PDF).
  8. ^ "OpenMP.org". openmp.org. Archived from the original on 2016-09-05. Retrieved 2016-09-07.
  9. ^ Boyer, L. L; Pawley, G. S (1988-10-01). "Molecular dynamics of clusters of particles interacting with pairwise forces using a massively parallel computer". Journal of Computational Physics. 78 (2): 405–423. Bibcode:1988JCoPh..78..405B. doi:10.1016/0021-9991(88)90057-5.
  10. ^ Yap, T.K.; Frieder, O.; Martino, R.L. (1998). "IEEE Xplore Document - Parallel computation in biological sequence analysis". IEEE Transactions on Parallel and Distributed Systems. 9 (3): 283–294. CiteSeerX 10.1.1.30.2819. doi:10.1109/71.674320.
  11. ^ Singh, H.; Lee, Ming-Hau; Lu, Guangming; Kurdahi, F.J.; Bagherzadeh, N.; Filho, E.M. Chaves (2000-06-01). "MorphoSys: an integrated reconfigurable system for data-parallel and computation-intensive applications". IEEE Transactions on Computers. 49 (5): 465–481. doi:10.1109/12.859540. ISSN 0018-9340.