[컴퓨터구조#14] SIMD

참고: Computer Architecture: A Quantitative Approach (5th edition) - 4.1.~4.3.

이번 글에서는 SIMD에 대해 알아볼 것이다.

목차

1. SIMD
2. 벡터 프로세서
3. 멀티미디어 SIMD Extensions
4. Roofline 성능 모델

---

1. SIMD

명령어와 데이터 스트림에 따라 프로세서를 다음과 같이 분류할 수 있다.

		Data Streams
		Single	Multiple
Instruction Streams	Single	SISD - Intel Pentium 4	SIMD - SSE instructions of x86
	Multiple	MISD - 없음	MIMD - Intel Xeon e5345

*SPMD(Single Program Multiple Data): MIMD 컴퓨터에 대한 병렬 프로그램. 서로 다른 프로세서에 대한 조건부 코드.

SIMD(Single Instruction Multiple Data): 데이터 벡터에 elementwise 연산을 수행하는 것

• 예시: x86의 MMX, SSE 명령어 -> 128-bit 레지스터 내 여러 데이터 element
• 모든 프로세서가 동시에 같은 명령어를 수행 (하지만 다른 데이터 주소로)
• 동기화를 단순하게 함
• 명령어 컨트롤 하드웨어를 줄임
• 매우 data-parallel한 응용에 최적으로 작동한다. 모든 프로그램에 적용 가능한 것은 아니다.

SIMD 아키텍처는 행렬-oriented scientific computing(Dense 행렬), media-oriented 이미지/소리 프로세서 등에서 높은 data-level 병렬성을 활용할 수 있다. 그리고 SIMD는 MIMD보다 더 에너지(=area) 효율적이다. 데이터 연산당 한 개의 명령어만 fetch하면 되기 때문이다. 이는 SIMD를 개인용 모바일 장치에 더 적합하도록 만들어준다. 또한, SIMD는 프로그래머가 sequentially 생각할 수 있도록 한다. 

 

2. 벡터 프로세서

고도로 파이프라인된 function unit으로, 데이터를 벡터 레지스터(한번에 여러 데이터를 저장할 수 있는 긴 레지스터)에서 function unit으로 스트리밍한다. 데이터는 메모리에서 레지스터로 모이고, 결과는 레지스터에서 메모리로 저장된다. 

• 예시) MIPS의 벡터 확장: VMIPS
  • 32개의 64-element 벡터 레지스터 (64-bit element)
  • 벡터 명령어: lv, sv, addv.d (add vector double), addvs.d (add scalar to each element of vector of double)
  • 장점: 명령어 fetch 대역폭을 크게 줄인다.
• MIPS와 VMIPS의 DAXPY(Y=a*X+Y) 비교: MIPS에 비해 VMIPS에서 훨씬 compact한 것을 알 수 있다. mulvs.d에서 최대 한번에 64개의 element까지 연산이 가능하므로 MIPS에서 사용했던 loop가 필요 없다.

 

Multiple Lanes

벡터 레지스터 A의 element n은 벡터 레지스터 B의 element n과 hardwire되어 있다. -> 즉 여러 개의 하드웨어 lane을 허용한다. lane이 많을수록 병렬성은 증가한다.

예를 들어 64 element vector register의 경우, 각 lane이 서로 다른 data element를 처리한다. 오른쪽 그림에서 Lane 0은 벡터 레지스터 내 0,4,8, ... 번째 element를, Lane 1은 1,5,9,...번째를 처리한다.

(왼) vector 덧셈 C=A+B의 성능을 향상시키기 위해 여러 functional unit을 사용하는 것 / (오) 4개의 lane을 포함하는 벡터 유닛의 구조

 

Vector supercomputer: cray-1

• Scalar Unit: Load/Store 아키텍처
• Vector Extension: 벡터 레지스터, 벡터 명령어
• 구현: hardwired control, 파이프라인된 functional units, interleaved 메모리 시스템, 데이터 캐시 없음, 가상메모리 없음

Cray-1 아키텍처

Vector programming Model

• Vector Arithmetic Instructions
  • ex) ADDV v3, v1, v2
  • 각 lane에서는 v1, v2 피연산자를 읽고 v3에 쓴다. lane 개수에 따라 동시에 실행할 수 있는 연산 수가 결정된다. 64 element vector register에서, lane이 64개라면 전체 벡터 덧셈은 한 단계만에 완료될 수 있지만, lane이 만약 8개라면 전체 덧셈을 완료하는 데 8단계가 걸린다. 즉, 벡터 연산이 얼마나 걸리는지는 vector length와 available lane에 따라 결정된다.
• Vector Load & Store Instructions
  • ex) LV v1, r1, r2
  • v1은 load해올 destination, r1은 source (base), r2는 stride를 뜻한다.

코드 예시를 통해 벡터 프로그래밍에 대해 알아보자.

C code	Scalar Code	Vector Code
for (i=0; i<64; i++)   C[i] = A[i]+B[i];	LI R4,64 loop:  L.D F0, 0(R1)  L.D F2, 0(R2)  ADD.D F4, F2, F0  S.D F4, 0(R3)  DADDIU R1, 8   DADDIU R2, 8  DADDIU R3, 8  DSUBIU R4, 1  BNEQ R4, loop	LI VLR 64 LV V1, R1 LV V2, R2 ADDV.D V3, V1, V2 SV V3, R3

스칼라 코드의 DADDIU R1, 8 ~ DSUBIU R4,1은 인덱스 관리 부분, BNEZ R4, loop는 bound checking하는 부분이다. 스칼라 코드에 비해 벡터 코드일 때 훨씬 단축되는 것을 알 수 있다. 이 예시는 i=0...63이고 VLR이 64이므로 벡터 코드에서 별도의 loop가 없었지만, 만약 i가 이보다 커진다면(e.g. i<4096) 벡터 코드에서도 스칼라 코드에서처럼 loop를 돌도록 해야 한다.

벡터 ISA의 특징은 다음과 같다.

• 컴팩트하다. 하나의 짧은 명령어가 N개의 연산을 인코딩할 수 있다.
• expressive하며, 하드웨어에 해당 N개의 명령어들이 다음 특징을 가진다고 알려준다.
  • 독립적, 동일한 functional unit을 사용, disjoint register에 접근, 이전 명령어와 동일한 패턴으로 레지스터 접근, 메모리의 연속적인 블록에 접근(unit-stride load/store), 알려진 패턴으로 메모리 접근(strided load/store)
• scalable하다. 같은 코드를 더 병렬적인 파이프라인(lane)에서 돌릴 수 있다.

 

3. 멀티미디어 SIMD Extensions

SIMD의 가장 널리 사용되는 variation은 SSE/AVX에 기초해 멀티미디어 프로그램의 성능을 향상시키도록 추가되어 오늘날 대부분 마이크로프로세서에서 찾아볼 수 있다.

8 bit +

8 bit +

8 bit +

8 bit +

하나의 넓은 ALU가 병렬적으로 실행될 수 있는 더 작은 여러 ALU로 나뉘어진다. load와 store가 보통 가장 넓은 ALU와 맞먹고, 따라서 같은 데이터 전송은 하나의 32bit value, 2개의 16bit value, 혹은 4개의 8bit value를 전달할 수 있다.

대표적인 SIMD 구현 예시들은 다음과 같다.

• Intel MMX (1996): 8개의 8bit 정수 연산 혹은 4개의 16bit 정수 연산 -> 64bit vector
• Streaming SIMD Extensions(SSE) (1999): 8개의 16bit 정수 연산 / 4개의 32bit 정수/fp 연산 혹은 2개의 64bit 정수/fp 연산 -> 128bit
• Advanced Vector Extensions (2010): 4개의 64bit 정수/fp 연산 -> 256bit 
• AVOX-512 (2017): 8개의 64bit 정수/fp 연산 -> 512bit (vector size == cacheline size)
• 피연산자는 연속적이어야 하고 메모리 위치에 aligned되어야 한다.

 

4. Roofline 성능 모델

peak의 FP throughput을 arithmetic intensity에 대한 함수로 그려, 타겟 머신에 대해 floating point 성능과 메모리 성능을 함께 확인할 수 있도록 한다.

성능 메트릭인 arithmetic intensity는 byte read당 FLOP을 뜻한다.

arithmetic intensity가 높을수록 계산 자원이 병목이고, 낮을수록 메모리 대역폭이 병목이다. 예를 들어 dense matrix는 arithmetic intensity가 O(N)일 때 공간에 대해서는 O(N^2), 시간에 대해서는 O(N^3)이 소요된다(계산 자원이 병목). 반면 sparse matrix는 계산에 대해선 O(1)으로 크게 차지하지 않고 메모리 대역폭이 병목이 된다.

예를 들어, 다음 그래프를 살펴보자. Attainable GFLOPS/sec = Peak Memory BW*ARithmetic Intensity, Peak FP perf

각 그래프에서 꺾이는 지점 기준으로

• 왼쪽: 메모리 대역폭이 병목. idle인 계산자원이 남아있으므로 arithmetic intensity에 대해 성능이 선형적으로 상승한다.
• 오른쪽: arithmetic intensity가 병목. 계산자원을 모두 사용하고 있기 때문에 성능은 saturate되어 더이상 개선되지 않는다.