Greg Wilson's Parallel Timeline 
Author Message
 Greg Wilson's Parallel Timeline

Dear All,

        You may be aware that Greg has incorporated some entries from
the parallel FP history into the more general time line (due to be
published in the IEEE's "Parallel & Distributed Technology" some time
after Christmas).  As I was fairly busy, I didn't have time to consult
the group as to what they thought should go in - so I'm remedying that
situation right here and now.  Greg assures me that there is still
time to get any corrections and additions into the final version.

        I've extracted the FP entries from the history (ignoring
some of the dataflow entries) and included them at the end of this
post.  Greg has some fairly stringent guidlines as to what does or
does not get into the list, and set a rough limit of 15 to 20 FP
entries, so some fairly brutal editing was called for.  I'd greatly
appreciate any feedback on the following points:

        1.  Is anything obviously missing?

        2.  Should anything be deleted (a lot of the entries after
1988 are not advanced enough to enable their importance to be
estimated)

        3. Corrections?  (I'm fairly sure the ParAlfl language entry
is wrong - the implementation described was part of the work on serial
combinators, and not on ParAlfl).

        I'll be making a new version of the Parallel FP history
available via FTP sometime next week - if people want a copy before
then, and their site has deleted the copies posted to this group, then
I can send stuff by mail (assuming I'm not inundated with requests :)

        Thanks for your time,

                Andy.

1978: {Backus, John} {FP} {functional programming} {dataflow}
In his Turing Award address, John Backus (inventor of fortran) argues
against dependence on conventional languages, and for functional
programming.

1978: {Arvind} {U-Interpreter} {dataflow} {Id} {University of
California (Irvine)}
Arvind, Kim Gostelow and Wil Plouffe (at the University of California,
Irvine) describe the Unravelling Interpreter (U-Interpreter), which
exploits greater concurrency than the static dataflow model.  This
idea comes to be referred to as the dynamic dataflow model.  The
dataflow language Id (Irvine dataflow) is introduced.

1980: Mago' proposes the cellular FFP
  machine, a massively parallel MIMD computer architecture using a
  functional programming language as a machine language, using a
  string reduction strategy as the evaluation mechanism.
  Investigations on the application of various interconnection
  networks, automatic parallelism and the use of scans was carried out
  before the project ended in 1989.  The machine was simulated but
  never built.

1981: {functional programming} {ZAPP}
The ZAPP (Zero Assignment Parallel Processor) machine is developed by
McBurney, Sleep, and Burton at East Anglia.  ZAPP contains a virtual
tree of transputers, and uses divide \& conquer to support parallel
functional programs.

1982: {functional programming} {granularity} {combinators}
John Hughes develops the notions of super combinators and lambda
lifting, removing the need for global environments.  This forms the
basis for many subsequent implementations of parallel functional
languages.

1982: {ALICE} {functional programming}
John Darlington begins development of ALICE (Applicative Language
Idealized Computing Engine), a multi-processor reduction engine for
the parallel evaluation of functional languages.

Quote:
>1983: {Keller}, {Davis}, {dataflow}, {FEL}, {DMMP}, {AMPS}
>  A second generation AMPS dataflow architecture, Rediflow, is proposed
>  by Keller and Davis, aimed at unifying the ideas of reduction and
>  dataflow.  The system is made up of multi-stage connected Xputers
>  (processor/memory/switch units), with FEL (Function Equation
>  Language) as its high level language. The machine was simulated but
>  never built, and the project terminated in 1987. Utah.}

This probably won't make it to the final version

1984: {Johnsson, Thomas} {G-Machine} {functional programming}
{Chalmers University}
Thomas Johnsson, at Chalmers University in Sweden, develops the
G-machine graph reduction technique, which forms the basis for the
majority of later implementations of parallel functional languages.

1986: {functional programming} {granularity} {combinators} {Yale}
{Hudak, Paul}
Paul Hudak and Benjamin Goldberg at Yale extend work of Hughes by
developing the serial combinator, an automatic technique for
extracting medium grained parallelism.

1986: {Hudak, Paul} {ParAlfl} {Yale}
Paul Hudak at Yale develops ParAlfl, a functional language with
meta-linguistic control of parallel operational semantics, and
implements a simplified version on a 128-node Intel iPSC.

1986: {Arvind} {I-structure} {Id} {functional programming} {dataflow}
{MIT} {Cornell}
Arvind (MIT), Nikhil (MIT) and Pingali (Cornell) propose the
I-structure, a parallel structure similar to arrays, but allowing side
effects that would result in an impure functional programming
language.  This is incorporated into the Id language.

1987: {ALICE} {functional programming}
First ALICE machine, containing 40 processing agents and an
``intelligent'' memory connected by a multi-way switching network, is
completed.

1987: {GRIP} {functional programming}
The GRIP (Graph Reduction in Parallel) team at the University of
Glasgow and University College, London, develop a bus-based system for
parallel functional programming.  Each of up to 20 boards contains 4
Motorola 68020s, 1~Mbyte of memory, and an ``intelligent'' memory
unit, which supports graph reduction and garbage collection.  The
machine runs a parallel version of the Haskell language.

1988: {Sabot, Gary} {paralation model} {data parallelism}
Gary Sabot describes the paralation model, a form of data parallelism
relying on the concepts of shape, move and elwise.

1989: {PAM} {functional programming} {University of Aachen}
Loogen, Kuchen, Indermark, and Damm at Aachen implement parallel
programmed graph reduction on a 64 processor transputer system,
including evaluation transformers and parallel applicative data
structures.

1989: {Cole, Murray} {skeletons} {University of Edinburgh}
Murray Cole, at the University of Edinburgh, proposes the use of
algorithmic skeletons as a basis for parallel functional programming.

1990: {TMC CM-2} {functional programming} {Yale}
George Mou, working at Yale, develops Divacon, a parallel functional
programming language based on divide \& conquer which runs on the CM-2
Connection Machine.

1990: {Bird-Meertens formalism}
David Skillicorn, working at Queen's University in Canada, proposes
that the Bird-Meertens theory of lists can be used as a basis for an
architecture-independent parallel functional system.

Quote:
>1991: {data distribution} {CRYSTAL}
>Jingke Li and Marina Chen describe CRYSTAL, a systematic approach for
>specifying communication and optimizing an automatic mapping from
>access patterns to communication structures.

I think this entry is wrong - the entry should be 1986 and I'm
fairly sure that Crystal is a FPL (prehaps non-pure).  Greg's tracking
this down - but any immediate feedback would be great

1993: {NESL} {functional programming} {data parallelism} {Belloch, Guy}
NESL, a nested data-parallel functional language designed to be
architecture independent, executes on the CM-2, CM-5, workstations
running PVM, and Cray Y-MP C90.  Language design and implementation
due to Blelloch, Chatterjee, Hardwick, Sipelstein and Zagha at
Carnegie Mellon.



Mon, 26 Feb 1996 20:36:50 GMT  
 Greg Wilson's Parallel Timeline

Dear All,

Sorry about the delay, but I've finally managed to collate all
the replies I received regarding the parallel time line.  Thanks
to everyone who went to the trouble of replying.  Hopefully the
new version (included at the end of the post) comes close to
representing a reasonable summary of the key events in the
field of parallel functional programming, though I would still
be very grateful for any further input (there's still a little
of time before Greg has to submit the final copy to the IEEE).
I'd be very interested in your opinions on the following:

        o Anything missing?
        o Anything included which shouldn't be?
        o Corrections
        o Rewording
        o Anything else....

I would be especially interested in any references to
Southampton's FAST project, and the current status of the
FLAGSHIP project (are ICL planning to launch a machine
based on this work?).

Note that there are no dataflow entries as they have already
secured a place in the final version.  I have also avoided
entries post 1990 (ish) as it is probably a little early to
label such research as "history".

Both this report and the more general version (still dealing soley
with parallel FP) can be obtained via anonymous ftp from
ftp.cs.bham.ac.uk:/pub/pub/dist/func-prog/TLHistory.tex.gz
and History.tex.gz respectively.

Cheers,

        Andy.

1   Introduction
================

This report describes the landmarks in the area of parallel functional pro-
gramming.

1.1   Contributors
==================

The following people have helped compile the history (email addresses will
not be included unless the contributors have given their permission to do
so):


          Edo Biagioni           EB
          Tony Davie             TD
          John Feo               JF
          John Glauert           JG
          Stefan U. Haenssgen    SH
          Kevin Hammond          KH
          Pieter H. Hartel      PHH
          Paul Hudak             PH
          Matthew Huntbach      MMH
          Robert M. Keller       RK
          Herbert Kuchen         HK
          Patrick Miller         PM
          Simon Peyton Jones     SPJ
          Fethi A Rabhi          FR
          Jay Sipelstein         JS
          David Turner           DT
          Philip Wadler          PW
          Paul Whiting          PGW
          Greg Wilson           GVW

Additions or amendments to the history should be sent to Andy Ben-Dyke.

2   Major Landmarks
===================

1978:

  John Backus (inventor of Fortran) publishes paper on FP systems, argu-
     ing that dependence on conventional languages has made the develop-
     ment and use of non-von Neumann architectures uneconomical, and
     has deprived computer architects of an intellectual foundation for new
     computers.(PGW)

1979:

  Turner describes a new implementation technique for functional lan-
     gauges, based on Curry's combinators, that does away with the need
     for a global environment, and points out its potential for parallelism.
     This provides a basis for all the later work on graph reduction.(TD,DT)

1980:

  Mag'o proposes the cellular FFP machine, a massively parallel MIMD
     computer architecture using a functional programming language as a
     machine language, using a string reduction strategy as the evaluation
     mechanism. Investigations on the application of various interconnec-
     tion networks, automatic parallelism and the use of scans was carried
     out before the project ended in 1989. The machine was simulated but
     never built.(EB)

1981:

  The ZAPP machine (Zero Assignment Parallel Processor) is developed by
     McBurney, Burton and Sleep at East Anglia - based on a network of
     transputers connected in a virtual tree (similar to a hypercube), using
     divide and conquer as it's underlying programming paradigm. Imple-
     mentations using up to 32 processors were developed by 1987(MMH,JG,KH)

1982:

  Hughes and Johnsson develop the notions of super combinators and
     lambda lifting, which form the basis of the majority of current FP
     implementations.(TD,ABD,PH)

  John Darlington develops ALICE (Applicative Language Idealized Com-
     puting Engine) - a multi-processor reduction engine for the parallel
     evaluation of applicative languages. Consisting of 40 processing agents
     and a packet pool segments (intelligent memory) connected with a
     multi-stage switching network, the machine became operational in
     1987. Imperial College, London.(ABD)

1983:

  Sisal 1.0 (Streams and Iterations in a Single-Assignment Language) lan-
     guage definition released by Lawrence Livermore National Laboratory
     (LLNL), Colorado State University, DEC, and University of Manch-
     ester.  A derivative of VAL, the language included array operations,
     streams, and iterations.(JF)

1984:

  Johnsson, at Chalmers University, Sweden, develops the G-machine - a
     highly efficient graph reducer which forms the basis for the majority
     of todays implementations. Variations suitable for parallel implemen-
     tation include the spineless, tagless G-Machine (Peyton Jones, Glas-
     gow, 1988) and the <v; G>-machine (Augustsson and Johnsson, also
     1988).(ABD,SPJ,PW)

  van Eekelen, N"ocker, Smetsers and Plasmeijer, at the University of Ni-
     jmegen, develop Clean, based on the ABC machine. Currently there
     are efficient implementations running on suns, macintoshes and trans-
     puter based ZAPP systems (implementation developed at the Univer-
     sity of East Anglia).(SH,JG)

1985:

  Sisal 1.2 language definition released; language definition does not change
     for another seven years.(JF)

1986:

  ParAlfl, a functional language with meta-linguistic control of parallel op-
     erational semantics, was developed by Hudak, with a simplified version
     running on a 128 node, Intel iPSC machine. Yale.(PH)

  Arvind (MIT), Nikhil (MIT) and Pingali (Cornell) propose the I-structure
     - a parallel structure similar to arrays, but having side effects (there-
     fore would result in an impure FPL). This is incorporated into the Id
     language.(ABD)

1987:

  Peyton Jones, Clack, Salkild, Hardie, Hammond and Mattson, at Univer-
     sity College, London, and then Glasgow, develop GRIP, a bus-based
     system designed specifically to execute parallel functional programs.
     GRIP provides fast hardware packet-routing and "intelligent" mem-
     ory units. Since 1990, the machine has run a dynamically-controlled
     parallel Haskell.(KH,SPJ)

  Burn develops evaluation transformers - a form of strictness analysis.
     Kingdon, Lester and Burn use this as the basis for the HDG machine,
     with a 5 node transputer system being developed by 1990. GEC Mar-
     coni, Hirst.(ABD)

  SC (SISAL Compiler) released by LLNL and Colorado State University.
     First functional language, native-code compiler and runtime system
     for shared-memory multiprocessor systems.(JF)

1988:

  Sabot describes the Paralation model, using the concept of shape, move
     and elwise to achieve data parallelism. Harvard.(ABD)

1989:

  Loogen, Kuchen, Indermark, and Damm implement parallel programmed
     graph reduction on a 64 processor transputer system, including evalua-
     tion transformers and parallel applicative data structures. The imple-
     mentation is based on PAM (Parallel Abstract Machine), which sepa-
     rates communication and processing activities, increasing the amount
     of exploitable parallelism. Aachen.(HK)

  Kelly describes the Caliban coordination language for loosely coupled
     MIMD machines, with an implementation soon to be released for the
     Meiko computing surface. Imperial.(ABD)

  Cole, at Edinburgh University, proposes the use of algorithmic skeletons
     as a basis for a parallel paradigm.  Kelly et al are currently working
     on a transputer system at Imperial College, London.(ABD)

  OSC (Optimizing SISAL Compiler) released by LLNL and CSU. The
     compiler optimizes the copy and memory management; SISAL pro-
     grams achieve Fortran speeds on conventional shared-memory multi-
     processors.(JF)

1990:

  Mou develops Divacon - a parallel FPL based on the divide and con-
     quer paradigm - the system runs on Connection Machine's CM-2.
     Yale.(ABD,PH)

1993:

  In an attempt to draw together the lazy functional community and dataflow
     community, the pH language (parallel Haskell) is proposed. A layered
     approach is suggested, starting with a pure foundation, then adding
     I and M structures on top.  Arvind (MIT), Augusston (Chalmers),
     Hicks (Motorola MCRC), Nikhil (DEC CRL), Peyton Jones (Glas-
     gow), Stoy (Oxford) and Williams (IBM Research) all plan to support
     the project.(ABD,KH)



Wed, 27 Mar 1996 00:54:09 GMT  
 
 [ 2 post ] 

 Relevant Pages 

1. Using Wilson Snyder's Verilog-Perl with NC Verilog

2. CFP: ACPC'96 - parallel DBs and parallel I/O

3. CFP: 3rd Int'l ACPC Conf: parallel DBS and parallel I/O

4. CFP: 3rd Int'l ACPC Conf: parallel DBS and parallel I/O

5. Trying to find Greg Leif's Book

6. Greg Michaelson's Ph.D thesis

7. See Greg's Oberon Questions (response)

8. Greg's Postings

9. reply to Greg's reply

10. Greg Stein's COM book

11. Greg's GUI Framework

12. ANN: Implementation of Greg's GUI API

 

 
Powered by phpBB® Forum Software