NASA Office of Logic Design

NASA Office of Logic Design

A scientific study of the problems of digital engineering for space flight systems,
with a view to their practical solution.


2.2.3 Logic Design

(1) Word Length

Word lengths of aerospace computers have varied from 9 to 52 bits with most being around 24 bits. The major considerations have to do with precision of calculations (with due attention to round off and truncation errors), addressing formats, input/output precision, economy of size, and programming convenience. The size, speed, and power consumption of the memory all increase with longer memory words. Shorter word lengths impose limitations on the operand addressing and precision of data representation.

Although approximately 80 to 90% of spacecraft data-processing computations can be performed with word lengths no longer than 15 to 16 bits, critical navigation quantities (such as the earth's radius) generally require 24 to 32 bit precision (ref. 46). When a shorter word length is used, for example the 15-bit word in the Apollo guidance computer, greater precision is obtained when required by multiple precision operations. In many applications, sufficient accuracy can be achieved by computing various terms in single precision and accumulating them in double precision.

The precision of data from analog-to-digital converters (generally from 6 to 12 bits) is often important when the word length is being specified. The minimum word length is usually selected to permit handling of I/O data in single precision. However, this consideration is usually academic since the lower bound is effectively placed by the format needed for instruction addressing (ref. 14). If the instruction format is too short, operand-addressing limitations are imposed, and increased use of indexed addressing accompanied by a performance loss usually results. For example, in the redesign of the Block I AGC, the original 15-bit word was not lengthened. The expanded operation code set and memory capacity were accommodated by such devices as bank registers, an extension operation, and the shared use of some bits for either operations or addresses. The motivation was to achieve commonality of ground equipment for the Block I and Block II versions, but this advantage was probably outweighed by the added programming difficulties which would have been alleviated if the word length had been increased by three or four bits.

Another addressing feature which affects the choice of word length is the use of single or multiple address instructions. In typical problems, a double address format is likely to save up to 30% in program space and 10% in execution time over a comparable single address format (ref. 47). A double address machine, however, is more costly to implement in terms of hardware than a single address machine. Triple address and list processing structures provide only marginal improvement in program size and execution speed over double address at considerable hardware cost.

The ability to address shorter words or parts of words may be desirable, even though the memory uses longer words in its access or selection scheme. Thus, the memory may read out two or more data or instruction words during a cycle, after which a selection circuit chooses from these words. For example, the Gemini computer utilized a 39-bit memory word consisting of three 13-bit syllables, each of which could contain an instruction or data. This approach can both increase the program operating speed and simplify the memory construction.

Several spaceborne computers have used multiple word lengths for instruction and data. The memory devices of these machines must use a word size which is some multiple or fraction of the program and/or data words. For example, the UNIVAC 1824 guidance computers used for Sabre 2 and the Titan 3 launch vehicle have a 16-bit instruction word and a 24-bit data word. The main NDRO memory word is 48 bits in length. Hence a memory word may contain either three 16-bit instructions, two 24-bit data words, or one operand and one instruction. Each DRO memory word is 24 bits in length and may represent either one operand or one instruction (refs. 48 and 49).

The goals of minimizing power, weight, volume, and cost are leading manufacturers to shorter word length machines in order to reduce hardware. This may be accomplished successfully by increasing the speed of operation sufficiently to accommodate double precision arithmetic (where needed) and by developing a computer architecture which can be programmed efficiently with short instructions (e.g., a small address field). The word length trend seems to be either toward 16 bits, following the commercial minicomputers, or toward 32 bits with 1/2 and 1/4 word addressing.

 

(2) Instruction Repertoire

Early spaceborne computers had very limited instruction repertoires, with several computers having sixteen or fewer instructions. More recent computers have much larger instruction repertoires, ranging to over 100 instructions for some developmental machines, with most having around 60. Early computers all provided conventional arithmetic operations for binary fractional numbers. Addition, subtraction, and multiplication were offered on nearly all machines although division was sometimes programmed. The original Centaur computer was an exception since both multiplication and division were performed as series of additions or subtractions.

All machines to date have included basic instructions such as load, store, logic and arithmetic, I/O instructions, conditional and unconditional branch instructions, and shift instructions for scaling. Current spaceborne computers go well beyond this, generally to obtain more speed at a cost in hardware. In many machines, the instruction repertoire features certain instructions that are "tailored" to perform functions or sequences of operations that frequently occur in specific spaceborne applications. For example, a multiplication is often followed by the addition of the product to a prior accumulation. This sequence occurs in vector multiplication, matrix manipulations, and in numerous algebraic equations. A "multiply and accumulate" instruction to perform this sequence of operations will provide a saving in program space as well as execution time. Another example is to combine with instructions a commonly occurring function, such as decision making based on the result of the instruction. Since the tailored instructions invariably have control sequences that are almost identical to sequences that must be generated to achieve the standard instruction complement, they require only little additional hardware (ref. 47). For example, the Apollo Block I computer repertoire consisted of only eleven regular machine instructions, which burdened both speed and storage. The Block II redesign had 34 instructions, which were implemented with only a modest hardware increase.

For extended precision data handling, certain instructions utilizing overflow bits are convenient. Because multiple words are used primarily to accumulate small increments or to sum products during polynomial evaluations, nearly all multiple precision computation can be performed directly by load, store, add, and subtract double-precision instructions. Long data-format shift instructions reduce the number of double-precision products that may be required (ref. 46).

Hardware floating point operations have not yet been utilized in spaceborne applications although programmed floating point routines have been made more convenient by inclusion of instructions as "shift left to most significant bit." There is, however, a strong tendency to provide developmental computers with at least an option for floating point instructions to simplify flight software development.

The introduction of scratchpad memories in the newer computers leads to two-address instruction words where one address, or both, refer to the scratchpad memory. The use of small scratchpad memories generally results in a shorter instruction word and thus economy of storage along with a higher rate of instruction execution. Computers which make extensive use of scratchpad memories can effectively and efficiently use a combined half and full word instruction repertoire. If the repertoire is well chosen, such systems can reduce the amount of storage required for the instruction portion of programs to almost half (ref. 50). This savings is significant since memory is the most costly hardware item in the system, and the memory reduction can be an important weight saving consideration.

The need for separate index registers can be eliminated by the use of scratchpad memory registers as either index registers or base registers in instruction word formats. Addressing can use base registers with such options as direct indexed, indirect indexed, relative branches, and relative operands. The latter two types of instruction addressing are found in most smaller machines, while the first two are common only to the larger machines.

Although a short (e.g., 16-bit) word provides stringent constraints in the design of an instruction format, careful study reveals a number of attractive possibilities which lead to a powerful machine organization. Page addressing, which becomes necessary because of the small address field available, is much less burdensome if it is done in such a way that the page moves along with the program counter; thereby identifying memory locations relative to the program step being processed. The use of multiple accumulators which can serve as address pointers as well as data registers provides a freedom of memory accessing that is impossible with instruction word memory address fields alone. Such an addressing scheme, combined with appropriate instruction mechanization, can achieve pushdown stack operation with the pointer registers. The concept also frees bits in the instruction word, allowing multiple register addressing for interregister operation. Interregister instructions decrease memory size as well as access time.

A revived development in the spaceborne computer field is the use of microprogramming (ref. 51). Although microprogrammed computers have not been flown yet, the technique provides a flexibility not customarily available in conventional computers by allowing modification of such processor parameters as the instruction set and operand length. Microprogramming provides a means of including macro instructions which are application-oriented operations of considerable complexity, such as root and trigonometric functions, vector/matrix operations, and coordinate conversions. Furthermore, microprogramming allows instruction-set modification much later in the design cycle than conventional machines, to permit optimization of the computer for an evolving set of requirements.

 

(3) Speed

The speed of a computer can be thought of as the time required to perform an assigned task (ref. 52). However, since the tasks vary widely, specific numbers such as instruction times and memory access or cycle times are normally used to indicate the speed of the computer. Speed is important in spaceborne computers, and logical complexities are employed in order to gain speed in virtually every design; but size and reliability restrictions are of sufficient importance to limit the number and extent of such complexities.

The speed of memory operation is generally specified in terms of the access time and/or the cycle time. Faster memories need additional power for selection circuitry and have lowered signal-to-noise ratios for read signals, while slower memories generally have simpler and less critical circuits, less power dissipation, and hence potentially more reliability. For DRO core or film memories, the cycle time is generally 2 to 3 times the access time, whereas for NDRO or fixed memories, the cycle time is only about 1-1/2 to 2 times the access time. As shown in figure 5, storage cycle times for aerospace computers have ranged from 0.6 to 27 Ásec, with most times lying from 2 to 6 Ásec (ref. 1). The advent of smaller cores and plated wire memories is yielding cycle times of a microsecond or less for more recent computers. In addition to plated wire, MOS and bipolar LSI show promise, particularly for small memories. Since the latter are NDRO memories, the write time, which can be from tens to hundreds of nanoseconds, is often quoted as well as the read or access time.

figure_5.jpg (138012 bytes)

Figure 5.  Chronological comparison of aerospace computer
memory cycle times, add times, and multiply times.

Early spaceborne computers (not including those with drum memories) performed such basic operations as addition and subtraction in tens of microseconds and multiplication and division in hundreds of microseconds. Present day computers have addition times on the order of 2 to 6 Ásec and multiplication and division times in the tens of microseconds. Figure 5 also compares the add and multiply times of a number of aerospace computers introduced or under development through mid 1970 (ref. 1). Some computers of recent design have addition and subtraction times of 2 Ásec or less, multiplication times of less than 10 Ásec, and division times of less than 20 Ásec. When comparing execution speeds for various computers, one must consider whether the arithmetic operation times given are for single-address or double-address instructions, whether or not memory banks are alternated, and whether the numbers given are average times as opposed to minimum times.

To assist in the comparison of speeds of various computers, several organizations (e.g., NASA and the Aerospace Corporation) have devised sample programs or tasks for which operation times may be calculated on either real or hypothetical machines. Generally, these sample programs consist of a given series of operations such as matrix inversion, or a typical guidance or navigation problem. The real or hypothetical computer is then programmed to perform this task, and the computer's speed is determined by 1) operation of the machine itself, 2) simulation on another computer in which the times for each of the simulated instructions are accumulated as they are executed, or 3) manual calculation. Sample problems to date have been most pertinent and useful for specifying and evaluating computers when many arithmetic operations with numbers of widely varied precision are required. They have not been as appropriate when large amounts of data handling are required.

Speed problems with spaceborne computers have been minor and generally resulted from attempts to minimize ground-based precomputation. However, even minor speed problems are costly and can be expected as long as storage is critical. In the Apollo guidance computer, a speed increase was implemented by the addition of instructions, including a double-precision addition operation and a variety of single- and double-precision data-handling operations. However, the increase was limited by the memory addressing scheme devised to overcome word length restrictions.

The most dramatic example of speed problems in a spaceborne computer was the overload that nearly created an abort during the final moments of the Apollo 11 spacecraft's descent to lunar landing (ref. 53). At least four program alarms were triggered by a work overload, which was produced by the last-minute decision to operate the rendezvous radar in the auto-tracking mode during descent. Because of the necessity of responding to interrogations of the radar, the computer rejected some jobs of lower priority, and simultaneously flashed a warning light to the crew that its speed was being taxed beyond capacity.

 

(4) Data Flow

Whereas most earlier machines transmitted and processed data serially, practically all recent spaceborne computers have used parallel data flow to achieve higher speed. Two exceptions to this trend are the Saturn 5 LVDC and the OAO-B onboard processor, which illustrate the ability of serial machines to successfully handle complex tasks and, potentially, provide hardware savings and reduced complexity. A compromise serial-parallel configuration, which will be used on the Apollo telescope mount (ATM) computer, requires less hardware than is needed for parallel processing while it provides higher speed than a serial processor. In this approach, the data words are divided into serial "bytes," each of which is processed in parallel. Parallel processing probably will continue to dominate future designs although serial machines may still be used in special applications which do not demand high speeds but do require extreme simplicity for greater reliability (ref. 52).

 

(5) Number Representation

All spaceborne computers operate with the binary system; i.e., numbers are expressed to base two. However, for compactness and the convenience of programmers, the binary words are frequently represented in octal (base eight) or hexadecimal (base sixteen) by grouping the binary bits into bytes of three or four, respectively.

Fixed-point representation has been used almost exclusively to date. The number range provided has been adequate, with suitable scaling, for most aerospace applications, so that the additional hardware required for floating-point representation has not been considered justified. In those cases where the range of certain variables has made it necessary to store numbers in floating-point form, subroutines have been used to perform arithmetic calculations.

The scaling of fixed-point variables imposes an extra burden on programmers, and also complicates program validation. However, the scaling process has been facilitated by the fact that the values through which variables may range are generally constrained by the details of the mission and can be predicted quite accurately. Scaling is also simplified by means of simulations on ground-based computers with floating-point representation; the simulation results are easily examined to determine the excursions of all variables under anticipated conditions. Contingency code is still required for critical programs to provide for inadequate scaling and the subsequent occurrence of an overflow. For high precision G&N calculations, which comprise about 30% of all AGC programs, the lack of floating-point capability requires the generation of approximately 35% more code, and at least a twofold increase in the programming and verification workload (ref. 12). The complex scaling used in the AGC is difficult to understand, requires excessive time and training to implement, and produces coding that is difficult to modify and/or verify. For example, the scaling strategy was responsible for a rendezvous convergence problem encountered during Apollo verification.

The introduction of medium and large scale integration techniques has made it possible at low cost for newer aerospace computers to offer floating-point number representation and floating-point operations wired in as instructions (e.g., IBM System/4 PI-EP, UNIVAC 1832, and CDC ALPHA). The additional equipment and instructions necessary for floating-point representation can be justified on the grounds of 1) ease of programming and 2) faster operating speed when many operations are performed on numbers which range through wide intervals and when precision is required. This can only be determined by the details or requirements for a particular mission, but, in the future, floating-point representation will undoubtedly become more common as the hardware becomes smaller, lighter, cheaper, and more reliable.

Three possible ways for representing positive and negative fixed-point binary numbers are available to the logic designer: sign and magnitude, one's complement, and two's complement (ref. 14). Sign and magnitude representation, which is convenient when direct human interrogation of memory is desired, has not seen application in spaceborne computers. Two's-complement representation has been used in practically every spaceborne computer, with the notable exception of the Apollo guidance computer. This representation provides a unique representation for zero, does not require recomplementation, and simplifies multiple precision arithmetic.

For fixed-point arithmetic, the binary point can be positioned either between the sign and the high order magnitude bit (fractional representation) or to the right of the low order magnitude bit (whole number or integer representation). The former approach has been used in all spaceborne computers to date.

Occasionally, communications may require alphanumeric characters, and provision for 6- and 7-bit codes and their handling may be necessary. Binary-coded-decimal (BCD) number representation systems have not been popular for spaceborne applications due to the poor economy in number representation, and it is not foreseen that much use of the BCD technique will be made, except perhaps in conjunction with alphabetic or alphanumeric codes in future manned flights.


Home - NASA Office of Logic Design
Last Revised: February 03, 2010
Digital Engineering Institute
Web Grunt: Richard Katz
NACA Seal