Parallel graph reduction for divide-and-conquer applications -- Part I: program transformation

Willem G. Vree, Pieter H. Hartel

    Research output: Book/ReportReportOther research output

    59 Downloads (Pure)

    Abstract

    A proposal is made to base parallel evaluation of functional programs on graph reduction combined with a form of string reduction that avoids duplication of work. Pure graph reduction poses some rather difficult problems to implement on a parallel reduction machine, but with certain restrictions, parallel evaluation becomes feasible. The restrictions manifest themselves in the class of application programs that may benefit from a speedup due to parallel evaluation. Two transformations are required to obtain a suitable version of such programs for the class of architectures considered. It is conceivable that programming tools can be developed to assist the programmer in applying the transformations, but we have not investigated such possibilities. To demonstrate the viability of the method we present four application programs with a complexity ranging from quick sort to a simulation of the tidal waves in the North sea.
    Original languageUndefined
    Place of PublicationAmsterdam
    PublisherUniversity of Amsterdam
    Number of pages29
    Publication statusPublished - Dec 1988

    Publication series

    NamePRM project internal report
    PublisherUniverstity of Amsterdam
    No.D-15

    Keywords

    • IR-68207
    • EWI-16201

    Cite this

    Vree, W. G., & Hartel, P. H. (1988). Parallel graph reduction for divide-and-conquer applications -- Part I: program transformation. (PRM project internal report; No. D-15). Amsterdam: University of Amsterdam.