This paper argues the case for a computer with massive amounts of primary storage, on the order of tens of billions of bytes. We argue that such a machine, even with a relatively slow processor, can outperform all other super-computers on memory bound computations. This machine would be simple to program. In addition, it could lead to new and highly efficient programs which traded the available space for running time. We present a novel architecture for such a machine, and show how it can lead to reduced memory access times and higher reliability.

The first component of a VLSI (very large-scale integration) design environment being built at Princeton University is described.The general theme of this effort is to make the design of VLSI circuits as similar to programming as possible.The attempt is to build tools that do for the VLSI circuit designer what the best software tools do for the implementer of large software systems.

ALI is a procedural language to specify VLSI layouts. It allows the designer to describe layouts without reference to the sizes and positions of the layout elements or to the distances between them. Among the interesting characteristics of ALI are that it does not need design rule checking, is easy to extend, facilitates the division of labor and permits the easy update of a layout to new design rules or to new processes. The general features of the language and the experience gained with a preliminary implementation of it are described.

Two components of a VLSI design environment being built at Princeton are described. The general theme of this effort is to make the design of VLSI circuits as similar to programming as possible. A conscious attempt is being made to apply experience in the design of large software systems to the creation of an appropriate environment for VLSI circuits. The two components described are a procedural language to specify circuit layouts and a switch-level circuit simulator for layout produced with this language. They have been chosen for presentation because many issues in their design are very similar to the issues that arise in the design of programming languages and software environments.

We present a linear-time algorithm to recognize the class of vertex series-parallel (VSP) digraphs. Our method is based on the relationship between VSP digraphs and the class of edge series-parallel multidigraphs. As a byproduct of our analysis, we obtain efficient methods to compute the transitive closure and transitive reduction of VSP digraphs, and to test isomorphism of minimal VSP digraphs.

A model of VLSI computation suitable for the description of algorithms at a high level is introduced. The model is basically a language to express parallel computations which can be efficiently implemented by a VLSI circuit. This language is used to describe area-time efficient algorithms for a few well known graph problems. The exact complexity of these algorithms and their relevance to recent work on the inherent limitations of VLSI computations are also presented.

We present an algorithm that recognizes the class of General Series Parallel digraphs and runs in time proportional to the size of its input. To perform this recognition task it is necessary to compute the transitive reduction and transitive closure of any General Series Parallel digraph. Our analysis is based on the relationship between General Series Parallel digraphs and a class of well known models of electrical networks.