DOC PREVIEW
COMPILED

This preview shows page 1-2-3-4-5-6 out of 17 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

COMPILED UNIT-DELAY SIMULATION FORCYCLIC CIRCUITSPeter M. MaurerDepartment of Computer Science and EngineeringUniversity of South FloridaTampa, FL 33620COMPILED UNIT-DELAY SIMULATION FORCYCLIC CIRCUITSABSTRACTThree techniques are presented for handling cyclic circuits in a compiled unit-delaysimulation. These techniques are based on the PC-set Method and the Parallel Techniqueof compiled unit-delay simulation. The first technique, called the Synchronous ParallelTechnique, is applicable only to synchronous circuits, but provides significant performanceimprovements over interpreted unit-delay simulation. The second and third techniques,called the Convergence Algorithm and the Asynchronous Parallel Technique, are applicableto all circuits, both synchronous and asynchronous. The Convergence Algorithm, which isbased on the PC-set Method, provides significant performance increases for some circuits,but performs poorly on others. The Asynchronous Parallel Technique performs ratherpoorly and is covered only briefly.COMPILED UNIT-DELAY SIMULATION FORCYCLIC CIRCUITS1. Introduction.Recent research in compiled simulation has provided a wide variety of techniques thatcan be used at different levels of the design hierarchy [1-9]. Traditionally, compiledsimulation has focused on the zero-delay model [5-7], but there are also several techniquesthat are based on the unit-delay model [1-4]. Existing simulation techniques fall into twobroad categories which can be termed "dynamic" and "oblivious." With dynamictechniques, the number of gates simulated varies from input vector to input vector based onboth the content of the vectors and the values obtained from simulating various gates, whilewith oblivious techniques, the number of gates simulated per vector is constant. By far themost common dynamic technique is event-driven simulation.Compiled unit-delay simulation has been implemented using both dynamictechniques [1,2] and oblivious techniques [3,4]. Two oblivious techniques are the PC-setmethod and the parallel technique [3]. Because both of these techniques are based on thewell-known concept of levelization, [10] they are restricted to acyclic circuits. The purposeof this paper is to extend these techniques to cyclic circuits.Cyclic circuits fall into two distinct categories, synchronous and asynchronous.Although synchronous circuits tend to be more important for modern-day VLSI design, theability to handle asynchronous circuits is still important. In this paper we present threetechniques, one of which is applicable only to synchronous circuits, and the other two ofwhich are applicable to both synchronous and asynchronous circuits. The first techniqueextends the Parallel Technique to synchronous sequential circuits, while the second andthird techniques extend the PC-set method and the Parallel Technique to asynchronouscyclic circuits. It should be noted that it is impossible to handle asynchronous circuits in astrictly oblivious manner, and that neither of the asynchronous techniques presented hereare truly oblivious. As Section 3 shows, some sensitivity to changes in the network isnecessary to obtain reasonable performance on asynchronous circuits.2. The Synchronous Parallel Technique.The parallel technique of compiled unit-delay simulation is fully described in [3], butfor the sake of completeness, a short description of the technique is included here. Thefirst step in the parallel technique is to levelize the circuit and determine its depth, which isthe total number of levels in the circuit. A bit-field, whose width is equal to the depth of2the circuit, is allocated for every net in the circuit. The bit-fields are mapped into 32-bitwords, and appropriate variables are generated, initialization code is generated for each netin the circuit, and finally code is generated for each gate in levelized order.Each bit in a bit-field corresponds to one instant of simulated time. The low-order bitrepresents time zero, the time at which primary inputs are assumed to change. (Because ofthe unit-delay assumption, no other net is permitted to change at time zero.) Times increasesequentially as one moves to the left. Figure 1 illustrates a typical bit-field for a circuit ofdepth d.012dTIMEFigure 1. A Typical Bit-Field.After a vector is simulated, the bit-field will contain a complete history of the value of anet during the simulation of the vector. For nets that are not primary inputs, theinitialization code copies the final value of the net (which is contained in the high-order bit)into the low-order bit, which represents the initialization value of the net. For primaryinputs, the net-value obtained from the input vector is replicated throughout every bit of thebit-field. Simulation code for a gate consists of bit-parallel logical operations which arereplicated for each 32-bit word in the bit-field. Because of the delay of the gate, the resultof these operations is a bit-field whose low-order bit corresponds to time one rather thantime zero. To align the intermediate result with the bit-field of the output net, it is necessaryto shift the intermediate result to the left one bit. The low-order word of the intermediateresult must be ORed with the low-order word of the net to preserve the time-zero bit. It ispossible to improve the speed of the parallel technique by using different alignments fordifferent nets, thereby eliminating some of the shift operations For a more completeexplanation of this technique, see [3] and [4].2.1. The Changes in the Algorithm.The first step in compiling a synchronous cyclic circuit is to convert it into an acycliccircuit so it can be levelized. Since the circuit is assumed to be synchronous, every cyclemust contain at least one clocked flip-flop. Furthermore, these flip-flops must either beedge-triggered with respect to the clock, or the circuit must be designed in such a way thatthe data inputs of the flip-flop do not change while the clock is active. This allows the3circuit to be broken at the flip-flops, thus converting the circuit to an acyclic circuit that canbe levelized.Although the procedure for converting a cyclic synchronous circuit to an acyclic circuitis straightforward, it is not obvious exactly how this should be done. First, does onesimulate the flip-flop before or after the rest of the circuit? As a practical matter, it isnecessary to break the nets that are attached to a flip flop rather than the flip-flop itself.However,


COMPILED

Download COMPILED
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view COMPILED and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view COMPILED 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?