Chapter 6  Conclusions

This thesis has developed several new compiler and run-time techniques for stream programming. In conclusion, the main contributions are as follows:

1. The Abstract Streaming Machine (ASM), a flexible machine description and coarse-grain simulator for a statically scheduled stream compiler. The ASM machine model uses a bipartite graph representation to describe the target system to the compiler. The coarse-grain simulator models the program’s dynamic behaviour.
   1. Paul Carpenter, David Rodenas, Xavier Martorell, Alejandro Ramirez, and Eduard Ayguadé. A streaming machine description and programming model. Proc. of the International Symposium on Systems, Architectures, Modeling and Simulation, Samos, Greece, July 16–19, 2007.¹
   2. ACOTES. IST ACOTES Project Deliverable D2.2 Report on Streaming Programming Model and Abstract Streaming Machine Description Final Version. 2008.
   3. Paul M. Carpenter, Alex Ramirez, and Eduard Ayguade. The Abstract Streaming Machine: Compile-Time Performance Modelling of Stream Programs on Heterogeneous Multiprocessors. In SAMOS Workshop 2009, pages 12–13. Best paper award.
   4. Paul M. Carpenter, Alex Ramirez, and Eduard Ayguade. The Abstract Streaming Machine: Compile-Time Performance Modelling of Stream Programs on Heterogeneous Multiprocessors. Transactions on HiPEAC, 5(3).
   5. Harm Munk et al. ACOTES Project: Advanced Compiler Technologies for Embedded Streaming. International Journal of Parallel Programming, 39:397–450, 2011¹.
2. A new partitioning heuristic for stream programs, which balances the load across the target, taking account of the processors and communication links. A good partitioning algorithm is crucial if the compiler is to produce efficient code. This algorithm also considers its effect on downstream passes, specifically software pipelining and buffer allocation, using a convexity constraint to control pipeline length. It uses a new formulation of connectivity to model the compiler’s ability to fuse kernels.
   1. Paul M. Carpenter, Alex Ramirez, and Eduard Ayguade. Mapping Stream Programs onto Heterogeneous Multiprocessor Systems. In CASES ’09: Proceedings of the 2009 International Conference on Compilers, Architectures, and Synthesis for Embedded Systems, pages 57–66, 2009.
3. Two static queue sizing algorithms for stream programs, which determine the sizes of the buffers used to implement streams. The queue sizing problem is important when memory is distributed, especially when local stores are small. The algorithm adjusts the sizes of the buffers, subject to memory capacities, in order to cover latency and variability in computation costs.
   1. Paul M. Carpenter, Alex Ramirez, and Eduard Ayguade. Buffer Sizing for Self-timed Stream Programs on Heterogeneous Distributed Memory Multiprocessors. In High Performance Embedded Architectures and Compilers, 5th International Conference, HiPEAC 2010, pages 96–110.
4. Two new low-complexity adaptive dynamic scheduling algorithms for stream-like programs. The apriority scheduler is specific to one-dimensional stream programs, and it requires information from the compiler. The gpriority scheduler does not need such information, and it is more general.
5. StarssCheck, a debugging tool for StarSs. StarssCheck runs the program under Valgrind, using a special analysis tool, and generates a warning whenever the program’s behaviour contradicts the StarSs pragma annotations. Many of the errors found by StarssCheck would otherwise be difficult to diagnose, since they would cause race conditions or exceptions deep inside the runtime system.
   1. Paul M. Carpenter, Alex Ramirez, and Eduard Ayguade. Starsscheck: A Tool to Find Errors in Task-Based Parallel Programs. Euro-Par 2010–Parallel Processing, pages 2–13, 2010.

1

These papers also contain material that is not a contribution of this thesis.