Adl(ID:3655/adl005)

Polymorphic non-recursive data-parallel functional language  


for Adelaide

Roe, Alexander, Engelhardt and Wendelborn, University of Adelaide, 1992-

Small functional polymorphic non-recursive data parallel language based on the Bird-Meertens formalism

Adl is a small strict functional language designed to support data parallelism. The purely functional nature of Adl ensures that BMF code produced from Adl source can be manipulated as a mathematical expression.
A small number of built-in higher-order combinators are provided. These include map, reduce, and scan and variants on these to cater for reductions and scans with no base value.

The scan operators have been provided as primitive, in spite of it being possible to define these in terms of list-homomorphisms. The reason for this decision is that a more efficient parallel implementation of scan exists than that furnished by the list homomorphism.

In addition to the list processing primitives Adl provides the two standard constructs of if and while. if caters for conditional evaluation of an expression. while is supplied as an iterator to be used in cases where computation is not bounded by the length of an input list.

The current version of Adl is non-recursive. The lack of recursion is convenient from the point of view of the language implementors since it allows all function calls to be in-lined and translated into composed sequences of functions in BMF. In the small number of Adl applications tested so far the lack of recursion has not caused us great difficulty, but further experiments on language expressiveness are underway.


Influenced by Blelloch, TAM, Skeletons, others in paper


Structures:
References:
  • Roe "Adl: The Adelaide Language" Technical report University of Adelaide 1992 view details ps
  • Alexander "Data Movement Optimisation in Adl" 1994 view details ps
  • Alexander "Mapping Adl to the Bird-Meertens Formalism" 1994 view details ps
  • Engelhardt and Wendelborn "Expressing Nested Data Parallel Operations Through Multithreading" University of Adelaide TR 94-16 May 1994 view details ps
  • Alexander, Engelhardt and Wendelborn "An Overview of the Adl Language Project" view details Abstract: The purpose of the Adl project is to demonstrate the efficient implementation of data parallel functional programming, firstly on the TMC CM-5 but ultimately on other parallel machines. We have designed a small polymorphic non-recursive language (Adl), which emphasizes high-level operations (second-order combinators) on aggregate structures. The Adl project incorporates the formal description of Adl semantics, translation and optimization, and the design of an abstract data-parallel machine which describes not only the CM-5 but also other distributed memory multicomputers and hence encourages architecture-independent code generation. An executable natural semantic description of translation to the Bird-Meertens Formalism (BMF) has been completed; similar techniques are being used with an optimizer. We also describe an implementation of the abstract machine for the CM-5 implementation. ps
          in Proceedings Conference on High Performance Functional Computing, Denver, Colorado, April 1995 view details
  • Engelhardt and Wendelborn "A Partitioning-Independent Paradigm for Nested Data Parallelism" view details ps Abstract: A generalization of the data parallel model has been proposed by Blelloch which permits the nesting of data parallel operators to specify parallel computation across nested and irregular data structures. In this paper we consider the costs of supporting the general model of nested data parallelism, analyzing the requirements such a model places upon an underlying model of execution. We propose a new multi-node execution model which meets the needs of the paradigm and is additionally generic in the partitioning of data aggregates within the system. The basis for our execution model is an abstract machine based upon elementary notions of nodal multi-threading. We demonstrate the utility of our proposal by providing a full definition for a simple nestable one-dimensional data parallel operator. We discuss the applicability of our design to existing multi-processor machines, illustrating performance statistics gathered from a prototype system we have constructed on the Thinking Machines CM-5.
          in Proceedings IFIP International Conference on Parallel Architectures and Compilation Techniques (PACT95), Cyprus, June 1995 view details
  • Engelhardt and Wendelborn "Visualizing Communications Patterns in Nested Data-Parallel Computations" University of Adelaide TR 96-02 Jan 1996 view details ps
          in Proceedings IFIP International Conference on Parallel Architectures and Compilation Techniques (PACT95), Cyprus, June 1995 view details
  • Alexander, Engelhardt and Wellborn "An overview of the Adl project" University of Adelaide 1997 view details ps Abstract: The purpose of the Adl project is to demonstrate the efficient implementation of data parallel functional programming, firstly on the TMC CM-5 but ultimately on other parallel machines. We have designed a small polymorphic non-recursive language (Adl), which emphasizes high-level operations (second-order combinators) on aggregate structures. The Adl project incorporates the formal description of Adl semantics, translation and optimization, and the design of an abstract data-parallel machine which describes not only the CM-5 but also other distributed memory multicomputers and hence encourages architecture-independent code generation. An executable natural semantic description of translation to the Bird-Meertens Formalism (BMF) has been completed; similar techniques are being used with an optimizer. We also describe an implementation of the abstract machine for the CM-5 implementation.
          in Proceedings IFIP International Conference on Parallel Architectures and Compilation Techniques (PACT95), Cyprus, June 1995 view details
  • Engelhardt and Wendelborn. A Multi-Threaded Implementation of Nested Data Parallelism Australian Computer Science Communications, vol. 19, no. 1 (Feb. 1997) view details ps Abstract: In previous work, we have proposed a multi-threaded execution model for describing nested data-parallelism on distributed multiprocessors in a fashion generic upon the partitioning of data aggregates within the system. This paper demonstrates an approach which uses this abstract model as the basis for a run-time system for a data-parallel functional language. We describe an active message based implementation of the model on the Thinking Machines CM-5 and also consider various issues related to efficient compilation targetting such a platform. Several issues central to the performance of the model are addressed. A hybrid scheme for thread synchronization and data flow is presented which incorporates a highly efficient mode of matching and one permitting the most general forms of interaction. We also describe a generic thread library of data-parallel primitive operations which operate independently of data partitioning. Finally, we detail work undertaken to instrument our execution environment for visualization and tracing.
          in Proceedings IFIP International Conference on Parallel Architectures and Compilation Techniques (PACT95), Cyprus, June 1995 view details
  • Engelhardt and Wendelborn "High-Level Specification of Data Layout in a Distributed Nested Data Parallel Computation" Proc. PART98, Adelaide, Australia, Sep. 1998 (Springer) view details Abstract: In previous work, we have presented a novel virtual machine for executing Nested Data-Parallel (NDP) languages on distributed memory architectures and described how a simple data-parallel functional language, Adl, can be realized upon this architecture. Within our model of NDP execution, declarations of data layout take the form of arbitrary partitioning functions, mathematical mappings from an index of the aggregate to the identity of its owner (the processing element which stores the value of that index). Each aggregate is associated with one such function at the time of its creation. PFN is an interactive visual tool which affords a higher-level view of design process of specifying the mapping of data to nodes. Programmers assign aggregate elements to a chosen processing node by gesture rather than by writing code. The executable partitioning functions implementing the PFN specification are generated by PFN according to an optimized set of templates provably free of logical errors. We describe our data placement model; a framework for for abstract specification of partitioning; and the PFN tool itself, illustrating its use in defining partitioning schemes. ps
          in Proceedings IFIP International Conference on Parallel Architectures and Compilation Techniques (PACT95), Cyprus, June 1995 view details
    Resources