제8장 병렬컴퓨터 구조

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

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

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

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

그림 8-1. Flynn의 분류 방식에 따른 컴퓨터 시스템의 구성도

그림 8-1(계속)

SISD 조직 SIMD 조직 MISD 조직 한 번에 한 개씩의 명령어와 데이터를 순서대로 처리하는 단일프로세서 시스템 파이프라이닝(pipelining), 슈퍼스칼라(superscalar)구조를 이용 SIMD 조직 배열 프로세서(array processor) 여러 개의 프로세싱 유니트(PU)들로 구성되고, PU들의 동작은 모두 하나의 제어 유니트에 의해 통제 모든 PU들은 하나의 명령어 스트림을 실행 데이터 스트림은 여러 개를 동시에 처리 MISD 조직 n 개의 프로세서들이 서로 다른 명령어들을 실행하지만, 처리하는 데이터 스트림은 한 개. 비현실적인 조직: 실제 구현된 경우는 없음.

MIMD 조직 n 개의 프로세서들이 서로 다른 명령어들과 데이터들을 처리 프로세서들간의 상호작용 정도에 따라 두 가지로 분류 밀결합 시스템(tightly-coupled system): 공유-기억장치 구조(shared-memory architecture)를 가지고 있으며, 다중프로세서 시스템(multiprocessor system)이라고도 부름. 소결합 시스템(loosely-coupled system): 지역 기억장치(local memory)를 가진 독립적인 컴퓨터 모듈로 구성되며, 프로세서간 통신은 메세지 전송(message-passing) 방식을 이용한다. 다중컴퓨터 시스템(multiple-computer system)이라고도 부름.

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

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

주요 용도: 호스트 컴퓨터에 접속되어서 계산전용 컴퓨터로서 사용. 동작 원리 각 PE는 프로세서와 기억장치로 구성되며, 간단한 연산만 수행 제어 유니트는 명령어들을 해석하고, 그것이 실행될 PE들을 결정 주요 용도: 호스트 컴퓨터에 접속되어서 계산전용 컴퓨터로서 사용. 호스트 컴퓨터: 일반목적용 컴퓨터로서, 프로그램을 컴파일한 다음에 기계어 코드들을 배열 프로세서의 제어 유니트로 보내고, 계산 결과를 되돌려 받아서 저장하거나 출력하는 역할을 수행. 정적 상호연결망(static interconnection network) [특징] 연결 구조가 고정적. 1차원 토폴로지 : 선형 배열(linear array) 2차원 토폴로지 : 원형(ring), 성형(star), 나무(tree), 매쉬(mesh), 시스토릭 배열(systolic array)구조 3차원 토폴로지 : 완전연결(completely connected) 구조, 코달 원형(chordal ring) 구조, 큐브 구조

그림 8-4. 정적 상호연결망

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

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

MIMD 조직으로서, 여러 개의 프로세서들이 비동기적으로 프로그램을 실행하는 시스템. 기억장치 모듈을 사용하는 (소유하는) 방식에 따른 분류 공유-기억장치 시스템(shared-memory system) 분산-기억장치 시스템(distributed-memory system) 8.3.1 공유-기억장치 시스템의 구조 밀결합 구조로서, 주기억장치가 어느 한 프로세서에 속해 있지 않고, 모든 프로세서들에 의해 공유됨.

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

1) 버스 구조 하드웨어가 매우 간단 버스 경합으로 인한 지연 시간 증가 버스의 전송 속도를 높이거나 캐쉬를 사용하여 성능 저하를 보완 그림 8-6. 공유-버스 다중프로세서 시스템의 구조

2) 다중-버스(multiple-bus) 구조 버스 경합을 줄이기 위하여 버스의 수를 증가 계층버스 구조(hierarchical bus structure): 용도가 다른 여러 계층의 버스들을 사용. 그림 8-7. 계층버스 구조를 가진 다중프로세서 시스템의 구조

3) 크로스바 스위치(crossbar switch) 프로세서들과 기억장치들 사이에 완전 연결성(full connectivity) 제공 비용이 많이 들고 하드웨어가 복잡 그림 8-8. 크로스바 스위치를 이용한 시스템 구조

4) 다단계 상호연결망(Multistage Interconnection Network: MIN) 크로스바 스위치의 기본 개념을 이용하면서도 하드웨어 복잡성을 감소시킨 상호연결망. [예] 오메가 네트워크(Omega network) 그림 8-9. 오메가 네트워크의 구조

스위칭 소자의 접속 방식(connection mode) 필요한 단계(stage)의 수(s) s = log2N (8-1) 각 단계의 스위칭 소자(switching element)들의 수(m) m = N/2 (8-2) 스위칭 소자의 접속 방식(connection mode) 직진(straight): 같은 위치의 입출력 단자들이 서로 접속되는 방식. 교차(swap): 서로 다른 위치의 입출력 단자들이 접속되는 방식. 하위 방송(lower broadcast): 하단의 입력 단자가 모든 출력 단자들로 접속되는 방식. 상위 방송(upper broadcast): 상단의 입력 단자가 모든 출력 단자들로 접속되는 방식. 그림 8-10. 스위칭 소자의 접속 방식들

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

[예제 8-1] SRC = 1 (001)과 DST = 7 (111) 사이의 경로 설정 ------------ (s2 = 0)  (d2 = 1) = 1 이므로, 스위치 B → 교차 접속 (s1 = 0)  (d1 = 1) = 1 이므로, 스위치 H → 교차 접속 (s0 = 1)  (d0 = 1) = 0 이므로, 스위치 L → 직진 접속 그림 8-11. 노드 1과 노드 7 사이에 설정된 경로 -----------------------------------------------------------------------------------------

여러 경로들의 동시 설정의 예 근원지 노드와 목적지 노드 사이에 설정되는 경로들을 순열로 표현 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 그림 8-12. 오메가 네트워크에서 8 개의 경로들이 동시에 설정된 경우

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

그림 8-14. 6번 노드가 모든 목적지 노드들로 데이터를 전송하는 예.

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

1) 선형 배열(linear array) 구조 버스 구조 보다 동시성이 더 높다. 통신 시간이 노드들 간의 거리에 따라 서로 다르며, 노드의 수가 많아지면(N이 커지면) 통신 시간이 매우 길어진다. 그림 8-15. 선형 배열 구조.

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

그림 8-16. 원형 구조와 코달 원형 구조.

3) 나무 구조 2진 나무(binary tree) 구조 3) 나무 구조 2진 나무(binary tree) 구조 층(level)의 수를 k라고 할 때 N = (2k-1)개의 노드들이 접속 네트워크 지름 = 2(k-1) 시스템 요소들의 수가 증가함에 따라 성능이 선형적으로 향상 그림 8-17. 2진 나무 구조.

살찐 나무(fat tree) 구조 상위 층으로 올라갈수록 노드간의 통신 채널 수가 증가하는 구조 나무 구조에서 상위 층으로 올라갈수록 통신량이 많아져서 채널이 병목이 되는 문제점을 해결 Thinking Machine 사의 CM-5시스템에서 실제 사용 그림 8-18. 2진 fat tree 구조.

4) 매쉬 구조(mesh network) Illiac IV, MPP, DAP, CM-2 및 Intel Paragon과 같은 시스템들에서 사용 그림 8-19. 매쉬 네트워크의 기본 구조.

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

5) 큐브 네트워크(cube network) 상호연결 함수 Ci(bm-1 bm-2 ... bi+1 bi bi-1 ... b1 b0) = bm-1 ... Bi’ ... b0 (8-3) 단, m = log2N, N: 전체 노드 수, 0 ≤ i 〈 m 가) C0 연결 C0(b2 b1 b0) = b2 b1 b0’ 그림 8-21. C0 연결 함수의 적용 결과 및 접속도.

나) C1 연결 C1(b2 b1 b0) = b2 b1’ b0 그림 8-22. C1 연결 함수의 적용 결과 및 접속도.

다) C2 연결 C2(b2 b1 b0) = b2’ b1 b0 그림 8-23. C2 연결 함수의 적용 결과 및 접속도.

큐브의 차원 수를 n이라 할 때, 전체 노드의 수는 2n 개 그림 8-24. 3차원 큐브 구조의 접속도.

(6) Shuffle-exchange 네트워크 S(bm-1 bm-2 ... b1 b0) = bm-2 bm-3 ... b1 b0 bm-1 그림 8-25. Shuffle 함수에 의한 노드간 연결 관계.

E(bm-1 bm-2 ... b1 b0) = bm-1 bm-2 ... b1 b0’ Exchange 함수 E(bm-1 bm-2 ... b1 b0) = bm-1 bm-2 ... b1 b0’ 그림 8-26. Exchange 함수에 의한 노드간 접속도. N=8인 경우의 전체 접속도 그림 8-27. Shuffle-exchange 네트워크의 접속도.

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

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

그림 8-28. 일반적인 파이프라인과 슈퍼스칼라 방식의 비교

두 명령어들 사이에 데이터 의존성이 존재하지 않아야 그들을 동시에 실행 가능 k 개의 단계들로 구성된 일반적인 파이프라인 프로세서에서 N 개의 명령어들을 실행하는 데 걸리는 시간 (8-6) m 개의 기능 유니트들을 가진 슈퍼스칼라 프로세서에서 N 개의 명령어들을 실행하는 데 걸리는 전체 시간 (8-7) 여기서, m : 슈퍼스칼라 정도(degree of superscalar) 일반적인 파이프라인 프로세서에 비하여 슈퍼스칼라 프로세서로 얻을 수 있는 속도 향상(speedup: Sp) (8-8) N → ∞이면, Sp → m

[사례] 펜티움 프로세서 그림 8-29. 펜티움 프로세서의 내부 구조

8.4.2 VLIW(Very Long Instruction Word) 구조 프로세서는 여러 개의 기능 유니트들을 가지고 있다. 컴파일러가 동시에 실행될 수 있는 연산을 가진 명령어들을 찾아서 하나의 명령어 코드 내에 재배열 VLIW 프로세서와 명령어 형식의 예 그림 8-30. 네 개의 기능 유니트들을 가진 VLIW 프로세서와 명령어 형식.

[예] Multiflow사의 TRACE 시스템 슈퍼스칼라와 다른 점 인출과 해독은 한 회로에 의해 수행, 실행 사이클만 여러 개의 기능 유니트들로 나누어져 동시에 처리 그림 8-31. VLIW 프로세서의 실행 시간 흐름도. [예] Multiflow사의 TRACE 시스템 TRACE-7 시스템: 기능 유니트의 수 = 7, 명령어 길이 = 256 비트 TRACE-28 시스템: 기능 유니트의 수 = 28, 명령어 길이 = 1024 비트

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

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

슈퍼파이프라인과 슈퍼스칼라가 결합된 superpipelined superscalar 구조 최근 대부분의 고성능 프로세서들에서 사용 [예] n = 2, m =3 인 프로세서의 명령어 실행 시간도 그림 8-33. 슈퍼스칼라와 슈퍼파이프라인이 결합된 구조의 실행 시간도.

이 구조를 가진 프로세서에서 N 개의 명령어들을 실행하는 데 걸리는 시간 (8-11) 속도 향상 (8-12) N → ∞이면, Sp → m n