병렬 컴퓨팅

병렬 컴퓨팅(parallel computing) 또는 병렬 연산은 동시에 많은 계산을 하는 연산의 한 방법이다. 크고 복잡한 문제를 작게 나눠 동시에 병렬적으로 해결하는 데에 주로 사용되며, 병렬 컴퓨팅에는 여러 방법과 종류가 존재한다. 그 예로, 비트 수준, 명령어 수준, 데이터, 작업 병렬 처리 방식 등이 있다. 병렬 컴퓨팅은 오래전부터 주로 고성능 연산에 이용되어 왔으며, 프로세서 주파수 의 물리적인 한계에 다가가면서 문제 의식이 높아진 이후에 더욱 주목받게 되었다. 최근 컴퓨터 이용에서 발열과 전력 소모에 대한 관심이 높아지는 것과 더불어 멀티 코어 프로세서를 핵심으로 컴퓨터 구조에서 강력한 패러다임으로 주목받게 되었다.
병렬 컴퓨터들은 대체적으로 하드웨어의 병렬화 방법에 따라 분류된다. 클러스터, MPP, 그리드는 여러 컴퓨터에서 한 가지 작업을 하도록 설계되었다. 멀티 코어나 멀티 프로세서 컴퓨터들은 여러 개의 처리 요소(CPU 등)을 한 기기에 탑재하고 작업한다. 특수화된 병렬 컴퓨터 구조들은 가끔씩 고전적인 프로세서들과 함께 특정한 작업을 가속화 시키는 목적으로도 사용된다.
병렬 컴퓨터 프로그램들은 순차적 프로그램보다 난해하다. 왜냐하면 동시처리는 여러 종류의 새로운 잠재적 소프트웨어 버그를 가지고 있기 때문이다. (경쟁 상태가 가장 흔하다) 통신과 동기화 를 요구하는 다른 하위 작업들은 병렬 프로그램 성능의 전형적인 방해요소다. 병렬화된 프로그램의 속도 향상은 암달의 법칙에 의해서 그 결과가 결정된다.

배경

전통적으로 컴퓨터 소프트웨어는 직렬 컴퓨팅 방식을 기본으로 작성되어 왔다. 문제를 해결하는 데 있어서 알고리즘은 직렬형 명령들로 이루어졌고 그 명령들은 하나의 CPU에 의해서 실행되었다. 한 명령이 한 번에 하나씩 실행된다. 하나가 끝나면 그 다음 명령이 실행된다.
병렬 컴퓨팅은 여러 개의 처리 요소(프로세서 등)를 이용하여 한 번에 문제를 해결한다. 이것은 그 문제를 독립적인 부분들로 나눠서 각 처리 요소가 그 부분의 알고리즘들을 한 번에 다른 요소들과 처리를 할 수 있게 하는 것을 가능하게 했다. 그 처리요소들은 여러 자원들을 포함한다. 예를 들면 한 컴퓨터에 있는 멀티프로세서, 여러 네트워크 컴퓨터들, 특수 하드웨어, 아니면 그런 것들을 섞어 쓸 수도 있다.
컴퓨터의 클럭 속도는 1980년도 중반부터 2004년까지 컴퓨터 성능을 향상시키는 데 가장 영향력 있는 요소였다. 프로그램 실행시간은 명령어 수를 명령어 당 평균시간을 곱한 것과 같았는데 클럭수를 늘리면 명령을 실행하는 평균시간은 짧아진다.
그러나 칩의 전력소모량은P = C × V² × F의 공식에 따른다. 여기서, P는 전력, C는 한 클럭 주기 당 스위칭된 전기용량(입력이 변화하는 트랜지스터의 개수에 비례), V는 전압(voltage)이고 F는 주파수(프로세서 속도)를 의미한다. 주파수 수(프로세서 속도)를 높이면 전력 사용량이 늘어난다는 뜻이다. 전력 사용량이 계속 높아가자 결국 인텔은 2004년 5월에 테자스와 제이호크(Tejas and Jayhawk)를 취소시키기에 이른다. 그 사건은 주파수 척도에 의한 컴퓨터 구조 패러다임이 끝나는 것을 의미하게 된다.
무어의 법칙은 매 18에서 24개월 동안 집적도가 두 배씩 늘어난다는 것을 예측하는데, 전력소모량 사건에 계속됐던 예측은 끝이나고 말지만 무어의 법칙은 여전히 유효하다. 주파수 척도는 끝이 났지만 추가적인 트랜지스터들은 추가적인 병렬 컴퓨팅에 쓰이게 된다.

잘게 나눔(fine-grained), 크게 나눔(coarse-grained), 처치 곤란 병렬(embarrassingly parallel)

응용 프로그램들은 가끔 얼마나 자주 하위 작업들이 동기화 되나 혹은 서로 통신해야 하냐에 따라서 분류가 나뉘기도 한다. 만약 병렬 응용 프로그램의 하위 작업들이 초당 통신을 많이 해야 하면 잘게 나뉘었다고 하고 초당 통신을 많이 안해도 되면 크게 나뉘었다고 한다. 그리고 만약 아주 가끔 통신하거나 아예 하지 않는다면 처치 곤란 병렬 이라고 한다. 처치 곤란 병렬 응용 프로그램은 가장 쉬운 병렬화로 알려져 있다.

일관성 모델들

병렬 프로그래밍 언어와 병렬 컴퓨터들은 반드시 일관성 모델 (메모리 모델이라고도 불린다) 을 가지고 있어야 한다. 일관성 모델이란 컴퓨터 메모리 위에서 어떻게 연산들을 할 것인지와 어떻게 결과들을 만들것인지 규칙을 정의하는 것이다.
일관성 모델 중에는 레슬리 램포트의 순차 일관성 모델 (sequential consistency) 이라는 것이 있다. 순차 일관성이란 병렬 프로그램 실행시 순차적 프로그램에서 나오는 결과와 똑같이 만드는 병렬 프로그램의 특성이다. 특히 만약에 “…어떤 실행에서의 결과가 모든 프로세서들의 연산이 어떤 순차적인 차례로 실행되거나 그 연산들의 각 독립적인 프로세서가 그 프로그램에 의해 보여주는 순서가 똑같다면” 프로그램은 순차적으로 모순이 없다.
소프트웨어 트랜잭셔널 메모리 (Software transactional memory (이하 STM)) 는 흔한 방식의 일관성 모델이다. STM은 데이터베이스 이론에서 원자 트랜잭션의 컨셉과 그것을 메모리 접근에 적용한걸 가져온 것이다.
수학적으로 이런 모델들은 여러가지 방법으로 표현될 수 있다. 1962년 칼 아담 페트리의 박사 논문으로 소 개된 페트리 넷은 일찍이 일관성 모델들을 체계적으로 분류하는걸 시도했던 사례다. 자료흐름 이론(dataflow theory) 은 그것을 기반으로 만들어졌고 자료흐름 구조 (Dataflow architectures) 는 자료흐름 이론의 아이디어들을 물리적인 방법에 의해 만들어졌다. 1970년도 후반에 시작된 통신 시스템 미적분 (Calculus of Communicating System) 이나 소통 순차적 프로세스 (Communicating Sequential Processes)들 같은 프로세스 미적분 (process calculi)들이 구성요소들의 상호 통합 이라는 대수적 논리에 의해서 개발될 수 있었다. 좀 더 최근에는 파이-미적분 같은 미적분 들이 동적 기하학에 대한 성능 향상을 위해 그 프로세스에 추가되었다. 램포트의 TLA+ 같은 논리들과 대각합 (traces)이나 액터 이벤트 다이어그램 (Actor event diagrams) 같은 수학적 모델들이 동시 행위 시스템의 행동을 설명하기 위해서 개발됐다.

비트수준 병렬처리

초고밀도 집적회로(VLSI)의 등장으로 1970년대부터 1986년까지 컴퓨터 칩 제조 기술은 두 배의 워드 크기를 가진 컴퓨터 구조를 만들어 내서 속도 향상을 달성했다. 프로세서의 정보량은 사이클 단위의 조작이 가능했는데, 워드 크기를 늘리게 되면 워드 길이보다 큰 변수 위에서 실행되어야 했던 명령어 개수가 줄어들게 됐다. 예를 들자면, 8비트 프로세서는 반드시 16비트 정수형 두 개를 추가시켜야 한다. 프로세서는 반드시 먼저 8 하위 비트를 각 표준 추가 명령어를 정수형으로부터 추가시켜야 하고 그 다음에 하위에서 추가로 ADC 명령과 캐리를 사용하는8 상위 비트를 추가시킨다. 8비트 프로세서는 한 개의 연산을 완료하기 위해서 2개의 명령어들을 필요로 하게 되고, 16비트 프로세서는 1개의 연산을 1개의 명령어로 끝낼수 있게 된다.
역사적으로 4비트 마이크로 프로세서들은 8비트, 16비트 그리고 32비트 마이크로 프로세서들에 의해서 교체됐다. 이 유행은 일반적으로 두 세대를 범용 컴퓨터 표준이 된32비트 프로세서의 등장과 함께 끝나는데, 최근 (2003-2004)엔 64비트 프로세서들을 가진x86-64 구조들이 등장하면서 표준이 된다.

명령어 수준 병렬 처리

컴퓨터 프로그램은 명령어들의 흐름이 프로세서에 의해서 실행되는걸 바탕으로 한다. 이 명령어들은 재 순차와 결과의 변경 없이 한꺼번에 그룹단위로 병렬실행이 가능했다. 이것을 명령어 수준 병렬화라고도 한다. 이 명령어 수준 병렬화는 80년대 중반부터 90년대 중반까지 컴퓨터 구조를 주름잡았다.
현대의 프로세서들은 다단계 명령어 파이프라인을 가졌다. 파이프라인에서 각 단계는 다른 행동을 하는 같은 단계의 명령어를 실행하는 프로세서와 일치시킨다. N 스테이지 파이프라인은 N 개 만큼의 다른 명령어들을 다른 완료된 단계에서 가질수 있다. 파이프라인된 프로세서의 정석은 RISC 프로세서다. (다섯 개의 단계 – 명령어 패치, 디코드, 실행, 메모리 접근, 다시 써넣기 (write back) 가 정석이다.) 펜티엄 4 프로세서는 31단계의 파이프라인을 가지고 있다.
파이프라인을 할 때 명령어 수준 병렬화에서 몇 프로세서들은 한 개 이상의 명령어를 한 번에 만들수 있었다. 이것을 슈퍼스칼라 프로세서라고도 한다. 만약에 자료종속성만 없다면 명령어들은 한꺼번에 합쳐질수 있다. 스코어보딩 (Scoreboarding)과 토마줄로 알고리즘 (스코어보딩과 비슷하지만 레지스터 리네이밍 (Register renaming)을 사용한다) 이 두 가지가 가장 흔한 비 순차적 실행과 명령어 수준 병렬화 기술들이다.

자료 병렬 처리

자료 병렬화는 프로그램 루프에 내재된 병렬화다. 프로그램 루프는 병렬로 처리된 다른 컴퓨팅 노드들의 자료를 분산시키는데 초점을 맞춘다. “루프를 병렬시키는 것은 가끔 비슷한 (완전 같을 필요는 없이) 순차 연산이나 큰 자료구조의 요소에서 실행되는 함수들을 실행시키게 한다.” 많은 과학적, 공학적인 응용물들이 자료 병렬화를 보여준다.
루프가 가지고 있는 종속성은 이전 반복의 하나 이상의 결과에 종속된다. 루프의 종속성은 병렬화 루프에 의해 막힌다. 예를 들면 아래의 피보나치 수 의사코드를 보자.
1      PREV1 := 0
2      PREV2 := 1
3      do:
4         CUR := PREV1 + PREV2
5         PREV1 := PREV2
6         PREV2 := CUR
7      while (CUR < 10)
이 루프는 병렬화할 수 없다. 왜냐하면 CUR 이 각 루프를 도는 동안 그 자신(PREV2)과 PREV1에 종속되기 때문이다. 각 반복이 그 이전 결과에 종속되므로 병렬화할 수 없다. 문제의 크기가 크면 클수록 자료의 병렬화의 유효성은 일반적으로 커진다.

작업 병렬처리

작업 병렬화는 병렬 프로그램 “전체적으로 다른 계산들은 같거나 다른 자료들에서 실행될 수 있다.” 라는 성질을 가지고 있다. 이것을 자료 병렬화와 상반시키면 계산이 같거나 다른 자료들에서 실행될 수 있다. 작업 병렬화는 일반적인 규모의 문제와 함께 측정되지 않는다.