$D.var pageno=1
$D.var Pic=0
$D.var NewChap,YTrap,PicH,TexH
$D.var(80) ChapTitle=''
$D.var(80) PicTitle=''

$D.format OddEven
=$y0.05"
=$Q(pageno&1) $x0.6" $10[$ChapTitle] $x2" $list12[$v(pageno)]$x>7.7"
=$Q(pageno&1) $O(0.6",0.4",7.4",10.5")[]
=$Q(1-pageno&1) $X0.2"$list12[$v(pageno)]$x1"
=$Q(1-pageno&1) $10[Microprogramming Exercise]$x>7.3"
=$Q(1-pageno&1) $O(0.2",0.4",7.2",10.5")[]
=$Q(1-pageno&1)$X0.2" $Y0.20" $G i3e7.1"
=$Q(pageno&1) $X0.6" $Y0.20" $G i3e7.1"
=$pageno=pageno+1
=$C
=$OddEven

$D.format dualcol
=$TexH=10.5"
=$Q(NewChap) $b1 $u(0.02",0.08")$17[$ChapTitle $ $ ] $NewChap=0 $TexH=TexH-1"
=$O(0   ,10.5"-TexH,3.4",TexH)[]
=$Q(Pic) $X0 $Y(10.5"-TexH+YTrap+0.1") $G i4e7.1"s(PicH)w7.1"n(PicH)
=$Q(Pic) $Y(10.5"-TexH+YTrap+PicH-0.1") $10[$PicTitle] $b^0
=$Q(Pic) $O(3.7",10.5"-TexH,3.4",Ytrap)[]
=$Q(Pic) $O(0,10.5"-TexH+Ytrap+PicH+0.2",3.4",TexH-Ytrap-PicH-0.2")[]
=$Q(Pic) $O(3.7",10.5"-TexH+Ytrap+PicH+0.2",3.4",TexH-Ytrap+PicH-0.2")[]
=$Q(1-Pic) $O(3.7",10.5"-TexH,3.4",TexH)[]
=$Pic=0
=$C
=$dualcol

$D pages
=$OddEven
=$dualcol

$D picture(title,height)
=$Ytrap=Y $Pic=1 $PicTitle='$title' $PicH=$height $C
$D chapter(title)
=$NewChap=1 $ChapTitle='$title' $C.OddEven
$D section(title)
=$b2,1" $14$u[$title] $b0.5
$D item='$k183 $x*+0.1"'

$J1 $Times12
$T=0.25",0.5",0.75",1",1.25",1.5",1.75",2",2.5",3",3.5",4",4.5",5",5.3"
$pageno=0

$pages
$chapter'Introduction'
$p0
The purpose of this exercise is to give you an opportunity of doing some more
experiments in the area covered by the lecture course Computer Structures I.
Hardware Laboratory covered the subjects related to the design of
digital circuits. Here we will concentrate on the area starting immediately
below machine language programming.
$p0.5
The task will be to write a microprogram that will 
run on a specialised graphics hardware (microprogramming level) and will
interpret a simple graphics protocol (machine language level)
$b0.5 $picture('System configuration',4.35")
The microcode
is almost completely horizontal, which gives direct control over the
separate functional blocks of the microprogrammed hardware.
$p0.5
The exercise is based on a two-processor configuration of the APM,
where a dedicated, microprogrammed graphics
processor performs specialised tasks on behalf of the user processor.
The configuration of the system is shown on the illustration below.
$section'What is to be done'
The minimum system which you
should design, implement and demonstrate is the one in which the user
processor can display and manipulate multiple windows with single-font 
text in them. This involves the specification of the protocol to be
used between the processors and subsequent implementation of subsystems
on both sides: the interpreting microcode and the user support software.
$p0.5
The following chapter describes an example protocol with applications
and some of its technical details. If you do not feel like designing
your own, choose the necessary subset of constructs from there.
Remember that the main target of the exercise is writing working
microcode and not designing graphics protocols.
$p0.5
The next chapter contains the description of the hardware to be used.
Programming details of the devices should be consulted with
the AMD Bipolar Microprocessor Logic and Interface Data Book, copies
of which can be found in the Hardware Laboratory on the sixth floor.
$section'Simulation'
As there may be some difficulties with providing more than one physical kit,
most of the microcode development should be done using a simulator, which
can be run on any APM in the Machine Halls, and which should become
available during the first week of the term.
$section'Submission'
$p0.5 You are encouraged to work in pairs, preferably the same ones as
in the Laboratory. Reports however have to be submitted individually.
$p0.5
This is to consist of the following:
$b1
$item[Demonstration of the working system in week $ $ $ $ $ $ of the term
]
$b0.5
$item[Listing of well commented source of your microcode
]
$b0.5
$item[Detailed description of how your microcode works and how to run the
demonstration.
]
$b0.5
$item[Description of the protocol which you have implemented and that of the
supporting system.
]
$b5
Remember to permit all the necessary files! $b^5
$U(0.03",0.1")[Deadline: 10:00, Friday, 30 May 1985] $b^0
$chapter'Graphics Interpreter: General Introduction'
$p0
This chapter describes a simple structured interface
between the applications programs, system utilities and user interface
modules on one side and the graphics support component of the system
on the other. The interface fits easily into a 
variety of applications through supporting structured hierarchical dependencies
of objects both between and within the applications. 
It provides flexible workspaces for the
individual applications while presenting a manageable and uniform
front to the graphics support subsystem. 
$p0.5
The interface is a directed graph, residing in the main system memory
where client processes in the system can manipulate their own allocated
sections on one side and a separate evaluation process caters
for the creation of the resulting images on the other as shown in a
paraphrase of a windowing system below. 
$b0.5 $picture('Windows',2.6")
$p0 The evaluation process
can be viewed as a function taking the graph as an argument and producing
the image as a value with the "propagation time" through the function
dependent on the performance of the graphics subsystem. 
$p0.5
The top part of the graph is usually under the supervision of the system window
manager, while its exit edges provide linkage to applications subgraphs
running within their allocated subwindows. Such hierarchy may reoccur 
recursively
where an application may have its own subwindow manager maintaining its
menu, workspace and other areas of activity.
$p0.5
The image is computed through a depth-first scan of the descriptor structure,
where for each of the nodes, its local evaluation environment is saved,
prior to following any of the downwards edges, and subsequently restored 
on return. The ordering of the exit edges defines the eventual overlap of
the graphical objects created by their execution.
Evaluation is terminated after the execution along the last vertical
edge of the node, at which it was invoked, thus allowing nested invokation
of selected substructures.
$p0.5
The speed of generating new images is strongly
dependent on the complexity of the graph and
on whether the evaluation process has to share the processor with other
processes, or it can have its own customised evaluation engine.
Depending on certain properties of the graph, like being acyclic or even
a tree, various optimisation techniques allow for only parts of the
graph to be scanned, still yielding a valid picture.
$Section'Graph construction'
The graph is constructed out of fixed-format nodes with two exit edges:
a $I[vertical] and a $I[horizontal] one. The vertical
edge is used to represent image hierarchy and the horizontal edge
supports linkage of multiple image components at the same level of
hierarchy.
$p0.5 Leaf nodes in such a directed binary graph i.e. those with no vertical 
exit edges are generally
responsible for the final drawing operations, and they can invoke 
operations like filling a polygon, drawing a stright line, drawing a
string of characters etc. These are executed with the necessary current
environmental attributes like: colour, font, scaling, clip boundaries etc. 
Some of the drawing
operations can have impact on the environment, like deposition of
character strings moves the working coordinates along the string baseline.
$b0.5 $picture('Format of the node',2.6")
$p0
Non-leaf nodes are generally responsible for the composition of the picture
out of subordinate ones as well as for the necessary modifications of the
environment, like coordinate manipulations, colour and font selection etc.
Some of these operations, like moving or scaling are cummulative
along the vertical paths in the graph; others like font or colour selection
are nested.
There are also some general control nodes, which allow the user
to exercise control over the evaluation process.
$p0.5
Each binary node consists of 11 consecutive half-words, where
the first two bytes contain the instruction code and the execution flags
of the node. They are followed by a long-word of argument field, and
then two long-words, where on exit, the evaluation process deposits the 
relative
dimensions of the bounding box for the image subordinate to the node.
These dimensions are relative to the environmental working
$I[(workX,workY)] coordinates on the entry to the node. 
$p0.5
The argument field can contain
a 32-bit pointer, two 16-bit geometrical or indexing
arguments, or
for some single-argument operations only the first half-word is taken into
account.
$p0.5
The last two long-words contain downwards and rightwards pointers of
the exit edges, with execution flags $I[Down] and $I[Right] indicating their
validity. Flag $I[Pointer] when 1 represents indirection in fetching
of arguments.
$p0.5
In all following examples, nodes will be denoted with their associated opcodes
and those of the flags, which are set to 1. Values of 1
for the
$I[Down] and $I[Right] flags are indicated by the presence of the 
corresponding exit edges.
$section'Example: VLSI editor'
$p0.5
This section provides a short presentation of
an editor for structured design of VLSI leaf cells which has been created
around the experimental graphics interface presented in this chapter. 
The editor is a component of a major design system which
comprises a high level composition language, on-line geometric design rule
checking and automatic stretching and compaction of composition cells.
The section outlines some of the capabilities of the editor, with particular 
emphasis on the ease with
which one can produce a leaf cell cicuit design when tools such as the
appropriate representing data structure and its efficient intepreter are 
available.
$b1
$h[Editor design environment]
$p0.5
There are certain features of a circuit design environment which are fundamental
to the user. It must exhibit: fast interactive response, the ability to 
view the design at arbitrary geometric scales
together with a clean and comprehensive user interface.
The designer should feel intimately coupled to his design environment, with
both control and the ability to perform structured operations such as
viewing, panning and zooming at the touch of a button.
$p0.5
The editor is menu driven, and uses a mouse as the manipulating device. 
The mouse is used for pointing and editing individual 
objects on the screen, or as an area selector where whole groups of
objects are operated upon. The menu consists of representations of
components the designer can paint with like wires, transistors, contacts etc.
together with a set of high level functions: view, move, clone, input, 
output etc.
which he can use to operate upon and compose design layouts. 
$p1
While operating within its own allocated window, the editor is a multiwindow
system in itself, with one menu and potentially more than one workspace
subwindow.
$b0.5 $picture('Editor: Simple VLSI structures',2.7")
$h[Simple VLSI building blocks]
$p0.5
The basic VLSI building blocks are wires, transistors and contacts. 
Using these primitive components it is possible to construct very large scale
circuit designs.
$p0.5
Wires are conventionally denoted as occupying certain "layers" on the silicon.
For a simple example of NMOS technology,
these layers are  polysilicon, diffusion and metal. 
Simple VLSI constructs, like transistors or contacts
are overlaps of the approriately sized and positioned "technological"
boxes. Using these objects more complex units such as
the "RAM cell" presented in the illustration can be constructed.
$p0.5
The fabrication process, however, still deals with a "flattened" design, 
and during fabrication objects such as contacts and transistors lose their
hierarchical structure and become merely "etchings" carved out of the
individual layers on the silicon wafer.
$p0.5
The colours selected are conventional circuit design, and the video planes
correspond directly with mask layers for
separate technological phases of the circuit production process.
$p0.5
Node $h[Move](X,Y) modifies current environmental working coordinates
by (X,Y), prior to passing them down the vertical edge. Nodes $h[DrawBox](X,Y)
and $h[DrawLine](X,Y) draw a box and a line of size (X,Y) respectively,
starting from
their current working coordinates. Line drawing node has also a 
$h[Move](X,Y)
node effect on the environment, allowing sequences of lines to be drawn,
through vertical composition of such nodes.
Node $h[SetInk](newcolour) defines the drawing colour for its subordinate
subgraph and node $h[SetPMask](enable mask) defines video planes with
permitted write operations.
Node $h[PutString](stringpointer) draws in current font and colour a 
string of characters starting from the current (workX,workY) to the right.
$p0.5
The transistor above has been built out of appropriately positioned
($h[Move]) boxes ($h[DrawBox]) of diffusion ($h[Plane](diffusion))
and polysilicon ($h[Plane](polysilicon)).
$b1
$h[Modularity and "Recipies" for cells]
$p0.5
The editor allows the user to create 
generalised descriptions of component structures
where subsequently they can be 
invoked with individual parameters for each instantiation.
$p0.5
The building blocks in circuit design are described both in terms of their
component structure and their geometric attributes, like size, shape and
orientation. For a
transistor we may have either an "etpx" (polysilicon in the x-direction)
or an "etpy" (polysilicon in the y-direction). Both these objects
share the same component structure but possess unique positioning parameters. 
We may think of an analogy
of a "recipe" which describes how to construct an object
and a list of "ingredients" which uniquely define each object type. By
partitioning the component description in this fashion it is possible to
perform geometric transformations such as scaling and rotation without
having to generate an entire component data structure each time. One merely
has to provide a new list of ingredients.
$p0.5
Nodes in the structure can obtain any of their two 16-bit arguments
through indexing into the current environmental argument array.
Execution flags $h[indexA] and $h[indexB] indicate whether
the first and the second half-word of the argument (possibly obtained
indirectly for $h[Pointer]=1) are the final arguments or indexes into
such array.
$b0.5 $picture('Variations of a transistor "recipe"',2.7")
$p0
The array itself is declared by a node
$h[Setarguments](array pointer) where the new array pointer replaces
the one inherited from above for the subordinate subgraph of the declaration
node.
The construct provides the subgraphs which can be used like drawing
procedures in several places in the graph.
$p0.5
In the example, the fixed-dimensions description of a transistor
from the previous page has been replaced by a "recipe" for a simple transistor,
where explicit dimensions have been replaced by indexes into a fixed-format
array. Various effects like rotation and size variations can be obtained
through appropriate swopping or variation of values in the individual
declarations of argument arrays prior to "calling" the transistor drawing graph.
$b1 $h[Replicated composition]
$p0.5
Examining a very large scale integrated circuit layout one observes
that it consists of clearly distinguishable cells (memory cell, 
ALU cell, data path cell etc.. ). There is also a certain 
regularity of pattern within each cell itself. This regularity is created
by a repetition of basic cell subsystems, a prime example being the generation 
of a memory cell. Here the designer defines a basic single bit memory 
subsystem (seen here left top in the background)
and subsequently creates a complete memory cell by abutted replication
of the subsystem cell in both X and Y directions (top subwindow).
A programming analogy is the 2-dimensional array and the algorithm
analogous to nested iteration cycles.
Such nested, 2-dimensional composition will usually incorporate circuitry
required at the edges of the array. In the example
the ram interface cell has been designed and deposited on the right after each
iteration in the X direction (bottom subwindow). 
$p0.5
This ability to iterate in the X and Y direction is a very important tool
for the circuit designer. It facilitates design creation and alleviates the
task of verifying a complete circuit cell, since if the subsystem cell is
geometrically correct and the abutting interface is also correct then the
entire cell is geometrically correct. 
$p0.5
Prior to descending along the vertical edge (for $h[Down]=1) the evaluation
process checks whether the $h[iteration] index in the current environment
is greater than zero and if not, the downward evaluation is not entered.
There are two nodes that control the value of the $h[iteration] index in
the environment. 
$h[Setiteration](number) provides nested presetting of the index
and $h[Deciteration] decrements it along the vertical edges.
$p0.5
In order to perform an iterated invokation of a subgraph (here 
of a subgraph drawing a RAM cell) we have to set the iteration index
above the graph and then create an iteration loop with decrementation of
the index in it. In the example, a $h[Move] node is placed immediately
to the right of the cell, allowing the cells to be placed side by side.
It is followed downwards by a $h[Deciteration] node, pointing in turn
down back at the memory cell.
This whole construct is then connected to the interface cell on the right
and embedded in the Y iteration construct above it.
$b1
$h[Virtual coordinates and design inspection]
$p0.5
Having adopted the structured design approach the circuit designer is free
to concentrate on individual leaf cell creation. These leaf cells can
be quite large and complicated and in most cases extend
beyond the domain of the visible design workspace. By providing functions
such as panning and viewing the editor offers a much larger virtual design
workspace and uses the graphics screen only as a viewport into the design. 
$b0.5 $picture('Iteration and Virtual Coordinates',5.1")
$p0
The designer may then, during an editing session, view and edit sections of 
the layout at arbitrary design scales. 
Although each of the design subwindows can show sections of the same design 
in different scales, the whole of the design is represented and manipulated
in its virtual coordinates, here being equal to 1/8 lambda 
(a conventional design dimension unit where its mapping onto real dimensions
reflects the resolution of production technology).
$p0.5
In the example the background window shows a simple 8x4 memory array
reduced 4x, the next window with 2x reduction allows inspection
of RAM cells abbutment and the top window, with 1.5x enlargement shows
the alignment details on the right edge of the array.
$p0.5
A $h[Dscale](factorX,factorY) declares the environmental deferred scaling 
factors in X and Y for the subordinate subgraph. The operation is not
cummulative and there should be no more than one such node in each vertical
path in the graph.
The factors provide independent scaling in both axes, and do not take
effect immediately, allowing for unscaled composition of objects in their
virtual coordinates. They are applied only by the final drawing nodes
prior to creating them on the screen. Within these nodes clipping
is performed still in virtual coordinates.
For that reason the only immediate effect of 
declaring a deferred scaling, remapping of the clipping
environment from above into the virtual coodinates below.
$p0.5
An inspection viewport into a design is created by vertically composed
declarations of its position ($h[Move]), size ($h[SetClip]) and viewing
scale ($h[Dscale]). The node $h[Move](-vX,-vY) below expresses in
designs virtual coordinates the positioning of the left bottom corner
of the viewport. All the viewports share the same global design structure.
Such "geometrical" viewing should be distinguished from "structured"
viewing, where the viewport can point at the selected subgraphs within the
design (the oblong window on previous page was in fact drawn by pointing
just below Y iteration loop in the global design of RAM array).
$p0.5
It is also worth noticing that the presented order of $h[SetClip] and
$h[Dscale] nodes fixes the physical size of the viewport, decreasing
the amount of details as scaling factors increase.
Swopping of these two nodes would result in a constant amount of detail
and a growing viewport as the clipping would now be defined in the design's
virtual coordinates.
$b0.5 $picture('Bounding boxes and cursors',2.7")
$h[Bounding boxes, cursors and pointers]
$p0.5
One of the major components of the screen in an interactive graphics
system is the representation of a pointing device and cursor operations,
marking the areas occupied by the selected objects.
$p0.5
In the example the pointer is implemented as a $h[PutTemplate](pointer)
drawing node, which takes a bit-map representation of a shape (here a hand)
in the memory and deposits it, with current colour, at the position 
indicated by the current working coordinates.
Normally, it will be placed under 
$h[SetInk](pointercolour) and
$h[Move](mouseX,mouseY) nodes. Such constructs are usually placed as
the last horizontal link within the window structure. It may appear on
the very top of the graph, providing general pointing capability
on the screen. Others may be linked within the applications windows,
with appropriately zeroed and clipped mouse coordinates supplied as
arguments.
$p0.5
A $h[Cursor](cursorpointer) node provides a nested declaration of
a graph to be used for drawing cursors. Cursorpointer points at the
top of the graph, which assumes a predeclared 4-element argument array.
In most cases it will be the bounding box information field of a selected node.
$p0.5
The evaluation process upon return to the node from the downwards evaluation
updates the node bounding box information, being the cummulative effect of
executing the node and the subordinate graph.
This information is stored as dimensions relative to the
working coordinates upon entry to the node.
Having updated the bounding box information and
upon seeing execution flag $h[Cursor] set to 1 the evaluation process
calls the current cursor drawing graph with the environment in which the
current argument array had been replaced by the node bounding box
definition field.
$p0.5
The construct allows to create individual cursors for various applications
with manipulation of flags being the only cost of invoking them.
Text strings can be underlined on their baseline by a small downwards 
$h[Move](0,-1), vertically composed with $h[SetInk](cursorcolour)
and two horizontally linked
$h[DrawLine,idxA](0,0) and $h[DrawLine,idxA](2,0) nodes.
To underline a string just below its lowest descendent it is enough
to add a vertically composed $h[Move,idxB](0,1).
Similarly, full background and framing cursors can be defined.
$p0.5
Bounding box information is also used by the VLSI editor for joining of
cells, where the $h[Move] positioning individual RAM cells
picks up its arguments from the top node of the cell.
Similarly, the positioning of the interface cells at the end of
X iteration loop obtains its Y argument from the node on top of the loop.
$p0.5
Variation in fonts is achieved through a nested $h[font](fontpointer)
node, which declares a pointer to an array of 256 short integers 
being offsets to templates of individual characters within the font.
$b1
$h[Nested windows and structured addressing of objects]
$p0.5
All of the examples have been developed within nested windowing environments.
$p0.5
An example general construct of a window can be defined by specifying its
relative position ($h[Move](Xbase,Ybase)),
its size ($h[SetClip](Xsize,Ysize)) and background colour ($h[SetInk](background)).
The construct can be nested, where subwindows can be used to host
different areas of activity maintained by the application process within the
window.
$b0.5 $picture('Nested windows',2.7")
$p0
The portrait of a dog in window 1 was brought in as a $h[PutTemplate] in yellow.
Window 2 contains two subwindows 2A and 2B, and the greyscale picture
in window 3 has been brought in by a $h[Pixels](pointer) node from
the main system memory. 
$p0.5
Live animation effects of manipulating the windows can be easily obtained
by appropriate modifications of arguments in the window data structure.
$p0.5
The task of identfying an object addressed by the mouse coordinates
can be split into two basic sub-tasks.
The first one is the identification of the
nodes in the graph with bounding boxes covering these coordinates.
It involves a fairly simple top-down scan of the graph, where its vertical
edges are followed only for the nodes containing the pointer address.
Such scanning creates vertical paths in the graph, where more than one
distinct path will be created for the pointer contained in more than one
hierarchically unrelated nodes. 
Example positioning of the pointer creates only one path, which is depicted
in the example by invoking a framing cursor for all the nodes containing it.
Positioning of the pointer
on "W" in window 2B would create 3 such paths.
$p0.5
The second task is the identification of a node within the paths,
where the active window identity, and the application running
within it perform the final selection.
$b1
$h[Dual buffering]
$p0.5
The system assumes the use of a dual buffering technique for most
of the applications, where a new image is being created outside the currently
visible area of the framestore, and upon completion is swopped onto the
screen during the nearest vertical flyback. The technique assumes 
framestore memory size to be at least twice the size of the amount
required to support one visible frame.
There are different methods of partitioning such memory: geometrically
in X or Y through framestore offset registers,
or by mapping different sets of planes into the video output.
$p0.5
In the example two 768x512 pixel buffers are fitted one above the other
in a 1024x1024 framestore.
Top $h[SetXY](baseX,baseY) node of the structure places the absolute
evaluation coordinates (workX,workY) in relative (0,0) coordinates
of one of the frames. A $h[SetClip](768,512) node below it protects
the neighbouring, displayed frame and points vertically to the image
definition graph.
Having completed evaluating the main graph, a $h[FlybackY] node
witholds the continuation to the right until the nearest frame
vertical flyback, when the $h[Pan](baseX,baseY) through
framestore offset registers puts the display area over the newly evaluated
frame. $h[SetXY] and $h[Pan] nodes indirect into a 2-element offset
definition, where location X remains at 0 and Y is alternatively swapped
between 0 and 512.
$C
$picture('Dual-buffering mechanism',5")
$E*
