RESEARCH IN COMPUTER ARCHITECTURE

M. J. Flynn Technical Report: CSL-TR-93-571 January 1993

The research described here has been supported by the Ames Research Center under NASA grants NAG2-248 and NAGW 419.

RESEARCH IN COMPUTER ARCHITECTURE

by M. J. Flynn Technical Report: CSL-TR-93-571 January 1993

Computer Systems Laboratory Departments of Electrical Engineering and Computer Science Stanford University Stanford, California 94305-4055

Abstract

Efficient processor implementations require complex architecture tradeoffs among a number of competing considerations (cycle time, register set size, cache size, instruction set capability, etc.). Concurrent techniques can be used to speed up processors both by achieving increased pipelining of the processor operations and by realizing efficient multi-processor architectures.

This progress report describes some of the work being performed by the Computer Architecture Group under contract with NASA.

Key Words and Phrases: Architecture simulation, direct mapped caches, lattice gas computers, page mapping, run-time resource management, virtual memory.

Copyright \begin{matrix}c \\ ◯ \end{matrix} 1994

by M. J. Flynn

Contents

1 The Parallel Architect’s Workbench 1 1.0.1 PADL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.0.2 Event Driven . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.0.3 Behavioral Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.0.4 Modularity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.0.5 Expandability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

2 Input/Output and Memory Evaluation 4 3 Page Coloring 5 4 Studies of Optical Interconnects for Multiprocessors 11 5 Computer Architectures for Lattice-Gas Simulations 12 6 The Computer Architect’s Workbench 13 7 A Variable-Resolution, Nonlinear Silicon Cochlea 15

List of Figures

1 Cache behavior. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Disk requests generated by non-volatile and volatile caches . . . . . . . . . . . . . . 6 3 Uncolored distribution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4 Uncolored allocation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 5 Round robin coloring. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 6 Block diagram of the ALGE processor . . . . . . . . . . . . . . . . . . . . . . . . . . 14 7 Schematic of 60 section cochlea cascade. . . . . . . . . . . . . . . . . . . . . . . . . . 16 8 Normalized impulse response at every fifth tap. . . . . . . . . . . . . . . . . . . . . . 17

List of Tables

v

1 The Parallel Architect’s Workbench

Andrew C. Zimmerman

This year we have developed tools for studying the effect of I/O storage systems on overall systems performance.

The PAWB is a set of tools to aid in the research of multiple instruction, multiple data (MIMD) multiprocessors. It consists of the AWB tools with extensions to support a Parallel C front end, multiprocessor trace generation, and a communications interconnect/memory hierarchy description. The scope of the PAWB is to do research into the class of multiprocessors with 2–64 processors, high speed 32-bit processing elements, and exploiting large grain parallelism.

The PAWB simulates the execution of a multiprocessor by creating a separate process for each processor on a host uniprocessor. Currently, context switches between processors use the scheduler of the host machine. This will be improved to use a scheduler that will switch processor simulation at the end of each basic block or shared memory reference of the executing program.

The Parallel Architects Workbench has been revised over the last year to produce a new version of the PAWB (version 2.0). The new PAWB consists of a new configurable simulator that uses the same traces as the previous version, and an Architecture Description file. Features of the new simulator include:

1. Reconfiguration using an Architecture Description written in PADL.

2. Event driven.

3. Behavioral models

4. Modular, allowing for easier extensions.

1.0.1 PADL

To allow for the study of many different parallel architectures, a Parallel Architecture Description Language (PADL) was developed. A PADL file consists of a description of each of the major components (processors, caches, and memory modules and busses) of the system and a netlist describing how they are interconnected. Each of the components has an optional section that further describes itself. For example, the cache component has options for setting the size, the linesize, the associativity, and the cycle time of that particular instance of a cache component.

PADL allows for a large number of architectures to be studies without major modifications to the simulator. The current version of PADL allows for a clustering of processors, multilevel caches, and split and unified caches. In addition, since PADL allows each component to be individually configured, non-homogeneous systems can also be studied.

PADL has been extended to allow for macro definitions. The developer may now define one macro for a component and replicate it, thus simplifying the description process and reducing the possibility of errors. At the same time, each component can still be separately defined if the developer so chooses.

1.0.2 Event Driven

To improve simulator performance, the PAWB was converted from a cycle-by-cycle simulator to an event driven simulation. The event driven simulator only simulates a component when its input signal changes, rather then simulating the component on every cycle. This technique greatly reduces the amount of simulation that must be performed. This reduction in total simulation becomes more significant when studying systems that have large variations in the cycle times between caches and main memory, and processor and network speed.

1.0.3 Behavioral Modeling

A number of different simulation techniques can be used to study computer architectures. These vary from analytical models to register level descriptions of the proposed architecture. The PAWB simulates behavioral models of each component. Behavioral models better predict the performance of the system then the analytical models, while taking less time to design and simulate then full register transfer level descriptions. Because of the complex nature of Parallel Architectures, the cache simulators used in the AWB had to be expanded to include the finite state machines necessary for cache coherence protocols.

1.0.4 Modularity

The new PAWB simulator has been broken into a small kernel and separate objects for each of the components to be simulated. The small kernel consists of the code to read the architecture description file, and the code used to schedule and process messages sent between the objects representing the various architectural components.

Each component consists of the code to simulate its behavior and the ports used to interface with other components. The interface between components is simulated using a message passing system. Address messages represent messages flowing from a processor to the main memory system. This type of message is acknowledged by Data messages which go from the main memory system to the processors.

1.0.5 Expandability

The use of PADL, event driven simulation, and modularity allows the PAWB to be easily expandable. When message passing is added to the PAWB, it will only require the addition of a network component and a communication processor component, rather then rewriting the simulator.

Hosts

With the exception of the assembly language instrumenter, the PAWB tools are machine independent or use existing programs that are available on most Unix machines. In order for the PAWB to be used on Sun4 computers, an assembly language instrumenter has been written for the Sparc computer architecture. The PAWB can now generate trace files on either the Sparc architecture or the Mips architecture. The rest of the PAWB, the PADL compiler and simulator, runs on most Unix systems.

The PAWB uses techniques to reduce the size of the trace files generated by the benchmark application. Even so, these files can become quite large for applications with large dynamic traces. To eliminate the need for the large tracefiles, the PAWB tools have been extended to allow for the concurrent generation of address traces and simulation.

As an example, an experiment was done using a matrix multiply application. The program did a matrix multiply on two square matrixes and produced a third result matrix. The data presented in Figure 1 are for a matrix of size 48×48, however, similar results were observed for an 80×80 matrix. The results of the study show the execution time vs. the number of processors for a cache size of 4, 8, 16, 32, and 64 Kbyte. The caches have a 1 cycle access time and used a simple write-invalidate coherence scheme. The bus has a width of 4 bytes (1 word) and an access time of 7 cycles for a read, 4 cycles for a write, and 1 cycle for an invalidate.

Depending on the size of the cache, the execution time actually increased when 16 processors were used. There was a pronounced effect for the case of a relatively small 4Kbyte cache and to a smaller degree for caches of size 16, 32, and 64 Kbytes. The obvious cause of this increase in execution time for 16 processors is bus contention, but the more important questions are what caused the increase in bus contention and whether it is typical of other applications.

Figure 1: Cache behavior.

To answer these questions, we examined the algorithm used to perform a matrix multiply. For each element in the result matrix the following operation must be performed.

A_{ij} = ∑(B_{ik} × C_{kj})

When one processor is used to do all of the computations for a given row of the A matrix, it only accesses only one row of the B matrix, but it must access the entire array of the C matrix. (The same would be true if one processor did all of the work for one column of the A matrix.) Given that each processor must access 1/n of one matrix and all of the other matrix, the amount of data traffic for n processors is n + 1 copies of an N × N matrix. In the case of 16 processors, 17 N × N matrixes are moved from the main memory to the caches of the processors, rather then the two matrixes moved for a uniprocessor, or roughly 8 times as much data traffic.

In addition to the extra data traffic, the average access time of each data location is also increased. For the (7/4/1) bus model described above, a uniprocessor would have an access time of (7 + N ∗ 1)/N = 1.15 cycles/access. In the case of 16 processors, a given processor will only operate on 1/n of the total matrix, and therefore the access time for a location is (7 + (N/n) ∗ 1)/(N/n) = 3.33 cycles/access, or roughly twice the access time.

For this type of access pattern, where a large portion of the data must be used by all of the processors, there is a tradeoff between cache temporal locality and the number of processors. If the same size cache is used for each of the processors in the multiprocessor and uniprocessor, the degradation is obscured by the larger total cache size. To factor out the increase in size, the final line of Figure 1 connects points of an equal multiprocessor cache size of 64 Kbytes. In this case, the four processor system with 16Kbyte caches on each processor performs better then an eight processor system with 4K caches on each processor. One conclusion is that without adequate cache support, increasing the number of processors is of marginal benefit.

The results of this study are being combined with the results of other benchmarks which exhibit different accessing patterns. The final result will give us a better understanding of the interrelationship between caches, number of processors and accessing patterns in shared-bus multiprocessors.

The PAWB is currently being used to study cache configurations and coherence protocols on shared bus multiprocessor systems. These studies concentrate on split-shared caches for processorcache configurations constrained by space and limited pin-out.

Caches in a multiprocessor system increase performance be reducing the latency of memory accesses and by reducing the amount of traffic over the shared bus. Bus traffic caused by cache accesses can be broken into four categories of cache misses: compulsory misses, capacity misses, conflict misses, and coherency misses. Compulsory traffic is the initial transfer of memory locations from the main memory into the cache. Capacity traffic is caused by accessing more unique locations from the memory system than can be held in the cache. Conflict traffic is caused by multiple memory locations mapping onto a single location in the cache. Coherency traffic is required to make certain that different caches do not have different values for the same memory location.

Shared caches can be used to reduce some of the bus traffic associated with compulsory traffic, coherency traffic, and capacity traffic. It is possible for conflict traffic to increase in shared caches, but the savings in the other traffic should outweigh this possible increase.

The memory traffic caused by a processor in a multiprocessor system consists of accesses to the instruction stream, the private data stream of each processor, and the shared data stream to memory shared by all processors. Each of these streams has differing amounts of spatial and temporal locality. By using a separate cache for each type of data reference, it is possible to take advantage of the characteristics of each type of reference stream to reduce traffic.

The goal of the split-shared cache study is to determine how to share the split caches to best improve the performance of multiprocessor systems. The study will concentrate on small, on-chip caches used on a single chip multiprocessor to be used as a cluster on a larger multiprocessor system. Due to the pin limitation of a single chip multiprocessor, the study is concentrating on shared bus multiprocessors which require a single external bus.

2 Input/Output and Memory Evaluation

Kathy Richardson

Disk I/O speed (latency and bandwidth) has and is expected to increase at a much slower rate than CPU speed and memory density. The gap in performance between the two continues to widen despite research and advancements in disk technology. I/O is emerging as a problem for all computer systems and application environments.

To compensate for the gap, we must fully understand the interaction between CPU, memory, and disk system, and make architectural and system enhancements accordingly. In order to do this, we have developed a set of tools (called TIME) that are designed to evaluate this interaction and to determine the role of new technologies in the storage system.

TIME is being used to investigate many issues involving I/O and its relationship to the memory system. The tools include a TLB simulator, virtual to real address translation via page tables, main memory allocation, I/O caches, and a disk system simulator.

The TIME tools mentioned are complete and are now being used to investigate I/O behavior. TIME is trace driven and designed to study real workloads rather than model statistical behavior. We have produced I/O traces from several workstation environments, using a modified operating system.

Progress

I/O caches (disk caches) are an important part of many I/O hierarchies. They are also useful for studying the I/O behavior of applications. The I/O cache simulator in TIME is suited for examining the referencing behavior of applications. It can keep track of the type of data requested, request sizes, and hit rates for each type. Request types can be selectively cached to evaluate interactions between requests in the cache, and to isolate and evaluate the spatial and temporal reference behavior.

Knowing how different types of data use an I/O cache can increase the effectiveness of the cache. Information from the system call level determines the type of requests. Since the trace is based on file names rather than disk block numbers, the filesystem maintenance, executable, and application data are all visible.

Each data type has different reference behavior. Each cache size supports different types to differing degrees. Properly exploiting these properties increases the reference hit rate in the I/O cache and reduces the number of references out of the cache to disk.

I/O caches reduce the I/O latency by eliminating disk accesses. Conventional approaches reduce latency by increasing the cache hit rate. But caches with the same hit rate, and the same disk, can have different miss latencies and different disk load characteristics. An alternate way to reduce the latency is to increase the efficiency of the load offered to the disk. The disk requests from both non-volatile and volatile cache configurations are evaluated. Neither configuration efficiently utilizes the cache to offer a low latency load to the disk. Ways to improve their load characteristics have been explored. The policies implemented in the cache impact the number of total disk requests as well as the time distribution of these requests. Figure 2 shows how typical management policies for non-volatile and volatile cache configurations affect the number of disk requests.

3 Page Coloring

William L. Lynch

Page Coloring uses the operating system to control the mapping of virtual to physical address by controlling the physical memory page which virtual pages are allocated to. Coloring becomes useful when the page number is involved in cache indexing, i.e., for large, low associativity, first level caches: exactly the trends the industry is following.

For these large physically-indexed caches, the use of the low-order bits of the physical page number (the color) in cache indexing involve the virtual to physical translation in the location of data in the cache. While the virtual address space is laid out very uniformly, the lack of control over the virtual-to-physical mapping by most operating systems causes the physical color (and therefore cache placement modulo the page size) to be “randomly” selected. Thus, depending on the order in which the physical pages are assigned, cache miss rate can vary significantly. Figure 3 shows the distribution of miss rate of 200 executions with different placements of virtual pages into physical pages. Note the factor of 4 between the best and worst miss rates. The small circles in the plot (their vertical location is meaningless) indicate the mean of this distribution, and the miss rate of a virtually-indexed cache (where the virtual color indexes the cache, rather than the physical color). The mean of the uncolored allocation is worse than for a virtually-indexed cache, and the variation is very high, although sometimes (about 30% of the time in this example) the uncolored cache out-performs the virtually-indexed cache, as a placement of pages in the cache superior to the location in virtual memory is happened upon. Figure 4 shows the cycles-per-instruction (CPI) effect of the cache miss rate on the overall system. An excess CPI of one due to the cache for a one-CPI machine gives a total CPI of two, and a machine which is twice as slow as one with no cache delays (misses). The black circles indicate 6 different page placements for each cache size, and the black line is the mean of these 6 runs. The dashed line is the performance of a virtually-indexed cache. A machine with a 64KB cache running the example benchmark would run at 1 + .05 = 1.05 CPI with a virtually-indexed cache, but with a mean of 1 + .17 = 1.17 CPI for uncolored physically-indexed caches, or more than 10% slower. Sometimes, the benchmarks would run fast, and sometimes as slow as 1 + .3 = 1.3 CPI or 25% slower than expected. Over the entire range of caches shown, the Figure 2: Disk requests generated by non-volatile and volatile caches, expressed as a percent of the original (or no-cache) requests.

Figure 3: Uncolored distribution. 7 Figure 4: Uncolored allocation.

8 uncolored physically-indexed cache performs significantly worse than a virtually-indexed cache, and also have significant variation, sometimes exceeding an order of magnitude in performance difference!

For physically indexed caches, coloring can greatly improve the average miss rate, and reduce the variation between runs. Figure 5 demonstrates the results of a round-robin coloring heuristic, which provides good performance and no variance. Note that the dashed line, representing the performance of virtually-indexed caches, is labeled ‘Perfect Static Coloring’ in this graph. Static coloring, where the virtual and physical color are forced to be equal, allows the cache to be indexed virtually for speed, and physically for operating system simplicity. Essentially, the virtual-to-physical translation is not required before cache indexing, yet can proceed in parallel with it. Additionally, the cache miss rate is precisely that for a virtually-indexed cache, as the physical color is forced by the operating system to match the virtual color.

For virtually-indexed cache hardware, static coloring is an appealing operating system paradigm for solving virtually-indexed cache aliasing problems (converting it to a physically-indexed cache), and has been shown to allow hashing and aliasing to co-exist. Hashing is becoming more important as first-level cache sizes increase dramatically. Additionally, static coloring greatly simplifies the use of virtually-indexed caches in multi-processor systems, where physical addresses on the bus can index the processor without reverse address translation (physical to virtual).

Over 30,000 simulations of caches and virtual memory systems have been run to test uncolored (conventional) page allocation. The orthogonal effects several parameters such as line size, associativity, and page size were tested for each of six benchmarks. Several coloring heuristics have been tested, some of which involved potential hardware feedback. Full results were developed for unified, data, and instruction first-level caches.

A paper, “The Effect of Page Allocation on Caches” [15], was presented at Micro-25 in December. Another paper, “Cache Improvements through Colored Page Allocation” [14], has been submitted to ACM Transactions on Computer Systems. Additionally, a dissertation, “The Interaction of Virtual Memory and Cache Memory,” [16] nears publication.

Some of the contributions and conclusions of the research follow.

The desire for low effective-latency memory systems inexorably leads to caches with lower associativity for low latency and larger size for low miss rates. Lower associativity and larger size caches in turn inevitably lead to cache index sizes larger than the virtual-memory-system page size. Coloring requires that the address bits used to address a page and to address a cache have a fixed relationship.

There is a precise taxonomy for page coloring. Perfect coloring always holds; imperfect allows lapses. Static coloring allocates pages based on virtual address; dynamic coloring allocates pages based on run-time allocation history.

For physically-indexed caches, this larger index must mean delay during address translation, or perfect static page coloring to increase the number of effectively untranslated bits available for indexing. To reduce high variation in inter-run miss rates, and therefore overall system performance, page coloring becomes a requirement for physically-indexed cache systems regardless of latency considerations. Page coloring’s necessity in such physically-indexed systems regardless of indexing requirements indicates that coloring should be used to also allow early cache indexing. Either perfect static coloring or round robin coloring reduce miss rate variation, but perfect static coloring would also allow virtual cache indexing, reducing overall latency.

Virtually-indexed caches, or perfect static colored physically-indexed caches, do not require page coloring for inter-run miss-rate consistency. However, as cache sizes increase, the compiler’s allocation of data to fixed virtual addresses will require hashing to make effective use of the virtuallyindexed cache. Perfect static coloring provides a framework within which virtual indexing and hashing can coexist without preventing aliasing. Perfect static coloring also simplifies cache snooping in multiprocessor systems because the first-level cache can be both virtually-indexed from the Figure 5: Round robin coloring.

10 processor side and physically-indexed from the snooping (bus) side. Perfect static coloring also enhances inclusion in second level caches by providing more effectively untranslated address bits.

The distributions of miss rates for uncolored caches show significant variation. Data caches distributions were fairly wide, while instruction cache distributions had more instances near the mean but the few colorings producing miss rates away from the mean could be far from it. Perfect static page coloring and round robin page coloring both reduce the variation in miss rate to the minimum, i.e., none, and while providing good miss rate performance, did not necessarily provide optimal miss rate performance. For medium sized caches, perfect static coloring provided miss rate results superior to round robin coloring, but for small unified or data caches, or large unified caches, round robin coloring provided better colorings. For systems with reasonabe main memory sizes relative to their cache size, the page faults simulations reported herein showed little if any deterioration in page fault rate to oppose these early indexing and miss-rate consistency advantages.

A well-written operating system should easily implement either dynamic or static page coloring. Page colors must be checked only on page allocation and during any remapping of virtual to physical addresses.

Perfect static coloring provides significant advantages in aliasing and hashing while allowing the low latency of virtually-indexed caches. Multiprocessor systems also benefit through increased second-level inclusion, and physical-indexing of the first level cache for snooping. Considering these varied advantages, the low impact on page fault rate, and the ease of implementation, perfect static page coloring deserves serious consideration in any computer system memory design.

4 Studies of Optical Interconnects for Multiprocessors

Timothy M. Pinkston

We have continued to study possible optical interconnections for multiprocessors.

The GLORI strategy is a multiprocessor interconnect scheme designed to aid the programmer, compiler, and/or run-time scheduler in facilitating locality, e.g., in partitioning, placement, and relocation of data and processes. It also aids the hardware architecture in performing the functions useful in capturing and exploiting locality, e.g., clustering, combining, and caching. The impetus behind GLORI is to use the interconnect as an additional resource for taking advantage of multiprocessor locality and to use optics to achieve this goal. Among some of GLORI’s non-optical features are hierarchical topology, clustering, combining, and minimal delay routing protocols.

Optics is a promising interconnect technology for multiprocessors. The usefulness of optics’ many interconnect features are evaluated using GLORI as a framework. In the proposed GLORI organization, M processor-memory elements (PMEs) are clustered together onto shared buses at the local interconnect level, and N/M bus clusters are arranged in a hypercube at the global interconnect level. Reconfiguration of PME connectivity occurs system-wide to allow arbitrary groups of PMEs to be clustered, but the baseline shared bus-hypercube topology is assumed to remain intact. Interconnect links are established by fiber and free-space holographic diffractive optics.

In previous work, we found that cluster affinity among PMEs is maintained over intervals of tens to hundreds of thousands of execution cycles. Interconnect reconfiguration occurring once every millisecond is therefore sufficient to exploit this behavior. Ferroelectric liquid crystal spatial light modulators and experimental photorefractive holographic devices assumed by GLORI can operate well within this switch frequency.

Progress

Recently, we studied the feasibility of a GLORI implementation. A single-pass, static optical geometry composed of elementary guided and free-space holographic optical components was analyzed. A number of issues determine the feasibility of the GLORI system. Some issues indirectly impact feasibility, such as those relating to the holographic beam steering element. Other issues, such as those relating to optical geometry, directly impact how the system size can be feasibly implemented due to fan-out and fan-in limitations.

A multiprocessor system of N = 256 processor-memory nodes can be feasibly implemented with a static optical shared bus-hypercube GLORI network. By improving aspects of the optical system which most limit scalability, systems on the order of thousands of nodes can be built. The volume of GLORI’s shared bus-hypercube optical routing unit was found to be about one cubic centimeter, which is far less than comparable electronic hard-wired implementations. The tradeoffs in implementing various GLORI strategy communication models in terms of resource count, implementation complexity, and latency reduction were also assessed.

Somewhat of an unexpected finding is that GLORI’s block-frequent reconfiguration policy is not a general solution for improving performance. Block-frequent reconfiguration is shown to prove useful when it reduces global reference activity to levels that do not saturate the global network. In other words, if there is not sufficient cluster locality, reconfiguration is unlikely to reduce network latency.

5 Computer Architectures for Lattice-Gas Simulations

Fung F. Lee

In the past year, we have obtained a number of results concerning the design of a massively-scalable dedicated processor for two and three-dimensional lattice-gas simulations capable of billions of cell updates per second (CUPS). The results will be reported in details in Fung F. Lee’s doctoral dissertation [8]. Some of the concepts have been previously published in [10, 11, 9, 12].

Many important simulation problems deal with complex physical systems with large numbers of degrees of freedom. All of the ten grand challenges such as fluid turbulence, pollution dispersion, and weather prediction, as listed in the report [7] prepared by the Office of Science and Technology Policy, fall into this category. Fluid dynamics provides an especially good case study of cellular automaton formulation of large complex physical systems because there are two rich and complementary ways to picture fluid motion. The microscopic picture of many simple molecules colliding rapidly with simple interactions coincides with our intuitive picture of dynamics on a cellular automaton, while the macroscopic picture of collective fluid motions based on considerations of conservation of mass, momentum and energy leads to the Navier-Stokes equations. Lattice gas models solving incompressible Navier-Stokes equations are selected as concrete examples of our study.

The kernel of a lattice gas simulation consists of updating the values of all lattice nodes (cells) by executing many repetitions of two alternating steps: particle collision and particle propagation. There are three major research issues involved in designing hardware support for lattice gas models, namely, collision mechanisms, propagation mechanisms and scalability. The most critical issue is the design of hardware mechanisms to support 3-D collision rules. On one hand, a full collision table implementation (requiring at least 384 Mbits) is relatively fast but very expensive, and thus hardly scalable in practice. On the other hand, algorithms that can use a reduced-size collision table (requiring 0.4 Mbits or more) execute relatively slowly. The best of both worlds would be a fast hardware collision unit that can use a reduced-size collision table. The second issue is the design of propagation mechanisms. When collision is fast, propagation becomes the bottleneck if nothing is done to improve it. In a system context, propagation implies data memory access and communication. Moreover, memory cost is likely to dominate the system cost. Therefore, the goal is to invent a set of mechanisms to support efficient memory access and utilization, and effective interprocessor communication. The third issue is scalability. A multiprocessor architecture is scalable if it achieves close to linear speedup as the number of processors dedicated to the task increases. (A massively-parallel machine is thus not necessarily massively-scalable.) Amdahl’s Law says that if we want to achieve close to linear speedup with a large number of processors, only a small fraction of the original computation can be sequential. Therefore, performance of much less frequent operations such as handling of boundary conditions, input/output operations and statistics collections in a large scale multiprocessor architecture becomes a larger issue than it would be in an uniprocessor architecture.

We have shown that with appropriate hardware support it is feasible to design a dedicated processor with performance comparable to existing supercomputers, and how to put together a scalable SIMD machine, ALGE, containing from a few to thousands of these processors with close to linear speedup. The efficiency of the ALGE architecture derives from a set of new mechanisms.

Based on group theory, two hardware collision rule reduction algorithms and architectures for use with reduced lookup tables have been developed. The isometric collision rule unit, which yields a moderate Reynolds coefficient for some fixed collision function, has been implemented in a field programmable gate array device with about 3000 gates. The general programmable collision rule unit, which works with a reduced collision table of 2.5 Mbits (or more if rest particles are added) can effectively compute all collision functions designed to yield higher Reynolds coefficient. Supporting propagation mechanisms include: virtual move as a zero buffering algorithm which gives the advantage of double buffering without the extra cost, multi-dimensional modulo adders for efficient address generation, transpose buffers for supporting the data structure optimized for efficient DRAM page-mode access, and a fast low-latency router for local nearest neighbor communication on a torus. Other supporting architectural mechanisms are extensive random number generators for flexible boundary conditions, support for statistics collection, and a scalable I/O mechanism.

An ALGE machine consists of a number of processor nodes connected in a two-dimensional torus. Each processor node contains an ALGE processor, a reduced collision table (SRAM) and data memory (DRAM). An ALGE processor is a VLSI circuit containing about half a million transistors, running at 20 MHz (see Figure 6). Most of the silicon area is spent on regular structures such as buffers and registers. The processor has multiple function units operating concurrently so that throughput is only limited by the data memory (page mode) cycle time. The processor has enough pins to support a collision table with 1 million entries of 32-bit words. The data memory is used to store the states of all the cells. A word of 64 bits can be accessed in one cycle. A typical local data memory has about 8 MB of DRAM. Simulation shows that with our chosen access sequence the page mode hit ratio can be high enough that the cell update rate per processor can be sustained at around 18 million cell updates per second (MCUPS). This per-processor performance compares very favorably with the performances of CRAY-2 (30 MCUPS) and CM-2 (45 MCUPS).

6 The Computer Architect’s Workbench

Brian Bray

We have continued our basic studies on special-purpose processors for pattern recognition and pattern perception.

Evaluating the usefulness of architectural/design decisions is complicated by the interdependence of architectural features, various levels of compiler sophistication, and the validity of benchmarks. At Stanford University, the Computer Architect’s Workbench (AWB) has been developed to aid in evaluating designs. The Architect’s Workbench is a set of tools to predict the relative performance Figure 6: Block diagram of the ALGE processor

14 of alternative computer and system architecture features. The Architect’s Workbench runs actual programs for various hardware configurations.

The Architect’s Workbench predicts the relative performance of alternative computer and system architectures. The system allows high-level tradeoff, including instruction format selection, instruction encoding, register set size and organization, and cache size and organization. The Compiler tools consists of compiler front ends, code optimizers, and register allocators. The remainder of the tools are used to simulate the architectures being studied. These consist of programs to do static analysis of the instruction and data stream and programs to simulate the memory hierarchy, i.e., instruction and data caches. Since simulation speed is crucial to examining many alternatives, the tools rely heavily on static analysis of the application to reduce simulation time.

As the issue rate of processors increases (from superscalar and/or superpipeline organizations), the demand on the memory system also increases. We have been extending the Architect’s Workbench by developing new tools to further analyze the nature of access and use of memory. In this last year, with the use of these tools we have made several discoveries that can help optimize pipelined processors for memory access management.

• We have developed a two-level windowed register file to reduce the cycle time of to that of a smaller windowed register file while retaining the performance of a large windowed register file [5].

• We have developed a tag cache to eliminate the need to check the data cache before a perform write [6].

• We have developed subword caching to eliminate the need for subword access hardware being in the primary cache access path [2].

• We have developed translation hint buffers to eliminate the latency of address translation for a physically addressed instruction cache [3], [4].

• We have continued to explored page coloring; a simple modification to an operating system’s page allocation algorithm to give physically addressed caches the access speed of virtually addressed caches [15].

In addition to our own research, we have continued to distribute the Architect’s Workbench to other universities. We also have ported the AWB to the Sun4.

7 A Variable-Resolution, Nonlinear Silicon Cochlea

Neal A. Bhadkamkar

The cochlea is an organ that sits behind the eardrum on each side of the head. Its fuction is to convert the sound-induced mechanical vibrations of the eardrum into electrical impulses that travel up the parallel fibers of the auditory nerve to the brain, where they are processed and understood.^{1} A low-power silicon implementation of the cochlea could potentially be used to develop better cochlear implants, higher functionality hearing aids, novel consumer products, and robust front ends for speech recognition systems.

Subthreshold analog CMOS is a particularly interesting technology for the development of intelligent sensing and recognition systems. First commercially used in the development of Swiss watches Figure 7: Schematic of 60 section cochlea cascade. In the physical circuit, the resistances are implemented by polysilicon wires, and the circuit is folded over at the midpoint, so that sections 31 to 60 are in a second row under sections 30 to 1 respectively.

1The brain, in turn, sends control signals back to the cochlea, much as it sends signals to the eyes to focus them on items of interest. However, this aspect of the brain/cochlea interaction is poorly understood compared to the signal processing done by the cochlea itself.

by Vittoz, it has more recently been extended and popularized by Mead [19] for use in circuits that mimic biological systems in both function and sometimes form. The technology uses standard, and therefore inexpensive, CMOS transistors, operating with continuous currents and voltages rather than the binary voltages used in digital circuits. The current levels are tiny and are those of a transistor in the off state; large circuits can be constructed in this medium with very little power consumption.

Subthreshold analog VLSI implementations of cochlea-circuits were pioneered by Lyon and Mead [18] using a cascade of 2nd-order resonant sections. Subseqent cascade implementations have been reported in the literature by Lyon [17] and by Liu et al. [13]. Our implementation is also a cascade implementation. It differs from the previously reported cascade implementations in two important respects. First, it is adjustable so that cascades with finer frequency resolution can be constructed without incurring a penalty in terms of the delay to a section with a given best frequency. Second, this implementation is nonlinear and implicitly models the saturating active mechanism of the outer hair cells that gives rise to basilar membrane response curves that become less sharply tuned as the input amplitude is increased.

Earlier work under this project had focused on the design and analysis of a circuit to model the behavior of a small length of the basilar membrane in the cochlea. During the past year we were able to successfully cast this design into silicon and construct a cochlea circuit by cascading 60 of these sections in series. The circuit is fabricated in a standard 2-micron CMOS process through MOSIS and occupies approximately 15% of the area of a standard 4.6 mm × 6.8 mm chip. The circuit is estimated to consume on the order of 300 nanowatts, not including off-chip communication requirements.

Experimental results demonstrate that the circuit is in fact adjustable, allowing cochleas with different resolutions to be simulated while maintaining the same gain and delay characteristics. An important aspect of this adjustability is the fact that the variation from nominal behavior of the cochlea-circuit due to circuit imperfections is reduced when the circuit is adjusted so that each section simulates a smaller rather than larger length of the basilar membrane. We suspect that a similar statistical mechanism is at work in the biological cochlea.

Experimental results also demonstrate that there are qualitative similarities between the largeinput induced nonlinear response of the cochlea-circuit and that of the biological cochlea. Just like the vibration of the basilar membrane in a biological cochlea, the gain versus frequency curves at a given section of the cochlea-circuit become flatter and broader as the input amplitude is increased.

Figure 7 shows a schematic of the overall cochlea circuit, and Figure 8 shows the impulse response at every fifth section. As expected, the time period and delay increase exponentially as the section number increases.

Figure 8: Normalized impulse response at every fifth tap.

The design has several limitations. First is the fact that it is not universally stable in its small signal linear region. This becomes an important consideration given the high degree of variation present in subthreshold circuits. A second limitation is the component count. Each section in the current design uses seven wide-range transconductance amplifiers and one buffer amplifier for driving the signal off the chip. Given the result that adjusting the circuit to get more sections per octave results in a lower variance system, one would like sections with the least number of components in order to limit the area requirements of high-resolution cochlea-circuits. A third limitation arises from the observation that this particular circuit was not designed with the goal of variance reduction in mind, which would have led to different choices of building blocks (such as simple rather than wide-range transconductance amplifiers), biasing techniques and layout.^{2}

Experience with the first chip has led to several ongoing efforts. A second chip incorporating two 60 section cochlea-circuits and associated hair cell circuits has been designed and fabricated [1], but only partially tested as of this writing. It is meant to provide inputs to a cross-correlator circuit, so that the combined system can locate sound sources in the horizontal plane.

A third chip that has been designed but not fabricated is a finite element implementation of the same cochlear model that formed the basis of this work. It models the bulk of the fluid in the cochlear chambers using a two-dimensional resistive network based on the same principle used by Watts et al. [21]. More importantly, it has a circuit for the basilar membrane that explicitly incorporates a saturating active outer hair cell model. While this design has an even higher component count than the present design, it has the advantage of modeling the cochlea in form as well as function, so that it will be easier to incorporate other features such as feedback to the outer hair cells from higher processing centers.

Another effort that is in a much earlier stage is aimed at developing robust feature detectors and incorporating them onto the cochlea chip. The goal of this undertaking is to develop inexpensive but highly functional front ends for speech recognition systems.

An implicit result of our research is the viability of subthreshold analog VLSI as a medium for implementing dense analog computational systems. We designed a circuit to provide performance akin to the results obtained from a mathematical model, layed it out using vanilla design tools, fabricated it using a common process available through MOSIS, and obtained working chips on the first attempt. This should encourage other researchers to use this technology with a greater degree of confidence. However, we caution people that the design rules for obtaining low-variance systems based on subthreshold circuits are more stringent than those used in typical digital or analog circuit designs. Some of these rules are described in Vittoz [20]. However, because of the relative infancy of this design form, these rules do not appear to be widely known.

2Layout is not related to the design per se, but we mention it here anyway. The process of working with this and other chips has led to an appreciation of the special design rules that must be used with subthreshold technology.

References

[1] Neal Bhadkamkar and Boyd Fowler. A sound localization system based on biological analogy. In Proceedings of the 1993 IEEE International Conference on Neural Networks, 1993. To be published March 1993.

[2] B. K. Bray and M. J. Flynn. Efficiently Supporting Subword Loads And Stores. Technical Report CSL-TR-92-514, Computer Systems Laboratory, Stanford University, April 1992.

[3] B. K. Bray and M. J. Flynn. Translation hint buffers to reduce access time of physicallyaddressed instruction caches. Technical Report CSL-TR-92-535, Computer Systems Laboratory, Stanford University, August 1992.

[4] B. K. Bray and M. J. Flynn. Translation hint buffers to reduce access time of physicallyaddressed instruction caches. In Micro-25 Conference Proceedings, pages 206–209, December 1992.

[5] Brian K. Bray and M. J. Flynn. A Two-Level Windowed Register File. Technical Report CSL-TR-91-499, Computer Systems Laboratory, Stanford University, December 1991.

[6] Brian K. Bray and M. J. Flynn. Tag Caching For Improving Write-Back Cache Bandwidth. Technical Report CSL-TR-92-509, Computer Systems Laboratory, Stanford University, February 1992.

[7] Committee on Physical, Mathematical, and Engineering Sciences of the Federal Coordinating Council for Science, Engineering, and Technology. Grand Challenges: High Performance Computing and Communications, The FY 1992 U.S. Research and Development Program. Office of Science and Technology Policy, 1991.

[8] F. Lee. A Scalable Computer Architectures for Lattice-Gas Simulations. PhD thesis, Department of Electrical Engineering, Stanford University, August 1993. CSL-TR-93-576.

[9] F. F. Lee and M. J. Flynn. Architectural Mechanisms to Support Three-Dimensional Lattice Gas Simulations. Third Annual ACM Symposium on Parallel Algorithms and Architectures, pages 115–122, July 1991.

[10] F. F. Lee, M. J. Flynn, and M. Morf. A VLSI architecture for the FCHC isometric lattice gas model. Technical Report CSL-TR-90-426, Stanford University, April 1990.

[11] F. F. Lee, M. J. Flynn, and M. Morf. Design of Compact High Performance Processing Elements for the FCHC Lattice Gas Models. In Jack J. Dongarra, Ken Kennedy, Paul Messina, Danny C. Sorensen, and Robert G. Voigt, editors, Proceedings of the Fifth SIAM Conference on Parallel Processing for Scientific Computing, March 1991.

[12] F. F. Lee, M. J. Flynn, and M. Morf. High-Performance Multiprocessor Architecture for a 3-D Lattice Gas Model. Third Annual NASA Symposium on VLSI Design, pages 7.2.1–7.2.14, October 1991.

[13] W. Liu, A. G. Andreou, and M. H. Goldstein, Jr. Voiced-speech representation by an analog silicon model of the auditory periphery. IEEE Transactions on Neural Networks, 3(3):477–487, May 1992.

[14] W. Lynch and M. Flynn. Cache improvements through colored page allocation. ACM Transactions on Computer Systems, 1993. Submitted for review, 1992.

[15] W. L. Lynch, B. K. Bray, and M. J. Flynn. The effect of page allocation on caches. In Micro-25 Conference Proceedings, pages 222–225, December 1992.

[16] William L. Lynch. The Interaction of Virtual Memory and Cache Memory. PhD thesis, Stanford University, October 1993. CSL-TR-93-587.

[17] Richard F. Lyon. CCD correlators for auditory models. In 1991 Asilomar Conference on Signals, Systems, and Computers, 1991.

[18] Richard F. Lyon and Carver Mead. An analog electronic cochlea. IEEE Transactions on Acoustics, Speech, and Signal Processing, 36(7):1119–1134, July 1988.

[19] Carver Mead. Analog VLSI and Neural Systems. Addison Wesley, 1989.

[20] Eric Vittoz. Subthreshold design. IEEE Circuits and Systems, 22:147–153, 1986.

[21] Lloyd Watts, Richard F. Lyon, and Carver Mead. A bidirectional analog VLSI cochlear model. In Advanced Research in VLSI 1991 : UC Santa Cruz, pages 152–162. 1991.