Advanced

Constraints-driven scheduling and resource assignment

Kuchcinski, Krzysztof LU (2003) In ACM Transactions on Design Automation of Electronic Systems 8(3). p.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 ( Java... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
resource assignment, high-level synthesis, constraint programming, design, experimentation, scheduling, system-level synthesis
in
ACM Transactions on Design Automation of Electronic Systems
volume
8
issue
3
pages
355 - 383
publisher
ACM
external identifiers
  • wos:000183884800005
  • scopus:0042745479
ISSN
1084-4309
DOI
10.1145/785411.785416
language
English
LU publication?
yes
id
2682b119-6735-446d-b511-a43ca52025bd (old id 307955)
date added to LUP
2007-09-16 10:37:14
date last changed
2018-08-05 04:06:03
@article{2682b119-6735-446d-b511-a43ca52025bd,
  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 ( 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.},
  author       = {Kuchcinski, Krzysztof},
  issn         = {1084-4309},
  keyword      = {resource assignment,high-level synthesis,constraint programming,design,experimentation,scheduling,system-level synthesis},
  language     = {eng},
  number       = {3},
  pages        = {355--383},
  publisher    = {ACM},
  series       = {ACM Transactions on Design Automation of Electronic Systems},
  title        = {Constraints-driven scheduling and resource assignment},
  url          = {http://dx.doi.org/10.1145/785411.785416},
  volume       = {8},
  year         = {2003},
}