Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Minimizing makespan under data prefetching constraints for embedded vision systems: a study of optimization methods and their performance

Khadija Hadj Salem 1 Vincent Jost 2 Yann Kieffer 3 Luc Libralesso 4 Stéphane Mancini 5
2 G-SCOP_ROSP - Recherche Opérationnelle pour les Systèmes de Production
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
4 G-SCOP_OC - Optimisation Combinatoire
G-SCOP - Laboratoire des sciences pour la conception, l'optimisation et la production
5 CDSI - Circuits, Devices and System Integration
TIMA - Techniques de l'Informatique et de la Microélectronique pour l'Architecture des systèmes intégrés
Abstract : The design of embedded vision systems, in confronting the "Mem-ory Wall", exhibits many challenges, regarding for example design cost, energy consumption and performance. This paper considers a variant of the Job Shop Scheduling Problem with tooling constraints, arising in this context, in which the completion time (makespan) is to be minimized. This objective corresponds to the performance of the produced circuit. Given a set of tasks and a set of prerequisites, this class of problem aims to schedule all the tasks. Each task can be processed if all its prerequisites (a specific subset of prerequisites) are loaded in the buffers and stay available during its whole operation. We discuss different formulations using integer linear programming and point out its characteristics, namely the size and the quality of the linear programming relaxation bound. To solve this scheduling problem with large size, we compare three sets of approaches including a Constraint Programming, two constructive greedy heuristics (published in previous work), two models of LocalSolver, a Simulated Annealing algorithm and Beam Search algorithm. Numerical experiments are conducted on 16 benchmark instances from the literature as well as on 12 real-life non-linear image processing kernels for validating their efficiency.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

https://hal.archives-ouvertes.fr/hal-03010229
Contributor : Khadija Hadj Salem <>
Submitted on : Tuesday, November 17, 2020 - 4:00:48 PM
Last modification on : Tuesday, February 2, 2021 - 3:27:35 PM
Long-term archiving on: : Thursday, February 18, 2021 - 7:57:30 PM

File

K.HADJ SALEM et al._ORIJ 2020....
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03010229, version 1

Citation

Khadija Hadj Salem, Vincent Jost, Yann Kieffer, Luc Libralesso, Stéphane Mancini. Minimizing makespan under data prefetching constraints for embedded vision systems: a study of optimization methods and their performance. inPress. ⟨hal-03010229⟩

Share

Metrics

Record views

106

Files downloads

56