The Homogeneous Machine

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 wth millions of switching elements, are forcing a new look at alternative computer architecuteres which use ensembles of computing elements under restricted and 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 same 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 bandwith 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 machne are described, and a simple example of its operation is given.