From the image below, implement the following division algorithm:

C = 0 ;

do {

A = A B ;

C = C + 1 ;

} while (A >= 0) ;

C = C 1 ;

This algorithm uses a do-while loop. It is slightly different than a normal while loop. The computer will always go through the loop once, and then check the condition before it performs it again. This differs from a while loop that will only perform the loop IF the condition is first met.

a) Show a Flow Chart, like the one shown in the previous segment, Programming a CPU with Machine Language - The Setup, this will help you break the program into its various states. Example format shown below.

b) Show a table (like the one shown below), listing the values of the control signals necessary to implement the algorithm above. You may assign registers any way you like to hold your variables and necessary data, but state it up front!

Example format:

c) Show an Execution Trace for your program in step (b). For your trace, assume A=5 and B=2. Example below (A=5 and B=2 and x = "don't care" in the example).

+/- ART 3 AR2 21 x k-bit Memory Algorithm: 23 x 16-bit Memory Aw while (B > 0) { C = C +A; B = B - 1; "Control" "Register WE File" ALUout NZP TEST NextPC +1 LAPC State 0: B > 0? Our program has 4 possible states. PC - will hold that state! True, next state =1 while (B>0){ C = C +A; B = B - 1; State 1: C = C+ A // END PROG. Goto state 2 State 2: B = B-1 Go back to state 0 False, next state = 3 Program done, Stay in state 3 forever State 3: Loop Let's implement the algorithm in control memory Algorithm: +- ARI ARz Aw we | nzp | Nextpc Functionality: while (B > 0) { C = C + A; In + um 11 ROWO TEST: is B > 0 ROW 1 ROW 2 Register File: RO = 0 (for comparison) R1 = 1 (to subtract from B) R2 = A (initially 5 for ex.) R3 = B (initially 2 for ex.) R4 = C (initially 0) ROW 3 Let's implement the algorithm in control memory Algorithm: AR1 ARZ AN WE NZP NextPC Functionality: while (B > 0) { C = C + A; B = B-1; ROW O R3 RO ROW 3 TEST: is B > 0 ROW 1 R2 000 C=C+A ROW 2 ROW O Register File: RO = 0 (for comparison) R1 = 1 (to subtract from B) R2 = A (initially 5 for ex.) R3 = B (initially 2 for ex.) R4 = C(initially O) B=B-1 and loop back to rowo ROW 3 1 x | x X 111 ROW 3 Loop forever on row 3 NZP Test Tricks NZP Condition: 000 Forces output to O NZP Condition: 111 Forces output to 1 Multiply Execution Trace Register values before PC "executes" 0 0 2 Clock Cycle PC (State) #0 ART ARZ WE | Aw ALUout 3 10 RO R1 R2 ("A") R3 ("B") R4 ("C") 10 10 10 Operation B>O? C=C+A B=B-1 B>O? C=C+A B=B-1 B>O? LOOP LOOP +/- ART 3 AR2 21 x k-bit Memory Algorithm: 23 x 16-bit Memory Aw while (B > 0) { C = C +A; B = B - 1; "Control" "Register WE File" ALUout NZP TEST NextPC +1 LAPC State 0: B > 0? Our program has 4 possible states. PC - will hold that state! True, next state =1 while (B>0){ C = C +A; B = B - 1; State 1: C = C+ A // END PROG. Goto state 2 State 2: B = B-1 Go back to state 0 False, next state = 3 Program done, Stay in state 3 forever State 3: Loop Let's implement the algorithm in control memory Algorithm: +- ARI ARz Aw we | nzp | Nextpc Functionality: while (B > 0) { C = C + A; In + um 11 ROWO TEST: is B > 0 ROW 1 ROW 2 Register File: RO = 0 (for comparison) R1 = 1 (to subtract from B) R2 = A (initially 5 for ex.) R3 = B (initially 2 for ex.) R4 = C (initially 0) ROW 3 Let's implement the algorithm in control memory Algorithm: AR1 ARZ AN WE NZP NextPC Functionality: while (B > 0) { C = C + A; B = B-1; ROW O R3 RO ROW 3 TEST: is B > 0 ROW 1 R2 000 C=C+A ROW 2 ROW O Register File: RO = 0 (for comparison) R1 = 1 (to subtract from B) R2 = A (initially 5 for ex.) R3 = B (initially 2 for ex.) R4 = C(initially O) B=B-1 and loop back to rowo ROW 3 1 x | x X 111 ROW 3 Loop forever on row 3 NZP Test Tricks NZP Condition: 000 Forces output to O NZP Condition: 111 Forces output to 1 Multiply Execution Trace Register values before PC "executes" 0 0 2 Clock Cycle PC (State) #0 ART ARZ WE | Aw ALUout 3 10 RO R1 R2 ("A") R3 ("B") R4 ("C") 10 10 10 Operation B>O? C=C+A B=B-1 B>O? C=C+A B=B-1 B>O? LOOP LOOP