Browse Prior Art Database

PIPELINING PERFORMANCE OF STRUCTURED NETWORKS

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

Publishing Venue

Software Patent Institute

Related People

Fred M. Tonge: AUTHOR [+3]

Abstract

System architectures for interconnecting I - arge numbers of processors are being studied widely CA1475JH753, Of' particilar interest in such architectures is the processors.This exploitation of' concurrency among tne concurrency can be either parallelism, in which different parts of a single aata case are processed at the same time, or pipelining, in which different processes are carried out simu.1taneously on successive data cases. Many problems involviri6 file ano vector processing can be viewed as pipelining problems.

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

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

PIPELINING PERFORMANCE OF STRUCTURED NETWORKS

by

Fred M. Tonge

Technical Report #117

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

May 6, 1978

I. Introduction

System architectures for interconnecting I - arge numbers of processors are being studied widely CA1475JH753, Of' particilar interest in such architectures is the processors.This exploitation of' concurrency among tne concurrency can be either parallelism, in which different parts of a single aata case are processed at the same time, or pipelining, in which different processes are carried out simu.1taneously on successive data cases. Many problems involviri6 file ano vector processing can be viewed as pipelining problems.

both structured and arbitrarily interconnected networks of' processors have been proposed. The asserted advantage of structurea networks is that they are easier to comprehend, control, and so utilize effectively (arguments analogous to those made for structured programming [DA72,KO741). The arguments for.arbitrary networks are that they allow greater flexibility of interconnection and so can be more efficient in many cases. Also, network architectures are being studied incorporating processor activation through data flow [AR77,AR78,DA77, DE74,DE75,SY771 and through flow of control [AN75,BR71,TH751-

In all of these cases, attention must be given to developing I -Languages for expressing procedures and rules for allocating drocedures (and their component parts) to processors so as to obtain maximum concurrency

Tnis paper presents a particular approach to specifying proceoures (process descriptions) for networks and to allocating these process descriptions to processors.

*work on structured process decomposition has involved i~obert 1)arton and hichard Cowan of the Burroughs Corporation ana t~anaell Flint of' U,C. Irvine as well as the author, ana all nave contributed to developing the concepts presented here. This particular study was suggested by a conjecture 01' Barton that structuring networks need not degrade throughput. Cowan's comments an an earlier draft greatly simplified tne proof' in section 7 rhis study was supported in part by the Burroughs Corporation and by National Science Foundation grant no.MCS77- 02715. Page- 2

The major result of' this paper is a proof' that, within our assumptions:

University of California, Irvine Page 1 Dec 31, 1978

Page 2 of 12

PIPELINING PERFORMANCE OF STRUCTURED NETWORKS

networks constructea using a small set of stri,ictured process connectives can achieve at least as good throughpat (pipelining performance) as arbitrarily interconnected networks.

2. Structured Process Description

The approach to process description of interest here involves successive structured decomposition of processes, with the resulting process network being mapped (allocated) onto interconnected processors [C067,TO761. These struct...