상위수준 합성을 위한 비트단위 지연시간을 고려한 스케줄링

Abstract

Modern VLSI designs get increasingly complex and time-to-market constraints get tighter. Using high level languages is one of the most promising solutions for improving design productivity by raising the level of abstraction. In high level synthesis process, most important step is scheduling. In this paper, we propose fast and efficient scheduling method under timing constraint based on list scheduling, firstly. Experimental results on well known data path intensive designs show fast run times (less than 0.5 sec) and similar results when compared to optimal solutions. Secondly, a new scheduling method considering bit-level delays for high-level synthesis is proposed. Conventional bit-level delay calculation for high-level synthesis was usually limited for specific resources. However, we have developed an efficient bit-level delay calculation method which is applicable to various resources, in this research. This method is applied to scheduling. The scheduling algorithm executes chaining considering bit-level delays. Furthermore, multi-cycle chaining can be allowed to improve performance under resource constraints. Experimental results on several well-known DSP examples show that our method improves the performance of the results by 14.7% on the average. Finally, we extend our scheduling methods to consider memory architecture and memory access by scheduling full search motion estimation of H.264 encoder.; VLSI 공정의 집적도가 향상되고 설계 복잡도가 크게 증가하는 반면 chip의 life cycle은 점점 줄어듦에 따라 기존의 Register Transfer Level (RTL) 기반의 설계방식은 time-to-market을 만족시키기 어렵다. 이에 따라 알고리즘 레벨 (C/C++)로 설계하여 system을 합성하는 상위수준 합성이 등장하였고 오랫동안 연구가 진행되었다. 하지만 매뉴얼 설계에 비해 성능이 떨어지고 다양한 어플리케이션에 적용이 어렵기 때문에 다양한 설계 공간탐색 기법과 빠르고 효율적인 알고리즘의 개발이 필요하다. 본 연구에서는 첫째, 리스트 스케줄링을 기반으로 효과적인 추가 resource 할당 방법을 이용한 빠르고 효율적인 timing constraint하에서의 스케줄링 기법을 제안한다. 실험결과 대부분의 예제에서 Integer Linear Program (ILP)를 이용한 최적 스케줄링 결과와 유사한 결과를 보였다. 둘째, 비트단위 지연시간을 고려한 새로운 스케줄링 기법을 제안한다. 기존의 상위수준 합성을 위한 비트단위 지연시간 계산 방법은 특정 resource에서만 제한적으로 이용할 수 있었다. 하지만 본 연구에서는 다양한 resource에 대해서도 적용할 수 있는 효율적인 비트단위 지연시간 계산 방법을 개발하여, 이를 스케줄링에 적용하였다. 스케줄링 과정에서 비트단위 지연시간을 고려하여 chaining을 수행한다. 또한 resource 제약조건하에서 성능을 더욱 향상시키기 위해 multi-cycle chaining을 수행할 수 있다. 잘 알려진 몇 가지 DSP 예제에 대한 실험 결과는 제안한 방법이 기존의 리스트 스케줄링에 비하여 평균 14.7% 성능을 향상시킬 수 있음을 보인다. 그리고 마지막으로 메모리 구조와 메모리 access를 고려한 스케줄링 기법으로 확장하여 H.264 encoder의 full search motion estimation 예제에 적용한다.