A new approach for minimizing buffer capacities with throughput constraint for embedded system design

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.