Tuesday, August 29, 2006

G-15 Instruction Set Architecture

[Skip this post if you're interested only in my stories.
It is expository, rather than anecdotal, part of my discussion of the Bendix G-15 architecture, which will feature in some of my stories. It relies on material from the Bit-serial arithmetic and G-15 Memory Model posts. [1]]

"Computers were expensive,
programmers were cheap." [2]

The basic structure of the G-15 involved 28 drum lines. In normal operation, the write head of each was connected to the corresponding read head, recirculating an amount of information that depended on the physical distance between the two heads. A key to minimizing the necessary hardware was that all buses were one bit wide.

There was an important exception to recirculation: Execution of an instruction could cause information from a source (any of the drum lines plus certain bitwise functions of particular drum lines) to a destination (any of the drum lines) for a period of from 1 to 108 word times. [3]

Instructions could be executed from any of the eight command lines (0-5, 19, and 23) or the accumulator register (AR, line 28). [4]

Each instruction occupied one 29-bit word, formatted into the following fields:
P T B N C S D c
T specified a (7-bit) word time, as did N. S specified a (5-bit) memory line, as did D. The characteristic, C was split: the sign bit (c) represented the value 4; the two bits between N and S were its low-order bits. P and B were 1-bit flags.

Combinations of C, S, and D specified the operation to be performed. S:T and/or D:T specified the address(es) of the operand(s) and/or result. N specified the word position of the next command. [5] B indicated that the command was breakpointed.

Ordinary (Data Transfer) Commands

Copy: The basic command transferred the contents of the word located at S:T to the location D:T, then executed the command located in word N (in the current command line).

This simple command structure could be modified in a number of ways:

Complementation: If C was odd, S:T was complemented if negative.

Addition: The special destinations 29 and 30 caused the contents of S:T to be added to 28:T or 26:T (the single- and double-precision accumulators) and the result stored back in 28:T or 26:T.

Absolute value: C of 2 with D 28 or greater cleared the sign of S:T.

Interchange: C of 2 or 3 with S and D less than 28 transferred the contents of S:T to 28:T (AR) and the contents of 28:T to D:T. [6]

Subtraction: C of 3 with S or D 28 or greater changed the sign of the source operand, then (since C was odd) complemented if negative.

Double-precision: Adding 4 to C (i.e., making the sign bit of the instruction negative) changed the command to double-precision, operating on 58 bits (starting at an even address) instead of 29, treating the even word as the sign and 28 low-order bits, and all 29 bits of the odd word as the high-order bits.

Block (immediate) commands: Setting the P flag [7] converted a command from deferred (executed starting at word time T) to immediate (starting at the word time immediately following the command and continuing through word time T-1). Thus, for example, a single command could copy an entire line to another, or sum from 1 to 108 consecutive locations in a line. [8]

Precession: A block command with a C of 2 and S = D would copy each word of the line to the location that was one word-time later, ending with the previous contents of AR in the first location, and the previous contents of the last location in AR. In a machine without index registers, it was frequently more efficient to iterate over data by "moving the data past the program," rather than modifying all the commands that accessed the data array. [9]

Special sources: The 5-bit S field encoded 32 sources, only 28 of which were drum lines. Source 27 was a complicated function of lines 20, 21, and 28. Source 29 provided all zeros, a very useful constant. Source 30 was the logical and of line 21 and not line 20; source 31 was the logical and of line 21 and line 20. These were very useful for unpacking data within words, e.g., floating point numbers.

Special destinations: Destination 27 was used to test for zero. If S:T was all zero the next command was taken from word N of the current command line. Otherwise, it was taken from word N+1. This was the most common form of conditional branching. (Destinations 29 and 30 for addition/subtraction have already been discussed.)

Destination 31

Almost none of the descriptions above applied when the destination was 31, which caused a different interpretation of the S and C fields. Most notably, S selected the complex operation to be performed, rather than a source line. [10]

Input/Output: Sources 0 to 15 initiated I/O operations on the various available devices (e.g., 8 selected type-out and 12 selected type-in; 10 selected punching paper tape and 15 selected reading paper tape). A full description of the I/O system would take us even further afield.

Special Commands: Sources 16 to 31 invoked a variety of different commands that did not fit into the basic transfer-source-to-destination paradigm.
16: Halt
17: Test for PUNCH switch on (and ring bell)
18: Send data to auxiliary equipment
19: Control optional Differential Analyzer
20: Select Command Line and Return (i.e., branch to command line C at the word time saved by a previous Mark; subroutine return)
21: Select Command Line and Mark (i.e., branch to C:N and store T; subroutine call) [11]
22: Test if Sign of AR Negative
23: Depending on C:
-- 0: Clear Multiplication and Division Registers (24 to 26)
-- 3: Extract and Copy into line 25 the bits of line 26 that correspond to 1 bits in 2:T, clearing the extracted bits in line 26 [12]
24, 25: Multiply and Divide (T determined the number of iterations of the bit-by-bit process, two word times per bit).
26: Shift line 24 left and line 25 right (the number of places could be controlled by T or by the contents of AR)
27: Normalize (shift the contents of line 24 left until there are no leading zeros, and add the number of places shifted to AR) [13]
28: Test for I/O System Ready
29: Test for Overflow (and clear the overflow bit)
30: Write File Code on Magnetic Tape
31: Take Next Command from AR (useful when instructions had to be explicitly indexed)

[1] I've simplified slightly for ease of exposition. For the nitty-gritty details, see the Coding Manual for the Bendix G-15, the G-15D Programmer's Reference Manual, and the G-15D Technical Manual, Simplified Drawings, from which the various figures have been extracted.
[2] A G-15 cost about $50K. A typical programmer's annual salary was about a tenth of that.
[3] Specifying a destination of 31 invoked a quite different class of instructions that will be discussed later.
[4] Memory line 19 was numbered as command line 6, and memory line 23 as command line 7, allowing the command line to be coded in the three bits of C. Since AR could hold only a single instruction, it was not considered a command line, and there was a special instruction to take the next command from AR (NCAR), after which execution continued in the previous command line.
[5] For minimum access coding, successive commands were not generally stored in consecutive locations. Inclusion of this field was why the command format was often referred to as "2.5-address," and inspired the comment: "The modified type of two-address code is unusual and difficult to classify."
[6] See also the section on precession.
[7] Customarily written as "u" on coding sheets.
[8] The sum of an entire line was called its checksum and was commonly used as a hash code to verify that information had not been damaged, either by an I/O failure or by corruption of memory. Its advantages were that it was fast, and caught the most common errors. Its disadvantages were that it did not provide enough redundancy to correct any errors, and it did not have the collision resistance required when hash functions are used as authenticators. (In fact, it was common to use any free word in a line to store the negative of the checksum of the rest of the line, so the full checksum would be the easily-recognized value zero.)
[9] There was also a trick shared among advanced programmers that used a peculiarity in the I/O system to precess line 19 by 4 words in a single drum cycle, allowing a factor of four speedup in certain programs.
[10] Since there was no clear pattern associating S with the commands, this list was the most-referenced part of the Programmer's Reference Card.
[11] Turing's insight about the need for a stack of return addresses was not reflected in the G-15. The hardware preserved a single return word time (mark). Thus subroutines could not call other subroutines, and needed to know to which line they should return. There was no provision for the programmer to access the mark other than by returning to it.
[12] A rather complex-looking command for a minimalist machine, but key to efficient binary-to-decimal conversion.
[13] Vital for software implementation of floating point arithmetic.