상상해 보세요. 맛있는 잔치를 준비하기 위해 서두르고 있지만 주방의 크기와 갑판에 있는 인원 수에 제약을 받고 있습니다. 병렬 컴퓨팅의 세계에서 Amdahl의 법칙과 Gustafson의 법칙은 요리의 걸작을 최적화하는 데 필요한 신뢰할 수 있는 요리법입니다. 이는 수십 년 동안 컴퓨터의 성능을 향상시켜 우리가 점점 더 빠른 처리 속도를 즐길 수 있게 해주는 비밀 재료와 같습니다. 이 두 가지 원칙은 병렬 컴퓨팅의 음과 양일 수 있으며 기술에 정통한 마법사들이 멀티 코어 프로세서와 고성능 컴퓨팅의 영역을 정복하려는 탐구를 이끌어 왔습니다. 그러면 암달의 법칙과 구스타프슨의 법칙은 무엇이며, 이 법칙들이 어떻게 개별적으로 또는 동시에 작용합니까? 병렬 프로그래밍의 중요성을 인식하면서 오늘 우리는 이러한 법칙의 복잡성을 자세히 알아보고 지식이 풍부한 프로그래머의 손에서 이러한 법칙을 강력한 도구로 사용할 수 있는 방법을 알아볼 것입니다.
암달의 법칙: 배경
– 최대 속도 향상
– 주의사항
구스타프슨의 법칙: 배경
– 확장된 속도 향상
– 주의사항
강력한 스케일링과 약한 스케일링
– 스케일링 테스트
— 강력한 스케일링
— 약한 스케일링
결론
1967년 Spring Joint Computer Conference에서 Gene Amdahl 박사는 IBM에서 심각한 컴퓨터 마술을 펼쳤고 Illiac-IV의 내부 작업을 뒷받침하는 천재인 천재 Daniel Slotnick을 포함하여 기술에 정통한 다른 세 사람과 함께 모였습니다. 그들은 무엇을 하고 있었나요? 글쎄요, 그들은 컴퓨터 아키텍처의 미래를 예측하고 있었습니다. 이 컨퍼런스에서 Gene Amdahl 박사는 실제 문제와 모든 지저분한 문제를 처리할 때 "다중 프로세서 접근 방식"이 직면하는 장애물에 대한 자신의 생각을 정리했습니다. 그리고 그는 그러한 성격의 문제에 대해 "단일 프로세서 접근 방식"을 크게 외쳤습니다!
IBM에 있는 동안 Amdahl은 자신이 적절하게 표현한 " 데이터 관리 관리 "가 컴퓨팅 작업의 상당 부분을 차지한다는 사실을 예리하게 알아차렸습니다. 그는 이 특정 부분이 대략 10년 동안 놀라울 정도로 일관되게 유지되어 생산 실행에서 실행된 명령의 40%를 지속적으로 차지했다고 확고히 주장했습니다.
이 "가사" 업무에는 무엇이 포함됩니까? 이는 필수적이지만 핵심 컴퓨팅 임무에 직접적으로 기여하지 않는 다양한 컴퓨팅 작업을 포함합니다. 특정 알고리즘 및 애플리케이션에 따라 여기에는 데이터 I/O, 전처리, 메모리 관리, 파일 처리 등이 포함될 수 있습니다. 이러한 일관성은 많은 애플리케이션에서 처리 시간의 상당 부분이 이러한 작업에 소비된다는 것을 의미합니다. 특정 수준의 데이터 관리 하우스키핑은 거의 불가피하며 크게 최소화하기가 어렵습니다. Amdahl은 이 오버헤드가 순차적으로 나타나는데, 이는 이것이 단계별로 발생하며 병렬 처리 기술에 적합하지 않다는 것을 의미합니다.
"이 시점에서 도출할 수 있는 상당히 분명한 결론은 거의 동일한 규모의 순차 처리 속도의 달성이 수반되지 않는 한 높은 병렬 처리 속도를 달성하기 위해 소비된 노력이 낭비된다는 것입니다." - 진 암달 박사 [1]
Amdahl은 자신의 원본 논문 [1]에서 "하우스키핑" 작업 영역은 "멀티 프로세서" 접근 방식이 직면한 과제와 관련하여 빙산의 일각에 불과하다고 덧붙였습니다. 박사 학위를 취득한 숙련된 이론 물리학자로서의 인상적인 배경을 바탕으로 Amdahl은 컴퓨터가 다루기 위해 설계된 실제 물리적 문제에 대해 깊은 이해를 갖고 있었습니다. 그는 불규칙한 경계, 불균일한 내부, 가변 상태에 대한 공간적, 시간적 종속성과 같은 많은 복잡성을 강조하며, 이 모든 것이 "멀티 프로세서" 패러다임에 엄청난 장애물을 제시합니다.
예를 들어 2D 데카르트 그리드에서 열 분포를 계산하는 것을 고려해 보세요. 특정 지점에서 온도(T)는 인접한 지점의 온도에 따라 달라집니다. 병렬 컴퓨팅 모델을 사용하는 경우 이러한 값을 별도의 프로세서에 저장할 수 있는 인접한 지점과 통신하는 것이 중요합니다. 이러한 문제는 현대 시나리오에서 계속해서 만연해 있습니다.
다행히도 컴퓨터 전문가들의 집단적 독창성은 이러한 복잡한 문제를 정면으로 해결하기 위해 맞춤화된 수많은 수치 방법과 프로그래밍 기술을 만들어냈습니다.
그의 원래 작업에서 Amdahl의 공식은 수학 방정식을 탐구하지 않았습니다. 최대 속도 향상이 정량화되는 것은 후속 분석에서만 가능했습니다.
암달의 법칙은 직렬 프로그램 실행 시간의 일부 f가 통신이나 동기화 오버헤드 없이 이상적으로 병렬화 가능하다는 가정을 기반으로 합니다. s = 1 − f 로 표시되는 보완 부분은 완전히 순차적입니다.
따라서 T가 순차 프로그램의 실행 시간인 경우 p 개 코어의 실행 시간 T(p) 는 다음과 같이 제공됩니다.
Speedup은 순차적 실행 시간과 병렬 실행 시간의 비율로 다음을 제공합니다.
따라서 속도 향상의 상한은 다음과 같이 정의될 수 있습니다.
단순함에도 불구하고 암달의 법칙에는 한계가 있습니다. 이 모델은 메모리 대역폭, 대기 시간, I/O 제약과 같은 중요한 하드웨어 병목 현상을 간과합니다. 또한 스레드 생성, 동기화, 통신 오버헤드 및 기타 실제 요인의 성능 단점을 고려하지 않습니다. 안타깝게도 이러한 설명되지 않은 요인은 일반적으로 실제 성과에 해로운 영향을 미칩니다.
다음 그림은 암달의 법칙에 따라 병렬화가 속도 향상에 미치는 영향을 보여줍니다. 95%의 상당한 병렬 비율과 광범위한 프로세서 배열을 사용하더라도 달성 가능한 최대 속도 향상 상한선은 약 20배라는 것이 분명합니다. 병렬화 비율을 99%로 높이고 무한히 많은 프로세서를 사용하면 100배 더 인상적인 속도 향상을 얻을 수 있으며 이는 유망합니다.
그러나 이렇게 많은 프로세서를 보유하는 것은 드문 일이라는 점을 인식하는 것이 중요합니다 . 우리는 종종 64개 이하와 같이 훨씬 더 적당한 숫자로 작업합니다.
64개의 프로세서(f는 95%)를 사용하는 프로그램에 Amdahl의 법칙을 적용하면 최대 속도 향상은 약 15.42배입니다. 물론, 이 수치는 그다지 유망하지 않습니다!
이 통찰력은 이 표현에 사용된 한계로 인해 다소 모호해졌습니다.
이 제한은 실제 프로세서 수를 고려할 때 속도 향상 수치가 눈에 띄게 낮다는 사실을 숨기는 경향이 있습니다.
그럼에도 불구하고 Amdahl 법칙의 가장 중요한 단점은 애플리케이션을 실행하기 위해 더 많은 코어를 활용할 때 문제 크기가 일정하게 유지된다는 가정에 있습니다.
기본적으로 병렬화 가능 비율은 사용된 코어 수에 관계없이 변하지 않는 것으로 가정합니다. 이 제한은 현재 Gustafson의 법칙 으로 알려진 수정된 관점을 제안한 John L. Gustafson 에 의해 철저히 해결되고 확장되었습니다. 그러나 이러한 알려진 문제와 주의 사항에도 불구하고 암달의 법칙에는 병렬화의 복잡성에 대한 귀중한 통찰력을 제공하는 고유한 장점이 있다는 점을 인식하는 것이 중요합니다. 암달의 법칙은 나중에 살펴볼 주제인 강력한 스케일링 테스트의 형태로 적용됩니다.
Sandia National Laboratories에서 대규모 병렬 컴퓨팅 시스템을 연구하는 동안 John L. Gustafson 박사 와 그의 팀은 1024 프로세서 하이퍼큐브에서 세 가지 다른 응용 프로그램에 대한 인상적인 속도 향상 요소를 얻었습니다. 일련번호 비율은 0.4~0.8%에 해당합니다.
“...우리는 전례 없는 1024 프로세서 하이퍼큐브의 속도 향상 요소를 달성했습니다. 공액 기울기를 사용한 빔 응력 분석의 경우 1021, 명시적 유한 차분을 사용한 당황한 표면파 시뮬레이션의 경우 1020, 플럭스 보정을 사용한 불안정한 유체 흐름의 경우 1016 수송." — 존 L. 구스타프슨 박사 [2]
우리는 마지막 섹션에서 Amdahl의 법칙에 따라 많은 수의 프로세서에 대해 달성할 수 있는 최대 속도 향상이 1/s라는 것을 분명히 보았습니다. 그렇다면 1021x라는 놀라운 속도 향상을 어떻게 달성할 수 있을까요?
Gustafson [2] 은 수학적 표현에 변수 f가 p 와 관련이 없음을 암시하는 미묘한 가정이 있음을 강조했습니다. 그러나 이 시나리오는 우리가 직면하는 현실이 아닙니다. 실제 시나리오에서는 학술 연구의 통제된 환경을 제외하고는 일반적으로 고정된 크기의 문제를 받아들이지 않고 다양한 수의 프로세서에서 실행합니다. 대신 실제 응용 프로그램에서는 문제 크기가 프로세서 수에 따라 확장되는 경향이 있습니다.
더 강력한 프로세서를 사용할 수 있게 되면 사용자는 향상된 기능을 최대한 활용하기 위해 문제의 복잡성을 확장하여 적응합니다. 그리드 해상도, 시간 단계 수, 차이 연산자의 복잡성 및 기타 매개변수와 같은 측면을 미세 조정하여 프로그램이 원하는 기간에 실행될 수 있도록 할 수 있습니다.
Gustafson에 따르면 실제로는 문제 크기보다는 런타임이 상대적으로 일정하게 유지된다고 가정하는 것이 더 현실적입니다.
Gustafson은 프로그램의 병렬 또는 벡터 비율이 문제 크기에 비례하여 증가한다는 사실을 발견했습니다. 프로그램 런타임의 구성 요소에 전체적으로 기여하는 벡터 시작, 프로그램 로딩, 직렬 병목 현상 및 I/O 작업과 같은 요소는 일반적으로 상대적으로 일정하게 유지되며 문제 크기에 따라 크게 증가하지 않습니다.
Gustafson은 물리적 시뮬레이션에서 자유도를 두 배로 늘리는 시나리오에서는 이에 상응하는 프로세서 수를 두 배로 늘리는 것이 종종 필수적이라는 점을 강조함으로써 이러한 주장을 더욱 발전시켰습니다. 예비 추정에 따르면 병렬로 효과적으로 분산할 수 있는 작업량은 프로세서 수에 따라 선형적으로 증가하는 경향이 있습니다.
언급된 세 가지 응용 프로그램에 대한 심층 조사에서 Gustafson과 그의 동료들은 병렬 구성 요소가 대략 1023.9969, 1023.9965 및 1023.9965의 배율 인수를 표시한다는 사실을 발견했습니다.
Gustafson의 가정은 p 코어의 정규화된 런타임을 고려하는 것입니다. 이는 합이 (1 − f) + f 가 되어 전체 값이 1이 됩니다. 이 논리에 따르면 if (1 − f) + f 는 p 코어의 런타임을 나타냅니다. , 단일 코어의 런타임은 (1 − f) + p*f 로 표현될 수 있습니다. 따라서 Gustafson이 " 확장된 속도 향상 "이라고 부르는 속도 향상은 다음과 같이 계산할 수 있습니다.
64개 프로세서(f는 95%)를 사용하는 프로그램에 구스타프슨의 법칙을 적용하면 예상 속도 향상은 60.85배입니다(암달의 법칙의 경우 15.42배). 이제 얘기하는 중이에요😉
다음 그림은 두 법칙의 차이점을 강조합니다.
Amdahl과 Gustafson의 관점은 병렬화에 대한 서로 다른 관점을 제공하며 각각 고유한 가정을 가지고 있습니다.
암달의 법칙은 병렬화할 수 있는 작업량이 일정하고 프로세서 수와 무관하다고 가정하므로 매우 비관적입니다. 병렬화할 수 있는 작업량이 코어 수에 따라 선형적으로 증가한다고 가정하는 Gustafson의 관점은 의심할 여지 없이 많은 시나리오에서 실용적입니다. 그러나 때로는 지나치게 낙관적일 수도 있습니다.
실제 애플리케이션에서는 이러한 선형 확장성을 제한할 수 있는 제약 조건에 자주 직면합니다. 예를 들어 코어 수가 증가하면 병렬 처리의 복잡성, 데이터 종속성 및 통신 오버헤드로 인해 수익 감소가 발생할 수 있습니다. 게다가 하드웨어 제한으로 인해 단일 칩에 효과적으로 통합할 수 있는 코어 수가 실질적으로 제한됩니다. 구스타프슨의 법칙은 이러한 복잡한 실제 문제를 항상 설명할 수는 없으므로 적용 가능성에 영향을 미치는 주의 사항을 고려해야 합니다.
구스타프슨 법칙의 유효성은 적용 자체의 성격에 따라 달라질 수도 있습니다. 일부 애플리케이션은 코어 수가 증가하면서 자연스럽게 선형 확장성을 제공하는 반면, 다른 애플리케이션은 내재된 제약이나 문제의 성격으로 인해 훨씬 더 빨리 정체될 수 있습니다. 실제 애플리케이션에서 선형 확장성의 타당성을 고려할 때 프로그래밍 복잡성과 수익 감소 가능성을 고려해야 합니다.
본질적으로 병렬화에 대해 보다 낙관적인 전망을 제시하는 동시에 구스타프슨의 법칙은 현대 컴퓨팅의 실제 복잡성에 맞춰 병렬 프로그래밍의 응용 프로그램, 하드웨어 제약 및 복잡성에 대한 깊은 이해를 바탕으로 적용되어야 합니다.
기본적으로 확장성은 규모가 확장됨에 따라 증가하는 워크로드를 효율적으로 관리할 수 있는 시스템 또는 애플리케이션의 용량을 의미합니다.
하드웨어든 소프트웨어든 컴퓨팅에서 확장성은 사용 가능한 리소스를 늘려 계산 능력을 향상시키는 능력을 의미합니다.
고성능 컴퓨팅(HPC) 클러스터의 맥락에서 확장성을 달성하는 것은 매우 중요합니다. 이는 추가 하드웨어 구성 요소를 통합하여 시스템의 전체 용량을 원활하게 확장할 수 있는 능력을 의미합니다. 소프트웨어와 관련하여 확장성은 종종 병렬화 효율성 과 동의어이며, 특정 수의 프로세서를 사용할 때 실현되는 실제 속도 향상과 달성 가능한 이상적인 속도 향상 사이의 비율을 나타냅니다. 이 지표는 소프트웨어가 병렬 처리를 얼마나 효과적으로 활용하여 성능을 향상시킬 수 있는지에 대한 통찰력을 제공합니다.
대규모 애플리케이션의 일반적인 개발 프로세스에서는 처음부터 전체 문제 크기와 최대 프로세서 수를 가지고 테스트를 시작하는 것이 비현실적인 경우가 많습니다. 이 접근 방식에서는 대기 시간이 길어지고 리소스가 과도하게 사용됩니다. 따라서 보다 실용적인 전략에는 초기에 이러한 요소를 축소하는 것이 포함됩니다. 이를 통해 테스트 단계를 가속화하고 최종 전체 규모 실행에 필요한 리소스를 보다 정확하게 예측할 수 있어 리소스 계획에 도움이 됩니다.
확장성 테스트는 응용 프로그램이 다양한 문제 크기와 다양한 프로세서 수에 얼마나 잘 적응하여 최적의 성능을 보장할 수 있는지 평가하는 수단으로 사용됩니다.
확장성 테스트에서는 애플리케이션의 전반적인 기능이나 정확성을 면밀히 조사하지 않는다는 점에 유의하는 것이 중요합니다. 주요 초점은 계산 리소스가 조정될 때 성능과 효율성에 있습니다.
두 가지 표준 스케일링 테스트( 강함 및 약함) 가 병렬 컴퓨팅에 널리 사용됩니다.
강력한 확장에는 문제 크기를 일정하게 유지하면서 프로세서 수를 늘리는 것이 포함됩니다. 이 접근 방식은 프로세서당 작업 부하를 줄여주는데, 이는 장기 실행 CPU 집약적 애플리케이션에 특히 유용합니다. 강력한 확장의 기본 목표는 리소스 비용을 관리 가능한 범위 내로 유지하면서 합리적인 실행 시간을 제공하는 구성을 식별하는 것입니다.
강력한 스케일링은 Amdahl의 법칙에 기반을 두고 있으며 처리 요소의 수가 증가하는 동안 문제 크기는 고정된 상태로 유지됩니다. 이 방법은 상당한 CPU 바인딩 작업 부하가 있는 프로그램에 대해 종종 정당화됩니다.
강력한 확장의 궁극적인 목표는 병렬 오버헤드로 인한 처리 주기 낭비를 최소화하면서 합리적인 시간 내에 계산을 완료할 수 있는 최적의 "최적 지점"을 찾는 것입니다.
강력한 확장에서는 단위 시간당 완료된 작업 단위 측면에서 속도 향상이 사용된 처리 요소 수(N)와 일치하는 경우 프로그램이 선형적으로 확장되는 것으로 간주됩니다. 마찬가지로 속도 향상은 프로세서 수에 따라 확장되는 정도에 따라 하위선형 또는 심지어 초선형이 될 수 있습니다.
마지막으로 내 코드 중 하나에 대해 강력한 스케일링 테스트를 수행해 보았습니다. Fluidchen-EM 은 다양한 유체 역학 문제를 해결할 수 있는 전산 유체 역학 솔버입니다. 다음 결과는 뚜껑 구동 캐비티 의 시뮬레이션에 해당합니다. 최종 타임스탬프(수렴 후)의 속도가 시각화되고 실행 런타임이 계산됩니다. Fluidchen-EM은 MPI를 사용하여 계산 영역을 iproc*jproc 프로세서에 분산합니다.
참고 : 결과는 내 개인용 컴퓨터에서 실행되었으며 모든 코어는 하나의 프로세서에만 해당합니다. 시뮬레이션이 더 크고 더 나은 기계에서 실행되면 결과가 달라질 수 있습니다!
계산 영역은 총 imax*jmax 그리드 포인트로 나누어집니다.
iproc: x 방향의 프로세서 수
jproc: y 방향의 프로세서 수
그림에서 볼 수 있듯이 프로세서 수가 1에서 2로 두 배로 증가함에 따라 실행 시간이 급격히 감소합니다. 그러나 다음 번에 프로세서를 2에서 4로 두 배로 늘리는 경우에는 속도 향상이 그다지 크지 않으며 추가 증가에 대해서는 포화 상태에 빠지기 시작합니다. 프로세서 수. 그러나 결과는 8개의 코어가 있는 프로세서에서 컴파일되었으므로 더 크고 강력한 시스템에서 실행이 수행되면 이러한 결과가 변경될 수 있습니다.
약한 확장에서는 프로세서 수와 문제 크기가 증가하여 프로세서 당 일정한 작업 부하를 유지합니다. 약한 스케일링은 고정된 문제 크기에 초점을 맞춘 암달의 법칙과 달리 스케일링된 문제 크기의 작업 부하를 기반으로 스케일링된 속도 향상이 계산되는 구스타프슨의 법칙과 일치합니다.
각 처리 요소에 할당된 문제 크기는 일정하게 유지되므로 추가 요소가 단일 노드의 메모리 용량을 초과할 수 있는 더 큰 전체 문제를 종합적으로 해결할 수 있습니다.
약한 확장은 단일 노드가 제공할 수 있는 것보다 더 많은 메모리를 필요로 하는 상당한 메모리 또는 리소스 요구 사항(메모리 바인딩된 요구 사항)이 있는 애플리케이션을 정당화합니다. 이러한 애플리케이션은 메모리 액세스 전략이 근처 노드의 우선 순위를 지정하여 더 높은 코어 수에 적합하도록 렌더링하므로 효율적인 확장을 나타내는 경우가 많습니다.
약한 확장의 경우 프로세서 수에 정비례하여 작업 부하가 증가함에 따라 런타임이 일정하게 유지될 때 선형 확장성이 달성됩니다.
이 모드를 채택한 대부분의 프로그램은 사용된 프로세스 수에 관계없이 통신 오버헤드가 상대적으로 일관되게 유지되기 때문에 특히 가장 가까운 이웃 통신 패턴을 사용하는 프로그램과 같이 더 높은 코어 수로 확장하는 데 유리한 모습을 보입니다. 이러한 추세의 예외에는 글로벌 통신 패턴에 크게 의존하는 알고리즘이 포함됩니다.
마지막으로 Fluidchen-EM을 사용하여 약한 스케일링 테스트를 수행했습니다. 다음 결과는 Rayleigh–Bénard 대류 시뮬레이션에 해당합니다. 다시 말하지만, 최종 타임스탬프(수렴 후)의 속도가 시각화되고 실행 런타임이 계산됩니다. Fluidchen-EM은 MPI를 사용하여 계산 영역을 iproc*jproc 프로세서에 분산합니다.
참고: 결과는 내 개인용 컴퓨터에서 실행되었으며 모든 코어는 하나의 프로세서에만 해당합니다. 시뮬레이션이 더 크고 더 나은 기계에서 실행되면 결과가 달라질 수 있습니다!
계산 영역은 총 imax*jmax 그리드 포인트로 나누어집니다.
iproc: x 방향의 프로세서 수
jproc: y 방향의 프로세서 수
imax: 채널 길이를 따른 그리드 포인트 수
jmax: 채널 높이를 따른 그리드 포인트 수
xlength: 채널의 길이
ylength: 채널의 높이
위 그림에서 볼 수 있듯이 문제 크기와 프로세서 수가 증가함에 따라 실행 런타임도 증가하는 것으로 나타났습니다. 이 동작은 여러 가지 요인에 기인할 수 있습니다. 모든 코어가 단일 프로세서에 상주하는 경우 문제 규모가 확대되고 더 많은 프로세서가 사용됨에 따라 MPI(Message Passing Interface) 통신을 설정하는 데 처리 시간의 일부가 소모됩니다. 또한 문제 크기가 커질수록 코어 간의 데이터 교환이 증가해야 하며, 통신 네트워크의 제한된 대역폭으로 인해 통신 지연 시간이 증폭됩니다.
따라서 이러한 테스트 결과는 문제의 병렬화에 대한 중요한 통찰력을 제공합니다.
알고리즘 병렬화에서 구스타프슨의 법칙과 암달의 법칙 사이의 선택은 계산 작업 부하의 적응성에 따라 달라집니다. 구스타프슨의 법칙은 알고리즘이 사용 가능한 병렬화에 맞게 계산량을 동적으로 조정할 수 있는 경우에 적합합니다. 대조적으로, 암달의 법칙은 계산 부하가 고정되어 있고 병렬화에 의해 크게 변경될 수 없을 때 더 적합합니다. 실제 시나리오에서 병렬화를 위해 알고리즘을 적용하려면 어느 정도의 계산 수정이 필요한 경우가 많으며, 두 법칙 모두 예측된 속도 향상에 대한 상한 및 하한을 제공하는 귀중한 벤치마크 역할을 합니다. 둘 사이의 선택은 병렬화 중에 도입된 계산 변경 정도에 따라 달라지므로 잠재적인 속도 향상 이점을 포괄적으로 평가할 수 있습니다.
[3] 두르간슈/플루이첸-EM
[4] 유해하다고 간주되는 멀티코어의 미래를 예측하는 암달의 법칙(tu-berlin.de)
[5] 확장 — HPC Wiki(hpc-wiki.info)
[6] 암달 대 구스타프슨 by r1parks — Infogram
Unsplash 의 Marc Sendra Martorell 의 특집 사진
여기에도 게시되었습니다.