The Homogeneous Machine

Author: Locanthi, Bartholomew Nicholas, III

Year: 1980

Degree: Dissertation (Ph.D.)

Advisor: Seitz, Charles L.

Committee Member: Unknown, Unknown

Option: Computer Science

DOI: 10.7907/0jdc-9578

Abstract

The advance of semiconductor technology is bringing about rapid changes in the scale and performance of integrated systems, thus also in their economics and potential applications. The highly visible and readily quantified changes in measures such as the number of transistors are accompanied by more subtle but increasingly significant shifts in fundamental relationships affecting system design. Specifically, as transistors become smaller, faster, and lower power, the wires used to interconnect them are becoming slower. These shifts, along with the challenge of managing the complexity of designs with millions of switching elements, are forcing a new look at alternative computer architectures which use ensembles of computing elements under restricted and regular interconnection.

This thesis addresses the problem of orchestrating many computing elements in the performance of general-purpose computations. There are three major obstacles in the way of this goal. First, it must be possible to express programs in a notation that allows concurrency to be discovered and exploited. Second, it must be possible to map computations onto a physical structure for execution by multiple computing elements. Third, such computing elements must be provided rapid access to storage while at the some time avoiding contention.

This thesis presents a scheme which automatically detects and exploits concurrencies in computations expressed in an applicative subset of the LISP programming language. The mapping of numerical and symbolic computations onto array and tree structures is also investigated.

This thesis approaches the design of multiprocessor systems as a problem in bandwidth reduction. To this end, the concept of a multi-level cache is introduced. The discussion culminates with a description of a multi-level LISP system implemented on a tree of processors. This implementation provides each processor with a superset of the address space of its immediate ancestor. Memory allocation and garbage collection for this machine are described and a simple example of its operation is given.

Files