The TRANSPOSE Machine -- A Global Implementation of a Parallel Graph Reducer

This paper describes a new concept for the parallel implementation of functional languages on a network of processors. The implementation uses a special variant of annotated graph reduction [3]. The main features of it are the following: We employ active waiting [6], to avoid complicated runtime data structures. We use a global address space, and a random distribution of the graph nodes over the local memories of the processors, in order to overcome the problems of load-balancing and scheduling. The reduction is organized in cycles during which, all annotated redices are reduced. This notion of "cycles" enables us, to restrict communication between the processors to the execution of a global permutation, defined by an array of messages M = [L LocalMessages \Theta P processors ]. This two dimensional (2D) permutation is realized by a simple and fast algorithm, that permutes all messages of M in 2L + 6L log(P ) steps, for any L sufficiently large. This algorithm actually maps any 2D-pe..