GeoSTAR-III, a 180 GHz prototype for the Precipitation and All-weather Temperature and Humidity Sounder (PATH), is the culmination of a decade of technology development funding. The interferometric radiometer comprises 144 receivers operating from 165-183 GHz and utilizes a 192×192 input, ASIC based mixed signal correlator. The demonstration of this instrument raises the technology readiness of the radiometer subsystem to level 6 (TRL 6) and the correlator subsystem to TRL 5. We demonstrate the full functionality of this system with observations of the Sun and Moon as well as nearby thermally emissive objects. This represents the final milestones in the development effort of pre-mission technologies for this decadal survey mission.

Modeling wave propagation through the earth is an important application in geoscience. We present a framework for wave propagation modeling on special-purpose hardware, which dramatically improves the application performance compared to conventional CPUs. We utilize custom hardware platforms consisting of a mix of x86 CPUs and dataflow engines connected by high-bandwidth communication links. Application programmers describe their algorithms in a domain specific language using Java syntax, with special dataflow semantics overlayed on top of the Java language. The application-specific dataflow engines run at hundreds of MHz with massive parallelism and deliver high performance/Watt, up to 30 times more energy efficient than conventional CPUs. The power efficiency of this approach suggests that dataflow computing may have a key role to play in the improvements in power efficiency necessary to reach exascale computing.

Over the past decades parallel processor speedup has been an elusive quantity for a broad class of applications. Yet with the end of performance scaling for single processors the need for speedup has never been greater. The problem is not technology but programming models. One answer to this speedup problem is to create an idealized data flow machine that exactly corresponds to the application and stream data through the resulting machine. This approach can be emulated with FPGAs, providing more than an order of magnitude speedup even as executed as an emulation of the data flow machine.

The following topics are dealt with: reconfigurable systems; computer arithmetic; computer algorithm; system profiling; multicore processor; communication systems; GPU; accelerator; image processing and FPGA application.

We describe the development and progress of the GeoSTAR-II risk reduction activity for the NASA Earth Science Decadal Survey PATH Mission. The activity directly addresses areas of technical risk including the system design, low noise receiver production, sub-array development, signal distribution and digital signal processing.

While recently the focus of architects and programmers has been on multi core, the alternative of processor node plus array oriented accelerator has some significant advantages especially in compute intensive static applications. We propose an acceleration methodology based on FPGA arrays (but, in principle it could be GPU or Cell based). The methodology uses a comprehensive application analysis supported by high performance FPGA hardware. The analysis provides a dataflow graph of the application which is replicated in SIMD for multiple data strips until limited by the pin bandwidth, then pipelined (MISD) until circuit limited. An oil exploration application shows the possibility of speedup of over 300x over an Intel Xeon.

Basic to parallel program speedup is dealing with memory bandwidth requirements. One solution is an architectural arrangement to stream data across multiple processing elements before storing the result in memory. This MISD type of configuration provides multiple operations per data item fetched from memory. One realization of this streamed approach uses FPGAs. We'll discuss both the general memory problem and some results based on work at Maxeler using FPGAs for acceleration.

Application specific is always a tradeoff among competing design goals (or design parameters). In addition to the well established area (cost) - time (performance) - power metrics specific applications imply a relatively limited market so design cost becomes an especially important consideration. As technology offers increasing transistor density with lower cost power constraints limit frequency as the primary avenue to performance. The alternative is to use area (transistors) to recover performance putting an additional strain on the design budget. The search for flexibility in design without paying a significant area - time - power cost remains the primary problem for application specific and system on a chip (SoC) design.

Some 50 years ago saw a series of rapid advances in design automation technology setting the stage for generations of reliable computers. Over the intervening years progress in the field continued to deal with the advancing complexity of the technology. This success in design automation was based on capturing or encapsulating complex designs into components to be managed in a larger design. On the other hand, in the past, power was never seen as a limitation yet this now looms as a major problem. Looking at the future, designer productivity and design complexity remain a central limitation on product development especially for specialized system applications (SoC type). Power presents a new challenge especially to the same emerging system applications. We look at these issues both in the context of the past and possibilities for the future.

For performance reasons, many high-speed floating-point multipliers today precompute multiple significand values (SVs) in advance. The final normalization and rounding steps are then performed by selecting the appropriate SV. While having speed advantages, this integrated rounding method complicates the development of the rounding logic significantly, hence, requiring a systematic rounding method. The systematic rounding method, presented in this paper, has three steps: 1) constructing a rounding table; 2) developing a prediction scheme; and 3) performing rounding digits selection (RDS). The rounding table lists all possible SVs that need to be precomputed. Prediction reduces the number of these SVs for efficient hardware implementation while RDS reduces the complexity of the rounding logic. Both prediction and RDS depend on the specifics of the hardware implementation. Two hardware implementations are described. The first one is modeled after that reported by Santoro et al. and the second improved one supports all IEEE rounding modes. Besides allowing systematic hardware optimization, this rounding method has the added advantage that verification and generalization are straightforward.

We use a partially redundant number system as an internal format for floating point arithmetic operations. The redundant number system enables carry free arithmetic operations to improve performance. Conversion from the proposed internal format back to the standard IEEE format is done only when an operand is written to memory. A detailed discussion of an adder using the proposed format is presented and the specific challenges of the design are explained. A brief description of a multiplier and divider using the proposed format is also presented. The proposed internal format and arithmetic units comply with all the rounding modes of the IEEE 754 floating point standard. Transistor simulation of the adder and multiplier confirm the performance advantage predicted by the analytical model.

The task of computer architecture is to match a user application with a base technology. This match is realized by implementing an interpreter of some representation of the application with an efficient realization, measured in cost (area), time (performance) and power. As silicon technology becomes increasingly limited by interconnects, more efficient cellular computers are attractive. Indeed larger cells (compared to FPGAs) seem to offer an improved area /spl times/ time /spl times/ power measure. In order to effectively used them, the programmability obstacle must be overcome. The ALGE experiment showed how this might be done by creating a new class of user representation for scientific applications.

In modern processors floating point divide operations often take 20 to 25 clock cycles, five times that of multiplication. Typically multiplicative algorithms with quadratic convergence are used for high-performance divide. A divide unit based on the multiplicative Newton-Raphson iteration is proposed. This divide unit utilizes the higher-order Newton-Raphson reciprocal approximation to compute the quotient fast, efficiently and with high throughput. The divide unit achieves fast execution by computing the square, cube and higher powers of the approximation directly and much faster than the traditional approach with serial multiplications. Additionally, the second, third and higher-order terms are computed simultaneously further reducing the divide latency. Significant hardware reductions have been identified that reduce the overall computation significantly and therefore, reduce the area required for implementation and the power consumed by the computation. The proposed hardware unit is designed to achieve the desired quotient precision in a single iteration allowing the unit to be fully pipelined for maximum throughput.

Simplifying the programming models is paramount to the success of reconfigurable computing with field programmable gate arrays (FPGAs). This paper presents a methodology to combine true object-oriented design of the compiler/CAD tool with an object-oriented hardware design methodology in C++. The resulting system provides all the benefits of object-oriented design to the compiler/CAD tool designer and to the hardware designer/programmer. The two examples for domain-specific compilers presented are BSAT and StReAm. Each domain-specific compiler is targeted at a very specific application domain, such as applications that accelerate Boolean satisfiability problems with BSAT, and applications which lend themselves for implementation as a stream architecture with StReAm. The key benefit of the presented domain specific compilers is a reduction of design time by orders of magnitude while keeping the optimal performance of hand-designed circuits.

General-purpose microprocessors are designed to deliver low-latency computation with maximal clock frequencies, leading to high power consumption. In terms of performance and power consumption, latency-tolerant applications can be efficiently implemented with architectures that provide high throughputs, such as Imagine, Score, RaPiD, and the PCI-PipeRench. Stream architectures are fully-pipelined, high-throughput microarchitectures. Algorithms are executed by mapping dataflow graphs to hardware and streaming the data through the architecture. In the best case, when all the loops are fully unrolled, the dataflow graph is acyclic and the clock frequency of the design is the data rate. In this paper, we develop a domain-specific compiler for programming FPGAs, called StReAm. StReAm is build on top of the module generation environment PAM-Blox.

The fine grain size of current FPGA has been a major performance bottleneck. In this paper, we introduce a coarse-grained carry architecture that increases the grain size from a two-bit addition/subtraction per logic block to an m-bit addition/subtraction. The m-bit addition is implemented by increasing the number of read-ports for a look-up table from 1 to m-2. In addition, we use a dedicated selection logic to implement an m-bit conditional addition/subtraction. The proposed architecture improves the performance of applications containing intensive arithmetic operations. We use throughout density as a cost-performance metric to justify the benefit of the new architecture and find the optimal grain size. We could achieve roughly up to 5 times larger throughput density for selected applications at the cost of 5-10% area penalty.

With the popularity of multimedia acceleration instructions such as MMX, MPEG decompression is increasingly executed on general purpose processors instead of dedicated MPEG hardware. The gap between processor speed and memory access means that a significant amount of time is spent in the memory system. As processors get faster-both in terms of higher clock speeds and increased instruction level parallelism-the time spent in the memory system becomes even more significant. Data prefetching is a well-known technique for improving cache performance. While several studies have examined prefetch strategies for scientific and commercial applications, this paper focuses on video applications. Data is presented for three types of hardware-prefetching schemes: the stream buffer, the stride prediction table (SPT), and the stream cache, as well as a new software-directed prefetching technique based on emulation of the hardware SPT. Up to 90% of the misses that would otherwise occur with no prefetching are eliminated. The stream cache can cut execution time by more than half with the addition of a relatively small amount of additional hardware. Software prefetching achieves nearly equal performance with minimal additional hardware. Techniques presented in this paper can be used to improve performance in a general-purpose CPU or an embedded MPEG processor. Performance gains achieved for MPEG benchmarks apply equally effectively to similar multimedia applications.

The evolution of microprocessor architecture depends upon the changing aspects of technology. As die density and speed increase, memory and program behavior become increasingly important in defining architecture trade-offs. While technology enables increasingly complex processor implementations, there are physical and program behavior limits to the usefulness of this complexity. Physical limits include device limits as well as practical limits on power and cost. Program behavior limits result from unpredictable events occurring during execution. Architectures and implementations that span these limits are vital to the continued evolution of the microprocessor.

The shared memory abstraction supported by hardware based distributed shared memory (DSM) multiprocessors is an inherently consumer driven means of communication. When a process requires data, it retrieves them from the global shared memory. In distributed cache coherent systems, the data may reside in a remote memory module or in the producer's cache. Producer initiated mechanisms reduce communication latency by sending data to the consumer as soon as they are produced. We classify producer initiated mechanisms as implicit or explicit, according to whether the producer must know the identity of the consumer when data are transmitted. Explicit schemes include data forwarding and message passing. Implicit schemes include update based coherence, selective updates, and cache based locks. Several of these mechanisms are evaluated for performance and sensitivity to network parameters, using a common simulated architecture and a set of application kernel benchmarks. StreamLine, a cache based message passing mechanism, provides the best performance on the benchmarks with regular communication patterns. Forwarding write and cache based locks are also among the best performing producer initiated mechanisms. Consumer initiated prefetch, however, has good average performance and is the least expensive to implement.

PAM-Blox are object-oriented circuit generators on top of the PCI Pamette design environment, PamDC. High-performance FPGA design for adaptive computing is simplified by using a hierarchy of optimized hardware objects described in C++. PAM-Blox consist of two major layers of abstraction. First, PamBlox are parameterizable simple elements such as counters and adders. Automatic placement of carry chains and flexible shapes are supported. PaModules are more complex elements possibly instantiating PamBlox. PaModules have fixed shapes and are usually optimized for a specific data-width. Examples for PaModules are multipliers, Coordinate Rotations (CORDICs), and special arithmetic units for encryption. The key difference of our approach to most other design tools for FPGAs is that the designer has total control over placement at each level of the design hierarchy, which is the key to high-performance FPGA design. Second, the object interface was chosen carefully to encourage code-reuse and simplify code-sharing between designers. PAM-Blox are intended to be part of an open library that allows design sharing between members of the adaptive computing community.

We explore the design space of field programmable gate arrays (FPGAs), processors and ASICs-hardware-software tri-design-in the framework of encryption for hand-held communication units. The IDEA (International Data Encryption Algorithm) is used to show the tradeoffs for the suggested technologies. The measures for comparing different options are: performance, programmability and power (P/sup 3/). More specifically we use the performance to power, or operations to energy ratio MOPS/Watt and Mbits/s/Watt to compare processors, FPGAs and ASICs. We compare the latest digital signal processor (DSP) from Texas Instruments to Xilinx XC4000 series FPGAs. Many DSP-like applications perform very well on FPGAs. We show the benefits and limitations of FPGA technology for IDEA.

Since integrated circuits were invented, fabrication engineers have been able to steadily decrease the dimensions of the devices (transistors). These reductions in the minimum feature sizes have resulted in improved performance. In addition, the dimensions of the interconnect used to connect the active transistors have also scaled. The decreasing dimensions of the physical devices causes the capacitance and resistances of the different parts of the multiplier to change. Therefore, the relative delay due to each part of the multiplier changes. In addition, the different encoding schemes used to generate the partial products and the different topologies used in the reduction of the partial products effect the total latency of the multiplier. This paper examines the effects of the smaller device dimensions on multipliers. It shows that the interconnect is becoming more important and that automatic generation of partial products provides the minimum latency for small feature sizes.

Addition is the most frequent floating-point operation in modern microprocessors. Due to its complex shift-add-shift-round data flow, floating-point addition can have a long latency. To achieve maximum system performance, it is necessary to design the floating-point adder to have minimum latency, while still providing maximum throughput. This paper proposes a new floating-point addition algorithm which exploits the ability of dynamically scheduled processors to utilize functional units which complete in variable time. By recognizing that certain operand combinations do not require all of the steps in the complex addition data flow, the mean latency is reduced. Simulation on SPECfp92 applications demonstrates that a speedup in mean addition latency of 1.33 can be achieved using this algorithm, while maintaining single-cycle throughput.

This paper presents an analysis of the complexity of quotient digit selection tables in SRT division implementations. SRT dividers are widely used in VLSI systems to compute floating-point quotients. These dividers use a fixed number of partial remainder and divisor bits to consult a table to select the next quotient-digit in each iteration. This analysis derives the allowable divisor and partial remainder truncations for radix 2 through radix 32, and it quantifies the relationship between table parameters and the complexity of the tables. Several techniques are presented for further minimizing table complexity. By mapping the tables to a library of standard-cells, delay and area values were measured and are presented for table configurations through radix 32. Several conclusions are drawn based on this data which impacts optimized SRT divider designs.

In recent years computer applications have increased in their computational complexity. The industry wide usage of performance benchmarks, such as SPECmarks, and the popularity of 3D graphics applications forces processor designers to pay particular attention to implementation of the floating point unit, or FPU. The paper presents results of the Stanford subnanosecond arithmetic processor (SNAP) research effort in the design of hardware for floating point addition, multiplication and division. We show that one cycle FP addition is achievable 32% of the time using a variable latency algorithm. For multiplication, a binary tree is often inferior to a Wallace tree designed using an algorithmic layout approach for contemporary feature sizes (0.3 /spl mu/m). Further, in most cases two bit Booth encoding of the multiplier is preferable to non Booth encoding for partial product generation. It appears that for division, optimum area performance is achieved using functional iteration, and we present two techniques to further reduce average division latency.

Processor cycle times are currently much faster than memory cycle times, and this gap continues to increase. Adding a high speed cache memory allows the processor to run at full speed as long as the data it needs is present in the cache. However, memory latency still affects performance in the case of a cache miss. Prediction caches use a history of recent cache misses to predict future misses and to reduce the overall cache miss rate. This paper describes several prediction caches, and introduces a new kind of prediction cache, which combines the features of prefetching and victim caching. This new cache is shown to be more effective at reducing miss rate and improving performance than existing prediction caches.

In this papel; we describe several methods which can improve the performance of the baseline H.263 encoder: All of our improvements were implemented in sofrware using the Telenor ~2.0 codec.We begin by presenting results of our optimization of the Telenor sofnvare, which reduced the computation time of the encoder by four rimes its original value.Next, we characterize individual parts of the encoder and observe how the distribution of computation time varies with input sequence and motion search type.Based on our characterization, we then propose two methods to reduce computation in the motion estimatol; discrete cosine transform, and quantizel; using a technique that detects all-zero coeficients in macrobIocks.Our combined results ultimately reduces the computational time of the original Telenor encoder by four to nine times its original value.LO repttbfkh.LO post or1 servm or lo redistribute 10 lisls, requires specific

Floating-point division is generally regarded as a low frequency, high latency operation in typical floating-point applications. However, in the worst case, a high latency hardware floating-point divider can contribute an additional 0.50 CPI to a system executing SPECfp92 applications. This paper presents the system performance impact of floating-point division latency for varying instruction issue rates. It also examines the performance implications of shared multiplication hardware, shared square root, on-the-fly rounding and conversion, and fused functional units. Using a system level study as a basis, it is shown how typical floating-point applications can guide the designer in making implementation decisions and trade-offs.

Many algorithms have been developed for implementing division in hardware. These algorithms differ in many aspects, including quotient convergence rate, fundamental hardware primitives, and mathematical formulations. The paper presents a taxonomy of division algorithms which classifies the algorithms based upon their hardware implementations and impact on system design. Division algorithms can be divided into five classes: digit recurrence, functional iteration, very high radix, table look-up, and variable latency. Many practical division algorithms are hybrids of several of these classes. These algorithms are explained and compared. It is found that, for low-cost implementations where chip area must be minimized, digit recurrence algorithms are suitable. An implementation of division by functional iteration can provide the lowest latency for typical multiplier latencies. Variable latency algorithms show promise for simultaneously minimizing average latency while also minimizing area.

Quadratically converging algorithms for high-order arithmetic operations typically are accelerated by a starting approximation. The higher the precision of the starting approximation, the less number of iterations required for convergence. Traditional methods have used look-up tables or polynomial approximations, or a combination of the two called piecewise linear approximations. This paper provides a revision and major extension to our study (1993) proposing a nontraditional method for reusing the hardware of a multiplier. An approximation is described in the form of partial product array (PPA) composed of Boolean elements. The Boolean elements are chosen such that their sum is a high-precision approximation to a high-order arithmetic operation such as square root, reciprocal, division, logarithm, exponential, and trigonometric functions. This paper derives a PPA that produces in the worst case a 16-bit approximation to the square root operation. The implementation of the PPA utilizes an existing 53 bit multiplier design requiring approximately 1,000 dedicated logic gates of function, additional repowering circuits, and has a latency of one multiplication.

SNAP-the Stanford subnanosecond arithmetic processor-is an interdisciplinary effort to develop theory, tools, and technology for realizing an arithmetic processor with execution rates under 1 ns. Specific improvements in clocking methods, floating-point addition algorithms, floating-point multiplication algorithms, division and higher-level function algorithms, design tools, and packaging technology were studied. These improvements have been demonstrated in the implementation of several VLSI designs.>

Wave-pipelining, or maximum rate pipelining, is a circuit design technique which allows digital synchronous systems to be clocked at rates higher than can be achieved with conventional pipelining techniques by relying on the predictable finite delay through combinational logic for virtual data storage. Digital system design with ubiquitous use of wave-pipelining faces significant obstacles, including: synthesis and optimization of large wave-pipelined logic structures, synchronization of multiple wave-pipelines with feedback, designing for variation in IC fabrication characteristics, and register and wave-based logic codesign. We have developed analytical models, circuit techniques, and a CMOS wave-pipelining design environment to address these obstacles. These techniques and tools were employed in the design of a CMOS vector processor unit. Wave-pipelining is used in its vector registers and multiplier and adder functional units. This VLSI design is being fabricated in a 1 micron CMOS process and has been simulated at greater than 300 MHz.

Recent simulation based studies suggest that while superpipelines and superscalars are equally capable of exploiting fine grained concurrency, multiprocessors are better at exploiting coarse grained parallelism. An analytical model that is more flexible and less costly in terms of run time than simulation, is proposed as a tool for analyzing the tradeoff between superpipelined processors, superscalar processors, and multiprocessors. The duality of superpipelines and superscalars is examined in detail. The performance limit for these systems has been derived and it supports the fetch bottleneck observation of previous researchers. Common characteristics of utilization curves for such systems are examined. Combined systems, such as superpipelined multiprocessors and superscalar multiprocessors, are also analyzed. The model shows that the number of pipelines (or processors) at which the maximum throughput is obtained is, as memory access time increases, increasingly sensitive to the ratio of memory access time to network access delay. Further, as a function of interiteration dependence distance, optimum throughput is shown to vary nonlinearly, whereas the corresponding optimum number of processors varies linearly. The predictions from the analytical model agree with similar results published using simulation based techniques.>

A 16/spl times/16-bit wave-pipelined multiplier was designed using static CMOS. Wave pipelining is achieved by applying new data to the circuit faster than the propagation delay. The circuit has been fabricated in a 1.0 /spl mu/m CMOS process and tested at 330-350 MHz, which is about 4 times faster than the maximum clock frequency without pipelining.>

Detecting independent operations is a prime objective for computers that are capable of issuing and executing multiple operations simultaneously. The number of instructions that are simultaneously examined for detecting those that are independent is the scope of concurrency detection. The authors present an analytical model for predicting the performance impact of varying the scope of concurrency detection as a function of available resources, such as number of pipelines in a superscalar architecture. The model developed can show where a performance bottleneck might be: insufficient resources to exploit discovered parallelism, insufficient instruction stream parallelism, or insufficient scope of concurrency detection. The cost associated with speculative execution is examined via a set of probability distributions that characterize the inherent parallelism in the instruction stream. These results were derived using traces from a Multiflow TRACE SCHEDULING compacting FORTRAN 77 and C compilers. The experiments provide misprediction delay estimates for 11 common application-level benchmarks under scope constraints, assuming speculative, out-of-order execution and run time scheduling. The throughput prediction of the analytical model is shown to be close to the measured static throughput of the compiler output.>

A method for obtaining high-precision approximations of high-order arithmetic operations is presented. These approximations provide an accurate starting approximation for high-precision iterative algorithms, which translates into few iterations and a short overall latency. The method uses a partial product array to describe an approximation and sums the array on an existing multiplier. By reusing a multiplier the amount of dedicated hardware is made very small. For the square-root operation, a 16-bit approximation costs less than 1000 dedicated logic gates to implement and has the latency of approximately one multiplication. This is 1/500 the size of an equivalent look-up table method and over twice as many bits of accuracy as an equivalent polynomial method. Thus, a high-precision approximation of the square root operation and many other high-order arithmetic operations is possible at low cost.>

An algorithm for high-radix nonrestoring division is proposed which combines a cost-efficient quotient estimation technique with collapsing of the division into one operation each iteration. The quotient estimation technique is a direct combinatorial algorithm which allows a more generalized partial remainder than similar studies. In addition, the successor partial remainder is calculated directly from the previous partial remainder. The intermediate steps of calculating the next quotient estimate, multiplying it by the divisor, and then subtracting the result from the previous remainder are telescoped into one step. This is possible due to the use of simple direct combinatorial equations for the quotient estimate. Thus, one operation is used to generate the next remainder from the previous remainder. This operation is similar to a multiplication with a reduced carry propagate adder. This algorithm reduces the latency of each iteration to less than the delay of one multiplication. Thus, high-radix nonrestoring division is possible with a low latency and no need for an off-chip ROM to hold a quotient estimate.>

Algorithms to automatically realize delays in combinational logic circuits to achieve wave pipelining are presented. The algorithms adjust gate speeds and insert a minimal number of active delay elements to balance input-output path lengths in a circuit. For both normal and wave-pipelined circuits, the algorithms also optimally minimize power under delay constraints. The authors analyze the algorithms and comment on their implementation. They report experimental results, including the design and testing of a 63-bit population counter in CML bipolar technology. A brief analysis of circuit technologies shows that CML and super-buffered ECL without stacked structures are well suited for wave pipelining because they have uniform delay. Static CMOS and ordinary ECL including stacked structures and emitter-followers do have some delay variations. A high degree of wave pipelining is still possible in those technologies if special design techniques are followed.>

The tradeoff between visualizing or hiding the highest levels of the memory hierarchy, which impacts both performance and scalability, is examined by comparing a set of architectures from three major architecture families: stack, register, and memory-to-memory. The stack architecture is used as reference. It is shown that scalable architectures require at least 32 words of local memory and therefore are not applicable for low-density technologies. It is also shown that software support can bridge the performance gap between scalable and nonscalable architectures. A register architecture with 32 words of local storage allocated interprocedurally outperforms scalable architectures with equal sized local memories and even some with larger sized local memories. When a small cache is added to an unscalable architecture, their performance advantage becomes significant.>

A fully static complementary metal-oxide semiconductor (CMOS) implementation of a Ling-type 32-bit adder is described. The implementation saves up to one gate delay and always reduces the number of serial transistors in the worst-case critical path over the conventional carry look-ahead (CLA) approach with a negligible increaser in hardware.>

A class of iterative integer division algorithms is presented based on look-up table and Taylor-series approximations to the reciprocal. The algorithm iterates by using the reciprocal to find an approximate quotient and then subtracting the quotient multiplied by the divisor from the dividend to find a remaining dividend. Fast implementations can produce an average of either 14 or 27 b per iteration, depending on whether the basic or advanced version of this method is implemented. Detailed analyses are presented to support the claimed accuracy per iteration. Speed estimates using state-of-the-art ECL components show that this method is faster than the Newton-Raphson technique and can produce 53-b quotients of 53-b numbers in about 25 ns using the basic method and 21 ns using the advanced method. In addition, these methods naturally produce an exact remainder, which is very useful for implementing precise rounding specifications.>

A class of iterative integer division algorithms is presented based on lookup table Taylor-series approximations to the reciprocal. The algorithm iterates by using the reciprocal to find an approximate quotient and then subtracting the quotient multiplied by the divisor from the dividend to find a remaining dividend. Fast implementations can produce an average of either 14 or 27 b per iteration, depending on whether the basic or advanced version of this method is implemented. Detailed analyses are presented to support the claimed accuracy per iteration. Speed estimates using state-of-the-art ECL (emitted coupled logic) components show that this method is faster than the Newton-Raphson technique and can produce 53-b quotients of 53-b numbers in about 28 or 22 ns for the basic and advanced versions.>

Achieving high instruction issue rates depends on the ability to dynamically predict branches. We compare two schemes for dynamic branch prediction: a separate branch target buffer and an instruction cache based branch target buffer. For instruction caches of 4KB and greater, instruction cache based branch prediction performance is a strong function of line size, and a weak function of instruction cache size. An instruction cache based branch target buffer with a line size of 8 (or 4) instructions performs about as well as a separate branch target buffer structure which has 64 (or 256, respectively) entries. Software can rearrange basic blocks in a procedure to reduce the number of taken branches, thus reducing the amount of branch prediction hardware needed. With software assistance, predicting all branches as not branching performs as well as a 4 entry branch target buffer without assistance, and a 4 entry branch target buffer with assistance performs as well as a 32 entry branch target buffer without assistance. The instruction cache based branch target buffer also benefits from the software, but only for line sizes of more than 4 instructions.

The search for efficient methods of computer simulanode updates per second (NUPS), about 600 times the performance of CRAY-2.A prototype of the key processing element has been implemented.

The authors provide a common platform for modeling different schemes for reducing the branch-delay penalty in pipelined processors as well as evaluating the associated increased instruction bandwidth. Their objective is twofold: to develop a model for different approaches to the branch problem and to help select an optimal strategy after taking into account additional i-traffic generation by branch strategies. The model presented provides a flexible tool for comparing different branch strategies in terms of the reduction it offers in average branch delay and also in terms of the associated cost of wasted instruction fetches. This additional criterion turns out to be a valuable consideration in choosing between two strategies that perform almost equally. More importantly, it provides a better insight into the expected overall system performance. Simple compiler-support-based low-implementation-cost strategies can be very effective under certain conditions. An active branch prediction scheme based on loop buffers can be as competitive as a branch-target-buffer based strategy.>

The relative amount of instruction traffic for two architectures is about the same in the presence of a large cache as with no cache. Furthermore, the presence of an intermediate-sized cache probably substantially favors the denser architecture. Encoding techniques have a much greater impact on instruction traffic than do the differences between instruction set families such as stack and register set. However, register set architectures have somewhat lower instruction traffic than directly comparable stack architectures of some local variables are allocated in registers. This study has clearly indicated that cache factors should be taken into consideration when making architectural tradeoffs. The differences in memory traffic between two architectures may be greatly amplified in the presence of a cache.

Wave pipelining is a technique for pipelining digital systems that can increase the clock frequency without increasing the number of storage elements. Due to limits and variations in fabrication, the clock frequency can be increased by a factor of 2 to 3 by using the best available design methods. The authors present algorithms that will equalize delays automatically by inserting a minimal number of active delay elements to lengthen short paths. This method can be combined with delay balancing by adjusting gate speeds to design wave-pipelined circuits.>

The authors describe a high performance 32-bit binary adder designed at Stanford University. Measurements indicate that the adder computes the sum of two numbers (and a carry) in 2.1 ns and consumes 900 mW, using a power-supply voltage of -4.5 V. The adder is implemented using silicon emitter-coupled-logic circuitry with 0.5-V output swings. The high performance is a result of high-speed logic/technology and a special addition algorithm which results in an adder with a maximum of three levels of logic from any input to any output. The maximum fanout on any signal is eight input loads, the maximum number of inputs on any gate is five, and the maximum number of WIRE-OR outputs is eight.>

Central to instruction set design is the issue of the instruction format. We discuss some common format encoding techniques, and introduce a method of representing high-level language parse trees by means of formats that cover successively larger portions of a tree. We then introduce variations on the method that represent directed acyclic graphs as well as simple parse trees, and that encode constants in a special fashion. For a particular representation, we measure the number of times each format is executed to run a sample program to completion.

Execution architectures include Directly Executed Languages, or DEL's, which are tailored to particular combinations of software and hardware technologies. In this paper, we review the general notion of DEL's, and show how they compare to traditional instruction set architectures. We focus on general techniques for synthesizing DEL's rather than performance questions per se, however. There are four aspects to this design problem: Naming: relating identifiers to objects. Formatting: associating objects to arguments/results. Control: specifying the order of interpretation. Function: operating on objects identified by the naming and format mechanisms, in the order specified by the control mechanism.

A hierarchical view of program representation is used to explain the problems of matching various representations to underlying distributed architectures. If a program is to effectively use a distributed computer system, it is necessary to represent and detect a high degree of parallelism. Methods of detecting such parallelism and their limitations are discussed. The actual machine level representation of a high-level language program also affects the ability to achieve a good match between the computer system resources and the program. The concept of an ideal machine for the program leads naturally to a representation employing a directly executed language. The initial program representation profoundly influences the possibility of obtaining a good representation at other levels of the hierarchy. A poor initial language representation leads to unnecessary architectural contraints or insufficient information to efficiently execute a program. The issue of suitable initial representation for distributed hardware is approached employing a functional language basis.

In this paper we examine the capabilities and limitations of Petri nets and investigate techniques for proving their correctness. We define different classes of nets where each is basically a Petri net with slight modifications and study the relationship between the various classes. One particular class appears to be quite powerful, with respect to its capability for representing coordinations. In the second part of the paper we establish the feasibility of using the methods of computational induction and inductive assertions to prove restricted statements about Petri nets.

A measure of the minimum cost of a logical network is important in the evaluation of such networks. A hypothesis is investigated which states that the average minimum cost depends on both the number of input variables and the entropy (``entropy'' in this sense is based on the probability of a ``1'' in the functions' truth table) of the function realized. Some experimental results are presented to support the hypothesis.

A formal technique for the representation of tasks such that the potential concurrency of the task is detectable, and hence exploitable, during the execution of the task is described. Instructions are represented as a pair of binary vectors d and ê which completely describe the sources and sinks specified by the instruction. Tasks are represented as square matrices M called ordering matrices. The values of the elements of these matrices are used to dynamically indicate the necessary ordering of the execution of instructions. It is shown how several different types of ordering matrices, each type having the capability of exhibiting different amounts of potential concurrency, can be calculated from the d and ê vectors of the instructions of a task using ``linear algebraic-like'' operations. For example, intercycle independencies can be detected with a ternary ordering matrix. This matrix can be extended to dynamically detect opportunities for reassigning the resources specified by certain instructions to increase the amount of potential concurrency. Experimental results are presented showing the relative capability of each of these matrix types for exhibiting potential concurrency. These techniques are shown to produce somewhat greater amounts of potential concurrency than other known dynamic techniques. However, the amounts of potential concurrency found are less than those reported for preprocessing detection techniques.

Two addition and three multiplication algorithms were studied to see the effect of pipelining on system efficiency. A definition of efficiency was derived to compare the relative merits of various algorithms and implementations for addition and multiplication. This definition is basically defined as bandwidth/cost. Previous comparisons of adders and multipliers have generally been based on latency. In a pipeline environment, latency (or its Inverse bandwidth) is not as important. Any bandwidth is possible up to the physical limitations on gate delay variations and pulse skew. The formal definition for efficiency is: Efficiency = N / D · G where N is the number of bits in the operands, D is the delay (uniform) of each pipeline stage in units of gate delays and G is the total number of gates, including any used for latching. In cases where gate variations and pulse skewing are well defined pipelining using the Earle latch results in increased efficiency. The most efficient adder is a maximally pipelined conditional-sum adder (3 stages with a delay of 4 gates per stage). Its efficiency is 6.30×10-3. The most efficient multiplier is a maximally pipelined tree multiplier (8 stages with a delay of 4 gates per stage). It efficiency is 3.48×10-4.

This book represents a major contribution to the study of the architecture of computer systems. It will be, I believe, must reading for any serious student of the field.

A hierarchical model of computer organizations is developed, based on a tree model using request/service type resources as nodes. Two aspects of the model are distinguished: logical and physical. General parallel- or multiple-stream organizations are examined as to type and effectiveness-especially regarding intrinsic logical difficulties. The overlapped simplex processor (SISD) is limited by data dependencies. Branching has a particularly degenerative effect. The parallel processors [single-instruction stream-multiple-data stream (SIMD)] are analyzed. In particular, a nesting type explanation is offered for Minsky's conjecture-the performance of a parallel processor increases as log M instead of M (the number of data stream processors). Multiprocessors (MIMD) are subjected to a saturation syndrome based on general communications lockout. Simplified queuing models indicate that saturation develops when the fraction of task time spent locked out (L/E) approaches 1/n, where n is the number of processors. Resources sharing in multiprocessors can be used to avoid several other classic organizational problems.

Two addition and three multiplication algorithms were studied to see the effect of pipelining on system efficiency. A definition of efficiency was derived to compare the relative merits of various algorithms and implementations for addition and multiplication. This definition is basically defined as bandwidth cost. Previous comparisons of adders and multipliers have generally been based on latency. In a pipeline environment, latency (or its inverse bandwidth) is not as important. Any bandwidth is possible up to the physical limitations on gate delay variations and pulse skew. The formal definition for efficiency is efficiency = N/D·G where N is the number of bits in the operands, D is the delay (uniform) of each pipeline stage in units of gate delays, and G is the total number of gates, including any used for latching. In cases where gate variations and pulse skewing are well defined, pipelining using the Earle latch results in increased efficiency. The most efficient adder is a maximally pipelined conditional-sum adder (three stages with a delay of four gates per stage). Its efficiency is 6.30×10-3. The most efficient multiplier is a maximally pipelined tree multiplier (eight stages with a delay of four gates per stage). Its efficiency is 3.48×10-4.

The two broad aspects of microprogramming that are addressed in this issue are:microprogramming as a technological tool used to define and establish system control, and the application of microprogramming in the effective realization of computer systems.

Dynamic microprogramnming (i. e., utilizing a READ/ WRITE microstorage) allows the structure of a computer to be altered to suit a problem at hand and results in major efficiencies (an order of magnitude) in running time for nonarithmetic programs (e. g., compilers).

In order to avoid the time delays associated with linearly convergent division based on subtraction, other iterative schemes can be used. These are based on 1) series expansion of the reciprocal, 2) multiplicative sequence, or 3) additive sequence convergent to the quotient. These latter techniques are based on finding the root of an arbitrary function at either the quotient or reciprocal value. A Newton-Raphson iteration or root finding iteration can be used.

For a single instruction stream–single data stream organization the problem of simultaneously issuing several instructions is studied.

Many medium-scale electronic computers currently are being designed to cater to scientific and business data-processing problems. Efficiency of floating point computation for scientific problems usually favors a fixed-word format and a word-oriented memory, so that a complete floating-point operand may be read out of or stored in memory in parallel. The logical processing of strings of characters not starting or ending on a word boundary, or the arithmetic processing of variable field-length fixed-point operands, are penalized. The penalty is the result of time-consuming combinations of masking and/or shifting which must be programmed before or after processing and before results can be stored. The purpose of this report is to describe several representative memory-access systems that avoid the housekeeping necessary for processing variable-length operands in a fixed word-length machine and to evaluate their relative efficiencies.