The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Constraints-driven scheduling and resource assignment

På svenska

Author

  • Krzysztof Kuchcinski

Summary, in English

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 ( Java Constraint Programming), 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.

Publishing year

2003

Language

English

Pages

355-383

Publication/Series

ACM Transactions on Design Automation of Electronic Systems

Volume

8

Issue

3

Document type

Journal article

Publisher

Association for Computing Machinery (ACM)

Topic

  • Computer Science

Keywords

  • resource assignment
  • high-level synthesis
  • constraint programming
  • design
  • experimentation
  • scheduling
  • system-level synthesis

Status

Published

ISBN/ISSN/Other

  • ISSN: 1084-4309