Non-Deterministic Specificationfor Sequential SynthesisForrest Brewer, Andrew Seawright, Andrew [email protected], [email protected], [email protected] of Electrical and Computer EngineeringUniversity of California, Santa BarbaraWhy another sequential specification tool?• Deterministic Model encourages global state-based specification style- Efficiency decreases rapidly with increasing numbers of states- Many properties of the machine make sense only for a subset of ‘bits’- Small changes in STG may lead to arbitrarily large changes in implementation• Designers are forced into partitioning the behavior into a set of managableDFSM’s- No guarantee that chosen partition is globally efficient- Very easy to create specification problems such as safety, deadlock, etc.- Can be diffcult to obtain desired global behavior from local behaviors of submachines- Applicable tools force bottom-up design methodology- Engineering changes on global specification can be difficult to integrate in submachines• Current Tools support only very small DFSM’s- State assignment optimized only for minimal (log), 1-hot or 2-hot, encodings- Tools limited by deterministic state complexity -- itself exponential in circuit size- Little correlation between STG and circuit implementation- Minimization of States/Latch # does not necessarily minimize designNon-Deterministic Finite State Machines• Use NDFA’s to describe DFA behavior in a more powerful representation• Can use NDFA to succinctly describe external (sequential) behaviorconstraints (ref. Brayton and Watanabe)0/11/01/01/00/1-/11/10/01/0• Multiple tokens (control points)• Can describe non-deterministic behavior• Any DFA graph is also an NDFA graph• Any NDFA graph can be rewritten to becomea DFA, if it is deterministic• Circuit model is effectively an NDFA-- localstates only depend on logic fan-in tree• Any synchronous circuit can be modeled bya comparably linear size NDFAAn Example NDFA• If a transition does not exist, the token is lost (destroyed)• If multiple transitions for an input, tokens are created• ‘1’ outputs dominate ‘0’ outputs---/---1-1/00011-/0101--/0000--/100SASBSCSD1-1/001Sample Input Sequenceinput state(s) outputstart A110 A,C 010101 A,B,C 000000 A,D 100101 A,B,C 000111 A,B,C 011111 A,B,C 011Eqivalent DFA BehaviorKISS TableState Transition GraphS0S2S5S3S4S1110/001100/000100/000110/001110/001100/000101/0000--/000100/000111/011101/0100--/100111/0010--/0000--/000100/000111/011101/010110/001101/000111/0010--/0000--/100101/010111/011101/000111/001100/000110/001.i 3.o 3.p 32.s 6.r S20-- S0 S2 100100 S0 S0 000101 S0 S1 000110 S0 S0 001111 S0 S1 00101- S2 S2 000111 S2 S3 001110 S2 S4 001001 S2 S2 000101 S2 S5 000-00 S2 S2 0000-- S1 S2 100100 S1 S0 000101 S1 S1 010110 S1 S0 001111 S1 S1 0110-- S3 S2 000111 S3 S1 011110 S3 S0 001100 S3 S0 000101 S3 S1 0100-- S4 S2 000111 S4 S1 001110 S4 S0 001101 S4 S1 000100 S4 S0 00001- S5 S2 000111 S5 S3 011110 S5 S4 001001 S5 S2 000101 S5 S3 010-00 S5 S2 000Machine Specification via Event Sequences• An alternative specification method is to describe those sequences of inputstimula (events) which cause desired outputs (actions)- a set of sequences defines DFA states implicitly- a timing diagram describes an event sequence, usually between 2 or more machines:- above, m1 outputs ALE and ADD and then looks at WAIT to see when DATA will be valid- m2 looks at ALE, latches the address, outputs WAIT until it is ready with the dataM1: [ALE][ADD], WAIT?, WAIT?, WAIT?, ~WAIT, Latch DATAM2: ALE?[Latch ADD], [WAIT], [WAIT], [WAIT], [~WAIT], [DATA]ADDDATAWAITALECLKMachine Specification via Event Sequences II• Typically, a timing diagram represents an infinite set of such sequences- no bound on the number of wait’s above...• a synchronous event sequence samples inputs and sets outputs on clock edges- particular clocking scheme can be abstracted to “sampling” and “signaling” events- sampling and signalling events must be well ordered- logically dependent signals disambiguate timing via clock synchronization• a set of such sequences can be ‘open’ or ‘closed’- a set is closed if any input sequence matches at least one event sequece- an implementation is necessarily closed, but not necessarily specified• a set of sequences can be “forbidden”- a specification may contain sequences that are required, some that are don’t care, and some thatmust not occur- typically, there is design freedom implicit in how the don’t care sequences are implementedRegular Expressions describe sets of event sequences- RE’s can represent any finite automata, and many possible event sequences• 3 Classical Regular Expression Operators- concatenation: “A,B” means “input A followed by input B”- closure: “A*” means “zero or more occurrences of A”- union: “A || B” means “either input A or input B”• A 4th “operator”: the action.- Creates a “complete” language allowing arbitrary symbolic machine description- However, the description is not guaranteed to be concise or complete• Above pair of Regular Expressions describe all possible sequences impliedby the previous timing diagramM1: (.[ALE][ADD], WAIT*, ~WAIT, .[Latch DATA])*M2: (ALE[Latch ADD], ~Dready*[WAIT], Dready[DATA])*Why Regular Expressions?• Regular expressions directly map to NDFA’s- NDFA has one state per identifier in the RE• A Circuit can always be constructed directly from RE- One memory element per NDFA state is always sufficient• So-- A simple Regular Expression => a Simple Circuit• A valid specification may be ‘open’ -- allowing great freedom to optimize theclosure or DFAa,(b* || ~a)Regular ExpressionaλabNDFA state diagramλabaCircuitExtended Regular Expressions• We can extend RE’s by adding several operators which keep the languagefinite, but greatly improve the conciseness:• Sequential AND: A&&B both A and B must accept at the same time• Sequential NOT: !A -- accepts whenever A is not accepting• Exception: A !E B -- B is enabled if A ‘fails’- a failure occurs if the input sequence matches no part of Regular Expression A- exceptions provide a succinct means of describing how to close a machine- although the complement of a DFA is not a state machine, the complement of a RE defined as allsequences which do not match the given set -- is a DFA!- consider a protocol decoder machine on a network: if a series of noise impulses