멀티코어 시스템 설계에서의 파이프라인 스케줄링 최적화 연구

Abstract

많은 연산량을 요구하는 문제를 해결하기 위해, 한 칩 안에 멀티프로세서 시스템이 집적되는 MPSoC (Multi-Processor System-on-Chip)의 사용이 증가하고 있다. MPSoC 아키텍처에 어플리케이션을 매핑하고 태스크를 스케줄링하는 것은 임베디드 시스템의 시스템 레벨 디자인에서 매우 중요한 문제이다. 본 논문에서는, 한 번에 사용자가 정하는 Zone안의 태스크만을 최적화함으로써 빠른 시간 안에 이종 MPSoC 아키텍처의 태스크 매핑과 스케줄링 문제를 해결하는 iterative zone refinement 알고리즘을 소개한다. 이 알고리즘에서는 하나의 Zone안에 포함되는 태스크의 개수를 변경함으로써 수행시간과 솔루션의 quality를 조절할 수 있다. 다양한 크기의 실제 예제와 랜덤 예제를 실험한 결과 제안한 알고리즘을 통해 기존의 잘 알려진 스케줄링 알고리즘인 Performance Effective Task Scheduling (PETS), Heterogeneous Earliest Finish Time (HEFT), Critical-Path-On a Processor (CPOP), Look-ahead technique를 사용한 Task Duplication (DUP/LA) 알고리즘보다 더 뛰어난 결과를 얻을 수 있었다.