A solution to the data re-ordering problem for multi-pipeline streaming applications on clustered MPSoC

We consider streaming applications modeled as a set of coarse-grained parallel threads. Their Task and Communication Graph (TCG) can contain pipeline or task farm parallelism, or any combination of both. Applications can be written in the form of several parallel pipelines. Data are potentially read and forwarded in an arbitrary order by a task which joins the streams having passed through the pipelines; such out-of-order arrival is unacceptable in video streaming. Mapping a multi-pipeline TCG on a clustered multi processor system-on-chip, where memory access latency varies strongly, further aggravates the problem. We present several methods to re-establish the order between data items; all these methods use a so-called merge task. This task employs an order re-establishing algorithm which uses a re-ordering buffer, initially described for telecommunication applications. The algorithm discards, on entering the re-ordering buffer, data items arriving too early or too late; it thus guarantees minimal buffer space. Preliminary experimental results are given for a multi-pipeline Motion JPEG decoder.