[카테고리:] 병렬컴퓨터구조론

병렬 컴퓨터는 프로세서들을 포함한 많은 하드웨어 자원들을 중복적으로 사용하여 구성하는 시스템이기 때문에, 단일 프로세서 시스테보다 성능이 높아지는 것은 당연한 일이다. 그러나 여러 가지 요인들에 의하여 성능 향상이 그에 비례하여 높아지지는 못하고 있다. 따라서 시스템 개발자들은 투자한 가격 대 성능비를 높이기 위하여 많은 노력을 계속하고 있다. 그를 위해 병렬 컴퓨터의 속도와 성능 향상 및 효율에 대한 척도에 대해서 살펴봐야 한다.

• 처리 속도

처리 속도는 시스템에서 단위 시간당 처리할 수 있는 연산들의 수로써, 여러 척도들이 사용되고 있다.

MIPS(Millions of Instructions Per Second): 초당 실행 완료되는 명령어들의 수를 나타내는 단위이다. 예를 들어, 1MIPS 및 100MIPS는 각각 초당 백만 개 및 1억 개의 명령어들을 실행하는 속도를 나타낸다. 그리고 1GIPS = 1000MIPS 로서, 초당 10억 개의 명령어들을 실행하는 속도이다. 8개의 프로세서들로 구성된 시스템은 퇴대 80MIPS의 실행 속도를 가질 수 있다. (여러 요인들에 의하여 실제로는 그보다 더 낮아진다.) 이 척도는 SIMD에서는 하나의 명령어가 실행되는 동안에 여러 개의 데이터들에 대한 연산들이 동시에 수행되기 때문이다.

MFLOPS(Millions of Floating-Point Per Second): 부동 소수점 연산에 대한 처리 속도를 나타내는 단위이다. 이 척도는 주로 과학계산 응용들을 처리하는 슈퍼컴퓨터의 처리 속도를 나타내는 데 사용되는데, 최근에 슈퍼컴퓨터로 분류되고 잇는 시스템들은 데부분이 TFLOPS 이상의 처리 속도를 기본으로 가지고 있다.

LIPS(Logical Inferences Per Second): 위의 두 척도들은 모두 수치 계산의 처리 속도를 나타내는 반면, LIPS는 인공지능 프로그램의 처리 속도를 나타내는 척도이다. 즉, 시스템이 단위 시간당 처리하는 논리 추론들의 수를 나타낸다.

• 속도 향상

속도 향상은 앞에서 설명하였던 바와 같이, 프로세서 수가 p개인 병렬컴퓨터가 단일 프로세서 시스템에 비하여 몇 배의 처리 속도를 가지는지를 나타내는 척도이다. 어떤 프로그램을 단일프로세서 시스템에서 처리하는 데 걸리는 시간을 T1이라 하고, 동일한 프로그램ㅁ을 p개의 프로세서들을 가진 병렬컴퓨터에서 처리하는 데 걸리는 시간을 Tp라고 할 때, 속도 향상 Sp를 나타내는 식을 다시 쓰면 아래와 같다.

Sp는 일반적으로 프로세서 수보다 더 작은데, 그 주요 요인들로는 불균등한 작업부하 및 각종 병렬처리 오버헤드들을 들 수 있다.

• 효율

병렬컴퓨터에서 효율이란 아래의 식과 같이 속도 향상과 프로세서의 수의 비율로 정의된다.

예를 들어, p=10인 병렬컴퓨터를 이용하여 8배의 속도 향상을 얻었담면, Ep=0.8이 된다.  (80%) 즉, 효율은 투자 비용에 따른 효과를 나타내는 척도이다.

• 중복성

중복성이란 어떤 응용 프로그램ㅁ을 병렬컴퓨터에서 처리하는 경우에 수행되는 연산들의 수와 단일 프로세서 시스템에서 처리하는 경우에 수행되는 연산들의 수의 비율을 말한다. 이 식은 아래와 같이 표현할 수 있는데, 이 값은 항상 1보다 크다. 그 이유는 병렬처리를 위하여 별도의 동작들(프로세서 동기화 및 프로세서 간 통신 등)이 추가적으로 수행되어야 하기 때문이다. 결과적으로, 그 연산들을 처리하는 만큼 시간이 더 소모됨으로써 속도 향상과 효율이 저하되는 것이다.

• 시스템 이용률

시스템 이용률은 아래 식과 같이 표현된다.

이것은 하드웨어 자원들이 어느 정도 효율적으로 사용되는지를 나타내는 척도이다. 즉, 프로그램을 처리하는 전체 시간 동안에 하드웨어 자원들이 실제 사용중인 상태에 있었던 비율을 가리킨다.

단일 프로세서 시스템에서는 O1 = T1인 것으로 가정한다면, 식은 더 간단해진다. 병렬 컴퓨터의 시스템 이용률은 대부분 1보다 더 적은데, 그 주요 이유는 프로세서들이 처리할 작업량이 균등하지 못하여 일부 프로세서들은 대기 상태에 있게되는 것과, 데이터 의존성으로 인하여 다른 프로세서로부터 데이터가 전송되어 올 때까지 기다려야 하는 경우가 있기 때문이다. 이 부분은 나중에 별도로 상세 설명이 필요하다.

• 병렬처리의 질

병렬처리가 어느 정도 효과적으로 이루어졌는지를 나타내는 질을 이전까지 작성한 식을 토대로 하여 종합적으로 작성하면 아래와 같이 정리된다.

즉, 병렬처리의 질은 속도향상과 효율에 비례하며, 중복성에는 반비례한다. 여기서 Ep는 항상 1보다 작고, Rp는 1과 p 사이의 값을 가지므로, Qp의 상한값(limit)은 속도 향상인 Sp가 된다.

일단 이정도의 내용만 가지고 병렬 컴퓨터의 성능 척도에 대해서 간단하게 살펴볼 수 있었다.

설명은 이전 글에서 간략하게 진행했었는데, 실제로 이해가 쉽기 위한 이미지를 그려서 올리는 것이 더 좋을 거 같아서 같이 올립니다.

UMA 구조입니다.

NUMA 구조입니다.

COMA 구조입니다.

NORMA 구조입니다.

CC-NUMA 구조입니다.

이 구조들은 이미 다 봤을법한 구조입니다만.. 혹시나 해서 올립니다. 이전 글과 같이 보면 좋습니다.

최근 병렬 컴퓨터의 공성능화를 위하여 여러 가지 형태의 시스템들이 구성되고 있다. 그들은 시스템의 크기, 용도, 사용자 환경, 비용, 프로세서간 통신 방버 및 OS의 수 등에 있어서 매우 다양하다. 이러한 시스템들은 프로세서, 기억장치 및 상호 연결망을 어떻게 구성하는지에 따라 일반적으로 아래와 같이 분류되고 있다.

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

어디선가 많이 본 시스템 구성들이 있을 것이다. 그것들을 일단 간단하게 설명하려한다.

SMP는 대략 2~64개의 프로세서들로 구성되는 중대형급 단일 시스템으로서, 일반적으로 완전-공유 구조를 가진다. 즉, 프로세서들이 시스템 내의 모든 자원들을 공유한다. 그리고 시스템 내에는 하나의 OS만 존재하며, 어느 프로세서든 공유 기억장치에 적재된 OS 코드를 수행할 수 있다. 대칭적이라는 명칭이 의미하듯, 모든 프로세서들은 동등한 권한으로 자원들을 공유하고, OS를 수행하며, 자신을 위한 작업 스케쥴링도 직접 수행한다. 이 분류에 속하는 시스템들의 주요 특징들을 정리하면 아래와 같다.

• 능력이 비슷한 다수의 프로세서들로 구성된다
• 프로세서들은 주기억장치와 IO 장치들을 공유하고, 버스 혹은 간단한 연결 방식에 의해 상호연결된다.
• 모든 프로세서들은 동등한 권한을 가지며, 같은 수준의 기능들을 수행할 수 있다.
• 프로세서들간의 통신은 공유-기억장치를 통하여 이루어진다.
• 작업 스케줄링 및 파일/데이터 수준에서의 프로그램들간 상호 작용은 하낭의 OS에 의해 통합적으로 지원된다.
• 상호연결망의 병목 현상으로 인하여 시스템 크기에 한계가 있다.

MPP는 주로 무공유 구조(shared-nothing architecture)를 기반으로 구성되는 대규모 병렬처리시스템이다. 이 시스템은 고속의 상호연결망을 통하여 서로 연결되는 수백 혹은 수천 개의 프로세싱 노드들로 이루어진다. 각 노드는 일반적으로 간단한 구조의 프로세서와 기억장치로 구성되며, 여러 개의 프로세서들이 하나의 노드에 포함되기도 한다. 또한 노드들 중의 일부분은 디스크와 같은 주변장치들과의 인터페이스를 가지고 있다. 그리고 대부분의 경우에 각 노드는 내부 자원 관리와 통신 자원을 위한 마이크로 커널 수준의 독립적인 운영체제를 탑제한다. 노드들 간의 통신은 메시지-패싱(message-passing) 방식을 주로 사용하며, 통신 거리를 최대한 단축시키고 대역폭을 높이기 위하여 복잡도가 높은 상호연결망(interconnection network)들을 사용한다.

CC-NUMA에서는 UMA 혹은  NUMA 시스템으로 구성되는 독립적인 노드들 여러개가 상호연결망에 의해 접속되며, 캐쉬 일관성 프로토콜에 의해 모든 노드의 캐쉬들과 주기억장치에 저장된 데이터들 간에 일관성이 유지된다. 이 모델의 시스템을 구성하기 위해서는 모든 노드들이 가지고 있는 기억장치들이 전체적으로 하나의 전역 주소 공간을 가지는 분산 공유 기억장치시스템으로 구성되어야 한다. 구성도를 그려서 좀 더 자세한 설명을 다른 문서에서 진행하겠다.

CC-NUMA의 주요 장점은 소프트웨어를 거의 변경하지 않고도 SMP보다 더 높은 수준의 병렬성을 이용할 수 있기 때문에 효율적인 성능을 제공할 수 있다는 점이다. 그러나 만약 기억장치 액세스의 많은 부분이 원격 노드에 대한 것이라면, 성능은 떨어질 것이다. 그러한 성능 저하는 캐쉬를 사용함으로써 어느 정도 방지될 수 있다. 그리고 프로그램 코드와 데이터들의 지역성이 높다면, 원격 기억장치 액세스의 빈도는 더 낮아질 것이다.

분산 시스템은 독립적인 컴퓨터시스템들이 전통적인 네트워크에 의해 연결되어 있는 컴퓨팅 환경을 말한다. 이것은 노드 수만ㅁ큼의 시스템 이미지들을 가진다. 즉, 각 노드는 별도의 OS를 가지고 독립적인 컴퓨터로서 기능을 수행하며, 다른 노드들과 정보를 교호나하거나 병렬처리를 수행할 때만 네트워크를 통하여 서로 통신한다. 각 노드는 PC, 워크스테이션, SMP, MMP 혹은 그들의 조합으로 이루어진다.

클러스터 컴퓨터랑 고속 LAN이나 네트워크 스위치에 의해 서로 연결된 PC들 혹은 워크스테이션들의 집합체를 말한다. 분산 시스템과는 달리, 클러스터 컴퓨터에서는 모든 자원들이 단일 시스템 이미지로 사용될 수 있다. 즉, 어느 한 노드 컴퓨터에 접속한 사용자는 클러스터를 코든 노드들에 포함된 프로세서들과 주기억장치 및 디스크들로 구성되는 하나의 큰 시스템으로 간주하고 사용할 수 있다. 그리고 클러스터 내의 어느 한 컴퓨터에 결함ㅁ이 발생하더라도 다른 컴퓨터가 신속히 대체될 수 있기 때문에 가용성도 높다. 이와 같은 새로운 시스템 설계 개념을 이용하면, 저렴한 가격으로도 높은 성능과 신뢰도를 가지는 병렬처리 환경을 구축할 수 있기 때문에, 최근 웹 컴퓨팅 서버 등의 개발에 널리 사용되고 있다.

이전에 작성한 Flynn의 분류들 중에서 병렬 컴퓨터의 구조로써 가장 널리 채택되고 있는 MIMD 조직은 기억장치의 위치와 주소지정 방식 및 프로세서들에 의한 기억장치 엑세스 시간에 따라 4가지 모델로 구분될 수 있다.

• 균일 기억장치 액세스(Uniform Memory Access: UMA) 모델
• 불균일 기억장치 액세스(Nonuniform Memory Access: NUMA) 모델
• 개쉬-온리 기억장치 액세스(Cache-Only Memory Access: COMA) 모델
• 무원격 기억장치 엑세스(No-Remote Memory Access: NORMA) 모델

UMA 모델에서는 모든 프로세서들이 상호연결망에 의해 접속된 주기억장치 모듈들을 공유한다. 그리고 프로세서들은 공유 기억장치의 어느 영역이든 같은 방법으로 액세스할 수 있으며, 그에 걸리는 시간도 동일하다. 이 모델에 기반을 둔 시스템은 하드웨어가 간단하고 프로그래밍이 용이하다는 장점이 있는 반면에, 공유 자원들에 대한 경합이 높아지기 때문에 시스템 크기에 한계가 있다. 일반적으로, 상호연결망으로 버스가 사용되는 경우에는 최대 30개의 프로세서들, 크로스바 스위치 혹은 다단계 상호연결망 등이 사용되는 경우에는 최재 64개의 프로세서들로 구성될 수 있다.

NUMA 모델은 시스템 크기에 대한 UMA 모델의 한계를 극복하고 더 큰 규모의 시스템을 구성하기 위한 것으로써, 다수의 UMA 모델들이 상호연결망에 의해 접속되며, 전역 공유 기억장치(Global Shared Memory)도 가질 수 있다. 이 모델에서는 시스템 내의 모든 기억장치들이 하나의 주소 공간을 형성하는 분산 공유 기억장치 구조를 가지기 때문에, 프로세서들은 자신이 속한 UMA 모듈의 기억장치뿐 아니라 GSM 및 다른 UMA 모듈의 기억장치들도 직접 액세스 할 수 있다. 그러나 기억장치 액세스 시간은 액세스 할 기억장치의 위치에 따라 잘라진다. 즉, 프로세서에 의한 기억장치 액세스는 세 가지 패턴으로 분류된다.

1. 지역 기억장치 엑세스: 자신이 속한 UMA 모듈 내의 기억장치에 대한 액세스로써, 가장 짧은 시간이 소요된다.
2. 전역 기억장치 액세스: 프로세서가 원하는 데이터가 전역 공유 기억장치에 있는 경우에 이루어지는 액세스다.
3. 원격 기억장치 액세스: 다른 UMA 모둘에 위치한 기억장치로부터 데이터를 액세스하는 경우로, 가장 긴 시간이 소요된다.

COMA 모델에서는 시스템 내에 주기억장치가 존재하지 않으며, 각 프로세서가 가지고 있는 기억장치는 모드 캐쉬로부터 동작한다. 모든 캐쉬들은 하나의 공통 시억장치 주소공간을 형성하며, 다른 프로세서의 개쉬에 대한 엑세스는 분산 캐귀 디렉토리들에 의해 지원된다. 초기 단계에서는 데이터들이 임의의 캐쉬에 저장되어 있으며, 실행 시간 동안에 실제 그 데이터들을 사용할 프로세서의 캐쉬로 이동된다.

NORMA 모델은 이름에서 의미하듯, 프로세서가 원격 기억장치는 직접 액세스할 수 없는 병렬컴퓨터 구조이다. 프로세서와 기억장치로 구성되는 노드들은 메시지 전송 방식을 지원하는 상호연결망에 의해 서로 접속된다. 그러나 어떤 노드의 프로세서가 다른 노드의 기억장치에 저장되어 있는 데이터를 원하는 경우에, 그 기억장치를 직접 액세스하지 못한다. 그 대신에, 그 노드로 기억장치 액세스 요구 메시지를 보내며, 메시지를 받은 노드는 해당 데이터를 인출하여 그것을 요구한 노드로 보내준다. 이러한 시스템에서는 각 노드가 별도의 기억장치를 가지고 있기 때문에 분산 기억장치 시스템이라고도 부른다. 이 모델을 위한 상호 연결망들이 별도로 존재하므로 이것들은 나중에 별도의 문서로 다룬다.

병렬 컴퓨터는 구조적 특징에 따라서도 분류가 될 수 있다. 구조적인 부분에 대해서는 지속적으로 새로운 것들이 많이 만들어지고 하지만, 대표적인 것들만 우선 살펴보려 한다.

• 파이프라인 컴퓨터

파이프라인 컴퓨터는 시간적 병렬성을 이용한 중첩 계산을 수행하는 시스템이다. 즉, 체인 평태로 연결된 연산 요소들이 동시에 연산을 수행함으로써 병렬성을 제공하는 것이다. 일반적으로 파이프라이닝은 프로세서의 명령어 실행 유니트와 ALU 내부 회로에 적용된다. 그리고 파이프라인된 ALU들은 벡터 처리 유니트의 구현으로 확장될 수 있다. (벡터는 1차원 데이터 배열을 말한다.) 만약 n개의 데이터들로 구성된 두 개의 벡터들에 대한 덧셈 ㅁ연산을 수행한다면, 같은 위치의 두 데이터들을 각각 더해야 한다. 이와 같이 n개의 동일한 연산들이 반복 수해오디는 경우에 파이프라인이 매우 효과적이며, Cray Y-MP와 같은 슈퍼컴퓨터들이 여러 개의 벡터 유니트들을 이용하는 대표적인 시스템이다.

• 배열 프로세서

배열 프로세서는 SIMD  조직에 해당되며, 공간적 병렬성을 실현하기 위해 여러 개의 동기화된 프로세싱 유니트들을 사용한다. 이 유니트들은 하나의 제어 유니트로부터 동시에 전송되는 동일한 연산 명령을 서로 다른 데이터에 대하여 수행한다. 따라서 이러한 처리 방식을 데이터 병렬모델이라고 부른다.

• 다중프로세서 시스템

다중프로세서 시스템은 MIMD 조직에 해당되며, 시스템 자원들(기억장치, IO 등)을 공유하는 여러 개의 프로세서들을 이용하여 비동기적 병렬성을 실현하는 시스템이다.

배열 프로세서와 다중 프로세서 시스템의 근본적인 차이점은 프로세서들이 수행하는 프로그램의 독립성에 있다. 배열 프로세서에서는 모든 프로세서들이 동일한 프로그램을 동기적으로 실행하고, 다중프로세서 시스템에서는 각 프로세서들이 서로 다른 별도의 프로그램을 비동기적으로 실행한다.

이 시스템들에 대해서는 이것들 말고도 정리할 것들이 많은데 아예 별도의 문서를 또 만들어서 작성해야겠다.

설명하다가 넘어간 부분이 있어서 마저 설명하려 한다.

프로세스 단위 병렬성을 좀 더 쉽게 이해해보기 위해 예시 그림을 그려보고 정리하려 한다.

예를 들어, 아래와 같은 프로그램을 살펴봅니다.

for i=1,5
{
x(i) = x(i-1)+y(i-1)
y(i) = x(i-2)+y(i-2)

s(i) = x(i)+y(i)
if s(i) >= 100
then a=a+1
else b=b+1
}

이런 프로그램 코드 중에서는 두 개의 프로세스들로 나누어질 수 있다. 앞에 두 문장과 나머지 문장으로 P1, P2로 나눠서 생각해 볼 수 있다. 그런데 이 경우에 두 프로세스들은 병렬로 처리될 수 없다. 그 이유는 P1(i)에서 계산되는 x(i), y(i)를 P2(i)에서 사용해야 하기 때문이다. 그러나, 더 면밀히 분석해보면, P1(i)와 P2(i-1)은 병렬로 처리될 수 있다는 것을 알 수 있다. 즉, 이 프로세스들의 처리 과정을 아래 그림에서처럼 나타내어볼 때, 대각선으로 친 부분에 대해서는 두 개 씩 동시 처리가 될 수 있다.

결과적으로, I=1일 대는 P1만 처리되지만, i=2부터는 P1, P2가 병렬로 처리될 수 있게 된다. 이때, P2를 처리하는 프로세서는 P1을 처리하는 프로세서로부터 그 이전에 계산한 x,y를 전송받아서 사용해야 하기 때문에, 프로세서간 통신이 필요하게 된다.

이처럼 프로세스 단위로 병렬처리를 할 경우에는 다른 처리단위와 달리 병렬화를 위해 확인해야 할 것들이 많다. 그리고 이런 규칙을 사용자(개발자)가 직접 지정할 수도 있고, 컴파일러에 의해 자동화될 수도 있다.

컴퓨터시스템을 분류하는 방식은 여럿 존재한다. 가장 널리 사용되는 방식이 바로 Flynn의 분류(Flynn’s classificaation) 방식이다. 방식 이름은 어색할 지 모르겠지만, 내용을 보면 아마 금방 “아, 그거!”할 것이다. 이 분류 방식에서는 프로세서들이 처리하는 명령어와 데이터의 스트림의 수에 따라 디지털 컴퓨터를 네 가지로 분류하고 있다. 여기서 맘ㄹ하는 스트림이란 하나의 프로세서에 의하여 순서대로 처리되는 일련의 명령어들과 데이터들의 흐름을 말한다. 즉, 명령어 스트림이란 프로세서에 의해 실행되기 위하여 순서대로 나열된 명령어 코드들의 집합을 의미하고, 데이터 스트림이란 그 명령어들을 실행하는 데 필요한 순서대로 나열된 데이터 집합을 의미한다.

명령어와 데이터 스트림을 처리하기 위한 하드웨어 구조에 따른 Flynn의 분류와 간략한 설명은 다음과 같다.

• SISD 조직(Single Instruction stream Single Data stream): 한 번에 한 개씩의 명령어와 데이터를 순서대로 처리하는 단일프로세서 시스템에 해당한다. 이러헌 시스템에서는 명령어가 순서대로 실행되지만, 실행 과정은 여러 개의 단계들로 나누어 시간적으로 중첩시킴으로써 실행 속도를 높이도록 파이프라이닝되어 잇는 것이 일반적이다. 또한 SISD 시스템에서 하나의 프로세서 내에 여러 개의 명령어 실행 유니트들이나 ALU 들을 포함함으로써, 동시에 두 개 혹은 그 이상의 명령어들을 동시에 실행하는 슈퍼스칼라(superscalar) 구조도 많이 사용되고 있다. 파이프라이닝과 슈퍼스칼라는 프로세서 내부에서 병렬처리를 이용하는 구조라고 할 수 있다.
• SIMD 조직(Single Instruction stream Multiple Data stream): 배열 프로세서(Array Processor)라고도 불린다. 이러한 시스템은 여러 개의 프로세싱 유니트(PU)들로 구성되고, 프로세싱 유니트들의 동작은 모두 하나의 제어 유니트에 의해 통제된다. 모든 PU들은 하나의 제어 유니트로부터 동일한 명령어를 받지만, 명령어 실행은 서로 다른 데이터에 대하여 이루어진다. 또한 모든 PU들이 기억장치를 공유하는 경우도 있고, 각 PU가 기억장치 모듈을 독립적으로 가지는 분산 기억장치 구조도 가능하다.
• MISD 조직(Multiple Instruction stream Single Data stream): 한 시스템 내에 n개의 프로세서들이 있고, 각 프로세서들은 서로 다른 명령어들을 실행하지만, 처리하는 데이터들은 하나의 스트림이다. 다시 설명하면, 프로세서들이 파이프라인 형태로 연결되어서, 한 프로세서가 처리한 결과를 다음 프로세서로 보내는 방식이다. 그러나 이 조직은 컴퓨터 구조 설계자들이 관심을 끌지 못하고 있으며, 실제로 이러한 시스템은 이론으로만 존재한다.
• MIMD 조직(Multiple Instruction stream Multiple Data stream): 대부분의 다중프로세서 시스템(multiprocessor system)과 다중컴퓨터 시스템(multiple-computer system)이 이 분류에 속한다. 이 조직에서는 n개의 프로세서들이 서로 다른 명령어와 데이터를 처리한다. MIMD 시스템은 프로세서들간의 상호작용 정도에 따라 두 가지로 나뉘는데, 그 정도가 높은 구조를 밀결합 시스템(tightly-coupled system)이라 하고, 그 정도가 낮은 구조를 소결합 시스템(loosely-coupled system)이라고 한다. 밀결합 시스템의 전형적인 구조는 기억장치가 모든 프로세서들에 의하여 공통으로 사용되는 공유 기억장치(shared-memory architecture) 구조이다. 소결합 시스템은 각 프로세서들이 자신의 지역 기억장치(local memory)를 가진, 독립적인 컴퓨터 모듈로 구성되고, 프로세서들간의 통신은 메시지 패싱(message-passing) 방식에 의해 이루어지는 구조를 가지고 있다.

병렬 프로그래밍을 배울 때, 혹은 멀티코어 CPU에 대한 자료를 봤을 때 봤던 내용들이 많이 있을 것이다. 병렬컴퓨터는 프로그램 코드와 데이터를 병렬로 처리하는 시스템이므로, Flynn의 컴퓨터 분류들 중에서 SIMD와 MIMD 조직이 그에 해당하는 조직이다.

그리고 최근에는 SISD 조직에 해당하는 단일프로세서 시스템도 프로세서 내부에 파이프라이닝과 슈퍼스칼라 구조를 이용하기 때문에 병렬처리를 구현하는 시스템으로 볼 수 있다. 이러한 SISD 구조의 프로세서들을 다이에 여렷 구성하고 내부에서 병렬로 제어 가능하도록 연결함으로써 병렬처리만을 위한 프로세서를 연구하기도 한다.

병렬처리란 여러 개의 프로그램들 혹은 한 프로그램의 분할된 부분들을 다수의 프로세서들을 이용하여 동시에 처리하는 것이라고 하였다. 그런데 병렬처리에 참여하는 각 프로세서(혹은 독립적인 컴퓨터 노드)에 분담되는 단위 프로그램의 크기에 따라 다양한 수준의 병렬성들이 존재할 수 있다. 그 단위 프로그램은 각각 독립적인 작업일 수도 있고, 더 작게 분할된 프로그램 세그먼트도 될 수 있다. 다만 그들이 서로 독립적으로 처리될 수만 있으면 된다. (이 부분을 원자성이라고 한다.)

• 작업 단위(job level): 서로 다른 사용자들에 의해 제출된 작업 프로그램들 혹은 한 사용자에 의해 제출된 여러 개의 독립적인 작업 프로그램 단위로 병렬처리 되는 것을 의미한다. 예를 들어, 어느 교수가 강의와 연구를 동시에 수행하는 과정에서 성적관리 프로그램과 실험 데이터를 처리하는 프로그램을 동시에 처리하려고 한다면, 그 프로그램들은 서로 독립적으로 처리될 수 있다. 만약 컴퓨터 시스템 내에 두 개 이상의 프로세서들이 있다면, 이 두 작업 프로그램들은 병렬로 처리될 수 있다.
• 태스크 단위(task level): 하나의 큰 작업은 내부적으로 서로 다른 기능을 수행하는 더 작은 프로그램들로 분리될 수 있다. 예를 들어, 팔과 다리를 가진 로봇이 있다고 하였을 때, 이 로봇을 움직이기 위해서는 부착된 여러 개의 센서들로부터 정보를 입력받아서 팔과 다리를 적절히 제어하도록 명령하는 컴퓨터 프로그램이 필요하다. 전체 프로그램은 하나의 작업 프로그램이지만, 그것은 여러 개의 태스크들로 분할 될 수 있다. 예시와 같이 보면, 각 팔을 제어하기 위한 태스크들과 각 다리를 제어하기 위한 태스크들로 나누어질 수 있으며, 그들은 병렬로 처리될 수 있다. 물로 ㄴ그들은 처리되는 도중에 상호 연관되는 정보를 교활할 필요도 있을 것이다.
• 프로세스 단위(process level): 각 태스크는 다시 여러 개의 프로세스들로 나누어 질 수 있다. 여기서 각 프로세스는 특정 함수를 계산하는 정도의 크기이다. 분할은 사용자에 의해 임의로 이루어질 수도 있고, 컴파일에 의해 자동적으로 이루어지도록 할 수도 있다. 프로세스 단위에 대해서는 예시를 보면서 이해하는 것이 좋기 때문에 별도로 글을 작성하도록 하자.
• 변수 단위(variable level): 프로세스 단위 병렬처리에서 각 프로세스는 여러 개의 프로그램 코드들로 이루어져 있는데, 각 코드(명령어)는 어떤 입력 변수를 받아서 연산을 수행한 후에 출력 변수를 생성한다. 그런데 한 프로세스 내의 여러 변수들을 동시에 계산하는 것이 가능할 수 있기 때문에 프로세스 내에도 병렬성이 존재한다. 그 이유는 변수들이 이전의 반복 루프에서 계산된 변수들을 이용하여 계산되기 때문이다.
• 비트 단위(bit level): 대부분의 컴퓨터에서는 비트 단위의 병렬 계산이 허용된다. 즉, 하나의 데이터 단위를 구성하고 있는 각 비트들에 대한 독립적인 연산들을 병렬로 처리할 수 있다. 이것은 가장 낮은 수준의 병렬성이라고 할 수 있다.

병렬 컴퓨터의 성능과 효율을 높이기 위해서는 이와 같은 다양한 수준의 병렬성을 최대한 이용할 수 있어야 하며, 그를 위해서는 시스템 구조와 프로세서 구조가 적절히 설계되어야 한다.

병렬 프로그래밍이 여러곳에서 말 나오면서 제일 많이 들어봤을 법칙이다. 병렬 처리를 이용하여 얻을 수 있는 속도 향상에 대한 한계를 제시한 법칙이다.

직렬 알고리즘 중에서 반드시 순차적으로 처리되어야 하는(= 병렬화 할 수 없는) 부분의 비율을 Amdahl의 비율이라 하는데, 여기서는 a라고 정하고 이야기를 진행한다. 실제 시스템에서 병렬화 할 수 없는 부분에 해당하는 예를 보면, 프로그램이나 데이터를 다운로드 하는 데 걸리는 시간, 운영체제의 커널 실행 시간 혹은 연산들 간에 선행 관계가 존재하는 경우 등등이 있다. a를 고려하면 Tp는 아래와 같은 식이 된다.

그를 통해 속도 향상은 아래 식으로 표현된다.

그런데, 만약 사용 가능한 프로세서의 수가 무한대라고 가정하면, 속도 향상의 비율값은 아래와 같아진다.

즉, 병렬처리를 이용하여 얻을 수 있는 최대 속도 향상은 a값의 역수가 된다. 예를 들어, 계산할 알고리즘 중에 반드시 순차적으로 처리해야 할 부분이 5%가 있다면, 프로세서가 무한히 많이 사용되더라도 속도 향상은 최대 1/0.05 = 20배 밖에 되지 못한다는 것이다. a값이 큰 경우에는 프로세서의 수가 증가하더라도 속도 향상은 거의 얻지 못하고 포화되며, 결과적으로 시스템 효율이 크게 떨어진다는 것을 알 수 있다.

그러나, Amdahl의 법칙도 처리할 응용의 특성에 따라 해석이 달라질 수 있다. 예를 들어, 대부분의 공학 및 과학 계산 문제들에서 Amdahl의 비율 a는 문제의 크기 n에 따라 값이 달라지게 된다. 여기서 문제의 크기란 선형방정식의 차수, 즉 변수의 개수에 해당한다. 그 크기가 증가하면 그만큼 계산량이 증가하게 되는 반면에, 순차적으로 처리되어야 하는 부분은 거의 일정하게 고정되기 때문에 a값은 상대적으로 감소한다. 이렇게 되면 즉.

이 될 수 있다. 따라서 그러한 응용들을 처리하는 경우에 문제의 크기가 무한대로 커진다고 가정하면, 속도 향상은 아래의 식과 같이 정의될 수 있다.

이러한 예는 실제로 미국의 Sandia 국립연구소에서 몇 가지 응용들을 1024개의 프로세서들로 구성된 하이퍼큐브시스템에서 처리한 결과, 거의 선행적인 성능 향상을 얻을 수 있다는 것을 입증하였다. (유명한 논문이다. 단, 작성날짜가….ㅠㅠ J.L.Gustafson, “Reevaluating Amdahl’s Law”, Communications of the ACM, Vol31, No. 5, Maay 1988, pp 532-533)

결론적으로, 큰 응용 문제가 효율적인 방법으로 처리되는 이상적인 경우에는 Amdahl의 법칙과는 달리, 프로세서의 수에 비례하는 선형적인 속도 향상을 얻을 수 있다는 것이다. 여기서 주의해야 할 사항은 문제의 크기가 증가하면 기억장치의 용량도 증가해야 하며, 그렇지 않은 경우에는 속도 향상이 프로세서의 수보다 기억장치 용량에 의해 더 큰 영향을 받을 수 있다는 점이다. 이 부분은 이후에도 지속적으로 설명하겠다.

병렬 컴퓨터의 성능 한계에 대한 초기의 비관적인 내용들을 확인해보았다. 이런 예측들은 응용 문제의 크기가 증가하고 효율적인 통신 매커니즘이 설계되면 충분히 개선될 수 있는 것이 입증되고 있었고, 그에 대해서도 현재 실제로 입증되고 있다. 그래서 최근의 개발된 거의 모든 고성능컴퓨터시스템들은 병렬처리 기술을 사용하고 있다.

P개의 프로세서들을 사용한 병렬컴퓨터에서 프로세서들 간의 정보 교환에 따른 통신 오버헤드 때문에 시스템 성능은 P배가 아닌 log2P배까지밖에 개선되지 못한다는 주장이다.

이런 주장은 1960년대에 적은 수의 프로세서들로 구성된 병렬처리시스템들을 이용하여 연구한 결과에 근거한 것이었다. 그러한 시스템들은 근대적인 운영체제를 사용하였는데, 프로세서의 수가 조금만 증가하여도 그에 따른 오버헤드가 매우 높아졌다. 통신 오버헤드가 커지면 프로세서의 이용률이 떨어지고 그것이 성능 저하의 주요 요인이 되었다.

그러나, 이후에 프로세서의 이용률을 높일 수 있는 여러 가지 방법들이 개발되었다. 우선, 더 효율적인 병렬 알고리즘들과 상호연결망들이 개발되었다. 또한 어떤 한 프로그램이 시스템 내의 모든 프로세서들을 이용하지 않는 경우에는, 남아있는 프로세서들이 다른 프로그램들을 처리하도록 해주는 스케쥴링 기술도 개발되었다. 이러한 기술들은 Minsky가 고려하지 못한 것들이었다.

물론, 통신 오버헤드 때문에 P개의 프로세서들을 가진 시스템의 성능이 단일프로세서 시스템 성능의 P배는 되지 못한다. 그러나 최근에 개발되고 있는 시스템들의 성능이 Minsky가 예측한 것보다는 훨씬 더 높아진 것에 대해서는 사실이다. 그로 인해 이 비관적인 예측 또한 어느 정도 빗나가게 되었다.