We are trapped in a sequential prison. We use sequential character strings to write sequential programs to control sequential computers. No wonder concurrency remains elusive. How did we come to be here? The high cost of vacuum tube logic forced sequence upon early computer builders. Sequential character strings were the economic way to describe what sequential computers should do. Sequential programs controlled the expensive part of the machine, namely logic. The lethargic pace of logic circuits masked the cost of moving data over distance, allowing programming languages to ignore the cost of communication. Today, the time delay and energy cost of communicating over distance dominate modern computers; logic is essentially free. Why then, do programming languages continue to control logic and largely ignore communication? It will take a broad effort to escape our sequential prison, requiring changes in hardware, programming notations and the ways in which they are expressed. Most importantly, it will require recognizing that we are in sequential prison, and planning for an escape.

Asynchronous circuits are often perceived to operate slower than equivalent clocked circuits. We demonstrate with fabricated chips that asynchronous circuits can be every bit as fast as clocked circuits. We describe two high-speed first-in-first-out (FIFO) circuits that we used to compare the performance of asynchronous FIFOs with that of conventionally clocked shift registers. The first FIFO circuit uses a pulse-like protocol, which we call the Asynchronous Symmetric Persistent Pulse Protocol (asP*), to advance data along a pipeline of conventional latches. Use of this protocol requires careful management of circuit delays. The second FIFO circuit uses a transition signaling protocol and special transition latches to store data. These transition latches are fast, but they are about 50% larger than conventional latches. Measurements obtained from chips fabricated in 0.6 /spl mu/m CMOS and from SPICE simulations show that the throughput of the first FIFO design matches that of a conventionally clocked shift register design, with a maximum throughput of 1.1 Giga data items per second. The throughput of the second design exceeds the performance of the asP* design and achieves a maximum throughput of 1.7 Giga data items per second. We have extensively tested the chips and have found them to operate reliably over a very wide range of conditions.

The paper examines tradeoffs between speed and quality of codebook/generation algorithms and offers new ways to produce excellent codebooks with only modest computation cost. It compares the performance of four algorithms for constructing codebooks. The LBG method of Linde, Buzo, and Gray (1980) produces the best codebooks but requires the most computation. The method by Equitz (1987, 1989) produces codebooks nearly as good and requires somewhat less computation. It describes a new method based on eigenvector subdivision that produces useable codebooks in a fraction of the computational effort of either of the other methods. A fourth hybrid method yields very good codebooks with modest computation by using the eigenvector subdivision method to obtain a first approximation that is refined with LBG optimization.>

With widespread use of raster scan displays and the ever-increasing desire for faster interactivity, higher image complexity, and higher resolution in displayed images, several techniques have been proposed for rasterizing primitive graphical objects. This paper characterizes the performance of these techniques and shows how they evolve for more complex images on higher resolution displays. This characterization will not only show the strengths and deficiencies of existing rasterization techniques, but will also reveal new architectures for future raster graphics systems.

This paper describes a display system designed to make the recording and rearrangement of bits in a frame-buffer display system convenient and rapid.The advantage of frame-buffer displays is that because the intensity of each pixel can be specified independently, any picture can be displayed.The disadvantage is that a great many bits in the frame-buffer memory must be changed to make major changes in the picture.The 8 by 8 display described in this paper gets its name from the fact that in a single memory cycle it can access any 8 by 8 square of pixels.Internal shifters and special memory addressing circuits are provided to make the access independent of word boundaries in the memory.Pixel manipulation functions are included to process the 64 pixels thus accessed, mask them, overwrite them with new information, or combine them logically with other pixels.The resulting data can be stored into any other 8 by 8 square of pixels in a subsequent memory cycle.Looping mechanisms implemented in microcode provide RasterOp functions that transfer information from any rectangular area of the display to any other area with or without intervening pixelmodification operations.The prototype system is able to copy the entire 768 by 1024 array of the display in 52 ms, or two frame times.The ability to rearrange data quickly has proved to be an asset for character generation, line drawing, and picture construction, as well as for scrolling and other rearrangements of material already displayed on the screen.A simple model is developed to compare the performance of the 8 by 8 memory system with conventional frame-buffer organization.Execution traces of Smalltalk display programs are applied to the model to obtain figures of merit for different hardware organizations.

Interactive use of a display requires the capability to update the display rapidly. This paper describes an on-going project at Carnegie-Mellon University in which we are designing a frame buffer raster-scan display system which has the high performance typically required for interactive display applications. The system is intended to be a display for personal computers, computer generated graphic images, and image processing applications. Built using smart VLSI memory chips, the system will use parallel processing techniques to provide high performance.

This correspondence outlines a theory for choosing printed circuit board dimensions in order to avoid crowding of printed wiring. Given a number of components to be mounted on the board and the dimensions of wiring, the theory predicts a minimum board size that should be easy to lay out. The theory does not tell how many components should be put on a board.

A method for solving mazes with extended open areas and arbitrarily placed walls is described. This method reduces large open areas containing many possible paths to a small set of shortest paths. It is then possible to use Moore's algorithm of which the paper includes a summary. A computer simulation of a vehicle exploring an unknown maze is discussed. Crude navigation and measurement are sufficient for maze solving with the techniques described.

The authors of the paper, "Linearity of Sequential Machines," which appeared on pages 337-354 of the June, 1966, issue of these Transactions, have called the following to the attention of the Editor errors on pages 338, 339, 342, 343, 347, and 351.

The display system discussed in this paper was implemented to provide a flexible test bed for man-machine interaction. The discussion includes both hardware and software design concepts, and concludes with an evaluation of the system based on operating experience. The two significant organizational features of the hardware are 1) the sharing of memory between a normal computer and a special picture computer (display device), together with 2) the capability of the latter to execute subroutines. The philosophy of design was that hardware should not limit the programmer's flexibility. This idea has been extended to utility software.