A new approach for minimizing buffer capacities with throughput constraint for embedded system design
Mohamed Benazouz, Olivier Marchetti, Alix Munier-Kordon, Pascal Urard · 2010
The design of streaming applications (e.g. multimedia or network packet processing) must consider several optimizations such as the minimization of the whole surface of the memory needed on a Chip. The problem tackled in this paper is the minimization of the whole surface of the memory needed to reach a minimum fixed throughput. The application is modelled using a Marked Timed Weighted Event Graphs (in short MTWEG), which is a subclass of Petri nets. Transitions correspond to specific treatments and places model buffers for data transfers. It is assumed that transitions are periodically fired with a fixed throughput. The problem is first mathematically modelled using an Integer Linear Program. We then study for a unique buffer the optimum throughput according to its capacity. A polynomial simple algorithm that minimizes the overall surface of memory for a fixed throughput is derived when there is no circuit in the initial MTWEG, which corresponds to a wide class of applications. We prove in this case that the capacities of every buffer may be optimized independently. For general MTWEG, the problem is NP-Hard and an original polynomial 2-approximation algorithm is presented. For practical applications, the solution computed is very close to the optimum.