COS 217: Introduction to Programming Systems

This assignment is a follow-on to the previous one.

Fundamentally, a digital circuit simulator consists of two phases: a parsing phase followed by a simulation phase. The simulation phase can be very time consuming, especially if the circuit has many flip flops and inputs, or if the simulation runs for many clock pulses. Thus it is desirable that the simulation phase be efficient. One way to make the simulation phase efficient is to translate (or "compile") it into machine language.

Your job in this assignment is to modify your program from the previous assignment so the core of its simulation phase is expressed in SPARC machine language.

Specifically, to compute the next state of its circuit your simulation phase should (recursively) traverse the circuit internal form, generating SPARC machine language instructions in an array. The machine language instructions should define a subroutine that simulates the circuit during a single clock pulse. The subroutine should accept as parameters (1) an array filled with the current input values, (2) an array filled with current flip flop values, and (3) an array that the subroutine should fill with the "next" set of flip flop values. The subroutine should use the first two arrays to compute the values within the third, and then return. After generating the machine language subroutine, your program should repeatedly call it -- once for each clock cycle.

More specifically...

Your Simulator from the previous assignment uses this (informally stated) algorithm:

For each clock pulse...

For each flip flop F...

Traverse F's expression tree to compute its next state.

Your Simulator for this assignment should use this (informally stated) algorithm:

Add a "save" instruction, expressed in SPARC machine language, to the beginning of an array. Thus the array contains the beginning of a subroutine.

For each flip flop F...

Traverse F's expression tree, adding to the array SPARC machine language instructions that compute F's next state. Those instructions should assume that the subroutine's first formal parameter is an array of input values, that its second formal parameter is an array of current flip flop values, and that its third formal parameter is the array of next flip flop values that it should compute.

Add "ret" and "restore" instructions, expressed in SPARC machine language, to end of the array. Thus the array contains a complete subroutine.

For each clock pulse...

Call the subroutine that resides in the array with three actual parameters: an array of current input values, and array of current flip flop values, and an array of next flip flop values.

Suppose you give your digital circuit simulator this "two-bit counter" circuit description:

INPUT x ; FLIPFLOP A B ; NEXT A (~A & ~B & ~x) | (~A & B & x) | (A & ~B & x) | (A & B & ~x) ; NEXT B (~A & ~B & ~x) | (~A & ~B & x) | (A & ~B & ~x) | (A & ~B & x) ;

Then your program's simulation phase might generate this array:

Index |
Contents |
Explanation |

0 |
9DE3BFA0 |
save %sp, -96, %sp |

1 |
E0066000 |
ld [%i1 + 0], %l0 ! Load A |

2 |
A01C2001 |
xor %l0, 1, %l0 ! Compute ~A |

3 |
E2066004 |
ld [%i1 + 4], %l1 ! Load B |

4 |
A21C6001 |
xor %l1, 1, %l1 ! Compute ~B |

5 |
A00C0011 |
and %l0, %l1, %l0 ! Compute ~A & ~B |

6 |
E2062000 |
ld [%i0 + 0], %l1 ! Load x |

7 |
A21C6001 |
xor %l1, 1, %l1 ! Compute ~x |

8 |
A00C0011 |
and %l0, %l1, %l0 ! Compute ~A & ~B & ~x |

9 |
E2066000 |
ld [%i1 + 0], %l1 ! Load A |

10 |
A21C6001 |
xor %l1, 1, %l1 ! Compute ~A |

11 |
E4066004 |
ld [%i1 + 4], %l2 ! Load B |

12 |
A20C4012 |
and %l1, %l2, %l1 ! Compute ~A & B |

13 |
E4062000 |
ld [%i0 + 0], %l2 ! Load x |

14 |
A20C4012 |
and %l1, %l2, %l1 ! Compute ~A & B & x |

15 |
A0140011 |
or %l0, %l1, %l0 ! Compute (~A & ~B & ~x) | (~A & B & x) |

16 |
E2066000 |
ld [%i1 + 0], %l1 ! Load A |

17 |
E4066004 |
ld [%i1 + 4], %l2 ! Load B |

18 |
A41CA001 |
xor %l2, 1, %l2 ! Compute ~B |

19 |
A20C4012 |
and %l1, %l2, %l1 ! Compute A & ~B |

20 |
E4062000 |
ld [%i0 + 0], %l2 ! Load x |

21 |
A20C4012 |
and %l1, %l2, %l1 ! Compute A & ~B & x |

22 |
A0140011 |
or %l0, %l1, %l0 ! Compute (~A & ~B & ~x) | (~A & B & x) | (A & ~B & x) |

23 |
E2066000 |
ld [%i1 + 0], %l1 ! Load A |

24 |
E4066004 |
ld [%i1 + 4], %l2 ! Load B |

25 |
A20C4012 |
and %l1, %l2, %l1 ! Compute A & B |

26 |
E4062000 |
ld [%i0 + 0], %l2 ! Load x |

27 |
A41CA001 |
xor %l2, 1, %l2 ! Compute ~x |

28 |
A20C4012 |
and %l1, %l2, %l1 ! Compute A & B & ~x |

29 |
A0140011 |
or %l0, %l1, %l0 ! Compute (~A & ~B & ~x) | (~A & B & x) | (A & ~B & x) | (A & B & ~x) |

30 |
E026A000 |
st %l0, [%i2 + 0] ! Store the result as the next value of A |

31 |
E0066000 |
ld [%i1 + 0], %l0 ! Load A |

32 |
A01C2001 |
xor %l0, 1, %l0 ! Compute ~A |

33 |
E2066004 |
ld [%i1 + 4], %l1 ! Load B |

34 |
A21C6001 |
xor %l1, 1, %l1 ! Compute ~B |

35 |
A00C0011 |
and %l0, %l1, %l0 ! Compute ~A & ~B |

36 |
E2062000 |
ld [%i0 + 0], %l1 ! Load x |

37 |
A21C6001 |
xor %l1, 1, %l1 ! Compute ~x |

38 |
A00C0011 |
and %l0, %l1, %l0 ! Compute ~A & ~B & ~x |

39 |
E2066000 |
ld [%i1 + 0], %l1 ! Load A |

40 |
A21C6001 |
xor %l1, 1, %l1 ! Compute ~A |

41 |
E4066004 |
ld [%i1 + 4], %l2 ! Load B |

42 |
A41CA001 |
xor %l2, 1, %l2 ! Compute ~B |

43 |
A20C4012 |
and %l1, %l2, %l1 ! Compute ~A & ~B |

44 |
E4062000 |
ld [%i0 + 0], %l2 ! Load x |

45 |
A20C4012 |
and %l1, %l2, %l1 ! Compute ~A & ~B & x |

46 |
A0140011 |
or %l0, %l1, %l0 ! Compute (~A & ~B & ~x) | (~A & ~B & x) |

47 |
E2066000 |
ld [%i1 + 0], %l1 ! Load A |

48 |
E4066004 |
ld [%i1 + 4], %l2 ! Load B |

49 |
A41CA001 |
xor %l2, 1, %l2 ! Compute ~B |

50 |
A20C4012 |
and %l1, %l2, %l1 ! Compute A & ~B |

51 |
E4062000 |
ld [%i0 + 0], %l2 ! Load x |

52 |
A41CA001 |
xor %l2, 1, %l2 ! Compute ~x |

53 |
A20C4012 |
and %l1, %l2, %l1 ! Compute A & ~B & ~x |

54 |
A0140011 |
or %l0, %l1, %l0 ! Compute (~A & ~B & ~x) | (~A & ~B & x) | (A & ~B & ~x) |

55 |
E2066000 |
ld [%i1 + 0], %l1 ! Load A |

56 |
E4066004 |
ld [%i1 + 4], %l2 ! Load B |

57 |
A41CA001 |
xor %l2, 1, %l2 ! Compute ~B |

58 |
A20C4012 |
and %l1, %l2, %l1 ! Compute A & ~B |

59 |
E4062000 |
ld [%i0 + 0], %l2 ! Load x |

60 |
A20C4012 |
and %l1, %l2, %l1 ! Compute A & ~B & x |

61 |
A0140011 |
or %l0, %l1, %l0 ! Compute (~A & ~B & ~x) | (~A & ~B & x) | (A & ~B & ~x) | (A & ~B & x) |

62 |
E026A004 |
st %l0, [%i2 + 4] ! Store the result as the next value of B |

63 |
81C7E008 |
ret |

64 |
81E80000 |
restore |

Note that it is column 2 of the table -- the SPARC machine language instructions that define a subroutine -- that your program should generate. The table contains the first and third columns only to help you interpret column 2.

For reasons that will be described in precepts, your program should flush the memory in which your array/subroutine resides before it calls the subroutine for the first time. To do that, your program should call the provided flushICache function.

The file /u/cs217/Assignment8/iflush.h contains the declaration of the flushICache function. In that same directory, the file iflush.S contains the definition of the flushICache function, in SPARC assembly language.

You should submit:

- The source code files (.h and .c) that comprise your program. You should not submit the given lexer.h, lexer.c, parser.h, parser.c, iflush.h, or iflush.S files.
- A makefile. The first rule in the makefile should command the make utility
to build a file named
**circuitsim**containing the executable version of your program. Your makefile should use the "-Wall", "-ansi", and "-pedantic" compiler options. Your makefile should**maintain object (.o) files**to allow for partial builds. - A readme file.

Your readme file should contain:

- Your name.
- A description of whatever help (if any) you received from others while doing the assignment, and the names of any individuals with whom you collaborated, as prescribed by the course "Policies" web page.
- (Optionally) An indication of how much time you spent doing the assignment.
- (Optionally) Your assessment of the assignment.
- (Optionally) Any information that will help us to grade your work in the most favorable light. In particular you should describe all known bugs.
- Your informal assessment of the
**relative time efficiency**of (1) the simulation phase of your program from the previous assignment vs. (2) the simulation phase of your program from this assignment. Suggestion: Execute both programs using the Turing machine circuit with an input file that causes simulation for, say, 9999 clock cycles. Observe the CPU times written to stderr.

Submit your work electronically via the command:

/u/cs217/bin/submit 8yoursourcecodefilesmakefile readme