스피드업

컴퓨터 구조에서 **스피드업**(speedup)은 동일한 문제를 처리하는 두 시스템의 상대적인 성능을 측정하는 숫자이다. 더 기술적으로는 서로 다른 자원을 가진 두 유사한 아키텍처에서 실행되는 작업의 실행 속도 향상을 의미한다. 스피드업의 개념은 암달의 법칙에 의해 확립되었는데, 이 법칙은 특히 병렬 처리에 중점을 두었다. 그러나 스피드업은 더 일반적으로 모든 자원 향상 후 성능에 미치는 영향을 보여주는 데 사용될 수 있다.

## 정의
스피드업은 두 가지 다른 유형의 양에 대해 정의될 수 있다: 레이턴시와 처리량.

아키텍처의 레이턴시는 작업 실행 속도의 역수이다:
: L = \frac{1}{v} = \frac{T}{W},
여기서
* v는 작업의 실행 속도;
* T는 작업의 실행 시간;
* W는 작업의 실행 작업량이다.
아키텍처의 처리량은 작업의 실행률이다:
: Q = \rho vA = \frac{\rho AW}{T} = \frac{\rho A}{L},
여기서
* ρ는 실행 밀도(예: 파이프라인화된 아키텍처의 명령어 파이프라인 단계 수);
* A는 실행 용량(예: 병렬 아키텍처의 프로세서 수)이다.
레이턴시는 종종 실행 작업량 단위당 초로 측정된다. 처리량은 종종 초당 실행 작업량 단위로 측정된다. 또 다른 처리량 단위는 클럭당 명령어 처리 횟수(IPC)이며, 그 역수인 클럭당 사이클 수(CPI)는 또 다른 레이턴시 단위이다.

스피드업은 무차원이며 일관된 측정항목이 되도록 각 유형의 양에 대해 다르게 정의된다.

### 레이턴시 스피드업
레이턴시 스피드업은 다음 공식으로 정의된다:
: S_\text{latency} = \frac{L_1}{L_2} = \frac{T_1W_2}{T_2W_1},
여기서
* Slatency는 아키텍처 1에 대한 아키텍처 2의 레이턴시 스피드업;
* L1은 아키텍처 1의 레이턴시;
* L2는 아키텍처 2의 레이턴시이다.

레이턴시 스피드업은 암달의 법칙 또는 구스타프슨의 법칙으로부터 예측할 수 있다.

### 처리량 스피드업
처리량 스피드업은 다음 공식으로 정의된다:
: S_\text{throughput} = \frac{Q_2}{Q_1} = \frac{\rho_2A_2T_1W_2}{\rho_1A_1T_2W_1} = \frac{\rho_2A_2}{\rho_1A_1}S_\text{latency},
여기서
* Sthroughput은 아키텍처 1에 대한 아키텍처 2의 처리량 스피드업;
* Q1은 아키텍처 1의 처리량;
* Q2는 아키텍처 2의 처리량이다.

## 예시
### 실행 시간 사용
프로그램 실행에 대한 분기 예측기의 효과를 테스트하고 있다. 먼저 프로세서에서 표준 분기 예측기로 프로그램을 실행하면 실행 시간이 2.25초가 나온다. 다음으로 동일한 프로세서에서 수정된(그리고 바라건대 개선된) 분기 예측기로 프로그램을 실행하면 실행 시간이 1.50초가 나온다. 두 경우 모두 실행 작업량은 동일하다. 스피드업 공식을 사용하면 다음을 알 수 있다.
:S_\text{latency} = \frac{L_\text{old}}{L_\text{new}} = \frac{2.25~\mathrm{s}}{1.50~\mathrm{s}} = 1.5.
새로운 분기 예측기는 원래 예측기보다 1.5배의 스피드업을 제공했다.

### 클럭당 명령어 처리 횟수 및 클럭당 사이클 수 사용
레이턴시인 클럭당 명령어 처리 횟수(CPI)로도 스피드업을 측정할 수 있다. 먼저 표준 분기 예측기로 프로그램을 실행하면 CPI는 3이 나온다. 다음으로 수정된 분기 예측기로 프로그램을 실행하면 CPI는 2가 나온다. 두 경우 모두 실행 작업량은 동일하며 두 아키텍처는 파이프라인화되거나 병렬화되지 않았다. 스피드업 공식을 사용하면 다음이 나온다.
: S_\text{latency} = \frac{L_\text{old}}{L_\text{new}} = \frac{3~\text{CPI}}{2~\text{CPI}} = 1.5.

처리량이며 CPI의 역수인 클럭당 명령어 처리 횟수(IPC)로도 스피드업을 측정할 수 있다. 스피드업 공식을 사용하면 다음이 나온다.
: S_\text{throughput} = \frac{Q_\text{new}}{Q_\text{old}} = \frac{0.5~\text{IPC}}{0.33~\text{IPC}} = 1.5.

다른 양을 측정했지만 동일한 1.5배 스피드업을 달성했다.

## 추가 세부 정보
S를 작업 실행의 스피드업이라고 하고 s를 아키텍처 자원 개선의 이점을 받는 작업 부분의 실행 스피드업이라고 하자. 선형 스피드업 또는 이상적인 스피드업은 일 때 얻어진다. 선형 스피드업으로 작업을 실행할 때, 로컬 스피드업을 두 배로 늘리면 전체 스피드업도 두 배가 된다. 이것은 이상적이므로 매우 좋은 확장성으로 간주된다.

효율성은 개선된 시스템의 자원 활용도를 측정하는 지표로 다음과 같이 정의된다.
: \eta = \frac{S}{s}.
그 값은 일반적으로 0과 1 사이다. 선형 스피드업을 가진 프로그램과 단일 프로세서에서 실행되는 프로그램은 효율성이 1인 반면, 병렬화하기 어려운 많은 프로그램은 프로세서 수 가 증가함에 따라 0에 가까워지는 1/ln(s)와 같은 효율성을 갖는다.

엔지니어링 맥락에서는 스피드업 곡선보다 효율성 곡선이 그래프에 더 자주 사용된다. 이는
* 그래프의 모든 영역이 유용하기 때문이다(스피드업 곡선에서는 공간의 절반이 낭비됨).
* 시스템 개선이 얼마나 잘 작동하는지 쉽게 알 수 있다.
* "완벽한 스피드업" 곡선을 그릴 필요가 없기 때문이다.
마케팅 맥락에서는 스피드업 곡선이 더 자주 사용되는데, 주로 위쪽과 오른쪽으로 올라가서 정보가 부족한 사람들에게 더 좋게 보이기 때문이다.

## 초선형 스피드업
때로는 병렬 컴퓨팅에서 A개의 프로세서를 사용할 때 A보다 큰 스피드업이 관찰되는데, 이를 초선형 스피드업이라고 한다. 초선형 스피드업은 드물게 발생하며, A개의 프로세서를 사용할 때 이론적인 최대 스피드업이 A여야 한다고 생각하는 초보자들을 종종 혼란스럽게 한다.

저수준 계산에서 초선형 스피드업이 발생하는 한 가지 가능한 이유는 현대 컴퓨터의 서로 다른 메모리 계층 구조에서 발생하는 캐시 효과이다: 병렬 컴퓨팅에서는 프로세서의 수만 변하는 것이 아니라 서로 다른 프로세서에서 누적된 캐시의 크기도 변한다. 누적 캐시 크기가 커지면 더 많은 또는 모든 작업 집합이 캐시에 들어갈 수 있고 메모리 접근 시간이 극적으로 줄어들어 실제 계산으로 인한 스피드업 외에 추가적인 스피드업을 유발한다.

BLAST 구현으로 검색되는 유전체 데이터와 같은 대규모 데이터 세트를 검색할 때 유사한 상황이 발생한다. 이 경우 클러스터의 각 노드에 축적된 RAM 덕분에 데이터 세트를 디스크에서 RAM으로 옮길 수 있어 예를 들어 mpiBLAST가 검색하는 데 필요한 시간을 획기적으로 줄일 수 있다.

초선형 스피드업은 병렬로 퇴각검색을 수행할 때도 발생할 수 있다. 한 스레드의 예외가 다른 여러 스레드가 스스로 예외에 도달하기 전에 일찍 퇴각검색하게 만들 수 있기 때문이다.

초선형 스피드업은 최적화를 위한 분기 한정 병렬 구현에서도 발생할 수 있다. 한 프로세서가 한 노드를 처리하는 것이 다른 프로세서가 다른 노드에 대해 수행해야 하는 작업에 영향을 미칠 수 있기 때문이다.

## 같이 보기
* 암달의 법칙
* 구스타프슨의 법칙
* 브룩스의 법칙
* 카프-플랫 지표
* 병렬 속도 저하
* 확장성

## 각주

분류:병렬 알고리즘 분석