암달의 법칙
덤프버전 :
1. 개요[편집]
Amdahl's law
암달의 법칙(Amdahl's law)은 암달의 저주로도 불리며 컴퓨터 시스템의 일부를 개선할 때 전체적으로 얼마만큼의 최대 성능 향상이 있는지 계산하는 데 사용된다. 진 암달의 이름에서 따왔다. 론(theory)만 많은 컴퓨터과학 분야에서 몇 안 되는 법칙(Law)이다.[1]
2. 설명[편집]
어떤 작업의 시간 효율을 개선할 때, 전체 작업시간에 대해 P만큼의 작업시간을 차지하는 작업의 효율을 S만큼 향상시켰다 가정하자. 그렇다면 전체 작업 효율은 다음과 같이 향상된다.
[math( \displaystyle \frac{1}{(1-P)+\frac{P}{S}} )]
가령, 전체 작업 시간 중에서 10%를 차지하는 작업의 속도를 2배 증가시켰다면, 전체 작업 속도는 약 1.05배로 증가한다.
[math( \displaystyle \frac{1}{(1-0.1)+\frac{0.1}{2}} = \frac{1}{0.95} \fallingdotseq 1.0526 )]
병목현상을 설명하는 이론이기도 하다. 가령 전체의 40% 부분의 성능이 2배로 향상되었을 때, 전체 성능은 1.25배 증가한다. 그런데 40% 부분의 성능이 무한히 증가한다 하더라도, 전체 성능의 증가폭은 1.66..배를 넘지 못한다. 40% 부분이 아무리 빨리 일을 처리한다 해도, 원래 성능을 유지하는 나머지 60% 부분이 발목을 잡아서 전체 작업 속도의 증가폭의 한계가 뚜렷한 것. 만일 90% 부분이 무한히 빨라진다 하더라도 남은 10% 부분이 발목을 잡아서 전체 성능 증가폭은 10배를 넘지 못하게 된다. 이는 CPU나 GPU 중 하나가 다른 하나에 비해 과도하게 세대나 급이 차이가 날 때 체감할 수 있다.
다음과 같은 의미를 지닌다. 첫째로, 전체 작업의 효율을 최대한 증가시키고 싶다면 그 중에 가장 비중이 큰 작업부터 초점을 맞추는 것이 좋다. 둘째로, 일부 작업들이 더 이상 개선의 여지가 없을 경우 전체 작업이 최대 어느정도의 개선 효율을 보일 수 있는지에 대해 예측이 가능하다. 가령 전체 작업의 80%가 더 이상 개선의 여지가 없을 경우 나머지 작업을 아무리 개선하더라도 전체 작업 속도는 1.25배 이상이 될 수 없다.
2010년도의 개인 사용자가 가장 쉽게 이 법칙을 느낄 수 있는 것은 바로 컴퓨터의 업그레이드이며, 그 중에서도 SSD가 가장 체감이 크다. 보조 기억 장치의 처리 시간은 네트워크를 제외한 다른 자원에 비해서 자릿수가 다른 수준으로 느리다. 그렇기 때문에 일정 수준 이상의 시스템에선 사용자 응답 시간의 대부분을 저장 장치 속도가 결정하는데, 이를 HDD에서 SSD로 바꿔주는 것으로 CPU나 메모리 업그레이드와는 차원이 다른 성능 향상을 체감할 수 있다. 또한 업그레이드한 부품이 이전 부품보다 벤치마크 점수나 단순 초당 연산력은 몇 배 수준으로 증가했더라도 실제 게임을 돌렸을 때 프레임 증가폭은 그보다 한참 떨어지는데, 그 이유를 설명해주는 법칙이기도 하다.[2]
병렬 컴퓨팅을 할 경우, 일부 병렬화 가능한 작업들은 사실상 계산에 참여하는 컴퓨터의 개수에 비례해서 속도가 늘어난다. 이러한 경우 암달의 법칙에 의해서 전체 수행시간의 개선 효과는 병렬화가 불가능한 작업들의 비중에 크게 영향을 받게 된다. 즉, 아무리 컴퓨터의 개수가 늘어나더라도 위의 그림에서 보는 것처럼 속도의 한계는 정해져있다는 것.
위에서 서술했듯이, 이 법칙에 의해서 수행 속도 증가폭의 한계가 정해져버리기 때문에, 이 법칙을 암달의 저주라고 부르기도 한다. 엄밀히 말해 암달은 현실에서 생기는 현상을 "내가 분석해보니 수식으로 표현하면 이렇다"고 이론으로 정립했을 뿐이지 암달이 컴퓨터 공학에 제약을 건 것은 아니기 때문에 저주라는 별칭은 억울하겠지만 (…)
3. 구스타프슨의 법칙[편집]
Gustafson's law
암달의 법칙과는 다르다. 암달의 법칙이 실행 시간의 감소에 초점을 두었다면 구스타프슨의 법칙은 동일한 시간 동안의 작업분량에 초점을 두었다.
즉, 암달의 법칙은 latency에, 구스타프슨의 법칙은 throughput에 기준을 두었다고 보면 된다.
아래와 같은 수식으로 표현된다.
[math( \displaystyle S(P)=P - a(P - 1) )]
여기에서 [math(P)]는 프로세서의 개수, [math(a)]는 병렬화되지 않는 부분의 비율, [math(S(P))]는 이론상 성능 향상 비율이다. 여기에서의 성능 향상은 같은 시간 동안 처리하는 데이터량의 비율이다.
가령 병렬화되지 않는 부분이 전체 프로세스의 50%이고 CPU를 128개 투입한다면 성능 향상은 [math(128 - 0.5 * (128 - 1) = 64.5)]이다. 즉 같은 시간 동안 128개의 CPU를 활용해서 64.5배의 데이터를 처리할 수 있게 된다.
4. 초선형적 성능향상 (Superlinear speedup)[편집]
암달의 법칙은 이론적이고 자명한 법칙인 만큼, 현실에 적용될 때에는 실제 연산장치가 이론적으로 완벽하지 않음에 의한 예외가 발생하기도 한다. 이 중에서 유명한 것 중 하나가 N개로 병렬 연산을 했을 때 N배를 뛰어넘는 성능 향상을 얻게 되는 초선형적 성능 향상이다.
기본적으로 이 현상은 이상적인 순차 계산 성능 에 비해 병렬처리로 N배 이상의 성능을 얻는 것이 아닌, 현실적으로 획득할 수 있었던 순차 계산 성능 에 비해 병렬처리를 도입할 때 병렬화 갯수 이상의 효과를 얻는 것을 의미한다. 따라서, 이러한 현상은 매우 제한적으로 발생하며 원한다고 얻을 수 있는 것도 아니다.
초선형적 성능 향상의 흔한 원인은 다음과 같다.
- 기존의 순차 알고리즘이 좋지 않거나, 데이터가 비효율적으로 배치되어 있거나, 알고리즘상 순차적으로 실행할 때 더 불리한 랜덤 워크(random walk)와 같은 프로세스를 포함하고 있는 경우.
이 경우 암달의 법칙에서 말하는 병렬화/순차화만으로 분리할 수 있는 것이 아니라, 순차 알고리즘일 때 종속된 부가적인 단계와 병렬 알고리즘일 때 종속된 부가적인 단계가 서로 다르게 된다.
- (사실상 초선형적 스피드업의 주된 케이스인) 캐시 메모리 효과.
실제 컴퓨터는 이론적인 연산장치와는 다르게, 저장장치에서 자료를 불러오는 과정에서 드는 시간이 경우에 따라 다르며 그 시간의 편차가 매우 크다. 현대의 모든 CPU는 여기에서의 시간 손실을 줄이기 위해 저장장치(메모리)에서 CPU로 자료를 옮길 때 좀 더 빠른 메모리에 앞으로 사용될 것으로 예상되는 메모리까지 미리 불러와 두는데, 이것이 캐시 메모리다. 이 때문에 CPU에 작업을 시킬 때, 띄엄띄엄 떨어진 메모리 위치에 있는 자료를 불러와서 계산을 하는 것과 가까운 곳에 옹기종기 모여있는 자료를 불러와서 계산을 하는 것은, 계산하는 양이 동일해도 어마어마한 속도 차이가 난다.
암달의 법칙에 대입해 보면, 순차 처리/병렬 처리 부분에서 차이가 없더라도 메모리에서 캐시 메모리로, 캐시 메모리에서 CPU로 데이터를 옮기는 등의 '연산 전후 과정'이 다르게 되는 것.
만일 캐시 메모리 알고리즘에 익숙하지 않더라도 일반적인 CPU를 떠올려 쉽게 이해할 수 있는 또 다른 예시를 들어 보자. 현대의 멀티 코어 CPU 내부에 있는 캐시 메모리는 보통 1개~몇 개씩의 코어마다 묶여있는 것이 보통이다. 예를 들어 16코어짜리 'A' CPU가 있다고 할 때, CPU 내부에는 8코어짜리 모듈 두개가 각각 32MB의 L3 캐시 메모리를 가지고, 각각의 모듈 내부에는 2코어짜리 페어 4개가 8MB의 L2 캐시 메모리를 추가로 가지고, 짝을 이루는 각각의 코어는 2MB의 L1 캐시 메모리를 전용으로 가지고 있는 구조일 수 있다.
만일 이 CPU에게 단일 코어로 순차 작업을 시킨다고 하면, 일을 하는 1개의 코어는 2MB의 L1 & 8MB의 L2 & 32MB의 L3 캐시 메모리 메모리를 활용하며 자료를 읽어들이고 연산 작업을 할 것이다.
반면 이 CPU에게 16코어로 분배된 병렬 작업을 시킨다고 하면, 일을 하는 코어들이 사용하는 캐시 메모리의 총 활용도는 32MB의 L1 & 64MB의 L2 & 64MB의 L3 캐시 메모리 메모리로 껑충 뛰어오르게 된다. 이론적으로 이상적인 경우라면 모든 코어에서 CPU에 있는 모든 L1, L2, L3의 용량 전체를 동일한 속도와 동일한 레이턴시로 읽어야만 하지만, 현실적으로는 그런 설계가 불가능하기 때문에 병렬처리를 할 때 제공되는 자원이 순차처리를 할 때 제공되는 자원보다 더 강력한 경우가 특정 시나리오에서는 불가피한 것이다.
물론 조금 지식이 있는 사람이면 눈치챌 수 있겠지만, 캐시 메모리 용량이 더 크다고 무조건 효율적이기만 한 것은 아니다. 예를 들어 L2 캐시 메모리의 경우, 1개 코어가 8MB를 혼자서 마음껏 사용하는 것과 16개 코어가 총합 64MB를 나누어 쓰는 것은 다르다. 따라서 위의 시나리오에서 '16개 코어 병렬처리량' > '1개 코어 순차처리량 x 16' 이 되기 위해서는, 해당 처리 알고리즘이 코어끼리의 충돌을 매우 적게 일으키고, 나눠쓰는 L3보단 둘이 쓰는 L2의 활용도가, 둘이 쓰는 L2의 활용도보다 혼자 쓰는 L1의 활용도가 매우 높을 때 가능하다.
암달의 법칙에 대입해 보면, 순차 처리/병렬 처리 부분에서 차이가 없더라도 메모리에서 캐시 메모리로, 캐시 메모리에서 CPU로 데이터를 옮기는 등의 '연산 전후 과정'이 다르게 되는 것.
만일 캐시 메모리 알고리즘에 익숙하지 않더라도 일반적인 CPU를 떠올려 쉽게 이해할 수 있는 또 다른 예시를 들어 보자. 현대의 멀티 코어 CPU 내부에 있는 캐시 메모리는 보통 1개~몇 개씩의 코어마다 묶여있는 것이 보통이다. 예를 들어 16코어짜리 'A' CPU가 있다고 할 때, CPU 내부에는 8코어짜리 모듈 두개가 각각 32MB의 L3 캐시 메모리를 가지고, 각각의 모듈 내부에는 2코어짜리 페어 4개가 8MB의 L2 캐시 메모리를 추가로 가지고, 짝을 이루는 각각의 코어는 2MB의 L1 캐시 메모리를 전용으로 가지고 있는 구조일 수 있다.
만일 이 CPU에게 단일 코어로 순차 작업을 시킨다고 하면, 일을 하는 1개의 코어는 2MB의 L1 & 8MB의 L2 & 32MB의 L3 캐시 메모리 메모리를 활용하며 자료를 읽어들이고 연산 작업을 할 것이다.
반면 이 CPU에게 16코어로 분배된 병렬 작업을 시킨다고 하면, 일을 하는 코어들이 사용하는 캐시 메모리의 총 활용도는 32MB의 L1 & 64MB의 L2 & 64MB의 L3 캐시 메모리 메모리로 껑충 뛰어오르게 된다. 이론적으로 이상적인 경우라면 모든 코어에서 CPU에 있는 모든 L1, L2, L3의 용량 전체를 동일한 속도와 동일한 레이턴시로 읽어야만 하지만, 현실적으로는 그런 설계가 불가능하기 때문에 병렬처리를 할 때 제공되는 자원이 순차처리를 할 때 제공되는 자원보다 더 강력한 경우가 특정 시나리오에서는 불가피한 것이다.
물론 조금 지식이 있는 사람이면 눈치챌 수 있겠지만, 캐시 메모리 용량이 더 크다고 무조건 효율적이기만 한 것은 아니다. 예를 들어 L2 캐시 메모리의 경우, 1개 코어가 8MB를 혼자서 마음껏 사용하는 것과 16개 코어가 총합 64MB를 나누어 쓰는 것은 다르다. 따라서 위의 시나리오에서 '16개 코어 병렬처리량' > '1개 코어 순차처리량 x 16' 이 되기 위해서는, 해당 처리 알고리즘이 코어끼리의 충돌을 매우 적게 일으키고, 나눠쓰는 L3보단 둘이 쓰는 L2의 활용도가, 둘이 쓰는 L2의 활용도보다 혼자 쓰는 L1의 활용도가 매우 높을 때 가능하다.
5. 관련 문서[편집]
이 문서의 내용 중 전체 또는 일부는 2023-12-08 04:01:20에 나무위키 암달의 법칙 문서에서 가져왔습니다.[1] 무어의 법칙 같은 건 자연 법칙이 아니라 고든 무어의 경험에 의한 관찰에 불과하다.[2] 물론 각 부품이 컴퓨터의 성능에서 정확히 몇 퍼센트의 비중을 차지하는지 딱 떨어뜨려 계산할 수도 없고, 게임의 프레임은 단순히 컴퓨터의 연산력 뿐만 아니라 그 게임이 컴퓨터에서도 어떤 부품의 성능에 주로 의존하는지, 해당 부품에 대한 최적화가 어떤지 등 복합적인 요인이 작용하기 때문에 암달의 법칙으로 실제 프레임 증가폭을 정확히 예측하기는 어렵다. 그냥 연산력 증가폭과 프레임 향상폭의 괴리가 왜 생기는지를 설명하는 정도라고만 보면 된다.