Browse Prior Art Database

HIGHLY CONCURRENT ALGORITHMS FOR SOLVING LINEAR SYSTEMS OF EQUATIONS

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

Publishing Venue

Software Patent Institute

Related People

Lennart Johnsson: AUTHOR [+3]

Abstract

There is a growing concern over the reduced rate at which computers of increased performance are being developed for large scale scientific computation, [Lax 82]. Buzbee, [Buzbee 81], presents statistics showing a decrease in the rate of increase in performance from more than two orders of magnitude per decade around 1960 to presently less than one order of magnitude per decade. To significantly change the trend concurrency is necessary. Here we will discuss algorithms for ' computers built out of several processors of approximately equal complexity. The number of processors may be very large. A taxonomy of ensemble architectures is given by Seitz, [Seitz 82] .

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

Page 1 of 15

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

HIGHLY CONCURRENT ALGORITHMS FOR SOLVING LINEAR SYSTEMS OF EQUATIONS

by

Lennart Johnsson Presented at Monterey Conference on Elliptic Problem Solvers January 1983

The research in this report was sponsored in part by the Defense Advanced Research Projects Agency, ARPA Order 3771, and monitored by the Office of Naval Research under Contract N00014-79C-0597 and in part by the System Development Foundation California Institute of Technology HIGHLY CONCURRENT ALGORITHMS FOR SOLVING LINEAR SYSTEMS OF EQUATIONS

Lennart Johnsson

' Computer Science California Institute of Technology Pasadena, CA

I. INTRODUCTION

There is a growing concern over the reduced rate at which computers of increased performance are being developed for large scale scientific computation, [Lax 82]. Buzbee, [Buzbee 81], presents statistics showing a decrease in the rate of increase in performance from more than two orders of magnitude per decade around 1960 to presently less than one order of magnitude per decade. To significantly change the trend concurrency is necessary. Here we will discuss algorithms for ' computers built out of several processors of approximately equal complexity. The number of processors may be very large. A taxonomy of ensemble architectures is given by Seitz, [Seitz 82] .

The machines envisioned are made up of a thousand to tens of thousands of processors with their own local storage, sparsely interconnected and possibly also connected to some form of auxiliary storage. Two construction projects are currently under way at Caltech based on this metaphor, the Tree Machine project, [Browning 80], [Browning, Seitz 81], [Li 81], and the Homogeneous Machine project, [DeBenedictis, Seitz 82], [Fox, Seitz 83]. These two projects are architectural experiments with a significant difference in processor archi-tecture, size, machine topology, and programming model. Both machines use message passing to synchronize computations in neighboring processors.

The Tree Machine node processors are intentionally kept very simple, the emphasis being on efficient communication and a large number of processors. In our first design a 16-bit processor is used with floating point in software and 1-2k words of local storage. Even though such a processor is very limited, a 1000 chip machine would have 8000 processors and 6M 16-bit words of storage in 2 micron technology. Such a machine would have an estimated capacity of about 0.5 Gflops.

The Homogeneous Machine node is currently based on standard parts, an Intel 8086 processor with an 8087 floating point processor, with additional chips for handling the communica-tion. The node that today requires a small PC board is expected to fit on a single chip at 1/2 micron

California Institute of Technology Page 1 Dec 31, 1983

Page 2 of 15

HIGHLY CONCURRENT ALGORITHMS FOR SOLVING LINEAR SYSTEMS OF EQUATIONS

technology. At 5 MHz clock rate each node has been benchmarke...