Title of Invention

A METHOD FOR DESIGNING A SYNCHRONOUS DIGITAL SYSTEM

Abstract A method for specifying and synthesizing a synchronous digital circuit by first accepting a specification of an asynchronous system in which stored values are updated according to a set of state transition rules. For instance, the state transition rules are specified as a Term Rewriting System (TRS) in which each rule specifies a number of allowable state transitions, and includes a logical precondition on the stored values and a functional specification of the stored values after a state transition in terms of the stored values prior to the state transition. The specification of the asynchronous circuit is converted into a specification of a synchronous circuit in which a number of state transitions can occur during each clock period. The method includes identifying sets of state transitions, for example by identifying sets of TRS rules, that can occur during a single clocking period and forming the specification of the synchronous circuit to allow any of the state transitions in a single set to occur during any particular clocking period.
Full Text FORM 2
THE PATENTS ACT 1970
[39 OF 1970]
COMPLETE SPECIFICATION
[See Section 10]
"SYNCHRONOUS CIRCUIT SYNTHESIS USING AN ASYNCHRONOUS SPECIFICATION"
MASSACHUSETTS INSTITUTE OF TECHNOLOGY, a State of Incorporation of Massachusetts, of 77 Massachusetts Avenue, Cambridge, Massachusetts 02142-1324, United States of America,
The following specification particularly describes and ascertain the nature of the invention and the manner in which it is to be performed:-


WO.01/13285 ■ PCT/USOO/22888 •
SYNCHRONOUS CIRCUIT SYNTHESIS --USlNG AN ASYNCHRONOUS
• SPECIFICTION
Background
This invention relates to design and synthesis of synchronous digital circuits.
Hardware description languages (HDLs) have been used for some time to design electronic circuits, and in particular to design synchronous (clocked) digital circuits. One class of hardware description languages are "register-transfer languages" (RTLs) in which the circuit has, or is abstracted to have, a set of registers, and the language specifies the values of the registers in each clock period in terms of the values in the previous clock period. A widely used HDL is Verilog, which has been standardized as IEEE standard 1364-1995, and for which numerous software tools are available. Verilog supports a variety of specification approaches, including a RTL approach.
Design of complex digital circuits, such as pipelined and superscalar processors, using an RTL approach typically requires a hardware architect to specify the overall functionality of the system which can be defined in terms of modular components that are defmed separately, as well as specify the correct coordination of concurrent processing modules in the circuit. As hardware systems become more complex, for example pipelined" processors which allow out-of-order and speculative instruction execution, this task is increasingly time consuming and is subject to human error.
Other HDL approaches attempt to specify a digital circuit in "behavioral"1 terms, without necessarily identifying the structure of the underlying circuit. For instance, Verilog supports such a behavioral specification approach. However, it is not always possible or feasible to synthesize an equivalent digital circuit from such a behavioral specification.
A variety of software tools are available for processing HDL specifications, including tools for simulating the specified circuits. Formal verification of the correctness of an HDL specification is often difficult, or even impossible, due in part to the nature and complexity of the specification.
Summary
In.one aspect, in general, the invention is a method for making a synchronous digital integrated circuit according to a specification of an asynchronous digital system. The specification of the asynchronous digital system is first accepted, for instance, from an architect or hardware designer who has composed the specification. This specification includes specifications of a number of data elements whose values define a state of the system, and specifications of a number of state transition rules that characterize non-deterministic operation
2

WO 01/13285- „ ,PCT/US00/22888-
of the system. Application of each of the state transition rules in the asynchronous system atomically updates values of the data elements according to the specification of the state transition rule. According to the method, the specification of the asynchronous system is processed to form a specification of a synchronous digital system such that state transitions of the synchronous system each correspond to application of one or more state transition rules of the asynchronous system. The specification of the synchronous digital system is then processed to form a specification of the synchronous digital integrated circuit, and the digital integrated circuit is fabricated according to the specification for the synchronous digital integrated circuit. In the way, the integrated circuit operates according to the specification of the asynchronous digital system.
The methou can merare one of MORE ot the following features :
Processing the specification of the synchronous digital system to form a specification of the synchronous digital integrated circuit can include forming a specification of the integrated circuit using a register-transfer language (R.TL).
Forming a specification of the integrated circuit using a register-transfer language includes optimizing the specification of the integrated circuit.
The specification using the register-transfer language includes a Verilog specification. The specification of each of the state transition rules includes a specification of a logical precondition for. enabling the rule and a specification of a resulting state that is reached as a result of applying the rule.
The specification of the asynchronous digital system includes a term rewriting system (TRS) specification of the system mat includes the specifications of the state transition rules: In another aspect, in general, the invention is a method for designing a synchronous digital system according to a specification of an asynchronous digital system. The method includes accepting the specification of the asynchronous digital system, including accepting specifications of a number of data elements whose values define a state of the system and accepting specifications of a number of state transition rules that characterize non-deteirninistic operation of the system. Application of each of the state transition rules atomically updates values of the data elements according to the specification of that state transition rule. The method then includes processing the specification of the asynchronous system to form a specification of the synchronous digital system such that state transitions of the synchronous system each correspond to application of zero or more state transition rules of the asynchronous system.


wo 01/13285

PCT/US00/22888

The method can include one or more of the following features: The synchronous digital system is such that any state transition of the synchronous system corresponds to application of at most one state transition rule of the asynchronous system.
The synchronous digital system is such that at least some state transitions of the synchronous system correspond to application of two or more state transition rules of the asynchronous system.
Processing the specification of the asynchronous system includes identifying a number oj groups of multiple of the state transition rules such that a state transition of the synchronous system that corresponds to application of state transitions from a single of the groups is permissible.
Processing the specification of the asynchronous system includes detennining a number of disjoint sets of potentially conflicting state transition rules such that concurrent application of any pair of rules taken from two different of the sets do not conflict in their access to the data elements and conqurrent application any pair of rules taken from a single of the sets may conflict in their access to one or more of the data elements.
Processing the specification also includes identifying the groups of multiple of the state transition rules such that each group includes at most one rule from each of the sets of potentially -conflicting state transition rules.
Processing the specification of the asynchronous system includes specifying a component of the digital system that implements a selection of at most one rule from each of the sets of potentially conflicting rules.
Processing the specification of the asynchronous system includes enumerating groups of the state transition rules such that concurrent application of multiple rules in any single of the groups does not conflict in their access to the data elements.
Processing the specification of the asynchronous system includes specifying a component of the digital system that encodes the enumeration of the number of groups.
Processing the specification of the asynchronous system includes enumerating groups of the state transition rules such that concurrent application of multiple rules in any single of the groups does not conflict in their access to the data elements includes enumerating one or more separate groups of state transition rules that do not conflict within different ones of the disjoint sets of potentially conflicting state transition rules.
Identifying the groups of multiple of the state transition rules is such that each of the groups includes at most one enumerated group from each of the sets of potentially conflicting state transition rules.

-W0 01/13285 -PCT/US00^2888

processing the specification of the asynchronous system includes identifying sequences of two or more state transitions rules such that a state transition of the synchronous system that corresponds to applications of any of the sequences of two or more rules iri sequence corresponds to application of the last of the sequence alone.
Processing the specification of the asynchronous system includes specifying a component of the digital system that implements a selection of the last of the sequence when each of the sequence of two or more rules are enabled.
Identifying the groups of multiple of the state transition rules is such that each of the groups includes at most one of the sequences of two or more state transitions from each of the sets of potentially conflicting state transition rules.
Processing the specification of the asynchronous system includes identifying a plurality of sequences of state transition rules such that for any particular of the sequences, a state transition of the synchronous system that corresponds to sequence application of any subset of that sequence is functionally equivalent to sequential application of that subset of rules in the order or the sequence in the asynchronous system.
Processing the specification of the asynchronous system includes specifying a componen of the digital system that for at least some of the data elements implements a calculation of new values for those data elements for a state transition of the synchronous system corresponds to sequential application of state transition rules of the asynchronous system in a sequence according one of the plurality of sequences.
In another aspect, in general, the invention is software stored on a computer-readable medium for causing a computer system to perform a function of designing a synchronous digital system according to a specification of an asynchronous digital system
In another aspect, in general, the invention is a computer-controlled system for designing a synchronous digital system according to a specification of an asynchronous digital system comprising means for accepting the specification of the asynchronous digital system, including accepting specifications of a plurality of data elements whose values define a state of the system and accepting specifications of a plurality of state transition rules that characterize non-deterministic operation of the system and wherein application of each of the state transition rules atomically updates values of the data elements according to the specification of the state transition rule; and means for processing the specification of the asynchronous system to form a specification of the synchronous digital system such that state transitions of the synchronous system each correspond to application of zero or more state transition rules of the asynchronous system.
5

WO 01/13285 . PCT/US00/23888 -
Tne invention has one or more of the following advantages:
A system that is intended to be implemented as a synchronous digital system, such as a synchronous digital circuit implemented as an integrated circuit, can be initially designed using an asynchronous system specification- Such an asynchronous specification is often significantly less complex than a corresponding synchronous specification. For example, the asynchronous specification does not need to include features of concurrent pipelined or concurrent operation that are often part of a synchronous specification. Furthermore, the asynchronous specification maybe more hirecfry related, to an external specification of the system, sucn as a specfication or a computer bus or a specification of a communication protocol according to which the system is intended to function.
The asynchronous specification may also be more amenable to automated or semi-automated validation approaches. The synchronous specification is guaranteed to be a valid implementation of the asynchronous system, and therefore further validation of the synchronous system may be unnecessary. This reduces design errors that are introduce while optimizing a circuit design, for example, by introducing deep pipelined architectures or large-scale
concurrency.
For a particular asynchrono us specification, various alternative synchronous implementations can be synthesized The alternative implementations can make different tradeoffs between concurrency and required circuit resources. That is, a relatively slower-operating implementation can be synthesized using fewer circuit elements than a relatively faster
implementation.
A single asynchronous specifiction can be used to synthesize multiple circuit modules that are designed to communicate among one another. Also, one or more modules can be implemented in software according to the asynchronous specification and correctly interact with modules implemented as digital circuits .
As communication protocol or computer interfaces specification evolve, new circuitry that implements those protocols and interfaces can be rapidly designed using the automated approach without necessarily requiring large amounts of manual design effort to yield efficient implementations of those new protocols and interfaces.
Other features and advantage of the invention are apparent from the following
description, and from the claims. Accompanying
Description of Drawings
FIG. 1 illustrates processing of an asynchronous system specification to form a detailed hardware description;

WO 01/13285- -PCT/US00/22888~

FIGS. 2A-B illustrate storage elements and TRS rules for a first exemplary asynchronous system specification;
FIG. 3A illustrates storage elements for a second exemplary asynchronous system
specification; ,
FIG. 3B illustrates dependencies of rules on storage elements;
FIG. 4 is a flowchart of the steps carried out by a Term Rewriting Architecture Compiler;
FIG. 5 illustrates exemplary sets of potentially conflicting rules;
FIGS. 6A-B illustrate arbitration logic which generates trigger signals for rules;
FIG. 6C illustrates a potion of a circuit specification which makes use of the trigger signals;
FIG. 7 is a set of data type declarations of a system specification;
FIG. 8 is a set of rewrite rules of a system specification;
FIG. 9 is a logical structure of a processor defined by the system specification;
FIG. 10 is a logical structure of a processor which includes a pipeline buffer;
FIG. 11 is a set of data type declarations for a processor which includes a pipeline buffer;
FIGS; 12A-B are rewrite rules for a system which makes use of a pipeline buffer;
FIGS. 13A-E are composite rewrite rules for a superscalar implementation;
FIG. 14 is a block diagram of update combination logic for a parallel combination of rules;
FIG. 15 is a circuit diagram for update combination logic for a parallel combination of set actions for a register storage element;
FIG. 16 is a diagram for update combination logic for a parallel combination of actions for a FIFO storage element;
FIG. 16 is a diagram for update combination logic for a parallel combination of actions for an array storage element;
FIGS. 18A-C are graphs which are used identify scheduling sub-groups based on a sequential composability property;
FIG. 18A is a graph with arcs that correspond to sequential composability between rules;
FIG. 18B is an acyclic graphs formed from arcs which correspond to sequential . composability between rules;
FIG. 18C is an undirected conflict graph with arc corresponding to potential conflicts between rules;
FIGS. 19A-B are graphs which illustrate an alternative identification of scheduling sub¬groups;
FIG. 19A is an acyclic graph formed from arcs which correspond to sequential composability between rules;

FIG. 19B is an undirected conflict graph;
FIG. 20 is a block diagram of update combination logic for a sequential combination of rules;
FIG. 21 is a circuit diagram for update combination logic for a sequential combination of set actions for a register storage element; and
FIG. 22 is a table showing input-output characteristics for an enumerated encoder for triggering sequentially composable rules in a scheduling sub-group.
Description
1 Overview
Referring to FIG. 1, a circuit synthesis system 110 accepts an asynchronous system specification 105 and produces a detailed hardware description 115, which describes a -synchronous (clocked) digital circuit that functions according to the asynchronous system specification. Circuit synthesis system 110 includes a term rewriting architecture compiler (TRAC) 130, which accepts asynchronous system specification 105 and produces a synchronous circuit specification 135. TRAC 130 is a software application which when executed on a general-purpose computer implements the circuit synthesis approach described below. In this version of circuit synthesis system 110, synchronous circuit specification 135 uses a subset of the Verilog hardware description language (HDL). In particular, synchronous circuit specification 135 uses a register transfer language (RTL) subset of Verilog. Synchronous circuit specification 135 passes to a hardware compiler 140, in this instance a Verilog compiler, which produces detailed hardware description 115 as output. Circuit fabrication 120 makes use of detailed hardware description 115 to fabricate hardware 125, for example a field programmable gate array. Hardware 125 is configured according to synchronous circuit specification 135 and thereby operates according to asynchronous system specification 105 in that when viewed once per clock period, the operation of hardware 125 is allowed" by asynchronous system specification 105.
In the embodiments described below, asynchronous system specification 105 is specified in terms of a Term Rewriting System (TRS). Term Rewriting Systems (TRS) can be used for design and verification of complex digital systems, such as general-purpose computer processors. See, for example, Arvind and X. Shen, using Term Rewriting Systems to Design and Verify Processors," MIT LCS MemoCSG-419, IEEE Micro, May/June 1999, in which an example of a processor with speculative instruction execution is described. It should be understood that this approach to specifying systems using a TRS is not limited to processor design, but is equally suited to specification and design of other types of systems, including but

not limited to memory controllers, distributed shared memory systems, and communication devices such as data routers.
In the context of asynchronous system specification 105, the content of number of named storage elements defines the state of the asynchronous system. These storage elements correspond to actual or abstract data types. An actual data type is one for which the storage structure and operation is completely known, whereas an abstract data type is defined only in terms of its interface which defines its externally visible behavior. Both actual and abstract data types have defined interfaces that include the possible actions that can be performed on storage elements of those data type and the arguments of those actions, as well as functions for accessing values in the storage elements. Examples of actual data types include a register that holds a single value. An action for a register would typically include set(val, and clearO, while a function for access the value in a register is get(). Examples of abstract data types include a array, FIFO queue, content-addressable FIFO, push-down stack, or other storage for multiple values that allows access to some but not necessarily all of the values, or other elements with well-defined interface semantics. Example of an actions on a FIFO include enqueue(val), dequeue(), and clear, while functions for accessing values or state of the FIFO might include firstO, which returns the head of the FIFO, and Boolean functions fullO and empty() that return a status of the FIFO.
Hardware 125 can be a single integrated circuit, in which some or all of the circuit is specified by detailed hardware description 115. As is discussed further below, hardware 125 can alternatively be made up of a number of interconnected integrated circuits, for example a separate memory controller and a processor that are meant to be interconnected by a communication bus, or separate communication devices, such as routers, that are intended to be connected by an extended communication channel. Also, in some embodiments, some or all of the synchronous system is implemented using software, for example using a micro-coded module within a circuit, or by making use of a programmable general purpose processor to implement some of the system.
TRAC 130 performs several steps in transforming asynchronous system specification 105 to form synchronous circuit specification 135. In many of the embodiments or approaches described below, TRAC 130 identifies sets of state transition rules of the asynchronous system specification that can be statically determined to be applicable within a single clocking cycle of the synchronous system without introducing conflicting access to storage elements that cannot be resolves statically at the time that the circuit is synthesized. TRAC 130 synthesizes enabling logic that generates signals indicating which rules are enabled given the state of the synchronous system, arbitration logic (also referred to as triggering logic) which selects a subset of the enabled rules to trigger for application in the same cycle of the synchronous circuit, update logic


WO 01/13285

PCT/US/2288S


that generates updated values for the storage elements based on application of the rules, and update combination logic that selects from or otherwise combines updated values with which to update the storage elements in the situations that more than one rule that can update a particular storage element. The general approach taken by TRAC is to trigger a subset of enabled rules that were statically identified as being applicable in a single cycle, with many of the embodiments having a goal of triggering many rules in each cycle of the synchronous circuit in order to achieve fast operation of the synchronous circuit.
2 First Example
Referring to FIGS. 2A, a first exemplary asynchronous system specification 105 characterizes a single-cycle (i.e., not pipelined) processor. Note that as discussed above, similar approaches to system specification are equally applicable to systems other than processors. The simplified processor used in this example is intended to illustrate the use of TRS. The processor has a number of storage elements, including a program counter register, PC 240, an addressable instruction memory, MEM 250, which holds processor instructions, an addressable data memory, DMEM 251, and a register file, RF 260, which holds data values. These four storage elements are grouped to form PROC 230. Referring to FIG. 2B, asynchronous system specification 105 includes TRS rules 210, which includes a number of individual rules 220 that describe allowable transitions in the values in the storage elements. An exemplary rule 220, the "Add Rule," in TRS rules 210 governs addition of two values stored in register file RF 260. Each rule 220 in TRS rules 210 has a left-hand-side (LHS) term 222, a predicate 224, and a right-hand-side (RHS) term 226. Each rule is, in general, applicable in multiple different arrangements of values in the storage elements (states) of the system as defined by its LHS term 222 and predicate 224. A primitive, or "delta," rule is applicable in only one state. A general rule is a shorthand expressed in terms of variables that represents a number of delta rules. For any rule, its RHS term 226 uniquely specifies new values of the storage elements (the new state) in terms of the values in storage elements at the time the rule was applied. Operation of the specified asynchronous system is based on the assumption that any rule is applied atomically, that is, storage elements are updated according to one rule before a new rule is considered.
In this first example, rule 220 shown in FIG. 2B has the following elements:



Rule 220: LHS term 222 if Predicate 224
RHS term 226
Add Rule: Proc(pc,rf,im,dm) ifim\pc] is Op(Add,rd,rl,r2) -> Proc[pc+1,rf[rd:=v],im,dm) where v=rf[rl]+rf[r2]
The term Proc0 has four positional arguments. Referring to FIG. 2A, the first argument, pc, matches PC 240, the second argument, rf, matches register file RF 260, and the third argument, im, matches instruction memory MEM 250, and the fourth argument, dm, matches data memory DMEM 251. The exemplary rale shown above is read as "If the system has a term ,Proc(pc,rf,im,dmy and im at addressee holds an instruction with opcode Add and variable arguments rd, rl, and r2 then the term "Proc(pc,rf,im,dm)" is replaced (i.e., rewritten) such that pc is replaced with/pc+1, and the rd entry of register file rf is replaced with the value v, which is the sum of the rl entry and the r2 entry of register file rf."
Note that in the rules, arguments such as im and Proc match actual storage elements or defined groups of storage elements, in this case IMEM 250 and Proc 230. The LHS term of a rule can, in general, be matched in multiple ways to storage elements of the system. For example, in a system with multiple identical processors a single rule applicable to a processor could be matched to any of the processors. When a rule can be matched to different storage elements of the system, the rule is essentially treated as separate multiple rule instances of the same rule each with a defined mapping to storage elements.
Two additional rules in this first example are used to specify a branch-if-zero instructions as:
Bz-taken rule:
Proc(pc,rf,im,dm)
if im[pc] is Bz(rc,ra) AND rffrc] is 0
-> Proc(rffraJ,rf,im,dm)
Bz-not-taken rule:
Proc(pc,rf,im,dm)
if im\pc\ is Bz(rc,ra) AND rffrc] is not 0
-> Procipc+l,rf jm.dm)


WO 01/13285-- PCT/US00/22888
The first rule, the "Bz-taken" rule, updates pc with the content of rf[raj if the content of rf [rc] is zero, while the second rule, the "Bz-not-taken" rule, increments pc if rf [rc] is not zero.
Additional instructions, including move pc to register, load immediate, register-to-register subtraction, and memory load and store, are specified using similarly structured TRS rules. An approach to compilation of these types rules into a synchronous circuit specification is described fully below.
For any state of the system, in general, multiple but not necessarily all rules can be applied based on their LHS terms and predicates. In this simple example, one way to specify a synchronous implementation of the rules is to "enable" all rules that are applicable to the state at the beginning of each clocking period and to essentially concurrently update the state according the RHS terms of all the rules that are enabled. By concurrently, we mean that the LHS term and the predicate for each rule is evaluated concurrently at the beginning of a clocking period, and the rewrite values in the RHS terms are computed using those initial values, and all updates to the values are performed at the end of a clocking period. Note that, in general, enabling all the applicable rules is not feasible due to possible conflicts, such as multiple rules updating the same location, or a rule updating a value used by another rule. For this simple example, at most one rule is applicable to any particular state of the system, and at most a single state transition therefore occurs in each clocking period.
3 Second Example
Referring to FIGS. 3A-B, a second exemplary asynchronous system specification 105 specifies a processor that uses a pipeline buffer BS 350, which is a FIFO queue storage element, into which the processor can fetch an instruction in a clock cycle prior to executing it. The notation for the content of a FIFO is a series of subsequences or values. For example, enqueuing a value a into a FIFO with a prior value bs is denoted enq(bs,a). Similarly, nonEmpty(Zw) is a Boolean function that returns true if the FIFO is hot empty, that is, if bs has some elements in it. The first element of a nonempty FIFO is referenced as first(&.s). The first (least recently enqueued) element of a nonempty FIFO is removed by deq(bs), which is a function whose value is the FIFO with the first element removed.
Referring to FIG. 3A, PRQC 330 has five storage elements, in their order as positional arguments in a Proc term: PC 240, RF 260, BS 350, IMEM 250, and DMEM 251. A subset of TRS Rules 210 for this second example is as follows:


WO~01/132S5

PCT/U300/22008


Fetch Rule 310:
Proc(pc,rf,bs,im,dm)
if im\pc]=inst and Source(inst) does not intersect Target(bs)
-> Proc(pc+l,rf,bs",im,dm)
where bs"is enq(bs,Decode(im[pc]))
Add Rule 320:
Proc(pc, rf.bs, im, dm)
if first(2w) is Op(Add,/rd,v/,v2)
-^ Proc{pc,rf[rd:=v],bs",im,dm)
where v=v7+v2
bs"=deq(bs)
Bz-taken rule 330:
Procipc, rf.bs, im, dm)
if firstfbs) is Bz(vc,va) AND vc is 0
-> Proc(va,rf,im,dm)
Bz-not-taken rule 340:
Proc(pc,rf,bs,im,dm)
if firsts is Bz(vc,va) AND vc is not 0
-^ Proc{pc,rf,bs"tim,dm)
where bs" is deq(bs)
The SourceO Function is a shorthand for extracting the set of source register names from. an instruction or a set of instructions. For example Source(Op(Add,rd,r1,r2)) ={rl,r2}. The Target0 function is a shorthand for extracting the set of destination register names from the instructions in bs. The Decode() function is a shorthand for the decoded version of an instruction where the register operands has been fetched. For example, Decode (Op(Addsd,rl,r2))=Op(Add,rd,rf[rlJ,rf[r2))
Notice that Fetch rule 310 is always ready to fire, unless there is a Read-After-Write register dependence in the instruction being issued and the instructions waiting to be completed in bs. If Bz-taken rule 330 is also ready to fire when the Fetch rule is ready to fire, the asynchronous system exhibits non-deterministic behavior since one of these two will be applied and the corresponding state transition will complete before the other rule is applied (if indeed it is still applicable after the first state transition).
Referring to FIG. 3B, each rule in the second example is illustrated with its dependency on values in particular storage elements and with its affect on values in storage elements. Note that Add rule 320, Bz-taken rule 330, and Bz-not-taken rule 340 all affect storage element BS


WO 01/13285 PCT/USOO/22888
350, in particular by dequeuing the next instruction form the FIFO.Hower, these three rules are enabled in disjoint sets of statesbin particular,no instruction in BS 350 enables more than one of the rules. However, Fetch rule 310 and Bz-taken rule 330 both update PC 240. Furthermore, there are states in which both rules are enabled, in particular whenever Bz-taken rule 330 is enabled when Bz-taken is enables and it is the only instruction in BS. The approach of specifying a synchronous implementation of the rules enabling all the rules in each clocking period does not necessarily produce the expected result. For instance, the race condition of writing the updated vales of ps 240 can result if both Fetch rule 310 and BZ-taken rule 330 each
enable state transitions that occur in one clocking period.As is described below an overall strategy used in Term Rewriting Architecture compiler (TARC) 130 (FIG.1) is to attempt to enable multiple rules in each clocking period without introducing conflicts such as the race condition in updating PC 240 outlined above
4 Compilation
Referring now to FIG. 4, operation of an embodiment of Term Rewriting Architecture Compiler (TRAC) 130 (FIG.)involves several step.Note that the steps are not necessarily performed in the sequence illustrated in the figure,as some step can be performed in parallel. First, in step 410, TRAC 130 maps the storage element specified in asynchronous system specification 105 (FIG. 1) into registers, or other predefined cricuit elements that provide storage of values within the synchronous cricuit Next in step 420 TRAC 130 synthesizes enabling logic from the LHS and predicate and uploding logic form the RHS of each rule in an internal representation that is essentially equivalent to logic cricuits needed to implement these terms. Note that these logic representation assocition with each rule are disconnected" and do not form an overall circuit representation at this step .In step 432,TRAC130 synthesizes rule arbitration and update combination logic and step434 connetcs the logic synthesized in steps 420 and 432 with the logic synthesized in step 434 to from an overall speification of the synchronous circuit. Then in step 440 TRAC 130 optimizes the resulting logic producing the final RTL specification. These step are considered in more detali as follows.
Returning to step 410, TRAC 130 maps strorage element in asynchronous system specification 105 into a variety of acture cricuit element that will hold the vales that determine the state of the system. In the case of scalar storage element the mapping is directly into a register circuit. Asynchronous system specification 105 includes data type declarations for each of the storage elements. For example in the case of scalar storage elements can include the number of bits needed in the register circuit Altematively, a default number of bits (e.g., 32 bits) can be used. In the case of abstrac storage element such as a register file or a FIFO


WQmft328S~" FCT/US00/2288g-

queue, TRAC 130 maps these elements into predefined circuit elements that are, for example, provided as library elements in the HDL.
Although an abstract data type may describe an unbounded storage, such as an unbounded length FIFO queue, the circuit elements have bounded storage. In the case of a FIFO queue, at this step TRAC 130 synthesizes circuitry which implements storage for one or more entries, as well as interlocking circuitry prevents writing into a full FIFO. Note that in an asynchronous system, a full FIFO cannot be written to. In a synchronous implementation, a full FIFO can be written to in a clocking period as long as an entry is dequeued in the same period. In this way, a FIFO queue may be implemented using a single register and interlocking logic that prevents writing into the. register only if the resister is holding a value that has not been dequeued, and that value is not dequeued in the clock period. Using this approach, the specification of the asynchronous system in terms of an unbounded FIFO is not complicated by " including the function of the interlocking logic in each rule that may enqueue a value in the FIFO, while ensuring proper operation for the synchronous system which uses a finite length FIFO, or even a single register.
Optionally, at step 410, TRAC 130 optimizes storage by identifying particular storage elements that can share registers, thereby reducing the amount for storage circuitry that is needed in the synthesized circuit.
In step 420, TRAC 130 synthesizes logic to implement the LHS and predicate and the RHS of each rule. Formally, for a rule i, TRAC 130 synthesizes logical expressions, m(s) and 5(s). The term s represents the state of the system, that is, the values in all the storage elements. The term n1,-(s) is a logical (Boolean) function that is true if rule i is enabled in state s, that is, if the rule"s predicate is true, and the LHS of the rule matches the state. The term 81(s) defines the updated values for the storage elements, that is, the next state, if the rule is applied.
An equivalent characterization of a rule i by the state-to-state transition function 5(s) is a characterization by a set of actions, a, on the storage elements (i.e., registers, arrays, and FIFOs) that make up the state, where each storage element is associated with a corresponding action, a = , and some actions are null, indicated symbolically as E. Then 5(s) is equal to the result of applying the actions specified in x to each of the storage elements.
In step 432, TRAC 130 generates "scheduling logicfor the rules, that is, TRAC generates logic that accepts enable signals identifying which rules are enabled given the current state, and outputs trigger signals that trigger a particular subset of those rules such that the rules in the subset can be applied in a single cycle of the synchronous circuit. A variety of alternative approaches to this step are described below. These alternatives can also be combined in yet other alternative approaches.


WO 01/13285 PCT/US300/22888
As outlined above, TRAC 130 identifies sets of state transition rules of the asynchronous system that can be statically determined to be applicable within a single cycle of the synchronous circuit. These sets are termed "scheduling groups" of rules. TRAC 130 does not necessarily explicitly enumerate all these scheduling groups. For example, in various approaches describe below, TRAC computes quantities (sets, graphs, etc.) from which scheduling groups can be determined constructively. Also, in various approaches described below, these scheduling groups are identified based on a static analysis of the system in which TRAC determines whether rules can be applied in a single synchronous cycle regardless of the state of the system. This static analysis is somewhat conservative in that, depending on the state of the system, additional rules might be applicable. However, since the scheduling groups do not depend on the state of the system, the implementation of the synchronous circuit is typically simpler than if the state of the system were taken into account to determine which rules could be applied within a single cycle. The use of a static analysis is not an absolute requirement in related alternative -approaches.
4.1 Single rule per cycle
A first approach to synthesizing the arbitration and update combination logic designing the synchronous circuit to apply at more one enabled rule in any particular cycle. Since only a single rule is triggered, there is no conflicting access to storage elements form different rules that are triggered concurrently. Conceptually, each scheduling group has a single rule in it and there is one such scheduling group for each rule. In order to maintain fairness among which rule is selected for triggering, TRAC 130 synthesizes a round-robin priority encoder that accepts the 7n1(s) signals, and outputs trigger signals (q1=(s) such that the corresponding enable signal is asserted and at most a single of the trigger signals is asserted. For each storage element that can be updated by more than one rule, TRAC 130 generates update selection logic that includes a selector that chooses the output of the update logic for the triggered rule to update that storage element. This approach may be relative inefficiency of applying at most one rule per cycle in the synchronous circuit. However, the approach also has the advantage of generating relatively little logic, which results, for example, in relatively little circuit area used by arbitration and update combination logic in an integrated circuit.
4.2 Conflict-free enumeration
In second approach to generating triggering logic TRAC 130 explicitly enumerates a number of scheduling groups. This list may be exhaustive, or alternatively, may represent a subset of all possible scheduling groups. TRAC makes use of a "conflict-free" condition between pairs of rules to form the enumerated scheduling groups. Essentially, a two rules are


conflict free if there is no state in which both can be enabled, or if there is such a state, the two rules can be applied "in parallel" without affecting one another. TRAC forms the enumerated scheduling groups by requiring that all pairs of rules in any particular group are conflict-free.
For any pair of rules that are or may possibly be both enabled in a state, then for the rules to be known to be conflict-free, the order of applying the two rules in sequence should not affect the resulting state transition after applying both rules. First, for any state in which both rules are enabled, each rule must continue to be enabled after the state transition defined by the other rule. Second, the order of the state transitions must not affect the resulting state after both transitions. The storage elements that are updated by the RHS terms of the rules are compared, and if there i* any storage element in common, the two rules are assumed to be in conflict. Even if there are no storage elements in conflict, if the result of performing the state update specified by the RHS term of one rule might affect the result of performing the state update of the other RHS term, for example by modifying the operands of that RHS term, then the two rules are also assumed to be in conflict. In this way, essentially parallel execution of two conflict-free state update in a single cycle is equivalent to sequential execution triggering the two state updates.
This conflict-free condition between two rules can be stated formally as follows. Consider two rules, i and j. Let s be the state of the system in terms of the values in all the storage elements of the system. As outlined above, the logical function ni(s) is true for a state s if the LHS terms and the predicate for rule i would enable the state transition defined by rule i, and the value of the state after that transition would be 5,(s). Two rules cannot both be enabled in any state s if ni(s) A NI(s) is false for all states s, and therefore would not be in conflict. If ni(s) and ni(s) are both true for some state s, then both ni,(8j(s)) and ni(8i(s)) must also be true to satisfy the requirement that both rules remain enabled after the state transition enabled by the other rule. Furthermore, the effect of the updates must not depend on the order of the updates, 8i(5j(s))= 8i(8i(s)), which is the case if the two rules update different storage elements and one rule does not update the operands of the other rule"s RHS term. Note that concurrent application of a set of non-conflicting rules in a synchronous implementation is equivalent to any sequence of application of those rules in the specified asynchronous system.
In this conflict-free enumeration approach, TRAC 130 enumerates the scheduling groups, and synthesizes triggering logic that accepts the enable signals and outputs trigger signals which correspond to an intersection of the enabled rules and the rules in a single of the scheduling groups. For example, this can be implemented using combinational logic that implements the intersection. The scheduling groups that have at least some rule intersecting with the enabled rules are selected by a round-robin priority encoded, optionally giving preference to those scheduling groups that would result in the largest number of rules being triggered. TRAC 130 synthesizes update combination logic that is similar to that in the approach in which only a single


W&4i#328£__

rCTYUaOO/22888*

rule is triggered per cycle, since the scheduling groups are chosen such that for any storage element, at most a single rule updates that storage element per cycle.
This approach has an advantage of triggering a relatively large number of rules per cycle, and a disadvantage that the portion of the scheduling logic that encodes the scheduling groups using a relatively large amount of circuitry for systems that have more than a small number of rules.
4.3 Potentially conflicting sets
Another approach taken by TRAC 130 to synthesize arbitration and update combination logic involves partitioning the rules into disjoint sets of potentially conflicting rules. Each rule in any such set of more than one rule possibly conflicts with at least one other rule in that set, that is, the.TRAC 130 has not determined with certainty that the two rules are conflict free. Also, any rule in such a potentially conflicting set is known to be conflict free with all rules outside that set. Therefore, in any clocking period, one rule from each set of potentially conflicting rules can safely be triggered simultaneously without conflict. TRAC 130 synthesizes arbitration logic that is used to prevent more than one rule in each potentially conflicting set from being triggered concurrently in one clocking period. This arbitration logic implicitly encodes membership in these potentially conflicting sets as well as implicitly encoding the set of scheduling groups.
Sets of potentially conflicting rules are identified in two steps. In one alternative approach each pair of rules is examined to determine whether there are any state of the system in which both rules are be enabled. TRAC 130 does this by examining the LHS terms and predicates of each of the pairs of rules and logically proving that a state exists that would enable both rules. In another alternative, rather than definitely proving that a state exists that enables both rules, a conservative approach is taken in which if TRAC 130 cannot prove that definitely no state exists that enables both rules, it assumes that such a state may possibly exist.
In the conservative static assessment of the conflict-free property based on the domain of the precondition and the domain and range of the action associated with each rule. The domain of an expression, such as a precondition n or an argument of an action is defined as the union of the domains sub-expressions. The domain for accessing functions for particular storage elements are defined in this embodiment as follows. The domain of axegister get(),is the register. The domain of an array a.-get (indx) is the union of the array and the domain of the index indx. The domain of a FIFO first() or emptyO function is the head of the FIFO, while the domain of a FIFO fullO function is the tail of the FIFO (that is, the head and tail are treated separately in this domain and range analysis). The ranges of actions are similarly defined. The range of a set(-) or a-set(-,-) action is the register or array updated by the action. The range of a FIFO enqueue(-) is



the tail of the FIFO, the range of a dequeue is the head of the FIFO, and the range of an enqueue-dequeue(-) (a concurrent enqueue and dequeue) and a clear() are both the head and tail of the FIFO. Based on these definitions of the domain and range of expressions and actions, the conservative static assessment of the conflict-free property is that if the ranges for two rules do not intersect, and the domain of one rule does not intersect with the range of the other, then the two rules are declared to be known to be conflict-free. Furthermore, if two rules i and j are mutually exclusive, that is ni(s) A NI(s) is false in all states s, then these rules are also declared to be conflict-free by default. In this embodiment, a conservative assessment of the mutual exclusive property searches the two expressions for n for contradicting constraints on any one state element, although a more detailed analysis can alternatively be performed.
Next, the rules are partitioned into potentially conflicting sets by first forming a conflict graph with the nodes representing the rules. The arcs of the graph each correspond to a pair of rules that have not been declared conflict free. Each connected set of states forms a potentially conflicting set. Two rules in different potentially conflicting set must have been declared conflict free or else the groups would be connected. Note that in this partitioning, it is possible for two rules within one group to actually have been declared conflict free. For instance, if rule A has not been declared conflict free with rules B and C, but B and C have been declared conflict free, all three rules would still be included in a single scheduling group:
Having identified the potentially conflicting sets of rules, TRAC 130 generates arbitration logic of a structure illustrated in the example shown in FIG. 6A. That is, for each potentially conflicting set with two or more rules TRAC 130 inserts a round-robin priority encoder to trigger at most one rule from each of the potentially conflicting sets.
TRAC 130 generates update combination logic for each storage element based on the data type of the storage element, and the nature of the potential conflict. Referring to FIG. 14, a general structure for the update combination logic associated with a storage element 1410 is a parallel update combination (PC) logic 1420 accepts signals that correspond to a number of actions, illustrated as x1, 0:2, and n1, and outputs to the storage element a signal corresponding to the parallel combination of those actions based on the trigger signals cpi, 92, and

W04[l«a28S frgT/USOO/22888
Referring to FIG. 16, the PC logic for a FIFO may modify the action by combining actions of several rules. Recall that access to the head and the tail of a FIFO do not necessarily conflict, and that one rule may perform an enqueue(val) action and another rule may perform a dequeue() action on the same FIFO in the same clocking period, in FIG. 16, a FIFO 1610 accepts an action signal at a port 1612, which includes the function to perform as well as any value that should be enqueued. PC logic 1620 in this example generates the action signal to pass to FIFO 1610 according to a table 1622. Note that both rules may be triggered, indicating that concurrent enqueue(val) and dequeue actions have been scheduled, and PC logic 1620 in this case outputs a combined enqueue-dequeue(val) action to the FIFO.
Referring to FIG. 17, a potential conflict may also arise through a conflict between a range of one rule and a domain of another. In FIG. 17, rule 1 performs an a.-set(addr1,val]) action on an array storage element 1710 while rule 2 makes use of an a.-get(addr2) expression. In this example, array 1710 has a shared input/output data port 1712 and a shared address port 1714. PC logic 1720 include a driver 1722 that drives data port 1712 only if rule 1 is enabled, and a multiplexer 1724 that selects between addr1 and addr2 depending on which rule is enabled.
4.4 Enumeration in potentially conflicting set
Another alternative approach combines the enumeration approach and with partitioning into potentially conflicting sets. TRAC 130 synthesizes scheduling logic that can trigger more than one rule from a potentially conflicting set. For example, consider the case in which a rule A potentially conflicts with rule B and separately potentially conflicts with rule C, but rules B and C are conflict free. Rules A, B, and C belong to a common potentially conflicting set. In the approach described above in Section 4.3 in which at most one rule from each potentially conflicting set is triggered, at most one of rules A, B, and C are triggered, thereby not allowing both A and B or both A and C to be triggered, but also not allowing both rules B and C to be triggered either. In this alternative approach, within each potentially conflicting set of rules, TRAC 130 enumerates conflict-free scheduling subgroups such that the rules in a subgroup all come from one potentially conflicting set of rules, and all pairs of rules in the subgroup are known to be conflict-free. In this way, {B,C} is a scheduling subgroup and if both B and C are enabled, they can both be triggered. Conceptually, the scheduling groups of the overall system are all combinations of the enumerated scheduling subgroups associated with the potentially conflicting sets of rules.
This approach has an advantage of being able to triggering more than one rule per cycle, and to trigger more than one rule per potentially conflicting set of rules, without requiring the scheduling logic to encode the entire set of scheduling groups of rules. Rather, the scheduling


logic encodes the separate sets of scheduling subgroups resulting in typically less circuitry being associated with the scheduling logic than in the full enumeration approach.
In alternative versions of this approach, an enumeration approach is not necessarily used for each potentially conflicting set. For instance, TRAC 130 may synthesize a round-robin encoder for some potentially-conflicting sets and exhaustively enumerate conflict-free scheduling subgroups for other potentially-conflicting sets. In one such approach, a designer may identify portions of the asynchronous system as portions in which the additional circuitry used by exhaustive enumeration is desirable to obtain potentially increased parallelism in the synchronous circuit, while in other portions less circuitry with a loss of potential parallelism is desirable. Also, the enumeration approach does not have to be exhaustive. For example, a designer may explicitly identify sets of rules that he would like to have concurrently applied in single cycles of the synchronous circuit, and TRAC then identifies scheduling subgroups that have as many of those rules as possible in them. Other approaches to partial enumeration are also possible, for example based on a constraint on the number of subgroups, or the amount of circuitry that results from synthesizing the arbitration logic based on the enumeration.
4.5 Dominance
Even when two rules potentially conflict, and state transitions are enabled by these rules both.update the same storage element, one rule may "dominate" the other. For instance, if two rules may both be enabled in some states, that is, ni(s) A NI(s) is true in states s, if ni,(8j(s)) is true and 5j(8j(s))= 8i(s) for all states s for which both are enabled, then rule i is said, to dominate rule j since even if rule j were to be enabled, subsequent firing of rule i would erase the effect of the prior firing of rule j. Therefore, conceptually, rule i can be applied after rule j in a clocking period in which both would be enabled. In the case of a synchronous circuit, if both rules i and j would enable state transitions, only the dominant state transition is triggered and the result is equivalent to having performed the dominant state transition after the other state transition.
TRAC 130 synthesizes arbitration logic such that if both rules i and j are enabled, the arbitration logic produces the same set of trigger signals as if only the dominant rule were enabled.
4.6 Second Example (continued)
Returning to the second example illustrated in FIG. 3B and introduced in Section 3, the conflict free relationship for the exemplary rules is illustrated in FIG. 5. Fetch rule 310 and Bz-taken rule 330 conflict because of the race updating PC 240 (FIG. 3B). Potentially conflicting set 510 is made up of fetch rule 310 and Bz-taken rule 330. The remaining rules do not conflict with any other rules.


Note that Bz-taken rule 330 dominates Fetch rule 310 under the definition stated above, and therefore in states in which both rules would enable state transitions, only Bz-taken rule 330 need be executed.
Turning to FIG. 6A, TRAC 130 synthesizes arbitration logic 650 according to the approach described in Sections 4.3 and 4.5. The arbitration logic takes as input enable signal ni(s) from each rule i, and outputs Qi(s), a trigger signal for each rule i. The Q1,(s) are such that for any potentially conflicting set of rules, at most one rule from that set has a trigger signal asserted. That rule is selected in a fair manner, for example in a priority round-robin manner 655, from the rules in the set for which nj(s) is true. Arbitration logic 650 also takes into account dominance, of one rule over another so that if dominant rule and the dominated rule can both fire, the dominant rule is chosen over the dominated rule, regardless of fairness. In FIG. 6, which corresponds to the second example above, combinational logic 610, 620, 630, and 640, implements nFetch(s), nAdd(s), nBz-taken(s) and.nBz-not-taken(s), respectively.
Referring still to FIG. 6A, the 7t,(s) signals are fed to arbitration logic 650. In this example, there is only one set of potentially conflicting rules, which includes the Fetch rule and the Bz-taken rule. Therefore the outputs nFetch(s) from combinational logic 610 and nBz-taken(s) from combinational logic 630 are fed to round-robin priority encoder 655. In this single example, the dominant relationship between Bz-taken rule 330 and Fetch rule 310 is used to trigger Fetch rule 310 unless Bz-taken rule 330 is also to be triggered.
Referring to FIG. 6B, arbitration logic 650 for this example is particularly simple, with the Fetch rule being arbitrated only if the Bz-taken rule is enabled, and arbitration logic 650 generating trigger signals for the other rules whenever they are enabled.
In a final part of step 430, TRAC 130 combines the outputs trigger signals 5j(s) through multiplexers that are used to select the outputs of appropriate 8j(s) functions which the multiplexers then feed the selected output to the registers.
Referring to FIG. 6C, a portion of the resulting synchronous circuit specification 135 (FIG. 1) produced by TRAC 130 is shown for the second example above. Trigger signals QBZ-takcn(s) 663 and (pFetch(s) 661 are generated by arbitration logic 650, as shown in FIG. 6A, and fed update combination logic that includes a multiplexor 750. In particular, the trigger signals are -fed to the select inputs of multiplexor 750. Combinational logic 730, and 720, implementing 5BZ-aken(s) and 8Fetch(s), respectively, generate outputs that are fed to multiplexor 750. Multiplexor 750 selects one of these two outputs based on its select input, and feeds the selected signal to register 740, which implements storage for PC 240 (FIG. 2). Register 740 is enabled by a latch enable signal 762 that is generated by an OR logic 760 based on the trigger signals 661 and 663 hat are fed to multiplexor 750. Register 740 also receives a clock 770 so that in a clock period


in which either Bz-taken rule 330 or Fetch rule 310 are enabled, register 740 is updated with the appropriate one of 8Bz-taken(s) or 8Fetch(s).
4.7 Sequential composition
In another approach by which TRAC 130 synthesizes rule arbitration and update combination logic, TRAC 130 makes associates transitions of the synchronous system with sequences of state transitions of the specified asynchronous system such that rules in such a sequence are not conflict free. Generally, the approach is to identify scheduling groups that are sequences of rules such that application of any subset of a sequence in the order specified by the sequence can be associated with a single synchronous transition of the synchronous system. For example, consider the case in which rule A uses the value of register X to update the value of register Y, while rule B does not use the value of register Y but does update the value of register X. There is a possible conflict between the update by rule B and the input by rule A. A valid application of rules A and B in a single synchronous transition would be one that is equivalent to application of rule A prior to rule B. Note that in this example, rules A and B are not conflict-free according to the definitions provided above: although 7nA(s) and nB(s) may both be true for some state s, nA(8B(S)) is not necessarily true, and 8A(5B(S)) is not necessarily equal to 5B(5A(S)).
The approach taken to generate logic from the rules can be best understood as first identifying pairs of rules that are "sequential composable" (also called "strongly transparent") and then forming the sequences of rules such that any rules in any sequence is sequentially composable with all rules later in that same sequence.
A rule A is sequentially composable with a rule B, denoted A TRAC 130 synthesizes arbitration logic such that given a set of applicable rules in a state, the triggered rules correspond to some valid sequence of rules according to the sequential composability property.


^WO-/13285 "

-PCT/US/22888-

4.8 Composable sequence enumeration
In a first approach that takes advantage of sequential composability, TRAC 130 enumerates sequentially composable sequences of rules. TRAC 130 automatically synthesizes arbitration logic such that for each clocking period, of the set of rules that are enabled according to the state of the system, a subset of those rules that all belong to a single sequentially composable sequence are triggered. Each storage element that is updated by these rules is updated according to the functional equivalent of applying the subset of enabled rules in that sequence in the asynchronous system according to the order of the sequence. Note that in general, for a particular set of enabled rules, multiple different sequentially composable sequences can be used. In this first approach, TRAC 130 identifies "maximal" composable sequences of rules, which are composable sequences such that the set of rules in the sequence is not a subset of the rules in any larger composable sequence.
As a first step, TRAC 130 makes a conservative static deduction of the property. This static deduction uses a sufficient condition for A Next, TRAC 130 enumerates the maximal composable sequences according to the static deduction of the pairwise sequential composability property. TRAC 130 then synthesizes arbitration logic in a manner similar to that used with enumeration of conflict-free groups as discussed in Section 4.2. That is, the arbitration logic asserts trigger signals for an intersection of the enabled rules and the rules in a single of the maximal composable sequences.
TRAC 130 synthesizes update combination logic for each storage element such that the update is equivalent to the sequential application of the triggered rules in the order determined by the selected maximal composable sequence.


WO 01/

PCT/US/22888


4.9 Composable sequences in conflict-free sets
As an alternative approach, TRAC 130 first partitions the rules into potentially-conflicting sets as described above in Section 4.3. TRAC 130 then enumerates maximal composable sequences for the rules in each of these potentially conflicting sets/ It then synthesizes arbitration logic such that at most one maximal composable sequence is selected from each potentially conflicting set, and the set of triggered rules are the intersection of the enabled rules and the rules in the maximal composable sequences selected for each of the potentially conflicting sets.
TRAC generates update combination logic as described in Section 4.9. Note that for any storage element, the rules which update the storage element come from at most one potentially conflicting group and therefore involve at most a single of the maximal composable sequences for the potentially conflicting sets.
Note that conceptually, the scheduling groups are all interleavings of the maximal composable sequences for the different potentially conflicting sets, since the relative ordering of the rules in different potentially conflicting sets does not affect the state transition of the synchronous system.
4.10 Composable sequence subgroups
In another approach that makes use of sequential composability, TRAC 130 identifies subsets of each potentially conflicting set of rules, and within each of those subsets identifies an scheduling groups according to the conflict-free property described above.
TRAC 130 partitions each potentially conflict set of rules into a number of subsets. The goal is to make any two rules in different of these subsets to either be conflict-free, or to be sequentially composable. Furthermore, if there are more than two subsets, then for a group of rules one from each subgroup, there is statically determined order in which the rules can be applied to form a sequentially composable sequence.
This step is implemented as follows. For each potentially conflicting set, a first directed graph is formed with the nodes representing the rules in the set. The graph includes a directed arc from a node for a rule A to a node for a rule B if and only if A


the acyclic graph to improve or optimize the average number of rules that are concurrently applied in a clocking period. Note that the resulting second directed graph is not necessarily fully connected.
A third undirected graph is formed from the second directed graph and the pairwise conflict-free property. In partialis the third graph again has nodes that each corresponds to a different rule in a potentially conf licting set. An arc between a node for rule A to a node for rule B is present in the third graph if and only if rules A and B and not known to be conflict free, and there is neither an arc form A to B no from B to Aa in the second directed graph. tje connected components of the third undirected grapd identify the subsets of the potentially conflicting set.
Next, TRAC 130 generates arbitration logic. As in the first approach, the arbitration logic for each potentially conflicting set is independent of the logic for the other potentially conflicting sets, since it is known that any rule in such set is necessarily conflict free with any other rule in another such set. In this second approach, the scheduling logic for each subet is independent and for a particular potentially conflicting set is such that for a particular group of enabled rules in the set, the arbitration logic triggers at least one rule from each subset that has an enabled rule. An important aspect of this approach is that since the second directed graph is acyclic, all the rules in a potentially conflicting set can be statically ordered so that for any set of trigger signals asserted by the arbitration logic, each rule in the sequence is either conflict free or sequentially composable with each of the triggered rules later in the sequence.
Referring to FIGS 18A-C,in an example TRAC 130 partitions a scheduling group made up of five rules, A-E, into subgroups according to the above procedure. FIG. 18A shows the first directed graph that corresponds to the pairwise sequential composability properties of these rules. Note that this graph has cycles A-B-C-D and A-C-D. FIG. 18B shows the second directed graph in which the arc from D-E is removed (indicated by the broken arrow). The second directed graph has no cycles. FIG, 18C shows the third undirected graph (assuming that A-D, B-D, and D-E and not known to be conflict-free pairs of rules). The two sub-groups are therefore
{A3,D,E} and {C}.
Referring to FIGS. 19A-B, TRAC 130 finds different sub-groups if it forms the second directed graph by removing a different arc. In FIG. 19 A, the second directed graph is formed by removing the C-D arc. In FIG. 19& the resulting third undirected graph yields sub-groups {A} and {B,C,D,E}. As introduced above the choice of which arcs to remove can in some embodiments be made to optimize criteria, such as separating different rules that are desirable to
trigger together into different sub-grousp
TRAC 130 generates update combination logic for each storage element based on the data type of the storage element, and the nature of the potential conflict. Referring to FIG. 20, a general structure for the update combination logic associated with a storage element 2010 is a


sequential combination (SC) logic 2020 accepts signals that correspond to a number of actions, illustrated as x1, x2, and x1, and outputs to the storage element a signal corresponding to the sequential combination of those actions based on the trigger signals Q1, (Q2, and Q3, that are generated by the scheduling logic and are applied to SC logic 2020. Recall that in forming the second directed graph, TRAC 130 has established an ordering for the rules in a scheduling group such that if the scheduling logic asserts a set of trigger signals for rules in the group, then each triggered rale is sequentially composable with each triggered rule later in the sequence. Without loss of generality, in FIG. 20, rule 1, rule 2, and rule 3 are ordered according to this ordering of rules.
Referring to FIG. 21, if, for example, rules 1, 2, and 3 have a range conflict with a register storage element 2110, that is, each rule has an action that sets the value of the register, then two or more of the trigger signals Q1, Q2 and Q3, may be asserted in a clocking period. Sequential composition of these set(val) actions associated with these rules dictates that the latest of these triggered rules determines which value will be set in the register. One implementation" of SC logic 2020 uses a multiplexer 2120 and a priority encoder 2124. Priority encoder 2124 determines while is the last of the asserted trigger signals, and asserts that select input for multiplexer 2120, The multiplexer then passes the corresponding value to the input data port of the register. OR logic 2122 asserts the set line for the register if any of the rules is triggered.
In a variant of this approach, TRAC 130 generates scheduling logic using combinatorial logic for each subset rather than priority encoders. For a particular subset, the combinatorial logic has the characteristic that for at least some combinations of input enable signals, it asserts two or more trigger signals. The asserted trigger signals have the property that taken in the static ordering determined by the second acyclic graph, each triggered rule is sequentially composable with each of the other triggered rules in that subgroup that are later in the sequence. Each triggered rule is also sequentially composable with the triggered rules in the other sub-groups that are later in the ordering.
Referring to FIG. 22, a table characterizes one implementation of the combination logic for the first sub-group of rules, {A,B,D,E}, of the example shown in FIGS. 18A-C. For example, if both rules D and E are enabled (line 2204 in the table), they cannot both be triggered since they are not known to be sequentially composable (there is ho arc joining those node in the second directed graph in FIG. 18B). In this implementation, rule D is triggered. On the other hand, if both rules B and D are enabled (line 2206), they are both trigged since rule B is sequentially composable with rule B. If rules A, B, and E are enabled (line 2213), then they can be all triggered, since A is sequentially composable with both B and E, and B is sequentially composable with E.


WO 01/13285 PCT/USOO/22888
As with the use of enumerated conflict-free sets, alternative variants do not necessarily trigger maximal subsets of rules within a scheduling sub-group. For example, combinatorial logic that encodes an entire input-output table may consume too many resources (too many gates) and a sub-optimal encoder can be used. In one alternative variant, this logic is generated to trigger rules within a subgroup that are often enable together when the circuit used.
5 Modular and Software Implementations
In the description above, the synthesis of a synchronous digital circuit is described largely in the context of synthesis of a single circuit, such as and integrated circuit. The approach is equally applicable to synthesis of a modular system, for instance, composed of multiple integrated circuits. For example, the storage elements of the system can be optionally partitioned into separate modules, and each module implemented as a separate circuit with interfaces between the modules coupling the separate circuits.
In some systems, it may be desirable to implement some of the interacting modules using a software implementation. For example, the asynchronous system specification may define operation of interacting modules where one module is to be implemented as an integrated circuit while another module that interacts with the first is implemented in software, for instance, on a general-purpose processor. The TRS specification for the software module is compiled into software using one of a number of techniques. For instance, the software can be implemented using a standard event-driven programming approach in which the software implements a loop in which an enabled rules is first selected and then selected the rule is applied.
Within a circuit, a software implementation of a portion of a circuit can also be used. For example, a submodule of an integrated circuit may be implemented using a micro-coded approach in which the submodule includes a processor and the software is stored in memory circuitry in the submodule. In this approach, a number of storage elements are identified as forming the submodule. Then, all rules that use only the storage elements of the submodule are implemented in micro-code. The external interfaces for the storage elements of the submodule are also implemented in micro-code. In synthesizing the overall circuit, the TRAC compiler combines the circuitry for the software-implemented submodule with the circuitry synthesized using the approaches described above.
Third Example
In the following description, the approach described in Section 4.3, which makes use of the conflict-free property, is used in another example. This example involves the task of specifying a simple processor, then specifying a pipelined version of the processor and finally specifying a superscalar version of the processor. An aspect of this last transformation, from


pipelined to superscalar, makes use of a rule composition property of TRS specifications. The rule-composition property allows new rules to be derived by composing existing rules without introducing illegal behaviors to the system.
An architect starts by formulating a high-level specification of the processor"s instruction set architecture (ISA) as a TRS. The goal at this stage is to define an ISA as precisely as possible without injecting implementation details. From such a description, the architect, using TRAC 130, generates a RTL (Register Transfer Language) description of a single-issue, in-order, non-pipelined processor. The generated RTL can be simulated and synthesized by commercial tools.
Next, the architect manually transforms the ISA"s TRS description into another TRS that corresponds to a pipelined microarchitecture. In this step, the architect makes high-level architectural decisions such as the locations of the pipeline stages. FIFO queues are introduced •between pipeline stages, thereby making many of the rules local to particular pipeline stages and not conflicting with rules local to other pipeline stages. A rule typically dequeues a partially executed instruction from one FIFO queue, computes on it using only local information, and enqueues it into the next FIFO. The architect is also responsible for exposing and resolving any data and control hazards introduced by pipelining. To guard against possible errors introduced during this manual transformation, a semiautomatic verification technique is optionally used to show the correctness of the pipelined TRS against the original ISA specification using state-simulation techniques. Using TRAC 130, the architect takes the asynchronous specifications and generate RTL"s for synchronous pipelines.
Finally, the architect transforms the pipelined TRS into a superscalar TRS by devising composite rules. The effect of a composite rule is to apply more than one pipeline rule at each stage of the pipeline. As is described further below, this rule composition can optionally be done automatically once the degree of "superscalarity" is specified. The correctness of the resulting transformation is guaranteed because the rules derived by rule composition are always correct by TRS semantics.
Both pipelining and superscalar transformations are source-to-source in the TRS language and the resulting TRS descriptions can be compiled into Verilog RTL descriptions using TRAC 130. Throughout the design flow, the architect can compile intermediate designs. The architect can evaluate the RTL"s of these compiled intermediate designs to steer design decisions in successive refinement steps. For instance, a tool, such as the commercially available Synopsys RTL Analyzer, is used to analyze the size and speed of the circuit designed from the RTL description. In addition, the operation of the processor on sample programs can be examined using a commercial Verilog RTL simulator. Based on the prompt feedback from these tools, the architect can rapidly explore a large number of architectural options and trade-offs.



Returning now to the architect"s first step in the example, he first specifies a single-issue, in-order, non-pipelined processor that implement a desired instruction set architecture. In this example, programmer visible state of the processor consists of a program counter, a register file,. instruction ROM (read-only memory) and data RAM (read-write memory). Referring to FIG. 7, the programmer-visible state is represented using the terms generated of the types listed in lines 701 through 715. Type PROC (line 701) is a product type with the constructor symbol Proc() and four fields. The declaration of type INST (line 709) demonstrates the use of an algebraic union to represent the processor instruction set. For simplicity, the program and data memory are modeled as storage arrays internal to the processor. Optionally, the memory arrays are replaced by external memory interfaces represented as FIFO"s prior to synthesis of a final circuit.
Referring to FIG. 8, a set of rewrite rules define processor"s dynamic behavior. For brevity, the LHS is listed only once (line 801) and is the same for all the rules. Also, the rule at line 804 is a shorthand for the rules for all arithmetic operations, op, that take two register values and puts the result of applying the appropriate function op(,) to the two register arguments. For example, the following rule describes the effect of executing an Add instruction.
Proc{pc,rf,im,dm)
ifim[pcJ=Op(Add,rd,r],r2)
Proc(pc+l,rf[rd:=r[[rlJ+rffr2]],im,dm)
The predicate is true if the program counter points to an instruction memory location containing Op(Add,rd,rl ,r2). When a term satisfies both the LHS template and the predicate, the rule"s RHS rewrite template specifies that the pc field should be incremented by 1 and register rd should be updated by rf[rl]+rf[r2].
Referring to FIG. 9, when synthesized, this TRS corresponds, at least logically from the point of view of.a programmer, to the datapaths shown. PC 910 is a register that stores the program counter which is used to retrieve instructions from instruction memory, IMEM 920. Instructions from IMEM 920 are used to address particular registers in register file RF 930. The values from RF 930 are fed to an ALU 950, to data memory, DMEM 940, or to a selector 960 that determines the next value of PC. A selector 970 selects a value from ALU 950 or DMEM 940 to store in a register in RF 930.
In the next step, the architect rewrites the TRS specification shown in FIG. 11 by essentially splitting rules into subrules that provide the same overall functionality .from the point of view of a programmer, with the intention that multiple subrules may execute in parallel and that the implemented processor may execute instructions at a higher overall rate.



Referring to FIG. 10, the datapaths shown in FIG. 9 are modified to include a FIFO queue BS 1010 between register file RF 930 and ALU 950. The FIFO queue is used to buffer partially decoded instructions in which the operand values have been fetched from RF 930 but the operation has not yet been performed.
Referring to FIG. 11, the architect modifies the system specification shown in FIGS. 7-8 for pipelined operation corresponding to the datapaths shown in FIG. 10. In FIG. 11, type PROCp, defined in line 1101, contains a new field, the FIFO queue BS 1010, to hold instructions after they have been decoded and the operands have been fetched.
Referring to FIG. 12A, all of the processor rules can be partitioned into separate fetch and execute rules to represent a two-stage pipeline. Lines 1201-1203 are a generic fetch rule. Splitting a rule into smaller rules destroys the atomicity of the original rule and thus, can cause new behaviors which may not conform to the original specifications. Therefore, in addition to determining the appropriate division of work across the stages, the architect must also resolve any newly created hazards. The predicate at line 1202 has two terms, one that identifies the particular instruction, inst, and a second term that guarantees that the source operands of the instruction, denoted in shorthand as Source (mst), are not also the target of any instruction already enqueued in bs, denoted in shorthand as Target(bs). This second term inhibits fetching when a read-after-write (RAW) hazard exists. If the architect were to make a mistake in the transformation, the error would be revealed when an attempt is made to verify the equivalence of the pipelined processor against the initial specification via TRS simulation. The RHS, at line 1203, includes the shorthand Decode(inst), which refers to the instruction decoded with its operand values already fetched. Referring to FIG. 12B the execute rules for the ISA make use of the prefetched instructions enqueued in BS 1.010. The LHS is shown once in line 1211 for the predicates and RHSs shown in lines 1212-1216. For example, considering the pair of Bz rules shown in FIG. 8, lines 805-806 which describe the effect of branch taken versus not taken conditions in the version without a FIFO buffer, the architect splits these rules into their fetch (instances of the generic fetch rule at lines 1201-1203) and execute components. Both rules share the same fetch rule. In the fetch phase, the processor performs a weak form of branch speculation by incrementing pc without knowingthe branch resolution. Consequently, in the execute phase, if the branch is resolved as taken (execute rule at line 1213), besides restarting pc at the correct value, speculatively fetched instructions in BS 1010 are discarded by setting bs to in the Bz-takeh rule at line 1213;
In the third step, the architect rewrites the rules in such a way that multiple instructions can be processed in a pipeline stage in one clock cycle. To achieve two-way superscalar execution, the architect composes two rules that specify operations in the same pipeline stage into a new composite rule that combines the state transitions of both rules. Since the TRAC


WO 01/13285

EC3VUS00/22888


compiler generates RTL that executes the transitions of a rule in a single clock cycle, the compilation of composite rules results in RTL that can execute two instructions at a time.
In order to illustrate this approach, consider the fetch rules shown generically in FIG. 12A at lines 1201-1203. Bz-fetch and Op-fetch rules that are instances of this generic rule can be written as:
Bz-fetch rule:
Procp(pc,rf,bs,im,dm)
if im\pc] is Bz(rc,rt) AND rc not in Target (bs)
AND fa not in Targetfbs)
-> Procp(pc+l,rf,bs"),im,dm)
where bs"=enq(bs,Bz(rf[rc],rf[rt])
Op-fetch rule:
Procp(pc,rf,bs,im,dm)
if im\pc\ is Op(op,rd,rl,r2) AND
r] not in Targetfbs) AND
r2 not in Targetfbs) Proep(pc+l,rf,bs",im,dm)
where bs"=enq(bs, Op(op,rd,rf[rl],rf[r2]))
The Bz-fetch rule rewritten as if it was being applied to the term on the RHS of the Op-fetch rule takes the form of the following rule:
Bz-fetch-1 rule:
Procp(pc+J,rf,bs",im,dm)
if im\pc+l] is Bz(rc,rt)
ANDbs"=enqfbs,Op(op,rd,rf[rl],rf[r2])
AND re not in Targetfbs")
AND ra not in Target (bs)
Procp((pc+l)+l,rf,bs ",im,dm)
where bs "=enq(bs",Bz(rf[rc],rf[rt]),
Bz-fetch-1 rule is more specific than the general Bz-fetch rule because it requires BS to contain a partially executed Op instruction. Now we can combine the effect of the Op-fetch and Bz-fetch-1 rules into a single atomic rule as follows:


wO 01 /13285.

PCT/US00/2288y


Op/Bz-fetch rule: Procp(pc,rf,bs,im,dm) if im\pc] is Op(op,rd,rl,r2) AND rl not in Target(bs) AND r2 not in Target(bs) AND im[pc+l) is Bz(rc,rt) AND rc not in Target(bs) AND ra not in Target(bs)
where bs"=enq(bs, Op(op,rd,rf[rl],rf[r2]))
~> ProCp((pc+l)+l,rf,bs",im,dm)
where bs"=enq(bs",Bz(rffrc],rf[rt]))
The above Op/Bz-fetch rule is an example of a derived rule, that is, it is a rule that is be derived from other TRS rules. A derived rule is guaranteed to be correct, that is, it cannot introduce observable behaviors which were not permitted by the original rules. However, if the derived rule replaces the rules from which it was derived, the system may not show some behaviors which were permitted otherwise. Although this error does not lead to illegal state transitions, it could result in a deadlock. Hence, unless other provisions are made, each new composite rule is simply added to the original set of rules and does not, in general, replace any of the original rules.
The TRAC compiler, in general, synthesizes very different circuits for composite and non-composite rules. Since the effect of a composite rule takes place in one cycle, significantly more resources and circuitry are required to implement composite rules. Using its understanding of the abstract data type operations, the compiler also tries to simplify the predicate. For example, the predicate in the above Op/Bz-fetch rule can be simplified as follows:
Op/Bz-fetch rule: Procp(pc,rf,bs,im,dm) if im[pc] is Op(op,rd,rl,r2) AND im{pc+l] is Bz(rc,rt) AND rl not in Target(bs) AND r2 not in Target(bs) AND rc not in Target(bs) AND rt not in Target(bs) AND rc not equal rd AND rt not equal rd


WO 01/13285

PCT/US00/22888


-> Procp((pc+l)+l,rf.bs",im,dm)
where bs"~enq(enq(bs,Op(op,rd,rf[rl],rf[r2])),
Bz(rf[rcJ,rffrtJ))
Complete superscalar fetching of all possible instruction pairs would require the composition of all combinations of the original fetch rules from the 2-stage pipelined microarchitecture. In general, given a pipeline stage with N rales, a superscalar transformatioi leads to an O(N5) increase in the number of rules where s is the degree of superscalarity. Fortunately, the mechanical nature of this tedious transformation is handled by a computer aideu synthesis system. Superscalar transformation also implies duplication of hardware resources such as register file ports, ALU"s and memory ports. Hence, one may not want to compose all combinations of rules in a stage. For example, we may not want to compose any other execute rules with memory load or store rules if the memory interface can only accept one operation per cycle.
is formed by first rewriting rule r2 to be directly applicable to the RHS of rule n as follows:
Rule r2.
Sj"
ifp2"
->s2"
This yields the composite rule
Rule r/r2

Abstractly, the procedure for forming a composition of rules n and r2, where the rules are written as


WO 01/13285
S1 .
if P1 ANDp2"
s2
To transform the 2-stage pipelined microarchitecture into a two-way superscalar
microarchitecture involves derivation of a composite rale for each pair in the cross product of
rules for each pipeline stage.
Referring to FIG.13A, a generic version of a superscalar fetch rule is shown corresponding to a composition of two instances of the generic fetch rule shown in FIG. 12A.
Referring to FIG., 13B, composition of Op rules, line 1212 in FIG. 12B, and any of the other execution rules shown in FIG. 12B can always be executed as shown in lines 1311-1316. Note that most rales shown in FIG. 13B require additional read ports in the register file, RF 930. Some combinations also require two write-ports.
There is no valid composition because the RHS of Bz-taken rule (line 1213 in FIG. 12B) produces an empty FIFO queue. Every execute-stage rule in FIG. 12B requires the FIFO queue BS to satisfy the condition notEmpty(bs) and the variable inst is bound to first(bs).
Referring to FIG. 13C executing a Bz-not-taken rule (line 1214 in FIG. 12B) has no side-effects other than removing its template from the head of bs. Hence, composing a Bz-not-taken rule with any other rule produces a composite rule that is nearly identical to the second rule in the composition. This is true even if the second rule being composed is Bz-taken or Bz-not-taken. The composite rules shown in FIG. 13C correspond directly to the basic rules in FIG. 12B.
Referring to FIG., 13D, since we have assumed a single ported memory, DMEM 940, it is not possible to compose a memory access rule (Load or Store) with another memory access rule. The composition of a Load rule with the non-memory access basic rules shown in lines 1212-1214 in FIG. 12B are shown in FIG. 13D. The composition of a Store rule with these basic rules is shown in FIG. 13E.
Note that these composite rules, shown in FIGS. 13A-E do not replace the original rules shown in FIGS. 12A-B. For instance, all five rules shown in FIG. 12B are needed in case there is only one instruction in BS.
In an alternative embodiment, the approach described above is used in conjunction with predefined modules for which synchronous hardware specifications are already available. An interface is defined for each of these modules, and the asynchronous system is specified in terms of these interfaces. This allows the architect to focus on the task of interconnecting and coordinating the modules separately from defining the internal aspects of the modules themselves. Examples of such predefined modules include memory units, such as multi-ported

WO01/13285 PCT/USOO/23888—
register files of cache memory units, and functional units, such as arithmetic units. Similarly, in yet another alternative embodiment the approach described above is used to design a synchronous circuit that forms a module that will later be incorporated into an overall system using any of a number of design approaches for synchronous circuits.
It is to be understood that while the invention has been described in conjunction with the detailed description thereof, the foregoing description is intended only to illustrate particular embodiments of the invention and not to limit the scope of the invention, which is defined by the scope of the appended claims. Other aspects, advantages, and modifications are within the scope of the following claims.


We Claim:
1. A method for designing a synchronous digital system according to an asynchronous system specification for a first system comprising: accepting the asynchronous system specification (105), including accepting specifications of a plurality of data elements whose values define a state of the first system and accepting specifications of a plurality of state transition rules (210), wherein application of any of the state transition rules atomically updates values of the data elements according to the specification of said state transition rule: and processing the asynchronous system specification" to form a specification of the synchronous digital system (135); characterised in that:
processing the asynchronous system specification includes identifying a sequence of two of more of the state transition rules of the asynchronous system specification for application in a single state transition of the synchronous digital system; and
in at least some state transition of said synchronous digital system application by the synchronous digital system of the two or more of the state transition rules of the identified sequence corresponds to sequential application of the two or more of the state transition rules.
2. The method as claimed in claim 1 wherein at least some of the rules in
37

the identified sequence potentially conflict in their access to data elements and at least some state transition of the synchronous digital system corresponds to sequential application of the state transition rules that conflict.
3. The method as claimed in claim 1 wherein identifying the corresponding sequence of two or more of the state transition rules includes determining that if a first rule of the sequence and a subsequent rule in the sequence are both enabled in a state then said subsequent rule in the seauence remains enabled after application of said first rule.
4. The method as claimed in any of the preceding claims wherein the state transition rules characterize non-deterministic operation of the first system.
5. The method as claimed in any of the preceding claims wherein each of the rules of the corresponding sequence is enabled in the state at the beginning of application of said sequence.
6. The method as claimed in any of the preceding claims wherein processing the asynchronous system specification to form the specification of a synchronous digital system includes:
identifying a sequence of state transition rules such that if a first rule of the sequence is: enabled in a state then subsequent rules in the sequence remained enabled after application of said first rule.

38
7. The method as claimed in any of the preceding claims wherein it
comprises:
processing the specification of the synchronous digital system (135) to form a specification of a synchronous digital integrated circuit (115).
8. The method as claimed in claim 7, wherein it comprises:
fabricating the digital integrated circuit (125) according to the specification for said integrated circuit, whereby said integrated circuit operates according to the asynchronous system specification.
9. The method as claimed in claim 7 wherein processing the specification of the synchronous digital system to form the specification of the synchronous digital integrated circuit includes forming a specification of said integrated circuit using a register-transfer language (RTL).
10. The method as claimed in claim 9 wherein forming the specification of said integrated circuit using a register-transfer language includes optimizing the specification of said integrated circuit.
11. The method as claimed in claim 9, wherein the specification using the register-transfer language includes a Verilog specification.
12. The method as claimed in any of claims 1 to 8 wherein the specification

of each of the state transition rules includes a specification of a logical precondition for enabling the rule and a specification of a resulting state that is reached as a result of applying the rule.
13. The method as claimed in any; of the claims 1 to 8, wherein the asynchronous system specification includes a term rewriting system (TRS) specification that includes the specifications of the state transition rules.
14. The method as claimed in any of the claims 1 to 8, wherein processing the asynchronous system specification to form the specification of a synchronous digital system includes: identifying a plurality of groups of multiple of the state transition rules such that a state transition of the synchronous system corresponds to application of state transitions from a single of the groups is permissible.
15. The method as claimed in any of the claims 1 to 8 wherein processing the asynchronous system specification to form the specification of the synchronous digital system includes:
deterrnining a plurality of disjoint sets of potentially conflicting state transition rules such that concurrent application of any pair of rules taken from two different of said sets do not conflict in their access to the data elements and concurrent application of any pair of rules taken from a single of said sets may conflict in their access to one or more of


the data elements; and
identifying the plurality of groups of multiple of the state transition
rules such that each group includes at most one rule from each of the


sets of potentially conflicting state transition rules.
16. The method as claimed in claim 15 wherein processing the
:
asynchronous system specification to form the specification of the synchronous digital system includes:
specifying a component of said digital system that implements a selection of at most one rule from each of the sets of potentially conflicting rules.
17. The method as claimed in claims 1 to 8 wherein processing the
asynchronous system specification to form the specification of a

synchronous digital system includes:
enumerating groups of the state transition rules such that concurrent application of multiple rules in any single of the groups does not conflict in their access to the data elements.
18. The method as claimed in claim 17 wherein processing the
asynchronous system specification to form the specification of a
synchronous digital system includes: specifying a component of said
digital system that encodes the enumeration of the plurality of groups.
41

19. The method as claimed in claims 1 to 8 wherein processing the asynchronous system specification to form the specification of a
synchronous digital system includes:
identifying a plurality of groups of multiple of the state transition rules

including determining a plurality of disjoint sets nf notentially
conflicting state transition rules such that concurrent application of any
pair of rules taken from two different of said sets do not conflict in their
access to the data eleraents and concurrent application of any pair of
rules taken from a single of said sets may conflict" in their access to one
or more of the data elements;
enumerating groups of the state transition rules such that concurrent
application of multiple rules in any single of the groups does not conflict
in their access to the data elements including enumerating one or more
separate groups of state transition rules that do not conflict within
\ "?.
different ones of the disjoint sets of potentially conflicting state
transition rules; and j
identifying the plurality of groups of multiple of the state transition
rules is such that each of said groups includes at most one enumerated
i group from each of the sets of potentially conflicting state transition
rules.
20. The method as claimed in claims 1 to 8, wherein processing the asynchronouds system specification to form the spacification of the synchronous digital system includes:
42

f
identifying sequences of two or more state transitions rules such that a state transition of the synchronous system that corresponds to applications of any of said sequences of two or more rules in sequence corresponds to application of the last of said sequence alone.
21. The method as claimed in claim 20 wherein processing the
asynchronous system specification to form a specification of the
synchronous digital system includes: specifying a component of said
digital system that implements a selection of the last of the sequence

when each of the sequence of two or more rules are enabled.

22. The method as claimed in claims 1 to 8, wherein it comprises:

identifying the plurality of groups of multiple of the state transition
i ; rules including determining a plurality of disjoint sets of potentially
conflicting state transition rules such that concurrent application of any
pair of rules taken from two different of said sets do not conflict in their
access to the data elements and concurrent application of any pair of
rules taken from a single of said sets may conflict in their access to one
or more of the data elements; and identifying sequences of two or more

state transitions rules such that a state transition of the synchronous system that corresponds to applications of any of said sequences of two or more rules in sequence corresponds to application of the last of said sequence alone including identifying said sequences such that each sequence includes only state transitions from a,single of said disjoint
42

sets;
wherein identifying the plurality of groups of multiple of the state
transition rules is such that each of said groups includes at most one of
the sequences of two or more state transitions from each of the sets of
potentially conflicting state transition rules

23. The method as claimed in claims 1 to 8 wherein processing the
asynchronous system specification to form a specification of the
synchronous digital system includes:
specifying a component, of said synchronous system that for at least
some of the data elements implements a calculation of new values for
those data elements for a state transition of ?the synchronous system
■ , | that corresponds to sequential application f |the state transition rules
according to a predetermined order.
24. The method as claimed in any of claims 1 to & wherein processing the
asynchronous system specification to form the specification of a
synchronous digital system includes: determining a plurality of disjoint
sets of potentially conflicting state transition rules such that concurrent
application of any pair of rules taken from two different of said sets do
not conflict in their access to the data elements and concurrent
application of any pair of rules taken from a single of said sets may
conflict in their access to one or more of the data elements; and
identifying a. sequence of state transition rules from each of the
44

plurality of disjoint sets.
25. The method as claimed in claims 1 to 8 wherein it comprises: scheduling the state transition rules, including identifying one or more sets of conflicting state transition rules for which state transitions specified by different rules in one of the conflicting sets may conflict in their access to data elements of the system.
26. The method as claimed; in claim 25 wherein determining the specification of the synchronous digital system includes determining a specification of arbitration logic that generates trigger signals for sets of state transitions rules such that the rules in each of said sets are
t
applicable in at least some order to the asynchronous digital system.
27. The method as claimed in claim 25 wherein determining the specification of the synchronous digital system includes determining said specification such that during any clocking period, the synchronous digital system makes state transitions equivalent to at most one state transition rule from each conflicting set of state transition rules.
28. The method as claimed in claim 25 wherein determining the specification of the synchronous system includes determining a specification of arbitration logic associated with each conflicting set of

state transition rules such that the arbitration logic generates trigger . signals that allow at most one state transition rule from the conflicting set of states to be applied in a single clocking period.
29. The method as claimed in claim 28 wherein the arbitration logic
j includes a round-robin priority encoder for generating the trigger
signals,
30 The method as claimed in claims 1 to 8, wherein it comprises:
transforming the asynchronous; system specification for the first system

into a second specification of a second system, wherein the second specification includes a second plurality of state transition rules, and the second system includes pipeline;
wherein at least some of the slate transitions rules for the first system each correspond to a plurality of the second state transition rules such that each of these corresponding rules of the second plurality of state transition rules is associated with a different stage of the pipeline.
31. The method as claimed in claims 1 to 8, wherein it comprises:
adding a plurality of composite rules to the asynchronous system specification, wherein each composite rule is associated with a plurality of the state transition rules, and each state transition specified by one of the composite state transition rules is equivalent to a sequence of state transitions each specified by the state transition rules.
46

32. The method as claimed in claims 1 to 8 wherein accepting the specification of the data elements includes accepting a specification; of an abstract data type, and wherein determining a specification or a synchronous digital circuit includes determining an implementation? of the abstract data type.
33. The method as claimed in claim 32 wherein the abstract data type is a first-in-first-out queue, and the implementation of the abstract data type is a register.
34. The method as claimed in claims 1 to 8 wherein the synchronous digital system includes a computer processor, and state transitions of the first system are associated with changes in; values stored in storage elements of the computer processor.
35. The method as claimed in claims 1 to 8 wherein determining the specification of the synchronous system includes determining a specification of a digital circuit, and optimizing the preliminary specification a correspondence between the preliminary specification and the specification of the asynchronous system
36. The method as claimed in any of the; preceding claims, wherein processing the asynchronous specification to form a specification of the
47

synchronous digital system includes specifying a component of the digital system that implements a selection of enabled rules for application in a state transition, including in at least some state transition a selection of the two or more rules of the identified sequence.
Dated this 15th Day of February, 2002.

Documents:

abstract1.jpg

in-pct-2002-00197-mum-abstract(19-08-2005).doc

in-pct-2002-00197-mum-abstract(19-8-2005).pdf

in-pct-2002-00197-mum-abstract(granted)-(3-10-2007).pdf

in-pct-2002-00197-mum-abstract-19-8-2005.pdf

in-pct-2002-00197-mum-assignment-15-2-2002.pdf

in-pct-2002-00197-mum-cancelled pages-(18-11-2005).pdf

in-pct-2002-00197-mum-cancelled pages-15-2-2002.pdf

in-pct-2002-00197-mum-claims(15-2-2002).pdf

in-pct-2002-00197-mum-claims(19-08-2005).doc

in-pct-2002-00197-mum-claims(amended)-(18-11-2005).pdf

in-pct-2002-00197-mum-claims(amended)-(19-8-2005).pdf

in-pct-2002-00197-mum-claims(amended)-(23-12-2005).pdf

in-pct-2002-00197-mum-claims(granted)-(3-10-2007).pdf

in-pct-2002-00197-mum-claims(granted)-19-8-2005.pdf

in-pct-2002-00197-mum-correspondence(ipo)-(31-10-2007).pdf

in-pct-2002-00197-mum-correspondence(ipo).pdf

in-pct-2002-00197-mum-correspondence.pdf

in-pct-2002-00197-mum-description(complete)-(15-2-2002).pdf

in-pct-2002-00197-mum-description(granted)-(3-10-2007).pdf

in-pct-2002-00197-mum-drawing(15-2-2002).pdf

in-pct-2002-00197-mum-drawing(19-8-2005).pdf

in-pct-2002-00197-mum-drawing(granted)-(3-10-2007).pdf

in-pct-2002-00197-mum-drawing-19-8-2005.pdf

IN-PCT-2002-00197-MUM-FORM 1(15-2-2002).pdf

in-pct-2002-00197-mum-form 13-23-12-2002.pdf

in-pct-2002-00197-mum-form 19-18-8-2004.pdf

in-pct-2002-00197-mum-form 1a-19-5-2005.pdf

in-pct-2002-00197-mum-form 2(15-2-2002).pdf

in-pct-2002-00197-mum-form 2(granted)-(3-10-2007).pdf

in-pct-2002-00197-mum-form 2(granted)-19-8-2005.pdf

in-pct-2002-00197-mum-form 2(title page)-(15-2-2002).pdf

in-pct-2002-00197-mum-form 2(title page)-(granted)-(3-10-2007).pdf

in-pct-2002-00197-mum-form 3-15-2-2002.pdf

in-pct-2002-00197-mum-form 5-15-2-2002.pdf

in-pct-2002-00197-mum-power of authority(19-8-2005).pdf

in-pct-2002-00197-mum-power of authority-15-2-2002.pdf

in-pct-2002-00197-mum-power of authority-19-8-2005.pdf

in-pct-2002-00197-mum-wo international publication report(15-02-2002).pdf

in-pct-2002-00197mum-form 2(granted)(19-08-2005).doc


Patent Number 210402
Indian Patent Application Number IN/PCT/2002/00197/MUM
PG Journal Number 41/2007
Publication Date 12-Oct-2007
Grant Date 03-Oct-2007
Date of Filing 15-Feb-2002
Name of Patentee MASSACHUSETTS INSTITUTE OF TECHNOLOGY
Applicant Address 77 MASSACHUSWETTS AVENUE, CAMBRIDGE, MASSACHUSETTS 02142-1324,
Inventors:
# Inventor's Name Inventor's Address
1 JAMES C. HOE CARNEGIE MELLON, ECE DEPARTMENT, D201 HH, 5000 FORBES AVENUE, PITTSBURGH, PENNSYLVANIA 15213,
2 ARVIND MITHAL 34 LOMBARD ROAD, ARLINGTON, MA 02476, U.S.A.
PCT International Classification Number G06F 17/50
PCT International Application Number PCT/US00/22888
PCT International Filing date 2000-08-18
PCT Conventions:
# PCT Application Number Date of Convention Priority Country
1 09/377,372 1999-08-19 U.S.A.
2 60/164,201 1999-11-09 U.S.A.