Constraints-driven scheduling and resource assignment
Open Access
- 1 July 2003
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Design Automation of Electronic Systems
- Vol. 8 (3) , 355-383
Abstract
This paper describes a new method for modeling and solving different scheduling and resource assignment problems that are common in high-level synthesis (HLS) and system-level synthesis. It addresses assignment of resources for operations and tasks as well as their static, off-line scheduling. Different heterogeneous constraints are considered for these problems. These constraints can be grouped into two classes: problem-specific constraints and design-oriented constraints. They are uniformly modeled, in our approach, by finite domain (FD) constraints and solved using related constrained programming (CP) techniques. This provides a way to improve quality of final solutions. We have developed in Java a constraint solver engine, JaCoP ( Ja va Co nstraint P rogramming), to evaluate this approach. This solver and a related framework make it possible to model different resource assignment and scheduling problems, and handle them uniformly. The JaCoP prototype system has been extensively evaluated on a number of HLS and system-level synthesis benchmarks. We have been able to obtain optimal results together with related proofs of optimality for all HLS scheduling benchmarks and for all explored design styles (except one functional pipeline design). Many system-level benchmarks can also be solved optimally. For large randomly generated task graphs, we have used heuristic search methods and obtained results that are 1--3% worse than lower bounds or optimal results. These experiments have proved the feasibility of the presented approach.Keywords
This publication has 16 references indexed in Scilit:
- Constraints-driven design space exploration for distributed embedded systemsJournal of Systems Architecture, 2001
- A formal approach to context scheduling for multicontext reconfigurable architecturesIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 2001
- Incorporating speculative execution into scheduling of control-flow-intensive designsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2000
- Partitioning and pipelining for performance-constrained hardware/software systemsIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 1999
- COSYN: Hardware-software co-synthesis of heterogeneous distributed embedded systemsIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 1999
- System Synthesis with VHDL1998
- A solution methodology for exact design space exploration in a three-dimensional design spaceIEEE Transactions on Very Large Scale Integration (VLSI) Systems, 1997
- Dynamic critical-path scheduling: an effective technique for allocating task graphs to multiprocessorsIEEE Transactions on Parallel and Distributed Systems, 1996
- Extending chip in order to solve complex scheduling and placement problemsMathematical and Computer Modelling, 1993
- An Algorithm for Solving the Job-Shop ProblemManagement Science, 1989