암달의 법칙 (Amdal's Law)

개념
프로그램은 병렬처리가 가능한 부분과 불가능한 순차적인 부분으로 구성되므로 프로세서를 아무리 병렬화 시켜도 더 이상 성능이 향상되지 않는 한계가 존재 한다는 법칙

I. 프로세스 병렬화 속도 한계성에 대한 암달의 법칙

가. 암달(Amdahl)의 법칙 정의

  • 프로그램은 병렬처리가 가능한 부분과 불가능한 순차적인 부분으로 구성되므로 프로세서를 아무리 병렬화 시켜도 더 이상 성능이 향상되지 않는 한계가 존재 한다는 법칙

 

나. 암달의 법칙 의미

  • 성능 한계는 캐쉬, 메모리, 버스와 같이 제한된 자원을 프로세스가 서로 점유하려고 쟁탈 하는 오버헤드에 이해 발생
  • 시스템 구성상 프로세서가 2배가 되더라도 20~40% 정도의 성능 손실이 발생, 4개의 CPU를 쓰더라도, 단일 CPU에 비해서 평균 2.5배 정도 성능 향상
  • 병렬처리 컴퓨터를 효율적으로 사용하기 위해서는 순차처리코드 부분이 적어야 함.
  • 순차처리 코드비율이 크면 프로세서 수가 증가해도 성능향상 및 속도개선이 안됨

     

II. 암달의 법칙 개념도

  • f : FRACTION[비율] : 순차적으로 수행해야되는 부분
  • 잠재적인 프로그램 Speed Up 을 기술하는 Amdahl 법칙은 병렬화 시킬 수 있는 코드의 비율(P)로 정의
  • Speedup = 1/(1-P)

 

III. 암달의 법칙 공식 적용 예제

가) 시스템 성능 향상도 구하기(Single CPU))

  • 암달의 법칙은 성능 향상 변수를 측정하여 파악하고 성능 향상과 상관관계를 분석하여 시스템 설계에 반영해야 함.

 

 

 

 

  • n : 향상배수, t : 향상 가능 부분
  • 프로그램 A 샘플

 

 

 

 

 

* 사례 A (상용업무 전반) : CPU Clock Speed 2배 가속

 

 

 

* 사례 B (공학계산) : 부동소수연산 가속기 부착 2배 가속

 

 

 

* 사례 C (거의 모든 상용업무) : 메모리/디스크 입출력 2배 향상(-> Bus 구조, 캐시, 디스크 등 시스템 아키텍처 최적화)

 

 

 

나) 코드의 병렬화만 개선시 성능 향상도

 

 

 

f : fraction of code which can be parallelized

  • f가  0%(0.0)인 경우 speedup = 1 즉, 속도 향상 없음
  • f가 50%(0.5)인 경우 speedup = 2 즉, 2배 향상
  • f가 80%(0.8)인 경우 speedup = 5 즉, 5배 향상
  • f가 90%(0.9)인 경우 speedup = 10 즉, 10배 향상
  • f가 Near 100%인 경우 speedup = 무한대 (이론상)

 

 

 

 

 

 

 

 

  • 코드의 병렬화가 100%인경우 시스템의 속도는 무한대 향상되지만 실제 구현은 불가능

 

다) 코드와 프로세서의 수를 함께 개선하는 경우 성능 향상도

 

P : Parallel fraction, N : Process의 수, S : Serial Fraction

  • Serial Fraction 의 경우 프로세서를 늘려도 성능 향상의 의미가 없음
  • Parallel Fraction의 경우 프로세서의 수와 병렬화 정도에 따라 성능 향상이 가능

 

- P + S = 1 이므로 P가 0.5 인 경우 S는 0.5로 간주
- P가 50% 인 경우 프로세서가 100개인 경우와 10,000개인 경우간의 성능향상이 거의 없음
- P가 90% 인 경우 프로세서가 1,000개인 경우와 10,000개인 경우간의 성능향상이 거의 없음

  • 프로세서 수가 증가해도 성능 향상 및 속도 개선은 한계가 있음

 

IV. 암달의 법칙을 이용한 CPU 성능향상 방안

 

가) 순차처리 코드의 오버헤드 극복

  • 프로그램에서 데이터 초기화 (I/O)는 병렬화가 어려움
  • 프로그램의 계산량은 데이터 크기의 지수승에 비례

* Rank Sort : n2에 비례, O(n2), 제곱승

* 행렬 곱셈 : n3에 비례, O(n3), 세제곱승

  • 암달의 법칙에서 데이터 초기화를 위한 순차처리 코드부분에 의한 성능저하는 데이터 크기를 증가함으로써 극복함 -> 동일한 수천 수만의 순차처리 업무를 대단위로 분산처리, 고도의 수치계산, Data Mining, 네트워크 통합 시뮬레이션 등에서 활용됨

나) 병렬처리 기법 적용

  • 파이프라인 구조의 시스템아키텍쳐 설계
  • 병렬프로세서 도입
  • 프로그램 컴파일 최적화 기법 적용
  • 데이터의 의존성 최소화한 응용시스템 개발

     

V. Amdahl의 법칙 활용

  • 최저 비용으로 최상의 시스템을 구현할 수 있는 수학적 근거로 활용
  • 시스템의 성능에 대한 개선을 하드웨어적인 접근 방식이 아닌 OS, 컴파일러, 소프트웨어등과 같은 다양한 분야에서 접근 가능하도록 전기를 마련
  • Sun의 경우 JDK 1.4 개발 시 Garbage Collection 성능 향상을 위한 설계에 적용
  • OS, 시스템 S/W, 전략적인 고도수치계산 등의 개발 시 분산처리는 기본적인 사항으로 고려됨

멧칼프의 법칙

암달의 법칙

네트워크 유용성 및 사용자 증가율

Process 수를 병렬화해도 성능 상상의 한계가 존재한다는 법칙

1981년 3Com의 멧칼프

1967년 Amdahl의 논문에서 발표

전화의 보급

4개 CPU 사용 -> 2.5배의 성능 향상

인터넷이 킬러 앱으로 점점 더 폭발적인 위력을 가질 것이라는 것을 보여줌

프로그램 내에서 데이터 초기화(I/O)는 병렬화가 어렵지만, 분산처리, 고도의 수치계산으로 극복 가능

 

 

댓글