§1  GB GATES ELTE  INTRODUCTION 1

Important: Before reading GB GATES ELTE, please read or at least skim the program for GB GRAPH.

1. Introduction. This GraphBase module provides eleven external subroutines:

risc elte, a routine that creates a directed acyclic graph based on the logic of a simple

RISC computer; prod , a routine that creates a directed acyclic graph based on the logic of parallel

multiplication circuits; print gates , a routine that outputs a symbolic representation of such directed acyclic

graphs; gate eval , a routine that evaluates such directed acyclic graphs by assigning boolean

values to each gate; simulate, a routine that simulate the behavior of the output of risc elte; partial gates , a routine that extracts a subgraph by assigning random values to some

of the input gates; run risc elte, a routine that can be used to play with the output of risc elte; risc elte reset , a routine that can be used to reset the output of risc elte; min risc elte, a routine that can be used to play with the output of risc elte with von

Neumann memory; small risc elte, a routine that can be used to play with the output of risc elte with

Harward memory; large risc elte, a routine that can be used to play with the output of risc elte with

paged memory.

Examples of the use of these routines can be found in the demo programs TAKE RISC ELTE, TEST RISC ELTE,

MINIMAL RISC ELTE, SMALL RISC ELTE and LARGE RISC ELTE.

⟨ 1 ⟩ ≡ #define print gates p gates /∗ abbreviation for Procrustean linkers ∗/

extern Graph ∗risc elte( ); /∗ make a network for a microprocessor ∗/ extern Graph ∗prod ( ); /∗ make a network for high-speed multiplication ∗/ extern void print gates ( ); /∗ write a network to standard output file ∗/ extern long gate eval ( ); /∗ evaluate a network ∗/ extern Graph ∗partial gates ( ); /∗ reduce network size ∗/ extern long simulate( ); /∗ simulate the microprocessor in software ∗/ extern long run risc elte( ); /∗ run the microprocessor ∗/ extern long risc elte reset ( ); /∗ reset the microprocessor ∗/ extern long min risc elte( ); /∗ run the microprocessor with von Neumann memory ∗/ extern long small risc elte( ); /∗ run the microprocessor with Harward memory ∗/ extern long large risc elte( ); /∗ run the microprocessor with paged memory ∗/ extern unsigned long risc state[ ]; /∗ the state of the microprocessor risc elte ∗/

See also sections 2, 84, and 99.

2  INTRODUCTION  GB GATES ELTE §2

2. The directed acyclic graphs produced by GB GATES ELTE are GraphBase graphs with special conventions related to logical networks. Each vertex represents a gate of a network, and utility field val is a boolean value associated with that gate. Utility field typ is an ASCII code that tells what kind of gate is present:

denotes an input gate, whose value is specified externally.

denotes an gate, whose value is the logical AND of two or more previous gates (namely, 1 if all

those gates are 1, otherwise 0). denotes an gate, whose value is the logical OR of two or more previous gates (namely, 0 if all those

gates are 0, otherwise 1). denotes an gate, whose value is the logical EXCLUSIVE-OR of two or more previous gates (namely,

their sum modulo 2). denotes an inverter, whose value is the logical complement of the value of a single previous gate. denotes a latch, whose value depends on past history; it is the value that was assigned to a subsequent

gate when the network was most recently evaluated. Utility field alt points to that subsequent gate. Latches can be used to include “state” information in a circuit; for example, they correspond to registers of the RISC machine constructed by risc. The prod procedure does not use latches.

The vertices of the directed acyclic graph appear in a special “topological” order convenient for evaluation: All the input gates come first, followed by all the latches; then come the other types of gates, whose values are computed from their predecessors. The arcs of the graph run from each gate to its arguments, and all arguments to a gate precede that gate.

If g points to such a graph of gates, the utility field g outs points to a list of Arc records, denoting “outputs” that might be used in certain applications. For example, the outputs of the graphs created by prod correspond to the bits of the product of the numbers represented in the input gates.

A special convention is used so that the routines will support partial evaluation: The tip fields in the output list either point to a vertex or hold one of the constant values 0 or 1 when regarded as an unsigned long integer. #define val x.I /∗ the field containing a boolean value ∗/ #define typ y.I /∗ the field containing the gate type ∗/ #define alt z.V /∗ the field pointing to another related gate ∗/ #define outs zz .A /∗ the field pointing to the list of output gates ∗/ #define is boolean(v) ((unsigned long)(v) ≤ 1) /∗ is a tip field constant? ∗/ #define the boolean(v) ((long)(v)) /∗ if so, this is its value ∗/ #define tip value(v) (is boolean(v) ? the boolean(v) : (v) val )

#define
#define
#define
#define

⟨ 1 ⟩ +≡ #define val x.I /∗ the definitions are repeated in the header file ∗/ #define typ y.I #define alt z.V #define outs zz .A #define is boolean(v) ((unsigned long)(v) ≤ 1) #define the boolean(v) ((long)(v)) #define tip value(v) (is boolean(v) ? the boolean(v) : (v) val ) #define #define #define #define

⟨ Type declarations 83 ⟩ 3. Let’s begin with the gate eval procedure, because it is quite simple and because it illustrates the conventions just explained. Given a gate graph g and optional pointers in vec and out vec, the procedure gate eval will assign values to each gate of g. If in vec is non-null, it should point to a string of characters, each or , that will be assigned to the first gates of the network, in order; otherwise gate eval assumes that all input gates have already received appropriate values and it will not change them. New values are computed for each gate after the bits of in vec have been consumed.

If out vec is non-null, it should point to a memory area capable of receiving m + 1 characters, where m is the number of outputs of g; a string containing the respective output values will be deposited there.

If gate eval encounters an unknown gate type, it terminates execution prematurely and returns the value −1. Otherwise it returns 0. ⟨ The gate eval routine 3 ⟩ ≡

long gate eval (g, in vec, out vec)

Graph ∗g; /∗ graph with gates as vertices ∗/

char ∗in vec; /∗ string for input values, or Λ ∗/

char ∗out vec; /∗ string for output values, or Λ ∗/ { register Vertex ∗v; /∗ the current vertex of interest ∗/

register Arc ∗a; /∗ the current arc of interest ∗/ register char t; /∗ boolean value being computed ∗/ if (¬g) return −2; /∗ no graph supplied! ∗/ v = g vertices ; if (in vec) ⟨ Read a sequence of input values from in vec 4 ⟩; for ( ; v < g vertices + g n; v^{++}) {

switch (v typ) { /∗ branch on type of gate ∗/

case : continue; /∗ this input gate’s value should be externally set ∗/ case : t = v alt val ; break;

⟨ Compute the value t of a classical logic gate 6 ⟩; default: return −1; /∗ unknown gate type! ∗/ } v val = t; /∗ assign the computed value ∗/

} if (out vec) ⟨ Store the sequence of output values in out vec 5 ⟩; return 0;

}

This code is used in section 7.

4. ⟨ Read a sequence of input values from in vec 4 ⟩ ≡ while (∗in vec ∧ v < g vertices + g n) (v^{++}) val = ∗in vec^{++} − ;

This code is used in section 3.

5. ⟨ Store the sequence of output values in out vec 5 ⟩ ≡

{ for (a = g outs ; a; a = a next ) ∗out vec^{++} = + tip value(a tip); ∗out vec = 0; /∗ terminate the string ∗/

}

This code is used in section 3.

6. ⟨ Compute the value t of a classical logic gate 6 ⟩ ≡ case : t = 1;

for (a = v arcs ; a; a = a next ) t &= a tip val ; break;

case : t = 0; for (a = v arcs ; a; a = a next ) t |= a tip val ; break;

case : t = 0; for (a = v arcs ; a; a = a next ) t ⊕= a tip val ; break;

case : t = 1 − v arcs tip val ;

break;

This code is used in section 3.

7. Here now is an outline of the entire GB GATES ELTE module, as seen by the C compiler: #include /∗ we will use the GB FLIP routines for random numbers ∗/ #include /∗ and we will use the GB GRAPH data structures ∗/

§8  GB GATES ELTE  THE RISC ELTE NETLIST 5

⟨ Preprocessor definitions ⟩ ⟨ Type declarations 83 ⟩ ⟨ Private variables 12 ⟩ ⟨ Global variables 80 ⟩ ⟨ Internal subroutines 11 ⟩ ⟨ The gate eval routine 3 ⟩ ⟨ The print gates routine 98 ⟩ ⟨ The risc elte routine 8 ⟩ ⟨ The simulate routine 46 ⟩ ⟨ The run risc elte routine 69 ⟩ ⟨ The risc elte reset routine 81 ⟩ ⟨ The min risc elte routine 82 ⟩ ⟨ The small risc elte routine 90 ⟩ ⟨ The large risc elte routine 94 ⟩ ⟨ The prod routine 115 ⟩ ⟨ The partial gates routine 133 ⟩ 8. The RISC ELTE netlist. The subroutine call risc elte(regs ) creates a gate graph having regs registers; the value of regs must be between 2 and 16, inclusive, otherwise regs is set to 16. This gate graph describes the circuitry for a small RISC computer, defined below. The total number of gates turns out to be 2300 + 150 ∗ regs ; thus it lies between 2600 (when regs = 2) and 4700 (when regs = 16). EXCLUSIVE-OR gates are not used; the effect of xoring is obtained where needed by means of ANDs, ORs, and inverters.

If risc elte cannot do its thing, it returns Λ ( ) and sets panic code to indicate the problem. Otherwise risc elte returns a pointer to the graph. #define panic(c) { panic code = c; gb trouble code = 0; return Λ; } ⟨ The risc elte routine 8 ⟩ ≡

Graph ∗risc elte(regs )

unsigned long regs ; /∗ number of registers supported ∗/ { ⟨ Local variables for risc elte 9 ⟩

⟨ Initialize new graph to an empty graph of the appropriate size 16 ⟩; ⟨ Add the RISC data to new graph 17 ⟩; if (gb trouble code) {

gb recycle(new graph);

panic(alloc fault ); /∗ oops, we ran out of memory somewhere back there ∗/ } return new graph;

}

This code is used in section 7.

9. ⟨ Local variables for risc elte 9 ⟩ ≡ Graph ∗new graph; /∗ the graph constructed by risc ∗/ register long i, j, k, r; /∗ all-purpose indices ∗/

See also sections 18, 20, 23, 30, 36, and 39. This code is used in section 8.

6  THE RISC ELTE NETLIST  GB GATES ELTE §10

10. This RISC ELTE machine works with 16-bit registers and 16-bit data words. It assumes the existence of an external memory. The circuit has 19 inputs, the last 16 of which are supposed to be set to the contents of the memory address computed on the previous cycle. Thus we can run the machine by accessing memory between calls of gate eval . The first input bit, called , is normally set to 1; if it is 0, the other inputs are effectively ignored and all registers and outputs will be cleared to 0. The second input bit is the interrupt bit ; it may cause an interrupt if this is enabled, see below. The third input bit is the page bit which is always 0 by smaller systems; it cause an interrupt anyway, even during an instruction, see below. Input bits for the memory appear in “little-endian order,” that is, least significant bit first. The circuit has 53 outputs. The first and second is the (new) value of the translation flag and the (new) value of the extra flag ; they can be ignored by small systems, see below. The third is data bit : it can be considered as an extension to the next 16 representing the 16 bits of a memory address register. (The output bits for the memory address register appear in “big-endian order,” most significant bit first.) A small von Neumann architecture can ignore and use a 64 kk word memory, other systems may use separate program and data memory (or mix the two). The remaining 34 output for write. The next output is the write bit ; if it is zero, no write data and the last 33 output is zero. Otherwise, comes the data bit belonging to the 16 bit write address and 16 bit data to write; they are also in “big-endian order”.

Words read from program memory are interpreted as instructions having the following format:

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0

The and fields specify a “source” value. If = 0, the source is , treated as a 16-bit signed number between −8 and +7 inclusive. If = 1, the source is the contents of register plus the (signed) value of . If = 2, the source is the contents of register . And if = 3, the source is the contents of the memory location whose address is the contents of register . Thus, for example, if = 3 and = 10, and if contains 17 while contains 1009, the source value will be −6 if = 0, or 17 − 6 = 11 if = 1, or 1009 if = 2, or the contents of memory location 1009 if = 3.

The field specifies the number of the destination register. This register receives a new value based on its previous value and the source value, as prescribed by the operation defined in the and fields. For example, when = 0, a general logical operation is performed, as follows: Suppose the bits of are called μ_{11}μ_{10}μ_{01}μ_{00} from left to right. Then if the kth bit of the destination register currently is equal to i and the kth bit of the source value is equal to j, the general logical operator changes the kth bit of the destination register to μ_{ij}. If the bits are, for example, 1010, the source value is simply copied to the destination register; if = 0110, an exclusive-or is done; if = 0011, the destination register is complemented and the source value is effectively ignored.

The machine contains four status bits called (sign), (nonzero), (carry), and (overflow). Every general logical operation sets equal to the sign of the new result transferred to the destination register; this is bit 15, the most significant bit. A general logical operation also sets to 1 if any of the other 15 bits are 1, to 0 if all of the other bits are 0. Thus and both become zero if and only if the new result is entirely zero. Logical operations do not change the values of and ; the latter are affected only by the arithmetic operations described below.

The status of the and bits can be tested by using the conditional load operator, = 2: This operation loads the source value into the destination register if and only if bit μ_{ij} = 1, where i and j are the current values of and , respectively. For example, if = 0011, the source value is loaded if and only if = 0, which means that the last value affecting and was greater than or equal to zero. If = 1111, loading is always done; this option provides a way to move source to destination without affecting or .

A second conditional load operator, = 3, is similar, but it is used for testing the status of and instead of and . For example, a command having = 1010, = 3, = 1, and = 1 adds the current overflow bit to the destination register. (Please take a moment to understand why this is true.)

We have now described all the operations except those that are performed when = 1. As you might expect, our machine is able to do rudimentary arithmetic. The general addition and subtraction operators belong to this final case, together with various shift operators, depending on the value of .

Eight of the = 1 operations set the destination register to a shifted version of the source value: = 0 means “shift left 1,” which is equivalent to multiplying the source by 2; = 1 means “cyclic shift left 1,” which is the same except that it also adds the previous sign bit to the result; = 2 means “shift left 4,” which is equivalent to multiplying by 16; = 3 means “cyclic shift left 4”; = 4 means “shift right 1,” which is equivalent to dividing the source by 2 and rounding down to the next lower integer if there was a remainder; = 5 means “unsigned shift right 1,” which is the same except that the most significant bit is always set to zero instead of retaining the previous sign; = 6 means “shift right 4,” which is equivalent to dividing the source by 16 and rounding down; = 7 means “unsigned shift right 4.” Each of these shift operations affects and , as in the case of logical operations. They also affect and , as follows: Shifting left sets to 1 if and only if at least one of the bits shifted off the left was nonzero, and sets to 1 if and only if the corresponding multiplication would cause overflow. Shifting right 1 sets to the value of the bit shifted out, and sets to 0; shifting right 4 sets to the value of the last bit shifted out, and sets to the logical OR of the other three lost bits. The same values of and arise from cyclic or unsigned shifts as from ordinary shifts.

When = 1 and = 8, the source value is added to the destination register. This sets , , and as you would expect; and it sets to the carry you would get if you were treating the operands as 16-bit unsigned integers. Another addition operation, having = 9, is similar, but the current value of is also added to the result; in this case, the new value of will be zero if and only if the 15 non-sign bits of the result are zero and the previous values of and were also zero. This means that you can use the first addition operation on the lower halves of a 32-bit number and the second operation on the upper halves, thereby obtaining a correct 32-bit result, with appropriate sign, nonzero, carry, and overflow bits set. Higher precision (48 bits, 64 bits, etc.) can be obtained in a similar way.

When = 1 and = 10, the source value is subtracted from the destination register. Again, , , , and are set; the value in this case represents the “borrow” bit. An auxiliary subtraction operation, having = 11, subtracts also the current value of , thereby allowing for correct 32-bit subtraction.

The operations for = 1 and = 12 is called and well-known from . Because of case = 1 seems to be not useful, this case considered = 2 but an operation is done. Matrix operations set and but does not change and .

The operations for = 1 and = 13 is the write operation and will write into memory. The content of the destination register specified by the field is written to the address which is the “source” value specified by the and fields as given the general rules with one exception: in the case = 1 the address

is the pre-decremented content of the  register, i. e., this is a  instruction. The only case when write
does not goes to data memory but to programm memory a  instruction with  = 0; this may be

useful in a debugger. Flags are not affected.

The operations for = 1 and = 14 and a final operation, called for = 1 and = 15, will be explained momentarily. They do not affect , , , or .

If the RISC ELTE is made with fewer than 16 registers, the higher-numbered ones will effectively contain zero whenever their values are fetched. But if you use them as destination registers, you will set , , , and as if actual numbers were being stored.

Register 0 is different from the other 15 registers: It is the location of the current instruction. Therefore if you change the contents of register 0, you are changing the control flow of the program. If you do not change register 0, it automatically increases by 1.

Special treatment occurs when = 3 and = 0. In such a case, the normal rules given above say that the source value should be the contents of the memory location specified by register 0. But that memory location holds the current instruction; so the machine uses the following location instead, as a 16-bit source operand. If the contents of register 0 are not changed by such a two-word instruction, register 0 will increase by 2 instead of 1.

The command moves the source value to register 0, thereby changing the flow of control. Furthermore, if ≠ 0, it also sets register to the location of the instruction following the . Assembly language programmers will recognize this as a convenient way to jump to a subroutine.

We have now discussed everything about the machine except the operations in the case = 1 and = 14. In the case = 0 a operation is done: data from the address given by (sign extended) will be loaded into the register named by . In the case = 2 a operation is done: the content of the register named by is replaced by number of one’s in the register named by . In the case = 3 data

from the address given by the register  will be loaded into the register named by  and the content
of register  is post-incremented if  ≠ ; i. e., a  instruction is done. Finally, the case = 1 is
connected to interrupts, pageing and system calls. It is called  if  ≠ 0 and  if  = 0. The

processor has two extra flags, the translate flag and the enable flag . For the normal user, both set to 1. The instruction set both to 0, and register 0 will set to 32 + 2 ∗ . Furthermore, it also sets register to the location of the instruction following the . Assembly language programmers will recognize this as a convenient way to a system call. The instruction make possible the return from system

calls: it sets register 0 to the content of register  if  ≠ 0, and to the content of the memory at address
0 if  = 0, and, finally sets flags and to 1. The case  = 0 is useful if we want to return from an
interrupt. There is one more way to set to 1: the  conditional instruction with = 3,  = 10,
= 1,  = 0 and  ≠ 0 has this side effect (but other  instructions, for example with = 3,
= 10, = 2 and  =  ≠ 0 has not). If the input  = 1 and also = 1, no new instruction is

started, but and set to 0, the content of register 0 is written to (data) memory address 0 and register 0 is set to 1. If the input = 1, it has the same effect, but instruction not finished; operating system and auxiliar hardware together may figure out where to and what to correct in register content before resume.

Auxiliary hardware may simulate auxiliary registers. For example, by a system running under Unix the second highest address of (data) memory may represent an interrupt register, and the third highest may represent an interrupt mask register. They can be read and write by the processor and by the auxiliar hardware, too. If their “and” gives a nonzero result, an is generated by the auxiliar hardware. The highest address may contain a translation register with least significant bits , and . If, for example, = 1 or = 1, then by any reading from or writing to program memory a translation is done: the most significant bits (for example, plus 3 bits) of the memory address used as a relative address to the translation table. The physical address given by the most significant 13 bits of the translation table data plus the 13 offset bits of the logical address. (If no translation, then the most significant 9 bits of the physical address are zero.) The least significant 3 bits , and of the translation table data used as protection bits. Next 10 bits of translation register can be used for other purposes, for example setting a bit may swich of a given or interval. (The translation register should be 0 by starting.) Some systems may leave out bits and double the physical address space. Of course, two word translation table entries can be used, too.

The auxiliary hardware must help for the operating system by page error for example on the following way: by page error during write from the most significant three bit , and of translation register the “previous” bit set to 1, the extra bit is set from the value of flag by the previous reading and is set to the complement of by the previous reading meaning instruction reading. By any other page error is set to 0, is set from the new value of meaning extra reading and is set to the complement of meaning instruction reading. Observe, that by any page error one of them is always set. If no page error, they are not changed. Operating system may figure out what to do; for example if p = 1 then in the case e = 0 the instruction cousing page error is on the previous address, in the the case e = 1 before it; etc. Auxiliar hardware may also save the address causing page error.

Example programs can be found in the TAKE RISC ELTE module, which includes a simple subroutine for multiplication and division, in the TEST RISC ELTE module for other tests, in the MINIMAL RISC ELTE module for a minimal von Neumann computer for testing interrupts and resumes, in the SMALL RISC ELTE module for a small Harvard architecture computer also for testing interrupts and resumes, and in the LARGE RISC ELTE module for test of pageing.

11. A few auxiliary functions will ameliorate the task of constructing the RISC logic. First comes a routine that “christens” a new gate, assigning it a name and a type. The name is constructed from a prefix and a serial number, where the prefix indicates the current portion of logic being created. ⟨ Internal subroutines 11 ⟩ ≡

static Vertex ∗new vert (t)

char t; /∗ the type of the new gate ∗/ { register Vertex ∗v;

v = next vert^{++};

if (count < 0) v name = gb save string (prefix ); else {

sprintf (name buf , , prefix , count ); v name = gb save string (name buf ); count^{++};

}

v typ = t; return v;

}

See also sections 13, 14, 15, 40, and 100. This code is used in section 7.

12. #define start prefix (s) strcpy (prefix , s); count = 0 #define numeric prefix (a, b) sprintf (prefix , , a, b); count = 0; ⟨ Private variables 12 ⟩ ≡

static Vertex ∗next vert ; /∗ the first vertex not yet assigned a name ∗/ static char prefix [5]; /∗ prefix string for vertex names ∗/ static long count ; /∗ serial number for vertex names ∗/ static char name buf [100]; /∗ place to form vertex names ∗/

This code is used in section 7.

13. Here are some trivial routines to create gates with 2, 3, or more arguments. The arcs from such a gate to its inputs are assigned length 100. Other routines, defined below, assign length 1 to the arc between an inverter and its unique input. This convention makes the lengths of shortest paths in the resulting network a bit more interesting than they would otherwise be.

#define  100_{L}

⟨ Internal subroutines 11 ⟩ +≡

static Vertex ∗make2 (t, v1 , v2 )

char t; /∗ the type of the new gate ∗/ Vertex ∗v1 , ∗v2 ;

{ register Vertex ∗v = new vert (t); gb new arc(v, v1 , ); gb new arc(v, v2 , ); return v;

} static Vertex ∗make3 (t, v1 , v2 , v3 )

char t; /∗ the type of the new gate ∗/ Vertex ∗v1 , ∗v2 , ∗v3 ;

{ register Vertex ∗v = new vert (t); gb new arc(v, v1 , ); gb new arc(v, v2 , ); gb new arc(v, v3 , ); return v;

} static Vertex ∗make4 (t, v1 , v2 , v3 , v4 )

char t; /∗ the type of the new gate ∗/ Vertex ∗v1 , ∗v2 , ∗v3 , ∗v4 ;

{ register Vertex ∗v = new vert (t); gb new arc(v, v1 , ); gb new arc(v, v2 , ); gb new arc(v, v3 , ); gb new arc(v, v4 , ); return v;

} static Vertex ∗make5 (t, v1 , v2 , v3 , v4 , v5 )

char t; /∗ the type of the new gate ∗/ Vertex ∗v1 , ∗v2 , ∗v3 , ∗v4 , ∗v5 ;

{ register Vertex ∗v = new vert (t); gb new arc(v, v1 , ); gb new arc(v, v2 , ); gb new arc(v, v3 , ); gb new arc(v, v4 , ); gb new arc(v, v5 , ); return v;

} 14. We use utility field w.V to store a pointer to the complement of a gate, if that complement has been formed. This trick prevents the creation of excessive gates that are equivalent to each other. The following subroutine returns a pointer to the complement of a given gate. #define bar w.V /∗ field pointing to complement, if known to exist ∗/ #define even comp(s, v) ((s) & 1 ? v : comp(v)) ⟨ Internal subroutines 11 ⟩ +≡

static Vertex ∗comp(v)

Vertex ∗v; { register Vertex ∗u;

if (v bar ) return v bar ;

u = next vert^{++};

u bar = v; v bar = u;

sprintf (name buf , , v name); u name = gb save string (name buf ); u typ = ; gb new arc(u, v, 1_{L}); return u;

}

15. To create a gate for the EXCLUSIVE-OR of two arguments, we can either construct the OR of two ANDs or the AND of two ORs. We choose the former alternative: ⟨ Internal subroutines 11 ⟩ +≡

static Vertex ∗make xor (u, v)

Vertex ∗u, ∗v; { register Vertex ∗t1 , ∗t2 ;

t1 = make2 ( , u, comp(v));

t2 = make2 ( , comp(u), v);

return make2 ( , t1 , t2 ); }

16. OK, let’s get going. ⟨ Initialize new graph to an empty graph of the appropriate size 16 ⟩ ≡

if (regs < 2 ∨ regs > 16) regs = 16; new graph = gb new graph(2300 + 150 ∗ regs ); if (new graph ≡ Λ) panic(no room); /∗ out of memory before we’re even started ∗/ sprintf (new graph id , , regs ); strcpy (new graph util types , ); next vert = new graph vertices ;

This code is used in section 8.

17. ⟨ Add the RISC data to new graph 17 ⟩ ≡ ⟨ Create the inputs and latches 19 ⟩; ⟨ Create gates for instruction decoding 21 ⟩; ⟨ Create gates for fetching the source value 22 ⟩; ⟨ Create gates for output write data, address and flags; 27 ⟩; ⟨ Create gates for the general logic operation 28 ⟩; ⟨ Create gates for the conditional load operations 29 ⟩; ⟨ Create gates for the matrix operation; 43 ⟩; ⟨ Create gates for the arithmetic operations 42 ⟩; ⟨ Create gates for the sideway add operation; 44 ⟩; ⟨ Create gates that bring everything together properly 31 ⟩; if (next vert ≠ new graph vertices + new graph n) panic(impossible);

/∗ oops, we miscounted; this should be impossible ∗/

This code is used in section 8.

18. Internal names will make it convenient to refer to the most important gates. Here are the names of inputs and latches. ⟨ Local variables for risc elte 9 ⟩ +≡

Vertex ∗run bit ;  /∗ the  input ∗/
Vertex ∗int bit ;  /∗ the  input;  ∗/
Vertex ∗page bit ;  /∗ the  input;  ∗/

Vertex ∗mem[16]; /∗ 16 bits of input from memory ∗/ Vertex ∗prog ; /∗ first of 10 bits in the program register ∗/ Vertex ∗extra; /∗ latched status bit : are we doing an extra memory cycle? ∗/ Vertex ∗xresume; /∗ latched status bit : extra cycle for resume? ∗/ Vertex ∗sign; /∗ the latched value of ∗/ Vertex ∗nonzero; /∗ the latched value of ∗/ Vertex ∗carry ; /∗ the latched value of ∗/ Vertex ∗overflow ; /∗ the latched value of ∗/

Vertex ∗enabled ;  /∗ latched status bit : is interrupt enabled?  ∗/
Vertex ∗translate;  /∗ latched status bit : must translate?  ∗/

Vertex ∗reg [16]; /∗ the least-significant bit of a given register ∗/ 19. #define first of (n, t) new vert (t); for (k = 1; k < n; k^{++}) new vert (t); ⟨ Create the inputs and latches 19 ⟩ ≡

strcpy (prefix , ); count = −1; run bit = new vert ( );

strcpy (prefix ,  ); count = −1; int bit = new vert ( );  /∗  ∗/
strcpy (prefix ,  ); count = −1; page bit = new vert ( );  /∗  ∗/

start prefix ( ); for (k = 0; k < 16; k^{++}) mem[k] = new vert ( ); start prefix ( ); prog = first of (10, ); strcpy (prefix , ); extra = new vert ( ); strcpy (prefix , ); xresume = new vert ( ); /∗ ∗/ strcpy (prefix , ); count = −1; sign = new vert ( ); strcpy (prefix , ); nonzero = new vert ( ); strcpy (prefix , ); carry = new vert ( ); strcpy (prefix , ); overflow = new vert ( );

strcpy (prefix , ); enabled = new vert ( );  /∗  ∗/
strcpy (prefix , ); translate = new vert ( );  /∗  ∗/

for (r = 0; r < regs ; r^{++}) { numeric prefix ( , r); reg [r] = first of (16, );

}

This code is used in section 17.

20. The order of evaluation of function arguments is not defined in C, so we introduce a few macros that force left-to-right order. #define do2 (result , t, v1 , v2 )

{ t1 = v1 ; t2 = v2 ;

result = make2 (t, t1 , t2 ); }

#define do3 (result , t, v1 , v2 , v3 )

{ t1 = v1 ; t2 = v2 ; t3 = v3 ; result = make3 (t, t1 , t2 , t3 ); }

#define do4 (result , t, v1 , v2 , v3 , v4 )

{ t1 = v1 ; t2 = v2 ; t3 = v3 ; t4 = v4 ; result = make4 (t, t1 , t2 , t3 , t4 ); }

#define do5 (result , t, v1 , v2 , v3 , v4 , v5 )

{ t1 = v1 ; t2 = v2 ; t3 = v3 ; t4 = v4 ; t5 = v5 ;

result = make5 (t, t1 , t2 , t3 , t4 , t5 ); }

⟨ Local variables for risc elte 9 ⟩ +≡

Vertex ∗t1 , ∗t2 , ∗t3 , ∗t4 , ∗t5 , ∗t6 , ∗t7 , ∗t8 ;

/∗ temporary holds to force evaluation order; ∗/ Vertex ∗tmp[16]; /∗ additional holding places for partial results ∗/ Vertex ∗imm; /∗ is the source value immediate (a given constant)? ∗/ Vertex ∗rel ; /∗ is the source value relative to the current destination register? ∗/ Vertex ∗dir ; /∗ should the source value be fetched directly from a source register? ∗/ Vertex ∗ind ; /∗ should the source value be fetched indirectly from memory? ∗/ Vertex ∗op; /∗ least significant bit of ∗/ Vertex ∗cond ; /∗ most significant bit of ∗/

Vertex ∗mod [4];  /∗ the  bits ∗/
Vertex ∗dest [4];  /∗ the  bits ∗/
Vertex ∗jump;  /∗ is this command a  , assuming cond is false?  moved ∗/
Vertex ∗write;  /∗ is this command a  , assuming cond is false?  ∗/
Vertex ∗mixed ;  /∗ is this command a  , assuming cond is false?  ∗/
Vertex ∗mo;  /∗ is this command an  or , assuming cond is false?  ∗/
Vertex ∗hop;  /∗ are we doing a  ? ∗/

Vertex ∗mor ; /∗ are we doing a ? ∗/

Vertex ∗brk ;  /∗ enabled interrupt or page error?  ∗/
Vertex ∗nzs ;  /∗ is the  field nonzero?  moved ∗/
Vertex ∗nzd ;  /∗ is the  field nonzero?  moved ∗/
Vertex ∗push;  /∗ is this command a  ?  ∗/
Vertex ∗pop;  /∗ is this command a ?  ∗/
Vertex ∗push or pop;  /∗ is this command a  or ?  ∗/
Vertex ∗trap;  /∗ is this command a  ?  ∗/
Vertex ∗trap or hop;  /∗ is this command a  or a  ?  ∗/
Vertex ∗resume0 ;  /∗ is this command a  with  = 0?  ∗/
Vertex ∗resume;  /∗ is this command a  with  ≠ 0?  ∗/
Vertex ∗load imm;  /∗ is this command an immediate  ?  ∗/
Vertex ∗nope;  /∗ is this command a  , assuming cond = 1, etc.?  ∗/
Vertex ∗write bit ;  /∗ shall we  ?  ∗/

21. The sixth line of the program here can be translated into the logic equation

op = (extra ∧ prog ) ∨ (\overline{extra} ∧ mem[6]) .

Once you see why, you’ll be able to read the rest of this curious code. ⟨ Create gates for instruction decoding 21 ⟩ ≡

start prefix ( ); do3 (imm, , comp(extra), comp(mem[4]), comp(mem[5])); /∗ = 0 ∗/ do3 (rel , , comp(extra), mem[4], comp(mem[5])); /∗ = 1 ∗/ do3 (dir , , comp(extra), comp(mem[4]), mem[5]); /∗ = 2 ∗/ do3 (ind , , comp(extra), mem[4], mem[5]); /∗ = 3 ∗/ do2 (op, , make2 ( , extra, prog ), make2 ( , comp(extra), mem[6])); do2 (cond , , make2 ( , extra, prog + 1), make2 ( , comp(extra), mem[7])); for (k = 0; k < 4; k^{++}) {

do2 (mod [k], , make2 ( , extra, prog + 2 + k), make2 ( , comp(extra), mem[8 + k]));

do2 (dest [k], , make2 ( , extra, prog + 6 + k), make2 ( , comp(extra), mem[12 + k]));

}

jump = make5 ( , op, mod [0], mod [1], mod [2], mod [3]);  /∗ assume cond = 0;  moved ∗/
mixed = make5 ( , op, comp(mod [0]), mod [1], mod [2], mod [3]);  /∗ assume cond = 0;  ∗/
write = make5 ( , op, mod [0], comp(mod [1]), mod [2], mod [3]);  /∗ assume cond = 0;  ∗/
mo = make5 ( , op, mod [3], mod [2], comp(mod [1]), comp(mod [0]));  /∗ assume cond = 0;  ∗/
hop = make2 ( , comp(cond ), jump);  /∗  command? ∗/
mor = make3 ( , mo, comp(cond ), rel );  /∗  command?  ∗/

do2 (brk , , page bit ,

make3 ( , comp(extra), int bit , enabled )); /∗ ∗/ do5 (write bit , , brk ,

make3 ( , write, comp(cond ), imm), make3 ( , write, comp(cond ), rel ), make3 ( , write, comp(cond ), dir ),

make3 ( , write, comp(cond ), extra));  /∗ value of output W;  ∗/
nzs = make4 ( , mem[0], mem[1], mem[2], mem[3]);  /∗  moved ∗/
nzd = make4 ( , dest [0], dest [1], dest [2], dest [3]);  /∗  moved ∗/
push = make3 ( , comp(cond ), write, rel );  /∗  ∗/
pop = make3 ( , comp(cond ), mixed , ind );  /∗  ∗/
push or pop = make2 ( , push, pop);  /∗  ∗/
trap = make4 ( , comp(cond ), mixed , rel , nzd );  /∗  ∗/
trap or hop = make2 ( , trap, hop);  /∗  ∗/

resume0 = make5 ( , comp(cond ), mixed , rel , comp(nzd ), comp(nzs ));

/∗ resume with zero source; ∗/ resume = make5 ( , comp(cond ), mixed , rel , comp(nzd ), nzs );

/∗ resume with nonzero source; ∗/ load imm = make3 ( , comp(cond ), mixed , imm); /∗ ∗/ nope = make5 ( , op, comp(mod [0]), mod [1], comp(mod [2]), mod [3]);

/∗ assume cond = 1, etc; ∗/

This code is used in section 17.

22. ⟨ Create gates for fetching the source value 22 ⟩ ≡ start prefix ( ); ⟨ Set old dest to the present value of the destination register 24 ⟩; ⟨ Set old src to the present value of the source register 25 ⟩; ⟨ Set inc dest to old dest plus 41 ⟩; ⟨ Set inc src and dec src bits; 26 ⟩; for (k = 0; k < 16; k^{++}) /∗ ∗/

do5 (source[k], , make2 ( , imm, mem[k < 4 ? k : 3]), make4 ( , rel , mo, comp(cond ), old src[k]), make3 ( , rel , comp(mor ), inc dest [k]), make2 ( , dir , old src[k]), make2 ( , extra, mem[k]));

This code is used in section 17.

23. ⟨ Local variables for risc elte 9 ⟩ +≡

Vertex ∗up, ∗down;  /∗ gates used when computing inc src, etc.;  moved ∗/
Vertex ∗dest match[16];  /∗ dest match[r] ≡ 1 iff  = r ∗/

Vertex ∗old dest [16]; /∗ contents of destination register before operation ∗/ Vertex ∗src match[16]; /∗ src match[r] ≡ 1 iff = r; ∗/ Vertex ∗old src[16]; /∗ contents of source register before operation ∗/ Vertex ∗inc dest [16]; /∗ old dest plus the field ∗/ Vertex ∗source[16]; /∗ source value for the operation ∗/ Vertex ∗log [16]; /∗ result of general logic operation ∗/ Vertex ∗matrix [16]; /∗ result of matrix operation; ∗/ Vertex ∗shift [18]; /∗ result of shift operation, with carry and overflow ∗/ Vertex ∗sum[18]; /∗ old dest plus source plus optional carry ∗/ Vertex ∗diff [18]; /∗ old dest minus source minus optional borrow ∗/ Vertex ∗ssum[5]; /∗ sideway sum source ∗/ Vertex ∗next loc[16]; /∗ contents of register 0, plus 1 ∗/ Vertex ∗next next loc[16]; /∗ contents of register 0, plus 2 ∗/

Vertex ∗inc src[16];  /∗ contents of register , plus 1;  ∗/
Vertex ∗dec src[16];  /∗ contents of register , minus 1;  ∗/

Vertex ∗result [18]; /∗ result of operating on old dest and source ∗/

24. Here and in the immediately following section we create OR gates old dest [k] and old src[k] that might have as many as 16 inputs. (The actual number of inputs is regs .) All other gates in the network will have at most five inputs. ⟨ Set old dest to the present value of the destination register 24 ⟩ ≡

for (r = 0; r < regs ; r^{++})

do4 (dest match[r], , even comp(r, dest [0]), even comp(r ≫ 1, dest [1]),

even comp(r ≫ 2, dest [2]), even comp(r ≫ 3, dest [3])); for (k = 0; k < 16; k^{++}) {

for (r = 0; r < regs ; r^{++})

tmp[r] = make2 ( , dest match[r], reg [r] + k); old dest [k] = new vert ( ); for (r = 0; r < regs ; r^{++}) gb new arc(old dest [k], tmp[r], );

}

This code is used in section 22.

25. ⟨ Set old src to the present value of the source register 25 ⟩ ≡

for (r = 0; r < regs ; r^{++}) /∗ ∗/

do4 (src match[r], , even comp(r, mem[0]), even comp(r ≫ 1, mem[1]),

even comp(r ≫ 2, mem[2]), even comp(r ≫ 3, mem[3])); /∗ ∗/ for (k = 0; k < 16; k^{++}) {

for (r = 0; r < regs ; r^{++})

tmp[r] = make2 ( , src match[r], reg [r] + k);  /∗  ∗/
old src[k] = new vert ( );  /∗  ∗/

for (r = 0; r < regs ; r^{++}) gb new arc(old src[k], tmp[r], ); }

This code is used in section 22.

26. ⟨ Set inc src and dec src bits; 26 ⟩ ≡ inc src[0] = comp(old src[0]); dec src[0] = comp(old src[0]); up = old src[0]; /∗ remaining bits must increase ∗/ down = comp(old src[0]); /∗ remaining bits must decrease ∗/ for (k = 1; ; k^{++}) {

comp(up); comp(down); do2 (inc src[k], ,

make2 ( , comp(old src[k]), up), make2 ( , old src[k], comp(up)));

do2 (dec src[k], , make2 ( , comp(old src[k]), down), make2 ( , old src[k], comp(down)));

if (k < 15) { up = make2 ( , up, old src[k]); down = make2 ( , down, comp(old src[k]));

} else break; }

This code is used in section 22.

27. ⟨ Create gates for output write data, address and flags; 27 ⟩ ≡ start prefix ( ); for (k = 0; k < 16; k^{++}) {

do2 (t5 , , make2 ( , comp(brk ), old dest [k]), make2 ( , brk , reg [0] + k));

{ register Arc ∗a = gb virgin arc( ); a tip = make3 ( , t5 , write bit , run bit ); a next = new graph outs ; new graph outs = a; /∗ pointer to memory address bit; ∗/

} } /∗ arcs for output write data bits will appear in big-endian order; ∗/ for (k = 0; k < 16; k^{++}) {

do2 (t5 , , make2 ( , rel , dec src[k]), make2 ( , comp(rel ), source[k]));

{ register Arc ∗a = gb virgin arc( ); a tip = make4 ( , t5 , write bit , comp(brk ), run bit ); a next = new graph outs ; new graph outs = a; /∗ pointer to write address bit ∗/

} } /∗ arcs for write address bits will appear in big-endian order ∗/ t5 = make3 ( , brk , comp(rel ), nzs ); /∗ write data flag ∗/ { register Arc ∗a = gb virgin arc( );

a tip = make3 ( , t5 , write bit , run bit ); a next = new graph outs ; new graph outs = a; /∗ pointer to write data flag ∗/

} { register Arc ∗a = gb virgin arc( );

a tip = make2 ( , write bit , run bit ); a next = new graph outs ; new graph outs = a; /∗ pointer to write flag ∗/

}

This code is used in section 17.

28. ⟨ Create gates for the general logic operation 28 ⟩ ≡ start prefix ( ); for (k = 0; k < 16; k^{++})

do4 (log [k], , make3 ( , mod [0], comp(old dest [k]), comp(source[k])), make3 ( , mod [1], comp(old dest [k]), source[k]), make3 ( , mod [2], old dest [k], comp(source[k])), make3 ( , mod [3], old dest [k], source[k]));

This code is used in section 17.

29. ⟨ Create gates for the conditional load operations 29 ⟩ ≡ start prefix ( ); do4 (tmp[0], ,

make3 ( , mod [0], comp(sign), comp(nonzero)), make3 ( , mod [1], comp(sign), nonzero), make3 ( , mod [2], sign, comp(nonzero)), make3 ( , mod [3], sign, nonzero));

do4 (tmp[1], , make3 ( , mod [0], comp(carry ), comp(overflow )), make3 ( , mod [1], comp(carry ), overflow ), make3 ( , mod [2], carry , comp(overflow )), make3 ( , mod [3], carry , overflow ));

do3 (change, , comp(cond ), make2 ( , tmp[0], comp(op)), make2 ( , tmp[1], op));

This code is used in section 17.

30. ⟨ Local variables for risc elte 9 ⟩ +≡ Vertex ∗change; /∗ is the destination register supposed to change? ∗/

31. Hardware is like software except that it performs all the operations all the time and then selects only the results it needs. (If you think about it, this is a profound observation about economics, society, and nature. Gosh.) ⟨ Create gates that bring everything together properly 31 ⟩ ≡

start prefix ( ); ⟨ Create gates for the next loc and next next loc bits 32 ⟩; ⟨ Create gates for the result bits 33 ⟩; ⟨ Create gates for the new values of registers 1 to regs 35 ⟩; ⟨ Create gates for the new values of flags; 37 ⟩; ⟨ Create gates for the new values of the program register 34 ⟩; ⟨ Create gates for the new values of register 0 and the memory address register 38 ⟩;

This code is used in section 17.

32. ⟨ Create gates for the next loc and next next loc bits 32 ⟩ ≡ next loc[0] = comp(reg [0]); next next loc[0] = reg [0]; next loc[1] = make xor (reg [0] + 1, reg [0]); next next loc[1] = comp(reg [0] + 1); for (t5 = reg [0] + 1, k = 2; k < 16; t5 = make2 ( , t5 , reg [0] + k^{++})) {

next loc[k] = make xor (reg [0] + k, make2 ( , reg [0], t5 )); next next loc[k] = make xor (reg [0] + k, t5 );

}

This code is used in section 31.

33. ⟨ Create gates for the result bits 33 ⟩ ≡

for (k = 0; k < 5; k^{++}) {

do5 (result [k], , make3 ( , mixed , dir , ssum[k]), make5 ( , mod [3], mod [2], comp(mod [1]), comp(mod [0]), matrix [k]), make2 ( , comp(mod [3]), shift [k]), make4 ( , mod [3], comp(mod [2]), comp(mod [1]), sum[k]), make4 ( , mod [3], comp(mod [2]), mod [1], diff [k]));

/∗ assuming op = 1 and cond = 0 for all; ∗/ do5 (result [k], ,

make3 ( , comp(cond ), comp(op), log [k]), make2 ( , trap or hop, next loc[k]), make3 ( , mixed , extra, source[k]), make3 ( , cond , change, source[k]), make3 ( , op, comp(cond ), result [k]));

} for ( ; k < 16; k^{++}) {

do4 (result [k], , make5 ( , mod [3], mod [2], comp(mod [1]), comp(mod [0]), matrix [k]), make2 ( , comp(mod [3]), shift [k]), make4 ( , mod [3], comp(mod [2]), comp(mod [1]), sum[k]), make4 ( , mod [3], comp(mod [2]), mod [1], diff [k]));

/∗ assuming op = 1 and cond = 0 for all; ∗/ do5 (result [k], ,

make3 ( , comp(cond ), comp(op), log [k]), make2 ( , trap or hop, next loc[k]), make3 ( , mixed , extra, source[k]), make3 ( , cond , change, source[k]), make3 ( , op, comp(cond ), result [k]));

} for (k = 16; k < 18; k^{++}) /∗ carry and overflow bits of the result ∗/

do3 (result [k], , make3 ( , op, comp(mod [3]), shift [k]), make5 ( , op, mod [3], comp(mod [2]), comp(mod [1]), sum[k]), make5 ( , op, mod [3], comp(mod [2]), mod [1], diff [k]));

This code is used in section 31.

34. The program register prog and the extra bit are needed for the case when we must spend an extra cycle to fetch a word from memory. On the first cycle, ind is true, so a “result” is calculated but not actually used. On the second cycle, extra is true. A slight optimization has been introduced in order to make the circuit a bit more interesting: If a conditional load instruction occurs with indirect addressing and a false condition, the extra cycle is not taken. (The next next loc values were computed for this reason.) #define latchit (u, latch) (latch) alt = make2 ( , u, run bit )

/∗ u & run bit is new value for latch ∗/

⟨ Create gates for the new values of the program register 34 ⟩ ≡

for (k = 0; k < 10; k^{++}) latchit (mem[k + 6], prog + k);

This code is used in section 31.

35. ⟨ Create gates for the new values of registers 1 to regs 35 ⟩ ≡

t8 = make4 ( , comp(write bit ), comp(load imm), change, comp(ind ));

/∗ should destination register change? ∗/ for (r = 1; r < regs ; r^{++}) {

t7 = make2 ( , t8 , dest match[r]); /∗ should destination register r change? ∗/ t6 = make2 ( , push or pop, src match[r]); /∗ should source register r change? ∗/ for (k = 0; k < 16; k^{++}) {

do4 (t5 , , make2 ( , t7 , result [k]), make4 ( , comp(t7 ), src match[r], push, dec src[k]), make4 ( , comp(t7 ), src match[r], pop, inc src[k]), make3 ( , comp(t7 ), comp(t6 ), reg [r] + k));

latchit (t5 , reg [r] + k); }

}

This code is used in section 31.

36. ⟨ Local variables for risc elte 9 ⟩ +≡

Vertex ∗nochange sn;  /∗ should the flags and changed?  ∗/
Vertex ∗nochange kv ;  /∗ should the flags and changed?  ∗/

Vertex ∗nextra; /∗ must we take an extra cycle? ∗/ Vertex ∗ntranslate; /∗ must we translate in the next cycle? ∗/ 37. ⟨ Create gates for the new values of flags; 37 ⟩ ≡

nochange sn = make5 ( , cond , ind , jump, write, mixed );  /∗  ∗/
nochange kv = make3 ( , nochange sn, comp(op), mo);  /∗  ∗/

do2 (t5 , , make2 ( , sign, nochange sn), make2 ( , result [15], comp(nochange sn)));

latchit (t5 , sign); do5 (t6 , , op, mod [0], comp(mod [2]), mod [3],

make2 ( , nonzero, sign)); do4 (t5 , ,

make4 ( , result [0], result [1], result [2], result [3]), make4 ( , result [4], result [5], result [6], result [7]), make4 ( , result [8], result [9], result [10], result [11]), make4 ( , result [12], result [13], result [14], t6 ));

do2 (t5 , , make2 ( , nonzero, nochange sn), make2 ( , t5 , comp(nochange sn)));

latchit (t5 , nonzero); do2 (t5 , ,

make2 ( , overflow , nochange kv ),

make2 ( , result [17], comp(nochange kv ))); latchit (t5 , overflow ); do2 (t5 , ,

make2 ( , carry , nochange kv ),

make2 ( , result [16], comp(nochange kv ))); latchit (t5 , carry ); do4 (nextra, , resume0 , load imm,

make2 ( , ind , comp(cond )), make2 ( , ind , change));

latchit (nextra, extra); do4 (t5 , , xresume, resume,

make3 ( , enabled , comp(brk ), comp(trap)), make5 ( , nope, cond , rel , nzd , comp(nzs )));

latchit (t5 , enabled ); do3 (ntranslate, , xresume, resume,

make3 ( , translate, comp(brk ), comp(trap))); latchit (ntranslate, translate); latchit (resume0 , xresume);

This code is used in section 31.

38. As usual, we have left the hardest case for last, hoping that we will have learned enough tricks to handle it when the time of reckoning finally arrives.

The most subtle part of the logic here is perhaps the case of a command with = 3. We want to increase register 0 by 1 during the first cycle of such a command, if = 0, so that the result will be correct on the next cycle. ⟨ Create gates for the new values of register 0 and the memory address register 38 ⟩ ≡

skip = make2 ( , cond , comp(change)); /∗ false conditional? ∗/ do4 (normal , ,

make2 ( , skip, comp(ind )), make2 ( , skip, nzs ), make3 ( , comp(skip), ind , comp(nzs )), make3 ( , comp(skip), comp(trap or hop), nzd )); /∗ goto next loc; ∗/

do3 (special , , load imm, resume0 ,

make3 ( , comp(skip), ind , nzs )); /∗ read from data memory; ∗/ for (k = 0; k < 16; k^{++}) {

switch (k) { case 1: case 2: case 3: case 4: do2 (t6 , ,

make3 ( , hop, comp(ind ), source[k]), make2 ( , trap, mem[k − 1]));

do5 (t5 , , t6 , make2 ( , normal , next loc[k]), make4 ( , skip, ind , comp(nzs ), next next loc[k]), make2 ( , resume, old src[k]), make5 ( , comp(skip), comp(trap or hop), comp(ind ), comp(nzd ), result [k]));

break; case 5: do2 (t6 , , trap, make3 ( , hop, comp(ind ), source[k]));

do5 (t5 , , t6 , make2 ( , normal , next loc[k]), make4 ( , skip, ind , comp(nzs ), next next loc[k]), make2 ( , resume, old src[k]), make5 ( , comp(skip), comp(trap or hop), comp(ind ), comp(nzd ), result [k]));

break; default: do5 (t5 , ,

make2 ( , normal , next loc[k]), make4 ( , skip, ind , comp(nzs ), next next loc[k]), make3 ( , hop, comp(ind ), source[k]), make2 ( , resume, old src[k]), make5 ( , comp(skip), comp(trap or hop), comp(ind ), comp(nzd ), result [k]));

break; } do2 (t4 , ,

make2 ( , special , reg [0] + k), make2 ( , comp(special ), t5 ));

latchit (t4 , reg [0] + k); do3 (t4 , ,

make2 ( , load imm, mem[k < 4 ? k : 3]), make4 ( , special , comp(resume0 ), comp(load imm), old src[k]), make2 ( , comp(special ), t5 )); /∗ ∗/

{ register Arc ∗a = gb virgin arc( );

if (k) /∗ ∗/

a tip = make3 ( , t4 , run bit , comp(brk )); else {

do2 (t5 , ,

make2 ( , run bit , brk ),

make3 ( , t4 , run bit , comp(brk ))); a tip = t5 ;

}

a next = new graph outs ;

new graph outs = a; /∗ pointer to memory address bit ∗/ }

} /∗ arcs for output bits will appear in big-endian order ∗/ { register Arc ∗a = gb virgin arc( ); /∗ ∗/

a tip = make3 ( , special , run bit , comp(brk ));

a next = new graph outs ;

new graph outs = a; /∗ pointer to special flag: data address space ∗/ } { register Arc ∗a = gb virgin arc( ); /∗ ∗/

a tip = make2 ( , nextra, run bit );

a next = new graph outs ;

new graph outs = a; /∗ pointer to nextra value ∗/ } { register Arc ∗a = gb virgin arc( ); /∗ ∗/

a tip = make2 ( , ntranslate, run bit );

a next = new graph outs ;

new graph outs = a; /∗ pointer to ntranslate flag ∗/ }

This code is used in section 31.

39. ⟨ Local variables for risc elte 9 ⟩ +≡ Vertex ∗skip; /∗ are we skipping a conditional load operation? ∗/ Vertex ∗normal ; /∗ is this a case where register 0 is simply incremented? ∗/

Vertex ∗special ;  /∗ is this a case where the memory address register point to data space?  ∗/
Vertex ∗fromresult ;  /∗ is this a case where register 0 is set from result?  ∗/

§40  GB GATES ELTE  SERIAL ADDITION 25

40. Serial addition. We haven’t yet specified the parts of risc elte that deal with addition and subtraction; somehow, those parts wanted to be separate from the rest. To complete our mission, we will use subroutine calls of the form ‘make adder (n, x, y, z, carry , add )’, where x and y are n-bit arrays of input gates and z is an (n + 1)-bit array of output gates. If add ≠ 0, the subroutine computes x + y, otherwise it computes x − y. If carry ≠ 0, the carry gate is effectively added to y before the operation.

A simple n-stage serial scheme, which reduces the problem of n-bit addition to (n − 1)-bit addition, is adequate for our purposes here. (A parallel adder, which gains efficiency by reducing the problem size from n to n/ϕ, can be found in the prod routine below.)

The handy identity x − y = \overline{\overline{x} + y} is used to reduce subtraction to addition. ⟨ Internal subroutines 11 ⟩ +≡

static void make adder (n, x, y, z, carry , add )

unsigned long n; /∗ number of bits ∗/ Vertex ∗x[ ], ∗y[ ]; /∗ input gates ∗/ Vertex ∗z[ ]; /∗ output gates ∗/ Vertex ∗carry ; /∗ add this to y, unless it’s null ∗/ char add ; /∗ should we add or subtract? ∗/

{ register long k; Vertex ∗t1 , ∗t2 , ∗t3 , ∗t4 ; /∗ temporary storage used by do4 ∗/ if (¬carry ) {

z[0] = make xor (x[0], y[0]); carry = make2 ( , even comp(add , x[0]), y[0]); k = 1;

} else k = 0; for ( ; k < n; k^{++}) {

comp(x[k]); comp(y[k]); comp(carry ); /∗ generate inverse gates ∗/ do4 (z[k], ,

make3 ( , x[k], comp(y[k]), comp(carry )), make3 ( , comp(x[k]), y[k], comp(carry )), make3 ( , comp(x[k]), comp(y[k]), carry ), make3 ( , x[k], y[k], carry ));

do3 (carry , , make2 ( , even comp(add , x[k]), y[k]), make2 ( , even comp(add , x[k]), carry ), make2 ( , y[k], carry ));

} z[n] = carry ;

26  SERIAL ADDITION  GB GATES ELTE §41

} 41. OK, now we can add. What good does that do us? In the first place, we need a 4-bit adder to compute the least significant bits of old dest + . The other 12 bits of that sum are simpler. ⟨ Set inc dest to old dest plus 41 ⟩ ≡

make adder (4_{L}, old dest , mem, inc dest , Λ, 1); up = make2 ( , inc dest [4], comp(mem[3])); /∗ remaining bits must increase ∗/ down = make2 ( , comp(inc dest [4]), mem[3]); /∗ remaining bits must decrease ∗/ for (k = 4; ; k^{++}) {

comp(up); comp(down); do3 (inc dest [k], ,

make2 ( , comp(old dest [k]), up),

make2 ( , comp(old dest [k]), down),

make3 ( , old dest [k], comp(up), comp(down))); if (k < 15) {

up = make2 ( , up, old dest [k]); down = make2 ( , down, comp(old dest [k]));

} else break; }

This code is used in section 22.

42. In the second place, we need a 16-bit adder and a 16-bit subtracter for the four addition/subtraction commands. ⟨ Create gates for the arithmetic operations 42 ⟩ ≡

start prefix ( ); ⟨ Create gates for the shift operations 45 ⟩; make adder (16_{L}, old dest , source, sum, make2 ( , carry , mod [0]), 1); /∗ adder ∗/ make adder (16_{L}, old dest , source, diff , make2 ( , carry , mod [0]), 0); /∗ subtracter ∗/ do2 (sum[17], ,

make3 ( , old dest [15], source[15], comp(sum[15])), make3 ( , comp(old dest [15]), comp(source[15]), sum[15])); /∗ overflow ∗/

do2 (diff [17], , make3 ( , old dest [15], comp(source[15]), comp(diff [15])), make3 ( , comp(old dest [15]), source[15], diff [15])); /∗ overflow ∗/

This code is used in section 17.

43. ⟨ Create gates for the matrix operation; 43 ⟩ ≡

for (i = 0; i < 4; i^{++})

for (j = 0; j < 4; j^{++}) { t1 = make2 ( , old dest [0 + i], source[4 ∗ j + 0]); t2 = make2 ( , old dest [4 + i], source[4 ∗ j + 1]); t3 = make2 ( , old dest [8 + i], source[4 ∗ j + 2]); t4 = make2 ( , old dest [12 + i], source[4 ∗ j + 3]); t5 = make xor (t1 , t2 ); t6 = make xor (t3 , t4 ); t7 = make xor (t5 , t6 ); t8 = make4 ( , t1 , t2 , t3 , t4 ); do2 (matrix [4 ∗ j + i], ,

make2 ( , rel , t8 ),

make2 ( , comp(rel ), t7 )); }

This code is used in section 17.

44. Sideway add operation use a three-adder; first we define this. (There is a much better construction for sideway add, find by Ádám Nagy; this simple version will be substituted by his version in the future.) #define three add (result high, result low , v1 , v2 , v3 )

{ t6 = v1 ; t7 = v2 ; t8 = v3 ; comp(t6 ); comp(t7 ); comp(t8 ); /∗ generate inverse gates ∗/ do4 (result low , ,

make3 ( , t6 , comp(t7 ), comp(t8 )), make3 ( , comp(t6 ), t7 , comp(t8 )), make3 ( , comp(t6 ), comp(t7 ), t8 ), make3 ( , t6 , t7 , t8 ));

do3 (result high, , make2 ( , t6 , t7 ),

make2 ( , t7 , t8 ),
make2 ( , t8 , t6 )); }

⟨ Create gates for the sideway add operation; 44 ⟩ ≡ three add (tmp[15], ssum[0], old src[0], old src[1], old src[2]); three add (tmp[14], ssum[1], old src[3], old src[4], old src[5]); three add (tmp[13], ssum[2], old src[6], old src[7], old src[8]); three add (tmp[12], ssum[3], old src[9], old src[10], old src[11]); three add (tmp[11], ssum[4], old src[12], old src[13], old src[14]); three add (tmp[10], tmp[7], old src[15], ssum[0], ssum[1]); three add (tmp[9], ssum[1], ssum[2], ssum[3], ssum[4]); ssum[0] = make xor (tmp[7], ssum[1]); tmp[8] = make2 ( , ssum[1], tmp[7]); three add (ssum[4], tmp[7], tmp[15], tmp[14], tmp[13]); three add (ssum[3], tmp[15], tmp[12], tmp[11], tmp[10]); three add (ssum[2], tmp[14], tmp[9], tmp[8], tmp[7]); ssum[1] = make xor (tmp[15], tmp[14]); tmp[7] = make2 ( , tmp[15], tmp[14]); three add (tmp[15], tmp[8], ssum[2], ssum[3], ssum[4]); ssum[2] = make xor (tmp[7], tmp[8]); tmp[14] = make2 ( , tmp[7], tmp[8]); ssum[3] = make xor (tmp[15], tmp[14]); ssum[4] = make2 ( , tmp[15], tmp[14]);

This code is used in section 17.

45. ⟨ Create gates for the shift operations 45 ⟩ ≡

for (k = 0; k < 16; k^{++})

do4 (shift [k], ,

(k ≡ 0 ? make4 ( , source[15], mod [0], comp(mod [1]), comp(mod [2])) :

make3 ( , source[k − 1], comp(mod [1]), comp(mod [2]))),

(k < 4 ? make4 ( , source[k + 12], mod [0], mod [1], comp(mod [2])) :

make3 ( , source[k − 4], mod [1], comp(mod [2]))),

(k ≡ 15 ? make4 ( , source[15], comp(mod [0]), comp(mod [1]), mod [2]) :

make3 ( , source[k + 1], comp(mod [1]), mod [2])),

(k > 11 ? make4 ( , source[15], comp(mod [0]), mod [1], mod [2]) :

make3 ( , source[k + 4], mod [1], mod [2])));

do4 (shift [16], , make2 ( , comp(mod [2]), source[15]), make3 ( , comp(mod [2]), mod [1], make3 ( , source[14], source[13], source[12])), make3 ( , mod [2], comp(mod [1]), source[0]), make3 ( , mod [2], mod [1], source[3])); /∗ “carry” ∗/

do3 (shift [17], , make3 ( , comp(mod [2]), comp(mod [1]), make xor (source[15], source[14])), make4 ( , comp(mod [2]), mod [1],

make5 ( , source[15], source[14], source[13], source[12], source[11]), make5 ( , comp(source[15]), comp(source[14]), comp(source[13]), comp(source[12]), comp(source[11]))),

make3 ( , mod [2], mod [1], make3 ( , source[0], source[1], source[2]))); /∗ “overflow” ∗/

This code is used in section 42.

§46  GB GATES ELTE  RISC SIMULATION 29

46. RISC simulation. The simulate routine works from global array risc state and simulate exactly the processor created by risc elte. Given optional pointers in vec and out vec, the procedure simulate will assign new values to risc state. If in vec is non-null, it should point to a string of characters, each or , that will be assigned to the first “gates” of the “network”, in order; otherwise simulate assumes that all input “gates” have already received appropriate values and it will not change them. New values are computed after this.

If out vec is non-null, it should point to a memory area capable of receiving m + 1 characters, where m is the number of outputs; a string containing the respective output values will be deposited there. ⟨ The simulate routine 46 ⟩ ≡

int simulate(in vec, out vec)

char ∗in vec; /∗ string for input values, or Λ ∗/ char ∗out vec; /∗ string for output values, or Λ ∗/

{ ⟨ Local variables for simulate 47 ⟩ regs = (risc state[17] &^{#}f) + 1; if (in vec) ⟨ Simulate input 67 ⟩ run bit = risc state[17] &^{#}8000; if (¬run bit ) ⟨ Clear everything 48 ⟩ else {

⟨ Set brk 50 ⟩;

if (brk ) ⟨ Simulate interrupt 51 ⟩

else { ⟨ Simulate instruction decoding 53 ⟩; ⟨ Simulate fetching the source value 55 ⟩; if (cond ) ⟨ Simulate the conditional load operations 57 ⟩ else if (a ≠ 3) if (op)

switch (mod ) {

case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: ⟨ Simulate the shift operations 60 ⟩; break;

case 8: case 9: case 10: case 11: ⟨ Simulate addition and subtraction 59 ⟩;

break; case 12: ⟨ Simulate the matrix operations 61 ⟩;

break; case 13: ⟨ Set output write data, address and flags 62 ⟩;

break; case 14: ⟨ Simulate mixed operations 63 ⟩;

break; case 15: ⟨ Simulate jump 65 ⟩;

break; }

else ⟨ Simulate the general logic operation 58 ⟩ else ⟨ Simulate fetching data 56 ⟩ ⟨ Bring simulation together properly 66 ⟩;

} } if (out vec) ⟨ Simulate output 68 ⟩ return 0;

}

This code is used in section 7.

30  RISC SIMULATION  GB GATES ELTE §47

47. ⟨ Local variables for simulate 47 ⟩ ≡ register unsigned i, j, k, l; /∗ all-purpose indices ∗/ unsigned regs ; /∗ number of registers ∗/ unsigned run bit ; /∗ the input ∗/ unsigned brk ; /∗ page error or enabled interrupt? ∗/ unsigned cond ; /∗ most significant bit of ∗/ unsigned a; /∗ the bits or greater then 3 by extra ∗/ unsigned op; /∗ least significant bit of ∗/

unsigned mod ;  /∗ the  bits ∗/

See also sections 49, 52, and 54. This code is used in section 46.

48. ⟨ Clear everything 48 ⟩ ≡

for (k = 0; k < 22; k^{++})

if (k ≡ 17) risc state[k] &= ^{#}e0ff; /∗ save input bits, four system bits and number of regs ∗/ else risc state[k] = 0;

This code is used in section 46.

49. ⟨ Local variables for simulate 47 ⟩ +≡

unsigned int bit ;  /∗ the  input ∗/
unsigned page bit ;  /∗ the  input ∗/

unsigned enabled ; /∗ ∗/

50. ⟨ Set brk 50 ⟩ ≡

{ int bit = risc state[17] &^{#}4000; page bit = risc state[17] &^{#}2000; enabled = risc state[17] &^{#}1000; brk = page bit ∨ (int bit ∧ enabled );

}

This code is used in section 46.

51. ⟨ Simulate interrupt 51 ⟩ ≡

{ risc state[18] = risc state[0]; /∗ old value of register 0 to write out ∗/ risc state[19] = 0; /∗ to address 0 ∗/ risc state[20] = risc state[0] = 1; /∗ jump to 1 ∗/ risc state[17] = (risc state[17] &^{#}e0ff) | ^{#}0300; /∗ reset , , dr , but set w, dw ∗/

}

This code is used in section 46.

52. ⟨ Local variables for simulate 47 ⟩ +≡ unsigned flags ; /∗ , , , , , and ∗/ unsigned extra; /∗ latched status bit : are we doing an extra memory cycle? ∗/ unsigned mem; /∗ input from memory ∗/ unsigned prog ; /∗ first of 10 bits in the program register ∗/ unsigned inst ; /∗ the actual instruction code, the program register ∗/ unsigned src; /∗ the bits or junk if extra ∗/ unsigned old src; /∗ contents of source register before operation ∗/ unsigned dest ; /∗ the bits ∗/ unsigned old dest ; /∗ contents of destination register before operation ∗/ unsigned loc; /∗ contents of register 0 before operation ∗/ unsigned la; /∗ next load address ∗/ unsigned dr ; /∗ is this a case where the memory address register point to data space? ∗/ unsigned nextra; /∗ must we take an extra cycle? ∗/ unsigned change; /∗ is the destination register supposed to change? ∗/ unsigned result ; /∗ result of operating on old dest and source ∗/

53. ⟨ Simulate instruction decoding 53 ⟩ ≡

{ flags = risc state[16] &^{#}3f; extra = flags &^{#}20; mem = risc state[21]; prog = risc state[16] &^{#}ffc0; risc state[16] = (mem &^{#}ffc0) + (flags &^{#}f);

/∗ presuppose no , no , but otherwise no change flags ∗/ inst = extra ? prog : mem; src = inst &^{#}f; old src = src < regs ? risc state[src] : 0; a = ((inst ≫ 4) &^{#}3) + extra; /∗ > 3 if extra ∗/ op = inst &^{#}40; cond = inst &^{#}80; mod = (inst ≫ 8) &^{#}f; dest = (inst ≫ 12) &^{#}f; old dest = dest < regs ? risc state[dest ] : 0; loc = risc state[0]; la = (loc + 1) &^{#}ffff; /∗ presuppose normal cycle ∗/ dr = 0; /∗ presuppose no special ∗/ nextra = 0; /∗ new extra; presuppose no extra ∗/ change = 1; /∗ presuppose change ∗/ result = old dest ; /∗ if no change, this remains ∗/ risc state[17] &= ^{#}f8ff; /∗ presuppose no data and no write, others not changed ∗/ risc state[18] = 0; /∗ presuppose no write ∗/ risc state[19] = 0; /∗ presuppose no write ∗/

}

This code is used in section 46.

54. ⟨ Local variables for simulate 47 ⟩ +≡ unsigned imm value; /∗ sign extended value of the field ∗/ unsigned inc dest ; /∗ old dest plus imm value ∗/ unsigned source; /∗ source value for the operation ∗/ 55. ⟨ Simulate fetching the source value 55 ⟩ ≡

imm value = (mem &^{#}f) + (((mem ≫ 3) & 1) ? ^{#}fff0 : 0); inc dest = (old dest + imm value) &^{#}ffff; switch (a) { case 0: source = imm value;

break; case 1: source = inc dest ;

break; case 2: source = old src;

break; default: source = mem;

break; }

This code is used in section 46.

56. ⟨ Simulate fetching data 56 ⟩ ≡

{ change = 0; nextra = ^{#}20; if (src) { /∗ otherwise fetching from program and hence normal ∗/

risc state[0] = loc;

dr = ^{#}400;

la = old src;

if (mod ≡ 14) risc state[src] = (old src + 1) &^{#}ffff; /∗ ∗/ }

}

This code is used in section 46.

57. ⟨ Simulate the conditional load operations 57 ⟩ ≡

{

if (op) { k = flags &^{#}3; /∗ and ∗/ change = (mod ≫ k) & 1;

} else {

k = (flags ≫ 2) &^{#}3; /∗ and ∗/

change = (mod ≫ k) & 1;

if (mod ≡ 10 ∧ a ≡ 1 ∧ dest ≠ 0 ∧ src ≡ 0) risc state[17] |= ^{#}1000; /∗ ∗/ } if (change)

if (a ≠ 3) result = source;

else nextra = ^{#}20; else if (a ≡ 3 ∧ src ≡ 0) la = (loc + 2) &^{#}ffff; /∗ skip direct data ∗/

}

This code is used in section 46.

58. ⟨ Simulate the general logic operation 58 ⟩ ≡

{ k = mod & 1 ? ((∼old dest ) & (∼source)) : 0; k |= ((mod ≫ 1) & 1) ? ((∼old dest ) & source) : 0; k |= ((mod ≫ 2) & 1) ? (old dest & (∼source)) : 0; k |= ((mod ≫ 3) & 1) ? (old dest & source) : 0; result = k &^{#}ffff; j = ((result ≫ 14) & 2) + ((result &^{#}7fff) ≠ 0); /∗ and ∗/ risc state[16] = (risc state[16] &^{#}fff3) | (j ≪ 2);

}

This code is used in section 46.

59. ⟨ Simulate addition and subtraction 59 ⟩ ≡

{

if ((mod ≫ 1) & 1) { j = (old dest − source) &^{#}ffff; /∗ subtraction ∗/ k = j > old dest ; /∗ new carry ∗/ result = (mod & 1) ? (flags ≫ 1) & 1 : 0; /∗ old carry or 0 ∗/ result = (j − result ) &^{#}ffff; k += result > j; j = (∼result & old dest & ∼source) | (result & ∼old dest & source); /∗ overflow ∗/ k = (k ≪ 1) + (j ≫ 15); /∗ and ∗/

} else {

result = (old dest + source) &^{#}ffff; /∗ addition ∗/

k = result < old dest ; /∗ new carry ∗/

j = (mod & 1) ? (flags ≫ 1) & 1 : 0; /∗ old carry or 0 ∗/

result = (result + j) &^{#}ffff;

k += result < j;

j = (∼result & old dest & source) | (result & ∼old dest & ∼source); /∗ overflow ∗/ k = (k ≪ 1) + (j ≫ 15); /∗ and ∗/

} j = ((result ≫ 14) & 2) + ((result &^{#}7fff) ≠ 0); /∗ and ∗/ if (mod & 1) j |= (flags & 3 ≠ 0); risc state[16] = (risc state[16] &^{#}fff0) | (j ≪ 2) | k;

}

This code is used in section 46.

60. ⟨ Simulate the shift operations 60 ⟩ ≡

{ j = 0; /∗ overflow ∗/ switch (mod ) { case 0: result = (source ≪ 1) &^{#}ffff;

k = source ≫ 15; j = (k ⊕ (source ≫ 14)) & 1; break;

case 1: result = (source ≪ 1) &^{#}ffff; k = source ≫ 15; j = (k ⊕ (source ≫ 14)) & 1; result += k; break;

case 2: result = (source ≪ 4) &^{#}ffff; k = source ≫ 12; k = ((k & 7) ≠ 0); j = source ≫ 11; j = (j ≠ 0) ∧ (j ≠ ^{#}1f); break;

case 3: result = (source ≪ 4) &^{#}ffff; k = source ≫ 12; result += k; k = ((k & 7) ≠ 0); j = source ≫ 11; j = (j ≠ 0) ∧ (j ≠ ^{#}1f); break;

case 4: result = (source ≫ 1); k = source &^{#}8000; result += k; k = source & 1; break;

case 5: result = source ≫ 1; k = source & 1; break;

case 6: result = source ≫ 4; k = source &^{#}8000; result = result + k + (k ≫ 1) + (k ≫ 2); k = (source & 8) ≫ 3; j = (source & 7) ≠ 0; break;

case 7: result = source ≫ 4; k = (source & 8) ≫ 3; j = (source & 7) ≠ 0; break;

} k = (k ≪ 1) + j; /∗ and ∗/ j = ((result ≫ 14) & 2) + ((result &^{#}7fff) ≠ 0); /∗ and ∗/ risc state[16] = (risc state[16] &^{#}fff0) | (j ≪ 2) | k;

}

This code is used in section 46.

61. ⟨ Simulate the matrix operations 61 ⟩ ≡

{ unsigned t, tt ; result = 0; tt = (a ≡ 1) ? old src : source; for (i = 0; i < 4; i^{++}) {

k = 0;

l = 0;

t = old dest ;

for (j = 0; j < 4; j^{++}, tt ≫= 1, t ≫= 4) { k ⊕= tt & 1 ? t &^{#}f : 0; l |= tt & 1 ? t &^{#}f : 0;

}

result += (a ≡ 1 ? l : k) ≪ (i ≪ 2); } j = ((result ≫ 14) & 2) + ((result &^{#}7fff) ≠ 0); /∗ and ∗/ risc state[16] = (risc state[16] &^{#}fff3) | (j ≪ 2);

}

This code is used in section 46.

62. ⟨ Set output write data, address and flags 62 ⟩ ≡

{ change = 0; risc state[18] = old dest ; risc state[19] = source; k = ^{#}300; /∗ presuppose and ∗/ if (a ≡ 1) {

risc state[19] = (old src − 1) &^{#}ffff;

if (src < regs ) risc state[src] = risc state[19]; k = src ? ^{#}300 : ^{#}200;

} risc state[17] |= k;

}

This code is used in section 46.

63. ⟨ Simulate mixed operations 63 ⟩ ≡

{ switch (a) { case 0: la = imm value;

dr = ^{#}400;

risc state[0] = loc;

nextra = ^{#}20;

break; case 1:

if (dest ) { /∗ trap ∗/ la = 32 + (src ≪ 1); result = (loc + 1) &^{#}ffff; risc state[17] &= ^{#}ebff; /∗ reset and ∗/

}

else { /∗ resume ∗/

if (src) { result = old src; risc state[17] |= ^{#}1800; /∗ set and ∗/

} else {

change = 0;

risc state[0] = loc;

dr = ^{#}400; la = 0; risc state[16] |= ^{#}10; /∗ set ∗/ nextra = ^{#}20;

} } break;

case 2: ⟨ Simulate the sideway add operation 64 ⟩;

break; default: result = source; /∗ if increment stack pointer by fetching data ∗/

break; }

}

This code is used in section 46.

64. ⟨ Simulate the sideway add operation 64 ⟩ ≡

{ k = ((source &^{#}aaaa) ≫ 1) + (source &^{#}5555); k = ((k &^{#}cccc) ≫ 2) + (k &^{#}3333); k = ((k &^{#}f0f0) ≫ 4) + (k &^{#}0f0f); result = ((k &^{#}ff00) ≫ 8) + (k &^{#}00ff);

}

This code is used in section 63.

65. ⟨ Simulate jump 65 ⟩ ≡

{ result = dest ? (loc + 1) &^{#}ffff : source; la = source;

}

This code is used in section 46.

66. ⟨ Bring simulation together properly 66 ⟩ ≡

{ if (dr ≡ 0) risc state[0] = la; if (change) {

if (dest < regs ) risc state[dest ] = result ;

if (dest ≡ 0) { dr = 0; la = result ;

} } risc state[16] |= nextra; risc state[17] |= dr ; risc state[20] = la; k = flags &^{#}10; /∗ old ∗/ risc state[17] |= (k ≪ 7) + (k ≪ 8); /∗ switch on and , if old ∗/

}

This code is used in section 46.

67. ⟨ Simulate input 67 ⟩ ≡

{

for (i = 0, k = ^{#}8000; ∗in vec ∧ i < 3; i^{++}, k ≫ 1) /∗ , , ∗/

risc state[17] = (risc state[17] & ∼k) | ((∗in vec^{++} − ) ? k : 0); for (i = 0, k = 1; ∗in vec ∧ i < 16; i^{++}, k ≪ 1) /∗ mem ∗/

risc state[21] = (risc state[21] & ∼k) | ((∗in vec^{++} − ) ? k : 0); for (i = 0, k = ^{#}40; ∗in vec ∧ i < 10; i^{++}, k ≪ 1) /∗ prog ∗/

risc state[16] = (risc state[16] & ∼k) | ((∗in vec^{++} − ) ? k : 0); for (i = 0, k = ^{#}20; ∗in vec ∧ i < 6; i^{++}) /∗ flags ∗/

risc state[16] = (risc state[16] & ∼k) | ((∗in vec^{++} − ) ? k : 0); for (i = 0, k = ^{#}1000; ∗in vec ∧ i < 1; i^{++}) /∗ ∗/

risc state[17] = (risc state[17] & ∼k) | ((∗in vec^{++} − ) ? k : 0); for (i = 0, k = ^{#}400; ∗in vec ∧ i < 1; i^{++}) /∗ ∗/

risc state[17] = (risc state[17] & ∼k) | ((∗in vec^{++} − ) ? k : 0); for (j = 0; j < regs ; j^{++}) /∗ regs ∗/

for (i = 0, k = 1; ∗in vec ∧ i < 16; i^{++}, k ≪ 1) /∗ mem ∗/

risc state[j] = (risc state[j] & ∼k) | ((∗in vec^{++} − ) ? k : 0); }

This code is used in section 46.

68. ⟨ Simulate output 68 ⟩ ≡

{

∗out vec^{++} = (risc state[17] &^{#}800) ?  : ;  /∗ ∗/
∗out vec^{++} = (risc state[16] &^{#}20) ?  : ;  /∗ ∗/
∗out vec^{++} = (risc state[17] &^{#}400) ?  : ;  /∗ dr ∗/

for (i = 0, k = 1; ∗in vec ∧ i < 16; i^{++}, k ≪ 1) /∗ da ∗/

∗out vec^{++} = (risc state[20] & k) ? : ;

∗out vec^{++} = (risc state[17] &^{#}200) ?  : ;  /∗ w ∗/
∗out vec^{++} = (risc state[17] &^{#}100) ?  : ;  /∗ dw ∗/

for (i = 0, k = 1; ∗in vec ∧ i < 16; i^{++}, k ≪ 1) /∗ wa ∗/

∗out vec^{++} = (risc state[19] & k) ? : ; for (i = 0, k = 1; ∗in vec ∧ i < 16; i^{++}, k ≪ 1) /∗ wd ∗/

∗out vec^{++} = (risc state[19] & k) ? : ; ∗out vec = 0; /∗ terminate the string ∗/

}

This code is used in section 46.

§69  GB GATES ELTE  RISC MANAGEMENT 39

69. RISC management. The run risc elte procedure takes a gate graph output by risc elte and simulates its behavior, given the contents of its memory. (See the demonstration program TAKE RISC ELTE, which appears in a module by itself, for a typical illustration of how run risc elte might be used.)

This procedure clears the simulated machine and begins executing the program that starts at address 0. It stops when it gets to an address greater than the size of memory supplied. One way to stop it is therefore to execute a command such as ^{#}0f00, which will transfer control to location ^{#}ffff; even better is ^{#}0f8f, which transfers to location ^{#}ffff without changing the status of and . However, if the given memory contains a full set of 2^{16} words, run risc elte will never stop.

When run risc elte does stop, it returns 0 and puts the final contents of the simulated registers into the global array risc state. Or, if g was not a decent graph, run risc elte returns a negative value and leaves risc state untouched. If g is Λ, the simulation goes in software. ⟨ The run risc elte routine 69 ⟩ ≡

long run risc elte(g, mem, size, trace regs )

Graph ∗g; /∗ graph output by risc elte ∗/ unsigned long mem[ ]; /∗ contents of memory; ∗/ unsigned long size; /∗ length of ram vector ∗/ unsigned long trace regs ; /∗ if nonzero, this many registers will be traced ∗/

{ register unsigned long la; /∗ load address ∗/ register unsigned long m; /∗ memory or register contents ∗/ unsigned long wd , wa; /∗ data and address to write ∗/ register Vertex ∗v; /∗ the current gate of interest ∗/ register Arc ∗a; /∗ the current output list element of interest ∗/ register long k, r; /∗ general-purpose indices ∗/ long i, p, x, s, n, c, ov , e, t, xr , w, dr , dw ; /∗ status bits ∗/ unsigned invalid ; /∗ invalid read or write ∗/ if (trace regs ) ⟨ Print a headline 72 ⟩ if (g) { r = gate eval (g, , Λ); /∗ reset the RISC by turning off the bit; ∗/

if (r < 0) return r; /∗ not a valid gate graph! ∗/ ⟨ Set up input bits appropriately 70 ⟩; ⟨ Dump the register contents into risc state 79 ⟩;

} else { simulate( , Λ);

risc state[17] |= ^{#}8000; } while (1) {

if (trace regs ) { if (g) ⟨ Dump the register contents into risc state 79 ⟩

⟨ Print and read from simplest memory 75 ⟩ } if (invalid ) break; /∗ stop if memory check occurs ∗/ if (w) ⟨ Write to simplest memory 78 ⟩ /∗ ∗/ if (invalid ) break; /∗ stop if memory check occurs ∗/ m = risc state[21]; if (g) { ⟨ Write m into the input gates 71 ⟩;

gate eval (g, Λ, Λ); /∗ do another RISC cycle; ∗/ } else simulate(Λ, Λ);

} if (trace regs ) ⟨ Print a footline 73 ⟩ if (g) ⟨ Dump the register contents into risc state 79 ⟩ return 0;

}

This code is used in section 7.

40  RISC MANAGEMENT  GB GATES ELTE §70

70. ⟨ Set up input bits appropriately 70 ⟩ ≡

g vertices val = 1;  /∗ turn the  bit on ∗/
(g vertices + 1) val = 0;  /∗ turn the  bit off ∗/
(g vertices + 2) val = 0;  /∗ turn the  bit off ∗/

This code is used in sections 69 and 81.

71. ⟨ Write m into the input gates 71 ⟩ ≡

for (v = g vertices + 3; v ≤ g vertices + 18; v^{++}, m ≫= 1) /∗ ∗/

v val = m & 1; /∗ store bits of memory word in the input gates ∗/

This code is used in sections 69, 82, 90, and 94.

72. If tracing is requested, we write on the standard output file. ⟨ Print a headline 72 ⟩ ≡

{ for (r = 0; r < trace regs ; r^{++}) printf ( ␣ ␣ , r); /∗ register names ∗/

  printf ( ␣  ␣    ␣    ␣      ␣␣  ␣␣      ␣␣  );

/∗ prog , extra, status and input bits, address, memory, w, wa, wd ; ∗/ }

This code is used in sections 69, 81, 82, 90, and 94.

73. ⟨ Print a footline 73 ⟩ ≡

printf (  ␣          ␣    ␣    ␣       ␣      ␣   ␣     ␣       ␣  , la, wa);

This code is used in sections 69, 82, 90, and 94.

74. ⟨ Print register contents 74 ⟩ ≡ for (r = 0; r < trace regs ; r^{++}) printf ( ␣ , risc state[r]); m = (risc state[16] ≫ 6) &^{#}3ff; /∗ prog ∗/ i = risc state[17] &^{#}4000; /∗ int bit ∗/ p = risc state[17] &^{#}2000; /∗ page bit ∗/ e = risc state[17] &^{#}1000; /∗ enabled ∗/ t = risc state[17] &^{#}800; /∗ translate ∗/ dr = risc state[17] &^{#}400; /∗ dr ∗/ w = risc state[17] &^{#}200; /∗ w ∗/ dw = risc state[17] &^{#}100; /∗ dw ∗/

x = risc state[16] &^{#}20;  /∗ extra  ∗/
xr = risc state[16] &^{#}10;  /∗ xresume  ∗/

s = risc state[16] & 8; /∗ sign ∗/ n = risc state[16] & 4; /∗ nonzero ∗/ c = risc state[16] & 2; /∗ carry ∗/ ov = risc state[16] & 1; /∗ overflow ∗/ la = risc state[20]; wa = risc state[19]; wd = risc state[18];

printf (  ␣        ␣        ␣       ␣ , m ≪ 2, x ?  : , xr ?  : , s ?  : ,
n ?  : , c ?  : , ov ?  : , e ?  : , i ?  : , p ?  : , t ?  : ,
dr ? : , la);

This code is used in sections 75, 85, 91, and 95.

75. ⟨ Print and read from simplest memory 75 ⟩ ≡

{ ⟨ Print register contents 74 ⟩; ⟨ Read from simplest memory 77 ⟩; if (invalid ) printf ( ); else printf ( , risc state[21]); ⟨ Print write data 76 ⟩;

}

This code is used in section 69.

76. ⟨ Print write data 76 ⟩ ≡ printf ( ␣ , w ? : ); if (w) printf ( ␣ , dw ? : , wa, wd ); else printf ( );

This code is used in sections 75, 85, 91, and 95.

77. Read from memory is very simple; more advanced versions later. ⟨ Read from simplest memory 77 ⟩ ≡

invalid = 1; la = risc state[20]; if (la < size) {

risc state[21] = mem[la];

invalid = 0; }

This code is used in section 75.

78. Write to memory is very simple; more advanced versions later. ⟨ Write to simplest memory 78 ⟩ ≡

invalid = 1; if (wa < size) mem[wa] = risc state[18]; invalid = 0; }

This code is used in section 69.

79. Here we peek inside the circuit to see what values are about to be latched. ⟨ Dump the register contents into risc state 79 ⟩ ≡

{ a = g outs ;

t = a tip val ;  /∗  ∗/
a = a next ;  /∗  ∗/
x = a tip val ;  /∗  ∗/
a = a next ;  /∗  ∗/
dr = a tip val ;  /∗  ∗/
a = a next ;  /∗  ∗/

for (la = 0, k = 0; k < 16; k^{++}, a = a next ) la = 2 ∗ la + a tip val ;

/∗ set la = load address; ∗/

w = a tip val ;  /∗  ∗/
a = a next ;  /∗  ∗/
dw = a tip val ;  /∗  ∗/
a = a next ;  /∗  ∗/

for (wa = 0, k = 0; k < 16; k^{++}, a = a next ) wa = 2 ∗ wa + a tip val ;

/∗ set wa = write memory address; ∗/ for (wd = 0, k = 0; k < 16; k^{++}, a = a next ) wd = 2 ∗ wd + a tip val ;

/∗ set wd = write data; ∗/ for (r = 0; r < 16; r^{++}) {

v = g vertices + (16 ∗ r + 52); /∗ most significant bit of register r ∗/ m = 0; if (v typ ≠ ) break; for (k = 0, m = 0; k < 16; k^{++}, v^{−}) m = 2 ∗ m + v alt val ; risc state[r] = m;

} for (k = 0, m = 0, v = g vertices + 28; k < 10; k^{++}, v^{−}) m = 2 ∗ m + v alt val ; /∗ prog ∗/

m = 2 ∗ m + x;  /∗ extra  ∗/
m = 2 ∗ m + (g vertices + 30) alt val ;  /∗ xresume  ∗/

m = 2 ∗ m + (g vertices + 31) alt val ; /∗ sign ∗/ m = 2 ∗ m + (g vertices + 32) alt val ; /∗ nonzero ∗/ m = 2 ∗ m + (g vertices + 33) alt val ; /∗ carry ∗/ m = 2 ∗ m + (g vertices + 34) alt val ; /∗ overflow ∗/ risc state[16] = m; /∗ program register and status bits go here; ∗/ m = g vertices val ; /∗ run bit ∗/ m = 2 ∗ m + (g vertices + 1) val ; /∗ int bit ∗/ m = 2 ∗ m + (g vertices + 2) val ; /∗ page bit ∗/ m = 2 ∗ m + (g vertices + 35) alt val ; /∗ enabled ∗/ m = (m ≪ 4) + (t ≪ 3) + (dr ≪ 2) + (w ≪ 1) + dw ;

risc state[17] &= ^{#}00f0;  /∗ save four bits  ∗/
risc state[17] |= (m ≪ 8) + (^{−}r);  /∗ input, output bits and number of regs go here;  ∗/
risc state[18] = wd ;  /∗ write data go here;  ∗/

risc state[19] = wa; /∗ write address go here, maybe this or ∗/ risc state[20] = la; /∗ this is the out-of-range address that caused termination; ∗/

}

This code is used in sections 69, 81, 82, 90, and 94.

80. ⟨ Global variables 80 ⟩ ≡ unsigned long risc state[64];

This code is used in section 7.

§81  GB GATES ELTE  MINIMAL RISC MANAGEMENT 43

81. Minimal RISC management. The min risc elte procedure takes a gate graph output by risc elte and simulates its behavior, given the contents of a sequence of memory blocks. (See the demonstration program MINIMAL RISC ELTE, which appears in a module by itself, for a typical illustration of how min risc elte might be used.)

This procedure set interrupt vector and execute a given number of steps. No separated data and program memory. Addresses above ^{#}ffe0 considered area of memory mapped i/o which is stored in the higher 32 words of the 64 word global array risc state. The bits of the highest address used switch off (if the bit is set) of memory blocks. Second highest address contains the interrupt flags and below this is the interrupt mask. This routine stops if and only if the given number of steps is done.

When min risc elte does stop, it returns 0 and puts the final contents of the simulated registers into the global array risc state. If g is Λ, the simulation goes in software.

Before using min risc elte, we have to use min risc elte reset to reset risc elte and the highest address of memory. ⟨ The risc elte reset routine 81 ⟩ ≡

long risc elte reset (g, trace regs )

Graph ∗g; /∗ graph output by risc elte ∗/

unsigned long trace regs ; /∗ this many registers will be traced ∗/ { register unsigned long la; /∗ load address ∗/

register unsigned long m; /∗ memory or register contents ∗/ unsigned long wd , wa; /∗ data and address to write ∗/ register Vertex ∗v; /∗ the current gate of interest ∗/ register Arc ∗a; /∗ the current output list element of interest ∗/ register long k, r; /∗ general-purpose indices ∗/ long i, p, x, s, n, c, ov , e, t, xr , w, dr , dw ; /∗ status bits ∗/ if (trace regs ) ⟨ Print a headline 72 ⟩ if (g) { r = gate eval (g, , Λ); /∗ reset the RISC by turning off the bit; ∗/

if (r < 0) return r; /∗ not a valid gate graph! ∗/

⟨ Set up input bits appropriately 70 ⟩;

⟨ Dump the register contents into risc state 79 ⟩; } else { simulate( , Λ);

risc state[17] |= ^{#}8000; } risc state[63] = 0; return 0;

}

This code is used in section 7.

44  MINIMAL RISC MANAGEMENT  GB GATES ELTE §82

82. ⟨ The min risc elte routine 82 ⟩ ≡

long min risc elte(g, mem, size, trace regs , intvec, steps )

Graph ∗g; /∗ graph output by risc elte ∗/ Memblock ∗ mem; /∗ memory ∗/ unsigned size; /∗ length of mem vector ∗/ unsigned trace regs ; /∗ this many registers will be traced ∗/ unsigned intvec; /∗ this goes to the interrupt vector ∗/ unsigned steps ; /∗ if nonzero, this many steps will be traced ∗/ { register unsigned long la; /∗ load address ∗/

register unsigned long m; /∗ memory or register contents ∗/ unsigned long wd , wa; /∗ data and address to write ∗/ register Vertex ∗v; /∗ the current gate of interest ∗/ register Arc ∗a; /∗ the current output list element of interest ∗/ register long k, r; /∗ general-purpose indices ∗/ long i, p, x, s, n, c, ov , e, t, xr , w, dr , dw ; /∗ status bits ∗/ unsigned memmask ; /∗ memory mask ∗/ char input [4] = ; risc state[62] = intvec &^{#}ffff; if (risc state[62] & risc state[61]) input [1] = ; if (trace regs ) ⟨ Print a headline 72 ⟩ while (1) {

memmask = risc state[63];

if (trace regs ) { if (g) ⟨ Dump the register contents into risc state 79 ⟩ ⟨ Print and read from von Neumann memory 85 ⟩

}

if (w) ⟨ Write to von Neumann memory 88 ⟩ /∗ ∗/ if (∼step^{−}) break; m = risc state[21]; if (g) {

⟨ Write m into the input gates 71 ⟩;

gate eval (g, input , Λ); /∗ do another RISC cycle; ∗/ } else simulate(input , Λ);

} if (trace regs ) ⟨ Print a footline 73 ⟩ if (g) ⟨ Dump the register contents into risc state 79 ⟩ return 0;

}

This code is used in section 7.

83. Each Memblock has four standard fields; hence it occupies 16 bytes on most systems, not counting the memory needed for memry arrays. ⟨ Type declarations 83 ⟩ ≡

typedef struct memblock struct { unsigned ∗memry ; /∗ a pointer to an array of memory words; ∗/ unsigned long start ; /∗ first physical address in the simulated masine; ∗/ unsigned long size; /∗ size in words of the simulated masine; ∗/ unsigned type; /∗ zero for ram and nonzero for rom. ∗/

} Memblock;

This code is used in sections 2, 7, and 84.

84. ⟨ 1 ⟩ +≡ ⟨ Type declarations 83 ⟩

85. ⟨ Print and read from von Neumann memory 85 ⟩ ≡

{ ⟨ Print register contents 74 ⟩; ⟨ Read from von Neumann memory 86 ⟩; printf ( , risc state[21]); ⟨ Print write data 76 ⟩;

}

This code is used in section 82.

86. We read from the first Memblock which is not masked out. The first is memory mapped i/o. ⟨ Read from von Neumann memory 86 ⟩ ≡

{ long unsigned a; a = risc state[20]; /∗ la ∗/ risc state[21] = ^{#}fedcba98; /∗ junk result ∗/ if (a ≥ ^{#}ffe0_{L} ∧ risc state[17] &^{#}400) /∗ dr from i/o ∗/

risc state[21] = risc state[la −^{#}fffc]; else ⟨ Read from mem array 87 ⟩

}

This code is used in section 85.

87. ⟨ Read from mem array 87 ⟩ ≡

{ unsigned j; for (j = 0; j < size; j^{++}) {

if ((memmask ≫ j) & 1) continue; if (a < mem[j].start ) continue; k = a − mem[j].start ; if (k ≥ mem[j].size) continue; risc state[21] = mem[j].memry [k]; break;

} }

This code is used in sections 86, 92, and 96.

88. We write to each Memblock which is not masked out and not a rom. The first is memory mapped i/o. ⟨ Write to von Neumann memory 88 ⟩ ≡

{ long unsigned a; a = risc state[19]; if (a ≥ ^{#}ffe0_{L}) risc state[a −^{#}fffc_{L}] = risc state[18]; ⟨ Write to mem array 89 ⟩;

}

This code is used in section 82.

89. ⟨ Write to mem array 89 ⟩ ≡

{ unsigned j; for (j = 0; j < mems ; j^{++}) {

if ((memmask ≫ j) & 1) continue; if (a < mem[j].start ) continue; k = a − mem[j].start ; if (k ≥ mem[j].size) continue; if (mem[j].type) continue; mem[j].memry [k] = risc state[18];

} }

This code is used in sections 88, 93, and 97.

§90  GB GATES ELTE  SMALL RISC MANAGEMENT 47

90. Small RISC management. The small risc elte procedure takes a gate graph output by risc elte and simulates its behavior, given the contents of a sequence of memory blocks. (See the demonstration program SMALL RISC ELTE, which appears in a module by itself, for a typical illustration of how small risc elte might be used.)

This procedure set interrupt vector and execute a given number of steps. There is a separated data and program memory. Addresses above ^{#}1ffe0 considered area of memory mapped i/o and this data is stored in the higher 32 words of the 64 word global array risc state. The bits of the highest address used to switch off (if the bit is set) of memory blocks. Second highest address contains the interrupt flags and below this is the interrupt mask. This routine stops if and only if the given number of steps is done.

When small risc elte does stop, it returns 0 and puts the final contents of the simulated registers into the global array risc state. If g is Λ, the simulation goes in software.

Before using small risc elte, we have to use risc elte reset to reset risc elte and the highest address of memory. ⟨ The small risc elte routine 90 ⟩ ≡

long small risc elte(g, mem, size, trace regs , intvec, steps )

Graph ∗g; /∗ graph output by risc elte ∗/

Memblock mem[ ]; /∗ contents of memory ∗/

unsigned size; /∗ length of mem vector ∗/

unsigned trace regs ; /∗ if nonzero, this many registers will be traced ∗/ unsigned intvec; /∗ this goes to the interrupt vector ∗/ unsigned steps ; /∗ if nonzero, this many steps will be traced ∗/

{ register unsigned long la; /∗ load address ∗/ register unsigned long m; /∗ memory or register contents ∗/ unsigned long wd , wa; /∗ data and address to write ∗/ register Vertex ∗v; /∗ the current gate of interest ∗/ register Arc ∗a; /∗ the current output list element of interest ∗/ register long k, r; /∗ general-purpose indices ∗/ long i, p, x, s, n, c, ov , e, t, xr , w, dr , dw ; /∗ status bits ∗/ unsigned memmask ; /∗ memory mask ∗/ char input [4] = ; risc state[62] = intvec &^{#}ffff; if (risc state[62] & risc state[61]) input [1] = ; if (trace regs ) ⟨ Print a headline 72 ⟩ while (1) {

memmask = risc state[63];

if (trace regs ) { if (g) ⟨ Dump the register contents into risc state 79 ⟩ ⟨ Print and read from Harvard memory 91 ⟩

}

if (w) ⟨ Write to Harvard memory 93 ⟩ /∗ ∗/

if (∼step^{−}) break;

m = risc state[21];

if (g) { ⟨ Write m into the input gates 71 ⟩;

gate eval (g, input , Λ); /∗ do another RISC cycle; ∗/ } else simulate(input , Λ);

} if (trace regs ) ⟨ Print a footline 73 ⟩ if (g) ⟨ Dump the register contents into risc state 79 ⟩; return 0;

}

This code is used in section 7.

48  SMALL RISC MANAGEMENT  GB GATES ELTE §91

91. ⟨ Print and read from Harvard memory 91 ⟩ ≡

{ ⟨ Print register contents 74 ⟩; ⟨ Read from Harvard memory 92 ⟩; printf ( , risc state[21]); ⟨ Print write data 76 ⟩;

}

This code is used in section 90.

92. ⟨ Read from Harvard memory 92 ⟩ ≡

{ long unsigned a; a = (risc state[17] &^{#}400) ≠ 0; /∗ dr ∗/ a = (a ≪ 16) + risc state[20]; risc state[21] = ^{#}fedcba98; /∗ junk result ∗/ if (a ≤ ^{#}1ffff_{L} ∧ a ≥ ^{#}1ffe0_{L}) risc state[21] = risc state[a −^{#}1fffc_{L}]; else ⟨ Read from mem array 87 ⟩

}

This code is used in section 91.

93. ⟨ Write to Harvard memory 93 ⟩ ≡

{ long unsigned a; a = (risc state[17] &^{#}100) ≠ 0; /∗ dw ∗/ a = (a ≪ 16) + risc state[19]; if (a ≤ ^{#}1ffff_{L} ∧ a ≥ ^{#}1ffe0_{L}) risc state[a −^{#}1fffc_{L}] = risc state[18]; ⟨ Write to mem array 89 ⟩;

}

This code is used in section 90.

§94  GB GATES ELTE  LARGE RISC MANAGEMENT 49

94. Large RISC management. The large risc elte procedure takes a gate graph output by risc elte and simulates its behavior, given the contents of a sequence of memory blocks. (See the demonstration program LARGE RISC ELTE, which appears in a module by itself, for a typical illustration of how small risc elte might be used.)

This procedure set interrupt vector and execute a given number of steps. There is a separated data and program memory. Addresses between ^{#}1ffe0 and ^{#}1ffff, incusively considered area of memory mapped i/o and this data is stored in the higher 32 words of the 64 word global array risc state. The bits of the highest address used for pageing (two least and three most significant bits) and to switch off (if the bit is set) of memory blocks. Second highest address contains the interrupt flags and below this is the interrupt mask. This routine stops if and only if the given number of steps is done.

When large risc elte does stop, it returns 0 and puts the final contents of the simulated registers into the global array risc state. If g is Λ, the simulation goes in software.

Before using large risc elte, we have to use risc elte reset to reset risc elte and the highest address of i/o. ⟨ The large risc elte routine 94 ⟩ ≡

long large risc elte(g, mem, size, trace regs , intvec, steps )

Graph ∗g; /∗ graph output by risc elte ∗/ Memblock mem[ ]; /∗ contents of memory; ∗/ unsigned size; /∗ length of mem vector ∗/ unsigned trace regs ; /∗ if nonzero, this many registers will be traced ∗/ unsigned intvec; /∗ this goes to the interrupt vector ∗/ unsigned steps ; /∗ if nonzero, this many steps will be traced ∗/

{ register unsigned long la; /∗ load address ∗/ register unsigned long m; /∗ memory or register contents ∗/ unsigned long wd , wa; /∗ data and address to write ∗/ register Vertex ∗v; /∗ the current gate of interest ∗/ register Arc ∗a; /∗ the current output list element of interest ∗/ register long k, r; /∗ general-purpose indices ∗/ long i, p, x, s, n, c, ov , e, t, xr , w, dr , dw ; /∗ status bits ∗/ unsigned memmask ; /∗ memory mask ∗/ char input [4] = ; risc state[62] = intvec &^{#}ffff; if (risc state[62] & risc state[61]) input [1] = ; if (trace regs ) ⟨ Print a headline 72 ⟩ while (1) { memmask = risc state[63] ≫ 2;

if (trace regs ) { if (g) ⟨ Dump the register contents into risc state 79 ⟩

⟨ Print and read from paged memory 95 ⟩ } if (w) ⟨ Write to paged memory 97 ⟩ /∗ ∗/ k = (risc state[16] &^{#}20) + (∼((risc state[17] &^{#}400) ≫ 6) &^{#}10); /∗ old bits ∗/ risc state[17] = (risc state[17] &^{#}30) | k; /∗ saved ∗/ if (step^{−} ≡ 0) break; m = risc state[21]; if (g) { ⟨ Write m into the input gates 71 ⟩;

gate eval (g, input , Λ); /∗ do another RISC cycle; ∗/ } else simulate(input , Λ);

} if (trace regs ) ⟨ Print a footline 73 ⟩ if (g) ⟨ Dump the register contents into risc state 79 ⟩ return 0;

}

This code is used in section 7.

50  LARGE RISC MANAGEMENT  GB GATES ELTE §95

95. ⟨ Print and read from paged memory 95 ⟩ ≡

{ ⟨ Print register contents 74 ⟩; ⟨ Read from paged memory 96 ⟩; printf ( , risc state[21]); ⟨ Print write data 76 ⟩;

}

This code is used in section 94.

96. ⟨ Read from paged memory 96 ⟩ ≡

{ long unsigned a; a = (risc state[17] &^{#}400) ≠ 0; a = (a ≪ 16) + risc state[20]; p = 1; /∗ page bit ∗/ if (risc state[17] &^{#}800 ∨ risc state[63] & 2) { /∗ if translate ∗/

k = a ≫ 13; /∗ page table address ∗/

a = a &^{#}1fff; /∗ offset ∗/

k = risc state[32 + k]; /∗ page table entry ∗/

a += k ≫ 2; /∗ physical address ∗/

if (k & 2) p = 0; /∗ allowed to read ∗/ } risc state[21] = ^{#}fedcba98; /∗ junk result ∗/ if (p) {

risc state[60] = risc state[20];

k = (risc state[16] &^{#}20) + (∼((risc state[17] &^{#}400) ≫ 6) &^{#}10);

/∗ and the complement of ∗/ risc state[63] = (risc state[63] &^{#}1fff) | (k ≪ 9);

} else if (a ≤ ^{#}1ffff_{L} ∧ a ≥ ^{#}1ffe0_{L}) risc state[21] = risc state[a −^{#}1fffc_{L}]; else ⟨ Read from mem array 87 ⟩

}

This code is used in section 95.

97. ⟨ Write to paged memory 97 ⟩ ≡

{ long unsigned a; a = (risc state[17] &^{#}100) ≠ 0; /∗ dw ∗/ a = (a ≪ 16) + risc state[19]; p = 1; /∗ page bit ∗/ if (risc state[17] &^{#}800 ∨ risc state[63] & 1) { /∗ if translate ∗/

k = a ≫ 13; /∗ page table address ∗/

a = a &^{#}1fff; /∗ offset ∗/

k = risc state[32 + k]; /∗ page table entry ∗/

a += k ≫ 2; /∗ physical address ∗/

if (k & 1) p = 0; /∗ allowed to write ∗/ } if (p) {

risc state[60] = risc state[19];

k = ^{#}40 + risc state[17] &^{#}30; /∗ old and the complement of old ∗/ risc state[63] = (risc state[63] &^{#}1fff) | (k ≪ 9);

} else {

if (a ≤ ^{#}1ffff_{L} ∧ addr ≥ ^{#}1ffe0_{L}) risc state[a −^{#}1fffc_{L}] = risc state[18]; ⟨ Write to mem array 89 ⟩;

} }

This code is used in section 94.

52  GENERALIZED GATE GRAPHS  GB GATES ELTE §98

98. Generalized gate graphs. For intermediate computations, it is convenient to allow two additional types of gates:

denotes a constant gate of value z.I. denotes a copy of a previous gate; utility field alt points to that previous gate.

Such gates might appear anywhere in the graph, possibly interspersed with the inputs and latches.

Here is a simple subroutine that prints a symbolic representation of a generalized gate graph on the standard output file: #define bit z.I /∗ field containing the constant value of a gate ∗/ #define print gates p gates /∗ abbreviation makes chopped-off name unique ∗/ ⟨ The print gates routine 98 ⟩ ≡

static void pr gate(v)

Vertex ∗v; { register Arc ∗a;

printf ( ␣ ␣ , v name); switch (v typ) {

case  : printf (  ); break;
case  : printf (  );

if (v alt ) printf ( ␣ , v alt name);

break; case : printf ( ␣ ); break; case : printf ( ␣ , v bit );

break; case : printf ( ␣ ␣ , v alt name); } for (a = v arcs ; a; a = a next ) {

if (a ≠ v arcs ) printf ( ␣ ␣ , (char) v typ);

printf (a tip name); } printf ( );

} void print gates (g)

Graph ∗g; { register Vertex ∗v;

register Arc ∗a; for (v = g vertices ; v < g vertices + g n; v^{++}) pr gate(v); for (a = g outs ; a; a = a next )

if (is boolean(a tip)) printf (  ␣  , the boolean(a tip));
else printf (  ␣  , a tip name);

}

This code is used in section 7.

§100  GB GATES ELTE  GENERALIZED GATE GRAPHS 53

99. ⟨ 1 ⟩ +≡ #define bit z.I 100. The reduce routine takes a generalized graph g and uses the identities \overline{\overline{x}} = x and

\begin{matrix}x ∧ 0 = & 0, & x ∧ 1 = & x, & x ∧ x = & x, & x ∧ \overline{x} = & 0, \\ x ∨ 0 = & x, & x ∨ 1 = & 1, & x ∨ x = & x, & x ∨ \overline{x} = & 1, \\ x ⊕ 0 = & x, & x ⊕ 1 = & \overline{x}, & x ⊕ x = & 0, & x ⊕ \overline{x} = & 1, \end{matrix}

to create an equivalent graph having no  or  or obviously redundant gates. The reduced graph also

excludes any gates that are not used directly or indirectly in the computation of the output values. ⟨ Internal subroutines 11 ⟩ +≡

static Graph ∗reduce(g)

Graph ∗g; { register Vertex ∗u, ∗v; /∗ the current vertices of interest ∗/

register Arc ∗a, ∗b; /∗ the current arcs of interest ∗/ Arc ∗aa, ∗bb; /∗ their predecessors ∗/ Vertex ∗latch ptr ; /∗ top of the latch list ∗/ long n = 0; /∗ the number of marked gates ∗/ Graph ∗new graph; /∗ the reduced gate graph ∗/ Vertex ∗next vert = Λ, ∗max next vert = Λ; /∗ allocation of new vertices ∗/ Arc ∗avail arc = Λ; /∗ list of recycled arcs ∗/ Vertex ∗sentinel ; /∗ end of the vertices ∗/ if (g ≡ Λ) panic(missing operand ); /∗ where is g? ∗/ sentinel = g vertices + g n; while (1) {

latch ptr = Λ;

for (v = g vertices ; v < sentinel ; v^{++}) ⟨ Reduce gate v, if possible, or put it on the latch list 102 ⟩; ⟨ Check to see if any latch has become constant; if not, break 101 ⟩;

} ⟨ Mark all gates that are used in some output 109 ⟩; ⟨ Copy all marked gates to a new graph 111 ⟩; gb recycle(g); return new graph;

}

101. We will link latches together via their v.V fields. ⟨ Check to see if any latch has become constant; if not, break 101 ⟩ ≡

{ char no constants yet = 1;

for (v = latch ptr ; v; v = v v.V) { u = v alt ; /∗ the gate whose value will be latched ∗/ if (u typ ≡ ) v alt = u alt ; else if (u typ ≡ ) {

v typ = ; v bit = u bit ; no constants yet = 0; }

} if (no constants yet ) break;

}

This code is used in section 100.

102. #define foo x.V /∗ link field used to find all the gates later ∗/ ⟨ Reduce gate v, if possible, or put it on the latch list 102 ⟩ ≡

{ switch (v typ) { case : v v.V = latch ptr ; latch ptr = v; break; case : case : break; case : u = v alt ;

if (u typ ≡ ) v alt = u alt ; else if (u typ ≡ ) {

v bit = u bit ; goto make v constant ; } break;

case : ⟨ Try to reduce an inverter, then goto done 103 ⟩; case : ⟨ Try to reduce an AND gate 104 ⟩; goto test single arg ; case : ⟨ Try to reduce an OR gate 105 ⟩; goto test single arg ; case : ⟨ Try to reduce an EXCLUSIVE-OR gate 106 ⟩; test single arg :

if (v arcs next ) break;

v alt = v arcs tip; make v eq : v typ = ; goto make v arcless ; make v 1 : v bit = 1; goto make v constant ; make v 0 : v bit = 0; make v constant : v typ = ; make v arcless : v arcs = Λ; } v bar = Λ; /∗ this field will point to the complement, if computed later ∗/

done: v foo = v + 1; /∗ this field will link all the vertices together ∗/ }

This code is used in section 100.

103. ⟨ Try to reduce an inverter, then goto done 103 ⟩ ≡ u = v arcs tip; if (u typ ≡ ) u = v arcs tip = u alt ; if (u typ ≡ ) {

v bit = 1 − u bit ; goto make v constant ; } else if (u bar ) { /∗ this inverse already computed ∗/

v alt = u bar ; goto make v eq ; } else {

u bar = v; v bar = u; goto done; }

This code is used in section 102.

104. ⟨ Try to reduce an AND gate 104 ⟩ ≡

for (a = v arcs , aa = Λ; a; a = a next ) { u = a tip; if (u typ ≡ ) u = a tip = u alt ; if (u typ ≡ ) {

if (u bit ≡ 0) goto make v 0 ; goto bypass and ;

} else for (b = v arcs ; b ≠ a; b = b next ) { if (b tip ≡ u) goto bypass and ; if (b tip ≡ u bar ) goto make v 0 ;

} aa = a; continue;

bypass and :

if (aa) aa next = a next ; else v arcs = a next ;

} if (v arcs ≡ Λ) goto make v 1 ;

This code is used in section 102.

105. ⟨ Try to reduce an OR gate 105 ⟩ ≡

for (a = v arcs , aa = Λ; a; a = a next ) { u = a tip; if (u typ ≡ ) u = a tip = u alt ; if (u typ ≡ ) {

if (u bit ) goto make v 1 ; goto bypass or ;

} else for (b = v arcs ; b ≠ a; b = b next ) { if (b tip ≡ u) goto bypass or ; if (b tip ≡ u bar ) goto make v 1 ;

} aa = a; continue;

bypass or :

if (aa) aa next = a next ; else v arcs = a next ;

} if (v arcs ≡ Λ) goto make v 0 ;

This code is used in section 102.

106. ⟨ Try to reduce an EXCLUSIVE-OR gate 106 ⟩ ≡

{ long cmp = 0;

for (a = v arcs , aa = Λ; a; a = a next ) { u = a tip; if (u typ ≡ ) u = a tip = u alt ; if (u typ ≡ ) {

if (u bit ) cmp = 1 − cmp;

goto bypass xor ; } else for (bb = Λ, b = v arcs ; b ≠ a; b = b next ) {

if (b tip ≡ u) goto double bypass ; if (b tip ≡ u bar ) { cmp = 1 − cmp; goto double bypass ;

}

bb = b; continue; double bypass :

if (bb) bb next = b next ; else v arcs = b next ; goto bypass xor ;

} aa = a; continue;

bypass xor :

if (aa) aa next = a next ; else v arcs = a next ; a a.A = avail arc; avail arc = a;

} if (v arcs ≡ Λ) {

v bit = cmp; goto make v constant ;

} if (cmp) ⟨ Complement one argument of v 107 ⟩;

}

This code is used in section 102.

107. ⟨ Complement one argument of v 107 ⟩ ≡

{

for (a = v arcs ; ; a = a next ) { u = a tip; if (u bar ) break; /∗ good, the complement is already known ∗/ if (a next ≡ Λ) { /∗ oops, this is our last chance ∗/

⟨ Create a new vertex for complement of u 108 ⟩; break;

} } a tip = u bar ;

}

This code is used in section 106.

108. Here we’ve come to a subtle point: If a lot of gates involve an input that is set to the constant value 1, the “reduced” graph might actually be larger than the original, in the sense of having more vertices (although fewer arcs). Therefore we must have the ability to allocate new vertices during the reduction phase of reduce. At least one arc has been added to the avail arc list whenever we reach this portion of the program. ⟨ Create a new vertex for complement of u 108 ⟩ ≡

if (next vert ≡ max next vert ) { next vert = gb typed alloc(7, Vertex, g aux data); if (next vert ≡ Λ) {

gb recycle(g);

panic(no room + 1); /∗ can’t get auxiliary storage! ∗/ } max next vert = next vert + 7;

} next vert typ = ; sprintf (name buf , , u name); next vert name = gb save string (name buf ); next vert arcs = avail arc; /∗ this is known to be non-Λ ∗/ avail arc tip = u; avail arc = avail arc a.A; next vert arcs next = Λ; next vert bar = u; next vert foo = u foo; u foo = u bar = next vert^{++};

This code is used in section 107.

109. During the marking phase, we will use the w.V field to link the list of nodes-to-be-marked. That field will turn out to be non-Λ only in the marked nodes. (We no longer use its former meaning related to complementation, so we call it lnk instead of bar .) #define lnk w.V /∗ stack link for marking ∗/ ⟨ Mark all gates that are used in some output 109 ⟩ ≡

{ for (v = g vertices ; v ≠ sentinel ; v = v foo) v lnk = Λ; for (a = g outs ; a; a = a next ) {

v = a tip;

if (is boolean(v)) continue;

if (v typ ≡ ) v = a tip = v alt ;

if (v typ ≡ ) { /∗ this output is constant, so make it boolean ∗/ a tip = (Vertex ∗) v bit ; continue;

}

⟨ Mark all gates that are used to compute v 110 ⟩; }

}

This code is used in section 100.

110. ⟨ Mark all gates that are used to compute v 110 ⟩ ≡

if (v lnk ≡ Λ) { v lnk = sentinel ; /∗ v now represents the top of the stack of nodes to be marked ∗/ do {

n^{++}; b = v arcs ; if (v typ ≡ ) {

u = v alt ; /∗ latch vertices have a “hidden” dependency ∗/ if (u < v) n^{++}; /∗ latched input value will get a special gate ∗/ if (u lnk ≡ Λ) {

u lnk = v lnk ; v = u;

} else v = v lnk ; } else v = v lnk ; for ( ; b; b = b next ) {

u = b tip; if (u lnk ≡ Λ) {

u lnk = v;

v = u; }

} } while (v ≠ sentinel );

}

This code is used in section 109.

111. It is easier to copy a directed acyclic graph than to copy a general graph, but we do have to contend with the feedback in latches. #define reverse arc list (alist )

{ for (aa = alist , b = Λ; aa; b = aa, aa = a) { a = aa next ;

aa next = b;

}

alist = b; }

⟨ Copy all marked gates to a new graph 111 ⟩ ≡ new graph = gb new graph(n); if (new graph ≡ Λ) {

gb recycle(g);

panic(no room + 2); /∗ out of memory ∗/ } strcpy (new graph id , g id ); strcpy (new graph util types , ); next vert = new graph vertices ; for (v = g vertices , latch ptr = Λ; v ≠ sentinel ; v = v foo) {

if (v lnk ) { /∗ yes, v is marked ∗/ u = v lnk = next vert^{++}; /∗ make note of where we’ve copied it ∗/ ⟨ Make u a copy of v; put it on the latch list if it’s a latch 112 ⟩;

} } ⟨ Fix up the alt fields of the newly copied latches 113 ⟩; reverse arc list (g outs ); for (a = g outs ; a; a = a next ) {

b = gb virgin arc( );

b tip = is boolean(a tip) ? a tip : a tip lnk ; b next = new graph outs ; new graph outs = b;

}

This code is used in section 100.

112. ⟨ Make u a copy of v; put it on the latch list if it’s a latch 112 ⟩ ≡ u name = gb save string (v name); u typ = v typ; if (v typ ≡ ) {

u alt = latch ptr ; latch ptr = v; } reverse arc list (v arcs ); for (a = v arcs ; a; a = a next ) gb new arc(u, a tip lnk , a len);

This code is used in section 111.

113. ⟨ Fix up the alt fields of the newly copied latches 113 ⟩ ≡

while (latch ptr ) { u = latch ptr lnk ; /∗ the copy of a latch ∗/ v = u alt ; u alt = latch ptr alt lnk ; latch ptr = v; if (u alt < u) ⟨ Replace u alt by a new gate that copies an input 114 ⟩;

}

This code is used in section 111.

114. Suppose we had a latch whose value was originally the AND of two inputs, where one of those inputs has now been set to 1. Then the latch should still refer to a subsequent gate, equal to the value of the other input on the previous cycle. We create such a gate here, making it an OR of two identical inputs. We do this because we’re not supposed to leave any in the result of reduce, and because every OR is supposed to have at least two inputs. ⟨ Replace u alt by a new gate that copies an input 114 ⟩ ≡

{ v = u alt ; /∗ the input gate that should be copied for latching ∗/ u alt = next vert^{++}; sprintf (name buf , , v name, u name); u = u alt ; u name = gb save string (name buf ); u typ = ; gb new arc(u, v, ); gb new arc(u, v, );

}

This code is used in section 113.

§115  GB GATES ELTE  PARALLEL MULTIPLICATION 61

115. Parallel multiplication. Now comes the prod routine, which constructs a rather different network of gates, based this time on a divide-and-conquer paradigm. Let’s take a breather before we tackle it.

(Deep breath.)

The subroutine call prod (m, n) creates a network for the binary multiplication of unsigned m-bit numbers by n-bit numbers, assuming that m ≥ 2 and n ≥ 2. There is no upper limit on the sizes of m and n, except of course the limits imposed by the size of memory in which this routine is run.

The overall strategy used by prod is to start with a generalized gate graph for multiplication in which many of the gates are identically zero or copies of other gates. Then the reduce routine will perform local optimizations leading to the desired result. Since there are no latches, some of the complexities of the general reduce routine are avoided.

All of the , , and gates of the network returned by prod have exactly two inputs. The depth of the circuit (i.e., the length of its longest path) is 3 log m/log 1.5+log(m+n)/log ϕ+O(1), where ϕ = (1+\sqrt{5} )/2 is the golden ratio. The grand total number of gates is 6mn + 5m^{2} + O((m + n) log(m + n)).

There is a demonstration program called MULTIPLY that uses prod to compute products of large integers. ⟨ The prod routine 115 ⟩ ≡

Graph ∗prod (m, n)

unsigned long m, n; /∗ lengths of the binary numbers to be multiplied ∗/ { ⟨ Local variables for prod 117 ⟩

if (m < 2) m = 2; if (n < 2) n = 2; ⟨ Allocate space for a temporary graph g and for auxiliary tables 116 ⟩; ⟨ Fill g with generalized gates that do parallel multiplication 119 ⟩; if (gb trouble code) {

gb recycle(g); panic(alloc fault ); /∗ too big ∗/ } g = reduce(g); return g; /∗ if g ≡ Λ, the panic code was set by reduce ∗/

}

This code is used in section 7.

62  PARALLEL MULTIPLICATION  GB GATES ELTE §116

116. The divide-and-conquer recurrences used in this network lead to interesting patterns. First we use a method for parallel column addition that reduces the sum of three numbers to the sum of two numbers. Repeated use of this reduction makes it possible to reduce the sum of m numbers to a sum of just two numbers, with a total circuit depth that satisfies the recurrence T (3N) = T (2N) + O(1). Then when the result has been reduced to a sum of two numbers, we use a parallel addition scheme based on recursively “golden sectioning the data”; in other words, the recursion partitions the data into two parts such that the ratio of the larger part to the smaller part is approximately ϕ. This technique proves to be slightly better than a binary partition would be, both asymptotically and for small values of m + n.

We define flog N, the Fibonacci logarithm of N, to be the smallest nonnegative integer k such that N ≤ F_{k+1}. Let N = m + n. Our parallel adder for two numbers of N bits will turn out to have depth at most 2+flog N. The unreduced graph g in our circuit for multiplication will have fewer than (6m+3 flog N)N gates. ⟨ Allocate space for a temporary graph g and for auxiliary tables 116 ⟩ ≡

m plus n = m + n; ⟨ Compute f = flog(m + n) 118 ⟩; g = gb new graph((6 ∗ m − 7 + 3 ∗ f) ∗ m plus n); if (g ≡ Λ) panic(no room); /∗ out of memory before we’re even started ∗/ sprintf (g id , , m, n); strcpy (g util types , ); long tables = gb typed alloc(2 ∗ m plus n + f, long, g aux data); vert tables = gb typed alloc(f ∗ m plus n, Vertex ∗, g aux data); if (gb trouble code) {

gb recycle(g);

panic(no room + 1); /∗ out of memory trying to create auxiliary tables ∗/ }

This code is used in section 115.

117. ⟨ Local variables for prod 117 ⟩ ≡ unsigned long m plus n; /∗ guess what this variable holds ∗/ long f; /∗ initially flog(m + n), later flog of other things ∗/ Graph ∗g; /∗ graph of generalized gates, to be reduced eventually ∗/ long ∗long tables ; /∗ beginning of auxiliary array of long numbers ∗/ Vertex ∗∗vert tables ; /∗ beginning of auxiliary array of gate pointers ∗/

See also sections 120 and 126. This code is used in section 115.

118. ⟨ Compute f = flog(m + n) 118 ⟩ ≡ f = 4; j = 3; k = 5; /∗ j = F_{f}, k = F_{f+1} ∗/ while (k < m plus n) {

k = k + j;

j = k − j;

f^{++}; }

This code is used in section 116.

119. The well-known formulas for a “full adder,”

x + y + z = s + 2c, where s = x ⊕ y ⊕ z and c = xy ∨ yz ∨ zx,

can be applied to each bit of an N-bit number, thereby providing us with a way to reduce the sum of three numbers to the sum of two.

The input gates of our network will be called x_{0}, x_{1}, …, x_{m−1}, y_{0}, y_{1}, …, y_{n−1}, and the outputs will be called z_{0}, z_{1}, …, z_{m+n−1}. The logic of the prod network will compute

(z_{m+n−1} … z_{1}z_{0})_{2} = (x_{m−1} … x_{1}x_{0})_{2} · (y_{n−1} … y_{1}y_{0})_{2} ,

by first considering the product to be the m-fold sum A_{0} + A_{1} + ⋯ + A_{m−1}, where

A_{j} = 2^{j}x_{j} · (y_{n−1} … y_{1}y_{0})_{2} , 0 ≤ j < m.

Then the three-to-two rule for addition is used to define further numbers A_{m}, A_{m+1}, …, A_{3m−5} by the scheme

A_{m+2j} + A_{m+2j+1} = A_{3j} + A_{3j+1} + A_{3j+2} , 0 ≤ j ≤ m − 3.

[A similar but slightly less efficient scheme was used by Pratt and Stockmeyer in Journal of Computer and System Sciences 12 (1976), Proposition 5.3. The recurrence used here is related to the Josephus problem with step-size 3; see Concrete Mathematics, §3.3.] For this purpose, we compute intermediate results P_{j}, Q_{j}, and R_{j} by the rules

\begin{aligned}P_{j} & = A_{3j} ⊕ A_{3j+1} ; \\ Q_{j} & = A_{3j} ∧ A_{3j+1} ; \\ A_{m+2j} & = P_{j} ⊕ A_{3j+2} ; \\ R_{j} & = P_{j} ∧ A_{3j+2} ; \\ A_{m+2j+1} & = 2(Q_{j} ∨ R_{j}) . \end{aligned}

Finally we let

\begin{aligned}U & = A_{3m−6} ⊕ A_{3m−5} , \\ V & = A_{3m−6} ∧ A_{3m−5} ; \end{aligned}

these are the values that would be P_{m−2} and Q_{m−2} if the previous formulas were allowed to run past j = m − 3. The final result Z = (z_{m+n−1} … z_{1}z_{0})_{2} can now be expressed as

Z = U + 2V .

The gates of the first part of the network are conveniently obtained in groups of N = m + n, representing the bits of the quantities A_{j}, P_{j}, Q_{j}, R_{j}, U, and V. We will put the least significant bit of A_{j} in gate position g vertices + a(j) ∗ N, where a(j) = j + 1 for 0 ≤ j < m and a(m + 2j + t) = m + 5j + 3 + 2t for 0 ≤ j ≤ m − 3, 0 ≤ t ≤ 1. ⟨ Fill g with generalized gates that do parallel multiplication 119 ⟩ ≡

next vert = g vertices ;

start prefix ( ); x = first of (m, );

start prefix ( ); y = first of (n, );

⟨ Define A_{j} for 0 ≤ j < m 121 ⟩;

⟨ Define P_{j}, Q_{j}, A_{m+2j}, R_{j}, and A_{m+2j+1} for 0 ≤ j ≤ m − 3 122 ⟩;

⟨ Define U and V 123 ⟩;

⟨ Compute the final result Z by parallel addition 124 ⟩;

This code is used in section 115.

120. ⟨ Local variables for prod 117 ⟩ +≡ register long i, j, k, l; /∗ all-purpose indices ∗/ register Vertex ∗v; /∗ current vertex of interest ∗/ Vertex ∗x, ∗y; /∗ least-significant bits of the input gates ∗/ Vertex ∗alpha, ∗beta; /∗ least-significant bits of arguments ∗/

121. ⟨ Define A_{j} for 0 ≤ j < m 121 ⟩ ≡

for (j = 0; j < m; j^{++}) { numeric prefix ( , j); for (k = 0; k < j; k^{++}) {

v = new vert ( ); v bit = 0; /∗ this gate is the constant 0 ∗/ } for (k = 0; k < n; k^{++}) make2 ( , x + j, y + k); for (k = j + n; k < m plus n; k^{++}) {

v = new vert ( ); v bit = 0; /∗ this gate is the constant 0 ∗/ }

}

This code is used in section 119.

122. Since m is unsigned, it is necessary to say ‘j < m − 2’ here instead of ‘j ≤ m − 3’. #define a pos (j) (j < m ? j + 1 : m + 5 ∗ ((j − m) ≫ 1) + 3 + (((j − m) & 1) ≪ 1)) ⟨ Define P_{j}, Q_{j}, A_{m+2j}, R_{j}, and A_{m+2j+1} for 0 ≤ j ≤ m − 3 122 ⟩ ≡

for (j = 0; j < m − 2; j^{++}) { alpha = g vertices + (a pos (3 ∗ j) ∗ m plus n); beta = g vertices + (a pos (3 ∗ j + 1) ∗ m plus n); numeric prefix ( , j); for (k = 0; k < m plus n; k^{++}) make2 ( , alpha + k, beta + k); numeric prefix ( , j); for (k = 0; k < m plus n; k^{++}) make2 ( , alpha + k, beta + k); alpha = next vert − 2 ∗ m plus n; beta = g vertices + (a pos (3 ∗ j + 2) ∗ m plus n); numeric prefix ( , (long) m + 2 ∗ j); for (k = 0; k < m plus n; k^{++}) make2 ( , alpha + k, beta + k); numeric prefix ( , j); for (k = 0; k < m plus n; k^{++}) make2 ( , alpha + k, beta + k); alpha = next vert − 3 ∗ m plus n; beta = next vert − m plus n; numeric prefix ( , (long) m + 2 ∗ j + 1); v = new vert ( ); v bit = 0; /∗ another 0, it multiplies Q ∨ R by 2 ∗/ for (k = 0; k < m plus n − 1; k^{++}) make2 ( , alpha + k, beta + k);

}

This code is used in section 119.

123. Actually v_{m+n−1} will never be used (it has to be zero); but we compute it anyway. We don’t have to worry about such nitty gritty details because reduce will get rid of all the obvious redundancy. ⟨ Define U and V 123 ⟩ ≡

alpha = g vertices + (a pos (3 ∗ m − 6) ∗ m plus n); beta = g vertices + (a pos (3 ∗ m − 5) ∗ m plus n); start prefix ( ); for (k = 0; k < m plus n; k^{++}) make2 ( , alpha + k, beta + k); start prefix ( ); for (k = 0; k < m plus n; k^{++}) make2 ( , alpha + k, beta + k);

This code is used in section 119.

66  PARALLEL ADDITION  GB GATES ELTE §124

124. Parallel addition. It’s time now to take another deep breath. We have finished the parallel multiplier except for one last step, the design of a parallel adder.

The adder is based on the following theory: We want to perform the binary addition

u_{N−1} … u_{2} u_{1} u_{0}
v_{N−2} … v_{1} v_{0}
z_{N−1} … z_{2} z_{1} z_{0}

where we know that u_{k} + v_{k} ≤ 1 for all k. It follows that z_{k} = u_{k} ⊕ w_{k}, where w_{0} = 0 and

w_{k} = v_{k−1} ∨ u_{k−1}v_{k−2} ∨ u_{k−1}u_{k−2}v_{k−3} ∨ ⋯ ∨ u_{k−1} … u_{1}v_{0}

for k > 0. The problem has therefore been reduced to the evaluation of w_{1}, w_{2}, …, w_{N−1}.

Let c_{k}^{j} denote the OR of the first j terms in the formula that defines w_{k}, and let d_{k}^{j} denote the j-fold product u_{k−1}u_{k−2} … u_{k−j}. Then w_{k} = c_{k}^{k}, and we can use a recursive scheme of the form

c_{k}^{j} = c_{k}^{i} ∨ d_{k}^{i}c_{k−i}^{j−i} ,  d_{k}^{j} = d_{k}^{i}d_{k−i}^{j−i} ,  j ≥ 2,

to do the evaluation.

It turns out that this recursion behaves very nicely if we choose i = down[j], where down[j] is defined for j > 1 by the formula

down[j] = j − F_{(flog j)−1} .

For example, flog 18 = 7 because F_{7} = 13 < 18 ≤ 21 = F_{8}, hence down[18] = 18 − F_{6} = 10.

Let us write j → down[j], and consider the oriented tree on the set of all positive integers that is defined by this relation. One of the paths in this tree, for example, is 18 → 10 → 5 → 3 → 2 → 1. Our recurrence for w_{18} = c_{18}^{18} involves c_{18}^{10}, which involves c_{18}^{5}, which involves c_{18}^{3}, and so on. In general, we will compute c_{k}^{j} for all j with k →^{∗} j, and we will compute d_{k}^{j} for all j with k →^{+} j. It is not difficult to prove that

k →^{∗} j → i  implies  k − i →^{∗} j − i;

therefore the auxiliary factors c_{k−i}^{j−i} and d_{k−i}^{j−i} needed in the recurrence scheme will already have been evaluated. (Indeed, one can prove more: Let l = flog k. If the complete path from k to 1 in the tree is k = k_{0} → k_{1} → ⋯ → k_{t} = 1, then the differences k_{0} − k_{1}, k_{1} − k_{2}, …, k_{t−2} − k_{t−1} will consist of precisely the Fibonacci numbers F_{l−1}, F_{l−2}, …, F_{2}, except for the numbers that appear when F_{l+1} − k is written as a sum of non-consecutive Fibonacci numbers.)

It can also be shown that, when k > 1, we have

flog k = min_{0<j<n} max(1 + flog j, 2 + flog(k − j)) ,

and that down[k] is the smallest j such that the minimum is achieved in this equation. Therefore the depth of the circuit for computing w_{k} from the u’s and v’s is exactly flog k.

In particular, we can be sure that at most 3 flog N gates will be created when computing z_{k}, and that there will be at most 3N flog N gates in the parallel addition portion of the circuit. ⟨ Compute the final result Z by parallel addition 124 ⟩ ≡

⟨ Set up auxiliary tables to handle Fibonacci-based recurrences 125 ⟩;

⟨ Create the gates for W, remembering intermediate results that might be reused later 127 ⟩; ⟨ Compute the last gates Z = U ⊕ W, and record their locations as outputs of the network 132 ⟩; g n = next vert − g vertices ; /∗ reduce to the actual number of gates used ∗/

This code is used in section 119.

§125  GB GATES ELTE  PARALLEL ADDITION 67

125. After we have created a gate for w_{k}, we will store its address as the value of w[k] in an auxiliary table. After we’ve created a gate for c_{k}^{i} where i < k is a Fibonacci number F_{l+1} and l = flog i ≥ 2, we will store its address as the value of c[k + (l − 2)N]; the gate d_{k}^{i} will immediately follow this one. Tables of flog j and down[j] will facilitate all these manipulations. ⟨ Set up auxiliary tables to handle Fibonacci-based recurrences 125 ⟩ ≡

w = vert tables ; c = w + m plus n; flog = long tables ; down = flog + m plus n + 1; anc = down + m plus n; flog [1] = 0; flog [2] = 2; down[1] = 0; down[2] = 1; for (i = 3, j = 2, k = 3, l = 3; l ≤ m plus n; l^{++}) {

if (l > k) { k = k + j; j = k − j; i^{++}; /∗ F_{i} = j < l ≤ k = F_{i+1} ∗/

}

flog [l] = i;

down[l] = l − k + j; }

This code is used in section 124.

126. ⟨ Local variables for prod 117 ⟩ +≡ Vertex ∗uu, ∗vv ; /∗ pointer to u_{0} and v_{0} ∗/ Vertex ∗∗w; /∗ table of pointers to w_{k} ∗/ Vertex ∗∗c; /∗ table of pointers to potentially important intermediate values c_{k}^{i} ∗/ Vertex ∗cc, ∗dd ; /∗ pointers to c_{k}^{i} and d_{k}^{i} ∗/ long ∗flog ; /∗ table of flog values ∗/ long ∗down; /∗ table of down values ∗/ long ∗anc; /∗ table of ancestors of the current k ∗/ 127. ⟨ Create the gates for W, remembering intermediate results that might be reused later 127 ⟩ ≡

vv = next vert − m plus n; uu = vv − m plus n; start prefix ( ); v = new vert ( ); v bit = 0; w[0] = v; /∗ w_{0} = 0 ∗/ v = new vert ( ); v alt = vv ; w[1] = v; /∗ w_{1} = v_{0} ∗/ for (k = 2; k < m plus n; k^{++}) {

⟨ Set the anc table to a list of the ancestors of k in decreasing order, stopping with anc[l] = 2 128 ⟩; i = 1; cc = vv + k − 1; dd = uu + k − 1; while (1) {

j = anc[l]; /∗ now i = down[j] ∗/ ⟨ Compute the gate b_{k}^{j} = d_{k}^{i} ∧ c_{k−i}^{j−i} 129 ⟩; ⟨ Compute the gate c_{k}^{j} = c_{k}^{i} ∨ b_{k}^{j} 130 ⟩; if (flog [j] < flog [j + 1]) /∗ j is a Fibonacci number ∗/

c[k + (flog [j] − 2) ∗ m plus n] = v; if (l ≡ 0) break; cc = v; ⟨ Compute the gate d_{k}^{j} = d_{k}^{i} ∧ d_{k−i}^{j−i} 131 ⟩; dd = v; i = j; l^{−};

}

w[k] = v; }

This code is used in section 124.

128. If k → j, we call j an “ancestor” of k because we are thinking of the tree defined by ‘→’; this tree is rooted at 2 → 1. ⟨ Set the anc table to a list of the ancestors of k in decreasing order, stopping with anc[l] = 2 128 ⟩ ≡

for (l = 0, j = k; ; l^{++}, j = down[j]) { anc[l] = j; if (j ≡ 2) break;

}

This code is used in section 127.

129. #define spec gate(v, a, k, j, t) v = next vert^{++}; sprintf (name buf , , a, k, j); v name = gb save string (name buf ); v typ = t;

⟨ Compute the gate b_{k}^{j} = d_{k}^{i} ∧ c_{k−i}^{j−i} 129 ⟩ ≡ spec gate(v, , k, j, ); gb new arc(v, dd , ); /∗ first argument is d_{k}^{i} ∗/ f = flog [j − i]; /∗ get ready to compute the second argument, c_{k−i}^{j−i} ∗/ gb new arc(v, f > 0 ? c[k − i + (f − 2) ∗ m plus n] : vv + k − i − 1, );

This code is used in section 127.

130. ⟨ Compute the gate c_{k}^{j} = c_{k}^{i} ∨ b_{k}^{j} 130 ⟩ ≡

if (l) {

spec gate(v, , k, j, ); } else v = new vert ( ); /∗ if l is zero, this gate is c_{k}^{k} = w_{k} ∗/

gb new arc(v, cc,  );  /∗ first argument is c_{k}^{i} ∗/
gb new arc(v, next vert − 2,  );  /∗ second argument is b_{k}^{j} ∗/

This code is used in section 127.

131. Here we reuse the value f = flog(j − i) computed a minute ago. ⟨ Compute the gate d_{k}^{j} = d_{k}^{i} ∧ d_{k−i}^{j−i} 131 ⟩ ≡

spec gate(v, , k, j, );

gb new arc(v, dd ,  );  /∗ first argument is d_{k}^{i} ∗/
gb new arc(v, f > 0 ? c[k − i + (f − 2) ∗ m plus n] + 1 : uu + k − i − 1,  );  /∗ d_{k−i}^{j−i} ∗/

This code is used in section 127.

132. The output list will contain the gates in “big-endian order” z_{m+n−1}, …, z_{1}, z_{0}, because we insert them into the outs list in little-endian order. ⟨ Compute the last gates Z = U ⊕ W, and record their locations as outputs of the network 132 ⟩ ≡

start prefix ( ); for (k = 0; k < m plus n; k^{++}) { register Arc ∗a = gb virgin arc( );

a tip = make2 ( , uu + k, w[k]); a next = g outs ; g outs = a;

}

This code is used in section 124.

70  PARTIAL EVALUATION  GB GATES ELTE §133

133. Partial evaluation. The subroutine call partial gates (g, r, prob, seed , buf ) creates a new gate graph from a given gate graph g by “partial evaluation,” i.e., by setting some of the inputs to constant values and simplifying the result. The new graph is usually smaller than g; it might, in fact, be a great deal smaller. Graph g is destroyed in the process.

The first r inputs of g are retained unconditionally. Each remaining input is retained with probability prob/65536, and if not retained it is assigned a random constant value. For example, about half of the inputs will become constant if prob = 32768. The seed parameter defines a machine-independent source of random numbers, and it may be given any value between 0 and 2^{31} − 1.

If the buf parameter is non-null, it should be the address of a string. In such a case, partial gates will put a record of its partial evaluation into that string; buf will contain one character for each input gate after the first r, namely if the input was retained, if it was set to 0, or if it was set to 1.

The new graph will contain only gates that contribute to the computation of at least one output value. Therefore some input gates might disappear even though they were supposedly “retained,” i.e., even though their value has not been set constant. The name field of a vertex can be used to determine exactly which input gates have survived.

If graph g was created by risc, users will probably want to make r ≥ 1, since the whole RISC circuit collapses to zero whenever its first input ‘ ’ is set to 0.

An interesting class of graphs is produced by the function call partial gates (prod (m, n), m, 0, seed , Λ), which creates a graph corresponding to a circuit that multiplies a given m-bit number by a fixed (but randomly selected) n-bit constant. If the constant is not zero, all m of the “retained” input gates necessarily survive. The demo program called MULTIPLY illustrates such circuits.

The graph g might be a generalized network; that is, it might involve the or gates described earlier. Notice that if r is sufficiently large, partial gates becomes equivalent to the reduce routine. Therefore we need not make that private routine public.

As usual, the result will be Λ, and panic code will be set, if partial gates is unable to complete its task. ⟨ The partial gates routine 133 ⟩ ≡

Graph ∗partial gates (g, r, prob, seed , buf )

Graph ∗g; /∗ generalized gate graph ∗/

unsigned long r; /∗ the number of initial gates to leave untouched ∗/

unsigned long prob; /∗ scaled probability of not touching subsequent input gates ∗/ long seed ; /∗ seed value for random number generation ∗/ char ∗buf ; /∗ optional parameter for information about partial assignment ∗/

{ register Vertex ∗v; /∗ the current gate of interest ∗/ if (g ≡ Λ) panic(missing operand ); /∗ where is g? ∗/ gb init rand (seed ); /∗ get them random numbers rolling ∗/ for (v = g vertices + r; v < g vertices + g n; v^{++})

switch (v typ) {

case : case : continue; /∗ input gates might still follow ∗/

case :

if ((gb next rand ( ) ≫ 15) ≥ prob) { v typ = ; v bit = gb next rand ( ) ≫ 30; if (buf ) ∗buf ^{++} = v bit + ; } else if (buf ) ∗buf ^{++} = ; break;

default: goto done; /∗ no more input gates can follow ∗/

} done:

if (buf ) ∗buf = 0; /∗ terminate the string ∗/

g = reduce(g);

⟨ Give the reduced graph a suitable id 134 ⟩;

return g; /∗ if (g ≡ Λ), a panic code has been set by reduce ∗/ }

§133  GB GATES ELTE  PARTIAL EVALUATION 71

This code is used in section 7.

134. The buf parameter is not recorded in the graph’s id field, since it has no effect on the graph itself. ⟨ Give the reduced graph a suitable id 134 ⟩ ≡

if (g) { strcpy (name buf , g id ); if (strlen(name buf ) > 54) strcpy (name buf + 51, ); sprintf (g id , , name buf , r, prob, seed );

}

This code is used in section 133.

72  INDEX  GB GATES ELTE §135

135. Index. Here is a list that shows where the identifiers of this program are defined and used.

a: \underline{3}, \underline{27}, \underline{38}, \underline{47}, \underline{69}, \underline{81}, \underline{82}, \underline{86}, \underline{88}, \underline{90}, \underline{92}, \underline{93},

\underline{94}, \underline{96}, \underline{97}, \underline{98}, \underline{100}, \underline{132}. a pos : \underline{122}, 123. aa: \underline{100}, 104, 105, 106, 111. add : \underline{40}. addr : 97. alist : \underline{111}. alloc fault : 8, 115. alpha: \underline{120}, 122, 123. alt : \underline{2}, 3, 34, 79, 98, 101, 102, 103, 104, 105, 106,

109, 110, 112, 113, 114, 127. anc: 125, \underline{126}, 127, 128. : \underline{2}, 6, 15, 21, 22, 24, 25, 26, 27, 28, 29, 32,

33, 34, 35, 37, 38, 40, 41, 42, 43, 44, 45, 102, 115, 121, 122, 123, 129, 131.

Arc: 2, 3, 27, 38, 69, 81, 82, 90, 94, 98, 100, 132. arcs : 6, 98, 102, 103, 104, 105, 106, 107, 108,

110, 112. aux data: 108, 116. avail arc: \underline{100}, 106, 108. b: \underline{100}. bar : \underline{14}, 102, 103, 104, 105, 106, 107, 108, 109. bb: \underline{100}, 106. beta: \underline{120}, 122, 123. bit : \underline{98}, \underline{99}, 101, 102, 103, 104, 105, 106, 109,

121, 122, 127, 133. brk : \underline{20}, 21, 27, 37, 38, 46, \underline{47}, 50. buf : \underline{133}, 134. bypass and : \underline{104}. bypass or : \underline{105}. bypass xor : \underline{106}. c: \underline{69}, \underline{81}, \underline{82}, \underline{90}, \underline{94}, \underline{126}. carry : \underline{18}, 19, 29, 37, \underline{40}, 42, 74, 79. cc: \underline{126}, 127, 130. change: 29, \underline{30}, 33, 35, 37, 38, \underline{52}, 53, 56, 57,

62, 63, 66. cmp: \underline{106}. comp: \underline{14}, 15, 21, 22, 26, 27, 28, 29, 32, 33, 35,

37, 38, 40, 41, 42, 43, 44, 45. cond : \underline{20}, 21, 22, 29, 33, 37, 38, 46, \underline{47}, 53. count : 11, \underline{12}, 19. da: 68. dd : \underline{126}, 127, 129, 131. dec src: \underline{23}, 26, 27, 35. : \underline{13}, 24, 25, 114, 129, 130, 131. dest : \underline{20}, 21, 24, \underline{52}, 53, 57, 63, 65, 66. dest match: \underline{23}, 24, 35. diff : \underline{23}, 33, 42. dir : \underline{20}, 21, 22, 33. done: \underline{102}, 103, \underline{133}. double bypass : \underline{106}. down: \underline{23}, 26, 41, 125, \underline{126}, 128. do2 : \underline{20}, 21, 26, 27, 37, 38, 42, 43. do3 : \underline{20}, 21, 29, 33, 37, 38, 40, 41, 44, 45. do4 : \underline{20}, 24, 25, 28, 29, 33, 35, 37, 38, 40, 44, 45. do5 : \underline{20}, 21, 22, 33, 37, 38. dr : 51, \underline{52}, 53, 56, 63, 66, 68, \underline{69}, 74, 79, \underline{81},

\underline{82}, 86, \underline{90}, 92, \underline{94}. dw : 51, 68, \underline{69}, 74, 76, 79, \underline{81}, \underline{82}, \underline{90}, 93, \underline{94}, 97. e: \underline{69}, \underline{81}, \underline{82}, \underline{90}, \underline{94}. enabled : \underline{18}, 19, 21, 37, \underline{49}, 50, 74, 79. even comp: \underline{14}, 24, 25, 40. extra: \underline{18}, 19, 21, 22, 33, 34, 37, \underline{52}, 53, 72, 74, 79. f: \underline{117}. Fibonacci, Leonardo, numbers: 116. first of : \underline{19}, 119. flags : \underline{52}, 53, 57, 59, 66, 67. flog : 125, \underline{126}, 127, 129. foo: \underline{102}, 108, 109, 111. fromresult : \underline{39}. g: \underline{3}, \underline{69}, \underline{81}, \underline{82}, \underline{90}, \underline{94}, \underline{98}, \underline{100}, \underline{117}, \underline{133}. gate eval : \underline{1}, \underline{3}, 10, 69, 81, 82, 90, 94. gb init rand : 133. gb new arc: 13, 14, 24, 25, 112, 114, 129, 130, 131. gb new graph: 16, 111, 116. gb next rand : 133. gb recycle: 8, 100, 108, 111, 115, 116. gb save string : 11, 14, 108, 112, 114, 129. gb trouble code: 8, 115, 116. gb typed alloc: 108, 116. gb virgin arc: 27, 38, 111, 132. Graph: 1, 3, 8, 9, 69, 81, 82, 90, 94, 98, 100,

115, 117, 133. hop: \underline{20}, 21, 38. i: \underline{9}, \underline{47}, \underline{69}, \underline{81}, \underline{82}, \underline{90}, \underline{94}, \underline{120}. id : 16, 111, 116, 134. imm: \underline{20}, 21, 22. imm value: \underline{54}, 55, 63. impossible: 17. in vec: \underline{3}, 4, \underline{46}, 67, 68. inc dest : 22, \underline{23}, 41, \underline{54}, 55. inc src: \underline{23}, 26, 35. ind : \underline{20}, 21, 34, 35, 37, 38. input : \underline{82}, \underline{90}, \underline{94}. inst : \underline{52}, 53. int bit : \underline{18}, 19, 21, \underline{49}, 50, 74, 79. intvec: \underline{82}, \underline{90}, \underline{94}. invalid : \underline{69}, 75, 77, 78. is boolean: \underline{2}, 98, 109, 111. j: \underline{9}, \underline{47}, \underline{87}, \underline{89}, \underline{120}. Josephus, Flavius, problem: 119. jump: \underline{20}, 21, 37.

§135  GB GATES ELTE  INDEX 73

k: \underline{9}, \underline{40}, \underline{47}, \underline{69}, \underline{81}, \underline{82}, \underline{90}, \underline{94}, \underline{120}. l: \underline{47}, \underline{120}. la: \underline{52}, 53, 56, 57, 63, 65, 66, \underline{69}, 73, 74, 77,

79, \underline{81}, \underline{82}, 86, \underline{90}, \underline{94}. large risc elte: \underline{1}, \underline{94}. latch: \underline{34}. latch ptr : \underline{100}, 101, 102, 111, 112, 113. latchit : \underline{34}, 35, 37, 38. len: 112. lnk : \underline{109}, 110, 111, 112, 113. load imm: \underline{20}, 21, 35, 37, 38. loc: \underline{52}, 53, 56, 57, 63, 65. log : \underline{23}, 28, 33. long tables : 116, \underline{117}, 125. m: \underline{69}, \underline{81}, \underline{82}, \underline{90}, \underline{94}, \underline{115}. m plus n: 116, \underline{117}, 118, 121, 122, 123, 125,

127, 129, 131, 132. make adder : \underline{40}, 41, 42. make v arcless : \underline{102}. make v constant : \underline{102}, 103, 106. make v eq : \underline{102}, 103. make v 0 : \underline{102}, 104, 105. make v 1 : \underline{102}, 104, 105. make xor : \underline{15}, 32, 40, 43, 44, 45. make2 : \underline{13}, 15, 20, 21, 22, 24, 25, 26, 27, 29,

32, 33, 34, 35, 37, 38, 40, 41, 42, 43, 44, 45, 121, 122, 123, 132.

make3 : \underline{13}, 20, 21, 22, 27, 28, 29, 33, 35, 37,

38, 40, 41, 42, 44, 45. make4 : \underline{13}, 20, 21, 22, 27, 33, 35, 37, 38, 43, 45. make5 : \underline{13}, 20, 21, 33, 37, 38, 45. matrix : \underline{23}, 33, 43. max next vert : \underline{100}, 108. mem: \underline{18}, 19, 21, 22, 25, 34, 38, 41, \underline{52}, 53, 55,

67, \underline{69}, 77, 78, 82, 87, 89, \underline{90}, \underline{94}. Memblock: 82, \underline{83}, 90, 94. memblock struct: \underline{83}. memmask : \underline{82}, 87, 89, \underline{90}, \underline{94}. memry : \underline{83}, 87, 89. mems : 89. min risc elte: \underline{1}, 81, \underline{82}. min risc elte reset : 81. missing operand : 100, 133. mixed : \underline{20}, 21, 33, 37. mo: \underline{20}, 21, 22, 37. mod : \underline{20}, 21, 28, 29, 33, 37, 42, 45, 46, \underline{47}, 53,

56, 57, 58, 59, 60. mor : \underline{20}, 21, 22. n: \underline{40}, \underline{69}, \underline{81}, \underline{82}, \underline{90}, \underline{94}, \underline{100}, \underline{115}. name: 11, 14, 98, 108, 112, 114, 129, 133. name buf : 11, \underline{12}, 14, 108, 114, 129, 134. new graph: 8, \underline{9}, 16, 17, 27, 38, \underline{100}, 111. new vert : \underline{11}, 13, 19, 24, 25, 121, 122, 127, 130. next : 5, 6, 27, 38, 79, 98, 102, 104, 105, 106, 107,

108, 109, 110, 111, 112, 132. next loc: \underline{23}, 32, 33, 38. next next loc: \underline{23}, 32, 34, 38. next vert : 11, \underline{12}, 14, 16, 17, \underline{100}, 108, 111, 114,

119, 122, 124, 127, 129, 130. nextra: \underline{36}, 37, 38, \underline{52}, 53, 56, 57, 63, 66. no constants yet : \underline{101}. no room: 16, 108, 111, 116. nochange kv : \underline{36}, 37. nochange sn: \underline{36}, 37. nonzero: \underline{18}, 19, 29, 37, 74, 79. nope: \underline{20}, 21, 37. normal : 38, \underline{39}. : \underline{2}, 6, 14, 102, 108. ntranslate: \underline{36}, 37, 38. numeric prefix : \underline{12}, 19, 121, 122. nzd : \underline{20}, 21, 37, 38. nzs : \underline{20}, 21, 27, 37, 38. old dest : \underline{23}, 24, 27, 28, 41, 42, 43, \underline{52}, 53, 54,

55, 58, 59, 61, 62. old src: 22, \underline{23}, 24, 25, 26, 38, 44, \underline{52}, 53, 55,

56, 61, 62, 63. op: \underline{20}, 21, 29, 33, 37, 46, \underline{47}, 53, 57. : \underline{2}, 6, 15, 21, 22, 24, 25, 26, 27, 28, 29, 33,

35, 37, 38, 40, 41, 42, 43, 44, 45, 102, 114, 115, 122, 130.

out vec: \underline{3}, 5, \underline{46}, 68. outs : \underline{2}, 5, 27, 38, 79, 98, 109, 111, 132. ov : \underline{69}, 74, \underline{81}, \underline{82}, \underline{90}, \underline{94}. overflow : \underline{18}, 19, 29, 37, 74, 79. p: \underline{69}, \underline{81}, \underline{82}, \underline{90}, \underline{94}. p gates : 1, 98. page bit : \underline{18}, 19, 21, \underline{49}, 50, 74, 79. panic: \underline{8}, 16, 17, 100, 108, 111, 115, 116, 133. panic code: 8, 115, 133. partial gates : \underline{1}, \underline{133}. pop: \underline{20}, 21, 35. pr gate: \underline{98}. Pratt, Vaughan Ronald: 119. prefix : 11, \underline{12}, 19. print gates : \underline{1}, \underline{98}. printf : 72, 73, 74, 75, 76, 85, 91, 95, 98. prob: \underline{133}, 134. prod : \underline{1}, 2, 40, \underline{115}, 119, 133. prog : \underline{18}, 19, 21, 34, \underline{52}, 53, 72, 74, 79. push: \underline{20}, 21, 35. push or pop: \underline{20}, 21, 35. r: \underline{9}, \underline{69}, \underline{81}, \underline{82}, \underline{90}, \underline{94}, \underline{133}. ram: 69. reduce: \underline{100}, 108, 114, 115, 123, 133. reg : \underline{18}, 19, 24, 25, 27, 32, 35, 38. regs : \underline{8}, 16, 19, 24, 25, 35, 46, \underline{47}, 53, 62, 66, 67. rel : \underline{20}, 21, 22, 27, 37, 43. result : 20, \underline{23}, 33, 35, 37, 38, \underline{52}, 53, 57, 58, 59,

60, 61, 63, 64, 65, 66. result high: 44. result low : 44. resume: \underline{20}, 21, 37, 38. resume0 : \underline{20}, 21, 37, 38. reverse arc list : \underline{111}, 112. risc: 2, 9, 133. risc elte: \underline{1}, \underline{8}, 40, 46, 69, 81, 82, 90, 94. risc elte reset : \underline{1}, \underline{81}, 90, 94. risc state: \underline{1}, 46, 48, 50, 51, 53, 56, 57, 58, 59,

60, 61, 62, 63, 66, 67, 68, 69, 74, 75, 77, 78, 79, \underline{80}, 81, 82, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97.

run bit : \underline{18}, 19, 27, 34, 38, 46, \underline{47}, 79. run risc elte: \underline{1}, \underline{69}. s: \underline{69}, \underline{81}, \underline{82}, \underline{90}, \underline{94}. seed : \underline{133}, 134. sentinel : \underline{100}, 109, 110, 111. shift : \underline{23}, 33, 45. sign: \underline{18}, 19, 29, 37, 74, 79. simulate: \underline{1}, \underline{46}, 69, 81, 82, 90, 94. size: \underline{69}, 77, 78, \underline{82}, \underline{83}, 87, 89, \underline{90}, \underline{94}. skip: 38, \underline{39}. small risc elte: \underline{1}, \underline{90}, 94. source: 22, \underline{23}, 27, 28, 33, 38, 42, 43, 45, 52, \underline{54},

55, 57, 58, 59, 60, 61, 62, 63, 64, 65. spec gate: \underline{129}, 130, 131. special : 38, \underline{39}. sprintf : 11, 12, 14, 16, 108, 114, 116, 129, 134. src: \underline{52}, 53, 56, 57, 62, 63. src match: \underline{23}, 25, 35. ssum: \underline{23}, 33, 44. start : \underline{83}, 87, 89. start prefix : \underline{12}, 19, 21, 22, 27, 28, 29, 31, 42,

119, 123, 127, 132. step: 82, 90, 94. steps : \underline{82}, \underline{90}, \underline{94}. Stockmeyer, Larry Joseph: 119. strcpy : 12, 16, 19, 111, 116, 134. strlen: 134. sum: \underline{23}, 33, 42. t: \underline{3}, \underline{11}, \underline{13}, \underline{61}, \underline{69}, \underline{81}, \underline{82}, \underline{90}, \underline{94}. test single arg : \underline{102}. the boolean: \underline{2}, 98. three add : \underline{44}. tip: 2, 5, 6, 27, 38, 79, 98, 102, 103, 104, 105, 106,

107, 108, 109, 110, 111, 112, 132. tip value: \underline{2}, 5.

tmp: \underline{20}, 24, 25, 29, 44.
trace regs : \underline{69}, 72, 74, \underline{81}, \underline{82}, \underline{90}, \underline{94}.
translate: \underline{18}, 19, 37, 74.
trap: \underline{20}, 21, 37, 38.
trap or hop: \underline{20}, 21, 33, 38.
tt : \underline{61}.
typ: \underline{2}, 3, 11, 14, 79, 98, 101, 102, 103, 104, 105,

106, 108, 109, 110, 112, 114, 129, 133. type: \underline{83}, 89. t1 : \underline{15}, \underline{20}, \underline{40}, 43. t2 : \underline{15}, \underline{20}, \underline{40}, 43. t3 : \underline{20}, \underline{40}, 43. t4 : \underline{20}, 38, \underline{40}, 43. t5 : \underline{20}, 27, 32, 35, 37, 38, 43. t6 : \underline{20}, 35, 37, 38, 43, 44. t7 : \underline{20}, 35, 43, 44. t8 : \underline{20}, 35, 43, 44. u: \underline{14}, \underline{15}, \underline{100}. up: \underline{23}, 26, 41. util types : 16, 111, 116. uu: \underline{126}, 127, 131, 132. v: \underline{3}, \underline{11}, \underline{13}, \underline{14}, \underline{15}, \underline{69}, \underline{81}, \underline{82}, \underline{90}, \underline{94}, \underline{98},

\underline{100}, \underline{120}, \underline{133}.

val : \underline{2}, 3, 4, 6, 70, 71, 79. vert tables : 116, \underline{117}, 125. Vertex: 3, 11, 12, 13, 14, 15, 18, 20, 23, 30, 36, 39, 40, 69, 81, 82, 90, 94, 98, 100, 108, 109, 116, 117, 120, 126, 133.

vertices : 3, 4, 16, 17, 70, 71, 79, 98, 100, 109,

111, 119, 122, 123, 124, 133. vv : \underline{126}, 127, 129. v1 : \underline{13}, 20, 44. v2 : \underline{13}, 20, 44. v3 : \underline{13}, 20, 44. v4 : \underline{13}, 20. v5 : \underline{13}, 20. w: \underline{69}, \underline{81}, \underline{82}, \underline{90}, \underline{94}, \underline{126}. wa: 68, \underline{69}, 72, 73, 74, 76, 78, 79, \underline{81}, \underline{82}, \underline{90}, \underline{94}. wd : 68, \underline{69}, 72, 74, 76, 79, \underline{81}, \underline{82}, \underline{90}, \underline{94}. write: \underline{20}, 21, 37. write bit : \underline{20}, 21, 27, 35. x: \underline{40}, \underline{69}, \underline{81}, \underline{82}, \underline{90}, \underline{94}, \underline{120}. : \underline{2}, 6, 102, 108, 115, 122, 123, 132. xr : \underline{69}, 74, \underline{81}, \underline{82}, \underline{90}, \underline{94}. xresume: \underline{18}, 19, 37, 74, 79. y: \underline{40}, \underline{120}. z: \underline{40}. zz : 2.

GB GATES ELTE NAMES OF THE SECTIONS 75

⟨ Add the RISC data to new graph 17 ⟩ Used in section 8. ⟨ Allocate space for a temporary graph g and for auxiliary tables 116 ⟩ Used in section 115. ⟨ Bring simulation together properly 66 ⟩ Used in section 46. ⟨ Check to see if any latch has become constant; if not, break 101 ⟩ Used in section 100.

⟨ Clear everything 48 ⟩ Used in section 46.

⟨ Complement one argument of v 107 ⟩ Used in section 106.

⟨ Compute f = flog(m + n) 118 ⟩ Used in section 116.

⟨ Compute the final result Z by parallel addition 124 ⟩ Used in section 119. ⟨ Compute the gate b_{k}^{j} = d_{k}^{i} ∧ c_{k−i}^{j−i} 129 ⟩ Used in section 127. ⟨ Compute the gate c_{k}^{j} = c_{k}^{i} ∨ b_{k}^{j} 130 ⟩ Used in section 127. ⟨ Compute the gate d_{k}^{j} = d_{k}^{i} ∧ d_{k−i}^{j−i} 131 ⟩ Used in section 127. ⟨ Compute the last gates Z = U ⊕ W, and record their locations as outputs of the network 132 ⟩ Used in

section 124.

⟨ Compute the value t of a classical logic gate 6 ⟩ Used in section 3. ⟨ Copy all marked gates to a new graph 111 ⟩ Used in section 100. ⟨ Create a new vertex for complement of u 108 ⟩ Used in section 107. ⟨ Create gates for fetching the source value 22 ⟩ Used in section 17. ⟨ Create gates for instruction decoding 21 ⟩ Used in section 17. ⟨ Create gates for output write data, address and flags; 27 ⟩ Used in section 17. ⟨ Create gates for the arithmetic operations 42 ⟩ Used in section 17. ⟨ Create gates for the conditional load operations 29 ⟩ Used in section 17. ⟨ Create gates for the general logic operation 28 ⟩ Used in section 17. ⟨ Create gates for the matrix operation; 43 ⟩ Used in section 17. ⟨ Create gates for the new values of flags; 37 ⟩ Used in section 31. ⟨ Create gates for the new values of register 0 and the memory address register 38 ⟩ Used in section 31. ⟨ Create gates for the new values of registers 1 to regs 35 ⟩ Used in section 31. ⟨ Create gates for the new values of the program register 34 ⟩ Used in section 31. ⟨ Create gates for the shift operations 45 ⟩ Used in section 42. ⟨ Create gates for the sideway add operation; 44 ⟩ Used in section 17. ⟨ Create gates for the next loc and next next loc bits 32 ⟩ Used in section 31. ⟨ Create gates for the result bits 33 ⟩ Used in section 31. ⟨ Create gates that bring everything together properly 31 ⟩ Used in section 17. ⟨ Create the gates for W, remembering intermediate results that might be reused later 127 ⟩ Used in

section 124.

⟨ Create the inputs and latches 19 ⟩ Used in section 17.

⟨ Define A_{j} for 0 ≤ j < m 121 ⟩ Used in section 119.

⟨ Define P_{j}, Q_{j}, A_{m+2j}, R_{j}, and A_{m+2j+1} for 0 ≤ j ≤ m − 3 122 ⟩ Used in section 119.

⟨ Define U and V 123 ⟩ Used in section 119. ⟨ Dump the register contents into risc state 79 ⟩ Used in sections 69, 81, 82, 90, and 94.

⟨ Fill g with generalized gates that do parallel multiplication 119 ⟩ Used in section 115. ⟨ Fix up the alt fields of the newly copied latches 113 ⟩ Used in section 111. ⟨ Give the reduced graph a suitable id 134 ⟩ Used in section 133. ⟨ Global variables 80 ⟩ Used in section 7. ⟨ Initialize new graph to an empty graph of the appropriate size 16 ⟩ Used in section 8.

⟨ Internal subroutines 11, 13, 14, 15, 40, 100 ⟩ Used in section 7. ⟨ Local variables for prod 117, 120, 126 ⟩ Used in section 115. ⟨ Local variables for risc elte 9, 18, 20, 23, 30, 36, 39 ⟩ Used in section 8. ⟨ Local variables for simulate 47, 49, 52, 54 ⟩ Used in section 46.

⟨ Make u a copy of v; put it on the latch list if it’s a latch 112 ⟩ Used in section 111. ⟨ Mark all gates that are used in some output 109 ⟩ Used in section 100. ⟨ Mark all gates that are used to compute v 110 ⟩ Used in section 109.

⟨ Print a footline 73 ⟩ Used in sections 69, 82, 90, and 94.

⟨ Print a headline 72 ⟩ Used in sections 69, 81, 82, 90, and 94.

⟨ Print and read from Harvard memory 91 ⟩ Used in section 90. ⟨ Print and read from paged memory 95 ⟩ Used in section 94. ⟨ Print and read from simplest memory 75 ⟩ Used in section 69. ⟨ Print and read from von Neumann memory 85 ⟩ Used in section 82.

⟨ Print register contents 74 ⟩ Used in sections 75, 85, 91, and 95. ⟨ Print write data 76 ⟩ Used in sections 75, 85, 91, and 95.

⟨ Private variables 12 ⟩ Used in section 7. ⟨ Read a sequence of input values from in vec 4 ⟩ Used in section 3. ⟨ Read from Harvard memory 92 ⟩ Used in section 91. ⟨ Read from paged memory 96 ⟩ Used in section 95. ⟨ Read from simplest memory 77 ⟩ Used in section 75. ⟨ Read from von Neumann memory 86 ⟩ Used in section 85.

⟨ Read from mem array 87 ⟩ Used in sections 86, 92, and 96.

⟨ Reduce gate v, if possible, or put it on the latch list 102 ⟩ Used in section 100. ⟨ Replace u alt by a new gate that copies an input 114 ⟩ Used in section 113. ⟨ Set output write data, address and flags 62 ⟩ Used in section 46. ⟨ Set the anc table to a list of the ancestors of k in decreasing order, stopping with anc[l] = 2 128 ⟩ Used in

section 127.

⟨ Set up auxiliary tables to handle Fibonacci-based recurrences 125 ⟩ Used in section 124. ⟨ Set up input bits appropriately 70 ⟩ Used in sections 69 and 81.

⟨ Set brk 50 ⟩ Used in section 46. ⟨ Set inc dest to old dest plus 41 ⟩ Used in section 22. ⟨ Set inc src and dec src bits; 26 ⟩ Used in section 22.

⟨ Set old dest to the present value of the destination register 24 ⟩ Used in section 22. ⟨ Set old src to the present value of the source register 25 ⟩ Used in section 22. ⟨ Simulate addition and subtraction 59 ⟩ Used in section 46. ⟨ Simulate fetching data 56 ⟩ Used in section 46. ⟨ Simulate fetching the source value 55 ⟩ Used in section 46.

⟨ Simulate input 67 ⟩ Used in section 46.

⟨ Simulate instruction decoding 53 ⟩ Used in section 46. ⟨ Simulate interrupt 51 ⟩ Used in section 46.

⟨ Simulate jump 65 ⟩ Used in section 46.

⟨ Simulate mixed operations 63 ⟩ Used in section 46.

⟨ Simulate output 68 ⟩ Used in section 46.

⟨ Simulate the conditional load operations 57 ⟩ Used in section 46. ⟨ Simulate the general logic operation 58 ⟩ Used in section 46. ⟨ Simulate the matrix operations 61 ⟩ Used in section 46. ⟨ Simulate the shift operations 60 ⟩ Used in section 46. ⟨ Simulate the sideway add operation 64 ⟩ Used in section 63. ⟨ Store the sequence of output values in out vec 5 ⟩ Used in section 3.

⟨ The gate eval routine 3 ⟩ Used in section 7. ⟨ The large risc elte routine 94 ⟩ Used in section 7. ⟨ The min risc elte routine 82 ⟩ Used in section 7. ⟨ The partial gates routine 133 ⟩ Used in section 7. ⟨ The print gates routine 98 ⟩ Used in section 7. ⟨ The prod routine 115 ⟩ Used in section 7. ⟨ The risc elte reset routine 81 ⟩ Used in section 7. ⟨ The risc elte routine 8 ⟩ Used in section 7. ⟨ The run risc elte routine 69 ⟩ Used in section 7. ⟨ The simulate routine 46 ⟩ Used in section 7. ⟨ The small risc elte routine 90 ⟩ Used in section 7.

⟨ Try to reduce an inverter, then goto done 103 ⟩ Used in section 102.

⟨ Try to reduce an AND gate 104 ⟩ Used in section 102. ⟨ Try to reduce an EXCLUSIVE-OR gate 106 ⟩ Used in section 102. ⟨ Try to reduce an OR gate 105 ⟩ Used in section 102. ⟨ Type declarations 83 ⟩ Used in sections 2, 7, and 84.

⟨ Write to Harvard memory 93 ⟩ Used in section 90. ⟨ Write to paged memory 97 ⟩ Used in section 94. ⟨ Write to simplest memory 78 ⟩ Used in section 69. ⟨ Write to von Neumann memory 88 ⟩ Used in section 82.

⟨ Write to mem array 89 ⟩ Used in sections 88, 93, and 97. ⟨ Write m into the input gates 71 ⟩ Used in sections 69, 82, 90, and 94. ⟨ 1, 2, 84, 99 ⟩ December 15, 2013 at 10:18

GB GATES ELTE

Section Page

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 The RISC ELTE netlist . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 5 Serial addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 25 RISC simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 29 RISC management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 39 Minimal RISC management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 43 Small RISC management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 47 Large RISC management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 49 Generalized gate graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 52 Parallel multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 61 Parallel addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 66 Partial evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 70 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135 72

\begin{matrix}c \\ ◯ \end{matrix} 1993 Stanford University

This file may be freely copied and distributed, provided that no changes whatsoever are made. All users are asked to help keep the Stanford GraphBase files consistent and “uncorrupted,” identical everywhere in the world. Changes are permissible only if the modified file is given a new name, different from the names of existing files in the Stanford GraphBase, and only if the modified file is clearly identified as not being part of that GraphBase. (The CWEB system has a “change file” facility by which users can easily make minor alterations without modifying the master source files in any way. Everybody is supposed to use change files instead of changing the files.) The author has tried his best to produce correct and useful programs, in order to help promote computer science research, but no warranty of any kind should be assumed. Preliminary work on the Stanford GraphBase project was supported in part by National Science Foundation grant CCR-86-10181.