Browse Prior Art Database

HIGHLY CONCURRENT ALGORITHMS FOR SOLVING LINEAR SYSTEMS OF EQUATIONS

IP.com Disclosure Number: IPCOM000147850D
Original Publication Date: 1983-Jan-31
Included in the Prior Art Database: 2007-Mar-28
Document File: 20 page(s) / 1M

Publishing Venue

Software Patent Institute

Related People

Johnsson, Lennart: AUTHOR [+2]

Abstract

CALIFORNIA INSTITUTE OF TECHNOLOGY Computer Science

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 20

CALIFORNIA INSTITUTE OF TECHNOLOGY

Computer Science

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 sf Naval Research
under Contract N00014-79C-0597

and in part by the System Development Foundation

California Institute of Technology

[This page contains 1 picture or other non-text object]

Page 2 of 20

[This page contains 1 picture or other non-text object]

Page 3 of 20

    HIGHLY CONCURRENT ALGORITHMS
FOR SOLVING LINEAR SYSTEMS OF EQUATIONS
Lennart Johnsson

       Computer Science
California Institute of Technology
Pasadena, CA 91125

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 821. Buzbee, [Buzbee
811, presents statistics showing a decrease in the rate of
increase in performance from more than two orders of magnitude
per decade arbund 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
821.

  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 801, [Browning, Seitz 811, [Li
811, and the Homogeneous Machine project, [DeBenedictis, Seitz
821, [Fox, Seitz 831. 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.

[This page contains 1 picture or other non-text object]

Page 4 of 20

  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 th...