Browse Prior Art Database

A VLSI Combinator Reduction Engine by

IP.com Disclosure Number: IPCOM000127936D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 16 page(s) / 52K

Publishing Venue

Software Patent Institute

Related People

William. C. Athas, Jr.: AUTHOR [+3]

Abstract

The design of concurrent architectures for high performance computing engines has been speculated upon for mare than twenty years [8]. Such systems can now readily be realized with VLSI technology if the two following guidelines are adhered to. First of all, locality in communcation must be preserved since it is intrinsic to the physics of integrated circuits. Secondly, since VLSI is a replication technology, this aspect of the technology can be exploited to reproduce homogeneous parts. Based on these two guidelines, a class of machines has been defined as "Ensemble Architectures" [16]. They are characterized by the regular interconnection of a single computing element replicated many times over.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 7% of the total text.

Page 1 of 16

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A VLSI Combinator Reduction Engine by

William. C. Athas, Jr.

In Partial Fulfillment of the Requirements for the

Degree of Master of Science

8 June 1983 The research described in this document was sponsored by the Defense Advanced Research Projects Agency, ARPA Order number 3771, and monitored by the Office of Naval Research under contract number N00014-79-C-059?.

Caltech Computer Science Department Document Number: 508fi:TR:83

Table of Contents 1 Introduction 1 2 Alternative Computation Models 2 3 Combinator Computation Model 6 4 Combinator Evaluation for a Single Path Reduction Engine - The REDEX 9 Simulator fi Foundations for a Concurrent Reduction Engine 12 6 The CRE-1 Simulator 18 7 Speculation on a VLSI Implementation 20 8 Conclusions and Future Work 21 Acknowledgements 24 I. REDEX LISP BNF 25 II. Simple CSP Rule Set 26 III. REDElC Reduction Rules in Graphical Form 27 IV. BNF Description of CRE-1 LISP Language 34 V. CSP Firing Rules for CRE-1 Combinator Tree Cells 31 List of Figures Figure 1: Sorting Element Using Linear Array of Computing Elements 2 Figure 2: Berkling Hierarchy of Computation 3 Figure 3: Algebraic Reduction of Quadratic Formula 4 Figure 4: Completely Worked Example of the SWR Function 6 Figure 5: LISP versus Turner Data Structures for the S4R function 10 Figure 6: (X+3) * (X+5) Function 13 Figure 7: Combinator Tree for Infinite Integer List 14 figure 8: Factorial Function Using Modified Combinator Tree 16 Figure 9: Block Diagram for CRE-1 Machine 21 Figure 10: Computation Hierarchy Including CRE-1 Machine 23

1 introduction

The design of concurrent architectures for high performance computing engines has been speculated upon for mare than twenty years [8]. Such systems can now readily be realized with VLSI technology if the two following guidelines are adhered to. First of all, locality in communcation must be preserved since it is intrinsic to the physics of integrated circuits. Secondly, since VLSI is a replication technology, this aspect of the technology can be exploited to reproduce homogeneous parts. Based on these two guidelines, a class of machines has been defined as "Ensemble Architectures" [16]. They are characterized by the regular interconnection of a single computing element replicated many times over.

Architecture experiments are currently underway at Caltech to investigate this class of machines. The machines are primarily differentiated by interconnect strategy and

granularity of concurrency. Listed to order of increasing granularity they are:

1. Cosmic Cube - Boolean N-Cube , 128K bytes per processor. [11 J 2. Mosaic Mesh - Torus, 1 to 4K bytes per processor.

3. Mosaic Tree - Binary tree, 1 to 4 K bytes per processor. [2]

California Institute of Technology Page 1 Dec 31, 1983

Page 2 of 16

A VLSI Combinator Reduction Engine by

4. Super Mesh - Torus, Single Instruction Multiple Data Path As would be expected, if an algorithm can...