카르프-플랫 미터법

이 문서에는 참고 자료, 관련 읽기 또는 외부 링크가 포함되어 있지만 인라인 인용이 부족하여 출처가 불분명합니다. 좀 더 정밀한 인용문을 도입하여 이 기사의 개선에 도움을 주시기 바랍니다. (2020년 3월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

Karp-Flatt 메트릭은 병렬 프로세서 시스템에서의 코드 병렬화의 척도입니다.이 메트릭은 Amdahl의 법칙과 Gustafson의 법칙 외에 특정 컴퓨터 코드가 병렬화되는 정도를 나타내는 지표로 존재합니다.그것은 Alan H. Karp와 Horace P에 의해 제안되었다.1990년에 플랫.

묘사

p$${\$displaystyle$$p$$}$ 프로세서에서$$ 속도 $향상$을 $나타내는{\displaystyle }$ 병렬 연산이 주어졌을 때,$p$ {\$displaystyle$p}$$> $1$에서 실험적으로 결정된 시리얼 $프랙션{\displaystyle }$e {\$displaystyle$ e$}$는 Karp-Flatt Metric viz로 정의됩니다.

${\displaystyle e=parcfrac {1}{\psi }}-{\frac {1}{p}}{1-{\frac {1}{p}}}}$

$\displaystyle$e$$값이 작을수록 병렬화가 우수합니다.

정당성

병렬 프로세서에서 실행되는 병렬 알고리즘의 성능을 측정하는 방법은 여러 가지가 있습니다.Karp-Flatt 메트릭은 다른 메트릭과 쉽게 구별되지 않는 성능의 측면을 나타내는 메트릭을 정의합니다.Amdahl의 법칙에는 다음과 같은 유사 "파생"이 있습니다.

${\displaystyle T(p)=T_{s}+{\frac {T_{p}}{p}}}$

장소:

• $)$ {$displaystyle$ T$(p)}$는$$p {$displaystyle$ p$}$ $프로세서시스템$에서의 코드 실행에 소요된 총 시간입니다.
• $(\$는 코드의 시리얼 부분이 실행되는 데 걸리는 시간입니다.
• ${\displaystyle {Tp}_{}}$\ $displaystyle T_{p}$는 코드의 병렬 부분이 1개의 프로세서에서 실행되는 데 걸리는 시간입니다.
• $\displaystyle$p는$$ 프로세서의 수

p$${\$style$p} =$$ 1 viz로 $치환$하여 얻은 결과입니다.$displaystyle$$T_{s}+T_{p$ 시리얼 $프랙션e{\displaystyle }${\$displaystyle$ e$}$ =$$ $T{\displaystyle \frac{{}_{}}{}}$ ${\displaystyle \frac{S_{}}{}}$ ( $){$ {$T(1)}}$을(를) 정의하면 방정식을 다음과 같이 다시 작성할 수 있습니다.

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

$속도$ $향상$과 관련하여 ${\$ ${\display$ \$psi{\displaystyle \frac{}{}}$$$} ${\displaystyle \frac{=<img\; alt="\backslash psi\; "\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/45e5789e5d9c8f7c79744f43ecaaf8ba42a8553a"\; style="vertical-align:\; -0.671ex;\; width:1.513ex;\; height:2.509ex;">}{}}$ ${\displaystyle \frac{T}{}}$ (${\displaystyle \frac{}{}}$ ) T${\displaystyle \frac{}{}}$( p$$) { $display$ {$frac${ T ( 1 ) $}$ { T$$( p ) }$$ :

${\displaystyle {1}{\psi }}=e+{\frac {1-e}{p}}}$

직렬 분율을 해결하면 위와 같은 Karp-Flatt 메트릭을 얻을 수 있습니다.왼쪽은 수학적으로 도출된 양이 아니라 메트릭을 나타내므로 이것은 Amdahl의 법칙에 따른 "유도"가 아닙니다.위의 처리는 카르프-플랫 측정이 Amdahl의 법칙과 일치함을 보여줄 뿐입니다.

사용하다

시리얼 프랙션e는 컴퓨터 사이언스 문헌에서 자주 언급되지만 속도 향상과 효율의 방법처럼 진단 도구로 사용되는 경우는 거의 없었습니다.Karp와 Flatt는 이 측정 기준을 제안함으로써 이것을 바로잡기를 원했다.이 메트릭은 컴퓨터 코드의 병렬화를 측정하는 데 사용되는 다른 법률 및 수량의 부족에 대처합니다.특히 Amdahl의 법칙에서는 로드밸런싱 문제도 고려되지 않고 오버헤드도 고려되지 않습니다.특히 프로세서의 수가 증가함에 따라 시리얼 프랙션을 메트릭으로 사용하면 다른 것보다 확실한 이점이 있습니다.

크기가 고정된 문제의 경우 병렬 계산의 효율은 일반적으로 프로세서의 수가 증가함에 따라 감소합니다.Karp-Flatt 메트릭을 사용하여 실험적으로 얻은 직렬 분율을 사용하여 효율성 감소가 병렬화의 제한된 기회 또는 알고리즘 또는 아키텍처 오버헤드의 증가 때문인지 판단할 수 있다.

레퍼런스

• Karp, Alan H. & Flatt, Horace P. (1990). "Measuring Parallel Processor Performance". Communications of the ACM. 33 (5): 539–543. doi:10.1145/78607.78614.
• Quinn, Michael J. (2004). Parallel Programming in C with MPI and OpenMP. Boston: McGraw-Hill. ISBN 0-07-058201-7.

외부 링크

• Karp-Flatt 메트릭 강의 노트 - 버지니아 공대