1.1 병렬처리의 한계와 가능성 1.2 병렬처리의 단위 1.3 병렬컴퓨터의 분류 1.4 병렬컴퓨터의 성능 척도 제1장 병렬처리의 개요 1.1 병렬처리의 한계와 가능성 1.2 병렬처리의 단위 1.3 병렬컴퓨터의 분류 1.4 병렬컴퓨터의 성능 척도

병렬처리(Parallel Processing) 다수의 프로세서들이 여러 개의 프로그램들 또는 한 프로그램의 분할된 부분들을 분담하여 동시에 처리하는 기술 컴퓨터시스템의 성능 향상을 위하여 가장 널리 사용되고 있는 방법 Parallel Computer Architecture

Parallel Computer Architecture 병렬처리의 조건 많은 수의 프로세서들로 하나의 시스템을 구성할 수 있도록 작고 저렴하며 고속인 프로세서들의 사용이 가능해야 한다  반도체 기술 발전에 따른 VLSI 칩의 개발에 의해 해결 한 프로그램을 여러 개의 작은 부분들로 분할 가능해야 하며, 분할된 부분들에 대한 병렬처리 결과가 순차적 처리의 결과와 동일해야 한다 <새로이 야기되는 과제들> 분할성(decomposability) : 한 프로그램을 여러 개로 분할 필요 복잡성(complexity) : 병렬 알고리즘의 개발 필요 프로세서간 통신(interprocessor communication) : 프로세서들간에 데이터 교환을 위한 통신 필요 Parallel Computer Architecture

Parallel Computer Architecture 1.1 병렬처리의 한계와 가능성 단일 프로세서의 속도 한계 Si 칩상의 전자 흐름 속도 = 3x107m/sec (광속도의 1/10) 지름 3cm인 칩 내 최대 전송시간 = 10-9sec  최대 계산 능력 : 109 FLOPS = 1 GFLOPS 속도 한계를 극복할 수 있는 방법  병렬처리 Parallel Computer Architecture

Parallel Computer Architecture Glosch’s law : 프로세서의 성능이 가격의 제곱에 비례하여 높아질 것으로 예측: 즉, n1/2 배의 비용만 투자해도 n배 빠른 프로세서 개발 가능 [비교] n 개의 프로세서들 사용  속도 : n 배, 비용 : n 배 여건의 변화 VLSI 기술의 발전으로 저렴한 가격의 소형 프로세서 개발 가능 Parallel Computer Architecture

Parallel Computer Architecture 병렬처리에 대한 비판적 이론 (II) Minsky’s conjecture : P개의 프로세서들을 사용한 병렬 프로세서에서 프로세서들 간의 정보 교환을 위한 통신 오버헤드 때문에, 시스템 성능은 P배가 아닌, 최대 log2P배까지만 개선될 수 있다 여건의 변화 효율적인 병렬 알고리즘들의 개발 고속 상호연결망 출현 프로세서 스케줄링 기술 개발, 등 Parallel Computer Architecture

Parallel Computer Architecture 병렬처리에 대한 비판적 이론 (III) Amdahl의 법칙(Amdahl’s law) 병렬처리를 이용하여 얻을 수 있는 속도 향상은 병렬화가 불가능한 비율(Amdahl’s fraction : a)에 의해 제한 Sp = T1 / Tp lim Sp = 1 / α p∞ [예] α = 20%  최대 Sp = 5배 α α a a a Parallel Computer Architecture

Parallel Computer Architecture Amdahl’s law (계속) 여건의 변화 대부분의 공학 및 과학 계산에서는 a가 문제의 크기(n)가 증가함에 따라 감소 lim α(n) = 0  lim Sp = p n∞ n∞ (Sp는 프로세서 수에 비례) Parallel Computer Architecture

Parallel Computer Architecture 1.2 병렬처리의 단위 작업 단위(Job level) : 독립적인 job program 단위로 병렬처리 [예] 성적관리 프로그램 // 실험 데이터 처리 프로그램 태스크 단위(Task level) : 하나의 큰 job을 기능에 따라 분할한 작은 프로그램(태스크) 단위로 병렬처리 [예] Robot 제어 프로그램 : 팔과 다리들을 제어하는 4 개의 태스크들로 분할한 후, 병렬처리  프로세서들간의 정보 교환 필요 Parallel Computer Architecture

Parallel Computer Architecture 병렬처리의 단위 (계속) 프로세스 단위(Process level) : 태스크 프로그램을 더 작게 분할한 크기인 프로세스 레벨에서의 병렬처리 [예] for i = 1, 5             x(i) = x(i-1) + y(i-1)            P1(i) y(i) = x(i-2) - y(i-1)            s(i) = x(i) + y(i)            if s(i) ≥ 100                    P2(i)               then a = a+1         else b = b+1 Parallel Computer Architecture

Parallel Computer Architecture 프로세스-단위 병렬처리의 예 P(i+1) // P2(i), P1(i) // P2(i-1), P1(i-1) // P2(i-2) Parallel Computer Architecture

Parallel Computer Architecture 병렬처리의 단위 (계속) 변수 단위(Variable level) : 독립적인 연산에 의해 계산될 수 있는 변수들 간의 병렬처리 [예] P1 내의 x(i) // y(i) 비트 단위(Bit level) : 가장 낮은 레벨의 병렬처리로서, 데이터 단어를 구성하고 있는 비트들에 대한 독립적 연산들을 병렬처리 Parallel Computer Architecture

Parallel Computer Architecture 1.3 병렬컴퓨터의 분류 1.3.1 Flynn의 분류(classification) SISD(Single Instruction stream Single Data stream) SIMD(Single Instruction stream Multiple Data stream) MISD(Multiple Instruction stream Single Data stream) MIMD(Multiple Instruction stream Multiple Data stream) Parallel Computer Architecture

Parallel Computer Architecture SISD 조직 한 번에 한 개씩의 명령어와 데이터를 순서대로 처리하는 단일 프로세서 시스템 성능 향상을 위한 프로세서 내부 구조 : 파이프라이닝(pipelining), 슈퍼 스칼라(superscalar) Parallel Computer Architecture

Parallel Computer Architecture SIMD 조직 하나의 명령어를 다수의 데이터들에 대하여 동시 실행  다수의 데이터들에 대하여 동일한 연산 수행 배열 프로세서(Array processor)라고도 부름 Parallel Computer Architecture

Parallel Computer Architecture MISD 조직 각 프로세서들은 서로 다른 명령어를 실행하지만, 처리되는 데이터들은 하나의 스트림 실제로 설계 및 구현된 사례는 없음 Parallel Computer Architecture

Parallel Computer Architecture MIMD 조직 다수의 프로세서들이 각각 다른 프로그램을 서로 다른 데이터들에 대하여 수행. 대부분의 병렬 컴퓨터들이 이 분류에 해당 밀결합 시스템(tightly-coupled system) : 프로세서들이 공유 기억장치(shared memory)를 이용하여 데이터 교환 소결합 시스템 (loosely-coupled system) : 프로세서들이 메시지 전송(message passing)을 이용하여 데이터 교환 Parallel Computer Architecture

Parallel Computer Architecture MIMD 조직 (계속) Parallel Computer Architecture

Parallel Computer Architecture 1.3.2 구조적 특징에 따른 분류 파이프라인 컴퓨터(Pipeline Computer) 시간적 병렬성(temporal parallelism)을 이용한 중첩 계산(overlapped computation)을 수행하는 시스템 배열 프로세서(Array Processor) 공간적 병렬성(spatial parallelism)을 실현하기 위하여 여러 개의 동기화 된 프로세싱 유니트(processing unit)들로 구성되는 시스템 다중프로세서시스템(Multiprocessor System) 시스템 자원들(기억장치, I/O장치)을 공유하는 여러 개의 프로세서들을 이용하여 비동기적 병렬성(asynchronous parallelism)을 실현하는 시스템 Parallel Computer Architecture

Parallel Computer Architecture 배열 프로세서와 다중프로세서의 차이점 프로그램 수행의 독립성 배열 프로세서 : 모든 프로세서들이 동일한 프로그램을 동기적으로 수행 다중프로세서시스템 : 각 프로세서들이 서로 다른 별도의 프로그램을 비동기적(독립적)으로 수행 Parallel Computer Architecture

Parallel Computer Architecture 1.3.3 기억장치 액세스 모델에 따른 분류 균일 기억장치 액세스(Uniform Memory Access: UMA) 모델 불균일 기억장치 액세스(Non-uniform Memory Access: NUMA) 모델 캐쉬-온리 기억장치 액세스(Cache-Only Memory Access: COMA) 모델 무-원격 기억장치 액세스(No-Remote Memory Access: NORMA) 모델 Parallel Computer Architecture

Parallel Computer Architecture UMA 모델 모든 프로세서들이 상호연결망에 의해 접속된 주기억장치 공유 프로세서들은 주기억장치의 어느 영역이든 액세스할 수 있으며, 그에 걸리는 시간이 동일 Parallel Computer Architecture

Parallel Computer Architecture UMA 모델 (계속) 장단점 장점: 하드웨어가 간단하고, 프로그래밍이 용이 단점: 공유 자원에 대한 경합이 높아지기 때문에 시스템 크기(프로세서 수)에 한계 [예] 최대 프로세서 수 - 공유-버스를 사용하는 시스템 : 30 개 이하, - 크로스바, MIN을 사용하는 시스템 : 64 개 이하 Parallel Computer Architecture

Parallel Computer Architecture NUMA 모델 UMA 모델의 한계를 극복하고 더 큰 규모의 시스템을 구성하기 위한 모델 다수의 UMA 모델들이 상호연결망에 의해 접속 분산 공유-기억장치 (distributed shared-memory) 구조 기억장치 액세스 시간은 기억장치의 위치에 따라 달라짐 지역 기억장치 액세스(local memory access) 전역 기억장치 액세스(global memory access) 원격 기억장치 액세스(remote memory access) Parallel Computer Architecture

Parallel Computer Architecture NUMA 모델의 일반적인 구성도 Parallel Computer Architecture

Parallel Computer Architecture COMA 모델 특징 시스템 내에 기억장치가 존재하지 않음 각 프로세서가 가지고 있는 기억장치들이 모두 캐쉬로서 동작하며, 하나의 공통 주소 공간을 가짐 다른 캐쉬에 대한 액세스는 분산 캐쉬 디렉토리(distributed cache directory)에 의해 지원 초기에는 데이터들이 임의의 캐쉬에 저장되어 있으며, 실행 시간 동안에 그 데이터를 사용할 프로세서의 캐쉬로 이동 대표적 시스템들: Data Diffusion Machine(DDM), KSR-1 Parallel Computer Architecture

Parallel Computer Architecture COMA 모델의 일반적인 구성도 Parallel Computer Architecture

Parallel Computer Architecture NORMA 모델 분산-기억장치 시스템(distributed-memory)이라고도 부름 프로세서가 원격 기억장치(remote memory)는 직접 액세스할 수 없는 시스템 구조 프로세서들과 기억장치들은 메시지-전송(message-passing)을 지원하는 상호연결망으로 접속 주요 상호연결망: 매쉬(mesh), 하이퍼큐브(hypercube), 토러스(torus), 등 Parallel Computer Architecture

Parallel Computer Architecture NORMA 모델의 일반적인 구성도 Parallel Computer Architecture

Parallel Computer Architecture 1.3.4 시스템 구성에 따른 분류 대칭적 다중프로세서(Symmetric Multiprocessor: SMP) 대규모 병렬프로세서(Massively Parallel Processor: MPP) 캐쉬-일관성 NUMA(Cache-Coherent NUMA: CC-NUMA) 시스템 분산 시스템(Distributed System) 클러스터 컴퓨터(Cluster Computer) Parallel Computer Architecture

Parallel Computer Architecture SMP 최대 수십(20~64) 개 이하의 프로세서들로 구성되는 중대형급 시스템 완전-공유 구조(shared-everything architecture) : 프로세서들이 시스템 내의 모든 자원들을 공유 시스템 내에 하나의 OS만 존재 대칭적(symmetric): 모든 프로세서들이 필요 시 직접 OS 코드 수행 모든 프로세서들이 자원들을 동등한 권한으로 사용 Parallel Computer Architecture

Parallel Computer Architecture SMP (계속) SMP의 특징 능력이 비슷한 프로세서들로 구성 프로세서들이 기억장치와 I/O 장치들을 공유하며, 상호연결망에 의해 접속 모든 프로세서들은 동등한 권한을 가지며, 같은 수준의 기능들을 수행 프로세서간 통신은 공유-기억장치를 이용 Job scheduling이 하나의 OS에 의해 통합적으로 이루어짐 공유 자원에 대한 경합으로 인하여 시스템 크기에 한계 Parallel Computer Architecture

Parallel Computer Architecture MPP 무공유 구조(shared-nothing)를 기반으로 하는 대규모 병렬처리시스템 수백 혹은 수천 개의 프로세서들로 구성 간단한 구조의 노드 프로세서 사용 마이크로-커널(micro-kernel) 수준의 노드 OS 탑재 노드들 간의 통신은 message-passing 방식 이용 복잡도 높은 상호연결망 이용 [사례 시스템] CM-5, Cray T3E, IBM BlueGene Parallel Computer Architecture

Parallel Computer Architecture CC-NUMA 독립적인 노드들(UMA 혹은 NUMA 시스템)이 상호연결망에 의해 접속 모든 노드들의 캐쉬 및 주기억장치들 사이에 데이터 일관성 유지 시스템 내의 모든 기억장치들이 전역 주소공간(global address space)을 가지는 분산 공유-기억장치 시스템(distributed shared-memory system)으로 구성 주요 장점: S/W 변경 없이 SMP보다 더 큰 시스템 구축 가능 [사례 시스템] DASH, SGI Origin, Sequent NUMA-Q Parallel Computer Architecture

Parallel Computer Architecture CC-NUMA 시스템의 일반적 구성도 Parallel Computer Architecture

Parallel Computer Architecture 분산시스템 독립적인 노드(컴퓨터시스템)들이 전통적인 네트워크에 의해 접속 노드들 간의 정보 교환 혹은 병렬처리를 수행할 때만 네트워크를 이용하여 통신 : 소결합 시스템(loosely-coupled system) 노드: PC, workstation, SMP, MPP, 혹은 그들의 조합 Parallel Computer Architecture

Parallel Computer Architecture 클러스터 컴퓨터 A collection of PCs or workstations 네트워크: 고속 LAN, 혹은 network switch 모든 시스템 자원들을 SSI(Single System Image)로 통합 주요 장점 저렴한 비용으로 병렬처리시스템 구축 가능 결함 대체 용이  가용성(availability) 향상 Parallel Computer Architecture

Parallel Computer Architecture SSI 및 scalability 비교 SSI(Single System Image) Scalability: System extendability Parallel Computer Architecture

Parallel Computer Architecture 1.4 병렬컴퓨터의 성능 척도 처리 속도에 대한 척도 MIPS(Millions of Instructions Per Second) : 초당 실행 완료되는 명령어들의 수를 나타내는 단위 1 MIPS : 초당 백만(106) 개의 명령어 실행 1 GIPS : 초당 10억 (109) 개의 명령어 실행 1 TIPS : 초당 1조 (1012) 개의 명령어 실행 M : Mega G : Giga T : Tera Parallel Computer Architecture

Parallel Computer Architecture 처리 속도에 대한 척도 (계속) MFLOPS(Millions of Floating-Point Operations Per Second) : 초당 실행 완료되는 부동-소수점 연산들의 수를 나타내는 단위 1 MFLOPS : 초당 백만(106) 번의 부동-소수점 연산 수행 1 GFLOPS : 초당 10억(109) 번의 부동-소수점 연산 수행 1 TFLOPS : 초당 1조 (1012) 번의 부동-소수점 연산 수행 주로 슈퍼컴퓨터의 성능 척도로 사용 LIPS(Logical Inferences Per Second) : 단위 시간당 처리하는 logical inference들의 수 AI 프로그램의 처리 속도를 나타내기 위해 사용 Parallel Computer Architecture

Parallel Computer Architecture 속도 향상에 대한 척도 속도 향상(speedup: Sp) : p 개의 프로세서를 가진 병렬컴퓨터가 단일프로세서시스템에 비하여 몇 배의 처리 속도를 가지는지를 나타내는 척도 Sp = T1 / Tp Sp < p 가 되는 주요 요인들 불균등 작업부하 병렬처리 오버헤드들(프로세서 동기화, 프로세서간 통신, 등) Parallel Computer Architecture

Parallel Computer Architecture 효율(efficiency) 투자 비용에 따른 효과를 나타내는 척도 속도 향상과 프로세서 수의 비율 Ep = Sp / p = T1 / p Tp Parallel Computer Architecture

Parallel Computer Architecture 중복성(redundancy) 응용 프로그램을 병렬컴퓨터에서 처리하는 경우에 수행되는 연산들의 수(Op)와 단일프로세서시스템에서의 연산들의 수(O1)의 비율 Rp = Op / O1 R p > 1 이 되는 주요 요인 : 병렬처리를 위해 추가되는 동작들(오버헤드: 프로세서 동기화 및 프로세서간 통신) Parallel Computer Architecture

시스템 이용률(system utilization) H/W resource들이 어느 정도 효율적으로 사용되는지를 나타내는 척도 프로그램 처리의 전체 시간 중 H/W 자원이 busy 상태인 시간의 비율 Up = Rp Ep = (Op/ O1 ) (T1 / p Tp) Up < 1 가 되는 주요 요인들 불균등 작업부하 데이터 전송 대기 시간 Parallel Computer Architecture

병렬처리의 질(quality of parallel processing) 병렬처리가 어느 정도 효과적으로 이루어졌는지를 나타내는 척도 속도 향상과 효율에 비례, 중복성에 반비례 Qp = Sp Ep / Rp Ep < 1, 1 < Rp < p  Qp < Sp Parallel Computer Architecture