Next: StackPacket or Up: Novel Architectures Previous: Novel Architectures

Reduction Machines

The first and most famous physical reduction machine was ALICE (Applicative Language Idealised Computing Engine), designed by Darlington and Reeve at Imperial College in 1981 [36] and built over a period of several years. The eventual aim was to build ALICE in VLSI, but in the event the only ALICEs actually built used stock components.

The prototype ALICE comprised 40 Transputer-based processing agents and packet pools, connected by a multi-stage switching network (Figure 1 shows an ALICE board). Overtaken by developments in sequential compiler technology such as supercombinators [69][66], and by improvements in conventional hardware design, the absolute performance of this machine was ultimately disappointing [53]. This may be partly explained by the interpretive nature of much of the prototype software, but the use of many small packets probably also degraded performance to some extent.

Many valuable lessons were learned from the design of this machine, and these have been applied to more recent architectures such as the ICL Flagship [39][117][119] and EDS/Goldrush designs [116] (now emerging as a commercial, though no longer purely functional, product). These machines have been designed to address a wide variety of pragmatic usability issues, such as the provision of multi-user computing and fault tolerance, which are of less importance in a basic research setting.

The novel graph reducer GRIP (Graph Reduction in Parallel) [97][98] is built from a network of distributed conventional processors. It has a two-level bus structure, and incorporates fast packet-switching hardware for message routing, and intelligent memory units for efficient operations on globally shared graph and spark/task pools. Because it uses microcoded CPUs for the intelligent memory units and PALs for the packet-switching hardware, the GRIP machine has proved extremely flexible. Since its inception it has undergone a transformation from a parallel abstract machine interpreter to a machine running compiled Haskell directly. Figure 2 shows a GRIP board being tested on the GRIP test rig.

Several other early machine designs were parallel combinator implementations. Examples of these are COBWEB [52], Burroughs' NORMA [101], and SKIM [114]. Most of these were built in some form, but were quickly overtaken by the widespread adoption of supercombinators before they could deliver significant results. Other interesting machine designs which have failed to come to fruition were Rediflow [71], COBWEB-2 [5], and Magó's FFP machine [79].

Most recent implementations have used conventional hardware. There have, however, been several recent proposals for novel implementations: Star:Dust suggests adding special communication and task control instructions to an otherwise unremarkable RISC processor [93]; BWM is a VLIW machine to execute functional programs [9]; and G-Line also exploits horizontal parallelism within supercombinator reductions [85].

Next: StackPacket or Up: Novel Architectures Previous: Novel Architectures

Kevin Hammond <>
Thu Jan 4 21:31:10 GMT 1996