Polynomial time approximation scheme for efficient execution of stream graphs on multicores

Abstract

As the multicore processor architectures have become the industry standard, the importance of stream programming paradigm demands more attention nowadays. Stream programming languages are designed to utilize the efficiency of parallel platforms. A stream program operates on a large stream of data where independent actors perform different functions. A stream graph representing a stream program consists of actors and their communication edges. Allocating actors of stream graphs on multicores is a major problem in this context. Integer Linear Programming (ILP) based approaches for the actor allocation problem provide the best quality of solutions, but they are impractical as an ILP solver could take exponential time to provide a solution. Heuristics based approaches often provide very good solutions and often fail to do so, resulting in a poor performance guarantee on the quality of the solution. Approximation algorithm based approaches run in polynomial time and have quality bound on the solution.

In this thesis, we have proposed a polynomial time approximation scheme (PTAS) for mapping actors of stream graphs on multicores. We provided detailed mathematical derivation of the PTAS.We have implemented our proposed PTAS scheme and also an ILP formulation and compared the results across a range of StreamIt benchmark programs. Our approximation obtains geometric man speedup of 5.88x on 8 processors for all benchmarks.