A Mixed Integer Linear Programming formulations for optimizing timing performance during the deployment phase in real-time systems design

Asma Mehiaoui (1) , Tucci-Piergiovanni Sara (1) , Jean-Philippe Babau (2)

1 LISE - Laboratoire d'Ingénierie dirigée par les modèles pour les Systèmes Embarqués
2 Lab-STICC - Laboratoire des sciences et techniques de l'information, de la communication et de la connaissance

Following the standard development methodologies for the real-time systems, the designer has to deploy functions exchanging signals information onto an execution platform. The deployment consists of the three stages i.e. (i) the placement of functions and signals on a distributed network of nodes, (ii) the partitioning of these functions and signals in fixed-priority tasks and messages, respectively, and (iii) the tasks and messages scheduling (i.e. tasks and messages priority assignment). As the design choices at each stage highly influence the timing performance of the system, in the present report, we are interested in supporting designers in their choices during the three stages. To achieve that, we use the Mixed Integer Linear Programming (MILP) technique. Therefore, we first give a MILP formulation which deals with the three stages at the same time; it is called one-step MILP formulation. Then, we face the high complexity of the one-step MILP formulation by decomposing it into two less complex MILP formulations; we call that two-step MILP formulation. The first MILP formulation treats the placement of functions and exchanged signals to nodes and buses, respectively. The second MILP formulation determines the partitioning of functions (resp. signals) in tasks (resp. messages) and assigns priorities to each partition.

Domains: Hardware Architecture [cs.AR]

Asma Mehiaoui, Tucci-Piergiovanni Sara, Jean-Philippe Babau. A Mixed Integer Linear Programming formulations for optimizing timing performance during the deployment phase in real-time systems design. 2012. ⟨cea-00811359⟩