세분화(병렬 컴퓨팅)

Granularity (parallel computing)

병렬 컴퓨팅에서 작업의 세분화(또는 낟알 크기)는 해당 작업에 의해 수행되는 작업(또는 계산)의 양을 측정하는 척도다.[1]

세분성에 대한 또 다른 정의는 다중 프로세서 또는 처리 요소 사이의 통신 오버헤드를 고려한다. 그것은 세분성을 통신 시간에 대한 계산 시간의 비율로 정의하는데, 여기서 계산 시간은 작업 계산을 수행하는 데 필요한 시간이고 통신 시간은 프로세서 간 데이터 교환에 필요한 시간이다.[2]

이(가) 계산 이고 c {\이(가) 통신 시간을 나타내는 경우 작업의 Granularity를 다음과 같이 계산할 수 있다.[2]

세분성은 대개 특정 작업에서 실행된 명령의 수에 따라 측정된다.[1] 또는, 세분성은 계산 시간과 통신 시간을 결합하여 프로그램의 실행 시간 측면에서도 지정할 수 있다.[1]

병렬의 종류

병렬과제에 의해 수행되는 작업의 양에 따라 병렬은 세 가지 범주로 분류될 수 있는데, 세 가지 범주는 미세한 결, 중간 결, 거친 결의 병렬이다.

미세한 평행도

자세한 내용은 마이크로파렐리즘을 참조하십시오.

세분화된 병렬화에서는 프로그램을 다수의 작은 작업으로 세분화한다. 이러한 작업은 많은 프로세서에 개별적으로 할당된다. 병렬 작업과 관련된 작업량이 적고 프로세서 간에 작업이 균등하게 배분된다. 따라서 미세한 병렬은 부하 분산을 용이하게 한다.[3]

각 작업이 더 적은 데이터를 처리함에 따라, 완전한 처리를 수행하는 데 필요한 프로세서의 수가 많다. 이는 결과적으로 통신 및 동기화 오버헤드를 증가시킨다.

미세한 병렬은 빠른 통신을 지원하는 아키텍처에서 가장 잘 이용된다. 통신 오버헤드가 낮은 공유 메모리 아키텍처는 미세한 병렬화에 가장 적합하다.

프로그래머는 프로그램에서 병렬을 검출하기 어렵기 때문에 미세한 병렬을 검출하는 것은 보통 컴파일러의 책임이다.[1]

(평행 컴퓨팅 영역 바깥에서) 미세한 결이 있는 시스템의 한 예는 우리 뇌에 있는 뉴런의 시스템이다.[4]

커넥션 머신(CM-2)과 J-머신(J-Machine)은 곡물 크기가 4~5μs인 미세 곡물 병렬 컴퓨터의 예다.[1]

굵은 결 평행도

굵은 결의 평행론에서는 프로그램이 큰 작업으로 나뉜다. 이 때문에 프로세서에서 대량의 연산이 이루어진다. 이로 인해 부하 불균형이 발생할 수 있으며, 특정 작업에서는 데이터의 대부분을 처리하는 반면 다른 작업에서는 유휴 상태일 수 있다. 또한 대부분의 연산이 프로세서에서 순차적으로 수행되기 때문에 거친 결절 병렬은 프로그램의 병렬화를 이용하지 못한다. 이러한 유형의 병렬 처리의 장점은 낮은 통신 및 동기화 오버헤드입니다.

메시지 전달 아키텍처는 거친 곡선의 병렬화에 적합하도록 프로세스 간에 데이터를 전달하는 데 오랜 시간이 걸린다.[1]

크레이 Y-MP는 곡물 크기가 약 20대인 굵은 곡물 병렬컴퓨터의 예다.[1]

중간곡선 평행도

중간곡선 병렬은 미세곡선과 거친곡선 병렬화에 상대적으로 사용된다. 중간 결 병렬은 미세 결 병렬보다 작업 크기와 통신 시간이 크고 거친 결 병렬 처리보다 낮다. 대부분의 범용 병렬 컴퓨터는 이 범주에 속한다.[4]

인텔 iPSC는 낟알 크기가 약 10ms인 중형 병렬 컴퓨터의 예다.[1]

예

처리해야 하는 10*10 이미지를 고려해 보십시오. 100픽셀의 처리 작업은 서로 독립적입니다.

미세한 병렬 처리: 10*10 이미지 처리를 담당하는 프로세서가 100개 있다고 가정해 보십시오. 통신 오버헤드를 무시한 100개의 프로세서는 10*10 이미지를 1회의 클럭 사이클로 처리할 수 있다. 각 프로세서는 이미지의 1픽셀에서 작업한 다음 출력을 다른 프로세서에 전달한다. 이것은 미세한 평행이론의 한 예다.

중간색 평행도: 10*10 이미지를 처리하는 프로세서가 25개라는 점을 고려하십시오. 이미지 처리에는 이제 4번의 클럭 사이클이 걸릴 것이다. 이것은 중간 그레인 평행주의 예다.

굵은 결 평행도: 또한, 프로세서를 2로 줄이면, 50번의 클럭 사이클이 소요될 것이다. 각 프로세서는 연산 시간을 증가시키는 50개의 요소를 처리해야 하지만, 데이터를 공유하는 프로세서의 수가 줄어들수록 통신 오버헤드는 감소한다. 이 사례는 굵은 결의 평행성을 예시한다.

미세곡선 : 100개 프로세서용 유사곡선 중간 회색 : 25개 프로세서용 유사 코드 굵은 회색 : 프로세서 2개에 대한 유사 코드 
공허하게 하다 본래의() {   바꾸다 (프로세서_아이디)   {     케이스 1: 계산 요소 1; 부숴뜨리다;     케이스 2: 계산 요소 2; 부숴뜨리다;     케이스 3: 계산 요소 3; 부숴뜨리다;     .     .     .     .     케이스 100: 계산 요소 100;                부숴뜨리다;   } } 
공허하게 하다 본래의() {   바꾸다 (프로세서_아이디)   {     케이스 1: 계산 요소들 1-4; 부숴뜨리다;     케이스 2: 계산 요소들 5-8; 부숴뜨리다;     케이스 3: 계산 요소들 9-12; 부숴뜨리다;     .     .     케이스 25: 계산 요소들 97-100;               부숴뜨리다;   } } 
공허하게 하다 본래의() {   바꾸다 (프로세서_아이디)   {     케이스 1: 계산 요소들 1-50;              부숴뜨리다;     케이스 2: 계산 요소들 51-100;              부숴뜨리다;   } }
계산 시간 - 1 클럭 사이클 계산 시간 - 4개의 클럭 사이클 계산 시간 - 50개의 클럭 사이클

병렬 수준

세분성은 처리 수준에 밀접하게 연관되어 있다. 프로그램은 4단계 병렬로 나눌 수 있다.

  1. 지시 수준.
  2. 루프 레벨
  3. 서브루틴 레벨 및
  4. 프로그램 레벨

명령 수준에서 가장 많은 양의 병렬 처리를 달성하고, 그 다음으로는 루프 레벨 병렬 처리를 달성한다. 지시와 루프 레벨에서 미세한 병렬 처리를 달성한다. 지시 수준의 일반적인 곡물 크기는 20개의 지시사항이고, 루프 수준의 곡물 크기는 500개의 지시사항이다.[1]

서브루틴(또는 절차) 레벨에서 곡물 크기는 일반적으로 수천 개의 지시사항이다. 중간 그레인 평행도는 서브루틴 수준에서 달성된다.[1]

프로그램 레벨에서는 프로그램의 병렬 실행이 이루어진다. 세분화는 수만 가지의 지침 범위 안에 있을 수 있다.[1] 이 수준에서는 굵은 결 평행성이 사용된다.

아래 표는 병렬 수준, 곡물 크기 및 병렬 수준 간의 관계를 보여준다.

레벨 그레인 사이즈 병렬주의
지시 수준 미세하다 가장 높은
루프 레벨 미세하다 중간
서브루틴 레벨 중간 중간
프로그램 레벨 거친 최소

세분성이 성능에 미치는 영향

세분성은 병렬 시스템의 성능에 영향을 미친다. 미세한 곡물이나 작은 일을 사용하면 평행성이 높아져 속도가 빨라진다. 그러나 동기화 오버헤드, 스케줄링 전략 등은 세분화된 작업의 성능에 부정적인 영향을 미칠 수 있다. 평행도를 높이는 것만으로 최상의 성과를 낼 수는 없다.[5]

통신 오버헤드를 줄이기 위해, 세분성을 높일 수 있다. 거친 분쇄 작업은 통신 오버헤드가 적지만 부하 불균형을 유발하는 경우가 많다. 따라서 미세한 곡선과 거친 곡선의 평행주의라는 두 극단 사이에서 최적의 성능을 얻을 수 있다.[6]

병렬 처리를 지원하는 최상의 세분성을 결정하는 데 도움이 되는 다양한 연구들이[5][7][8] 그들의 솔루션을 제안했다. 가장 좋은 곡물 크기를 찾는 것은 여러 요인에 따라 달라지며 문제마다 크게 다르다.

참고 항목

인용구

  1. ^ a b c d e f g h i j k Hwang, Kai (1992). Advanced Computer Architecture: Parallelism,Scalability,Programmability (1st ed.). McGraw-Hill Higher Education. ISBN 978-0070316225.
  2. ^ a b Kwiatkowski, Jan (9 September 2001). "Evaluation of Parallel Programs by Measurement of Its Granularity". Parallel Processing and Applied Mathematics. Lecture Notes in Computer Science. Vol. 2328. pp. 145–153. doi:10.1007/3-540-48086-2_16. ISBN 9783540437925. {{cite book}}: 누락 또는 비어 있음(도움말) ISBN 9783540480860.
  3. ^ Barney, Blaise. Introduction to Parallel Computing.
  4. ^ a b Miller, Russ; Stout, Quentin F. (1996). Parallel Algorithms for Regular Architectures: Meshes and Pyramids. Cambridge, Mass.: MIT Press. pp. 5–6. ISBN 9780262132336.
  5. ^ a b Chen, Ding-Kai; Su, Hong-Men; Yew, Pen-Chung (1 January 1990). "The Impact of Synchronization and Granularity on Parallel Systems". Proceedings of the 17th Annual International Symposium on Computer Architecture. 18 (2SI): 239–248. CiteSeerX 10.1.1.51.3389. doi:10.1145/325164.325150. S2CID 16193537.
  6. ^ Yeung, Donald; Dally, William J.; Agarwal, Anant. "How to Choose the Grain Size of a Parallel Computer". CiteSeerX 10.1.1.66.3298. {{cite journal}}: Cite 저널은 필요로 한다. journal= (도움말)
  7. ^ McCreary, Carolyn; Gill, Helen (1 September 1989). "Automatic Determination of Grain Size for Efficient Parallel Processing". Commun. ACM. 32 (9): 1073–1078. doi:10.1145/66451.66454. ISSN 0001-0782.
  8. ^ Kruatrachue, Boontee; Lewis, Ted (1 January 1988). "Grain Size Determination for Parallel Processing". IEEE Softw. 5 (1): 23–32. doi:10.1109/52.1991. ISSN 0740-7459. S2CID 2034255.