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:
https://lup.lub.lu.se/record/307955
- author
- Kuchcinski, Krzysztof
LU
- organization
- publishing date
- 2003
- 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
- Association for Computing Machinery (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
- 2016-04-01 15:53:09
- date last changed
- 2022-04-22 18:05:30
@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}},
keywords = {{resource assignment; high-level synthesis; constraint programming; design; experimentation; scheduling; system-level synthesis}},
language = {{eng}},
number = {{3}},
pages = {{355--383}},
publisher = {{Association for Computing Machinery (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}},
doi = {{10.1145/785411.785416}},
volume = {{8}},
year = {{2003}},
}