What Are Parallel Computers and Multiprocessor Systems in Computer Architecture

Parallel computers and multiprocessor systems fall under the sub-concepts of computer architecture and computer systems, and they are important elements that explain the utilization and configuration methods of CPUs.

병렬 컴퓨터와 다중 프로세서 시스템은 컴퓨터 아키텍처와 컴퓨터 시스템의 하위 개념에 속하며, CPU의 활용 방식과 구성 방법을 설명하는 중요한 요소들이다.

Contents

병렬컴퓨터(Parallel Computer)

1️⃣ 병렬처리의 개념과 필요성(Overview of Parallel Computers)
2️⃣ 병렬처리의 단위(Units of parallel processing)
3️⃣ 병렬컴퓨터의 분류(Classification of parallel processing)

다중 프로세서 프로그램 (Multiprocessor Systems)

1️⃣개요 (Overview of Multiprocessor system architecture)
2️⃣공유-기억장치 시스템(shared-memory system)
3️⃣분산-기억장치 시스템(distributed-memory system)

1️⃣ 병렬처리의 개념과 필요성

(Overview of Parallel Computers)

병렬처리란 다수의 프로세서들이 여러 개의 프로그램들 혹은 한 프로그램의 분할된 부분들을 분담하여 동시에 처리하는 기술이다.

이것과 상반되는 개념은 '직렬처리'인데 통신같은 경우에 직렬 전송이란 선로 하나에 데이터를 전송하는 것이고 병렬전송은 많은 선로를 통해 동시 다발적으로 전송한다. 이렇게 글로만 봐도 병렬처리가 효율성이 높음을 알수있다. 다만 초기비용이 더 들뿐이다. 컴퓨터에서 사용되는 병렬컴퓨터 또한 마찬가지이다.

병렬처리를 위한 선결 조건 (Condition for Parallel Computing)

하드웨어의 관점에선 많은 수의 프로세서들로 하나의 시스템을 구성할 수 있도록 작고 저렴하며 고속인 프로세서들의 사용이 가능해야 해야한다. 반도체 기술의 발전과 VLSI 집적도 향상으로 병렬처리의 조건을 만족하게되었다.

소프트웨어의 관점에선 한 프로그램을 여러 개의 작은 부분들로 분할하는 것이 가능해야 하며, 분할된 부분들을 병렬로 처리한 결과가 전체 프로그램을 순차적으로 처리한 경우와 동일한 결과를 얻을 수 있어야 한다.

야기되는 새로운 문제들 (Challenges for Parallel Computing)

문제 분할(problem partition): 병렬처리를 위 문제(혹은 프로그램)를 여러 개로 나누는데 어떻게 '잘' 분할하는가?

프로세서간 통신(communication between processer): 프로세서가 많다. 분할된 부분을 나누어 처리하는 프로세서간의 데이터 교환을 위해 어떻게 커뮤니케이션 할 것인지에 대한 메카니즘이 필요하다.

필요한 관련 기술들 (Required technology for Parallel Computing)

병렬 프로그램 언어와 컴파일러의 개발
상호 배타 메커니즘(mutual exclusion mechanism) 지원, 즉 프로세스간에 서로 종속되는것이 아닌 독립적으로 커뮤니케이션 할 수 있는 매커니즘이 지원되어야 함
공유자원들에 대한 경합(contention)을 줄이고 이용률을 극대화할 수 있는 새로운 운영체제의 개발, 공유하는 프로세서들이 많기 때문에 경쟁 구도로 가지 않도록 조정할 수 있는 운영체제가 필요하다.

2️⃣ 병렬처리의 단위

(Units of parallel processing) 4가지

병렬처리의 선결조건이 충족되었다는 가정하에 어떻게 단위로 나눠서 처리할 것인지의 분류이다.

✅ 작업-단위 병렬성(Job-level parallelism) : Job은 Task에 비해 더 큰 개념이다. 독립적인 작업 프로그램(job program) 단위로 병렬처리 [예] 성적관리 프로그램 // 실험 데이터 처리 프로그램과 같은 처음부터 끝까지 독립적으로 이루어져 프로세서간의 정보 교환이 필요없다.

✅ 태스크-단위 병렬성(task-level parallelism) : 하나의 큰 작업을 기능에 따라 분할한 작은 프로그램(태스크) 단위로 병렬처리 [예] 로봇 제어 프로그램 ➔ 두뇌, 팔과 다리들의 동작을 제어하는 다수의 태스크들로 분할한 후, 병렬처리 → 프로세서들간의 정보 교환이 필요하다. 또한 이 Task 들이 모여서 전체적인 하나의 Job을 형성하기 때문에 서로 종속적이다.

✅ 스레드-단위 병렬성(thread-level parallelism): 동시에 처리될 수 있는 가장 작은 크기의 독립적인 단위 프로그램인 스레드 단위의 병렬처리이다.

✅ 명령어-단위 병렬성(instruction-level parallelism): 데이터 의존성이 존재하지 않는 여러 개의 명령어들을 동시에 수행하는 병렬처리이다. 병렬처리를 하려면 데이터들이 우선 independent 해야한다.

3️⃣ 병렬컴퓨터의 분류

(Classification of parallel processing)

✅ Flynn의 분류 (Flynn's classification/ Flynn's Taxonomy)

플린의 분류는 병렬 컴퓨터의 구조를 배울 때 처음나오는 기본적인 개념인데 스탠퍼드 대학교의 전기공학과 교수인 마이클 J. 플린이 1966년에 제안한 구조적 특징에 따른 컴퓨터 분류 방식이라고 할 수 있다. 명령어 스트림(instruction stream)과 데이터 스트림(data stream)의 갯수에 따라 구분된다.

명령어 스트림(instruction stream): 프로세서에 의해 실행되기 위하여 순서대로 나열된 명령어 코드들의 집합을 뜻한다.

데이터 스트림(data stream): 그 명령어들을 실행하는 데 필요한 순서대로 나열된 데이터들의 집합이다.

프로세서들이 처리하는 명령어와 데이터의 스트림(stream; 흐름) 의 수에 따라 4가지로 분류된다.

단일 명령어 스트림 - 단일 데이터 스트림 (SISD)
단일 명령어 스트림 - 복수 데이터 스트림 (SIMD)
복수 명령어 스트림 - 단일 데이터 스트림 (MISD)
복수 명령어 스트림 - 복수 데이터 스트림 (MIMD)

단일 명령어 스트림 - 단일 데이터 스트림
(SISD, Single instruction stream, single data stream.)

한번에 한 개씩의 명령어와 데이터를 순서대로 처리하는 단일프로세서 시스템기법이다. 폰 노이만 구조의 컴퓨터는 기본적으로 이 기법을 따른다. 일반적으로 가지고 있는 PC, 노트북들이 해당한다. 가장 기본적이고 간단한 구조이지만 명령어를 실행할 때마다 명령어와 데이터를 읽어와 처리해야 하기 때문에 효율이 떨어진다. 파이프라이닝(pipelining), 슈퍼스칼라(superscalar)구조를 이용하여 컴퓨터의 기능을 향상시킨다.

PU: Processing Unit, MM: Memory Module, CU: Control Unit, IS: Instruction stream, DS: Data stream
MM에서 IS를 가져온 뒤 -> CU가 PU로 IS를 보낸다. -> MM에서 데이터가 필요할시 가져온다. 필요시엔 MM에 저장해야하기 때문에 양방향임을 알 수 있다.

단일 명령어 스트림 - 복수 데이터 스트림
(SIMD, Single instruction stream, multiple data streams.)

한 번에 데이터 스트림 여러개를 명령어 하나로 처리하는 기법이다. 배열 프로세서(array processor)로 되어있는데 이 말은 즉슨 여러개를 사용한다는 뜻이다. 하지만 "단일 명령어" 이기 때문에 프로세서들이 많아도 명령어는 다 동일하다.
여러 개의 프로세싱 유니트(PU)들로 구성되고, PU들의 동작은 모두 하나의 제어 유니트에 의해 통제 되고있다. CU는 하나인데 PU는 여러개인 모습이다. 모든 PU들은 하나의 명령어 스트림을 실행한다.

SM: 공유 기억장치는 Shared Memory로써 메모리를 공유한다.
SIMD에서 중요한 개념은 IS는 하나, DS는 여러개(PU가 여러개 이므로)이다.

복수 명령어 스트림 - 단일 데이터 스트림
(MISD, Multiple instruction streams, single data stream)

N개의 프로세서들이 서로 다른 명령어들을 실행하지만, 처리하는 데이터 스트림은 한 개인 개념이다. 비현실적이므로 실제 구현된 경우는 없음

DS는 하나이고 IS는 여러개가 있다.

복수 명령어 스트림 - 복수 데이터 스트림
(MIMD, Multiple instruction streams, multiple data streams)

N 개의 프로세서들이 서로 다른 명령어들과 데이터들을 처리한다. 즉 다수의 명령이 다수의 데이터를 처리한다. 멀티프로세서에 사용된다.

프로세서들간의 상호작용 정도에 따라 두 가지로 분류된다.

밀결합 시스템(tightly-coupled system): 공유-기억장치의 구조(shared-memory architecture)를 사용하는 것이 기본적인 특징이다. 즉 기억장치를 가지고 여러개의 프로세서들이 공유한다는 뜻이다. 이로인해 프로세스들끼리의 관계는 밀접하기 때문에 "밀결합"이다. 다중프로세서 시스템(multiprocessor system)
소결합 시스템(loosely-coupled system): 프로세서는 자기만의 기억장치를 가지고있다. 독립되어있다. 지역 기억장치(local memory)를 가진 독립적인 컴퓨터 모듈로 구성된다. 독립적인 이유로 인해 프로세서간 통신은 메시지 전송(message-passing) 방식으로 이루어진다. 연속적으로 이루어지는 것이 아님. 다중컴퓨터 시스템(multiple-computer system)이 loosely coupled system에 해당한다.

✅ 기억장치 액세스 모델에 따른 분류

(Classification based on Memory Access Model)

컴퓨터는 기억장치 액세스 모델에 따라 3가지로 나뉠 수 있다.

균일 기억장치 액세스(Uniform Memory Access: UMA) 모델
불균일 기억장치 액세스(Non-uniform Memory Access: NUMA) 모델
무-원격 기억장치 액세스(No-Remote Memory Access: NORMA) 모델

UMA 모델 (UMA Model)

모든 프로세서들이 상호연결망에 의해 접속된 주기억장치를 균등하게 공유한다. 프로세서들은 주기억장치의 어느 영역이든 액세스할 수 있으며, 그에 걸리는 시간이 동일하다.

프로세서를 여러개 사용하고 있다 (P1, P2, P3.. )
SM1 (Shared Memory1), SM2, I/O 등을 어디든지 액세스한다.

UMA모델 장단점(Pros and Cons of UMA model)

장점(Pros): 하드웨어가 간단하고, 프로그래밍이 용이하다
단점(Cons): 공유 자원에 대한 경합이 높아지기 때문에 시스템 크기에 한계가 있다 [예] 공유-버스를 사용하는 시스템 : 프로세서 30개 이하 크로스바, MIN을 사용하는 시스템 : 프로세서 64개 이하까지 가능하다 위의 이유로 UMA모델로 병렬컴퓨터를 제작할 시 한계에 부딪히게 되기 때문에 가장 기본적인 모델이라고 할 수 있다.

NUMA 모델(NUMA Model)

UMA 모델의 한계를 극복하고 더 큰 규모의 시스템을 구성 하기 위한 모델이다. 다수의 UMA 모델들이 상호연결망에 의해 접속하는 형태를 가지고 있다.

분산 공유-기억장치(distributed shared-memory) 구조로써 기억장치 액세스 시간은 기억장치의 위치에 따라 시간 달라지는데 이 위치는 3가지로 나뉜다.

기억장치의 위치

지역 기억장치 액세스(local memory access)
전역 기억장치 액세스(global memory access)
원격 기억장치 액세스(remote memory access)

NORMA 모델 (NORMA Model)

프로세서가 원격 NOMA모델에서 언급된 기억장치(remote memory)는 직접 액세스할 수 없는 시스템 구조이다. 프로세서들과 기억장치들은 메시지-전송(message- passing)을 지원하는 상호연결망으로 접속한다. 분산-기억장치 시스템(distributed-memory)으로도 부른다. 주요 상호연결망은 메시(mesh), 하이퍼큐브(hypercube), 토러스(torus)등 의 구조이다.

프로세서(P)에 메모리(M)가 딸려있다.
상단의 P가 하단의 M으로 바로 엑세스가 불가능하다

✅시스템 구성 방법에 따른 분류

(Classification based on System Configuration Method)

컴퓨터는 시스템 구성방법에 따라 5가지로 분류된다.

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

대칭적 다중프로세서(Symmetric Multiprocessor: SMP)

Symmetric(대칭적)having similarity in size, shape, and relative position of corresponding parts. 모든 프로세서들이 필요 시 직접 OS 코드 수행하고 모든 프로세서들이 자원들을 동등한 권한으로 사용한다는 뜻.

64개 이하의 프로세서들을 가지는 중대형급 시스템에서 사용한다. (위에 언급된 UMA모델의 시스템 크기는 프로세서 64개 이하까지 가능하다고 언급했다. 이로인해 UMA모델 SMP는 밀접한 관계가있다무는 것을 알수있다.) 완전-공유 구조(shared-everything architecture) 로 메모리든 I/O 장치든 프로 세서들이 시스템 내의 모든 자원들을 공유한다. UMA모델도 동일하다. 시스템 내에 하나의 OS만 존재한다.

대칭적 다중프로세서 한줄 요약:

능력이 비슷한 프로세서들로 구성된다.
프로세서들이 기억장치와 I/O 장치들을 공유하며, 상호연결망에 의해 접속한다.
모든 프로세서들은 동등한 권한을 가지며, 같은 수준의 기능들을 수행한다.
프로세서간 통신은 공유 기억장치를 이용한다.
작업 스케줄링(Job scheduling)이 하나의 OS에 의해 통합적으로 이루어진다.
공유 자원의 경합으로 인하여 시스템 크기에 한계가 있다.
UMA모델과 비슷하다.

대규모 병렬프로세서(Massively Parallel Processor: MPP)

무공유 구조(shared-nothing)를 기반으로 하는 대규모 병렬처리시스템이다. 수백 혹은 수천 개의 프로세싱 노드(processing node)들로 구성된다. 간단한 구조의 노드 프로세서 사용한다. 각 노드는 독립적인 OS를 탑재한다. 노드들 간의 통신은 메시지 전송 방식 이용한다. 복잡도 높은 상호연결망 이용하기 때문에 규모가 크다.

캐시-일관성 NUMA(Cache-Coherent NUMA: CC-NUMA) 시스템

기존의 NUMA시스템에서 Cache-Coherent, a measure of the relationships between backlog items which make them worthy of consideration as a whole. 즉 캐시를 가지고 있는 NUMA이다.

독립적인 노드들(UMA 혹은 NUMA 시스템)이 상호연결망에 의해 접속되어있다. 하나하나의 프로세서도 있지만 프로세서가 합쳐서 하나의 모듈을 구성하듯이, 그 모듈이 캐시-일관성 NUMA에서는 독립된 노드들이다. 모든 노드들의 캐시 및 주기억장치들 사이에 데이터 일관성을 유지한다. 시스템 내의 모든 기억장치들이 전역 주소공간(global address space)을 가지는 분산 공유-기억장치시스템 (distributed shared-memory system)으로 구성되어 있다.

주요 장점: S/W(소프트웨어) 변경 없이 SMP보다 더 큰 시스템 구축이 가능하다.

P(프로세서)에 C(캐시)가 딸려있다. M(모듈)은 하나씩 있고 어디든지 액세스가 가능하다. 상호연결망으로 서로를 연결하기 위해 N.I / F(네트워크 인터페이스)가 필요하다. 이따 배울 상호연결망(interconnection network)은 아주 복잡하다.

분산 시스템(Distributed System: DS)

독립적인 노드(컴퓨터시스템)들이 전통적인 네트워크에 의해 접속되어 있는 것. 노드들 간의 정보 교환 혹은 병렬처리를 수행할 때만 네트워크를 이용하여 통신한다. 이것은 loosely-coupled system이다 즉 관계가 밀접하지 않고 소원하다. 여기서 언급되는 노드는 PC, workstation, 혹은 그들의 집합을 뜻한다.

클러스터 컴퓨터(Cluster Computer: CC)

A collection of PCs or workstations, 네트워크는 고속 LAN, 혹은 network switch로 이루어진다. 모든 시스템 자원들을 단일 시스템 이미지(SSI: Single System Image)로 통합한다. 즉 여러개의 PC나 workstation이 네트워크를 통해 연결되어 있지만 전체적으로는 하나의 컴퓨터 시스템처럼 보인다는 뜻이다.

주요 장점으로는 저렴한 비용으로 병렬처리시스템 구축 가능하다. 네트워크만 연결하면 되기 때문이다. 결함 대체 용이하다. 이로 인해 가용성(availability)이 향상된다.

1️⃣ 다중프로세서시스템 구조의 개요

(Overview of Multiprocessor system architecture)

고성능 컴퓨터에서 언급되는 개념은 병렬 컴퓨터, 다중프로세서 시스템이다. MIMD 조직으로서, 여러 개의 프로세서들이 비동기적(Asynchronous)으로 프로그램을 실행하는 시스템이다. 위에 언급된 MIMD의 밀결합 시스템(tightly-coupled system)에 해당한다.

비동기적(Asynchronous) 동시에 일어나지 않는 뜻을 가지고 있으며, 요청과 결과가 동시에 일어나지 않을거라는 약속이다.

기억장치 모듈을 사용하는 (소유하는) 방식에 따라 2가지로 나뉜다.

공유-기억장치 시스템(shared-memory system)
분산-기억장치 시스템(distributed-memory system)

밀결합 구조((tightly-coupled structure)로서, 주기억장치가 어느 한 프로세서에 속해 있지 않고 모든 프로세서들에 의해 공유되는 시스템이다.

상호연결망을 구현하는 방법 3가지

버스(Bus): 공유-버스(shared-bus),다중-버스(multiple-bus)
크로스바 스위치(Crossbar Switch)
다단계 상호연결망(Multistage Interconnection Network: MIN)

장점(Pros of shared-memory system) 프로세서들이 공통으로 사용하는 데이터들이 공유 기억장치에 저장되므로 별도의 프로세서간 데이터 교환 메커니즘이 필요하지 않는다. 메모리를 이용해서 서로 커뮤니케이션하면 되기 때문이다. 프로그램 실행시간 동안에 각 프로세서들이 처리할 작업들을 동적으로 균등하게 할당할 수 있기 때문에 프로세서 이용률을 극대화 하여 시스템 효율을 높일 수 있다.

단점(Cons of shared-memory system) 프로세서들과 기억장치들 간의 통로(버스 또는 상호연결망)상에 통신량이 많아지기 때문에 경합으로 인한 지연 시간이 길어질 수 있다. 통신량이 적당하면 상관없지만 많은 수의 프로세스들이 메모리를 이용할 경우 상호연결망에서 문제가 발생할 수 있다. 두 개 이상의 프로세서들이 공유자원(기억장치 모듈 또는 입출력장치)을 동시에 사용하려는 경우에 한 개 이외의 프로세서들은 대기해야 하기 때문에 → 프로세서 수가 증가해도 선형적(linear) 성능 향상은 불가능하다. (고속 상호연결망과 캐시 기억장치의 사용으로 보완가능하다. )

2️⃣공유-기억장치 시스템(shared-memory system)

버스(Bus): 공유-버스(shared-bus)

하드웨어가 매우 간단하고 버스 경합으로 인한 지연 시간이 증가 할 수 있다. ➔ 버스의 전송 속도를 높이거나 캐시를 사용하여 성능 저하를 보완할 수 있다.

버스(Bus): 다중-버스(multiple-bus)

버스 경합을 줄이기 위하여 버스의 수를 증가하였다. 계층버스 구조(hierarchical bus structure)라고도 불리 용도가 다른 여러 계층의 버스들을 사용한다.

전체적인 중심을 잡아주는 '시스템버스' 그 하위 단계엔 지역버스(Local bus)가 있다.

크로스바 스위치(Crossbar Switch)

프로세서들과 기억장치들 사이의 완전 연결성(full connectivity)을 보장하는 구조이다. 그대신 비용이 많이 들고 하드웨어가 복잡하다.

P0와 M0를 연결하려면 스위칭 소자를 on하면 된다. 다른 곳도 마찬가지이다. 스위치의 숫자와 선로가 너무 많이들기 때문에 고비용이다.

다단계 상호연결망(Multistage Interconnection Network: MIN)

크로스바 스위치와 버스 중간 정도의 하드웨어 복잡성을 가진 상호연결망이다. 예로는 오메가 네트워크(Omega Network)가 있다.

크로스바는 모든 것을 연결했지만 MIN에선 연결해야하는 곳만 연결한다. (노란선) 동시에 8개가 '독립적'으로 연결되어 있다. 하드웨어 복잡도는 크로스바 스위치보다 낮기 때문에 비용이 좀 더 저렴하다.

3️⃣ 분산-기억장치 시스템(distributed-memory system)

앞에서는 메모리를 공유하는 구조였지만 분산 - 기억장치는 소결합 구조(loosely-coupled structure)이다. 결합이 소원한 구조이다. 각 프로세서가 자신의 지역 기억장치(local memory)를 소유하고 있다. 다른 프로세서들과의 통신은 메시지 전송(message- passing)을 이용한다. 장점으로는 공유자원에 대한 경합이 감소한다이고 단점은 통신 프로토콜에 의한 지연 시간이 증가한다.

네트워크 지름(network diameter) : 네트워크 내에서 가장 멀리 떨어져 있는 노드들 간의 거리(즉, 링크의 수) 값이 크면 클수록 네트워크의 지름이 크다.

분산-기억장치 시스템을 구현하는데는 아래와 같다.

선형 배열(linear array)구조
링(ring)구조
트리(Tree)구조
팻 트리(fat tree)구조
메시(mesh) 구조
토러스 네트워크(torus network)
하이퍼큐브 네트워크(hypercube network)

선형 배열(linear array)구조 네트워크 지름이 N-1로서, 다른 구조들에 비하여 가장 길다. 버스 구조 보다 동시성이 더 높다. (동시성이 높다는 뜻은 0, 1, 2 모두 동시에 가능)

통신 시간이 노드들 간의 거리에 따라 서로 다르며, 노드 의 수가 많아지면(N이 커지면) 통신 시간이 매우 길어진다.

링(ring)구조

트리(tree) 구조 시스템 요소들의 수가 증가함에 따라 성능이 선형적으로 향상되는 구조를 가지고 있다.

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

메시 구조(mesh network) 옆으로 모두 연결되어 있다. 많은 병렬컴퓨터에서 사용하고 있는 구조이다. ILLIAC IV, MPP, DAP, CM-2 및 Intel Paragon에서 사용한다.

토러스 네트워크(torus network) 처음과 끝이 연결되어 원형 구조와 메시 구조가 혼합된 구조로 확장이 용이하다.

하이퍼큐브 네트워크(hypercube network) 3차원적으로도 시스템을 구성할 수 있는데 상호연결 함수가 나오면서 아주 복잡해진다. 오늘은 3차원으로도 분산-기억장치 시스템구조를 가지는 병렬 컴퓨터를 구현할 수 있다. 까지만 알아두자.