The problem of minimizing power consumption during the state encoding of a finite-state machine is addressed. A new power cost model for state encoding is proposed, and encoding techniques that minimize this power cost for two- and multilevel logic implementations are described. These techniques are compared with those that minimize area or the switching activity at the present state bits. Experimental results show significant improvements.

This paper addresses the problem of state assignment for large Finite State Machines (FSM).This is an important problem in the high performance digital system design where added functionality often comes at the expense of a larger (and slower) FSM to control the system.We present a new method to solve the graph embedding problem which is the main step in the state assignment process.The basic idea is to place the state adjacency graph in a two-dimensional grid while minimizing the total wire length.The grid is then mapped into an n-dimensional hypercube while nearly preserving the adjacency relations that is with dilation at most 2. Experimental results are presented and compared with those of NOVA.

This paper addresses the problem of partitioning a large PLA into a number of smaller PLA's (sub-PLA's) such that the total area of these sub-PLA's is minimum and the cycle time of the partitioned circuit is minimized. First, we describe an iterative improvement method that deals with the case that sub-PLA's assume arbitrary sizes. Second, we present a partitioning technique based on fuzzy logic that deals with the case that the sizes of the sub-PLA's are fixed. Finally, we describe a method that considers not only delay through each sub-PLA, but also loading of sub-PLA's on the stage that is driving them. These techniques have been implemented and significantly outperformed conventional PLA partitioning schemes.

In this paper we describe the design and implementation of a 190-MHz pipelined 4-Kbyte instruction and data cache. The caches are designed in 1.0-µm CMOS and measure 0.78 x 0.47 cm 2 . This paper describes the microarchitecture, cache timing, circuit implementation, and layout of both the instruction and the data cache. The key features of these caches are pipelined execution and the use of dynamic single-phase clock logic. We discuss the interface of this cache with the processor core and the off-chip controller. This paper also describes the pipelined structure of the cache and the miss detection and handling logic. Published in ISCAS `95, Seattle 1 ABSTRACT In this paper we describe the design and implementation of a 190-MHz pipelined 4-Kbyte instruction and data cache. The caches are designed in 1.0-µm CMOS and measure 0.78 x 0.47 cm 2 . This paper describes the microarchitecture, cache timing, circuit implementation, and layout of both the instruction and the data cache. T...

In instruction set serves as the interface between hardware and software in a computer system. In an application specific environment, the system performance can be improved by designing an instruction set that matches the characteristics of hardware and the application. We present a systematic approach to generate application-specific instruction sets so that software applications can be efficiently mapped to a given pipelined micro-architecture. The approach synthesizes instruction sets from application benchmarks, given a machine model, an objective function, and a set of design constraints. In addition, assembly code is generated to show how the benchmarks can be compiled with the synthesized instruction set. The problem of designing instruction sets is formulated as a modified scheduling problem. A binary tuple is proposed to model the semantics of instructions and integrate the instruction formation process into the scheduling process. A simulated annealing scheme is used to solve for the schedules. Experiments have shown that the approach is capable of synthesizing powerful instructions for modern pipelined microprocessors, and running with reasonable time and a modest amount of memory for large applications.>

Recently developed methods for power estimation have primarily focused on combinational logic. We present a framework for the efficient and accurate estimation of average power dissipation in sequential circuits. Switching activity is the primary cause of power dissipation in CMOS circuits. Accurate switching activity estimation for sequential circuits is considerably more difficult than that for combinational circuits, because the probability of the circuit being in each of its possible states has to be calculated. The Chapman-Kolmogorov equations can be used to compute the exact state probabilities in steady state. However, this method requires the solution of a linear system of equations of size 2/sup N/ where N is the number of flip-flops in the machine. We describe a comprehensive framework for exact and approximate switching activity estimation in a sequential circuit. The basic computation step is the solution of a nonlinear system of equations which is derived directly from a logic realization of the sequential machine. Increasing the number of variables or the number of equations in the system results in increased accuracy. For a wide variety of examples, we show that the approximation scheme is within 1-3% of the exact method, but is orders of magnitude faster for large circuits. Previous sequential switching activity estimation methods can have significantly greater inaccuracies.>

This paper focuses on the issues of designing an optimal superpipelined ISP (instruction set processor) driven by a set of benchmark programs. Most issues discussed in this paper also apply to VLIW and superscalar processors.>

We present a systematic approach to synthesize an instruction set such that the given application software can be efficiently mapped to a parameterized, pipelined microarchitecture. In addition, the assembly code is generated to show how the application can be compiled with the synthesized instruction set. The design of instruction sets is formulated as a modified scheduling problem. A binary tuple is proposed to model the semantics of instructions and integrate the instruction formation process into the scheduling process. A simulated annealing scheme is used to solve for the schedules. Experiments have shown that the approach is capable of synthesizing powerful instructions for modern pipelined microprocessors. The synthesis algorithm ran with reasonable time and a modest amount of memory for large benchmarks. 1.

In this paper, we consider the problem of calculating the signal and transition probabilities of the internal nodes of the combinational logic part of a finite state machine (FSM). Given the state transition graph (STG) of the FSM, we first calculate the state probabilities by iteratively solving the Chapman-Kolmogorov equations. Using these probabilities, we then calculate the exact signal and transition probabilities by an implicit state enumeration procedure. For large sequential machines where the STG cannot be explicitly built, we unroll the next state logic k times and estimate the signal probability of the state bits using an OBDD-based approach. The basic computation step consists of solving a system of non-linear equations. We then use these estimates to approximately calculate signal and transition probabilities of the internal nodes. Our experimental results indicate that the average errors of transition probabilities and power estimation(compared to the exact method) are on...

This paper presents a study of cache hashing functions for micro-parallel processors (e.g., superpipeline and super-scalar processors). Several novel cache hashing functions are experimented. Our simulation results show that an unconventional cache hashing function applied on a direct-mapped cache results in hit rates as good as a two-way set associative cache with traditional mapping, while the cache hit times are as fast as a direct-mapped cache with traditional mapping.

The performance of a superpipeline processor heavily relies on its branch performance. Traditional branch strategies used in pipelined processors are delayed branches and branch with squashing. Delayed branches use safe instructions to fill delay slots. However, for a deeply pipelined processor, a compiler may not be able to find sufficient safe instructions to fill the branch delay slots. Branch with squashing takes advantage of using instructions in target basic blocks to fill the branch delay slots. However, the penalty of branch misprediction is large in superpipelined processors. The authors propose a novel branch scheme, named branch with masked squashing, which takes advantage of both delayed branch and branch with squashing. The basic idea is to fill delay slots with safe instructions which may come from above or after the branch. For the remaining unfilled delay slots, the authors fill with instructions from the predicted target path. In the case of misprediction, only unsafe instructions are annulled. The safe instructions in branch delay slots are always executed. Simulation results show that this branch strategy performs better than traditional delayed branch and branch with squashing.>

Branch misprediction penalties depend on branch misprediction rates and branch penalties. Dynamic branch schemes take advantage of hardware to record and predict branch behavior at run-time for reducing branch misprediction rates. Static branch schemes take advantage of scheduling safe instructions into branch delay slots at compile-time for reducing branch penalties. This paper evaluates and compares the performance of various state-of-the-art static and dynamic branch schemes for super-pipelined processors.

We propose a new power consumption model that accounts for the power consumption at the internal nodes of a CMOS gate. Next, we address the problem of minimizing the average power consumption during the technology dependent phase of logic synthesis. Our approach consists of two steps. In the first step, we generate a NAND decomposition of an optimized Boolean network such that the sum of average switching rates for all nodes in the network is minimum. In the second step, we perform a power efficient technology mapping that finds a minimal power mapping for given timing constraints (subject to the unknown load problem).>

In his paper, we address the problem of minimizing the average power dissipation during the technology dependent phase of logic synthesis. Our approach consists of two steps. In the first step, we generate a Nand decomposition of an optimized Boolean network such that the sum of average switching rates for all nodes in the network is minimum. Our power-efficient decomposition procedure is optimal for dynamic CMOS circuits with uncorrelated input signals and produces very good results for static CMOS. In the second step, we perform a power efficient technology mapping that finds an optimal power delay trade-off value (subject to the unknown load problem) four given timing constraints. We obtain an average of 21% improvement in power at the expense of 12.6% increase in area and without any degradation in performance on a number of benchmarks.

One major problem in pipeline synthesis is the detection and resolution of pipeline hazards. We present a new solution to the problem in the domain of pipelined application-specific instruction set processors, based on hardware/software concurrent engineering approach. An extended taxonomy of inter-instruction dependencies is proposed for the analysis of pipeline hazards. Hardware/software resolution candidates are then associated with these dependencies. Algorithms using the taxonomy and the resolutions are developed to detect and resolve pipeline hazards, and to explore the hardware and software design space. Application benchmarks are used to evaluate the designs and guide the design decision. The power of these tools are demonstrated through the pipeline synthesis of two processors including industrial one. Compared with other approaches, our method achieves higher throughput, and provides a way to explore the hardware/software tradeoff. Our method can be combined with current approaches to achieve even higher performance since they are orthogonal.

In CMOS circuits, glitches account for a sizeable part of the total power consumption. In this paper, we present a fast and memory efficient power estimation technique for CMOS circuits which estimates the power consumed due to the glitches. Our technique is based on the notion of tagged transition waveforms. In particular, we approximate the correlation between transition waveforms for two signal lines by the correlation between the steady state values of these lines. We obtain an order of magnitude speed up over an exact method with an average error of only 1%.

Several architectural innovations intended to reduce access latency and improve overall throughput increase system bandwidth requirements. Bandwidth scales with clock speed, and can be regarded as an architectural resource to be applied to latency reduction. A properly designed bus provides low arbitration latency and delivers high sustained bandwidth. The paper evaluates the performance of 3.2 Gbyte/s peak bandwidth, low-latency arbitration bus connecting a GaAs superscalar CPU to a GaAs memory management unit. A microarchitectural performance model was written in the Verilog hardware description language. Bus transactions characteristic of the SPECint92 benchmarks and other workloads were generated as input. Sustained bandwidths of 1.68 Gbytes/s were achieved with arbitration costs of less than 0.5 cycles per data transfer.>

Presents a novel mechanism that implements register renaming, dynamic speculation and precise interrupts. Renaming of registers is performed during the instruction fetch stage instead of the decode stage, and the mechanism is designed to operate in parallel with the tag match logic used by most cache designs. It is estimated that the critical path of the mechanism requires approximately the same number of logic levels as the tag match logic, and therefore should not impact cycle time.>

Clocked (synchronous) and self-timed (asynchronous) methodologies represent the two principal design approaches associated with timing control and synchronization of digital systems. In the paper, clocked and asynchronous instruction pipelines are modeled and compared. The approach which yields the best performance is dependent on technology parameters, operating range and pipeline algorithm characteristics. Design curves are presented which permit selection of the best approach for a given application and technology environment.>

This paper reviews past attempts to systematize in-struction set design and offers an alternative approach. Our technique is based on compaction of microopera-tions to form instructions. The compaction is done in such a way as to optimize a metric which is a function of cycle count, code size, and instruction set size. To illus-trate our technique, optimal instruction sets are derived for data structure creation in Prolog. 1

Most Prolog machines have been based on specialized architectures. Our goal is to start with a general purpose architecture and determine a minimal set of extensions for high performance Prolog execution. We have developed both the architecture and optimizing compiler simultaneously, drawing on results of previous implementations. We find that most Prolog specific operations can be done satisfactorily in software; however, there is a crucial set of features that the architecture must support to achieve the best Prolog performance. The emphasis of this paper is on our architecture and instruction set. The costs and benefits of the special architectural features and instructions are analyzed. Simulated performance results are presented and indicate a peak compiled Prolog performance of 3.68 million logical inferences per second.

Performance results are presented for a parallel execution model for Prolog that supports AND-parallelism, OR-parallelism, and intelligent backtracking. The results show that restricted AND-parallelism is of limited benefit for small programs, but produced speedups from 7-10 on two large programs. OR-parallelism was found to be generally not useful for the benchmarks examined if the semantics of Prolog were preserved. Of particular interest is the phenomenon of super-multiplicative behavior, in which the performance improvement obtained when more than one technique is used is greater than the product of the performance improvements due to each technique individually. The implications of the performance results for parallel Prolog systems are discussed, and directions for future work are indicated.>

Performance of high-speed multiprocessor systems is limited by the available bandwidth to memory and the need to synchronize write sharable data. This paper presents a new memory system that separates synchronization related data from others. The memory system has two tiers: synchronization memory and high bandwidth (HB) memory. The synchronization memory consists of snooping caches connected to a bus and is used to store synchronization variables such as locks and semaphores. The HB memory is used to store the bulk of the application program code and data. It contains caches and a high bandwidth interconnection network to memory, such as the crossbar, but does not have full snooping among caches.The two tier memory system has been evaluated by analyzing the memory behavior of the simulated parallel execution of Prolog programs. Initial results indicate that the two tier memory system potentially reduces memory interference and speeds up synchronization. Three different schemes have been studied for the caches on the HB memory and the results are presented. The two-tier memory system has potential applications in areas where synchronization is light to medium and local data is often accessed.

This paper presents a new multiprocessor architecture for the parallel execution of logic programs, developed as part of the Aquarius Project. This architecture is designed to support AND-parallelism, OR-parallelism, and intelligent backtracking. We present the most comprehensive experimental results available to date on combined AND-parallelism, OR-parallelism, and intelligent backtracking in Prolog programs. Simulation results indicate that most Prolog programs in use today cannot effectively make use of multiprocessing.

The MOST program chooses appropriate sizes for transistors in a VLSI schematic to meet specified delay criteria. A simulated annealing algorithm is used in conjunction with a timing analyzer, both written in Prolog. A screening function takes advantage of the symbolic equations provided by the timing analyzer to reject clearly inappropriate choices, so full timing analysis is performed less frequently. Despite running in an interpreted Prolog, performance gains of over 50% versus an unsized circuit can be attained in less than 10 CPU minutes.

Many options are possible in a cache synchronization (or consistency) scheme for a broadcast system. We clarify basic concepts, analyze the handling of shared data, and then describe a protocol that we are currently exploring. Finally, we analyze the evolution of options that have been proposed under write-in (or write-back) policy. We show how our protocol extends this evolution with new methods for efficient busy-wait locking, waiting, and unlocking. The lock scheme allows locking and unlocking to occur in zero time, eliminating the need for test-and-set. The scheme also integrates processor atomic read-modify-write instructions and programmer/compiler busy-wait-synchronized operations under the same mechanism. The wait scheme eliminates all unsuccessful retries from the bus, and allows a process to work while waiting.

article Free Access Share on Performance studies of a Prolog machine architecture Authors: T. P. Dobry Computer Science Division, University of California,Berkeley, Berkeley, California Computer Science Division, University of California,Berkeley, Berkeley, CaliforniaView Profile , A. M. Despain Computer Science Division, University of California,Berkeley, Berkeley, California Computer Science Division, University of California,Berkeley, Berkeley, CaliforniaView Profile , Y. N. Patt Computer Science Division, University of California,Berkeley, Berkeley, California Computer Science Division, University of California,Berkeley, Berkeley, CaliforniaView Profile Authors Info & Claims ACM SIGARCH Computer Architecture NewsVolume 13Issue 3June 1985 pp 180–190https://doi.org/10.1145/327070.327161Published:01 June 1985Publication History 60citation339DownloadsMetricsTotal Citations60Total Downloads339Last 12 Months35Last 6 weeks7 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In some signal processing applications, it is desirable to build very high performance fast Fourier transform (FFT) processors. To meet the performance requirements, these processors are typically highly pipelined. Until the advent of VLSI, it was not possible to build a single chip which could be used to construct pipeline FFT processors of a reasonable size. However, VLSI implementations have constraints which differ from those of discrete implementations, requiring another look at some of the typical FFT'algorithms in the light of these constraints.

A new method of deriving very fast Fourier transform (FFT) algorithms is described. The resulting algorithms do not employ multiplication and have a form suitable for high performance hardware implementations. The complexity of the algorithms compares favorably to the recent results of Winograd [1].

The problem of organizing multiple, monolithic microprocessors into an effective general purpose computer structure is examined. A tree structure with extra interconnections was found to be especially attractive. It provides a structured hierarchy for control, addressing and message routing. More important, it appears to provide a mechanism to automatically migrate data abstractions and processes over the network of processors. The network can be expanded to any desired size and no global control or routine mechanisms are needed.

The CORDIC iteration is applied to several Fourier transform algorithms. The number of operations is found as a function of transform method and radix representation. Using these representations, several hardware configurations are examined for cost, speed, and complexity tradeoffs. A new, especially attractive FFT computer architecture is presented as an example of the utility of this technique. Compensated and modified CORDIC algorithms are also developed.