Optimized Mapping of Pipelined Task Graphs on the Cell BE
Christoph W. Keßler · 2009
Abstract. Limited bandwidth to off-chip main memory poses a problem in chip multiprocessors for streaming applications, such as Cell BE, and will become more severe with the expected increase in the number of cores. Especially for streaming computations where the ratio between computational work and memory transfer is low, the generation of memory-efficient code is thus an important compiler optimization. We suggest to use pipelining between the SPEs over the high-bandwidth internal bus of Cell BE to reduce the required main memory bandwidth, and thereby improve the computation throughput for memory-intensive computations. At the same time, we are constrained by the limited size of SPE on-chip memory available for additional buffers that are necessary for the pipelining between SPEs. We investigate mappings of the nodes of a pipelined parallel task graph to the SPEs that are optimal trade-offs between load balancing, buffer memory consumption, and communication load on the on-chip bus. We solve this multiobjective optimization problem by deriving an integer linear programming (ILP) formulation and compute Pareto-optimal solutions for the mapping with a stateof-the-art ILP solver. For larger problem instances, we sketch a two-step approach to reduce problem size. We exemplify our mapping technique with several memory-intensive example problems: with acyclic pipelined task graphs derived from data parallel code, with complete d-ary tree pipelines for parallel mergesort on Cell BE, and with butterfly pipelines for parallel FFT on Cell BE. We validate the mappings with discrete event simulations. 1