Systolic Array

목적 

1. Simple, regular design

2. High concurrency으로 인한 High performance달성

3. Balanced computation and I/O memory bandwidth

 

아이디어 

- a single processing element (PE)를 regular array of PEs로 대체하고 PE 사이의 data flow를 조율할 수 있음

 

systolic system의 기초적인 요소

- Data는 rhythmical한 방식으로 흐르며, 메모리로 돌아오기 전에 많은 처리 요소들을 통과한다.

- 피의 흐름이 심장, 세포를 거쳐 다시 심장으로 오는데 다른 세포들이 혈액을 'process'하는 방식과 유사하며

- 정맥이 simultaneously하게 작동하는 것과 같다.

- pipelining방식과 다른 점은 이는 individual PE방식인데다가 Array 구조가 non-linear하고 multi-dimensional하다는 것이다.

- 그리고 PE connection들이 multidirectional하고 각기 다른 속도로 처리한다.

- PE는 명령어 방식이 아닌, local memory와 execute kernel을 갖는다.

 

Systolic Computation Example

1. Convolution은 filtering, pattern matching, correlation, polynomial evaluation을 활용하는 모델

Systolic Array에서 Convolution 되는 과정

Systolic Array에서 Convolution 되는 과정

- data element들이 Array에 입력으로 들어갈때 Systolic은 element들을 조율한다.

- output이 찻을 때 Array dimensionality는 증가하고 PE는 latency관점에서 unpredictable하다

- Systolic array는 chain형태로 결합되는데 이는 powerful한 system을 형성한다.

 

Systolic Array의 장점

1. 제한된 메모리 대역폭을 I/O대역폭과 computation사이를 효율적으로 조율한다.

2. 적은 메모리 대역폭으로 좋은 성능을 낼 수 있다.

 

Systolic Array의 단점

1. not generally application

 

-  Systolic Array에서 각 PE는 weight를 저장하고 implementation하기 쉽다.

- 각 PE는 자기만의 data와 instruction memory를 갖는다.

- 이는 stream processing과 pipeline parallelism를 야기한다.

 

 

Pipeline-parallel program

- Loop iteration은 stage라 불리는 code segment로 나뉜다. 

- Threads는 다른 코드에서 stage를 실행한다.

- Systolic Array의 예시 : Warp computer, TPU

 

 

Decoupled Access/Execute

 

(차후에 다시 정리)

 

Branch를 제거하기 위한 Loop Unrolling

- loop body를 반복문 안에서 여러번 반복한다.

- loop maintenance overhead를 줄인다

- basic block를 증가시키고 이는 code optimization과 scheduling을 가능하게 한다.

- 만약에 iteration count가 unroll factor와 나눠떨어지지 않으면 이를 감지하는 코드가 추가로 필요하다