Name
Title | ||
|---|---|---|
An in-place search algorithm for the resource constrained scheduling problem during high-level synthesis |
Abstract | ||
|---|---|---|
We propose an in-place search algorithm for computing the exact solutions to the resource constrained scheduling problem. This algorithm supports operation chaining, pipelining and multicycling in the underlying scheduling problem. Based on two lower-bound estimation mechanisms that are capable of predicting the criterion values of search nodes represented by partially scheduled data flow graphs, the proposed algorithm can effectively prune the nonpromising search space and finds the optimum usually several times faster than existing techniques. As opposed to existing search-based scheduling techniques whose space complexity is squared or exponential in the search depth, our approach requires only a constant storage space during the traversal of the search tree. The low space complexity is accomplished by using a combination-generating algorithm, which leads our approach to visit search nodes in such a way that each one is obtained by making only a small change to its sibling without keeping any parent nodes in memory. Experimental results on several well known benchmarks with varying resource constraints show the effectiveness of the proposed algorithm. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1145/1835420.1835422 | ACM Trans. Design Autom. Electr. Syst. |
Keywords | Field | DocType |
high-level synthesis,constant storage space,search tree,search depth,low space complexity,nonpromising search space,proposed algorithm,design automation,exact scheduling,resource-constrained scheduling,optimal scheduling,search node,combination-generating algorithm,space complexity,in-place search algorithm,exact solution,search space,generic algorithm,high level synthesis,data flow graph,lower bound,search algorithm,scheduling problem | Mathematical optimization,Search algorithm,Fair-share scheduling,Min-conflicts algorithm,Computer science,Beam search,Bidirectional search,Dynamic priority scheduling,Best-first search,Iterative deepening depth-first search | Journal |
Volume | Issue | ISSN |
15 | 4 | 1084-4309 |
Citations | PageRank | References |
4 | 0.43 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sheng-De Wang | 1 | 720 | 68.13 |
| Sheng-De Wang | 2 | 720 | 68.13 |
| Yi-Hsin Wu | 3 | 4 | 1.11 |