하한 추정을 이용한 휴리스틱 스케쥴링 기법

엄성용, 전주식 · 1993

본 논문에서는 ASAP(As Soon As Possible) 스케쥴링 결과를 초기 상태로 하고, 각 상태에서 한 제어스텝씩 지연할 연산의 선택을 하나의 분기로 하는 탐색 공간을 분기와 한계 방식으로 탐색하면서, 최소의 면적 비용을 갖는 스케쥴링 결과를 찾는 새로운 스케쥴링 기법에 대해 설명한다. 이 방법에서는 각 상태에서 면적 비용이 줄어들기 위해 반드시 지연되어야 할 연산을 적어도 하나 포함하는 최소한의 연산 집합을 추출함으로써 탐색 공간을 축소하는 한편, 하한 추정 기법을 도입하여 불필요한 탐색을 효과적으로 방지함으로써 탐색의 효율을 높인다. 이와 더불어, 최적의 결과를 항상 보장하지는 못하지만 탐색 속도를 더욱 향상시키는 휴리스틱 기법을 사용한다. 새로운 방법의 효율성을 보이기 위해 기존의 연구에서 주로 사용된 몇가지 예에 대한 실험 결과를 제시한다.

Cited by 2 works.

Authors