鬆弛時間最佳化之運算排序

A Formal Approach to the Slack Driven Scheduling Problem in High Level Synthesis

程駿華(Chun-Hua Cheng)

指導教授 ： 黃世旭

中原大學/工學院/電子工程研究所/碩士(2005年)

https://doi.org/10.6840/cycu200500329

摘要

隨著深次微米世代的來臨, 在高階合成上我們必須對設計目標可否收斂的問題多加考量。先前的研究顯示，有效地利用鬆弛時間 (slack)，可以容忍運算元在製程上時間延遲的變異。這篇文章中，我們建議用整線性規劃 (ILP) 方法解決鬆弛時間導向的排序問題。我們的目標在時間和資源的設計條件考量下，把所有可用的鬆弛時間達到最大有效的運用。和之前的研究相比，我們的方法有下列兩個優點:第一，我們的方法保證是最佳的解。第二，我們的方法更適用於 design space exploration。

關鍵字

高階合成 ； 排序 ； 鬆弛時間最佳化與整數線性規劃 ； 設計收斂

並列摘要

With the advent of deep sub-micron era, there is a growing need to consider the design closure problem in high-level synthesis. Previous work has shown that the slack (in terms of the number of clock cycles) is an effective means of tolerating variations in operation delays. In this paper, we propose an integer linear programming (ILP) approach for the slack driven scheduling problem. Our objective is to maximize the total useable slack under the design constraints (timing and resource). Compared with previous work [4], our approach has the following two advantages: first, our approach guarantees the optimality; secondly, our approach is more suitable for the design space exploration.

並列關鍵字

High-Level Synthesis ； Design Closure ； Scheduling ； Slack Optimization and Integer Linear Programming

參考文獻

[3] P. Faraboschi, J.A. Fisher and C. Young, “Instruction Scheduling for Instruction Level Parallel Processors”, Proc. of the IEEE, vol. 89, no. 11, pp. 1638—1659, 2001.

[6] C.A. Papachristou and H. Konuk, “A Linear Program Driven Scheduling and Allocation Method Followed by an Interconnect Optimization Algorithm”, Proc. of IEEE/ACM Design Automation Conference, pp. 77—83, 1990.

[8] M. Balakrishnan and P. Marwedel, “Integrated Scheduling and Binding: A Synthesis Approach for Design Space Exploration”, Proc. of IEEE/ACM Design Automation Conference, pp. 68—74, 1989.

[10] S. H. Huang, C.T. Hwang, Y.C. Hsu, and Y. J. Oyang, “A New Approach to Schedule Operations across Nested-ifs and Nested-loops”, Proc. of IEEE/ACM International Symposium on Micro-architecture, pp. 268—271, 1992.

[12] R. Cloutier and D. Thomas, “The Combination of Scheduling, Allocation and Mapping in a Single Algorithm”, Proc. of IEEE/ACM Design Automation Conference, pp. 71—76, 1990.