PARALLEL EVALUATION OF SUPERCOMBINATOR PROGRAM ON A DATA FLOW MACHINE-

Abstract

Next generation of computer is aimed to achieve increased performance by exploiting the inherent parallelism existing in problem and using a large number of cheep processor chips available through VLSI technology. Declarative languages based on lambda calculus are known as function languages. They allow parallel evaluation in a natural manner and lack the notion of assignment. These languages can be used to progran a large number of chips with no side effects introduced. The lambda calculus possesses several features of programming languages but still has a simple syntax. The Beta reduction rule is the basic- reduction rule of lambda calculus. Lambda expressions can be evaluated in normal order or in applicative order and these orders can be implemented through string or graph reduction. The G machine developed by Johnsson and Augustossn is a fast implementation of graph reduction based on supercombina-tor compilation. It takes imput as.a supercombinator definition and utilizes fast recursion. The execution speed can be further increased by executing G code in parallel. In present work an algorithm is developed which checks the inherent parallelism in any problem and executes independent G codes in parallel. This is implemented through pipelined data driven computation model in which executable packets consisting of G codes and other information are processed in a pipeline of several processors.