| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px); word-break: keep-all" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin:-5px -1px -11px" | <colbgcolor=#3CC>기반 학문 | 수학 (해석학 · 이산수학 · 수리논리학 · 선형대수학 · 미적분학 · 미분방정식 · 대수학 (환론 · 범주론) · 정수론) · 이론 컴퓨터 과학 · 암호학 · 전자공학 · 언어학 (형태론 · 통사론 · 의미론 · 화용론 · 음운론) · 인지과학 |
하드웨어 구성 | SoC · CPU · GPU(그래픽 카드 · GPGPU) · ROM · RAM · SSD · HDD · 참조: 틀:컴퓨터 부품 | |
| 기술 | 기계어 · 어셈블리어 · C(C++) · C# · Java · Python · BIOS · 절차적 프로그래밍 · 객체 지향 프로그래밍(디자인 패턴) · 해킹 · ROT13 · OTP · IoT · 와이파이 · GPS · 임베디드 · 인공신경망 · OpenGL · EXIF · 마이크로아키텍처 · ACPI · UEFI · NERF · gRPC · 리버스 엔지니어링 · HCI · UI · UX · 대역폭 · DBMS · NoSQL · 해시(SHA · 브루트 포스 · 레인보우 테이블 · salt · 암호화폐) · RSA 암호화 | |
| 연구 · 기타 | 논리 회로(보수기 · 가산기 · 논리 연산 · 불 대수 · 플립플롭) · 정보이론 · 임베디드 시스템 · 디자인 패턴 · 데이터베이스 · 프로그래밍 언어{컴파일러(어셈블러 · JIT) · 인터프리터 · 유형 이론 · 파싱} · 메타데이터 · 기계학습 · 빅데이터 · 폰노이만 구조 · 양자컴퓨터 · 행위자 모델 · 인코딩(유니코드 · MBCS) · 네트워크 · 컴퓨터 보안 · OCR · 슈퍼컴퓨터 · 튜링 머신 · FPGA · 딥러닝 · 컴퓨터 구조론 · 컴퓨터 비전 · 컴퓨터 그래픽스 · 인공지능 · 시간 복잡도(최적화) · 소프트웨어 개발 방법론 · 정보처리이론 · 재귀 이론 · 자연어 처리(기계 번역 · 음성인식) | }}}}}}}}} |
| '''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#aa3366> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 기계 · 람다 대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍) · 메타 프로그래밍 · 형식언어 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
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배 증가한다. 하지만 그 향상폭이 무한히 높아져도 전체 성능의 증가폭은 1.666..배를 넘지 못한다. 속도향상의 결과에는 0이라는 시간 하한선이 있지만 나머지 60% 부분의 소요시간은 독립적이기 때문이다. 이는 CPU나 GPU 중 하나가 다른 하나에 비해 과도하게 세대나 급이 차이가 날 때 체감할 수 있다. 이어달리기에 비유하면 '병목' 의 역할을 이해하기 쉽다. 두 사람이 구간을 나눠 달려야 한다는 규칙이 존재하는 한, 한명이 혼자 아무리 빠르게 달려도 결국 나머지 한 명과 교대하여 그의 시간기록과 합쳐야 한다고 생각해 보자.
다음과 같은 의미를 지닌다. 첫째로, 전체 작업의 효율을 최대한 증가시키고 싶다면 그 중에 가장 비중이 큰 작업부터 초점을 맞추는 것이 좋다. 둘째로, 일부 작업들이 더 이상 개선의 여지가 없을 경우 전체 작업이 최대 어느정도의 개선 효율을 보일 수 있는지에 대해 예측이 가능하다.
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의 활용도가 매우 높을 때 가능하다.
5. 관련 문서
[1] 무어의 법칙 같은 건 자연 법칙이 아니라 고든 무어의 경험에 의한 관찰에 불과하다.[2] 물론 각 부품이 컴퓨터의 성능에서 정확히 몇 퍼센트의 비중을 차지하는지 딱 떨어뜨려 계산할 수도 없고, 게임의 프레임은 단순히 컴퓨터의 연산력 뿐만 아니라 그 게임이 컴퓨터에서도 어떤 부품의 성능에 주로 의존하는지, 해당 부품에 대한 최적화가 어떤지 등 복합적인 요인이 작용하기 때문에 암달의 법칙으로 실제 프레임 증가폭을 정확히 예측하기는 어렵다. 그냥 연산력 증가폭과 프레임 향상폭의 괴리가 왜 생기는지를 설명하는 정도라고만 보면 된다.