🚀 go-pugleaf

          The University of Western Ontario
            Department of Computer Science

                    COLLOQUIUM

Speaker: Zvi M. Kedem, Courant Institute
Title:   Coping with Asynchrony in Parallel Systems
Time:    Friday, 23, 1992, at 2:00pm
Place:   MC 320
Abstract:
  High-level parallel programming languages are designed to present a
  simple virtual machine model to the programmer.  This allows the
  programmer to focus on the essentials of the correctness and
  efficiency of programs, and thereby improves productivity. However,
  engineering constraints do not always allow these idealized
  abstractions to be directly implemented in practice.  A natural
  approach to bridging this gap is via mechanisms for automatically
  transforming the parallel algorithms or programs designed in the
  (idealized) high-level language to execute correctly on machines that
  can be actually realized in practice.
  
  In this talk, we will describe program transformations that provide a
  basis for the compilation of (ideal) {\it synchronous\/} programs to
  run efficiently on {\it asynchronous\/} parallel machines with shared
  memory.  In addition to being correct and efficient, the transformed
  programs have the important property that they are {\it responsive\/}.
  Essentially, responsive computations always make progress on the
  asynchronous target machine without waiting for slow or failed
  processors to complete their work.  Therefore, responsive executions
  are {\it fault-tolerant\/} in the following strong sense: the
  computation will terminate correctly even if processors fail
  arbitrarily often during the computation, as long as at least one
  processor is executing correctly at any time.  No implicit assumptions
  about the relative speeds of processors, or about synchronization
  primitives built into the target machines, are required for our
  methods to work.  By using randomization, we can guarantee that the
  executions on the asynchronous targets are guaranteed to require small
  overhead in space and work.

  This is joint work with Krishna Palem, Michael Rabin, and Arvind
  Raghunathan.