Performance
성능
- 컴퓨터의 대표적인 Performance Measurement 지표로는 Response Time(응답시간)과 Throughput(처리율)이 있다.
- 시스템의 타입이나 용도에 따라 중요시되는 지표가 서로 다르다.
Response Time = Execution = Latency (응답 시간, 실행 시간, 대기 시간)
- 하나의 Task가 시작되고 종료되기까지 소요된 시간이다.
- 컴퓨터 시스템을 구성하는 모든 요소들의 성능에 좌우되는 지표이다.
(이에 반해, CPU만의 성능을 나타내는 지표로는 CPU Time*이 있다.)
- PC(개인 사용자), Embedded Computer등에서 중요시되는 지표이다.
* CPU Time
- CPU가 특정 Job 하나를 처리하는데 걸린 시간이다.
- 메모리, I/O장치, OS Overhead 등의 다른 요소는 고려하지 않고, CPU의 응답시간만을 의미하는 개념이다.
\(\mathrm{Performance = Response Time^{-1}}\)
: 성능과 응답 시간은 반 비례 관계에 있다.
\(\mathrm{Performance_{x} \over Performance_{y}} = {Response Time_{y} \over Response Time_{x}} = n\)
: \(\mathrm{x}\)가 \(\mathrm{y}\)보다 \(\mathrm{n}\)배 빠르다고할 때의 상관관계
\(\mathrm{CPU\_Time = CPU\_Clock\_Cycles\; *\; Clock\_Cycle\_Time = {CPU\_Clock\_Cycles \over Clock\_Frequency}}\)
: Period(Clock Time)와 Frequency(Clock Frequency)는 서로 역수 관계임을 상기하자.
\(\mathrm{CPU\_Clock\_Cycles = \#\; Instructions * CPI \iff \sum\limits_{i=1}^{n}(\# \; Instruction_{i} * CPI_{i})}\)
- \(\mathrm{\# \; Instructions}\) : Machine Code 레벨에서의 전체 명령어 개수
- \(\mathrm{CPI}\) : Clock Cycles Pre Instruction, 한 명령어를 처리하는데 걸린 평균 클럭 사이클
- 엄밀하게, CPI는 특정 명령어에 필요한 클럭 사이클 수 이지만, 일반적으로 평균 개념을 내포한 것으로 간주된다.
- 보다 자세한 결과를 얻기 위해선, 맨 오른쪽 항(\(\sum\)를 이용한 식)과 같이 Weighted Average를 계산해야 한다.
\(\mathrm{CPI} = {\mathrm{Clock Cycles} \over \mathrm{\# \; Instructions} } = \sum\limits_{i=1}^{n}(\mathrm{CPI_{i} * {\# \; Instruction_{i} \over \# \; Instructions}})\)
- 맨 오른쪽 항(\(\sum\)를 이용한 식)과 같이 엄밀한 계산 과정에서 \(\mathrm{CPI}\)는 명령어 종류의 분포에 따라 달라지게 된다.
Examples
Ex_1. Computer A는 특정 프로그램 P를 2GHz의 클럭 주파수로 10초에 처리할 수 있다.
설계하고자 하는 Computer B는 A보다 1.2배 큰 클럭 사이클로 설계되어 P를 6초만에 처리한다고 할 때,
Computer B의 클럭 주파수는 얼마인가?
Solution 1.
- \(\mathrm{CPU\_Time_{A} = 10_{sec} = {Clock\_Cycle_{A} \over 2GHz}}\)
\(\therefore \mathrm{Clock\_Cycle_{A} = 10*2*10^{9}}\)
- \(\mathrm{CPU\_Time_{B}} = 6_{sec} = {1.2*10*2*10^{9} \over Clock\_Frequency_{B}}\)
\(\therefore \mathrm{Clock\_Frequency_{B} = 4*10^9 Hz = 4 GHz}\)
Ex_2. 같은 ISA, 같은 컴파일러를 사용하지만, 서로 다른 마이크로아키텍처로 구성된 컴퓨터 A, B가 있다.
컴퓨터 A는 250ps의 Clock Cycle Time, 2.0의 CPI로 프로그램 P를 처리할 수 있으며,
컴퓨터 B는 500ps의 Clock Cycle Time, 1.2의 CPI로 프로그램 P를 처리할 수 있다고 할 때,
어느 컴퓨터가 얼마나 더 빠를까?
Solution 2.
- 같은 ISA로 구성된 컴퓨터들은 머신 코드 레벨에서 표현할 수 있는 명령어 체계가 같음을 의미한다.
- 같은 컴파일러를 사용한다 함은, 프로그램을 구성하는 머신 코드와 프로그램 흐름이 서로 일치함을 의미한다.
- 서로 다른 마이크로아키텍처로 구성된다 함은, 명령어를 분석해서 수행하는 회로의 설계가 서로 다름을 의미한다.
- 컴퓨터 A는 클럭 주기가 250ps이고, 한 명령어 당 2.0번의 클럭이 돌아야하므로, 하나의 명령어를 평균적으로 500ps에 처리할 수 있다.
- 컴퓨터 B는 클럭 주기가 500ps이고, 한 명령어 당 1.2번의 클럭이 돌아야하므로, 하나의 명령어를 평균적으로 600ps에 처리할 수 있다.
- 즉 컴퓨터 A는 컴퓨터 B보다 1.2배 우수하다.
Ex 3. 특정 ISA를 사용하는 한 컴퓨터에서 같은 프로그램을 두 개의 컴파일러 P, Q를 통해 각기 다르게 컴파일한다고 한다.
컴파일러 P는 Sequence 1 머신 코드를 생성하고,
컴파일러 Q는 Sequence 2 머신 코드를 생성하며,
3개의 명령어 A, B, C 각각의 CPI와, 두 컴파일러가 생성한 머신 코드의 명령어 분포는 아래 표와 같다.
| Instruction Type | A | B | C |
| CPI | 1 Clock | 2 Clocks | 3 Clocks |
| Sequence 1 Machine Code by Compiler P |
2개 | 1개 | 2개 |
| Sequence 2 Machine Code by Compiler Q |
4개 | 1개 | 1개 |
이 때 어느 컴파일러의 머신코드가 더 우수한 프로그램일까?
Solution 3.
Sequence 1을 수행하는 데 필요한 총 Clock Cycles = 2 * 1Clock + 1 * 2 Clocks + 2 * 3Clocks = 10 Clocks 이며,
평균 \(\mathrm{CPI_{1} = {10\; Clocks \over 5\; Instructions} = 2.0\; Clocks}\) 이다.
Sequence 2를 수행하는 데 필요한 총 Clock Cycles = 4 * 1Clock + 1 * 2Clocks + 1 * 3Clocks = 9 Clocks 이며,
평균 \(\mathrm{CPI_{2} = {9\; Clocks \over 6\; Instructions} = 1.5\; Clocks}\) 이다.
즉, 컴파일러 Q가 생성한 프로그램 Sequence 2가 1.34배 더 우수한 프로그램이다.
Throughput (처리율)
- 단위 시간동안 처리되는 Task의 양이다.
- 클라우드, 데이터센터, 슈퍼컴퓨터와 같이 대형 시스템에서 중요시되는 지표이다.
Pipelining (파이프라이닝 기법)
- 동시에 서로 다른 여러 개의 Task를 처리하는 기법이다.
- 다수의 Task로 이루어진 Work Load의 Throughput을 개선하는 데 도움을 주는 기법이다.
- 처리율을 극대화하기 위해선, 각 스테이지가 균형을 이루어 동시에 많은 Task가 수행되게 하는 것이 중요하다.
- Single Task에 대한 처리시간을 개선시켜 주지는 못한다.
Performance Determinant (성능에 영향을 미치는 요인들)
1. Algorithm(알고리즘) : 명령어의 개수
2. Programming language(프로그래밍 언어) : 명령어의 개수, CPI
3. Compiler(컴파일러) : 명령어의 개수, CPI
4. ISA(명령어 구조) : 명령어의 개수, CPI, 클럭 주기
5. Microarchitecture, Hardware implementation(하드웨어 구조) : CPI, 클럭 주기
6. Semiconductor technology(반도체 성능) : 클럭 주기
Amdahl's Law (암달의 법칙)
\({{1}\over{(1-P)+{P \over S}}}\)
: 전체 프로그램 시간(1이라는 전제 하에) 중 P 부분이 S만큼 개선될 때 기대되는 전체 성능 향상
이러한 종류의 성능 향상을 보통 "Speed up"이라고 부른다.
P: 최적화된 부분의 비율, S: 최적화된 부분의 성능 향상 (스피드업)
- 암달의 법칙은 프로그래머가 프로그램 성능을 개선시킬 때, 가장 많은 시간이 소요되는 부분을 중점적으로 개선해야 함을 의미한다.
- 자세히는, 병렬 컴퓨팅에서 컴퓨터 성능 최적화의 한계점을 측정할 때 이용하는 공식이다.
- 프로세서 설계자 역시 자신이 최적화하려는 부분이 전체에서 얼마나 중요한지를 생각하고 우선순위를 결정해야 한다.
- "Make the common case fast."와 일맥상통한다.
* 노르웨이계 미국 컴퓨터 공학자인 Gene amdahl의 이름을 딴 법칙이다. amdahl은 IBM에서 Mainframe개발에 크게 공헌했다.
병렬처리에서의 암달의 법칙
\({1 \over {(1-P) + {P \over N}}}\)
P: 병렬화가 가능한 부분의 비율, N: 프로세서 개수
: 직렬화 가능한 부분(1-P)은 최소화, 병렬화 가능한 부분은 최대화 하는 것이 핵심이다.
* 암달의 법칙의 제한
- 프로세서 N이 완벽하게 P만큼의 일을 병렬 처리한다는 이상적인 가정 하에 세워진 공식이다.
- 병렬성에 대한 구체적 정의 없이, 단순히 병렬 가능한 부분이 완벽히 프로세서 개수만큼 수행 시간이 줄어든다고 가정했다.
- 그러므로, 실제 병렬화 후 얻어지는 성능은 이보다 크게 낮을 가능성이 있다.
- 병렬화에는 스레드 생성 비용과 같은 고정 비용 및 프로세스/스레드 사이에 MUTEX* 같은 동기화 객체로
효율이 떨어지게 되므로 큰 성능 향상이 이루어지지 않을 수 있다.
* MUTEX: 상호 배제(MUTual EXclusion)의 약자이다.
* Embarrassingly parallel: 주어진 작업이 별 노력 없이 완벽히 병렬화 가능한 경우에 해당 작업을 지칭하는 용어
Ex. \(\texttt{add}\) 연산에는 30s,
\(\texttt{sub}\) 연산에는 20s,
\(\texttt{mul}\) 연산에는 25s,
\(\texttt{div}\) 연산에는 25s가 소요되는 하드웨어에서
덧셈 연산 부분에 대해 10배 만큼의 성능 개선을 성공시켰다.
이 때, 전체 프로그램은 얼마나 개선된 것일까?
Solution
개선 전, 프로그램은 4개의 사칙 연산을 수행하는 데 100s의 시간이 소요된다.
개선 후, 프로그램은 4개의 사칙 연산을 수행하는 데 73s의 시간이 소요된다.
즉, 성능이 27%만큼 개선된 것이다.
이를 암달의 법칙에 적용해보면,
여기서 \(\mathrm{P}\)는 덧셈 연산이 차지했던 비율, 즉 0.3이고,
\(\mathrm{S}\)는 성능 향상 정도, 즉 10이다.
암달의 법칙으로 확인해보자.
식에 대입해보면 \(\mathrm{{1 \over {1-0.3 + {0.3 \over 10}}}} = 0.73\) 으로 되고,
이 값과 1.0(100%)과의 차이를 구해보면 0.27 즉, 27%의 성능향상이 이루어졌음을 암달의 법칙을 통해서도 확인할 수 있다.
More Precise Memory Unit (보다 정확한 메모리 단위 체계)
- 컴퓨터 내부에서 처리되는 수치는 이진수이므로, 메모리의 단위는 1,000이 아닌,
\(2^10 = 1,024\)씩 차이가 나도록 정의되었다.
- 그러나, 일상 생활에서 계산, 표기에 용이하게 하기 위해 메모리의 단위를 1,000으로 사용하는 것이 일반적이다.
(1,024와 큰 차이가 나는것은 아니기 때문이다.)
- 보다 엄밀한 계산을 위해서는 Decimal Term이 아닌, Binary Term 단위를 이용하는 것이 바람직하다.
Single Cycle MIPS Performance
- Critical Path : 가장 긴 수행 시간을 필요로 하는 명령어가 처리되는 경로를 의미하는 용어이다.
클럭 주기를 결정하는 경로이다.
- Single Cycle MIPS의 경우 \(\texttt{lw}\) 명령어가 Critical Path에 해당되는 명령어이다.
- Register File에 두 번 접근(Base를 읽기 위한 접근, 메모리 값을 레지스터에 쓰기 위한 접근)하기 때문에 \(\texttt{lw}\)가 critical Path인 경우가 대부분이다.
- \(\texttt{sw}\)의 경우 Register파일에 두 번 접근하지는 않는다.
- \(\texttt{lw}\)을 수행하는 데 걸리는 모든 Path에서 소요되는 Delay의 합을 \(T_{c}\)라 했을 때, 그 값은 아래 수식과 같다.
\(T_{c} = T_{pcq_PC} + T_{mem} + \mathrm{max}(T_{RFread}, T_{Sext} + T_{mux} + T_{ALU} + T_{mem} + T_{mux} + T_{RFsetup})\)
| Parameter | Elements |
| \(T_{pcq_PC}\) | 클럭이 Rising_Edge일 때 부터 PC값을 받아들일 수 있는 시간 |
| \(T_{mem}\) | 메모리로부터 명령어를 읽어오는 시간 |
| \(T_{RFread}\) | 레지스터 파일로부터 읽어오는 시간 |
| \(T_{Sext}\) | Sign-Extension을 취하는 시간 |
| \(T_{mux}\) | MUX를 거치는 시간 |
| \(T_{ALU}\) | ALU를 거치는 시간 |
| \(T_{RFsetup}\) | 레지스터 파일에 값을 입력하는 시간 |
※ 레지스터 파일, 메모리 접근 시간, ALU 처리 시간이 대부분을 차지하는 경우가 많다.
※ \(f_{c} = {1 \over T_{c}}\) 임을 이용해, 클럭 주파수 또한 구할 수 있다.
Reference: Computer Organization and Design 5E (David A. Patterson, John L. Henessy 저, MK, 2014)
