Bibliographic Citation
Document | For copies of Journal Articles, please contact the Publisher or your local public or university library and refer to the information in the Resource Relation field. For copies of other documents, please see the Availability, Publisher, Research Organization, Resource Relation and/or Author (affiliation information) fields and/or Document Availability. |
---|---|
Title | Demand-driven interpretation of FP programs on a data-flow multiprocessor |
Creator/Author | Wei, Y.H. ; Gaudiot, J.L. |
Publication Date | 1988 Aug 01 |
OSTI Identifier | OSTI ID: 6902290 |
Other Number(s) | CODEN: ITCOB |
Resource Type | Journal Article |
Resource Relation | IEEE Trans. Comput. ; Vol/Issue: 37:8 |
Research Org | Dept. of Electrical Engineering-Systems, Univ. of Southern California, Los Angeles, CA (US) |
Subject | 990210 -- Supercomputers-- (1987-1989); ARRAY PROCESSORS-- DATA-FLOW PROCESSING; DEMONSTRATION PROGRAMS;F CODES;FOURIER TRANSFORMATION |
Related Subject | COMPUTER CODES;INTEGRAL TRANSFORMATIONS;PROGRAMMING;TRANSFORMATIONS |
Description/Abstract | The functional programming language approach has been proposed as a solution to the programmability of large scale multiprocessor systems.^ This paper presents a demand-driven evaluation system for the list-structure language, Backus` FP systems.^ It enables execution in a data-driven environment.^ A formal approach for transforming FP programs into lazy programs, which contains the notion of demands, is used.^ The superset language of FP is called DFP (demand-driven FP).^ The DFP lazy programs are shown to have the property of always evaluating a sufficient and necessary result.^ A demand reduction scheme is used to remove unnecessary demand propagations on DFP programs to reduce run-time overhead.^ The DFP programs are translated into data-flow graphs according to the graph schemata developed from the FP-DFP transformation rules.^ The execution characteristics of the DFP graphs are identified and the architecture supports for efficient execution are suggested.^ Due to the laziness and the least evaluation property of transformed DFP programs, the system allows programming in FP with infinite data structures and the application of partial-functional-value evaluation.^ Examples of these applications including an infinite sequence generation and a fast Fourier transform are used to demonstrate the transformation process, the principles of run-time interpretation, the effectiveness of the transformation, and the power of the lazy evaluation system. |
Country of Publication | United States |
Language | English |
Format | Pages: 946-966 |
System Entry Date | 2001 May 13 |
Top |