Implementation and Evaluation of a List-Processing-Oriented Data Flow Machine

The architecture of a data flow machine, called DFM, is developed for parallel list processing. The DFM can maximally exploit parallelism inherent in list processing, due to its ultra-multi-processing mechanism, packet communication-based parallel and pipeline execution mechanism, and lenient cons mechanism. A practical DFM implementation is described. A DFM prototype machine is implemented and DFM performance is evaluated in a simulation on the register transfer level using several benchmark programs. The DFM single processor system is shown to be about five times faster than conventional machines which use the same device technology, while a multi-processor DFM system is shown to achieve a linear speed-up ratio of 0.6 ~ 0.9.