Indiana University Computer Science Department

B443/543 Computer Architecture Spring 1998

Lab Assignment #2:

Designing and Coding the Gemini Simulator:
An Application of the STAIR Problem-Solving Process
---------------------------------------------------


Table of Contents
-----------------

1. The STAIR Method
2. Initial Design
3. The K Stamp: Gemini's Microcontroller Simulator
4. The D Stamp: Gemini's Datapath and Memory Simulator



1. The STAIR Method
-------------------

"How should I design and code the Gemini simulator?"

This is a frequently asked question, probably because your first glance at the 
Gemini documentation suggested a bewildering number of choices. We can analyze 
the problem, and make a few decisions about the kind of simulator we will 
build, by applying a method to use our critical thinking and analysis skills. 
We can make our task easier by doing this before starting to write code.  
("Resist the urge to code!" - Harlan Mills, no relation to me. Or it might 
have been Knuth or Wirth who said it; I can't find the reference.)

The problem-solving technique I will introduce is the STAIR method used in 
A110 and other Axxx courses.  It is easy to learn and use, and helps focus 
your thinking about a problem. It also has the advantage that it can be a 
"mental toolbox" in which you can keep many more problem-solving techniques 
than I'll discuss here, at hand and ready to use.

STAIR is an acronym for a repetitive five-step process:

	- State the problem

	- identify the Tools and Techniques available to solve it

	- Analyze the problem to decide which tools and techniques to
	  use, how to use them, and what the solution will look like, or
	  design an Algorithm to solve the problem

	- Implement the prototype solution

	- Revise the solution, Repeating the STAIR method as often as
	  necessary

The STAIR method is a guide, not a straight-jacket, so as I design the Gemini 
simulator you will see that I often depart from the purely linear
S-T-A-I-R-S-T-A-I-R sequence and follow one more like S-T-A-T-A-I-R.  Also, 
once a solution begins to take shape, most people stop using the STAIR method 
explicitly because the solution is "staring them in the face".

Applying the STAIR method involves thinking introspectively about the problem, 
and about your personal methods of solving it.  It also involves your ability 
to reflect on the problem situation to reduce it to a statement that will lead 
to action.  Catiline, a Roman senator, was the world's expert at this, 
repeatedly declaiming in the senate, "Delenda est Carthago!" (Carthage must be 
destroyed!).

It was.

So, with that bit of history to encourage us, but in a constructive way, let's 
start designing the Gemini simulator.


2. Initial Design
-----------------


This is the statement of the problem I came up with after reading the lab 
assignment:

	- Simulate the Gemini microprocessor on two BASIC Stamp IIs



At this point identifying tools & techniques must defer to analysis, as a 
question immediately arises:

	Q: What kind of simulator?

Simulators exist that model computers at the:

	- device level (transistors)
	- circuit level (groups of transistors that form logic gates)
	- logic, or gate, level (Boolean logic functions)
	- register transfer level (data and control flow within processor)
	- functional level (abstract machine)

At each level the temporal behavior of the computer (timing) is modeled 
differently as the level of abstraction increases. Because Gemini will be used 
later in lab exercise #3 to study pipelining, we need a simulator that can be 
modified later, but that is no more complex than necessary. Therefore the 
question is answered:

	A: Gemini will be simulated at the register transfer level.

This has immediate consequences. The clock generator, ø, will not be simulated 
explicitly, but by the synchronization between the two Stamps. This also means 
that the clock timing is not accurate, but that is OK.  As long as the 
simulator performs all of the operations called for in a clock cycle, even 
sequentially as long as this does not cause incorrect results, the goals of a 
register transfer level simulation will be met.  (The goals are to observe 
data flow through the processor under the control of microcode, to transfer 
data in a structurally correct way, and to be able to modify the simulator in 
Lab Assignment #3 to introduce pipelining.)



Now we return to tools and techniques.

We have available the Gemini documentation.  The microprogrammer's model of 
Gemini provides almost all the information we need to create the structure of 
our simulator.  




The tools and techniques we apply are:

	- decomposing the Gemini, and
	- modularizing the resulting components

One technique that is useful in this process is to view a program as a 
collection of objects, actions on the objects, and interactions between the 
objects. (One can do object-oriented design without an object-oriented 
programming language, although it's a mental exercise instead of a coding 
exercise.)

                                                     

Next we analyze the microprogrammer's model of the Gemini. Our technique 
produces three questions about the diagram:

	Q1: What parts of the diagram represent objects?
	Q2: What parts of the diagram represent, or IMPLY, actions on objects?
	Q3: What parts represent, or IMPLY, interactions between objects?

We can answer the questions in order by inspection of the diagram:

	A1: The two major objects are:

		- datapath and memory, and
		- the microcontroller

Each is inside its own "box", and the documentation indicates that each "box" 
should be simulated on one BASIC Stamp II.  Let's designate the datapath and 
memory "box" as "D", and the microcontroller "box" as "K" (from Baer's 
terminology, where K = controller).  Now we answer the remaining questions:

	A2: There are no actions on D and K, but -inside- D and K we find that:

		- D transfers and processes bytes in response to microinstruction
		  bits sent from K, and

		- K steps and/or branches through the microcode to get the 
		  microinstructions to control D

	A3: There are two interactions between D and K:

		- D sends the IR and CYF to K every clock cycle (because
		  the IR output is always active), and

		- K sends control signals (ø + active microinstruction bits) to
		  D throughout the clock cycle, except when the next microinstruction
		  is latched on the rising edge of ø

It is necessary to define the earlier statement about our simulator's timing:

	"The clock generator, ø, will not be simulated explicitly, but by the 
	 synchronization between the two Stamps."

The interactions between D and K, synchronized via the serial data link, is 
used to simulate the clock. This technique is explained in the next section.
                                                     


Think of the Gemini simulator as operating in an endlessly repeating cycle:



The simulator will pass control back and forth between the D Stamp and the K 
Stamp until it is turned off.  If we had a red LED light up when the D Stamp 
is active, and a green LED light up when the K Stamp is active, we would see 
this sequence of blinking LEDs, shown above, over a time interval. This 
synchronized behavior implicitly simulates Gemini's clock, ø.




The alternating operation of the pair of processors simulates the clock, ø. 
Relating the blinking LEDs to the timing diagram from the Gemini documentation 
shows that the D Stamp is active during the "middle" of the clock cycle, while 
the K stamp is active on the rising edge of the clock cycle.

                                                     


The clock simulation is inaccurate: the two LEDs will actually blink equally 
long, because their duration is governed by the software that each stamp 
executes during its active part of the cycle.  The K Stamp has a lot to do 
during the "rising edge" of the clock, so its LED would blink for a longer 
time than it would if our simulation of the clock was correct.  But as long as 
we can count clock cycles -- and we can -- this is as good as the simulation 
needs to be.  Of course we need to relate this technique to our previous 
analysis and decomposition of the Gemini simulator into the D and K stamps.



Let's start by simplifying the microprogrammer's model to deal with the 
communication between the two Stamps.  Our intermediate goal -- our first step 
in implementing the simulator -- is now becoming clear, so let's state it:

	Write a PBASIC program that produces the synchronized behavior that 
	implicitly simulates the clock.


                                                     

We can make the analysis easier by introducing another technique, removing 
everything that is not essential to the problem.  When we do that, the 
microprogrammer's model is reduced to the following diagram.


At this point we know enough to identify the programming and circuit building 
tools that we need to configure the D and K Stamps, and get them running. If 
you haven't done it yet, now is the time to print the BASIC Stamp II 
description of the SERIN and SEROUT instructions.  It would also be a very 
good idea if you printed the application note from the <READ CAREFULLY>:

	the BASIC STAMP I manual

titled "14: Networking Multiple Stamps".

If you just string a wire between two Stamps and start trying to communicate 
via the serial commands, you MAY DAMAGE THE STAMPS.  Take some time to read 
the applications note to understand in detail why.

So, what tools (and parts) do we need?  These:

	- SERIN documentation
	- SEROUT documentation
	- red and green LEDs
	- 220 and/or 330 ohm resistors

Let's see what we do with them.  It is time to develop the algorithm for our 
PBASIC program, and the circuit schematic for the Gemini simulator.


                                                     

Finally!  At last!  "A" stands for algorithm!  We will use the "circle" 
diagram to develop the program structure for our D and K Stamps.  It is 
labelled below with the actions each stamp must perform:


The D and K Stamps are locked into an infinite loop, each doing some 
processing, then waiting for the other's message. The only problem now is how 
to start this loop rolling (or, how to start this "clock" ticking). The answer 
is that we will have D begin by waiting for K's message (after all, how can D 
perform an action without a microinstruction?).  We will have K start by 
selecting the microinstruction at the label RESET in the PROLOG (see the 
Gemini documentation on the structure of a microprogram). Diagrammatically our 
"circle" figure now becomes this:



                                                     

The algorithm is complete, but the system is not: we need its schematic.  Here 
is where a little "back of the envelope" scrawling is a valuable technique!  
(I also like to draw these things on napkins, tablecloths, and 3x5 cards.)

                                                     

It's ugly, but this drawing gets the idea across.  Note that the schematic is 
drawn to match the layout of the two Stamps on the prototype board, even to 
the central channel that carries +9 volts and ground.  It is easier to wire up 
the circuit if the schematic visually matches the physical circuit.  (Although 
this only works for small and simple circuits.)


The important feature of this circuit is the use of an open-collector single-
wire connection between two BASIC Stamp IIs so that we don't fry the 
electronics. This means that we must tie the connection to +9 volts, and send 
data that is active low (that is, the bit we send pulls the +9 volt signal 
down to ground).  We only need one wire because one stamp will always be the 
transmitter, and the other the receiver, and because we will perform our 
"handshake" -- the recognition by one Stamp that the other is signalling -- in 
software using the SERIN and SEROUT commands.

Finally, so that we can watch the simulation of the clock by the interaction 
of synchronous processors, we have a red LED on the D Stamp, and a green LED 
on the K Stamp, just like the figures shown previously.

Let's implement the program, then wire up the D and K Stamps, and see if the 
initial design of the Gemini simulator works.




I referred to the BASIC Stamp Manual to find the correct syntax for the SERIN 
and SEROUT commands. From earlier analysis of the problem, the data must be 
sent over an open-collector link, with inverted logic (binary 1's are sent as 
0's to pull down the data line). This is chosen because a Stamp can sink more 
current than it can source, so inverted data will be more reliably 
transmitted.

                                                     

As I was coding the D Stamp simulator I realized that there is no reason to 
send nine of the 33 bits to it because they control the K stamp. (Eight bits 
are the next microcode address, one is the next microPC selector.) Therefore I 
can send a clean three-byte package to the D Stamp containing only the 
datapath and memory control bits.

I also recognized that there is no need to "and" the active control bits with 
the clock because the clock is implicit.  Thus, if a bit is one in the 
microinstruction, it is implicitly "and"ed with the simulated clock just by 
being transmitted from the K Stamp to the D Stamp.

                                                     


Here are the two Stamp programs:

	'D Stamp Simulator ("skeleton" program simulates clock)

	uinst var byte(3)
	ir    var byte
	cyf   var byte

	start:
	loop:	serin 15, 32+$4000,	'19.2Kbaud, open-collector, inverted
			60000, loop, 
			[wait("d"),
			bin uinst(1),	'receive 24 microinstruction bits
			bin uinst(2),
			bin uinst(3)]
		high 8
		pause 1000		'datapath and memory actions go here
	retry:	serout 15, 32+C000,
			[60000,
			retry,
			"k",
			bin ir,
			bin cyf]
		low 8
		goto loop
		end


	'K Stamp Simulator ("skeleton" program simulates clock)

	uinst var byte(3)
	ir    var byte
	cyf   var byte

	start:	goto retry
	loop:	serin 15, 32+$4000,	'19.2Kbaud, open-collector, inverted
			60000, loop, 
			[wait("k"),
			bin ir,
			bin cyf]
		high 7
		pause 1000		'microcontroller actions go here
	retry:	serout 15, 32+C000,
			[60000,
			retry,
			"d",
			bin uinst(1),	'send 24 microinstruction bits
			bin uinst(2),
			bin uinst(3)]
		low 7
		goto loop
		end




I have not tested these programs or wired up the stamp yet, so they are 
probably wrong.  I will do that Friday in the LH120 lab.  Then we can continue 
to work on the lab assignment, repeating the STAIR method to design the D and 
K Stamp simulators.


Summary
-------

Remember the STAIR method.  See if you can apply it to begin designing the D 
and K Stamp simulators, using the skeleton programs as a starting point.