Programming with Data Dependency Algebras (DDAs)
Data dependencies are inherent in the notion of an algorithm. Data dependency algebras (DDAs) [BH09] turn dependencies into explicit, programmable entities, that are more fundamental than general dependency analysis of, e.g., loops in an imperative program. DDAs abstract how parts of a computation depend on data supplied by other parts at a fine-grained level.
A hardware architecture’s space-time communication layout can be defined as a special Hardware Space-Time DDA. It has projections into space and time, where space comprises the hardware’s static spatial connectivity pattern. By embedding a computation’s DDA into the Space-Time DDA of the hardware, we map the computation onto the communication layout of the hardware.
In a DDA-enabled compiler each hardware system is associated with a computational mechanism based on its Space-Time DDA. The generated code has precise placement of the computation steps as defined by the embedding. We are developing the Magnolia language to support DDA-based programming.
Portability: In the figure, DDA + Expression is hardware independent. Embeddings onto various hardware is defined from the DDA, and is thus reusable when the DDA is reused.
Reusability: The Butterfly pattern, used as an example here, appears in many divide & conquer algorithms, sorting networks and signal processing problems. The same DDA and embeddings can be reused for many computations, only the expressions differ.
Embeddings are high-level and controlled by DDA projections, usually short, reusable code snippets. The extra detail in the example shows the Bitonic Sort DDA embedding onto CUDA.
People and Partners
- Steinar Søreide – worked on the DDA-based Sapphire language
- Eva Burrows and Magne Haveraaen. Programmable data dependencies and placements. In Proceedings of the 7th workshop on Declarative aspects and applications of multicore programming, DAMP '12, pages 31-40, New York, NY, USA, 2012. ACM. [ bib | DOI ]
- Eva Burrows. Programming with Explicit Dependencies: A Framework for Portable Parallel Programming. PhD thesis, Research School in Information and Communication Technology, Department of Informatics, University of Bergen, Norway, PB 7803, 5020 Bergen, Norway, 2011. [ bib | .html | .pdf ]
- Eva Burrows and Magne Haveraaen. A hardware independent parallel programming model. Journal of Logic and Algebraic Programming, 78:519-538, 2009. [ bib | DOI ]
- Vytautas Čyras and Magne Haveraaen. Modular programming of recurrencies: a Comparison of Two Approaches. Informatica, 6(4)397-444, 1995. [ pdf ]
- Magne Haveraaen: Efficient Parallelisation of Recursive Problems Using Constructive Recursion. In Arndt Bode and Thomas Ludwig and Roland Wismüller (editors): Euro-Par 2000, Lecture Notes in Computer Science, volume 1900, pp. 758--761, Springer Verlag, 2000. [ DOI ]
- Magne Haveraaen and Steinar Søreide. Solving recursive problems in linear time using Constructive Recursion. Proceedings of Norsk Informatikk Konferanse NIK'98, Tapir, Norway, 1998, pp. 310-321. [ ps ]