Theflowchart method is a procedure for designing the

processor of a computer. It helps transform the English description

into theformal description a circuit designer needs.

How to Flowchart for Hardware

I I I
Nick Tredennick, IBM T. J. Watson Research Center

The "flowchart method" is a procedure for designing machine. (Doing this imposes a controller structure on
the processor of a computer. The technique works for big the English specification; the problem is to find an effi-
processors and little processors. cient structure.) The block diagram is one of the pro-
A processor has two parts: a "controller" and "execu- cedure's outputs. My flowcharts show the design as the
tion unit. " The controller tells the execution unit what to flow of simple machine actions. An example machine ac-
do when. The controller determines, more than anything tion is "RX-A-ALU," which means "put the contents
else, the processor's "personality." The execution unit is of register RX on the A bus to the ALU. " (That also ex-
a collection of fast but latent capabilities (registers, emplifies the notation; it doesn't get more complicated
ALUs, shifters, and data paths) which are awakened by than that.) One of these is called a "task"; machine states
the controller. can be one or more tasks. I depict the flow of states by
Processor chip designs begin with an appeal: "We need boxes (one for each state); I draw these in a specific for-
a processor that's twice as good as any rival." "Ar- mat, and it matters that you draw the states precisely the
chitects" turn the petition into an English description of way I say. With the flowchart method you see major
the machine (in IBM's System/370, this is the "Principles flow (a complicated microprocessor can fit on six 8½2
of Operation" manual). Engineers use the techniques of by 11-inch pages) without losing important detail.
logic design and circuit design to implement the machine "RX-.A-ALU" is uncluttered by the usual hardware
from the English description. We have lots of books to details that hide significant controller structure issues.
help us with logic design and circuit design. The trouble is, The hdfdware is debugged using the flowcharts; they are
nobody says how to transform the English description the authoritative reference for the design.
into the kind of formal description a circuit designer
needs. The procedure is carried out with a particular tech-
It's much like a mathematical word problem. The hard nology in mind. Decisions in the procedure are based on
part is getting the equations from the written description the capabilities of the particular technology. The pro-
of the problem. Once we have the equations we can apply cedure does not depend on the implementation method.
documented methods to find the solution. The English This means the same flowcharts are used to implement the
description of a chip is like a book-length mathematical chip with combinational logic, PLAs, or microcode! I will
problem! The hardware flowcharts in this paper are a show how to implement a simple processor using the flow-
bridge between English and the circuit designer. These charts.
flowcharts are a compact formal description of what the I tell how to flowchart hardware using just pencil and
machine does. paper. I describe flowcharting using such simple tools
The method I describe was used to design the controller because
in the MC68000 microprocessor. The flowchart method is (1) The method is useful whether the designer has just
both procedure and notation. The designer follows the a desk and wastebasket, or several million dollars in
procedure to express the design in the particular form I computers and fancy equipment.
call flowcharts. Unlike most procedures, this one does (2) Design automation should be subservient to the
not start out by presuming a block diagram for the design method. It should support the design pro-

0ecember 1981 0018-9162/81/1200K0087$00.75 (3 1981 IEEE 87

 cedure, not be the design procedure. (Often, engi- ter indirect, indexed, etc.), and
neers' methods are solely the result of available (4) registers (as seen by the programmer).
design automation tools; I think that's bad.)
Execution unit. A processor's execution unit (or "data
flow") details are not usually published: users don't want
Prerequisites to know, users shouldn't know, or manufacturers want
competitive advantages kept secret. We need a block
Flowcharts tell I get from the architecture to the diagram of the execution unit which shows the following:
implementation. 1 ,ink the programmer's (external) (1) programmer's register set,
model to the hardw e (internal) implementation. Flow- (2) additional registers (like the instruction register,
charts specify exactly how commands from the instruc- program counter, and temporary registers),
tion set are carried out using execution unit hardware. We (3) ALU and any special function units (such as a
must have the instruction set summary and an execution shifter),
unit specification before we begin flowcharting. (4) internal data paths, and
(5) rules of operation.
Instruction set summary. The instruction set summary
is published as a necessary part of the user's manual. (See, All this information (except maybe some rules of opera-
for example, the MC68000 Preliminary User's Manual tion) should be in the execution unit block diagram. The
for the Motorola MC68000 or the MCS-86 User's Manual rules of operation tell what can and cannot be done with
for the Intel 8086.) The instruction set summary has the execution unit pieces (registers, buses, arithmetic
units, etc.). The rules of operation also tell clock phases,
(1) instruction formats, timing, and electrical load constraints for the pieces.
(2) operations (ADD, AND, SUB, etc.),
These rules are imposed by circuit design limits.
(3) addressing modes (base-plus-displacement, regis- If you are responsible for both the execution unit and
the flowcharts, do the execution unit first. To design the
execution unit, I recommend doing trial flowcharts for 10
frequently used instructions to determine an initial execu-
tion unit structure. I think a simple bus-oriented structure
is best, so I start with that. The execution unit will evolve.
In a current (1981) VLSI implementation, some limits on
your interconnect scheme will come from the circuit de-
signers. For example, having no more than three buses
allows bus wiring to pass right over the registers and
arithmetic units without using extra chip area.

Example processor
To avoid confusing details, I illustrate the method with
a simple microprocessor, called MIN. Figure I shows the
instruction format and register set; Figure 2 shows a
subset of the instruction set summary. This subset is ade-
quate to demonstrate flowchart construction. Figure 3
shows a sufficiently detailed block diagram of the execu-
tion unit. It also includes some rules of operation; others
will be added as we progress.
Figures 1, 2, and 3 don't have the usual details about
word length, instuction length, address length, bus width,
ALU size, and register size. Though you know this infor-
mation, it doesn't necessarily change the sequence of
operations for the execution unit. The sequence of opera-
tions depends on the ratio of these parameters to each
other and not their absolute value. You implement the
design from the flowcharts with a particular word length,
etc.

Flowchart objectives
Now we have ample information to construct flow-
Figure 1. MIN instruction format and register set. charts. But we face difficult questions:
88 COM PUTER
 (1) What are the design objectives?
(2) Which objective is most important? Which one is
next? Least?
Here are some reasonable design objectives:
* Limit controller size to some fraction of a single chip.
(Since profit goes up as die size goes down, there will
be pressure to make the controller smaller even when
it fits.)
* Make the machine as fast as possible (and certainly
faster than its contemporaries).
* Complete the project early-to give the product an
early start in the market.
* Make the flowcharts easy to translate into hardware.
This illustrates the value of a good project manager. He
ranks the objectives!

Flowcharts
It is time to begin the flowcharts.
How do we begin?
What do we write?
How do we write it?
I will suggest methods that have worked for me. I use a
register transfer notation to describe the operations ofthe
execution unit. Each statement in this notation is called a
task in the flowcharts. Each state contains one or more
tasks. Use rectangles for states. (In a microprogrammed Figure 2. MIN instruction set summary.

Figure 3. MIN execution unit block diagram.

December 1981 89
 controller, each state becomes a microword.) A sequence loads. (This information comes from the circuit de-
is a succession of states. Work on large sheets of high- sign engineer.)
quality quadrule paper (preferably 17 x 22-inch vellum * ALU inputs are from the internal A bus and either K
with 10 lines per inch). Large sheets make it simpler to see or the internal B bus.
and to plan large segments of the control flow, and high- * When the ALU is a destination, register TI is auto-
quality paper lasts through many changes. matically loaded from the combinational ALU out-
It takes months to complete the flowcharts for a com- put at the end of the state time.
plicated controller. So you won't have to copy several * Any transfer to the address out (AO) buffer (see
generations of flowcharts, observe these rules: Figure 3) signals a data transfer to the (on-chip) bus
* Work in pencil. (Use a 0.5m/m Pentel with F lead.) controller for the external bus. This bus controller
* Work on the back of the vellum so you won't erase postpones the next state until the external transfer is
the grid. complete.
* Use an erasing shield and an electric eraser. In Figure 4, time.advances from the top of the page to the
* Always use a cover sheet to prevent smearing. bottom of the page, except within a state. Tasks within a
* Plan changes on scratch paper and transcribe them state appear to be concurrent and are governed by rules-
to the vellum. of-operation timing. In a microprogrammed controller
* Always use reproductions for work and reference. (I each state is one microcycle (and may have phases such as
reduced the copies to 8.5 x I 1-inch for easier use.) source, transfer, destination, and precharge).
* Accumulate changes (in red ink) on a reproduction.
* Do trial level 2 flowcharts (level 2 flowcharts are ex- The notation of the flowcharts. Keep the register-
plained later) on 8.5 x lI -inch scratch paper with transfer notation simple! It must capture the essence of
1.5-inch high, 2-inch wide penciled-in rectangles as what the machine is doing without all the details-which
guides. come later. You may think this is a simple notation in-
Figure 4 shows flowchart sequences for the register-to- vented for just this one case. Well, that's somewhat true.
register ADD instruction and the register-to-memory The notation is modified to fit the problem. If I want to do
ADD instruction using the MIN execution unit (Figure 3) a special task, I modify the notation to fit. I want the
and a simple register-transfer notation. Each box is a notation to be a simple, natural, readable way to express
state. Each line entry in a state is a task. Tasks are ex- what the machine is doing. The notation is not formally
pressed in the register-transfer notation; the notation has defined. In a formal notation, constructs might prevent
a source-bus-destination format. Alphabetize tasks in natural expression of tasks and hinder the design.
each state by source (if there are multiple destinations on a Flowcharts are graphical notations which depict the
single line alphabetize them too); we will use this to com- processor in two ways:
pact the flowcharts later on. Some rules of operation for (1) They visually emphasize changes in sequence and
the execution unit are evident from Figure 4: concurrency for whatever you are doing.
* A transfer from source to bus to destination takes (2) They visually communicate the relationship of se-
one state time. quence to concurrency for whatever you are doing.
* The source cannot drive more than three destination The design is made up of sequential state flows made up of
concurrent task flows. Each task is a sequential source-
bus-destination flow. Flowcharts are a flow-intensive
notation; you see the concurrent and sequential nature of
things before you see the things.
Execution speed. The flowchart sequences in Figure 4
are not complete. They do not include the instruction
fetch and the program counter (PC) increment. The PC
increment and instruction fetch could be added to the
beginning or end of both sequences (with different conse-
quences). Which leads to the fastest controller? Just what
is the fastest controller?
I propose the following definition for controller effi-
ciency:
* Relevant external bus activity in every state is
evidence of sufficient controller efficiency.
* Restated: The controller is efficient if execution
never delays external bus cycles. (If some other part
of the system is the bottleneck, what I do is good
enough.)
I can't give a general definiton for the fastest controller
Figure 4. Execution of register-to-register ADD and register-to-memory because I think it depends on what the controller does. I
ADD instructions. have given a definition that works for a microprocessor;

90 COMPUTER
but this definition is not the one an application engineer Increased speed may not be the only objective of the
would use, because he won't want the external bus tied up merge. We should also merge the tasks to create as many
by the processor all the time. identical states (across instruction types) as possible. We
Figure 5 augments the examples of Figure 4 with the PC assume that a controller with fewer unique states is
increment and instruction fetch. I removed the lines con- smaller.
necting boxes because they are unnecessary and it saves I added one more thing in Figure 6. IRE is the instruc-
space. The more states you fit on a page, the more of the tion register for execution (see Figure 3). The IRE can be
design you take in at a glance. (I still use lines to show the decoded in the state during which it is loaded. It allows a
next states of sequences with internal branches.) To make rudimentary prefetch. The IRE holds the current instruc-
a quick measure of efficiency possible, I put a shaded box tion and drives the register selection decoders (for RX and
in the upper right-hand corner of states with external bus RY). (It cannot be changed until after the last RX or RY
activity. Assuming states of equal duration, the overall ef-
ficiency of the execution unit is 20 percent for the register-
to-register instruction and 50 percent for the register-to-
memory instruction. Our competitors will be pleased.
What can we do about it? In some states of each flowchart
sequence the major internal buses (A and B) are not both
occupied. Not good! It should be possible to merge tasks
for greater efficiency. We must find a way to squeeze
more performance out of the execution unit.

Operation tasks and housekeeping tasks. I separate an

instruction's execution into operation tasks and house-
keeping tasks and treat each differently. Operation tasks
are transfers required to perform the instruction. These
tasks (such as accessing operands, storing results, and
moving data to and from the ALU) must occur in a spe-
cific order and may be unique to a particular instruction.
Figure 4 shows the operation tasks for two types of ADD
instructions. Housekeeping tasks, such as incrementing
the PC and fetching the next instruction, must be per-
formed for every instruction. We have some leeway in
when these tasks are accomplished. I separate kinds of
tasks so I can optimize the execution of th,e operation
tasks.

Level 1 flowcharts
Figure 6 shows the flowcharts in a format designed to Figure 5. Revised execution of ADD Instruction examples.
aid merging of operation tasks and housekeeping tasks
for maximum execution efficiency. This is the level I
flowchart format. For each instruction, operation tasks
are in the left sequence and housekeeping tasks are in the
right sequence. The objective is to merge the housekeep-
ing tasks with the operation tasks. The direction of the
merge is into the operation tasks. (We are going to make
the housekeeping tasks "disappear" into the operation
task sequence.) The order of each column must be pre-
served in the final sequence (called the execution se-
quence) but housekeeping tasks can be merged with
operation tasks wherever reasonable, with some restric-
tions. (We shall see consequences of this merging later.)
We would achieve the most efficient execution (for this
execution unit) if we merged the housekeeping tasks with
the operation tasks without increasing the number of
states in the operation task sequence. Usually, it is ade-
quate to have the number of states in the final execution
sequence be significantly less than the total states in
housekeeping task and operation task sequences. Figure 6. Level 1 flowcharts for two types of ADD instruction.

December 1981 91
 reference in the flowchart sequence for the current in-
struction.) The instruction register (IR) can be used to
hold the next instruction until the current instruction is
done. It can be loaded any time during the current instruc-
tion-this is the simple prefetch. More accurately, the IR
gets the word following the current instruction (which
may not be the next instruction if the current instruction is
a branch or a two word instruction).

Level 2 flowcharts
Figure 7 shows the housekeeping tasks merged with the
operation tasks to form what I call level 2 flowcharts. The
efficiency of the register-to-register sequence is 33 per-
cent, and the efficiency of the register-to-memory se-
quence is 75 percent. (We could do much better by pro-
posing a more complicated machine.) Register T2 saves
the operand address in the register-to-memory ADD ex-
ample. The last state changes the IRE and stores the result
because T2 contains the store address and the static de-
coders (which are driven by the IRE) are available (there
are no more RX or RY references).
Figure 7. Experimental reduction of the level 1 flowcharts.
Feedback on execution unit design. Do a level 2
flowchart of the fastest instruction. This will point to in-
adequacies in the execution unit design. In general, we
discover inefficiencies in the structure of the execution
unit as we merge the housekeeping tasks with the opera-
tion tasks. In the register-to-register ADD example, if the
AO buffer had not been accessible from the A bus (see
Figure 3), we would not have been able to do the instruc-
tion in under four states. Less than full use of the A and B
buses in the resulting sequence would signal the need to
improve the execution unit. Figure 8 shows a register-to-
register ADD sequence for an execution unit with no path
from the A bus to the AO buffer. But beware! The in-
creased complexity of the execution unit can increase the
number of unique states and result in a larger controller.
So it is only after carefully studying the flowcharts and the
execution unit that we suggest execution unit changes to
improve the efficiency of the overall design.
Feedback on controller design. Use the format in
Figure 6 to create level I flowcharts for the entire instruc-
tion set. How many sequences is that? The upper bound is
2* *w if w is the instruction length in bits. However, this is
too many because we write only one sequence for each in-
Figure 8. Reduced sequence for an unmodified execution struction-independent of which registers are specified.
unit. (This is an advantage of static decode for the register
fields.) We really only need to decode the operation code
and the mode bits in the effective address field (see Figure
2). Suppose our simple MIN processor has k operations
(ADD, AND, OR, SUB, . . . ) and a address modes
(register indirect, base plus displacement, indexed, . . . ).
If any address mode is valid for any operation we would
need k*a instruction sequences! Clearly, this number can
be large. For example, the Motorola MC68000 lhas about
14 address modes and over 50 instruction types. If an
average instruction has eight states, then we must imple-
ment more than 5600 states in the controller. Our chip
Figure 9. Ranking of MIN instructions. would make a good office partition.

92 COMPUTER
 Idea: If most address modes can be used with most (3) Unfortunately, the STORE instruction reads the
operations, why not share address mode sequences? (Ad- word at the store destination location because it shares the
dress mode sequences are sequences which only do ad- address mode sequences with other instructions. We sac-
dress calculations.) Then we need only k +a sequences, rificed speed to make the controller smaller. (There are
and that is in keeping with our goal to reduce controller other reasons you may not want to do STORE with a read
size. It's a good idea, but what will it cost? It's not free. first. Some systems want locations that are read pro-
Suppose we enter the execution sequence, jump to an ad- tected. Other systems have memory-mapped I/O periph-
dress mode sequence (subroutine), then return to the ex- erals that change states upon read.)
ecution sequence to complete execution of the instruc- (4) The branch-on-zero (BZ) instruction is a special
tion. Such a subroutine call costs time, but it permits a case. Since the condition code (Z) may have been set on
much smaller controller (since the address mode se- the last state of the previous instruction (in TEST, for ex-
quences are shared by most operations). The size and ample), it may not be available to help make the next state
speed goals conflict, so a tradeoff is in the offing. decision. (Because of the simple prefetch, the instruction
How important is the time lost in these subroutine decoder can be operating concurrently with the execution
calls? To find out, have the instruction set designer rank unit. Information that can change in the execution unit
the instructions in order of importance. He could base the cannot be used by the instruction decoder.) As a result,
ranking on static or dynamic frequencies of occurrence. the branch appears between the first and second states of
However he does it, if he designed the instruction set, he the flowchart sequence for the branch instruction. Be-
must take the stand on what is important. The ranking for cause there is a delay state for decision, we must decide
the sample MIN instructions is in Figure 9. what to do with it. The example in Figure 10 shows an an-
We know sharing sequences reduces controller size. ticipated branch prefetch (it is discarded if the branch is
From the ranking we see that slow subroutine calls are not taken). The instruction set designer should be able to
costly because at least three of the four most important in- tell you which condition ought to be made faster (or if
struction types can use any address mode. We won't use both must be equal).
subroutine calls. Assume address mode sequences can be Each instruction's flowchart further shapes the design.
shared by initially entering the address mode sequence Functional characteristics of the controller will eventually
and then branching directly to the appropriate execution be completely defined by the flowcharts. We have still not
sequence. One way to do this in a microprogrammed con- constrained the design to be either combinational or mi-
troller is to have the instruction decoder provide more croprogrammed. Once we combine the standard dual
than one micro address-one for the address mode se- operand instructions (ADD, AND, SUB, . . . ) into one
quence and one for the execution sequence. Flowcharting flowchart sequence for register-to-register and another
has led us to a functional requirement for the controller. for register-to-memory, the level 1 flowcharts are com-
(The instruction decoder is to provide more than a single plete. Then we can work with the level 1 flowcharts, merg-
output.) This shows how controller requirements come ing housekeeping tasks with operation tasks to produce
from the procedure. We have not, however, constrained the level 2 flowcharts.
the implementation of the controller to be combinational
or microcoded; that choice lies in the future. We don't
even have a block diagram of a controller. And we don't Doing level 2 flowcharts
want one yet because we want the procedure to give us the
requirements for the controller independently of what we Figure 11 shows the housekeeping tasks merged with
think a controller should look like. The flowchart method the operation tasks for the instructions in Figure 10. I try
finds requirements for a controller that best fit what the to do this without increasing the number of states in the
machine wants to do (the specification). operation task sequence. In Figure 10 I wasn't able to do
this; I did reduce the number of states from a potential 54
to an actual 35. (I merged 28 housekeeping states with 26
operation states.) If I can't reduce the number of states
Doing level 1 flowcharts significantly (a matter of judgment), I try to improve the
execution unit. Take care in merging, because operation
The level 1 flowcharts for the subset of MIN instruc- tasks can use the same resources (such as buses, registers,
tions are shown in Figure 10. In a real machine, the and arithmetic units) as the housekeeping tasks so ar-
flowcharts have many more address mode and execution bitrary interleaving is not possible. For example, if there
sequences. Note the following things in Figure 10: are PC (program counter) relative address modes, the PC
(1) The register-to-register instructions have execution update (a houskeeping task) must consistently precede (or
sequences which are not sharable with execution se- follow) the address calculation in all of them. If a problem
quences for memory reference instructions. This reduces during an instruction execution causes an interrupt that
the savings from sequence sharing. stores the old PC value, that value should be consistent
(2) The flowchart sequences for standard dual- for all instructions.
operand instructions (ADD, AND, SUB, etc.) are iden- Does this complete the flowcharts? Not quite. Before
tical except for the ALU function. They can use the same we can transform the flowchart description to a hardware
execution sequence if you use the op code directly to implementation, we must identify the states. In Figure 11
specify the ALU operation (the same way register fields I put state identifiers in the lower right-hand corner of
drive the register selection). each state.

December 1981 93
 3-DIN EDB-IR
PC-A-ALU,AO -B-AO,T2 I RY-A-ALUAC
+ 1 -ALU +1-ALU
1 -A-PC

IN-B-ALU WV- I K
Y-A-ALU Ti-B-PC PC-A-ALU,AO
+1-ALU
EDB-DIN
ri1 B-AO,T2 I ~~IR-IRE
I I~~Tl -B-PC

DIN B- RX,T2
IRX-A-ALU IEDB-IR
IDIN-B-ALU
EDB-IR
PC-A-ALIJAC Z-t-AU
+ 1-ALU O-ALU
VU-A-ALU,
+1-ALU IPC-A-ALU,AO
I ~ ~~~+-ALU
T2-A-ALU
O-ALU IR-IRE
Tl B13 PC
IR-IRE
T1-B-PC
|T1-A--DO I-IRE
|T2-B-AO |T1-B-PC

DIN-B-ALU
RX-A-ALU EDB-IR
PC-A-ALU,AO DIN-B-ALU
RX-A-ALU
EDB-IR |DIN-B-T2 |EDB- IR
+1 -ALU PC -A-ALU,
+1 -ALU
|
I~
~PC-A-ALU,AC
~~~+-ALU
ri -A DO
T2- B-AO
IR IRE
Tl-13-B-PC Ti-A-BDO
T2- B- AO
IR-IRE
T1-B-PC
IT2-A-ALU
10-ALU TIIIR-IRE
T13-B-PC

RY-A-ALU,RX
O-ALU EDB-IR IRX-A-ALU IEDBI
IPC-A-ALLIAO
f-
IRY-B-ALU
nA LU, MY
PC-A-ALLIAO
-

+ 1-ALLU
0-AL U PC-A-ALU,AO
+1-ALU
I ~+ 1 ALU
IR IRE
Tl1-A- PC
IR- IRE
Tli-A- PC
T-A-
Tl RY IIR-IRE
T-A-
Tl PC

RX A-ALU EBI
RY-B-ALU PC-A-ALU,AO tUB-DIN
RY-
EOB-IR
A-ALU,AO PC-A-ALU,AO
RY-A-ALU
-1- ALU IEBI
IPC-A-ALU,AO
++I -ALU +1-ALU +1 -ALU |+1-ALU
"I-A -RY IR-IRE DIN-B-RX IR-IRE RX-A-DO IR-IRE
Ti-A-PC Tl-A-RY Ti -A-PC Ti - B- AO,RY T1-A-PC

Figure 10. Example level 1 flowcharts for the MIN processor.

94 COMPUTER
 1-UlB T
PC-A-ALU,AO - B-AO,T2 Y-A-ALU,AO
+1 -ALU -1-ALU

Ti -A- PC

DIN-B-ALU IR-IRE
RY-A-ALU T1-B-PC PC-A-ALU,AO'
+ 1-ALU
| BRZz3
EDB-DIN R-IRE
Ti -A-AO,T2 T1-B-PC

DIN- B-RX,T2 RX-A-ALU,DU

EDB-IR T2-B-AO RX-A-ALU EDB-IR
PC-A-ALU,AO O-ALU PC-A-ALU,AO
+1-ALU +1-ALU
| |TEST1
IR-IRE EDB-IR Ti -A-DO IR-IRE
Ti-B-PC PC-A-ALU,AO T2-B-AO T1-B-PC
T2-A-ALU + 1-ALU T2-A-ALU
O-ALU - O-ALU
R-IRE EDOB-I R
Ti-B-PC PC-A-ALU,AO
+1-ALU

IR-IRE
Ti-B-PC

EUB-IK KY-A-ALU
PC-A-ALU,AO PC-A-ALU,AO RY-B-ALU RY-A-ALU,AO -1-ALU
RY-B-RX,T2 RX-B-RY,T2 +1 -ALU
+i-ALU +1-ALU
-
WLi
IR-IRE IR-IRE EDB-IR DIN-B-RX RX-A-DO
Ti-B-PC Ti-B-PC PC-A-ALU,AO Ti -A-RY T1-B-AO,RY
T2-A-ALU T2-A--ALU Tl-B-RY
O-ALU - o-ALU , + 1-ALU
IR-IRE EDB-IR EDB-IR
Tl-B-PC PC-A-ALU,AO PC-A-ALU,AO
+ 1-ALU + 1-ALU

IR-IRE IR-IRE
Ti -B-PC Ti-B-PC

Figure 11. Merged level 1 flowcharts for the MIN processor.

December 1981 95
 If we add descriptive information we ease the transition be reached by a conditional branch, a sequence
from flowcharts to hardware. But what descriptive infor- branch (a new address from the instruction de-
mation will help? What information do we need? Listed coder), or a direct branch (address from the current
below are some useful kinds of descriptive information microword).
for translating flowcharts into hardware. I listed informa- (5) State identification (state ID). Each state should
tion useful for implementing the MIN controller; a more have its own identifier. Use descriptive identifiers.
complicated controller requires more information (for For example, STRMI is the state ID for the first
register-decoder substitutions or operand sizes, for exam- state in the store register-to-memory sequence.
ple). Refer to Figure 12. Figure 13 shows the level 2 flowcharts with the above in-
(1) Sequence labels. These labels identify each execu- formation. We used one method to reduce the number of
tion sequence or address mode sequence with the states: share address mode sequences among the execu-
instructions or address modes using the sequence. tion sequences. A second method is to eliminate duplicate
Here are the abbreviations: states.
@ - means the quantity is an address Eliminate duplicate states at the tail ends of sequences
ALU - arithmetic and logic unit by specifying a direct branch to a common sequence. This
d - displacement merges the ends of flowchart sequences. Compare the
MEM - memory ending states of each sequence in Figure 13 with all ending
OP - operation code states below and to the right of the current sequence to
RX - source operand register merge the flowcharts. Alphabetic organization of tasks,
RY - address or operand register (See corner shadings, and access type indicators make it easier
Figure 2) to compare states. The result is Figure 14; it has one-third
(2) Access type. This says whether the controller is us- fewer states than the Figure 13 flowcharts. This is the
ing the external bus for an instruction fetch or a most direct method for reducing controller size using
data read or write. flowcharts. When I did this for a machine with hundreds
(3) AL U function and condition code setting. The of states, I wrote each state on a separate IBM card and
ALU function determines the operation code for alphabetized the deck. I then compared each card with the
the ALU for a particular state. The condition code cards below it to find duplicate or similar states.
setting tells if a condition code is to be set. When you merge the level I flowcharts to make level 2
(4) Next state transition. The next state transition tells flowcharts, consider moving operands into temporary lo-
how the controller determines the next state. In a cations early so later states in the sequence are more in-
microprogrammed controller, the next state might dependent of exact instruction details. Similar states oc-
curring at other than the end of the sequence cannot be
merged (states ADRMI, BRZZI, and POPRI in Figure
14 could be made identical, but none can be eliminated).
We implement the design from the level 2 flowcharts.
Though a real processor is much more complicated
than the MIN processor, the flowcharts for a real pro-
cessor look just like the ones in Figure 14.

Implementing the design

The choice of whether to implement in microcode is
finally upon us. I will not say how to make the choice be-
tween a microcoded and a combinational design, nor will
I give all of the implementation details. It is not because I
don't want to, but because this paper is about the flow-
chart method, not implementation. I want to show you
how flowcharts are used, to prove to you that flowcharts
are really useful. So, first, I will tell how I would use them
for a microcoded design and a PLA design; then I will tell
how I would use them for a combinational design. These
designs are simplified to illustrate the idea.
Combinational designs are currently viewed as bad
compared to the "regular" PLA and ROM (microcoded)
designs. Regular designs fit better with automated design
techniques. Relative size and speed advantages among the
types are difficult to prove. Combinational designs evolved
from design of simpler machines and are appropriate for
very simple machines. Microcoded designs are appropriate
for machines using ROM or RAM as a building block for
Figure 12. Template for a level 2 flowchart state. the controller or for machines that need microprogram-
96 COMPUTER
 3-DIN liDH EDB-IR
PC-A-ALU,AO _B-AO,T2I X N RY-A-ALU,AC
+ 1-ALU +1 -ALU

Ti-A-PC

DIN-B-ALU TI-B-L CUD-in

RY-A-ALU T1-B- PC PC-A-ALU,AC
+1-ALU
ABDM3
EDB-DIN DRR IR-IRE
T1-A-AO,T2 X-N Tl - B- PC

IX-A-ALU,DD
EDB-IR ADD-X 2- B-AO -A-ALU EDB-IR
PC-A-ALU,AO I-ALU PC-A-ALU ,A
+ I-ALU LDRM2
LDRM1 STRM1
R-IRE NA EDB-IR HIR Ti-A-DO
Ti-B-PC
T2-A-ALU
ADD-S )C-A-ALU,AC
+ 1-ALU
O ADD-N T2-B-AO
_
Ti-B-PC
T2-A-ALU
)-ALU RB STRM3
STRM2
R-IRE NA EDB-IR
11-B-PC XN PC-A-ALU,A(
+1-ALU
RB

_ IR-IRE
Ti-B-PC

IRK RX-A-ALU NA EB-UIN RY-A-ALU

'C-A-ALU,AC IDD-X RY-B-ALU X-S RY-A-ALU,A -1-ALU
+1-ALU
IX- B-RY,T2
+ 1-ALU
+1-ALU
OPRR2I
STRR1 OPRR1 TI
R-IRE R-IRE NA EDB-IR ' R DIN-B-RX X--A--D-O
T1-B- PC T1-B-PC ADD-S PC-A-ALU,AO ADD-N Tl -A-RY Ti -B-AO,RY X-N
r2-A-ALU T2-A-ALU T-B_RY
Tl
O-ALU )-ALU RB + 1-ALU RB
OPRR3 PUSH3
STRR2 OPRR2 PUSH 2
1|1IR-IRE NA IEDB-IR EDB-IHR
PC-A-ALU,AO ADD-N
T-B-PC
Tl RB |P+C1-^-A-LALU ,AC + 1-ALU
PUSH4
PUSH3
IR-IRE NA
1*11 iEll I Tl1-B-PC Ti-B-PC X-N

Figure 13. Format for final version of the level 2 flowcharts.

December 1981
 mable controllers. PLA designs are good for VLSI because (3) the next micro control store address, and
chip area is at a premium. (4) the source of the next micro control store address.
The microword contains the address of the next micro-
Microprogrammed controller. Figure 15 is the block word for direct microinstruction branches; for condi-
diagram of a simple microprogrammed controller. I show tional branches, the next address would be modified by
only enough detail to prove the controller will work. I information from the execution unit. For branches from
want you to see the relationship between the controller address mode sequences to execution sequences or be-
and the flowcharts. tween whole instructions, the next address is a decoded
Some translation of the IRE contents provides the ad- IRE value (possibly modified by the NA field from the
dress of the first microword in the micro control store.
The control store microword format is Figure 16. Each microword).
Each microword has control fields which are decoded
flowchart state (see Figure 14) corresponds to a micro- to drive the control lines in the execution unit and con-
word. The microword can specify troller. The decode logic (see Figure 15) drives the control
(1) register transfers (data and control registers), lines by mixing static information and timing signals with
(2) the ALU function and condition code setting, the microword control fields. Static information does not

Figure 14. Merged level 2 flowchart example.

98 COMPUTER
change during the instruction execution and can go direct- you will probably want to assign control store locations to
ly to the decode logic. The register fields in a register-to- make the address decoder smaller (also, certain control
register ADD instruction, for example, do not change store addresses are reserved for reset, interrupt, and other
during instruction execution. special sequences).
In a simple microprogrammed controller implementa-
tion, each state in the level 2 flowcharts corresponds to PLA controller. Figure 17 is a block diagram of a simple
one microword. Thus, each state in the level 2 flowcharts programmed logic array controller. Note the strong simi-
maps to one word in the micro control store. The fewer larity between the PLA controller in Figure 17 and the mi-
microwords we have, the smaller the micro control store croprogrammed controller in Figure 15. I consider PLA
will be. controllers to be a variety of microprogrammed con-
To program the control store we must transform the troller. If the control store address logic and the micro
flowcharts into control store bit patterns. control store are implemented as an AND-OR PLA, the
address logic would be the AND array and the micro con-
* The state ID becomes the location of the microword trol store would be the OR array.
in the micro control store. Another way to see the similarity between a micro-
* The next state becomes the micro address select (TY) coded implementation and the PLA implementation is to
and next address (NA). consider the micro control store as an orderly decode of
* The tasks become bits in the control bit fields. an input address into a microword. If the control store ad-
dress logic (address decode, micro address modifier, and
These transformations can be done on a computer, but multiplexer) of Figure 15 produced the microword direct-

Figure 15. Microprogrammed controller block diagram.

December 1981 99
 ly (instead of an address for the micro control store); it charts of Figure 14, the equation for the EDB to DIN
would behave exactly like a PLA. transfer would be
The flowcharts are used in the same way except now
you may be able to combine like states in the flowcharts EDIN = ABDMI + ABDM4 + ADRMI + POPRI
not at the ends of sequences (provided the states can be
made to lie logically next to each other for the AND
EDIN is the name given to the control point (gate) con-
decoder). Program the PLA OR array using the same
flowchart transformations as for the microprogrammed trolling the transfer of EDB to DIN. The real equation for
the transfer would be much larger if all the flowchart se-
controller. The PLA OR array contains the same bit pat-
terns as the control store for the microprogrammed con- quences were available, but the method is the same.
If I write the equations for unique states instead of in-
troller. Unused control store locations will be left out of dividual tasks, I end up with the OR array from the PLA
the corresponding PLA. A further reduction in controller controller. (Lines duplicated in the OR array will not be
size may be possible using methods for splitting or folding
a PLA. I will not discuss these; they don't relate directly duplicated here, but the state controller might be bigger.)
to the use of the flowcharts. This is because PLA design fixes the decode method for
all terms (a two-level NAND NOR or a three-level AND
OR AND, for example) but combinational design allows
Combinational controller. There are many ways to the implementation of terms to vary individually. I could
design a combinational controller (also called a combina- write equations for groups of lines or group subexpres-
torial or random logic controller). I will describe one. sions of the equations to reduce the logic. The flexibil-
First, design a state machine to duplicate the state transi- ity of this method is probably the source of some of the
tions in the flowcharts. The flowcharts contain a com- trouble it causes.
plete state diagram. Methods for converting state dia-
grams to state machines aie known and I will not discuss
them. Next, make as many copies of the flowcharts as
there are different tasks in the flowchart sequences (each
line in a state box is one task). Each copy will be assigned
to a different task. On the copy, mark all occurrences of
the assigned task, then write an equation for the task
using state IDs.
As an example, take the transfer of EDB to DIN in
Figure 14. Assign this task to one copy of the flowcharts
by highlighting all occurrences of the EDB to DIN trans-
fer. Write the equation for the EDB to DIN transfer. If I
chose to implement the controller from the level 2 flow-

Figure 16. Control store microword format.

100 COMPUTER
Why it works cal judgments you are faced with every step of the way.
"You mean success with the flowchart method can de-
The flowchart method lets you use your natural human pend on a bunch of mysterious 'technical judgments'?"
skill at pattern recognition by showing you whole instruc- you ask.
tion flows and groups of instruction flows together on a You bet . . . in the sense that the more proficient you
single page. With this method, you literally see the struc- are as an engineer the greater insight you have into the
ture of the design evolve from a rough proposal to a com- organized picture the flowchart method presents. (To ful-
plete design. You never have a limited set of tasks or se- ly automate or even to express fully that part of engi-
quence of states whose order is fixed as the result of im- neering design is the domain of an artificial intelligence
posing some form of preconceived block diagram of the project.)
controller on the design. Rather, you start with a block I've asked many chip designers, "How did you get
diagram of an execution unit and simply begin flowchart- from the English to the logic design?" To some, the odd-
ing the seqyence of states for each machine operation. By ness of my query was that I seemed to be asking how
using the method discussed, you derive the detailed level 2 thinking works. But I wasn't asking that. I was asking
flowcharts for the controller. what the designers did. Among chip designers it takes
Because these flowchart sequences are unhampered several minutes to explain what I'm talking about because
by independent notions of how control signals and data this level of chip design is rarely discussed. (It actually
"should" flow, the controller design can emerge in a way takes less time among non chip designers because they
precisely suited to the operation of this machine. Whether don't know that.) Until recently, we engineers haven't
it does emerge depends on how well you make the techni- had to attempt anything complicated! That sounds ludi-

Figure 17. PLA controller block diagram.

December 1981 101
 crous but it is really true at the level of the initial specifica- just a portion of a page interferes directly with the method
tion. We design complicated circuits, but what the chip and isn't as good as pencil anid paper.
does as a whole is describable in a sentence or two. We Flowcharting is an iterative procedure and it uses feed-
don't even come close to the titanic complexities of a back from a register-transfer simulator (or breadboard)
large operating system or data base management sys- and a circuit simulator. (A register-transfer simulator ac-
tem-complexities which programmers routinely face. cepts the MIN's instructions, assumes the MIN's execu-
tion unit, substitutes flowchart sequences for MIN in-
structions, and pretends to do the tasks in each state.) You
compare what your flowchart sequences do with what the
I've asked many chip designers, user's manual says the instruction should do. The result:
"How did you get from the English to the you correct errors and add successive detail to the
logic design?" To some, I seemed to be flowcharts. If you didn't correctly update the stack
pointer to point to the next empty location, a register-
asking how thinking works. transfer simulator will quickly point to the problem.
Even if an instruction appears to work, a register-transfer
simulator finds subtle bugs underlying context-depen-
dent errors.
The flowchart method is not a way to think. It is a way
to write down the design so that you can see it in an
organized way. The value of the method is that in orga- The flowchart method is a straightforward way to
nizing the steps you encounter new insights. You see a new derive the design of a processor. The level I flowcharts
pattern in the logic or, you notice you are having difficul- distinguish two types of activities, called housekeeping
ty. There is an immediate answer to this difficulty. The tasks and operation tasks, so we can concentrate on find-
reason may be more mechanical than logical, but that's ing the sequence of operation tasks which best imple-
ok. Note it. Then ask: why does this condition exist? ments the instruction. The subsequent merge of house-
Within three or four whys of where you encountered diffi- keeping tasks with operation tasks produces level 2 flow-
culties you will learn something completely new about the charts. Weaknesses in the execution unit surface. The way
design. It will be so new that it will make you restructure the information is organized lets you see how to reduce
that part of the design (still following flowchart method the number of states (even for a large number of states).
rubrics) so you avoid the original difficulty. You implement the processor from level 2 flowcharts.
I think much information is lost with early functional The flowchart method is a technology-conscious method.
partitioning, because structures are too simple or are in- Flowcharts are input to whichever implementation meth-
appropriate. This leads to pieces of the final implementa- od you choose (microprogrammed, PLA, or combina-
tion actually fighting each other and having to compen- tional). The method works for complicated processors
sate for each other's shortcomings. too. c
The flowchart method requires you to confer with the
circuit designers. You discuss functional assumptions
with the circuit designers. For example, you assume the
ability to substitute the first state of an interrupt sequence
for the normal next state selection. Or you ask for certain
features in a branch control unit. The circuit designers tell
you about costs and suggest alternatives. They describe
the constraints imposed by the technology. If you ask for
a programmable branch control unit, the circuit designers
may tell you it will be slow. They suggest a fixed branch
unit with a selection of two or three outputs for each input
condition. This is how technology affects the design.
The phenomenon, as I have described it, drives the
method. This makes the flowchart method a procedure
and not just a notation. You see, at each step of the way,
you are merely REACTING to what is before you in the
flowcharts . . . in pictures, not equations. Reacting, not Nick Tredennick is an occupant of IBM's
IMPOSING, not trying to constantly map onto some T.J. Watson Research Center in Yorktown
fixed set of assumptions (like a block diagram or Heights, N.Y. He has the usual degrees
microcode instruction set) about how the control flow from a couple of universities (PhD,
works. All the while, the design is before you, and University of Texas; MSEE and BSEE,
Texas Tech University) and belongs to the
manageable pieces can be taken in at a glance, at a level of customary societies and organizations
detail which I feel is right. The notation is so simple and (IEEE, ACM, Sigma Xi, Phi Kappa Phi,
natural that it never seems to be between you and what it Tau Beta Pi, and Eta Kappa Nu). His in-
represents. terest is microprocessor controller design.
He has some patents (Motorola 68000 con-
Any design tool, therefore, that changes the presenta- troller) and publications and claims an
tion format or limits what you can see of the flowcharts to average number of jobs for experience.

102 COMPUTER