hardware optimization이 일어나는 원리 locality of reference

1. hardware specific optimization

 

deep learning model의 compile과정에서 backend단에서 target hardware에 맞춰가는 optimization을 위해 여러가지 방법들이 사용

 

hardware intrinsic mapping, memory allocation & fetching, loop oriented optimization techniques, parallelization 등등

 

여러가지 hardware specific optimization 개략적인 그림

 

 

loop oriented optimization technique는 직관적으로 이해하기 쉬운데 loop fusion은 겹치는 loop를 하나로 합치는 것일테고

 

reordering은 loop 순서를 바꾸는 것일테고 unrolling은 loop를 풀어서 하나하나 실행되게 만드는 것

 

slide window는 outer loop와 inner loop사이에 sliding window를 넣어서

 

inner loop가 돌 때 window안에 데이터를 저장해놓고 필요없을 때까지 재사용하는 방법이라는데…

 

tiling은 outer loop를 tile단위로 나누고 그 tile안에서 inner loop가 돌아가는데

 

여기에 사용하는 데이터를 cache에 미리 저장한 데이터로 fitting시켜서 사용한다는데

 

parallelization은 병렬처리가 안되는 복잡한 loop를 적절하게 끊어서 병렬처리가 되도록 만드는 방법

 

내 생각에는 이런 것들이 와닿지가 않음..

 

그냥 deep learning model들이 compiler backend단에서 hardware에 맞춰지는 optimization과정에 사용되는 방법이 여러가지가 있다… 이 정도로 끝내면 될듯??

 

 

2. polytope method

 

outer loop와 inner loop가 혼합된 다중 loop는 inner loop가 outer loop를 참고해야하므로 보통은 병렬처리가 안된다

 

그래서 polytope method의 transformation을 이용해 loop를 풀어서 병렬처리가 되게 만든다

 

 

 

알고리즘에서도 가능한거 아냐?

 

 

3. locality of reference

 

hardware optimization 과정들이 왜 수행되는가?에 대한 근본적인 원리?

 

사람들이 memory나 cache에 있는 데이터를 뽑아쓰다가 어떤 pattern을 발견하였는데

 

‘a program spends 90% of its time in 10% of its code’

 

프로그램은 코드의 10%에 90%의 시간을 소비하더라

 

자주쓰는 코드는, 자주쓰는 데이터는 계속 자주쓰게 된다

 

1) temporal locality

 

한번 썼던 데이터는 이후에도 짧은 시간안에 다시 쓸 가능성이 높다

 

2) spatial locality

 

내가 어떤 메모리 공간에 저장된 데이터를 한번 참고했다면 짧은 시간안에 그 데이터와 가까운 곳에 있는 데이터를 또 다시 참고하게 된다

 

내가 무언가 참고하기위한 데이터를 그것만 가져와서 메모리나 cache에 올리는 것은 상당히 비효율적

 

그 데이터와 비슷한 위치의 데이터들을 모두 batch로 memory에 올려서 사용한다면 전체적인 memory access를 덜하게 된다는 의미

 

3) branch locality

 

loop를 돌거나 할 때 현재 point에서 if~ then~문(conditional branch instruction)에 의한 branch가 뻗어나가는 branch의 개수는 현재 point에 dependent하더라

 

condition에 의한 분기로 branch가 생성될 때 무한하게 생성되는 것이 아니라 현재 point에 의한 제약이 걸려 branch가 생성된다.

 

그래서 이 branch 범위를 미리 예상하여 그 안에서 데이터를 미리 가져온다면 효율적이다.

 

4) equidistant locality

 

for loop같은 것을 돌 때 메모리적으로 거리가 있는 step이더라도 일괄적으로 데이터를 균등하게 가져오는 pattern이 관찰될 수 있다.

 

simple linear function으로 현재 이 곳을 참조했다면 다음에 참조할 곳을 높은 가능성으로 예측할 수 있다는 의미

 

CPU가 필요하기전에 미리 예측하여 cache에 데이터를 담아둔다면

 

진짜로 그 요청이 있을 때 그냥 바로 가져오면 되니까 접근을 덜 할 수 있어서 메모리 절약이 가능하다

 

locality를 직관적인 그림으로 나타냄

 

 

dd