Here are the answers to the four EQ problems that appeared in Circuit Cellar 318.
Problem 1: Outside of simply moving data from one place to another, most of the work of a computer is performed by “dyadic” operators — operations that combine two values to form a third value. Examples include addition, subtraction and multiplication for arithmetic; AND, OR and XOR for logical operations. A dyadic operation requres three operands — two “source” values and a “destination” location. One way to classify a computer’s ISA (instruction set architecture) is by the number of operands that are explicitly specified in a dyadic instruction. The classifications are:
- 0-address (stack machine)
- 1-address (accumulator-based)
- 2-address
- 3-address
Can you describe some of the pros and cons of each of these choices?
Answer 1:
0-address
A 0-address machine is also known as a “stack” machine. All operators take their source operands from the stack and place their result on it. The only instructions that contain memory addresses are the “load” and “store” locations that transfer data between the stack and main memory.
— ADVERTISMENT—
—Advertise Here—
Pros: Short instructions, no implicit limit on the size of the stack.
Cons: More instructions required to implement most computations. Parallel computations and common subexpressions require a lot of “stack shuffling” operations.
1-address
In this type of machine, the ALU output is always loaded into an “accumulator” register, which is also always one of the source operands.
Pros: Simple to construct. Eliminates many of the separate “load” operations.
Cons: Requires results to be explicitly stored before doing another calculation. Longer instructions, depending on the number of registers, etc.
2-address
This type of machine allows the two source operands to be specified independently, but requires that the destination be the same as one of the source operands.
Pros: Allows more than one destination, eliminating more “move” operations.
— ADVERTISMENT—
—Advertise Here—
Cons: Even longer instructions.
3-address
This type of machine allows all three operands to be specified independently.
Pros: Most flexible, eliminates most data moves.
Cons: Longest instructions.
To summarize, the short instructions of the stack machine allow a given computation to be done in the smallest amount of program memory, but require more instruction cycles (time) to complete it. The flexibility of the 3-address architecture allow a computation to be done in the fewest instruction cycles (least time), but it consumes more program memory.
Problem 2: In order to be generally useful, a computer ISA must be “Turing complete”, which means that it can — at least theoretically, if not in practice — perform any computation that a Turing Machine can do. This includes things like reading and writing data from a memory, performing arithmetic and logical computations on the data, and altering its behavior based on the values in the data. Most practical computers have relatively rich instruction sets in oder to accomplish this with a reasonable level of efficiency. However, what is the minimum number of instructions required to achieve Turing-completeness?
Answer 2: Just one instruction, chosen carefully, is sufficient to achieve Turing-completeness. One example would be the instruction “subtract one from memory and branch if the result is not zero”. All of the operations of an ordinary computer can be synthesized as sequences of these “DJN” instructions. Note that since there is only one choice, there is no need to include an “opcode” field in the coding of each instruction. Instead, each instruction simply contains a pair of addresses: the data to be decremented, and the destination address of the jump.
Problem 3: Some processor ISAs are notorious for not being “friendly” to procedure-oriented languages such as C, requiring a lot of work on the part of the compiler in order produce reasonably efficient code, and even then, often introducing some restrictions for the programmer. What are some key features of an ISA that would make it “C-friendly”
Answer 3: The key concept in procedure-oriented languages like C is that of function composition. This means that it must be easy to produce new functions by combining calls to existing functions, and that functions can be called in the process of building argument lists for other functions. The C language takes this to the extreme, in the sense that every operator &mdash including the assignment operator — creates an expression that has a result value that can be used to build larger expressions. Therefore, one key architectural element is the ability to create function contexts — sets of parameters, local variables and return values — that can be “stacked” to arbitrary levels. In terms of an ISA, this means that it must support the direct implementation of at least one data stack that includes the ability to index locations within that stack relative to a stack pointer and/or a frame pointer. This concept is a direct abstraction from the hardware addressing modes of the PDP-11 minicomputer, the machine on which the first versions of C were developed. The PDP-11 ISA allows any of its 8 general-purpose registers to be used to address memory, with addressing modes that include “predecrement” and “postincrement” — implementing “push” and “pop” operations as single instructions — as well as “indexed indirect”, which allows local variables to be addressed as an offset from the stack pointer.
Problem 4: Sometimes a computer must work on data that is wider than its native word width. What is the key feature of its ISA that makes this easy to do?
Answer 4: The key feature in an ISA that allows arithmetic and shift operations to be extended to multiples of the processor’s native word width is that of a “carry” status bit. This bit allows one bit of information to be “carried” forward from one instruction to the next without requiring extra instructions to be executed.
For arithmetic operations, this bit remembers whether the instruction operating on the lower-order words of the operands resulted in a numerical “carry” or “borrow” that will affect the instruction operating on the next-higher-order words. Similarly, for shift and rotate instructions, this bit remembers the state of the bit shifted out of one word that needs to be shifted into the next word.
Contributor: David Tweed
Sponsor this Article
Circuit Cellar's editorial team comprises professional engineers, technical editors, and digital media specialists. You can reach the Editorial Department at editorial@circuitcellar.com, @circuitcellar, and facebook.com/circuitcellar
