Amdahl's law


Gene Amdahl에 의해서 만들어진 법칙이다.



어떤 시스템의 P만큼 부분을 S만큼 개선하면


전체 시스템에서의 최대 성능 향상은 아래의 식을 따른다.




즉, 이것을 병렬처리에 적용하면 아래와 같다.

S만큼 개선이라는 말은 CPU 갯수를 의미한다. 2개면 2배, 3개면 3배이다.

P만큼 부분이라면 CPU를 늘렸을때 향샹되는 것이기 때문에 병렬화가 가능한 Instruction의 수이다.


proof of Amdahl’s Law

Suppose an algorithm needs n operations to compute the result. With 1 processor, the algorithm will take n time units. With N processors, the (1f)n parallelizableoperations will take (1f)n time units and the remaining fn non parallelizable operations will take fn time units for a total running time of fn+(1f)nN time units. So the speedup S is nfn+(1f)nN=1f+1fN.



예를들어, P가 40%로 0.4이고 S가 2배 향상되어 2라면 아래와 같다.




이러한 Amdahl's law는 병렬 컴퓨팅에서의 멀티 프로세서에 따른 성능향상을 설명할때 사용 된다.



위의 그림과 같이 병렬 컴퓨팅에서 멀티프로세서를 사용할 때 프로그램의 성능향상은 프로그램의 순차적인 부분에 의해 제한된다. 예를 들면, 프로그램의 95%가 병렬화 할 수 있다면 이론적인 최대 성능 향상은 아무리 많은 프로세서를 사용하더라도 최대 20배로 제한된다.



'Computer Science > 컴퓨터 구조' 카테고리의 다른 글

Purpose of memory alignment  (0) 2014.11.25
4. 멀티 프로세서  (0) 2013.06.09
성능평가 방법  (0) 2012.11.21

Purpose of memory alignment


http://stackoverflow.com/questions/381244/purpose-of-memory-alignment

'Computer Science > 컴퓨터 구조' 카테고리의 다른 글

Amdahl's law  (0) 2015.03.18
4. 멀티 프로세서  (0) 2013.06.09
성능평가 방법  (0) 2012.11.21


4.4 분산 공유 메모리와 디렉터리 기반 일관성


스누핑 프로토콜은 공유 데이터에 대한 쓰기나 캐시 미스가 발생할 때마다 모든 캐시들 사이에 통신을 필요로 한다.


장점: 캐시 상태를 추적하는 중앙 데이터 구조가 없는 것이 장점이다.

단점: 하지만 확장성 면에서 문제가 있다.


매번 브로드캐스를 해야한다면, 메모리 대여폭 면에서 문제가 발생하게 된다. 


이것에 대한 해결방법이 디렉터리 기반의 프로토콜이다.


디렉터리는 캐시되는 모든 블록의 상태를 기록한다.


디렉터리에는 다음의 내용들이 저장되어 진다.

즉, 어떤 캐시들이 이 브록의 복사본을 가지고 있고, 이 브록이 변경되었는지 등을 기록한다.


가장 간단한 디렉터리 구현은 각 메모리 블록마다 하나의 디렉터리 엔트리를 갖게 하는 것이다. 


간단한 프로토콜은 다음과 같은 상태들을 관리한다.


1) 공유(shared): 하나 이상의 프로세서가 이 블록을 캐시한다. 모든 캐시와 메모리는 최신 값을 가지고 있다.

2) 캐시 안됨: 어떤 프로세서도 이 캐시 블록의 복사본을 갖고 있지 않다.

3) 변경: 단 하나의 프로세서만 이 캐시 블럭의 복사본을 갖고 있으며 이 프로세서가 블록에 쓰기를 수행하였다. 따라서 메모리에 있는 사본은 오래된 값을 갖고 있다 




'Computer Science > 컴퓨터 구조' 카테고리의 다른 글

Amdahl's law  (0) 2015.03.18
Purpose of memory alignment  (0) 2014.11.25
성능평가 방법  (0) 2012.11.21

시간이 중요하다.


결국 경과시간과 CPU시간은 다르다.


CPU 시간 = CPI * 명령어 수 * CPU 클럭 이다.



컴퓨터의 성능을 비교하는 기준으로 MIPS를 사용하는데는 세 가지 문제가 있다.


1) MIPS는 단순히 명령어를 실행하는 속도를 나타낼 뿐이지, 그 명령어 하나가 얼마나 많은 일을 수행하는지는 반영하지 못한다. 


명령어의 집합이 다르면 명령어 개수가 달라지기 때문에 단순히 MIPS 값으로만 성능을 비교할 수는 없다.


2) 같은 컴퓨터에서도 어떤 프로그램을 실행하느냐에 따라 MIPS값은 달라진다. 그러므로 컴퓨터의 MIPS 값은 하나가 아니다.


3) MIPS가 컴퓨터 성능과 정반대로 나타나는 경우가 있다는 것이다.(FALSE)가 존재한다.


인스트럭션을 많이 실행한다고해서 실행시간이 빨라지는것은 아니기 때문이다.


실행시간이 20 초인게 350MIPS

실행시간이 30초인게 400MIPS


위와 같을 수 있다.

인스트럭션은 아래의 것이 훨씬더 많이 실행하지만, 그래봐야 느리다는것이다.

근본적인 이유는 instruction은 모두 실행시간이 다 다르다. pipeline stall이나 cache miss와 같은 이유에서, 또한 MIPS는 프로그램마다 다르게 측정 되기 때문이다.


따라서 2개의 컴파일러를 비교할때 결국 다르고, 컴파일러가 다르면 같은 컴퓨터에서라도 제대로 측정이 안된다.




요점 정리


성능을 종합하는 측도라면 반드시 실행시간을 반영 해야 한다. 가중 산술평균은 실행 시간을 잘 반영하는 성능 측도이다. 각 프로그램의 실행시간이 다르더라도 가중치를 사용하면 모든 프로그램이 같은 비율로 반영되게 할 수 있다.




참고사이트: Wikipedia




'Computer Science > 컴퓨터 구조' 카테고리의 다른 글

Amdahl's law  (0) 2015.03.18
Purpose of memory alignment  (0) 2014.11.25
4. 멀티 프로세서  (0) 2013.06.09

+ Recent posts