Exploiting data-parallelism in functional languages
Guido Karel Jouret · Spiral (Imperial College London) · 1991
Existing sequential languages are inherently unsuitable for data-parallel programming because of the von-Neumann execution model built-in to the semantics o f these languages.Consideration of the requirements for data-parallel programming leads to the development of a declarative language based on the functional style.The powerful abstraction mechanism provided by functional languages allow the capabilities of data-parallel architectures to be presented via a set o f higher-order primitive operations defined on an underlying array data-type.Functional programs consisting of composition of these data-parallel operations therefore naturally exhibit data-parallelism.A set of appropriate primitive data-parallel operations is added to a simple functional language.Derived operations are defined in terms of this initial set and sample application programs demonstrate the elegance and advantages o f data-parallel programming in a functional language.A compilation scheme for compiling this extended functional language to an abstract data-parallel machine architecture is developed.An abstract data-parallel architecture, the Planar Abstract Machine (PAM) is presented.PAM is a dual-instruction architecture as two forms of basic instructions exist: those that operate on scalar (wordsize) values, and those that take planar (multiple word) values as operands.A compilation scheme generates planar-code from conventional, user-defined functions, translating all basic operations and control structures into planar forms suitable for data-parallel execution.This permits the use of fully-general user-defined functions (e.g. with recursion, conditional statements, algebraic data-types) in parallel.Efficiency concerns and possible optimizations are discussed.The development of a methodology for optimizing and parallelizing programs by the transformation o f computation and communication operations is developed.Further possible avenues o f research, including the development of primitive operations on alternative aggregate datastructures, implementation o f the data-parallel model o f computation on MIMD systems, and the role o f transformation in the possible development of systolic algorithms are discussed.He who sees the Infinite in all things sees God.He who sees the Ratio only sees himself only.Therefore God becomes as we are, that we may be as he -William Blake a c k n o w l e d g e m e n t s A thesis is an individual and often solitary journey on the path to understanding and knowledge.The satisfaction gained at the conclusion is not from arriving, but from what has been learned along the way, both about the subject matter at hand and o f one's potentials and limitations.A number o f individuals have been instrumental in my education and deserve particular acknowledgement My supervisor John Darlington provided unfailing support, freedom, and encouragement, consistent since the beginning, when I hadn't the foggiest idea o f what I was talking about.Advice (both solicited and unsolicited) was generously provided by David Lillie, Andrew Bennett, Ross Paterson, David Sharp, and many o f the other members o f the Functional Programming Section at Imperial.Tony Field and Peter Harrison elicit my gratitude for their forthright (constructive) criticisms which improved the presentation of the thesis considerably.I never would have considered trying for a Ph.D. if it weren't for the moral-support provided by my world-wide circle o f friends, specifically: Hilary Wilkinson, Chris Marriott, Alan Spidle, Steve Fernandez, and most o f all, Kenn Frankel, whose confidence in my abilities vastly exceeded my own.My brother Dirk and my sister Erika have supported me since the beginning.For putting up with my anxieties and worries over these past few years, and for never losing faith in me, Nadege Ferrero