Browse Prior Art Database

PERFORMANCE ANALYSIS OF TWO CLASSES OF DATAFLOW COMPUTING SYSTEMS

IP.com Disclosure Number: IPCOM000128328D
Original Publication Date: 1978-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 29 page(s) / 84K

Publishing Venue

Software Patent Institute

Related People

Robert Eugene Thomas: AUTHOR [+3]

Abstract

one need hardly mention to those familiar with dataflow that research in the field has progressed very rapidly in recent years. Althoughl have tried to keep the results of this thesis as general as possible, the sparsity of dataflow architectural models which were available at the time the study was being done had its influence in limiting the scope of the thesis. This is particularly evident in the classification of dataflow machines into two types -- the preallocated and dynamically allocated machines. This classification has been found to be too rough and it is now felt that attempts at classification are too preliminary in.this rapidly changing field. As a result of this thesis and subsequent follow-up studies, it has been found that -the dynamic allocation model (i.e., as described herein using allocation tokens) suffers from a serious lack of efficiency. For this reason, the allocation token model should not be taken as being advocated by members of the UCI Dataflow Architec-ture Project. Although limited space prevents description of our current (and ongoing) ideas on allocation, we have found that it is more appropriate to raise the "granularity" of allocation while perhaps retaining a smaller granularity of computational steps. A scheme such as this is actually a mixture of a preallocated and a dynamically allocated machine (as described in the thesis) and we feel that it has most of the advantages of both. The subject of allocation aside, I feel that some of the other ideas and results presented in the thesis are worthy of serious consideration. 3 May 1978 Bob Thomas

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

Page 1 of 29

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

PERFORMANCE ANALYSIS OF TWO CLASSES OF DATAFLOW COMPUTING SYSTEMS*

by

Robert Eugene Thomas

Technical Report #120

Department of Information and Computer Science University of California, Irvine Irvine, CA 92717 May 3, 1978

*Master of Science Thesis

Preface to the Thesis

one need hardly mention to those familiar with dataflow that research in the field has progressed very rapidly in recent years. Althoughl have tried to keep the results of this thesis as general as possible, the sparsity of dataflow architectural models which were available at the time the study was being done had its influence in limiting the scope of the thesis. This is particularly evident in the classification of dataflow machines into two types -- the preallocated and dynamically allocated machines. This classification has been found to be too rough and it is now felt that attempts at classification are too preliminary in.this rapidly changing field.

As a result of this thesis and subsequent follow-up studies, it has been found that -the dynamic allocation model (i.e., as described herein using allocation tokens) suffers from a serious lack of efficiency. For this reason, the allocation token model should not be taken as being advocated by members of the UCI Dataflow Architec-ture Project. Although limited space prevents description of our current (and ongoing) ideas on allocation, we have found that it is more appropriate to raise the "granularity" of allocation while perhaps retaining a smaller granularity of computational steps. A scheme such as this is actually a mixture of a preallocated and a dynamically allocated

machine (as described in the thesis) and we feel that it has most of the advantages of both.

The subject of allocation aside, I feel that some of the other ideas and results presented in the thesis are worthy of serious consideration.

3 May 1978 Bob Thomas

CONTENTS

List of Figures . . . . . . . . . . . o . . . . . . . iv

List of Graphs

University of California, Irvine Page 1 Dec 31, 1978

Page 2 of 29

PERFORMANCE ANALYSIS OF TWO CLASSES OF DATAFLOW COMPUTING SYSTEMS

Acknowledgments

Abstract . . . . .

Section 1: Introduction o . . . . . . . . . . 1

Section 2: Dataflow Principles of Operation . . . . 3

Section 3: An Abstract Dataflow Machine (ADM) . . . 5

Peformance Analysis of Dataflow Machines . . . 6

Section 4: Simulation of a Dynamically Allocated Dataflow Machine . . . . . . 24

Specification of the Simulated Machine . . . . . 24

Simulator Input . . . . . . . . . . . . . . . . 31

Simulator Output . . . . . . . . . . . . . . . . 33

Experimental Time and Resource Utilization . 37

Experimental Effects of Allocation Policy . . . 43

Experimental Effects of Variance in C . . . . . 45

Substantiation of Analytical Results . . . . . . 45

Section 5: Further Research . . . . . . . . . . . . 49

Section 6: Conclusions . . . . . . . . . . . . . . . 50

References . . . . . . . . . o . . . . . ....