병렬 처리 (Parallel Processing)
병렬 처리(Parallel Processing)란 하나 이상의 연산을 동시에 수행하여 컴퓨터 연산 속도를 증가시키는 방법이다. 병렬처리기는 이러한 병렬 처리 기법을 구현한 컴퓨터 구조를 말한다. 병렬처리기는 순차처리기에 비해 꽤나 높은 성능 향상을 이끌어내었다.
컴퓨터 성능 평가
컴퓨터 성능을 평가하는 척도는 "시간"이다. 같은 작업량을 최단시간에 수행하는 컴퓨터가 가장 성능이 좋은 것이다. 그리고 이때 말하는 시간은 프로세서가 순수하게 프로그램을 실행하기 위해 소비한 시간인 "CPU 시간"을 말한다. CPU 시간은 다음과 같이 정의된다.
NOTE!
프로그램 CPU 시간 = 프로그램의 CPU 클록 사이클 수 X 클록 사이클 시간
병렬 처리 시스템 분류
병렬처리기 구조는 동시에 처리 가능한 명령어, 데이터 수, 처리기의 내부조직, 처리 기간의 연결구조 등에 따라 분류된다. 대표적인 분류 방법으로 "플린(Flynn)의 분류", "펭(Feng)의 분류", "구조에 의한 분류"가 있다.
플린의 분류 (Flynn)
플린은 컴퓨터 구조를 명령어 스트림과 데이터 스트림이 컴퓨터 내에 몇 개인지를 기준으로 분류했다. 명령어 스트림과 데이터 스트림의 정의는 다음과 같다.
- `명령어 스트림(Instruction Stream)`: 프로세서에 의해 실행되기 위하여 순서대로 나열된 명령어 코드들의 집합
- `데이터 스트림(Data Stream)`: 명령어들을 실행하는데 필요한 순서대로 나열된 데이터들의 집합
플린의 분류 방식에 따른 컴퓨터 구조는 명령어 스트림과 데이터 스트림을 처리하는 방식에 따라 아래와 같이 나눌 수 있다.
- `SISD(Single Instruction Single Data)`: "단일 명령어 스트림-단일 데이터 스트림" 방식으로, 한 번에 한 개씩의 명령어와 데이터를 순서대로 처리하는 단일 프로세서 시스템이다.
- `SIMD(Single Instruction Multiple Data)`: "단일 명령어 스트림-복수 데이터 스트림" 방식으로, 모든 프로세서가 같은 프로그램을 수행하며, 각 프로세서가 병렬적으로 다른 데이터를 처리하는 구조이다. 여러 개의 데이터 스트림을 동시에 처리 가능하다.
- `MISD(Multiple Instruction Single Data)`: "복수 명령어 스트림-단일 데이터 스트림" 방식으로, 다수의 프로세서들이 서로 다른 명령어들을 실행하지만, 처리하는 데이터 스트림은 한 개인 구조이다. 비현실적이기에 실제로 구현하지 않는다.
- `MIMD(Multiple Instruction Multiple Data)`: "복수 명령어 스트림-복수 데이터 스트림" 방식으로, 각 프로세서가 서로 다른 프로그램을 수행하며 또 다른 데이터를 처리하는 구조이다. 모든 프로그램들이 협력하여 통합적인 목적을 이루도록 하는 가장 복잡한 구조이다. 현재까지 개발된 대부분의 다중처리기 컴퓨터 시스템은 MIMD 컴퓨터 구조에 속한다.
펭의 분류 (Feng)
펭은 컴퓨터 구조를 병렬수행 정도에 따라 분류했다. 한 컴퓨터에서 단위 시간 내에 처리 가능한 최대 비트 수를 $P$라고 한다면, 이는 "최대 병렬수행도"가 된다. 그리고 $P_i$를 $i$번째 클록 펄스에서 수행될 수 있는 비트 수라고 하고, $T$ 사이클 동안 처리되는 평균 비트 수 $P_a$는 다음과 같이 구할 수 있다.
$$ P_a = \frac{P_1 + P_2 + \cdots + P_T}{T} $$
이때, $P_a$를 "평균 병렬수행도"라고 한다. 그리고 주어진 컴퓨터 시스템 $C$의 최대 병렬수행도 $P$는 비트 슬라이스의 길이 $n$과 단어의 길이 $m$의 곱셈으로 나타낼 수 있다.
$$P(C) = n \times m$$
펭의 분류 방식에 따른 컴퓨터 구조는 비트 처리 방식에 따라 아래와 같이 나눌 수 있다.
- `WSBS(Word-Serial, Bit-Serial)`: 단어별 순차, 비트별 순차 방식으로, 한 워드에 대해 한 번에 한 비트씩 처리하는 방식
- `WPBS(Word-Parallel, Bit-Serial)`: 단어별 병렬, 비트별 순차 방식으로, 여러 워드에 한 번에 한 비트씩 병렬적으로 처리되는 방식이다. $m$개의 워드를 묶어 그 중 1개의 비트 슬라이스 단위를 순차적으로 처리하는 방식
- `WSBP(Word-Serial, Bit-Parallel)`: 단어별 순차, 비트별 병렬 방식으로, 한 번에 한 워드의 모든 비트를 병렬적으로 처리하는 방식이다. 가장 널리 사용되는 방식
- `WPBP(Word-Parallel, Bit Parallel)`: 단어별 병렬, 비트별 병렬 방식으로, 병렬처리의 가능성을 최대로 높인 방식이다,
구조에 의한 분류
다중처리기 시스템은 문제를 해결하기 위해 협력하여 동작하는 독립적인 많은 처리기가 하나의 컴퓨터 시스템을 이루는 것이다. 여러 처리기가 결합하여 하나의 시스템을 이루는 방법은 "분산 처리"와 "병렬 처리"가 있다.
- `분산 처리`: 하드웨어 자원이 프로세스 작업에 대하여 상대적으로 약하게 결합되어 동작하는 것
- `병렬 처리`: 하드웨어 자원이 프로세스 작업에 대하여 강하게 결합되어 동작하는 것
병렬 처리 시스템은 다중처리기와 다중 컴퓨터로 구분된다.
- `다중처리기`: 독자적인 처리기, 기억장치, 입출력, 운영체제를 가진 여러 컴퓨터로 구성된다.
- `다중 컴퓨터`: 하나의 운영체제만 가지고 기억장치공간의 입출력 자원을 공유한다.
병렬적이며 비동기적인 컴퓨터 시스템에서 동시에 여러 태스크를 수행하는 "다중 프로세싱"에는 공유기억장치 시스템과 메세지 전달 시스템, 두 가지 기본 모델로 나누어진다.
공유기억장치 시스템 (Shared Memory)
공유기억장치 시스템을 가지는 다중처리기 구조는 처리기와 기억장치모듈 사이에 완전한 연결성이 있는 강결합 시스템이다. 즉, 모든 프로세서들이 상호 연결망에 의해 접속된 주기억장치를 공유한다.
프로세서들이 공통으로 사용하는 데이터들이 공유기억장치에 저장되므로, 별도의 통신 매커니즘이 필요하지 않다. 또한 시스템 효율도 높아지게 된다. 그러나, 공유기억장치를 사용하기에 많은 프로세서가 동시에 통신하는 것은 불가능하다.
메세지 전달 시스템 (Message Passing)
메세지 전달 시스템은 여러 개의 컴퓨터 모듈과 상호 연결망으로 구성되고, 데이터 통신은 메세지를 통해 이루어진다. 즉, 프로세서가 기억장치에 직접 접근할 수 없고 메세지를 통해 통신이 이루어진다는 것이다.
메세지 송수신 방식을 사용하기에 송수신 시간은 길어지지만, 각각의 프로세서가 개별 메세지를 사용하기에 많은 프로세서가 동시에 통신하는 것이 가능하다.
다중처리기 고려사항
병렬성을 활용하고 연산 속도를 증가시키기 위하여 다중처리기를 사용하는데, 이때 몇 가지 고려해야 할 사항들이 있다.
- `병렬성 고려사항`: 병렬성을 어떻게 표현해야 하는 가에 대한 고려와 병렬로 처리할 작업을 어떻게 분할할지에 대한 고려가 필요하다.
- `기억장치 고려사항`: 기억장치 충돌 문제에 대한 고려, 기억장치 접근의 효율성에 대한 고려와 캐시 일관성에 대한 고려가 필요하다.
- `그 밖의 고려사항`: 스케줄링에 대한 고려와 프로세스 동기화에 대한 고려, 시스템의 균형에 대한 고려가 필요하다.
병렬처리기 종류
파이프라인 처리기 (Pipeline Processor)
파이프라인 처리기는 프로그램에 내재하는 시간적 병렬성(Temporal Parallelism)을 활용하기 위하여 프로그램 수행에 필요한 작업을 시간적으로 중첩하여 수행시키는 처리기이다. 이러한 기법을 명령어에 사용하는 것이 "명령어 수행 파이프라인"이다.
한 명령어의 $S_i$ 단계의 수행이 끝나면, 그 다음 단계인 $S_{i+1}$ 단계로 넘어간다. 그리고 다음에 수행시킬 명령어는 $S_{i-1}$에서 $S_i$ 단계로 넘어가게 된다. 따라서 한 파이프라인의 각 단계마다 서로 다른 명령어의 각 단계가 수행된다.
명령어 파이프라인이 정상적인 동작에서 벗어나게 되기도 하는데, 그 원인은 다음과 같다.
- `자원 충돌`: 두 세그먼트가 동시에 기억장치에 접근하고자 할 때 발생한다. 명령어 기억장치와 데이터 기억장치를 분리하면 해결된다.
- `데이터 의존성`: 어떤 명령어가 이전 명령어의 결과에 따라 수행될 때, 그 값이 준비되지 않았을 경우 발생한다.
- `분기 곤란`: 분기 명령어와 같이 프로그램 카운터의 값을 변경시키는 명령에 의해 발생한다.
배열처리기 (Array Processor)
한 컴퓨터 내에서 여러 개의 처리장치를 배열 형태로 가질 때, 이를 배열처리기라고 한다. 배열 내의 처리기들은 동기화되어 병렬 처리를 하여 동시에 같은 작업을 수행한다. 프로그램의 수행을 위해서는 배열 내의 처리기 사이에 데이터 교환이 가능해야 하기 때문에 배열처리기 사이에는 적절한 정보 교환 수단이 세팅되어야 한다.
배열처리기를 구성하는 처리기들은 레지스터, 연산기, 지역기억장치를 가지며 "상호연결망"에 의해 데이터 교환이 가능하다.
다중처리기 (Multiple Processor)
다중처리기란 시스템 상의 여러 처리기에 여러 개의 독립적인 작업을 각각 배정하여 2개 이상의 처리기를 동시에 수행할 수 있는 기능을 갖춘 시스템을 말한다. 다중처리기의 목적은 다음과 같다.
- 한 작업을 여러 처리기로 나누어 서로 다른 처리기에 할당하고 동시에 실행하여 수행시간을 줄인다.
- 여러 작업을 동시에 처리하여 시스템의 전반적인 효율성을 향상시킨다.
- 같은 기능의 처리기를 중복시켜 에러 허용과 동시 처리로 인한 수행 속도를 향상시킨다.
다중처리기의 모든 처리기는 공통의 기억장치모듈, 입출력 채널, 입출력 장치에 접근 가능하며 각 처리기는 자체의 지역기억장치를 가진다. 다중처리기를 구성하는 각 요소들의 연결은 "상호연결 구조"에 의해 결정된다.
데이터 흐름 컴퓨터 (Data Flow Computer)
보편적으로 사용되는 폰 노이만형 컴퓨터를 "제어 흐름 컴퓨터(Control Flow Computer)"라고 한다. 제어 흐름 컴퓨터는 하나의 프로그램 카운터로 명령어가 순차적으로 수행된다. 수행 속도가 느리다는 단점을 극복하고자 내재된 병렬성을 극대화 시키려 하는 시도가 계속 발생되었고, 데이터 흐름 컴퓨터는 그 중의 한 예이다.
데이터 흐름 컴퓨터는 프로그램 내의 모든 명령어를 수행에 필요한 피연산자들이 모두 준비되었을 때, 프로그램에 나타나는 명령어의 순서와 무관하게 수행시킨다.(데이터 추진 방식) 이렇게 명령어들이 수행되면 그 결과는 결과를 필요로 하는 명령어들에 보내진다.
데이터 추진 방식에서는 프로그램 카운터가 필요하지 않고, 명령어 수행 시작은 명령어 출현 시기와 무관하며, 단지 "피연산자들이 준비되었는가"에 의 달려있는 것이다. 이는 이론적으로 최대의 병렬성을 얻을 수 있으며, 이용 가능한 하드웨어 자원의 양에만 제한을 받을 뿐이다.
VLSI 처리기 (Very Large Scale Integration)
VLSI 기술, 초규모 직접 회로 설계 기술이 발전함에 따라 병렬 알고리즘을 직접 하드웨어로 구현하는 VLSI 처리기가 등장하게 되었다. VLSI 처리기는 파이프라인 기법을 이용한 다중처리 기법을 사용하며, 규칙적인 단위인 "셀(Cell)" 등의 연결망으로 이루어져 있다.
상호연결망 구조
병렬처리 시스템은 하나의 문제를 해결하기 위해 여러 개의 처리요소가 동작하기에, 각각의 처리요소 사이 통신 가능한 경로가 필요하다. 이때, 처리요소와 기억장치를 연결하는 네트워크를 "상호연결망(Interconnection Network)"이라고 한다. 현재 개발된 상호연결망은 여러 종류가 있는데, 크게 "정적 상호연결망"과 "동적 상호연결망"으로 구분된다.
정적 상호연결망
정적 상호연결망은 직접 연결된 경로를 사용하고, 한 번 마련된 경로는 변경 불가능하다. 따라서 정적 상호연결망은 통신 유형이 예측 가능한 상황에 적합하다. 정적 상호연결망의 종류는 다음과 같다.
- `성형 구조`: 허브(hub)라는 특별한 노드와 연결되는 연결도 1의 노드로 구성된다. 허브 충돌에 대한 위험 때문에 10여 개의 노드로 제한한다.
- `완전상호연결 구조`: 각 처리기와 각 기억장치모듈 사이에 가능한 연결이 모두 존재한다. 노드를 추가하는 비용이 비싸다.
- `선형 구조`: 이용 가능한 가장 단순한 구조로, 모든 노드가 연결도를 가지기에 노드를 추가하는 비용은 고정되지만 통신 시간은 노드 사이 거리에 비례하며 결함 노드 발생 시, 결함 노드로 인해 분리되는 모든 노드 사이 통신이 마비된다.
- `링 구조`: 양 끝이 연결된 선형 노드로, 선형 구조와 같이 노드 추가 비용은 고정된다. 결함 노드 발생 시, 메세지는 반대 방향으로 가서 결함 노드를 피할 수 있다.
- `트리 구조`: 완전 트리 형태를 가지며, 각 지역 그룹에서 프로세서들이 하나의 기억장치로 강결합되는 형태를 가진다. 노드의 연결도는 일정하게 유지하며 확장 가능하지만, 통신 거리는 상대적으로 길다.
- `메시 구조`: 노드들이 2차원 망의 교차점에 배치된 형태로, 2개의 노드가 상하좌우로 근접하며 서로 연결된다.
- `토러스 구조`: 메시 구조에서 상하 끝과 좌우 끝을 서로 연결해 대칭성을 부여하여 평균 통신 거리를 줄인다.
- `하이퍼큐브 구조`: 기하학적으로 $n$차원 공간에서 정의되는 큐브의 $2^n$개의 꼭짓점에 노드를 가진 구조이다. 아주 좋은 효율을 가지고, 높은 확장성을 가진 구조이다. 또한 모든 노드가 동등하기에 같은 경로 배정 방식을 사용할 수 있다.
동적 상호연결망
동적 상호연결망은 가능한 모든 유형의 통신이 가능하기에 범용적인 시스템 구축에 적합하다. 다만, 동적인 연결을 위해 경로 뿐만 아니라 스위칭 모듈이나 중계기가 필요하다.
- `버스 구조`: 사용되는 처리기 수가 적을 때, 좋은 성능을 발휘한다. 비용이 저렴하기에 작은 규모의 다중처리기 시스템에 적합하며 트리 구조의 시스템에 지역적인 기반으로 이용 가능하다. 다만, 버스 사이클 당 하나의 연결만을 제공한다.
- `다중 버스 구조`: 여러 개의 버스를 가지는 구조로, 여러 개의 장치가 다른 여러 개의 장치와 동시에 통신 가능하기에 고성능 시스템에 이용된다.
- `크로스바 구조`: $P \times M$ 크로스바는 $P$개의 처리기와 $M$개의 기억장치 모듈과 동시에 연결 가능하다. 이때, 기억장치 모듈의 개수가 정확히 $M$개라면, 완전 크로스바가 된다. 완전 크로스바는 스위치의 수가 "처리기의 수와 기억장치의 수의 곱"으로 증가하기에 규모가 커지면 매우 비싸지지만, 지역적 기반구조로는 매우 유용하다.
- `다단계 네트워크 구조`: 근원지와 목적지 사이에 여러 개의 스위치 요소가 있는 상호연결망으로, 많은 연결이 필요하고 처리기의 수가 많을 때 이용된다. 연결망은 여러 단계로 구성되며 인접한 두 단계는 "순열(Permutation)" 연결을 이루게 된다.
