Paper Info
Title
Heuristic algorithm for the resource constrained scheduling problem during high-level synthesis.
Abstract
Scheduling is considered the most important task in a high-level synthesis process. A heuristic algorithm based on the A* search to find optimal schedules quickly is presented. This algorithm reduces the computational effort required to obtain the best schedules on a pre-defined datapath by effectively pruning the non-promising search space. The pruning method is accomplished by an admissible heuristic that estimates the schedule length, or the cost, of a search node represented by a partially scheduled data flow graph. The search node with the least cost is considered the most promising candidate and is expanded next, avoiding an exhaustive search of the problem space. When the costs of the candidate search nodes are identical, the A* search is guided by a depth-first search to speed up the computation. Experimental results on several well known benchmarks with varying resource constraints show the effectiveness of the proposed algorithm. Multicycle, pipelined and chaining execution of operations are supported.
Year
DOI
Venue
2009
10.1049/iet-cdt:20070162
IET Computers & Digital Techniques
Keywords
DocType
Volume
data flow graphs,scheduling,search problems,A* search,data flow graph,heuristic algorithm,high-level synthesis,pruning method,resource-constrained scheduling
Journal
3
Issue
ISSN
Citations 
1
1751-8601
0
PageRank 
References 
Authors
0.34
15
3
Name
Order
Citations
PageRank
Yi-Hsin Wu141.11
Cheng-Juei Yu200.34
Sheng-De Wang372068.13