Princeton University
COS 217: Introduction to Programming Systems

Assignment 8: A Digital Circuit Simulator: Compiled Version

Purpose

The purpose of this assignment is to help you learn about SPARC machine language. It also will give you more experience with advanced C programming and the GNU/UNIX programming tools.

Background

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 Task

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.

An Example

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.

Flushing the Instruction Cache

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.

Logistics

You should develop on arizona. Use Emacs to create source code. Use gdb to debug.

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 8 yoursourcecodefiles makefile readme

Grading

As always, we will grade your work on functionality and design, and will consider understandability to be an important aspect of good design. (Function-level comments in both .h and .c files are critical documentation.) To encourage good coding practices, we will take off points based on warning messages during compilation.

Princeton University COS 217: Introduction to Programming Systems