Lecture 6 Algorithmic State Machines (ASMs)
ECE 474A/57AComputer-Aided Logic DesignControl and Datapath Interaction Binary information in digital systemcan be classified into two categories DataInput dataControlSignalsLecture 6Algorithmic State Machines (ASMs) Discrete elements of informationmanipulated by arithmetic, logic,shift, and other data processing Operations implemented via digitalcomponents such as adders,decoders, muxes, etc. Input lsOutputdataControl Provides command signals thatcoordinate the execution of variousoperations in data section toaccomplish desired taskECE 474a/575a1 of 21What Control Path Implements? Many representationsIngredients 1/3 cup unsweetened cocoa 1/4 cup cornstarch 2 tablespoons butter 2 2/3 cups skim milkSteps1.2.3.Combine all ingredients in a small saucepan.Heat over low heat, stirring constantly, untilmixture boils. Boil gently, stirring constantly,for one minute.Pour into serving dishes and chill untilthickened. Lamp doesn’tworkLamp pluggedin? return n;elsePlug in lamp Sequential way of representing procedural steps and decision paths for algorithm No time relations incorporated}YesBulb burnedout?Replace bulb ASM chart Representation of sequence of events together with timing relations between states ofsequential controller and events occurring while moving between stepsNoBuy new lampRecipeFlowchartECE 474a/575aFlowchart vs. ASM Conventional flowchartreturn fib(n-1) fib(n-2);YesAlgorithmic State Machine (ASM) Flowchart defined specifically for digital hardware algorithmsint fib(int n){if (n 2)NoFlowchart Convenient way to graphically specify sequence of procedural steps and decisionpaths for algorithm Enumerates sequence of operations and conditions necessary for execution Finite set of instructions/steps to solve a problem Terminates in finite time at a known end state 2 of 21Flowcharts and Algorithmic State Machines (ASM)Sequencing of control signals to execute algorithm implemented by circuitAlgorithm ECE 474a/575aComputer Program3 of 21ECE 474a/575a4 of 211
ASM Chart State boxThree basic elements State box Decision box Conditional box State name and binary code placed on topof box Register operations and names of outputsignals generated in state placed inside boxState and decision boxes used in conventional flowcharts Conditional box characteristic to ASM Binary codeRegister operationsConditionMoore-type output signals Output signal asserted: Start OP 1Mealy-type output signalsExit pathExit pathExit pathState BoxDecision Box5 of 21Reflects the effect of an input6 of 21Diamond shaped boxUnique to ASM Inputs come from one of exit paths ofdecision boxesRegister operation or outputs listed insidebox generated during given state Exit pathExit pathExit pathRegister operationsMealy-type output signals Generated as Mealy-type signals Associated with the state transition In binary case one path represents true theother false, represented by 1 and 0respectively 1BExample Status of input B checked Conditional operation executed dependingon result coming from decision box0Example If B 1, assert Incr Reg signal Otherwise Incr Reg remains unchanged Check B If B is true ( 1), take path marked 1 If B is false ( 0), take path marked 0ECE 474a/575a From exit path of decision boxexternal or internal, input or status Condition to be tested inside Two or more outputs represent exit pathsdependant on value tested ECE 474a/575aConditional BoxCondition 0101R 0Start OPConditional BoxDecision Box Moore-type output signals Launches some operation in datapathECE 474a/575a Binary codeRegister operationsS pause Register R is to be cleared to 0Register operationsState nameExample State name: S pause Binary encoding: 0101 Register operation: R 0From exit path of decision boxState nameUsed to indicate states in control sequence7 of 21ECE 474a/575a1B0Incr Reg8 of 212
ASM Block Interpretation of Timing OperationsReset bStructure consisting of One state box All decision and conditional boxesassociated with its exit paths S 0Block has one entrance and anynumber of exits pathsEach block in ASM dedicated to stateof system during one clock cycleF0010Clear B011S 3100Simplifications E0F0In ASM the entire block considered asone unitS 10101Clear B1S 2011S 3100 All operations within block occurringduring single edge transition The next state evaluated during thesame clock System enters next state S 1, S 2, orS 3 during transition of next clockASM chart consists of one or moreinterconnect ASM Blocks9 of 21ASM Example 001A A 1 clear B Go to state S 311S 2ECE 474a/575a S 0 If E 1E0 ASM Block not usually drawn becauseblocks are well defined Can label just the “1” and omit the “0” Reset bConventional flowchart, evaluation ofeach follows one another Reg A incremented Condition E evaluatedA A 1S 1 001ECE 474a/575a10 of 21ASM Example ContinuedConvert pseudo code to ASM chartExample Want to detect the number of 1’s in a 2bit register called Input start input indicates when to begincomparison busy output indicates when comparison inprogress ones hold count value F outputs resultReset bS0:busy 0;ones 0;S 0busy 0ones 0if(start 1)goto S1elsegoto S0S1:busy 1;if(Input[1] 1)ones ;if(start 1)goto S1elsegoto S0S1:busy 1;if(Input[1] 1)ones ;start 11S 1010busy 1goto S2S2:busy 1;if(Input[0] 1)ones ;Input[1] 1goto S2S2:busy 1;if(Input[0] 1)ones ;1ones S 2goto S3S3:busy 0;F ones;011busy 1S 3Input[0] 11111busy 0F onesones goto S0ECE 474a/575aS0:busy 0;ones 0;00111 of 21goto S3S3:busy 0;F ones;goto S0ECE 474a/575a12 of 213
ASM – MuxASM – Full AdderDescribe a 4x1 MUX using a ASM x1 x2 x3 x4s0s10123s1 s0f0001x1x21101x3x4001A1s1coutBS 01s0F x4F x3F x2aFs014x1 mux001cinFA11fF x1ECE 474a/575aabcinf cout00001111001100110101010101101001000101111cinf 1cout 11b1f 0cout 113 of 211cinf 0cout 1f 1cout 0f 0cout 1b1cinf 1cout 0f 1cout 0ECE 474a/575aSmaller Multiplier Describe a 1-bit full adder usingan ASM chart S 0cinf 0cout 014 of 21Smaller Multiplier -- Sequential (Add-and-Shift) StyleMultiplier in array style Fast, reasonable size for 4-bit: 4*4 16 partial product AND terms, 3 adders Rather big for 32-bit: 32*32 1024 AND terms, and 31 addersSmaller multiplier: Basic idea Don’t compute all partial products simultaneouslyRather, compute one at a time (similar to by hand), maintain running suma32-bit adder would have 1024 gates hereb0b1b2b3a2a1a0pp4 pp3 pp2 pp1a300Step 10110 0 0 11Step 20110 0 01 1Step 30110 00 1 1Step 40110 00 1 1(running sum)0000(partial product) 0 1 1 0(new running sum) 0 0 1 1 000110 0 1 1 0010010 000000100100010010 000000010010010010a (5-bit)00a (6-bit)0 00 (7-bit). and 31 adders here (big adders)p7.p0ECE 474a/575a15 of 21ECE 474a/575a16 of 214
Smaller Multiplier -- Sequential (Add-and-Shift) StyleNote that shifting running sumright (relative to partial product)after each step ensures partialproduct added to correct runningsum bits multiplierstartmultiplicandmdldStep 20110 0 01 1Step 30110 00110000 01100011000110 0 1 1 0010010010010 00000010010 multiplierregister (4)loadmrld loadclearshr mr0 1, add multiplicand to running sumShift running sum right 1 positionStep 40110 0011controllerS 4mdld 1mrld 1rsclear 1rsshr 1multiplicandregister (4)loadmrldmultiplierregister (4)load running sumregister 00110000018 of 21Able to convert between formatsOnce we have a FSMD, we’ve already seen how to implement in hardware0101A1Reset b0101S 0R 0Start OP4-bit addermr3mr2mr1mr0rsloadrsclearrsshr1mr2S 2loadclearshrECE 474a/575aS pauseS 14-bit adderproductmultiplicandmdldS 0rsload 10011mr3mr2mr1mr0ASMs to FSMDsmultiplier1multiplierregister (4)loadproduct17 of 21start1mrld0110Step 4 Check multiplier bit 3 (mr3) Shift running sum right 1 positionASM – Sequential Multipliermr1mdldrsloadrsclearrsshrStep 3 Check multiplier bit 2 (mr2) Shift running sum right 1 positionrunning sumregister (8)ECE 474a/575astartmultiplicandmultiplicandregister (4)loadmr0 1, add multiplicand to running sumShift running sum right 1 positionStep 2 Check multiplier bit 1 (mr1)4-bit addermr3mr2mr1mr0(running sum)0010010(partial product) 00000 0 0 1 0 0 1 0 (new running sum)Reset bstartStep 1 Check multiplier bit 0 (mr0)rsloadrsclearrsshrStep 10110 001 1multiplierStep 0 Set running sum to 0 Load valuesmultiplicandregister (4)loadcontrollerDesign circuit that computes onepartial product at a time, adds torunning sumcontroller Smaller Multiplier -- Sequential (Add-and-Shift) StyleB100S 1running sumregister (8)E0Incr Regloadclearshr001A A 1F1Clear B1010 S 2011S 3100rsload 1S 51mr0rsshr 1rsload 1product1mr3S 3S 0rsload 1rsshr 1A1S pauseR 0Start OP 1S 6rsshr 1BE’F’E’FB’ / Incr Reg 1S 1ECE 474a/575a19 of 21ECE 474a/575aS 2A A 1E / Clear B 1S 320 of 215
Not Used Much, But There are commerical ASM Editors Mentor Graphics Summit Design, Inc. Others ECE 474a/575a21 of 216
Each block in ASM dedicated to state of system during one clock cycle Simplifications ASM Block not usually drawn because blocks are well defined Can label just the “1” and omit the “0” ASM chart consists of one or more interconnect ASM
Introduction of Chemical Reaction Engineering Introduction about Chemical Engineering 0:31:15 0:31:09. Lecture 14 Lecture 15 Lecture 16 Lecture 17 Lecture 18 Lecture 19 Lecture 20 Lecture 21 Lecture 22 Lecture 23 Lecture 24 Lecture 25 Lecture 26 Lecture 27 Lecture 28 Lecture
In these notes we focus on algorithmic game theory, a relatively new field that lies in the intersection of game theory and computer science. The main objective of algorithmic game theory is to design effective algorithms in strategic environments. In the first part of these notes, we focus on algorithmic theory's earliest research goals—
Lecture 1: A Beginner's Guide Lecture 2: Introduction to Programming Lecture 3: Introduction to C, structure of C programming Lecture 4: Elements of C Lecture 5: Variables, Statements, Expressions Lecture 6: Input-Output in C Lecture 7: Formatted Input-Output Lecture 8: Operators Lecture 9: Operators continued
“algorithmic” from “software” has been also reflected in media studies. [2] “Drawing on contemporary media art practices and on studies of visual and algorithmic cultures, I would like to develop the idea of algorithmic superstructuring as a reading of aest
Algorithmic Trading Table: Proportions of trading volume contributed by di erent category of algorithmic and non-algorithmic traders in the NSE spot and equity derivatives segment (for the period Jan-Dec 2015) Custodian Proprietary NCNP Total Spot Market Algo 21.34% 13.18% 7.76% 42.28% Non-
aforementioned model. Thus, the Triangulation Algorithmic Model is provided and defined to aid in understanding the process of measurement instrument construction and research design. The Triangulation Algorithmic Model for the Tri-Squared Test The Algorithmic Model of Triangulation is of the form (Figure 2). Where,
What problems have beginners in learning algorithms/programming? Give some examples why algorithmic thinking is useful in other subjects/daily life Try to give a definition of Algorithmic Thinking : Title: Learning Algorithmic Thinking with Tangible Objects Eases Transition to Computer Programming
v. Who is doing algorithmic trading? Many algorithmic trading firms are market makers. This is a firm that stands ready to buy and sell a stock on a regular and continuous basis at a publicly quoted price. Customers use them to place large trades. Large quantitative funds (also called investment or hedge funds) and banks have an algorithmic .
