Name
Abstract | ||
|---|---|---|
Heuristics are widely used for solving computational intractablesynthesis problems. However, until now, there has been limitedeffort to systematically develop heuristics that can be applied to avariety of synthesis tasks. We focus on development of generaloptimization principles so that they can be applied to a wide rangeof synthesis problems. In particular, we propose a new way torealize the most constraining principle where at each step wegradually relax the constraints on the most constrained elementsof the solution. This basic optimization mechanism is augmentedwith several new heuristic principles: minimal freedom reduction,negative thinking, calibration, simultaneous step consideration,and probabilistic modeling.We have successfully applied these optimization principles to anumber of common behavioral synthesis tasks. Specifically, wedemonstrate a systematic way to develop optimization algorithmsfor maximum independent set, time-constrained scheduling, andsoft real-time system scheduling. The effectiveness of theapproach and algorithms is validated on extensive real-lifebenchmarks. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1109/ICCAD.2003.78 | Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design |
Keywords | Field | DocType |
scheduling,maximum independent set,real time systems,probabilistic model | Heuristic,Mathematical optimization,Fair-share scheduling,Computer science,Real-time computing,Two-level scheduling,Theoretical computer science,Heuristics,Rate-monotonic scheduling,Probabilistic logic,Dynamic priority scheduling,Round-robin scheduling | Conference |
ISBN | Citations | PageRank |
1-58113-762-1 | 1 | 0.36 |
References | Authors | |
24 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zhiru Zhang | 1 | 1020 | 71.74 |
| Yiping Fan | 2 | 456 | 25.67 |
| Miodrag Potkonjak | 3 | 6392 | 709.11 |
| Jason Cong | 4 | 7069 | 515.06 |