Throughput optimization for pipeline workflow scheduling with setup times

In this paper, we tackle pipeline workflow applications that are executed on a dis- tributed heterogeneous platform with setup times. In such applications, several computation stages are interconnected as a linear application graph. The considered stage/processor mapping strategy is based on interval mappings, where an interval of consecutive stages is performed by the same processor. Each stage holds a buffer of limited size where intermediate results are stored and a setup time occurs when passing from one stage to another. Typical examples for this kind of applications are streaming applications such as audio and video coding or decoding, image pro- cessing using co-processing devices as FPGA. In this paper, we focus on throughput optimization. This problem is known to be NP-hard as soon as heterogeneous processors are used, even without setup times and with homogeneous communication links. We provide an optimal algorithm for the inner-processor scheduling of stages on homogeneous platforms with identical buffer capacities. We also provide an interval mapping that, when running the former algorithm including all processors, maximizes the throughput of the application. Last, we deal with the problem of allocating the buffers for each stage in shared memory. We provide an optimal algorithm for buffer allocation in the case where the memory may be split evenly, and we propose heuristics to handle any remainder in the memory allocation