### Efficient Algorithms for Minimizing Buffer Capacities with Throughput Constraints

Co-authorMohamed benazouz, Olivier Marchetti and Pascal Urard

The design of streaming (e.g. multimedia or network packet processing)
applications must consider several optimizations such as the minimization of
the whole surface of the memory needed on a Chip. The minimum throughput of the
output is usually fixed. In this paper, we present an original methodology to
solve this problem.

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
the capacity. A first polynomial simple algorithm computing the minimum surface
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.