Lecture #10 제8장 병렬컴퓨터 구조

강의 목차 8.1 병렬컴퓨터의 분류 8.2 배열 프로세서의 구조 8.3 다중프로세서시스템 구조 8.4 첨단 프로세서 구조

병렬처리 (1) 병렬처리(Parallel Processing) 병렬처리를 위한 선결 조건 다수의 프로세서들이 여러 개의 프로그램들 혹은 한 프로그램의 분할된 부분들을 분담하여 동시에 처리하는 기술 병렬처리를 위한 선결 조건 많은 수의 프로세서들로 하나의 시스템을 구성할 수 있도록 작고 저렴하며 고속인 프로세서들의 사용이 가능해야 함  반도체 기술의 발전과 VLSI 집적도 향상으로 가능해짐 한 프로그램을 여러 개의 작은 부분들로 분할하는 것이 가능해야 하며, 분할된 부분들을 병렬로 처리한 결과가 전체 프로그램을 순차적으로 처리한 경우와 동일한 결과를 얻을 수 있어야 함 Computer Architecture

병렬처리 (2) 야기되는 새로운 문제들 필요한 관련 기술들 문제 분할(problem partition) : 병렬처리를 위하여 문제(혹은 프로그램)를 여러 개로 나누는 것 프로세서간 통신(interprocessor communication) : 분할된 부분을 나누어 처리하는 프로세서간의 데이터 교환을 위해 메카니즘 필요 필요한 관련 기술들 병렬 프로그램 언어와 컴파일러의 개발 상호 배타 메커니즘(mutual exclusion mechanism) 지원 공유자원들에 대한 경합(contention)을 줄이고 이용률을 극대화할 수 있는 운영체제의 개발 Computer Architecture

8.1 병렬컴퓨터의 분류 Flynn의 분류(Flynn's classification) 구조적 특징에 따른 분류 방식 명령어 스트림(instruction stream) : 프로세서에 의해 실행되기 위하여 순서대로 나열된 명령어 코드들의 집합 데이터 스트림(data stream) : 그 명령어들을 실행하는 데 필요한 순서대로 나열된 데이터들의 집합 프로세서들이 처리하는 명령어와 데이터의 스트림(stream; 흐름)의 수에 따라 분류 단일 명령어 스트림 - 단일 데이터 스트림 (SISD) 단일 명령어 스트림 - 복수 데이터 스트림 (SIMD) 복수 명령어 스트림 - 단일 데이터 스트림 (MISD) 복수 명령어 스트림 - 복수 데이터 스트림 (MIMD) Computer Architecture

SISD(Single Instruction Single Data) 한번에 한 개씩의 명령어와 데이터를 순서대로 처리하는 단일프로세서 시스템 파이프라이닝(pipelining), 슈퍼스칼라(superscalar)구조를 이용 Computer Architecture

SIMD(Single Instruction Multiple Data) 배열 프로세서(Array Processor) 여러 개의 프로세싱 유니트(PU)들로 구성되고, PU들의 동작은 모두 하나의 제어 유니트에 의해 통제 모든 PU들은 하나의 명령어 스트림을 실행 데이터 스트림은 여러 개를 동시에 처리 Computer Architecture

MISD(Multiple Instruction Single Data) Computer Architecture

MIMD(Multiple Instruction Multiple Data) 프로세서들간의 상호작용 정도에 따라 두 가지로 분류 밀결합 시스템(tightly-coupled system) 공유-기억장치 구조(shared-memory architecture) 다중프로세서 시스템(multiprocessor system) 소결합 시스템(loosely-coupled system) 지역 기억장치(local memory)를 가진 독립적인 컴퓨터 모듈로 구성 프로세서간 통신은 메세지 전송(message-passing) 방식을 이용 다중컴퓨터 시스템(multiple-computer system) Computer Architecture

MIMD 조직의 구성도 Computer Architecture

8.2 배열 프로세서의 구조 모든 프로세싱 요소(processing element: PE)들이 하나의 제어 유니트(control unit)의 통제하에 동기적으로 동작하는 시스템 Computer Architecture

배열 프로세서 동작 원리 주요 용도 각 PE는 프로세서와 기억장치로 구성되며, 간단한 연산만 수행 호스트 컴퓨터에 접속되어서 계산전용 컴퓨터로서 사용 호스트 컴퓨터 : 일반목적용 컴퓨터로서, 프로그램을 컴파일 한 다음에 기계어 코드들을 배열 프로세서의 제어 유니트로 보내고, 계산 결과를 되돌려 받아서 저장하거나 출력하는 역할을 수행 Computer Architecture

배열 프로세서의 다른 구조 Computer Architecture

정적 상호연결망 Static interconnection network 연결 구조가 고정적 토폴로지(topology) 1차원 토폴로지 : 선형 배열(linear array) 2차원 토폴로지 : 원형(ring), 성형(star), 나무(tree), 매쉬(mesh), 시스토릭 배열(systolic array)구조 3차원 토폴로지 : 완전연결(completely connected) 구조, 코달 원형(chordal ring) 구조, 큐브 구조 Computer Architecture

정적 상호연결망의 예 (1) Computer Architecture

정적 상호연결망의 예 (2) Computer Architecture

정적 상호연결망의 예 (3) Computer Architecture

배열 프로세서 PE의 내부 구조 (1) ALU와 레지스터들로 구성 레제스터 : 데이터 레지스터들(R1,R2,R3), 주소 레지스터(A), 인덱스 레지스터(I), 데이터 전송 레지스터(T) 및 상태 플래그 레지스터(F) PE는 F=1이면 명령어 실행에 참여, F=0이면 대기 상태 제어 유니트(CU) PE 수만큼의 비트들로 구성된 마스크 레지스터(mask register) 보유 각 비트들은 F의 상태를 결정하며, 그에 따라 각 PE들은 그 명령어 사이클에서의 데이터 처리에 대한 참여 여부를 결정 Computer Architecture

배열 프로세서 PE의 내부 구조 (2) Computer Architecture

8.3 다중프로세서시스템 구조 MIMD 조직으로서, 여러 개의 프로세서들이 비동기적으로 프로그램을 실행하는 시스템 기억장치 모듈을 사용하는 (소유하는) 방식에 따른 분류 공유-기억장치 시스템(shared-memory system) 분산-기억장치 시스템(distributed-memory system) Computer Architecture

공유-기억장치 시스템 구조 밀결합 구조로서, 주기억장치가 어느 한 프로세서에 속해 있지 않고 모든 프로세서들에 의해 공유 상호연결 구조 버스(Bus) 공유-버스(shared-bus) 다중-버스(multiple-bus) 크로스바 스위치(Crossbar Switch) 다단계 상호연결망(Multistage Interconnection Network: MIN) Computer Architecture

공유-기억장치 시스템 구조의 장단점 장점 단점 프로세서들이 공통으로 사용하는 데이터들이 공유 기억장치에 저장되므로 별도의 프로세서간 데이터 교환 메커니즘이 필요하지 않음 프로그램 실행시간 동안에 각 프로세서들이 처리할 작업들을 동적으로 균등하게 할당할 수 있으므로 프로세서 이용률을 극대화할 수 있어서 시스템 효율을 높일 수 있음 단점 프로세서들과 기억장치들 간의 통로(버스 또는 상호연결망)상에 통신량이 많아지기 때문에 경합으로 인한 지연 시간이 길어질 수 있음 두 개 이상의 프로세서들이 공유자원(기억장치 모듈 또는 입출력장치)을 동시에 사용하려는 경우에 한 개 이외의 프로세서들은 대기해야 함  프로세서 수가 증가해도 선형적 성능 향상 불가능 (고속 상호연결망과 캐쉬 기억장치의 사용으로 보완) Computer Architecture

공유-버스 구조 하드웨어가 매우 간단 버스 경합으로 인한 지연 시간 증가 버스의 전송 속도를 높이거나 캐쉬를 사용하여 성능 저하를 보완 Computer Architecture

다중-버스 구조 버스 경합을 줄이기 위하여 버스의 수를 증가 계층버스 구조(hierarchical bus structure) : 용도가 다른 여러 계층의 버스들을 사용 Computer Architecture

크로스바 스위치(crossbar switch) 프로세서들과 기억장치들 사이의 완전 연결성(full connectivity) 비용이 많이 들고 하드웨어가 복잡 Computer Architecture

다단계 상호연결망 크로스바 스위치의 기본 개념을 이용하면서도 하드웨어 복잡성을 감소시킨 상호연결망 예 - 오메가 네트워크(Omega network) Computer Architecture

오메가 네트워크 입력단과 출력단이 각각 N 개인 경우 스위칭 소자의 접속 방식(connection mode) 필요한 단계(stage)의 수 s = log2N 각 단계의 스위칭 소자(switching element)들의 수 m = N/2 스위칭 소자의 접속 방식(connection mode) 직진(straight) : 같은 위치의 입출력 단자들이 서로 접속 교차(swap) : 서로 다른 위치의 입출력 단자들이 접속 하위 방송(lower broadcast) : 하단의 입력단자가 모든 출력단자들로 접속 상위 방송(upper broadcast) : 상단의 입력단자가 모든 출력단자들로 접속 Computer Architecture

상호 연결 방식 (일대일 연결) 근원지 노드(source node)의 주소를 SRC, 목적지 노드(destination node)의 주소를 DST라고 할 때 SRC = sn-1, …, s1, s0 DST = dn-1, …, d1, d0 만약 di ≠ si 이면, i번째 단계의 스위치는 교차 접속 만약 di ＝ si 이면, i번째 단계의 스위치는 직진 접속 Computer Architecture

일대일 연결에서 경로설정 예 SRC = 1 (001)과 DST = 7 (111) 사이의 경로 설정 (s2 = 0)  (d2 = 1) = 1 이므로, 스위치 B  교차 접속 (s1 = 0)  (d1 = 1) = 1 이므로, 스위치 H  교차 접속 (s0 = 1)  (d0 = 1) = 0 이므로, 스위치 L  직진 접속 Computer Architecture

여러 경로들의 동시 설정 예 근원지 노드와 목적지 노드 사이에 설정되는 경로들을 순열로 표현  p1 = (0,7,6,4,2) (1,3) (5) 노드 0  노드 7, 노드 7  노드 6, 노드 6  노드 4, 노드 4  노드 2, 노드 2  노드 0, 노드 1  노드 3, 노드 3  노드 1, 노드 5  노드 5 Computer Architecture

방송 접속 (broadcast connection) 하나의 근원지 노드로부터 여러 개 또는 모든 노드들로 데이터를 전송하기 위하여 사용 방송 접속을 포함한 제어 신호와 스위치의 구성 Computer Architecture

방송 전송의 예 Computer Architecture

분산-기억장치 시스템 구조 소결합 구조(loosely-coupled structure) 각 프로세서가 자신의 지역 기억장치(local memory)를 소유 다른 프로세서들과의 통신은 메세지 전송(message-passing) 이용 장점 - 공유자원에 대한 경합 감소 단점 - 통신 프로토콜에 의한 지연 시간 증가 네트워크 지름(network diameter) : 네트워크 내에서 가장 멀리 떨어져 있는 노드들 간의 거리(즉, 링크의 수) Computer Architecture

선형 배열(linear array) 구조 네트워크 지름이 N-1로서, 다른 구조들에 비하여 가장 길다 버스 구조 보다 동시성이 더 높다 통신 시간이 노드들 간의 거리에 따라 서로 다르며, 노드의 수가 많아지면(N이 커지면) 통신 시간이 매우 길어진다 Computer Architecture

원형(ring) 구조 네트워크 지름 각 링크가 양방향성(bi-directional)이면  N/2  단방향성(uni-directional)이면 N-1 변형 구조: 코달 원형(chordal ring) 링크의 수가 증가될수록 네트워크 지름은 감소 d(degree) : 각 노드가 가지는 링크의 수 Computer Architecture

원형 구조와 코달 원형 구조 Computer Architecture

2진 나무(binary tree) 구조 층(level)의 수를 k라고 할 때 N=(2k-1)개의 노드들이 접속 시스템 요소들의 수가 증가함에 따라 성능이 선형적으로 향상 Computer Architecture

패트 트리(fat tree) 구조 상위 층으로 올라갈수록 노드간의 통신 채널 수가 증가하는 구조 트리 구조에서 상위 층으로 올라갈수록 통신량이 많아져서 채널이 병목이 되는 문제점을 해결 Thinking Machine 사의 CM-5시스템에서 실제 사용 Computer Architecture

매쉬 구조(mesh network) Illiac IV, MPP, DAP, CM-2 및 Intel Paragon에서 사용 Computer Architecture

토러스 네트워크(torus network) 원형 구조와 매쉬 구조가 혼합된 구조로 확장이 용이 n×n 토러스의 경우에 네트워크 지름은 2 n / 2  Computer Architecture

큐브 네트워크(cube network) (1) 상호연결 함수 Ci(bm-1 bm-2 ... bi+1 bi bi-1 ... b1 b0) = bm-1 ... Bi’ ... b0 단, m = log2N, N: 전체 노드 수, 0 ≤ i 〈 m C0 연결 C0(b2 b1 b0) = b2 b1 b0’ Computer Architecture

큐브 네트워크(cube network) (2) C1(b2 b1 b0) = b2 b1’ b0 Computer Architecture

큐브 네트워크(cube network) (3) C1(b2 b1 b0) = b2‘ b1 b0 Computer Architecture

3차원 큐브 구조의 접속도 큐브의 차원 수를 n이라 할 때, 전체 노드의 수는 2n 개 Computer Architecture

Shuffle-exchange 네트워크 (1) shuffle 함수 : S(bm-1 bm-2 ... b1 b0) = bm-2 bm-3 ... b1 b0 bm-1 Computer Architecture

Shuffle-exchange 네트워크 (2) E(bm-1 bm-2 ... b1 b0) = bm-1 bm-2 ... b1 b0’ N=8인 경우의 전체 접속도 Computer Architecture

8.4 첨단 프로세서 구조 슈퍼스칼라(superscalar) 구조 프로세서 내에 파이프라인된 기능 유니트(functional unit; ALU 또는 명령어 실행 유니트)를 여러 개 포함시켜서, 매 사이클마다 한 개 이상의 명령어들이 동시에 처리될 수 있도록 하는 구조 4단계 파이프라인, 슈퍼스칼라 정도가 2인경우의 예 단계 1 : 명령어 인출(instruction fetch: IF) 단계 2 : 명령어 해독(instruction decode: ID) 단계 3 : 연산 수행(EX) 단계 4 : 연산 결과 저장(writeback: WB) Computer Architecture

파이프라인과 슈퍼스칼라 방식의 비교 Computer Architecture

슈퍼스칼라(superscalar) 구조 두 명령어들 사이에 데이터 의존성이 존재하지 않아야 그들을 동시에 실행 가능 k 개의 단계들로 구성된 일반적인 파이프라인 프로세서에서 N 개의 명령어들을 실행하는 데 걸리는 시간 m 개의 기능 유니트들을 가진 슈퍼스칼라 프로세서에서 N 개의 명령어들을 실행하는 데 걸리는 전체 시간 여기서, m : 슈퍼스칼라 정도(degree of superscalar) Computer Architecture

슈퍼스칼라(superscalar) 구조 일반적인 파이프라인 프로세서에 비하여 슈퍼스칼라 프로세서로 얻을 수 있는 속도 향상(speedup: Sp) N → ∞ 이면, Sp → m Computer Architecture

펜티엄 프로세서의 내부 구조 Computer Architecture

VLIW(Very Long Instruction Word) 구조 프로세서는 여러 개의 기능 유니트들을 포함 컴파일러가 동시에 실행될 수 있는 연산을 가진 명령어들을 찾아서 하나의 명령어 코드 내에 재배열 슈퍼스칼라와 다른 점 인출과 해독은 한 회로에 의해 수행, 실행 사이클만 여러 개의 기능 유니트들로 나누어져 동시에 처리 Multiflow사의 TRACE 시스템 TRACE-7 시스템 : 기능 유니트의 수 = 7, 명령어 길이 = 256 비트 TRACE-28 시스템 : 기능 유니트의 수 = 28, 명령어 길이 = 1024 비트 Computer Architecture

VLIW 프로세서와 명령어 형식의 예 네 개의 기능 유니트들을 가진 VLIW 프로세서와 명령어 형식 Computer Architecture

VLIW 프로세서의 실행 시간 흐름도 Computer Architecture

슈퍼파이프라인(super-pipeline) 구조 각 단계를 두 개 혹은 그 이상으로 분할 슈퍼파이프라이닝의 정도(degree of superpipelining)가 n인 기능 유니트의 클럭 사이클 시간은 기본 사이클의 1/n n = 2인 슈퍼파이프라인에서의 명령어 실행 시간도 Computer Architecture

슈퍼파이프라인(superpipeline) 구조 단계의 수가 k인 슈퍼파이프라인 구조에서 N 개의 명령어들을 실행하는 데 걸리는 시간 슈퍼파이프라인에 의한 속도 향상 N → ∞이면, Sp → n Computer Architecture

Superpipelined Superscalar 구조 슈퍼파이프라인과 슈퍼스칼라가 결합된 구조 최근 대부분의 고성능 프로세서들에서 사용 n = 2, m =3 인 프로세서의 명령어 실행 시간도 Computer Architecture

Superpipelined Superscalar 구조 n = 2, m =3 일때 N 개의 명령어들을 실행하는 데 걸리는 시간 속도 향상 N → ∞이면, Sp → m n Computer Architecture