Search

This Deliverable 5.1 contains the design and a description of the work undertaken to combine and integrate the engaged software (SUMO, ns3, iCS, PHEM, ...) to suite the investigation tasks of the COLOMBO project. Requirements from the traffic management solutions to be developed in COLOMBO put on the overall simulation system have been collected. They are given in D5.1 together with short explanations about the implementation of the solutions using the COLOMBO suite of simulation applications. Both the components of the simulation system as well as the system’s architecture are described. Additionally, the software development process in COLOMBO is also described in the document.

In this paper we introduce a complex allocation and scheduling problem for variable voltage Multi-Processor System-on-Chip (MPSoC) platforms. We propose a methodology to formulate and solve to optimality the allocation, scheduling and discrete voltage selection problem, minimizing the system energy dissipation and the overhead for frequency switching. Our approach is based on the Logic Benders decomposition technique where the allocation is solved through an Integer Programming solver, and the scheduling through a Constraint Programming solver. The two solvers are interleaved and their interaction regulated by cutting plane generation. The objective function depends on both master and sub-problem variables. We demonstrate the efficiency of our approach on a set of realistic instances.

Most problems addressed by the software optimization flow for multi-processor systems-on-chip (MPSoCs) are NP-complete, and have been traditionally tackled by means of heuristics and high-level approximations. Complete approaches have been effectively deployed only under unrealistic simplifying assumptions. We propose a novel methodology to formulate and solve to optimality the allocation, scheduling and discrete voltage selection problem for variable voltage/frequency MPSoCs, minimizing the system energy dissipation and the overhead for frequency switching. We integrate the optimization and validation steps to increase the accuracy of cost models and the confidence in quality of results. Two demonstrators are used to show the viability of the proposed methodology.

The purpose of this introductory chapter is to provide the basic concepts behind Constraint Programming CP and Integer Programming IP. These two fields cover a variety of aspects and have been widely studied. Therefore, here we do not intend to give a deep insight of the fields, but to provide the definitions and concepts for understanding the rest of this book. We explain CP and IP modelling aspects and solving strategies. We ground our discussion on an example: the car sequencing problem. The chapter provides references to relevant biography which can be referred to for a deeper understanding.

In this chapter, we present the integration of various forms of problem relaxation in Constraint Programming (CP). The main motivation for the integration proposed concerns the introduction in CP languages of some form of {em optimality reasoning}. Indeed, CP languages provide effective and powerful tools for reducing the search space of the problem by removing infeasible values. However, they barely consider the problem objective function and implement a naive form of branch-and-bound which poorly reduces the search space to be explored. % Relaxations can be integrated in CP in different ways. Some approaches propose to automatically translate the whole CP program in linear form, while some other focus only on global constraints. In this perspective, a further differentiation can be noted. Some approaches translate all global constraints in a unique linear store, while others embed an optimization component within each global constraint. In other approaches, the part of the problem to be relaxed is decided by the user that explicitly states it in the program. First, we provide an introduction on different kinds of relaxation and we discuss many integration approaches, how they exploit results coming from the relaxation, providing references to related bibliography. In the second part of the chapter, we consider global constraints as suitable software components to integrate relaxations in CP. We discuss, as a case study, a particular global constraint, the path constraint, and show different relaxations and their tightness.