2021. 6. 30. 23:54ㆍReview
Published online: 19 Jaunary 2013
@ Springer Science+Businiess Media New York 2013
논문 링크 : https://link.springer.com/article/10.1007/s11227-013-0870-6
너무 오랜만에 글을 쓰는것 같다. 우선, 이번 3학년 1기를 마친 시점 이고 꽤 잘 보냈던것 같다.
이번 학기에 리눅스 시스템 프로그래밍 과목을 재미있게 들으면서, 가장 재미있게 했던 과제가 있다.
링크 : https://github.com/Ju-nic2/LinuxSystemPrograming/tree/branch1
이걸 직접 해보며 수행 시간 단축, 컴퓨터 시스템에도 관심이 가고 좀더 알아보고 싶었다.
혼자 찾긴 어려워 논문 하나를 추천 받았다.
아직 많이 부족하지만 교수님이 소개해 주신 논문을 읽어보며 정리해 보려 한다.
단순 소개로 받은 논문이지만 처음으로 읽어보는 것이라. 뭐 하나라도 남겨 가고 싶은 마음이다.
현재 수준에서 읽었을 때와, 좀더 공부 하고 다시 읽어봤을때의 시각 차이를 경험해 보고 싶다.
주제를 소개하기전 간략히 논문의 Background를 요약해 보겠다.
Scheduling shemem 은 2가지 단계가 있다고 한다.
1. application selection
실행될 application 선택하는 단계이다.
2. device selection
실행 할 device를 선택한다.
이 논문에선 1. 을 First-Come, First-Serve (FCFS) 방식에관한
CPU vs GPU Schedulig scheme만을 다룬다.
먼저 기본 3가지를 소개한다.
- Alternate-Assignment(AA)
단순히 두 device에 번갈아 가며 application을 실행한다.
- First-Free(FF)
두 device중 먼저 idle 상태가 되는걸 선택하여 실행한다.
- Performance History(PH)
실행 시간 기록 정보를 file system으로 부터 얻어 실행할 device 를 선택한다.
이떄 ratio = Execute Time on CPU/ Execute Time on GPU 값을 이용하여 device 가 결정 된다.
:AA,FF 와는 달리 PH는 꽤 적절한 방법이라 생각했다.
하지만 저자는 각 device 의 Remaining Time 을 고려하지 않는다면 over,unter - utilization이 일어나
시스템 performance 저하를 일으킨다고 한다.
왜 그런진 잘 모르겠지만. 그래픽 카드가 없거나, 작은 노트북 에서 과한 프로그램을 돌린다면
갑자기 컴퓨터가 멈추거나, 느려지는 현상을 떠올려 이해해 보려 한다.
저자가 제시한 Scheduling 기법을 다루어 보자.
Estimated Executin Time (EET) 라고 한다.
저자는 위 PH 방식의 단점을 보안한 방식을 제안했다.
EET 방식은 Executin history time tlabe 에 더해서 Remaining time table 을 가지고 동작한다.
각 Table은 CPU, GPU가 모두 1개씩 가지고 있다.
1. Execution history time table
6개 entriy를 가진다. TaskName, Size, Count , Sum, Average, Lifetim.
TaskName - app 이름, Size - input data 크기, Count - 실행 횟수, Sum - 실행시간 총합 Average - 실행시간 평균, Lifetime- data 유효시간
이 Table 은 TaskName, Size 로 indexing 되어 있다.
application 이 CPU,GPU 사이에 선택될 때 각 table에 동시에 접근하여 Average Time을 가져온다.
: 이 논문에선 input data type은 다루지 고려하지 않는다. 보통은 실행할 application의 특성에 따라 어느정도 유추할 수 있기 때문일것 같다. 또한 각 table에 남겨진 time 정보에서도 어느정도 구분되기 때문에 따로 고려햐진 않은것 같다.
2. Remaining time table
여기엔 오직 1개의 entry 만 존제 한다.
해당 device에 가장 최근에 실행된 application의 실행 시간만 담긴다.
Remaining time table의 data를 다루는 방법은 다음과 같다
1. application을 실행할 device가 결정되면
2. entry는 history table를 이용하여 update 된다.
3. 이과정이 끝나면 각 device 의 remaining time 이 1초씩 감소한다.
: 1,2,3 의 remaining time 관리 방식으로 인해 PH방식의 utilization문제를 해소할 수 있을것 이다.
위 Table을 이용하여 estimated CPU/GPUTime을 구한다.
estimated CPU/GPUTime = remainginCPU/GPUTime + CPU/GPUTime(from history table)
estimated CPU/GPUTime을 이용하여 device를 선택 할땐 3가지 경우로 나눈다.
1. estimated GPUTime <= estimated CPU/Time * (treshold value) 일때
2. 두 time 정보가 얼마 차이 안날때 - First-Free방식으로 선택
3. estimated CPU/Time <= estimated GPUTime * (treshold value) 일때
저자는 직접 test를 통해 treshold value (임계값)을 0.5를 제시 하였다.
: 임계값 까지 이용한 결과값이 단순 estimated Time 보다 작다면 확실히 빠른 수행을 보장할 것이라 생각한다.
1번비교 먼저 수행하는 이유는 GPU 의 강력한 병렬처리 능력을 이용하면 GPU, CPU 의 수행시간 차이가 생각보다 크다. 이를 이용하여 최대한 빠른 수행으로 유도하기도 하고. 확실하게 CPU를 이용했을때 더 빠른 결과를 얻을 수 있는 상황에선 CPU를 이용하기 위함인것 같다.
이 방식의 단점으로는 Table에 data가 어느정도 쌓기지 전까진 해당 방식의 장점을 얻을 수 없다는 것이다.
저자는 어느정도 data가 쌓이기 전까진 FF 방식을 이용한다고 한다.
다음 포스팅에는 Experiments 부분을 정리해보려 한다.