Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Mapping task-graphs on distributed ECU networks: Efficient algorithms for feasibility and optimality
 
conference paper

Mapping task-graphs on distributed ECU networks: Efficient algorithms for feasibility and optimality

Damm, Werner
•
Metzner, Alexander
•
Eisenbrand, Friedrich  
Show more
2006
Proceedings - 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2006

This mapping problem has to be solved in many application scenarios. In the automotive industry, for example, the implementation of car functions involves distributed task sets running on multiple electronic control units (ECU) with bus-based inter-task communication, a problem we consider in this paper. Our approach is based on mixed integer linear programming (MILP). MILP is concerned with optimizing a linear function subject to a set of linear constraints where some variables are required to be integer. The current state-of-the art method to solve integer programs is the branch-and-cut (B&C) algorithm and several industrial strength solvers are available. We describe a MILP-model for the mapping problem. Handling this model over to a general MILP-solver does not yield satisfactory results in terms of running time. To make the model more efficient we use the above ingredients: we incorporate a primal heuristic, strengthen the model with further inequalities and generate on-demand cutting planes, which violate the current fractional solution. These routines drastically speed up the solution time

  • Details
  • Metrics
Type
conference paper
DOI
10.1109/RTCSA.2006.42
Author(s)
Damm, Werner
Metzner, Alexander
Eisenbrand, Friedrich  
Shmonin, Gennady
Wilhelm, Reinhard
Winkel, Sebastian
Date Issued

2006

Published in
Proceedings - 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, RTCSA 2006
Start page

87

End page

90

Written at

OTHER

EPFL units
DISOPT  
Available on Infoscience
May 13, 2008
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/23720
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés