분류 전체보기 에 해당되는 글 57건

2011. 12. 13. 21:35

병렬 컴퓨팅

기본카테고리 2011. 12. 13. 21:35

병렬 컴퓨팅

병렬 컴퓨팅(parallel computing) 또는 병렬 연산은 동시에 많은 계산을 하는 연산의 한 방법이다. 크고 복잡한 문제를 작게 나눠 동시에 병렬적으로 해결하는 데에 주로 사용되며^[1], 병렬 컴퓨팅에는 여러 방법과 종류가 존재한다. 그 예로, 비트 수준, 명령어 수준, 데이터, 작업 병렬 처리 방식 등이 있다. 병렬 컴퓨팅은 오래전부터 주로 고성능 연산에 이용되어 왔으며, 프로세서 주파수^[2]의 물리적인 한계에 다가가면서 문제 의식이 높아진 이후에 더욱 주목받게 되었다. 최근 컴퓨터 이용에서 발열과 전력 소모에 대한 관심이 높아지는 것과 더불어 멀티 코어 프로세서를 핵심으로 컴퓨터 구조에서 강력한 패러다임으로 주목받게 되었다^[3].

병렬 컴퓨터들은 대체적으로 하드웨어의 병렬화 방법에 따라 분류된다. 클러스터, MPP, 그리드는 여러 컴퓨터에서 한 가지 작업을 하도록 설계되었다. 멀티 코어나 멀티 프로세서 컴퓨터들은 여러 개의 처리 요소(CPU 등)을 한 기기에 탑재하고 작업한다. 특수화된 병렬 컴퓨터 구조들은 가끔씩 고전적인 프로세서들과 함께 특정한 작업을 가속화 시키는 목적으로도 사용된다.

병렬 컴퓨터 프로그램들은 순차적 프로그램보다 난해하다.^[4] 왜냐하면 동시처리는 여러 종류의 새로운 잠재적 소프트웨어 버그를 가지고 있기 때문이다. (경쟁 상태가 가장 흔하다) 통신과 동기화 를 요구하는 다른 하위 작업들은 병렬 프로그램 성능의 전형적인 방해요소다. 병렬화된 프로그램의 속도 향상은 암달의 법칙에 의해서 그 결과가 결정된다.

[편집] 배경

전통적으로 컴퓨터 소프트웨어는 직렬 컴퓨팅 방식을 기본으로 작성되어 왔다. 문제를 해결하는 데 있어서 알고리즘은 직렬형 명령들로 이루어졌고 그 명령들은 하나의 CPU에 의해서 실행되었다. 한 명령이 한 번에 하나씩 실행된다. 하나가 끝나면 그 다음 명령이 실행된다. ^[5]

병렬 컴퓨팅은 여러 개의 처리 요소(프로세서 등)를 이용하여 한 번에 문제를 해결한다. 이것은 그 문제를 독립적인 부분들로 나눠서 각 처리 요소가 그 부분의 알고리즘들을 한 번에 다른 요소들과 처리를 할 수 있게 하는 것을 가능하게 했다. 그 처리요소들은 여러 자원들을 포함한다. 예를 들면 한 컴퓨터에 있는 멀티프로세서, 여러 네트워크 컴퓨터들, 특수 하드웨어, 아니면 그런 것들을 섞어 쓸 수도 있다.^[5]

컴퓨터의 클럭 속도는 1980년도 중반부터 2004년까지 컴퓨터 성능을 향상시키는 데 가장 영향력 있는 요소였다. 프로그램 실행시간은 명령어 수를 명령어 당 평균시간을 곱한 것과 같았는데 클럭수를 늘리면 명령을 실행하는 평균시간은 짧아진다.

그러나 칩의 전력소모량은P = C × V² × F의 공식에 따른다. P는 전력이고 C는 전기용량 V는 전압(voltage)이고 F는 주파수(프로세서 속도)를 의미한다.^[6] 주파수 수(프로세서 속도)를 높이면 전력 사용량이 늘어난다는 뜻이다. 전력 사용량이 계속 높아가자 결국 인텔은 2004년 5월에 테자스와 제이호크(Tejas and Jayhawk)를 취소시키기에 이른다. 그 사건은 주파수 척도에 의한 컴퓨터 구조 패러다임이 끝나는 것을 의미하게 된다.^[7]

무어의 법칙은 매 18에서 24개월 동안 집적도가 두 배씩 늘어난다는 것을 예측하는데,^[8] 전력소모량 사건에 계속됐던 예측은 끝이나고 말지만 무어의 법칙은 여전히 유효하다. 주파수 척도는 끝이 났지만 추가적인 트랜지스터들은 추가적인 병렬 컴퓨팅에 쓰이게 된다.

[편집] 암달의 법칙과 구스탑슨의 법칙

이 부분의 본문은 암달의 법칙입니다.

이 부분의 본문은 구스탑슨의 법칙입니다.

암달의 법칙을 그림으로 표현했다. 병렬화로 인한 프로그램의 속도 향상은 프로그램이 얼마나 병렬화 되어있느냐에 제한되어있다. 예를 들면 90%의 프로그램이 병렬화될 수 있다면 이론적으로 병렬 컴퓨팅을 사용한 속도 향상은 몇 개의 프로세서를 쓰던지 10배의 속도까지만 향상시킬 수 있다.

병렬화로 인한 속도 향상중 제일 좋은 것은 역시 선형적 결과다. 프로세서 수를 두 배로 늘리면 두 배 역할을 해서 실행시간을 절반으로 줄이고 프로세서 수를 또 두 배로 늘리면 또 실행시간이 절반으로 줄어든다. 그런데 아주 적은수의 병렬 알고리즘만이 최적의 속도 향상을 달성했다. 대부분은 그저 비슷한 선형적 속도 향상을 적은 수의 처리요소(프로세서)로 달성했을 뿐이다. 그것들은 처리 요소들의 숫자가 많아질수록 효과가 적어진다.

병렬 컴퓨팅 기반에서 잠재적인 속도 향상 알고리즘인 암달의 법칙은 1960년대에 진 암달에 의해서 만들어졌다.^[9] 병렬화할 수 없는 작은 부분의 프로그램은 전체적인 병렬화에 영향(제한)을 가져온다는 것이었다. 수학적이나 공학적 문제들은 전통적으로 몇 가지 병렬화된 부분과 병렬화되지 않은 부분으로 구성되게 된다. 이 관계는 아래와 같은 공식으로 나타나게 된다.

$S = \frac{1}{1 - P}$

여기서 S는 프로그램의 속도 향상을, P는 병렬화 가능한 분수를 의미한다. 만약 프로그램의 10%가 순차적 부분이라면 우리는 몇 개의 프로세서를 추가하든 간에 10배 이상 속도를 높일 수가 없다. 이것이 실용적으로 병렬실행 유닛들을 추가할 수 있는 한계이다. 순차적 부분의 제한으로 작업을 더 이상 나눌 수 없게 될 때 응용 프로그램들은 그 이상 빠른 결과를 만들 수 없게 된다. 인월미신의 예를 인용하자면 “임산부가 아무리 많아도 아이를 낳는 데에는 9개월이 걸린다.”

구스탑슨의 법칙은 컴퓨터 공학의 또 다른 법칙인데, 암달의 법칙과는 밀접한 관계가 있다. 이 공식은 다음과 같다:

$S(P) = P - \alpha(P-1) \,$

작업이A하고 B, 두 개의 독립적인 부분으로 되어있다고 가정하자, B는 전체 계산중에 대충 25%정도 시간을 차지한다. 프로그래머가 노력해서 이 부분을 5배 빠르게 만들었다. 그러나 이것은 전체 계산을 봤을 때에는 그냥 약간의 시간 감소에 불과하다. 반대로 A 부분을 2배로 만들면 B 부분을 빠르게 만드는 것보다 훨씬 더 효과가 있다 B를 5배 빠르게 만들었다고 해도 말이다.

P는 프로세서 수고 S는 속도 향상. α는 비 병렬 부분이다.^[10] 암달의 법칙은 문제가 고정된 크기라는 것과 순차적 부분을 독립적인 프로세서들이라고 가정한다. 구스탑슨의 법칙은 그런 가정을 하지 않는다.

[편집] 종속성

병렬 알고리즘은 자료 종속성을 이해하는 것이 기본이 된다. 어떤 프로그램도 가장 길게 연결되어 있는 종속적(비독립) 계산보다 빠르게 실행될 수 없다. (크리티컬 패스라고도 함) 이는 계산들이 이전 계산에 종속되어 있으면 계산은 그 차례를 지켜야 한다는 것을 뜻한다. 그러나 대부분 알고리즘들은 그런 긴 종속의 연결을 포함하지 않는다. 일반적인 병렬에서는 비종속적인(독립적인) 계산을 실행할 가능성이 많다.

P_i 와 P_j 두 프로그램 조각들이 있다고 하자. 번스타인 상태^[11]는 두 개의 독립적이고 병렬적으로 실행될 수 있을 때를 설명한다. I_i 는 P_i의 입력 변수고 Oi는 출력 변수라고 하고 P_j 도 같이 그렇다고 하자. 만약 다음을 만족시키면 P_i와 P_j는 독립적이다.

$I_j \cap O_i = \varnothing, \,$
$I_i \cap O_j = \varnothing, \,$
$O_i \cap O_j = \varnothing. \,$

첫번째 상태의 위반은 종속성 흐름(flow dependency) 을 야기한다. 첫번째 문(文)을 일치시키는 것은 두 번째 문이 작성한 결과를 만든다. 두 번째 상태는 대 종속성(anti-dependency) 상태를 의미한다. 첫번째 문이 두 번째 문에 의해 필요가 된 변수를 덮어쓸 때 세 번째와 마지막 상태는 출력의 독립을 의미하게 된다. 두 개의 문들이 같은 장소에서 작성할 때 마지막 결과는 논리적으로 반드시 마지막으로 실행됐던 명령이 되어야 한다. ^[12]

아래 함수는 몇가지 종속성을 보여준다.

1: function Dep(a, b)2:    c := a·b3:    d := 2·c4: end function

Dep 함수 세 번째 줄은 두 번째 줄이 실행되기 전에는 실행될 수 없다. 왜냐하면 세 번째 줄은 두 번째줄의 결과에 의해서 실행되야 하기 때문이다. 이것은 첫번째 상태를 위반한거다. 즉, 종속성 흐름을 야기시킨다.

1: function NoDep(a, b)2:      c := a·b3:      d := 2·b4:      e := a+b5: end function

이 예에서 명령어 간에 종속성은 없다, 따라서 이것들은 병렬로 처리할 수 있다.

번스타인의 상태는 다른 프로세스들 간에 메모리 공유를 허용하지 않는다. 그 때문에 서로 접근할 수 있게 만드는 방법이 필요할지도 모른다. 예를 들면 세마포어나 배리어나 아니면 다른 동기화 방법들 말이다.

[편집] 경쟁상태, 상호배제, 동조화, 병렬감속

병렬 프로그램에서 하위 작업들은 스레드라고 불리기도 한다. 몇몇 병렬 컴퓨터 구조는 작고 경량화된 버전의 스레드인 파이버를 이용하기도 한고 큰 버전으로는 프로세스 라고도 한다. 그러나 “스레드”는 일반적으로 하위 작업을 가리키는 단어로 해석된다. 스레드들은 자기들끼리 공유되는 몇몇 변수들을 갱신할 필요가 있다. 두 프로그램들 사이의 명령어들은 아마 끼워넣을 지도 모른다. 예를 들자면 아래 프로그램을 보자.

스레드 A	스레드 B
1A: 변수 V를 읽는다	1B: 변수 V를 읽는다
2A: 변수 V에 1 을 추가한다	2B: 변수 V에 1 을 추가한다
3A: 변수 V를 써넣는다	3B: 변수 V를 써넣는다

만약 명령어 1B가 1A과 3A 사이에서 실행되었다거나 1A가 1B나 3B 사이에서 실행되었다면 프로그램은 잘못된 정보를 만들게 된다. 이것을 바로 “경쟁 상태” 라고 한다. 프로그래머는 반드시 락을 사용해서 상호 배제를 해야 한다. 락은 한 개의 스레드가 락이 풀리기 전까지 변수를 제어하고 다른 스레드가 읽거나 쓰는 것을 막는 프로그래밍 언어 구조체다. 스레드는 락을 임계 구역 (몇몇 변수를 접근할 수 있게 허용해 주는 프로그램 구역) 내에서 자유롭게 실행할 수 있게 만든다. 그리고 다 끝나면 잠금을 해제한다. 따라서 올바른 프로그램 실행을 보장시켜준다. 위의 프로그램을 락을 사용해서 다시 작성하면 다음과 같다.

스레드 A	스레드 B
1A: 변수V 를 잠금	1B: 변수V 를 잠금
2A: 변수V 를 읽음	2B: 변수V 를 읽음
3A: 변수V 에 1 추가	3B: 변수V 에 1 추가
4A: 변수 V를 써넣는다	4B: 변수 V를 써넣는다
5A: 변수V 를 잠금해제	5B: 변수V 를 잠금해제

다른 스레드가 락 아웃( V가 다시 풀릴 때까지 진행하지 못하게 함)될 때 한 스레드는 변수V를 성공적으로 잠궜다. 이것은 프로그램이 정상적으로 실행되는 것을 보장한다. 잠금은 프로그램이 정상적으로 실행되는 것을 반드시 보장하지만 프로그램 속도를 느리게 할 수도 있다.

여러 개의 변수들을 비원자성 을 사용해서 잠그면 교착 상태에 빠질 수도 있다. 원자성 락은 한꺼번에 여러 개의 변수를 잠근다. 만약 전부다 잠글수 없다면 아무것도 잠그지 않는다. 만약 두 개의 스레드들이 서로 같은 두 변수들을 비원자성을 사용해서 잠가야 한다면 한 개의 스레드는 하나를 잠글지도 모르고 그러면 두 번째 스레드는 두 번째 변수를 잠가야 한다. 이 경우 두 스레드 다 잠그지 않을것이다. 그리고 교착 상태로 이어진다.

많은 병렬 프로그램들이 하위작업으로 동기화를 필수로 한다. 배리어 는 그 작업에 필요한데, 배리어는 원래 소프트웨어 락에 포함 (implement) 되어 사용된다. 한 클래스의 알고리즘들인 비차단 동기화 (lock-free와 wait-free 알고리즘)는 모두 락과 배리어의 사용을 피한다. 그러나 이 접근은 일반적으로 포함시키기 어렵고 정확한 디자인의 자료구조를 요구하게 된다.

모든 병렬화가 속도 향상을 시키진 않는다. 일반적으로 스레드들을 나누면 나눌수록 그 스레드들은 서로 의사소통 하는 데 시간을 더 증가시킨다. 결국 의사소통에 의한 문제를 해결하기 위해서 간접적인 시간소모를 해야하고 그 이상의 병렬화는(부하를 나누기 위해 스레드들을 나눌 때) 실행시간을 단축시키기는 커녕 늘리게 된다. 이것을 병렬 감속이라고 한다.

[편집] 잘게 나눔(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) 같은 수학적 모델들이 동시 행위 시스템의 행동을 설명하기 위해서 개발됐다.

[편집] 플린의 분류학

마이클 J. 플린은 가장 쉬운 컴퓨터와 프로그램 병렬(과 순차) 분류 시스템 중에 하나를 만들었다. 이것은 플린의 분류학(영어: Flynn's taxonomy)이라고도 알려져 있다. 플린은 프로그램들과 컴퓨터들을 그것이 단일, 아니면 복수의 명령어 셋을 사용하느냐 아니냐 그리고 그 명령으로 단일 아니면 복수의 데이터 들을 연산하는지 여부에 따라서 분류를 했다.

**플린의 분류학**
	단일 명령어	복수 명령어
단일 자료	SISD	MISD
복수 자료	SIMD	MIMD
v • d • e • h

SISD(단일명령-단일자료)는 완전히 순차적 프로그램과 같다. SIMD(단일명령-복수자료)는 반복되는 큰 자료에 대한 연산을 한다. SIMD는 일반적으로 신호처리 응용 프로그램들에서 실행된다. MISD(복수명령-단일자료)는 거의 쓰이지 않는 분류인데, 컴퓨터 구조들이 이것을 고민하고 있을 때(시스톨릭 배열같은 것들) 몇몇 응용 프로그램들이 이 분류를 구현시켜냈다. MIMD(복수명령-복수자료) 프로그램들은 제일 흔한 종류의 병렬 프로그램들이다.

데이비드 A. 패터슨과 존 L. 헤네시에 따르면 “몇 머신들은 이 카테고리를 여러 개 가질수도 있다, 당연히, 그런데 이 오래된 모델은 살아남는다. 왜냐하면 간단하고 이해하기 쉽기도 하고 처음 배울 때 좋다. 그리고 또 아마 어떤 조직을 넓게 이해하는 데 가장 많이 쓰였기 때문이다.”^[13]

[편집] 병렬처리의 종류

[편집] 비트수준 병렬처리

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

역사적으로 4비트 마이크로 프로세서들은 8비트, 16비트 그리고 32비트 마이크로 프로세서들에 의해서 교체됐다. 이 유행은 일반적으로 두 세대를 범용 컴퓨터 표준이 된32비트 프로세서의 등장과 함께 끝나는데, 최근 (2003-2004)엔 64비트 프로세서들을 가진x86-64 구조들이 등장하면서 표준이 된다.

[편집] 명령어 수준 병렬 처리

컴퓨터 프로그램은 명령어들의 흐름이 프로세서에 의해서 실행되는걸 바탕으로 한다. 이 명령어들은 재 순차와 결과의 변경 없이 한꺼번에 그룹단위로 병렬실행이 가능했다. 이것을 명령어 수준 병렬화라고도 한다. 이 명령어 수준 병렬화는 80년대 중반부터 90년대 중반까지 컴퓨터 구조를 주름잡았다.^[15]

현대의 프로세서들은 다단계 명령어 파이프라인을 가졌다. 파이프라인에서 각 단계는 다른 행동을 하는 같은 단계의 명령어를 실행하는 프로세서와 일치시킨다. N 스테이지 파이프라인은 N 개 만큼의 다른 명령어들을 다른 완료된 단계에서 가질수 있다. 파이프라인된 프로세서의 정석은 RISC 프로세서다. (다섯 개의 단계 – 명령어 패치, 디코드, 실행, 메모리 접근, 다시 써넣기 (write back) 가 정석이다.) 펜티엄 4 프로세서는 31단계의 파이프라인을 가지고 있다.^[16]

파이프라인을 할 때 명령어 수준 병렬화에서 몇 프로세서들은 한 개 이상의 명령어를 한 번에 만들수 있었다. 이것을 슈퍼스칼라 프로세서라고도 한다. 만약에 자료종속성만 없다면 명령어들은 한꺼번에 합쳐질수 있다. 스코어보딩 (Scoreboarding)과 토마줄로 알고리즘 (스코어보딩과 비슷하지만 레지스터 리네이밍 (Register renaming)을 사용한다) 이 두 가지가 가장 흔한 비 순차적 실행과 명령어 수준 병렬화 기술들이다.

[편집] 자료 병렬 처리

자료 병렬화는 프로그램 루프에 내재된 병렬화다. 프로그램 루프는 병렬로 처리된 다른 컴퓨팅 노드들의 자료를 분산시키는데 초점을 맞춘다. “루프를 병렬시키는 것은 가끔 비슷한 (완전 같을 필요는 없이) 순차 연산이나 큰 자료구조의 요소에서 실행되는 함수들을 실행시키게 한다.”^[17] 많은 과학적, 공학적인 응용물들이 자료 병렬화를 보여준다.

루프가 가지고 있는 종속성은 이전 반복의 하나 이상의 결과에 종속된다. 루프의 종속성은 병렬화 루프에 의해 막힌다. 예를 들면 아래의 피보나치 수 의사코드를 보자.

1:    PREV1 := 02:    PREV2 := 14:    do:5:       CUR := PREV1 + PREV26:       PREV1 := PREV27:       PREV2 := CUR8:    while (CUR < 10)

이 루프는 병렬화할 수 없다. 왜냐하면 CUR 이 각 루프를 도는 동안 그 자신(PREV2)과 PREV1에 종속되기 때문이다. 각 반복이 그 이전 결과에 종속되므로 병렬화할 수 없다. 문제의 크기가 크면 클수록 자료의 병렬화의 유효성은 일반적으로 커진다.^[18]

[편집] 작업 병렬처리

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

[편집] 같이 보기

[편집] 참조

↑ Almasi, G.S. and A. Gottlieb (1989). Highly Parallel Computing. Benjamin-Cummings publishers, Redwood City, CA.
↑ S.V. Adve et al. (November 2008). "Parallel Computing Research at Illinois: The UPCRC Agenda" (PDF). Parallel@Illinois, University of Illinois at Urbana-Champaign. "The main techniques for these performance benefits – increased clock frequency and smarter but increasingly complex architectures – are now hitting the so-called power wall. The computer industry has accepted that future performance increases must largely come from increasing the number of processors (or cores) on a die, rather than making a single core go faster."
↑ Asanovic, Krste et al. (December 18, 2006). pdf "The Landscape of Parallel Computing Research: A View from Berkeley" (PDF). University of California, Berkeley. Technical Report No. UCB/EECS-2006-183. "Old [conventional wisdom]: Increasing clock frequency is the primary method of improving processor performance. New [conventional wisdom]: Increasing parallelism is the primary method of improving processor performance ... Even representatives from Intel, a company generally associated with the 'higher clock-speed is better' position, warned that traditional approaches to maximizing performance through maximizing clock speed have been pushed to their limit."
↑ Patterson, David A. and John L. Hennessy (1998). Computer Organization and Design, Second Edition, Morgan Kaufmann Publishers, p. 715. ISBN 1558604286.
↑ ^가 ^나 Barney, Blaise. Introduction to Parallel Computing. Lawrence Livermore National Laboratory. 2007년 11월 9일에 확인.
↑ Rabaey, J. M. (1996). Digital Integrated Circuits. Prentice Hall, p. 235. ISBN 0131786091.
↑ Flynn, Laurie J. "Intel Halts Development of 2 New Microprocessors". The New York Times, May 8, 2004. Retrieved on April 22, 2008.
↑ Moore, Gordon E. (1965). Cramming more components onto integrated circuits (PDF). Electronics Magazine 4. 2006년 11월 11일에 확인.
↑ Amdahl, G. (April 1967) "The validity of the single processor approach to achieving large-scale computing capabilities". In Proceedings of AFIPS Spring Joint Computer Conference, Atlantic City, N.J., AFIPS Press, pp. 483–85.
↑ Reevaluating Amdahl's Law (1988). Communications of the ACM 31(5), pp. 532–33.
↑ Bernstein, A. J. (October 1966). "Program Analysis for Parallel Processing,' IEEE Trans. on Electronic Computers". EC-15, pp. 757–62.
↑ Roosta, Seyed H. (2000). "Parallel processing and parallel algorithms: theory and computation". Springer, p. 114. ISBN 0387987169.
↑ Patterson and Hennessy, p. 748.
↑ Culler, David E.; Jaswinder Pal Singh and Anoop Gupta (1999). Parallel Computer Architecture - A Hardware/Software Approach. Morgan Kaufmann Publishers, p. 15. ISBN 1558603433.
↑ Culler et al. p. 15.
↑ Patt, Yale (April 2004). "The Microprocessor Ten Years From Now: What Are The Challenges, How Do We Meet Them? (wmv). Distinguished Lecturer talk at Carnegie Mellon University. Retrieved on November 7, 2007.
↑ ^가 ^나 Culler et al. p. 124.
↑ ^가 ^나 Culler et al. p. 125.

[편집] 외부 링크

[보이기] v • d • e • h 컴퓨터 과학의 주요 분야
수학적 기초	수리논리학 ·집합론 ·정수론 ·그래프 이론 ·형 이론 ·범주론 ·수치 해석 ·이산수학
계산 이론	오토마타 이론 ·계산 가능성 이론 ·계산 복잡도 이론 ·양자 계산 이론
알고리즘 & 자료 구조	알고리즘 ·알고리즘 설계 ·알고리즘 해석 ·자료 구조 ·계산기하학
프로그래밍 언어 & 컴파일러	구문 분석 ·컴파일러 ·인터프리터 ·프로그래밍 언어 ·구조적 프로그래밍 ·객체 지향 프로그래밍
병렬 & 분산 시스템	병렬 컴퓨팅 ·컴퓨터 클러스터 ·분산 컴퓨팅 ·그리드 컴퓨팅 ·클라우드 컴퓨팅 ·IaaS ·PaaS ·SaaS
소프트웨어 공학	요구 분석 ·소프트웨어 설계 ·컴퓨터 프로그래밍 ·형식수법 ·소프트웨어 테스트 ·소프트웨어 개발
시스템 아키텍처	컴퓨터 아키텍처 ·마이크로아키텍처 ·운영 체제
통신 & 네트워크	컴퓨터 오디오 ·라우팅 ·네트워크 토폴로지 ·암호학 ·차세대 통신망
데이터베이스	데이터 마이닝 ·RDBMS ·SQL ·오라클 데이터베이스
인공 지능	자동추론 ·전산언어학 ·컴퓨터 비전 ·진화 연산 ·기계 학습 ·자연 언어 처리 ·로봇학
컴퓨터 그래픽	시각화 ·영상 처리
인간과 컴퓨터 상호 작용	컴퓨터 접근성 ·사용자 인터페이스 ·착용 컴퓨터 ·유비쿼터스 컴퓨팅 ·가상현실
계산과학	인공생명 ·생물정보학 ·인지과학 ·계산화학 ·계산론적 신경과학 ·계산물리학 ·수치 해석 ·Symbolic mathematics
정보보호	암호학 ·물리 보안 ·소프트웨어 보안 ·인터넷 보안 ·네트워크 보안 ·해킹 ·크래킹

[보이기] v • d • e • h 병렬 컴퓨팅
일반	클라우드 컴퓨팅 ·고성능 컴퓨팅 ·클러스터 컴퓨팅 ·분산 컴퓨팅 ·그리드 컴퓨팅
병렬화 수준	비트 ·명령어 ·데이터 ·테스크
스레드	슈퍼스레딩 ·하이퍼스레딩
이론	암달의 법칙 ·구스타프손의 법칙 · 비용 효과 · Karp–Flatt metric ·slowdown · speedup
구성 요소	프로세스 ·스레드 ·Fiber ·PRAM ·Instruction window
조정	다중 처리(대칭형 ·비대칭형) ·멀티스레딩 ·메모리 일관성 ·캐시 일관성 ·Barrier ·동기화 ·Application checkpointing
프로그래밍	모델(내재적 병렬성 ·외재적 병렬성 ·동시성) ·플린의 분류학(SISD · SIMD ·MISD ·MIMD)
하드웨어	메모리(NUMA ·COMA ·분산 ·공유 ·분산 공유) ·SMT ·SMP ·MPP ·슈퍼스칼라 ·벡터 프로세서 ·슈퍼컴퓨터 ·베어울프(Beowulf)
API	POSIX 스레드 ·OpenMP ·PVM ·MPI ·UPC ·인텔 스레딩 빌드 블록 ·Boost.Thread ·전역 배열 ·Charm++ ·Cilk ·Co-array Fortran ·OpenCL ·CUDA
문제	처치 곤란 병렬 문제 ·Grand Challenge ·Software lockout ·확장성 ·경쟁 상태 ·교착 상태 · 라이브락 ·결정론적 알고리즘 ·Parallel slowdown

'기본카테고리' 카테고리의 다른 글

결함허용컴퓨터/ FTS / 장애 허용 시스템 (0)	2011.12.18
CPU 스케줄링 (0)	2011.12.15
parallel processing ; 병렬처리 (0)	2011.12.13
병렬 처리의 법칙 (0)	2011.12.13
[CA] CISC VS RISC (0)	2011.12.12

2011. 12. 13. 21:28

parallel processing ; 병렬처리

기본카테고리 2011. 12. 13. 21:28

parallel processing ; 병렬처리

컴퓨터에서 병렬처리란 프로그램 명령어를 여러 프로세서에 분산시켜 동시에 수행함으로써 빠른 시간 내에 원하는 답을 구하는 작업을 일컫는다. 초기의 컴퓨터에서는 한번에 오직 하나의 프로그램만 수행되었다. 예를 들어 계산 수행에 1시간 걸리는 프로그램과, 테이프에서 데이터 읽기에 1시간 걸리는 프로그램이 있다면, 이 두 프로그램을 수행시키는데는 총 2시간이 소요되었다. 초기의 병렬처리는 이 두 프로그램이 섞여서(interleaved) 수행되도록 하는 방법이었다. 즉 한 프로그램이 입출력을 시작하여 끝나기를 기다리는 동안, 다른 계산 수행을 하는 프로그램이 실행될 수 있도록 하여 1시간 조금 더 걸리는 시간에 작업을 마치는 방법이었다.

다음 단계의 병렬처리는 멀티프로그래밍이었다. 멀티프로그래밍 시스템에서는 여러 사용자가 수행시킨 여러 프로그램이 있을 때 한 프로그램이 프로세서를 짧은 시간 동안 차지하여 작업을 수행시키고, 운영체계가 그 다음 프로그램이 수행되도록 하는 방식으로 작업을 하였다. 사용자에게는 모든 프로그램이 동시에 수행되는 것처럼 보인다. 이 시스템이 처음 봉착한 문제는 여러 프로그램이 한 자원을 집중적으로 사용할 때 효율적으로 해결해주지 못해서 나타나는 데드록 현상이었다.

벡터 프로세싱은 한 번에 한 개 이상의 일을 수행하려는 또 다른 시도였다. 이런 시스템에서는 한 개의 명령어로 두 어레이의 데이터를 더하거나 뺄 수 있는 기능이 추가되었다. 이런 기능은 벡터나 매트릭스 계산이 빈번히 나타나는 많은 엔지니어링 프로그램에서 매우 유용하게 이용되었다. 하지만 이런 계산을 많이 필요로 하지 않는 프로그램에서는 큰 효용이 없었다.

그 다음에 개발된 병렬처리의 기법은 멀티프로세싱이었다. 이 시스템에서는 두 개 이상의 프로세서가 한 프로그램을 같이 수행하여 작업을 마쳤다. 초기 단계에서는 주종(master/slave)관계의 구조였다. 한 프로세서(master)가 시스템의 모든 작업을 관장하도록 설계되었고, 다른 프로세서(slave)는 주 프로세서가 부여한 일만을 수행하였다. 이런 구조로 설계된 것은 그 당시에는 여러 프로세서가 협동하여 시스템 자원을 사용하는 것에 대한 기술이 부족했었기 때문이다.

이러한 문제를 해결하면서 나온 것이 SMP이다. SMP에서는 각 프로세서가 동등하게 시스템 작업의 흐름을 제어하는 기능이 있다. 원래의 목표는 SMP를 단일 프로세서가 멀티 프로그래밍을 하는 것처럼 보이게 하는 것이었다. 하지만 엔지니어들은 어떤 명령어의 순서를 바꾸어 실행시킴으로써 성능을 10~20% 향상시킬 수 있다는 것을 알아냈고, 프로그래머들은 좀더 복잡하게 프로그램을 하도록 주문 받게 되었다 (이러한 것은 두 개 이상의 프로그램이 같은 인자에 읽기나 쓰기를 동시에 실행할 때에만 나타난다. 따라서 복잡하게 프로그램해야 되는 경우는 소수의 특정한 프로그래머에게만 필요하다).

SMP시스템의 프로세서 수가 증가함에 따라 시스템의 한 편에서 다른 모든 부분으로 데이터를 전파시키는데 걸리는 시간도 증가했다. 프로세서의 수가 수십 개를 넘어가면 프로세서 수를 증가시킴으로 얻어지는 성능 향상이 너무 적어지게 된다. 전파 속도가 길어지는 문제를 해결하기 위하여 메시지 패싱 시스템이 고안되었다. 이런 시스템에서는 데이터를 공유한 프로그램이 특정 인자에 새로운 값이 할당되었다는 것을 알리기 위해 메시지를 전송한다. 그 인자의 새로운 값을 시스템의 모든 부분에 방송하는 대신에 그 값을 필요로 하는 프로그램에게만 전송한다.

공유 메모리를 사용하는 대신 프로그램간 메시지 전송을 위해 네트웍를 이용하는 방식도 등장했다. 이렇게 함으로써 한 시스템 내에 수백 개나 수천 개의 프로세서가 효율적으로 함께 작동할 수 있게 되었다(확장성이 좋다는 표현을 쓴다). 이러한 시스템을 MPP시스템이라 부른다.

MPP에서 효율적으로 수행되는 프로그램들은 방대한 데이터를 처리할 때 프로그램을 여러 독립적인 부분으로 나누어 실행시킬 수 있는 것들이다. 예를 들어 데이터마이닝 같은 경우 정적인 데이터베이스에 대하여 여러 가지 독립적인 검색을 수행한다. 또 체스 게임 같은 인공지능에서는 여러 가지 다른 수를 분석하여 볼 필요가 있다. 많은 경우 MPP시스템은 프로세서의 클러스터로 구성된다. 각 클러스터는 SMP처럼 작동하며, 메시지 패싱은 클러스터간에서만 일어난다. 인자를 어드레싱하는 것이 메시지를 통해서나 메모리 어드레스를 통해 가능하기 때문에 어떤 MPP시스템은 NUMA 시스템이라 부른다.

SMP는 비교적 프로그래밍이 간편하지만 MPP는 그렇지 않다. SMP시스템은 다뤄야 할 데이터 량이 너무 방대하지 않다면 거의 모든 종류의 프로그램에 잘 맞는다. 하지만 방대한 데이터를 다루는 데이터마이닝은 MPP만이 다룰 수 있다.

미국 위스칸신 대학에서 Doug Burger와 Mark Hill이 The WWW Computer Architecture Home Page를 만들었으니 참고하시기 바랍니다.
David A. Bader가 병렬 컴퓨팅 사이트들의 IEEE 목록을 제공합니다.

'기본카테고리' 카테고리의 다른 글

CPU 스케줄링 (0)	2011.12.15
병렬 컴퓨팅 (0)	2011.12.13
병렬 처리의 법칙 (0)	2011.12.13
[CA] CISC VS RISC (0)	2011.12.12
[CA] 무어/멧칼프/코우즈의 법칙 (0)	2011.12.11

2011. 12. 13. 21:16

병렬 처리의 법칙

기본카테고리 2011. 12. 13. 21:16

병렬 처리 관련 법칙들

[출처] http://bart7449.tistory.com/244

"모든컴퓨터 아키텍트들은 암달의 법칙을 알고 있다. 그럼에도 불구하고, 우리는 때때로 불가능한 성능 최적화를 위해 막대한 노력을 기울인다. 그리고, 전체 속도향상이 실망스러운 수준임을 확인했을 때에서야 비로소 암달의 법칙을 떠올린다."-In Computer Architecture: A Quantitative Edition, 4th ed. John L. Hennessy and David A. Patterson

"모두들 암달의 법칙을 알고 있지만, 금방 잊어버린다!" - Thomas Puzak

병렬 처리에 있어 중요한 비교척도로는 속도향상과 효율성이 존재한다.1개의 프로세서 또는 1개의 노드 추가로 이루어지는 어떠한 알고리즘의 속도향상(speedup)은 다음과 같이 계산된다.

$\120dpi \inline Speedup(n)= \frac{T_1}{T_n}$ (식 1)

여기에서, n는 프로세서의 수 또는 노드의 수,T₁은 직렬 알고리즘의 실행 시간, T_n 는 n 개의 프로세서 또는 노드를 이용한 병렬 알고리즘의 실행 시간을 의미한다. 속도 향상은 다시 크게 절대 속도향상(absolute speedup)과 상대 속도향상(relative speedup)으로 나뉘는데, 절대 속도 향상은 T₁ 이 가장 최적의 직렬 알고리즘(best sequential algorithm)의 실행 시간인 반면에, 상대 속도 향상에서는 T₁이 병렬 알고리즘을 한 프로세서에서 실행된 시간이다. 보통 속도향상을 얘기할 때는 상대 속도향상을 의미한다.

효율성(Efficiency)은 한 프로세서 또는 노드가 병렬 처리를 위해 얼마나 잘 활용되는지를 비교하는데 이용된다.

$\120dpi \inline Efficiency(n)=\frac{Speedup(n)}{n}= \frac{T_1}{n\cdot T_n }$ (식 2)

이 상적으로는 병렬 처리에서 속도 향상은 추가되는 n 개의 프로세서 또는 노드의 수에 따라 선형(linear)으로 증가한다. 즉, Speedup(n) = n이 된다. 이 경우 효율성은 1이 된다. 하지만 실제로는 I/O, 네트워크 대역폭(bandwidth), 지연시간(latency) 등 여러 이유로 1이 되지 못한다. 가장 대표적인 이유는 알고리즘의 모든 부분을 병렬화(parallelize) 시킬 수가 없기 때문인데, 이 알고리즘에 남아있는 직렬 처리 부분은 모든 알고리즘의 병렬화의 한계를 결정한다. 이는 암달의 법칙(Amdahl's law)으로 설명된다.

Amdahl's law¹

암달의 법칙은 1967년 한 컨퍼런스에서 IBM의 Gene Amdahl이 논한 것으로,이 공식은 어떤 시스템의 f 비율만큼의 부분이 S만큼 속도향상이 있을 때, 최대로 얻을 수 있는 이상적인 속도향상은 다음과 같이 제약됨을 설명한다.또한, 여기에서는, 프로그램 수행을 통해 풀고자 하는 문제의 크기가 특정 부분의 속도 향상의 전후에도 언제나 동일한 것으로 가정한다.

$\120dpi Speedup_{enhanced}(f,S)=\frac{1}{(1-f)+\frac{f}{s}}$ 식(3)

1) 만약 속도향상을 이룬 부분이 작다면 (f값이 작다면), 전체 시스템의 속도향상은 미미하다.

2) 만약 f 부분의 속도향상을 무한대(S →∞)로 할 수 있다면, 전체 시스템의 속도향상은 1/(1-f)로 수렴될 수 있다.

예를 들어 전체 시스템의 20%를 2배만큼 속도향상을 시킬 수 있다면, 이로 인해 얻을 수 있는 전체 시스템의 속도향상은:

$Speedup_{enhanced}(0.2, 2)=\frac{1}{(1-0.2)+\frac{0.2}{2}}= \frac{1}{0.8+0.1}= 1.11$ (식 4)

로 제한된다. 이 암달의 법칙은 어떠한 프로그램을 병렬화할 때 얻을 수 있는 최대한의 속도향상을 예측하는데 이용되기도 하는데, 이 때는 아래와 같은 형식으로 표현될 수 있다.

$\120dpi Speedup_{parallel}(f,n)=\frac{1}{(1-f)+\frac{f}{n}}$ (식5)

여기에서 f는 프로그램에서 병렬화된 부분을 n은 프로세서 또는 노드의 수를 의미한다.

먼저, 한 프로그램을 하나의 프로세서 또는 노드로 수행시켰을 때의 실행 시간을 1로 한다.

다 음으로 프로그램의 일정 부분 f를 n개의 프로세서나 노드로 병렬화하여 처리한다면, 이 f의 실행 시간은 f/n만큼의 시간이 들게 될 것이다. 반대로, 남은 부분 1-f는 한개의 프로세서 또는 노드로 수행하기 때문에 그대로 원래 만큼의 시간이 소요된다. 즉, 프로그램의 일정 부분 f를 n개의 프로세서나 노드를 이용하여 병렬화하는 경우 전체 수행 시간은 1-f+f/n만큼 소요되고, 이를 원래 시간 1과 비교하면 위의 식 5만큼의 성능 개선이 있다고 설명할 수 있다.

예 를 들어, 만약 f=1, n=16, 즉 프로그램의 모든 부분이 병렬화되어 있고, 16개의 프로세서를 이용해 병렬 처리한다면, 속도향상은 16배가 될 것이다. 그리고, 이 경우 효율성은 1(=16/16)이 된다. 하지만, 프로그램의 모든 부분을 병렬화 할 수는 없다. 이런 이유로 실제 프로세서나 노드 수를 늘린다고 해도, 어느 수준 이상에서는 속도향상을 기대할 수 없다. 아래 그림은 암달의 법칙에서 프로세서의 증가에 따른 속도 향상의 한계를 보인다.

Figure 1a.

그 래프를 보면 프로그램의 95%(f=0.95)가 병렬화 되어 있다고 해도, 16개의 프로세서를 가지고 10배 이상의 속도향상을 내지 못한다. 이후로는 아무리 많은 수의 프로세서를 가진다 해도 20배 이상의 속도향상을 낼 수가 없다. 즉, 병렬화 되지 않은 부분이 많을수록 속도향상은 더 적다. 50%의 병렬화를 통해 16 프로세서를 가지고 얻을 수 있는 속도향상은 2배 밖에 되지 못한다.실제로 프로그램 상에 남아있는 직렬 실행 부분의 비율은 아래 그래프와 같이 병렬화를 통해 얻을 수 있는 속도향상을 제약한다.

Figure 1b.

이 러한 이유로 병렬 처리에서 있어서는 프로그램의 직렬화 부분(1-f)를 얼마만큼 줄이느냐, 다른 말로 병렬화 부분(f)을 얼마나 늘이느냐 것이 관건이 되어 왔다. 또한, 실제로는 모든 부분을 병렬화할 수 없기 때문에, 프로세서 수를 계속 늘려도 병렬화의 이점을 추가로 가질 수가 없다. 이에 따라서 병렬 처리는 보통 소수의 프로세서를 가지고서 병렬 처리를 해 왔다. 프로그램의 병렬 부분과 속도향상과의 관계는 위 식에 의해 아래와 유도가 가능하다.

$\120dpi f=\frac{\frac{1}{speedup_{parallel}}-1}{\frac{1}{n}-1}$ (식 6)

Gustafson's law²

구스타프슨의 법칙은1988 년Sandia national Lab에 있던 John Gustafson이 고안한 것으로 규모가 충분히 큰 문제들은 효과적으로 병렬화가 가능함을 기술하고 있다. 이는 암달의 법칙이 병렬화를 통해 일정 수준 이상의 속도향상을 기대할 수 없다고 얘기하는 것에 배치되는데, 그렇다고 암달의 법칙이 틀렸다는것은 아니다. 암달의 법칙은 계속 유효하다. 이 법칙은 아래와 같이 표기된다.

$\120dpi Speedup(n)=n- \alpha\cdot (n-1)$ (식 7)

여기에서 n은 프로세서 또는 노드의 수,α는 프로그램에서 병렬화되지 않은 부분을 의미한다(,α= 1-f).

이 법칙에 따르면, 만약 n=16이고α=0.05이라면(95%가 병렬화 되어 있다면), 얻을 수 있는 속도향상은 15.25배(16-0.05*15) 이다. 이는 동일한 조건에서 속도향상은 10배를 넘지 못한다는 암달의 법칙과 상반된다. 이 이유는 무엇인가?

암달의 법칙이 병렬 처리에 있어 병렬화 전후의 문제 크기는 변하지 않는 것을 가정하는데 반해, 구스타프슨의 법칙은 고정된 처리 시간 개념을 도입하여 보다 큰 문제에 대한 속도향상을 설명한다.

즉, 암달의 법칙에서는 고정된 문제 크기를 갖는다고 가정하였는데, 이는프로세서 수의 증가에 상관없이 문제 크기는 증가하지 않는 것을 기초로 출발하였다. 아래의 그림을 보자.

그 림과 같이 직렬 시스템에서 프로그램을 실행하는데 걸린 시간은 프로그램의 직렬 부분 s와 병렬화 가능한 부분 p의 실행 시간으로 구성된다. 즉, s+p=1 이 병렬화 이전에 소요된 시간이다. 그리고 병렬화를 통해 얻어진 실행시간은 s+p/N이다. 여기에서 N은 프로세서의 수이다. 따라서 전체 속도향상은 식 1에 따라

1/(s+p/N)이 된다. s를 1-f라 하고 p를 f로 치환하면 위의 암달의 법칙(식 5)와 동일한 수식을 얻게 된다.

반대로, 구스타프슨의 법칙은 주어진 시간 내에 보다 많은 크기의 문제를 해결하는 경우 병렬화가 효과적인 방법이 됨을 설명한다. 아래 그림을 보자 .

여 기에서는 프로그램을 병렬화하였을 때의 실행 시간을 s+p=1로 하고, 이를 기준으로 프로그램의 직렬 시간과 비교한다. 즉 여기에서 속도향상은 식 1에 따라 s+Np가 된다.여기에서 s를α로, N을 n으로 치환하면, 식 7의 구스타프슨 법칙과 같게 된다. 즉 구스타프슨의 법칙은 주어진 시간에 병렬화로 임의 크기의 문제를 해결할 수 있을 때, 직렬 프로그램 실행 시간과의 비교를 통해 속도향상을 측정하는 반면에, 암달의 법칙은 직렬 실행 시간을 기준으로 병렬화를 수행하였을 때 얼마만큼의 속도향상이 있는지를 보인다는 점이 다르다. 병렬화 가능한 부분의 문제 크기가 클수록 구스타프슨 법칙에 따르면, 속도향상이 높게 나올 수 있다. 왜냐하면 문제 크기에 따라 더 많은 프로세서 할당을 통해 병렬 실행 시간 값(p)을 고정시킬 수 있기 때문이다. 예를 들어, 병렬가능한 문제 크기가 100이면, 100개의 프로세서로 할당하면 p=1이 된다. 1000이면, 1000개의 프로세서를 할당해서 p=1로 떨어지게 한다.반대로 암달의 법칙은 문제 크기와 상관없이 고정된 제한 속도향상 값을 갖는다.

자동차를 가지고 두 법칙을 비유하자면,

1) 자동차로 120Km 떨어진 도시로 이동한다고 하자. 그리고, 60Km/h의 속도로 한시간을 이미 이동하였다. 이제 나머지 절반의 거리를 아무리 빠르게 운전한다 하더라도, 출발지에서 목적지까지의 자동차의 평균 시속은 120Km/h를 넘을 수 없다. 이미 이동하는데 한시간을 써버렸고 아직 60Km의 이동 거리가 남아 있기 때문에 자동차가 남은 거리를 무한대의 시속으로 이동한다 하더라도, 이미 지나간 시간은 돌아오지 못하기 때문이다. (암달의 법칙)

2) 자동차로 120Km/h보다 낮은 속도로 이동하고 있었다고 하자. 남은 시간과 남은 이동거리가 충분하다면, 이전까지 얼마나 많이, 또 얼마나 천천히 운전했냐에 상관없이 자동차의 평균 시속은 120Km/h를 넘을 수 있다. 만약 60Km/h의 속도로 자동차를 한 시간 동안 운전했다면, 이 후 한 시간을 180Km/h 로 운전하거나 또는 150Km/h로 두 시간을 운전한다면, 총 이동 거리에 대한 평균 시속은 120Km/h에 도달하게 된다. (구스타프슨의 법칙)

Karp-Flatt metric³

카프-플랫 척도는1990년에 Alan H. Karp와 Horace P. Flatt에 의해병 렬 프로세서 시스템에서 코드의 병렬화를 측정하기 위해 고안되었다. 이 식은 측정된 속도향상 값을 가지고, 프로그램의 직렬화 부분의 비율을 찾아내는데 효과적이다. 암달이나 구스타프슨의 법칙은 실제 병렬 처리에 있어스케쥴링,프로세서간 통신 비용이나 프로세스간 동기화에 소비되는 비용, 프로세서간 불균형한 작업량 등을 고려하지 않는 이상적인 법칙이다. 반면에 이 척도는 실제 실험 결과를 대상으로 직렬화 부분의 비율을 계산할 수 있게 해준다.

$\120dpi e=\frac{\frac{T_n}{T_1}-\frac{1}{n}}{1-\frac{1}{n}}$ (식 7)

예를 들어, 1개의 프로세서를 가지고 프로그램을 실행하였을 떄 측정된 실행 시간이 5분(T1-5min)이 걸렸고, 10개의 프로세서(n=10)을 가지고 프로그램을 병렬화하였을 때 실행 시간이 1분이 걸렸다면(Tn=1min),

$\120dpi e=\frac{\frac{1}{5}-\frac{1}{10}}{1-\frac{1}{10}}=\frac{1/10}{9/10}=1/9$ (식 8)

으로 해당 코드의 직렬 실행 부분은 1/9(약 11.1%) 임을 식을 통해 유도할 수 있다.

Superlinear Speedup

암달의 법칙에 따르면, 병렬화를 통해 얻을 수 있는 속도향상은 선형 이상이 될 수가 없다. 하지만, 특정한 경우에 프로그램의 병렬화는 초선형(superlinear) 의 속도향상을 보이기도 한다. 즉, n개의 프로세서로 병렬화를 하였을 때 n배를 초과한 속도 향상이 나오기도 한다. 이렇다고 암달의 법칙이 틀렸다고 할 수는 없다. 다만 암달의 법칙이 초선형의 속도 향상을 보이기도 하는 이유를 설명하지 않는다 정도로 해석하는 것이 맞다. 초선형의 속도향상이 가끔씩 발생하는 이유 중 가장 큰 이유는 메모리 계층 상의 캐시 히트 때문이다. 즉 데이터 처리에 있어 이전에 이용되었던 데이터가 캐시에 남아 있어 메모리나 디스크 IO 없이 빠르게 처리된 경우에는 가끔씩 이런 경우가 목격된다.

또 다른 이유로는 데이터의 공간 복잡도에서 발생하기도 한다. 예를 들어 x개의 입력을 가지고 2^x의 처리 데이터를 작성하는 시스템이 있다고 하자. 이 데이터를 n개의 프로세서에 분할 할당한다고 하면, 각 프로세서는 2^x/n 크기의 데이터를 처리할 것이다. 하지만 입력 자체를 n개로 나누어 처리 데이터를 작성한다면, 각 프로세서에 할당되는 데이터의 크기는 2^x/n으로2^x/n 보다 훨씬 작게 된다. 병렬 처리 알고리즘의 복잡도가 선형이라면, 그만큼 병렬 실행 시간도 초선형으로 줄어들 수 있다.

Acknowledgement

그림 1a.는 Wikipedia의 암달의 법칙에서, 1b.~2b.는 참고문헌 [2]의 논문에서 발췌하였음. 식들은 모두 Online LaTeX Equation Editor를 이용해 작성되었음.

Written by bart7449

Amdahl, G.M. Validity of the single processor approach to achieving large scale computing capabilities, In AFIPS Conference Proceedings, Vol. 30 (Atlantic City, NJ Apr. 18-20). AFIPS Press, Reston, Va., 1967, pp. 483--385 [본문으로]
Gustafson, J.L, Reevaluating Amdahl's law, Communications of ACM , May 1988 Vol. 31, No. 5 pp.532--533 [본문으로]
Karp Alan H. and Flatt Horace P. Measuring Parallel Processor Performance, Communications of ACM, Vol 33, No. 5, May 1990 [본문으로]

'기본카테고리' 카테고리의 다른 글

병렬 컴퓨팅 (0)	2011.12.13
parallel processing ; 병렬처리 (0)	2011.12.13
[CA] CISC VS RISC (0)	2011.12.12
[CA] 무어/멧칼프/코우즈의 법칙 (0)	2011.12.11
정보처리기술사 학습관련 사이트 (0)	2011.06.04

2011. 12. 12. 23:01

[CA] CISC VS RISC

기본카테고리 2011. 12. 12. 23:01

CISC VS RISC

CISC(Complex Instruction Set Computer)

[출처] http://nearfri.egloos.com/1621691

-복잡하고 기능이 많은 명령어로 구성된 프로세서

-복합 명령을 가짐으로써 하위 호환성을 충분히 확보

-트랜지스터 집적에 있어서 효율성이 떨어짐(성능 향상에 난점)

-전력소모가 큼. 속도가 느리고 가격이 비쌈

-호환성이 절대적으로 필요한 PC 환경에 사용

-386, 486, Pentium 등 PC용 CPU

RISC(Reduced Instruction Set Computer)

-CPU의 명령어를 최소화하여 단순하게 제작된 프로세서

-대단히 효율적이고 특화된 CPU 구조. 다양한 기술 이용 가능

-하드웨어가 간단한 대신 소프트웨어는 복잡하고 크기가 커짐(컴파일러의 최적화가 요구됨)

-하위 호환을 위해 에뮬레이션 방식을 채택. 호환성 부족

-전력 소모가 적음. 속도가 빠르고 가격이 저렴

-용도에 최적화가 요구되는 환경에 사용

-IBM System/6000, 임베디드(MIPS, ARM계열 등), 매킨토시, 서버, 워크스테이션 등을 위한 특수목적 CPU

---------------------------------------------------------------------------

CISC

인텔의 8086은 16비트 프로세서로, 명령어의 길이가 1바이트에서 8바이트까지 가변적으로 구성되어 있다. 명령어가 가변적이고 복잡하므로 CISC 방식이라고 하는 것이다. 이 구조는 가능한 한 명령어의 길이를 줄여서 명령어의 디코딩(decoding, 해석) 속도를 높이고 최소의 메모리 구조를 갖도록 하기 위해서 정해진 것으로, 하나의 프로세서가 일련의 명령어를 순차적으로 처리하기에는 무척 유용한 방법이며, CPU의 동작 속도가 높아짐에 따라 성능이 비례로 증가한다. CISC 방식은 32비트 프로세서인 80386까지도 아무런 문제없이 적용된 기술이므로 완벽한 하위 호환성을 유지할 수 있었다.

그러나, 80486이 등장하면서 단순히 CPU의 클럭(Clock, 동작 속도)을 높이는 방식으로 성능 향상을 기대할 수 없으므로 CISC 방식의 문제점이 드러나기 시작했다. 클럭에는 한계가 있기 때문이다. 그래서, 한번에 여러 개의 명령어를 동시에 수행할 수 있는 기술이 필요하게 되었다. 즉, 동일한 클럭에서 두 개의 명령어를 한번에 처리하게 되면 두 배의 성능 향상을 기대할 수 있기 때문이다. 그러나, 슈퍼 스칼라(Super Scalar) 구조에서는 명령어의 길이가 가변적이기 때문에 순차적으로 해석해야 하고 조건/비조건 분기가 중간에 자주 등장하므로 여러개의 명령어를 처리하기에는 적합하지 못했다.

결국, 펜티엄부터 RISC86이라는 기법이 사용되었다. 이 방식은 AMD의 인텔 호환 CPU에서 사용된 기술로, 명령어의 해석 부분을 기존의 슈퍼 스칼라 방식으로 유지하면서 독립된 장치로 설계하여 연속적이고 고속으로 명령어를 RISC 방식으로 변환시키는 것이다. 그리고, 실제로 연산을 처리하는 장치는 RISC 방식으로 처리하여 여러 개의 명령어를 처리할 수 있도록 하는 방식이다. 그래서, 인텔 펜티엄 프로세서는 최대한 두 개의 명령어를 동시에 처리할 수 있는 것이다.

---------------------------------------------------------------------------

RISC

1970년대에 등장한 RISC 방식은 최신 프로세서의 핵심 기술로, CPU에서 수행하는 모든 동작의 대부분이 몇 개의 명령어만으로 가능하다는 사실을 전제로 하고 있다.

인텔과 경쟁하며 제품을 개발하던 모토롤라(Motorola)의 프로세서를 사용한 애플(Apple)의 매킨토시 컴퓨터에는 68 계열의 프로세서가 장착되어 있는데, 이 프로세서가 CISC 방식을 채택하고 있다. 모토롤러의 RISC계열로는 88계열이, 인텔에서는 x60계열이 있었다. 말 그대로 간단한 명령어만으로 구성되는 CPU이다. 그래서, 인텔 CPU 기반으로 개발된 프로그램은 매킨토시에서 사용할수 없었는데, 이것은 CPU 아키텍처가 다르기 때문이다.

RISC CPU는 고정된 길이의 명령어를 사용하고 명령어의 종류가 미리 정해져 있으므로 해석 속도가 빠르고 여러 개의 명령어를 처리하기에 적합하다는 장점이 있다. 특히, 분기 위치가 정해져 있고 비순차 처리도 가능하다. 그러나, 처리 비트 단위가 변하거나 CPU의 구조가 조금만 바뀌어도 하위 프로세서와의 호환성이 떨어지므로 문제가 발생한다. 이것은 하위 컴퓨터의 표준이 될만한 호환 명령어라는 개념이 없고 프로세서의 단계에 따라 최적의 명령어가 정해져 있기 때문이다.

이처럼 RISC 방식의 대표적인 CPU인 모토롤라 68 계열은 소프트웨어의 호환성 결여 때문에 인텔에 비해서 뛰어난 성능을 가지고 있음에도 불구하고 많은 사용자를 확보하지 못하고 있다. 단지 고성능의 대용량 데이터 처리가 필요하고 소프트웨어 활용이 비교적 고정되어 있는 워크스테이션을 중심으로 해서 많이 사용되고 있다.

RISC는 명령어가 전부 1워드(Word) 길이로 짧고 파이프라인(Pipeline)과 슈퍼 스칼라(Super Scalar)를 통해서 멀티 태스킹이 가능하므로 CISC에 비해서 많은 레지스터를 가지고 있다는 특징을 가진다.

---------------------------------------------------------------------------

RISC와 CISC는 CPU의 Architecture, 즉 구조적 측면의 차이로 어떤 일정한 방법으로 명령어를 처리하느냐에 따라 구분된다. 예전에는 RISC를 단순히 CISC를 간소화 시킨 정도로 보는 시각도 있었지만 현재에 와서는 그런 개념을 뛰어넘고 있다.

CISC는 복합 명령 집합 컴퓨팅으로 말 그대로 복합적인 명령어를 가지고 있다. 일단 컴퓨터에 어셈블리, 또는 베이직 따위의 언어로 명령을 주면, CPU에서 그것을 여러 단계로 세분화되어 마이크로 코드(Microcode)라 하는 수행 절차를 걸쳐 처리하게 된다. 그런데, 이런 수행에 있어 좀 더 복잡한 연산에 대응하는 명령어 셋을 추가하는 것이 CISC로, 여러 개의 단순한 명령어 셋으로 명령을 처리하기 보다는 그것들을 포괄하는 연산 셋으로 한 개의 명령어로 처리해 효율을 도모한다는 것이 CISC다. MMX도 이런 의미에서 볼 때는 CISC의 확장이라 볼 수 있겠다.

한편 RISC는 CISC와는 반대로 기본 명령어 셋을 추구하는 형태이다. 그러나 RISC라고 해서 단순히 명령어를 간소화 시킨 형태라고 봐서는 안된다. 단순히 명령어만 간소화 시킨다면, CISC보다 뛰어날 이유가 없기 때문이다. RISC에서는 컴퓨터에서 주 수행되는 작업을 색출해, 거기에 최적화 시켜 만든다. 핵심이 되는 작업 항목에 특화시켜 전체적인 속도를 향상시키는 것이다. 한가지 예를 들어 설명하자면, 모든 컴퓨터 작업에 있어서 읽고 쓰는 작업은 항상 포함된다. 일단 데이터를 읽어 들이고 쓰는 과정은 Loading과 Swap으로 이루어지기 때문이다. 그 과정에 최적화시키면 그 만큼 작업 속도,즉 전체적인 처리 효과를 얻게 되는 것이다. 그러기 위해선 다른 명령어 셋과는 달리 다른 공정이 필요하다.

CISC의 예로 CISC CPU의 대명사 Intel을 살펴보자. 현재 CISC는 RISC를 clock 속도로써는 충분히 능가할 수 있다. 다만 그 과정에서 트랜지스터 집적도가 너무 과다하게 올라가고 있다. 특히 Intel은 CISC에 MMX를 덧붙여 CISC에 CISC를 더한 셈이 되었다. 어차피 MMX의 세부를 열어보면 그것 역시 CISC의 확장이 되는 셈이기 때문이다. 특정 연산에 대한 명령어를 추가하는 것이 결국 CISC의 특성이 아니던가. Intel이 트랜지스터 집적도를 무리하게 올리면서 지금의 가격을 형성하고 인하 정책을 펼치는 것이 신기할 정도다. 아마도 현재의 PC CPU는 RISC로 갈 가능성은 희박할 듯 하다. 그 예로 Intel이 내세우는 차세대 CPU 머시드는 EPIC라고 하는 CISC를 또 다시 확장한 형태로 구현된다고 하니 말이다. 그 결과 머시드의 트랜지스터 집적수는 3억개라는 천문학적인 숫자에 이르고 말았다.

RISC의 예로 O2에 사용된 R10000 프로세서를 살펴보자. R10000 프로세서의 경우 clock은 그리 높지 않다. 175MHz의 동작 clock을 가진 제품도 있기 때문이다. 1MB의 L2 캐시를 가지고 있으며(R5000SC의 경우 5MB의 L2 캐시를 탑재), R10000 프로세서는 RISC프로세서의 정점을 보여주는 CPU로 RISC의 효율성을 최대한으로 발휘하고 있다. 4방향 슈퍼스칼라(4개 명령 동시 처리)에 64비트 구조를 가지고 있으며 비순차적 명령 실행 방법과 128비트 L2 캐시 버스에 별도 5개의 실행 유닛을 가지고 있다. PC식의 난폭한 마케팅으로 말하자면, R10000 프로세서는 128비트 프로세서란 말을 들을 수도 있다는 이야기가 된다.

요즘에 와서는 CISC도 RISC와 비슷한 공정을 채용해 단일 사이클에 처리하는 명령어를 많이 갖게되었다. 때문에 RISC와 CISC의 차이를 명확하게는 구분할 수 없게 되었고, 결국 캐시에 따른 차이가 두각을 드러냈다. 바로 CISC가 가진 맹목으로, 복합적인 명령어를 많이 가지려고 하다 보니, 트랜지스터 직접도가 과다하게 늘어나는 것이다. CISC가 가진 비효율이라 할 수 있겠다. RISC에서는 이와는 달리 명령어 체계 단순화를 지향하고, 핵심명령 특화 체제에 있어, 트랜지스터 집적에 여분이 있기 때문에 L1 캐시를 증대시켜 성능을 더욱 증대 시키는 것이다.

예를 들면, Pentium Pro의 경우 L1 캐시 16KB(명령어/데이터 캐시 합친 양)이고 L2 캐시를 제외한 펜티엄 프로의 트랜지스터 집적 수가 550만개인데 반해, RISC CPU인 Power PC 604e 프로세서의 경우 L1 캐시가 64KB인데도 트랜지스터는 510만개다. 특히, 604 프로세서의 세부적인 RISC의 특성을 살펴보자면 한 실행주기당 여러 명령을 동시에 처리하는 슈퍼스칼라(6~7개의 명령어를 처리)를 구현하고 있다. RISC가 CISC를 앞서는 구조적 특징이다.

'기본카테고리' 카테고리의 다른 글

parallel processing ; 병렬처리 (0)	2011.12.13
병렬 처리의 법칙 (0)	2011.12.13
[CA] 무어/멧칼프/코우즈의 법칙 (0)	2011.12.11
정보처리기술사 학습관련 사이트 (0)	2011.06.04
[전송통신] 차세대 서비스 오버레이와 기존 망과의 관계 (0)	2010.06.20

이전 1 2 3 4 5 6 ··· 15 다음

가을의 곰의 기술사 준비

검색결과 리스트

분류 전체보기 에 해당되는 글 57건