암달의 법칙

컴퓨터 아키텍처에서 Amdahl의 법칙(또는 Amdahl의 주장^[1])은 리소스가 개선된 시스템에서 기대할 수 있는 고정 워크로드에서의 작업 실행 지연 시간을 이론적으로 단축하는 공식입니다.구체적으로는 "시스템의 단일 부분을 최적화함으로써 얻을 수 있는 전체적인 성능 향상은 개선된 부품이 실제로 사용되는 시간의 비율에 의해 제한된다"^{[2][page needed]}고 명시되어 있습니다.컴퓨터 과학자 Gene Amdahl의 이름을 따서 1967년 AFIPS 스프링 조인트 컴퓨터 컨퍼런스에서 발표되었습니다.

Amdahl의 법칙은 병렬 컴퓨팅에서 여러 프로세서를 사용할 때 이론적으로 속도를 예측하기 위해 자주 사용됩니다.예를 들어, 하나의 스레드를 사용하여 프로그램을 완료하는 데 20시간이 필요하지만 프로그램의 1시간 부분은 병렬화할 수 없으므로 나머지 19시간(p = 0.95)의 실행 시간만 병렬화할 수 있으며, 이 프로그램의 병렬 실행에 할당되는 스레드 수에 관계없이 최소 실행 시간은 다음과 같습니다.1시간 미만이어서는 안 된다.따라서 이론적인 속도 향상은 단일 스레드 성능(1${\displaystyle {\displaystyle \frac{1\mathrm{}}{}}}$ - ${\displaystyle {\displaystyle \frac{p}{}}}$ $=$ ${\displaystyle 20}$)의 최대 20배$(\backslash {\displaystyle }$displaystyle $\leftfrac {1}{1-p$}}=$20\right$로 제한됩니다.

정의.

Amdahl의 법칙은 다음과 같은 방법으로 ^[3]공식화할 수 있습니다.

${\displaystyle S_{\text{latency}}=svsfrac {1}{(1-p)+{\frac {p}{s}}}$

어디에

• S는_latency 전체 작업 수행의 이론적 속도 향상이다.
• s는 시스템 자원의 개선으로 이익을 얻는 태스크 부분의 속도 향상이다.
• p는 리소스 개선을 통해 이익을 얻는 부품이 원래 점유한 실행 시간의 비율입니다.

더 나아가,

${\displaystyle\case\case}S_{\text{latency}}\leq {dfrac {1}{1-p}\[8pt]\lim \lim \s\to \infty }S_{\text{latency}}=sdfrac {1}{1-p}}.\end {case}}$

는 전체 작업의 이론적 실행 속도가 시스템 자원의 개선과 함께 증가하며, 개선의 규모에 관계없이 이론적인 속도 향상은 항상 개선의 혜택을 받을 수 없는 작업의 일부에 의해 제한된다는 것을 보여줍니다.

Amdahl의 법칙은 문제 크기가 수정된 경우에만 적용됩니다.실제로 더 많은 컴퓨팅 리소스를 사용할 수 있게 되면 더 큰 문제(더 큰 데이터 세트)에 사용되는 경향이 있으며 병렬 가능한 부분에 소요되는 시간이 기본적으로 직렬 작업보다 훨씬 더 빨리 증가하는 경우가 많습니다.이 경우, Gustafson의 법칙은 병렬 ^[4]성능에 대해 덜 비관적이고 더 현실적인 평가를 제공합니다.

파생

처음과 유사한 시스템에 비해 리소스가 개선된 시스템에 의해 실행되는 태스크는 두 부분으로 나눌 수 있습니다.

• 시스템 자원 개선의 혜택을 받지 못하는 부분
• 시스템 자원의 개선으로 이익을 얻는 부분.

예를 들어 파일을 처리하는 컴퓨터 프로그램이 있습니다. 이 프로그램의 일부는 디스크의 디렉토리를 스캔하여 메모리에 파일 목록을 만들 수 있습니다.그 후, 프로그램의 다른 부분은, 각 파일을 처리를 위해서 다른 스레드에 건네준다.디렉터리를 검사하고 파일 목록을 생성하는 부분은 병렬 시스템에서 속도를 높일 수 없지만 파일을 처리하는 부분은 속도를 높일 수 있습니다.

시스템 자원 개선 전 작업 수행 시간은 T$(\displaystyle$ T$)$로 나타내며, 자원 개선으로 혜택을 받지 못하는 부분의 실행 시간과 혜택을 받는 부분의 실행 시간을 포함한다.자원 개선으로 이익을 얻을 수 있는 태스크 실행 시간의 비율은$$p\$displaystyle$$p$로 표시됩니다.따라서 $이{\displaystyle \mathrm{}}$ 부품에서 혜택을 받지 못하는 부품은$(\displaystyle 1-p$입니다. 그 다음:

${\displaystyle T=(1-p)T+pT}$

자원 개선 후 요소 $s{\displaystyle }${\$displaystyle$ s$$$}$에 의해 가속화되는 자원 개선으로 이익을 얻는 부분의 실행이다.따라서 효익이 없는 부분의 실행시간은 그대로 유지되지만 효익이 있는 부분은 다음과 같이 된다.

$(\displaystyle\frac {p}{s}T).}$

자원 개선 후 전체 작업의 이론적 실행 $시간{\displaystyle }$ T${\displaystyle }$(${\displaystyle }$s$$) \ $displaystyle$T ($s$ )는 다음과$$ 같습니다.

${\displaystyle T(s)=(1-p)T+{\frac {p}{s}}T.}$

Amdahl의 법칙에 따라 고정 $워크로드$에서 작업 전체의 실행 지연 시간이 이론적으로 빨라집니다$.$W \ $display$ W$$\ $style$ W$$。이러한 값은 다음과 같습니다.

${\displaystyle S_{\text{latency}}}(s)=secfrac {TW}{T}W}}=flac {T}{T(s)}}=flac {1}{1-p+{\frac {p}{s}}}.}$

병렬 프로그램

실행 시간의 30%가 속도 업의 대상인 경우 p는 0.3이 되고, 개선으로 인해 영향을 받는 부품의 속도가 2배가 되면 s는 2가 됩니다.Amdahl의 법칙에 따르면 개선 적용의 전반적인 속도는 다음과 같습니다.

${\displaystyle S_{\text{latency}}=pc{1-p+{\frac {p}{s}}}=pc{1}{1-0.3+{\frac {0}}.3}{2}}}}=1.18.}$

예를 들어 연속된 4개의 부분으로 분할된 직렬 작업이 주어졌다고 가정합니다. 이 작업의 실행 시간의 백분율은 각각 p1 = 0.11, p2 = 0.18, p3 = 0.23, p4 = 0.48입니다.그러면 첫 번째 부분은 속도가 빨라지지 않으므로 s1 = 1인 반면 두 번째 부분은 5배 빨라지므로 s2 = 5, 세 번째 부분은 20배 빨라지므로 s3 = 20, 네 번째 부분은 1.6배 빨라지므로 s4 = 1.6이다.Amdahl의 법칙을 사용함으로써 전체적인 속도 향상은

${\displaystyle S_{\text{latency}=sfrac {1}{s1}+{\frac {p2}{s2}}+{\frac {p3}{s3}}+{\frac {p4}}}}=sfrac {1}{\frac {011}}{frac}}{{frac}}}{frac}{{frac}}}}{frac}}}}{frac}{frac}}}}}{frac}}}}{frac}}}}}}}{frac}}}}6}}}}=2.19.}$

4부(실행시간의 48%)를 1.6배만 가속해도 2부, 3부 각각 5배, 20배 가속은 전체 속도 상승에 큰 영향을 미치지 않는 점에 유의하십시오.

시리얼 프로그램

예를 들어, T = 3s 및_B T = 1s의_A 두 부분 A와 B의 직렬 프로그램을 사용할 경우,

• 부품 B가 5배 더 빨리 실행되도록 만든 경우, 즉 s = 5와 p = T_B/(T_A + T_B) = 0.25입니다.

$({displaystyle S_{\text{latency}}=param frac {1}{1-0.25+{\frac {0.25}{5}}}}=1.25;})$

• 부품 A가 2배 더 빨리 실행되도록 만든 경우, 즉 s = 2 및 p = T_A/(T_A + T_B) = 0.75입니다.

${\displaystyle S_{\text{latency}}=paramfrac {1}{1-0.75+{\frac {0.75}{2}}}=1.60.}$

따라서 부품 A를 2배 빠르게 실행하는 것이 부품 B를 5배 빠르게 실행하는 것보다 좋습니다.속도 향상률은 다음과 같이 계산할 수 있습니다.

${\displaystyle {\text{$

• 부품 A를 2배 개선하면 전체 프로그램 속도가 1.60배 증가하여 원래 계산보다 37.5% 빨라집니다.
• 그러나 부품 B를 5배 개선하면 더 많은 노력이 필요할 것으로 생각되므로 전체 속도 향상 계수는 1.25에 불과하므로 20% 더 빨라집니다.

병렬 프로그램의 순차적 부분 최적화

병렬 불가능한 부품이 O$(\displaystyle$ O$)$ 계수만큼 $최적화$되어 있는 경우,

${\displaystyle T(O,s)=(1-p){\frac {T}{O}}+{\frac {p}{s}}T.}$

Amdahl의 법칙에 따라 병렬로 인한 속도 상승은 다음과 같이 주어진다.

${\displaystyle S_{\text{latency}(O,s)=param frac {T(O,s)}}=param frac {(1-p)}+{p}{\frac {1-p}{\frac {1-p}}{\frac {1-p}}{\frac {\p}}}O}}+{\frac {p}{s}}}}.}$

s ${\displaystyle =}$ ${\displaystyle 1}${$displaystyle$ s$=$$1$이면 S ${\displaystyle {\text{지연}}_{}}$시간(${\displaystyle O}$,${\displaystyle s}$ ) ${\displaystyle =}$ {$displaystyle S_{\text{latency}}(O,s$)=1$\}$이 $됩니다{\displaystyle {}_{}}$. 즉, 비호환성 부품이 최적화되고 나서 실행 시간에 대해 속도 향상을 측정합니다.

s ${\displaystyle =}$ { $displaystyle$ s = \ $infty$ $\}$인 경우,

${\displaystyle S_{\text{latency}(O,\infty)=parcfrac {T(O,s)}}=parcfrac {(1-p)}+{p}{\frac {1-p}{\frac {1-p}}{\frac {1-p}}{\p}O}}+{\frac {p}{s}}}}=1+{\frac {p}{1-p}}O.}$

$1{\displaystyle }$${\displaystyle }$- ${\displaystyle p}$ ${\displaystyle =0}$.4$${$displaystyle 1-p=$${\displaystyle 0}$$.$4$},$ O$= 2 {displaystyle$ O=2} $및$ s ${\displaystyle =}$ {$displaystyle$ s$=5$인 경우:

${\displaystyle S_{\text{latency}(O,s)=param frac {T(O,s)}{T(O,s)}}=param frac {0.4}{\frac {1}{2}}+0.6}{\frac {0}4}{2}}+{\frac {0}.6}{5}}}}=2.5.}$

병렬 프로그램의 순차적인 부분을 병렬화할 수 있는 부분으로 변환

다음으로 병렬화 불가능한 부분을 O ${\$ { $displaystyle$ O$\}$$배$로 줄이고 병렬화 가능한 부분을 그에 따라 증가시키는 경우를 고려한다.그리고나서

${\displaystyle T'(O',s)=param frac {1-p}{O'}T+\left(1-{\frac {1-p}{O'}}\right){\frac {T}{s}}.}$

Amdahl의 법칙에 따라 병렬로 인한 속도 상승은 다음과 같이 주어진다.

${\displaystyle S'_{\text{latency}(O',s)=param frac {T'(O',s)}}}=param frac {1}{\frac {1-p}}+\left(1-{\frac {1-p}}{\frac {1-p}}}}}{\frac {\f}}}}}}{\f}}}}}}}{Displaysty frac {Displaysty}}}}}}}}}{Displaystyp}O'}}\right) {\frac {1}{s}}}}.}$

위의 도출은 실행 시간 대 속도 향상 트레이드오프에 ^[5]대한 Jakob Jenkov의 분석과 일치합니다.

수익 체감의 법칙과의 관계

Amdahl의 법칙은 종종 수익 체감의 법칙과 결합되지만 Amdahl의 법칙을 적용하는 특별한 경우만이 수익 체감의 법칙을 보여줍니다.개선해야 할 것을 최적으로(달성된 속도 향상 측면에서) 선택하면 개선될수록 단조롭게 감소하는 것을 볼 수 있다.그러나 차선의 성분을 개선하고 더 최적의 성분을 개선하기 위해 이동한 후 비최적적으로 선택하면 수익률이 증가할 수 있습니다.일부 개선은 다른 개선보다 어렵거나 개발 시간이 더 오래 걸리는 점을 고려할 때 이러한 의미에서 "최적이 아닌" 순서로 시스템을 개선하는 것이 합리적이라는 점에 유의하십시오.

Amdahl의 법칙은 사용 가능한 프로세서를 모두 사용하는 고정 크기 계산을 실행하는 머신에 프로세서를 추가함으로써 얻을 수 있는 수익의 종류를 고려하는 경우 수익 감소의 법칙을 나타냅니다.시스템에 새로운 프로세서를 추가할 때마다 이전 프로세서보다 사용 가능한 전력이 줄어듭니다.프로세서의 수를 2배로 늘릴 때마다 총 throughput이 제한치 1/(1 - p)에 가까워지기 때문에 속도 향상 비율은 감소합니다.

이 분석에서는 메모리 대역폭 및 I/O 대역폭과 같은 기타 잠재적인 병목 현상을 무시합니다.이러한 리소스가 프로세서 수에 따라 확장되지 않는 경우 프로세서를 추가하는 것만으로 수익률이 더 낮아집니다.

Amdahl의 법칙이 시사하는 바는 시리얼 부분과 병렬 부분을 모두 갖춘 실제 애플리케이션을 고속화하기 위해서는 ^[6]이종 컴퓨팅 기술이 필요하다는 것입니다.일반적인 형태의 이질성이라고 불리는 이질성의 보다 일반적인 표현에 기초한 새로운 속도 향상 및 에너지 소비 모델이 있으며, 이 모델은 광범위한 이질적인 다핵심 아키텍처를 지원합니다.이러한 모델링 방법은 시스템 전력 효율과 성능 범위를 예측하는 것을 목표로 하며 하드웨어 및 시스템 소프트웨어 ^[7][8]수준에서 연구개발을 촉진합니다.

「 」를 참조해 주세요.

• 구스타프슨의 법칙
• 병렬 알고리즘 분석
• 크리티컬 패스 방식
• 무어의 법칙

레퍼런스

추가 정보

• Amdahl, Gene M. (1967). "Validity of the Single Processor Approach to Achieving Large-Scale Computing Capabilities" (PDF). AFIPS Conference Proceedings (30): 483–485. doi:10.1145/1465482.1465560.

외부 링크

• "Parallel Programming: When Amdahl's law is inapplicable?". 2011-06-25. Archived from the original on 2013-04-14. Retrieved 2011-06-26.
• Amdahl은 위스콘신 대학에서의 그의 대학원 연구와 WISC 설계에 대해 논의합니다Gene M. Amdahl (1989), Oral history interview with Gene M. Amdahl, Charles Babbage Institute, University of Minnesota, hdl:11299/104341.STARTH, IBM 701 및 IBM 704를 포함한 IBM용 여러 컴퓨터 설계에서 그의 역할에 대해 설명합니다.Nathaniel Rochester와 함께 작업한 내용과 설계 프로세스에 대한 IBM의 관리에 대해 논의합니다.Ramo-Woldridge, Aeronutronic 및 Computer Sciences Corporation과의 협력에 대해 언급합니다.
• Amdahl의 법칙: 모든 성능 향상이 동일한 것은 아니다(2007년)
• 조엘 F의 '암달의 법칙'Klein, Wolfram 데모 프로젝트 (2007)
• 멀티코어 시대의 Amdahl의 법칙 (2008년 7월)
• 어쨌든 병렬주의란 무엇인가? (Charles Leiserson, 2008년 5월)
• James Charles, Preet Jassi, Ananth Narayan S, Abbas Sadat 및 Alexandra Fedorova(2009)에 의한 인텔 Core i7 터보 부스트 기능 평가
• 스레드 수의 함수로서의 병렬 프로그램 가속 계산(George Popov, Valeri Mladenov 및 Nikos Mastorakis 2010년 1월)
• Danny Hillis - Amdahl의 법칙이 틀렸음을 증명하는 비디오, 2016년 10월 녹화