Introduction: Functional Units, Buses and Addressing Modes

A bus is a group of common wires used to carry information between the units of a computer. Different types are used.

• Address bus: carries the memory or I/O address from the CPU. It is one way.
• Data bus: carries the data between the CPU, memory and I/O. It is two way.
• Control bus: carries signals such as read, write, clock and interrupt, to control the other buses.

Together, they form the system bus.

Bus architecture is the way a common set of wires is arranged to connect the CPU, memory and I/O devices. It has three parts: an address bus, a data bus and a control bus. A single shared bus is cheap and simple, but only one transfer can occur at a time. Large systems use many buses, such as a fast local bus and a slower I/O bus, joined by a bridge.

Its role is to let any unit communicate with any other over the same wires. It cuts the number of connections, makes it easy to add devices, and uses standard signals. An arbiter decides who uses it.

The three buses together make the system bus. Their characteristics are compared below.

Address bus

It selects the one location that the CPU wants. With $n$ address lines, the CPU can address $2^n$ locations. For example, 16 lines give $2^{16} = 65536$ locations, that is 64 K.

Data bus

It carries the word that is read or written. A 32-bit data bus moves 32 bits in one transfer. A wider data bus gives a faster system.

Control bus

It carries signals like memory read, memory write, I/O read, I/O write, clock, interrupt request and bus grant. It tells all the units when and how to use the address and data buses. In short, the address bus says where, the data bus says what, and the control bus says when and how.

Example of how they work together

Suppose the CPU wants to read a word from memory. It places the address on the address bus. It then activates the memory read signal on the control bus. The memory finds the location and puts the word on the data bus. The CPU takes the word from the data bus. For a write, the CPU puts the address on the address bus and the data on the data bus, and the control bus carries the memory write signal. All three buses are therefore needed in every transfer, and a fault in any one of them stops the system.

A computer has three types of buses.

• Address bus: it carries the address of the memory location or I/O device that the CPU wants to reach. It is one way, from the CPU to the memory and devices. Its width decides the memory size.
• Data bus: it carries the actual data between the CPU, memory and I/O. It is two way. Its width decides how many bits move at a time.
• Control bus: it carries control signals such as read, write, clock, interrupt request and bus grant. It manages the use of the other two buses.

Bus arbitration is the method of deciding which device may use a shared bus when more than one device requests it at the same time. The device that gets the bus is called the bus master. The unit that decides is the arbiter. The arbiter can be the CPU, or a special bus controller.

Why it is needed

A bus is a shared resource, and only one device can send data on it at a time. If two devices sent together, the signals would mix and the data would be wrong. Several devices, such as the CPU, DMA controllers and I/O processors, can all become bus masters. So a rule is needed to give the bus to one of them and to make others wait. Arbitration also gives the important devices a higher priority and stops any device from using the bus for ever.

Daisy chaining scheme

In this scheme, all the devices are connected in series. The devices share one common bus request line. The bus grant line passes from the arbiter through each device in turn, and it goes from one device to the next one.

 Arbiter --grant--> [Dev 1] --grant--> [Dev 2] --grant--> [Dev 3]
    ^                  |                 |                  |
    +------ common bus request line (wired OR) -------------+

The working is as follows.

1. Any device that needs the bus puts a signal on the common bus request line. The line is the OR of all requests.
2. The arbiter sees the request and sends the grant signal to the first device in the chain.
3. If this device did not request the bus, it passes the grant signal on to the next device.
4. The first device that did request the bus keeps the grant signal and does not pass it on. It becomes the bus master and also sets a busy line, so that the others know the bus is in use.
5. When the master finishes, it removes the busy signal. The arbiter then looks at the request line again.

The priority of a device depends only on its position in the chain. The device nearest to the arbiter has the highest priority, and the last one has the lowest.

Advantages and disadvantages

It is simple and needs very few wires, and a new device is easy to add at the end. But the priority is fixed by position, and a device at the end may starve if the earlier ones request often. The grant signal has to pass through every device, so the delay grows with the chain length. If one device in the chain fails, the devices after it cannot get the bus.

In daisy chaining, the devices are connected in series on one grant line. The bus grant signal passes from the first device to the next. A device that has requested the bus stops the signal and takes the bus. So the priority depends on the position in the chain, and the closest device has the highest priority. It needs few wires but is slow.

In centralized parallel arbitration, each device has its own separate request and grant lines to a central arbiter. The arbiter looks at all the requests together and grants one. It is faster and more flexible in priority, but needs more lines and a more complex arbiter.

In a single bus system, all the units share one bus, so only one transfer can take place in a clock cycle. This makes it slow. In a multiple bus organization, the CPU has two or three internal buses, so that more than one transfer can take place at the same time.

Three-bus organization of the CPU

The common design has bus A, bus B and bus C. The registers are in a register file with two read ports and one write port. Bus A and bus B carry the two source operands from the register file to the two inputs of the ALU. Bus C carries the ALU result back to the register file.

  +--------------------------------+
  |        Register file R0..Rn    |
  +--+--------------+----------^---+
     |A bus         | B bus    | C bus
     v              v          |
   +---------------------+     |
   |         ALU         |-----+
   +---------------------+

The program counter, the instruction register, the memory address register and the memory data register also connect to these buses, as needed.

Working

In one clock cycle, two registers are read onto bus A and bus B, the ALU adds them, and the result is written to a third register through bus C. For example, ADD R4, R1, R2 with $R4 \leftarrow R1 + R2$ needs only one clock step. In a single bus system, the same instruction needs three steps. First R1 is moved to a temporary register, then R2 is put on the bus and added, and then the result is moved to R4.

Advantages

• Fewer clock cycles per instruction, so the program runs faster.
• Two operands can be read at the same time.
• No temporary registers such as the Y register are needed for ALU inputs.
• It supports pipelining more easily.

Disadvantages

• More wires and more control signals are needed.
• The hardware and the cost are higher.
• The control unit becomes more complex.

Example of the saving

Take the three instructions ADD R4, R1, R2, SUB R5, R4, R3 and MUL R6, R5, R1. On a three-bus CPU each of them needs one data-path step, so three steps in all. On a single bus CPU, each needs about three steps, so nine steps in all. The three-bus design is therefore about three times faster for this short program, although the real gain depends on the program and the instruction mix.

Other multiple bus use

At the system level, there may be separate buses for memory and for I/O, or separate address, data and control buses. Some systems also have a fast local bus for the CPU and the cache, and a slower expansion bus for devices, joined by a bridge. The slow devices then do not delay the fast ones.

So multiple bus organization improves the performance of the processor by allowing parallel transfers, at the price of a higher cost and more complex control.

Bus arbitration is the process of deciding which device becomes the bus master when several devices ask for the shared bus at the same time. Only one master can use the bus at a time.

Two types of bus arbitration exist.

• Centralized arbitration: a single arbiter or the CPU grants the bus. It has the daisy chaining method, the polling method and the independent request (parallel) method.
• Distributed arbitration: there is no central arbiter. Every device has its own arbitration logic, and the devices decide by themselves using a priority code placed on the bus.

(i) Bus system using multiplexers

There are four registers A, B, C and D, each of 4 bits. The bus is also 4 bits wide. We need one 4-to-1 multiplexer for each bit, so four multiplexers are used. Bit 0 of every register goes to MUX 0, bit 1 goes to MUX 1, and so on. Two select lines $S_1S_0$ are common to all the multiplexers. They choose which register is placed on the bus.

 A3..A0   B3..B0   C3..C0   D3..D0
   |        |        |        |
   v        v        v        v
+------------------------------------+
| MUX 3 | MUX 2 | MUX 1 | MUX 0      | <- S1 S0
+------------------------------------+
        |   4-bit common bus   |
        v                      v
   (loaded into any register by its LOAD input)

The select value 00 chooses A, 01 chooses B, 10 chooses C and 11 chooses D. The bus output is then loaded into a destination register by enabling its load input at a clock pulse. For example, with $S_1S_0 = 10$ and the load input of A enabled, the transfer $A \leftarrow C$ takes place at the next clock edge. The same bus can be used for any transfer between the four registers, but only one transfer can happen in one clock pulse.

(ii) Evaluating X = A + B * [C * D + E * (F + G)]

In a stack computer, every arithmetic instruction takes its operands from the top of the stack, so it needs no address. First we write the expression in reverse Polish notation. The conversion is checked with a program.

$$ABCDEFG++*+$$

Then we scan it from left to right. A letter becomes a PUSH instruction. An operator becomes one instruction without an operand. The program is:

The program needs 14 instructions. The last instruction stores the result at location X.

As a check, let $A=1, B=2, C=3, D=4, E=5, F=6, G=7$. The stack program computes $CD = 12$, $F+G = 13$, $E13 = 65$, then $12 + 65 = 77$, then $B * 77 = 154$, and finally $A + 154 = 155$. The direct calculation of the expression also gives 155, so the program is correct.

Bus arbitration is the method used to decide which device gets control of a shared bus when two or more devices want it at the same time. Only one device, called the bus master, can drive the bus at any moment.

The arbiter looks at all the requests. It then grants the bus to one device according to a rule such as fixed priority or rotating priority. When the master finishes its transfer, it releases the bus and the arbiter grants it to the next requester. This prevents two devices from sending data together and corrupting it.

A digital computer has five functional units. The input unit accepts data and programs. The memory unit stores them. The arithmetic and logic unit (ALU) does addition, subtraction and logic operations. The control unit fetches and decodes instructions and sends control signals to all other units. The output unit shows the results. The ALU and the control unit together form the CPU. The units are joined by a system bus.

The basic functional units of a digital computer are as follows.

• Input unit: it takes in data and programs.
• Memory unit: it stores the data and programs.
• Arithmetic and logic unit (ALU): it performs arithmetic and logic operations.
• Control unit: it fetches, decodes and controls the execution of instructions.
• Output unit: it gives the results to the user.

The ALU and the control unit together are called the CPU.

A computer is a system made of five functional units. They are the input unit, the memory unit, the arithmetic and logic unit, the control unit and the output unit. The ALU and control unit together are called the central processing unit (CPU). Each unit does a clear job, and they work together under the control of a stored program.

Input unit

The input unit takes data and instructions from the user and converts them into binary form that the computer can use. Keyboard, mouse, scanner and microphone are examples. The data is placed in memory or sent to a register of the CPU. Input is usually read one character or one word at a time.

Memory unit

The memory stores programs and data. It has two levels. The main (primary) memory, made of semiconductor RAM, is fast and holds the programs now being run. It is directly used by the CPU. The secondary memory, such as a hard disk or SSD, is larger and cheaper but slower. It keeps programs and data permanently. Each word of main memory has an address, and the CPU can reach any word by giving its address.

Arithmetic and logic unit (ALU)

The ALU does the arithmetic operations such as add, subtract, multiply and divide. It also does logic operations such as AND, OR, NOT and comparison. The operands come from registers. The result goes back to a register. A set of flag bits records things like zero, carry and overflow.

Control unit

The control unit is the brain of the computer. It reads each instruction from memory, decodes it, and sends the right timing and control signals to the other units. It tells memory when to read or write, tells the ALU what to do, and tells the input and output devices when to transfer data. It does not process data itself. The program counter (PC) holds the address of the next instruction, and the instruction register (IR) holds the present one.

Output unit

The output unit shows the results to the user in a form that people can understand. Monitor, printer and speakers are examples. It receives the binary results from the memory or CPU and converts them.

Interconnection

The units are joined by the system bus, which has an address bus, a data bus and a control bus. Data goes from the input unit to memory, then through the ALU, then back to memory and out through the output unit. The control unit directs the whole flow.

Working in short

A program is first loaded into memory through the input unit. The control unit fetches an instruction, decodes it and fetches the operands. The ALU does the work and the result is stored or displayed. This fetch, decode and execute cycle repeats until the program ends.

The structure of a computer has four main components.

• Central processing unit (CPU): it controls the computer and does the data processing. It has the control unit, the ALU and the registers.
• Main memory: it stores the programs and data that the CPU is working on.
• Input/output (I/O): it moves data between the computer and the outside world, such as a keyboard, a disk or a display.
• System interconnection (system bus): it is the path that carries data, addresses and control signals between the CPU, the memory and the I/O.

Computer architecture means the attributes of a computer that are visible to the programmer. It includes the instruction set, the data formats, the addressing modes, the registers and the I/O methods. It decides what the machine can do.

Computer organization means how these features are actually built in hardware. It deals with control signals, the interfaces between units, the memory technology and the data paths. It decides how the machine does it.

For example, a multiply instruction is architecture. Whether it is done by a separate multiplier circuit or by repeated addition is organization.

Computer architecture describes the attributes of a computer that a programmer can see and use. These are the instruction set, the number of bits used for data, the addressing modes, the registers and the way input and output is handled. It answers the question "what does the machine do?".

For example, whether a processor has a multiply instruction is an architectural decision. How that instruction is built with gates and circuits is not part of architecture. That is the job of computer organization. The same architecture can therefore be built with different organizations, as in the Intel x86 family over many years.

A computer has five basic functional units: the input unit, the memory unit, the arithmetic and logic unit (ALU), the control unit, and the output unit. The ALU and the control unit together form the CPU.

Input devices bring data and programs into memory. The control unit fetches each instruction from memory and sends signals to the other units. The ALU performs arithmetic and logic operations. Results go back to memory and then to the output unit, such as a monitor or printer.

A register is a small, very fast storage place inside the CPU that holds a word of data, an address or an instruction. It is made of flip-flops.

General-purpose registers (such as R0 to R15) can be used by the programmer for any purpose, such as holding operands, results or addresses.

Special-purpose registers have a fixed job. Examples are the program counter (address of the next instruction), instruction register (the present instruction), stack pointer (top of stack), memory address register, memory data register, accumulator and the status (flag) register.

A digital system has registers, a bus and a memory. Data moves between them by register transfers, bus transfers and memory transfers. All of them happen under the control of timing signals and are written in register transfer language.

Register to register transfer

The content of one register is copied to another by $R2 \leftarrow R1$. R1 keeps its value. The transfer takes place only if a control condition is true, written as

$$P:\ R2 \leftarrow R1$$

When $P = 1$, the load input of R2 is enabled and the transfer takes place at the next clock pulse.

Transfer through a common bus

If a computer has many registers, joining each pair by wires is costly. So a common bus is used. The select lines of multiplexers (or the enable of three-state buffers) pick the source register, which puts its content on the bus. The destination register has its load input enabled. For example, to do $R3 \leftarrow R1$, the select lines choose R1 and the load of R3 is enabled. Only one source drives the bus in a clock pulse.

Memory transfer

Memory is accessed through the address register (AR) and the data register (DR). The AR holds the address of the word. DR holds the data being moved.

For a read, the address is placed in AR and the read signal is given. The memory places the word on the data lines, and it is loaded into DR.

$$Read:\ DR \leftarrow M[AR]$$

For a write, the address is placed in AR, the data in DR, and the write signal is given. The memory stores DR at the address AR.

$$Write:\ M[AR] \leftarrow DR$$

Each of these operations takes one memory cycle. A word transferred from memory to the CPU always goes through DR, and a word to be written is always taken from DR.

Example

To add a number from memory into a register, the sequence is $AR \leftarrow 500$, then $DR \leftarrow M[AR]$, then $R1 \leftarrow R1 + DR$. The first step loads the address, the second reads memory, and the third uses the ALU to add. In this way, data moves between registers, buses and memory, one controlled step at a time.

Memory is connected to the CPU through the address register (AR), the data register (DR) and the control signals.

For a read, the CPU puts the address of the required word in AR and activates the read signal. The memory places the word on the data lines, and it is loaded into DR.

$$Read:\ DR \leftarrow M[AR]$$

For a write, the CPU puts the address in AR and the data in DR, and activates the write signal. The memory stores the word at that address.

$$Write:\ M[AR] \leftarrow DR$$

Each operation takes one memory cycle.

A bus is a set of common wires that carries information between the units of a computer. A bus transfer moves the content of one register to another register over this common path, and it is written as $R2 \leftarrow R1$.

A memory transfer is the movement of data between the CPU and the memory. A read brings a word from memory into a register, written $DR \leftarrow M[AR]$. A write stores a register's content into memory, written $M[AR] \leftarrow DR$. Here AR holds the address and DR holds the data.

The statement has two conditions, so it gives two register transfers. The first one occurs when $P = 1$. The second occurs when $P = 0$ and $Q = 1$, because the "else if" is checked only when the first condition fails.

$$P:\ R1 \leftarrow R2$$

$$P'Q:\ R1 \leftarrow R3$$

Here $P'$ means the complement (NOT) of $P$. The part before the colon is the control function. It must be 1 for the transfer to take place at the next clock pulse. If both $P = 0$ and $Q = 0$, no transfer happens and R1 keeps its old value.

In a multiplexer bus, there is one multiplexer for each bit of the bus. All the registers feed their bits into these multiplexers, and a common set of select lines decides which register is put on the bus. The question gives 8 registers of 16 bits each.

I. Select inputs in each multiplexer

A multiplexer must be able to choose any one of the 8 registers. The number of select lines $k$ must satisfy $2^k \geq 8$.

$$2^k = 8 \Rightarrow k = \log_2 8 = 3$$

Therefore each multiplexer has 3 select inputs. The same 3 lines are connected to all multiplexers, so the 3-bit code selects the same register in every bit position.

II. Size of the multiplexers

Each multiplexer takes one bit from each of the 8 registers, so it has 8 data inputs and one output. The size of each multiplexer is 8 to 1, which is written as $8 \times 1$. It is also called an 8-to-1 line multiplexer.

III. Number of multiplexers

The bus carries 16 bits, because each register has 16 bits. We need one multiplexer for each bit.

$$\text{number of multiplexers} = 16$$

Multiplexer 0 takes bit 0 of all 8 registers, multiplexer 1 takes bit 1 of all registers, and so on up to multiplexer 15.

 R0..R7 (16 bits each)
  bit15 of R0..R7 --> [MUX 15 8x1] --+
  ...                                |--> 16-bit bus
  bit 0 of R0..R7 --> [MUX  0 8x1] --+
        S2 S1 S0 (common select lines)

Check of the totals

The total number of data inputs to all the multiplexers is $16 \times 8 = 128$. This is the same as the total number of register bits, $8 \times 16 = 128$. So every register bit is connected to exactly one multiplexer input.

Working of the bus

Suppose the select code is $S_2S_1S_0 = 101$. This chooses register R5. All 16 bits of R5 appear on the bus at the same time. If the load input of register R2 is also enabled, then at the next clock pulse the transfer $R2 \leftarrow R5$ takes place.

Select lines and their register:

Only one register can drive the bus at any moment, so there is no conflict. This is the main advantage of the multiplexer bus. Its disadvantage is the large number of gates. Here we need 16 multiplexers of size 8 to 1.

Therefore the bus needs 3 select inputs per multiplexer, 8-to-1 multiplexers, and 16 multiplexers in all.

A three-state buffer is a gate that has three output states: logic 0, logic 1, and high impedance. In the high-impedance state the output is disconnected, as if the gate were not there. A control input decides this. When the control input is 1, the buffer passes its input to the output. When the control input is 0, the output is in high impedance.

Because a disabled buffer does not affect the line, the outputs of many buffers can be joined to one wire. We only need to make sure that one buffer is enabled at a time. That is how a common bus is formed without multiplexers.

Bus with four registers

Take four registers A, B, C and D of 4 bits each. For every register there is a group of four 3-state buffers, one for each bit. The outputs of the four buffers of the same bit position are tied together to make that bit of the bus. A 2-to-4 decoder produces the enable signals. Its two inputs $S_1S_0$ select the register, and each of its four outputs enables the group of buffers of one register.

 S1 S0 --> [ 2-to-4 DECODER ]
            |   |   |   |
           E_A E_B E_C E_D   (enable of each buffer group)
            |   |   |   |
          [buf][buf][buf][buf]   4 buffers per register
            ^   ^   ^   ^
            A   B   C   D        (registers)
            |   |   |   |
            +---+---+---+--->  4-bit common bus

Working

The decoder makes exactly one of its outputs 1 for each value of $S_1S_0$.

Suppose $S_1S_0 = 01$. Only the buffers of B are enabled. Their outputs show the bit values of B on the bus. The buffers of A, C and D are in high impedance, so they do not affect the bus. The data on the bus can then be loaded into any register whose load input is enabled at the clock pulse.

Care is needed in the design. If two groups of buffers were enabled together, two different values would try to drive the same wire. This is a bus conflict, and it can damage the circuit. The decoder prevents it, because it never enables more than one output at a time.

Comparison with the multiplexer bus

A multiplexer bus needs one multiplexer for every bit. A three-state bus replaces the set of multiplexers by buffers and a single decoder. For 8 registers of 16 bits, the multiplexer method needs sixteen 8-to-1 multiplexers. The buffer method needs 128 buffers and one 3-to-8 decoder.

The three-state method also has an important advantage: the bus can be extended simply by connecting one more set of buffers. It is easy to build in integrated circuits, and it can carry data in both directions. Real computer buses use this idea.

A multiplexer (MUX) is a selector. It has many data inputs, a few select lines and one output. The select lines decide which one input is passed to the output. A 4-to-1 MUX has 4 inputs and 2 select lines. It is used to choose one source among many, for example in a bus system.

A decoder does the opposite job. It takes an n-bit binary code and activates exactly one of its $2^n$ output lines. A 3-to-8 decoder has 3 inputs and 8 outputs. It is used to select one register, one memory chip or one device from an address.

General-purpose registers are the CPU registers that a programmer can use freely for any purpose. They are not tied to one special job. They can hold data, operands, intermediate results, or memory addresses (as pointers or index values).

Examples are R0 to R15 in ARM, or AX, BX, CX and DX in the Intel 8086. Instructions can name them directly, as in ADD R1, R2. Because the registers are inside the CPU, they are much faster than memory. Using more of them reduces the number of memory accesses and makes the program run faster.

Processor organization is the way the registers, ALU and control unit inside a CPU are arranged and connected. It decides where operands are kept while an instruction works on them. Three types are common.

Single accumulator organization

One special register, the accumulator (AC), holds one operand and also receives the result. The instruction has one address field for the other operand. For example, ADD X means $AC \leftarrow AC + M[X]$. To compute $Z = X + Y$ the program is LOAD X, ADD Y, STORE Z. It is simple and cheap, but every result passes through AC, so many load and store instructions are needed. Early machines such as the IBM 701 used it.

  Memory ---> [ ALU ] ---> [ AC ] ---+
                 ^                   |
                 +-------------------+

General register organization

A group of registers R1 to R7 can each hold data. Two multiplexers select the two source registers for the ALU, and a decoder selects the destination register. For example, ADD R1, R2, R3 means $R1 \leftarrow R2 + R3$. Data stays in the CPU, so fewer memory accesses are needed and the program is fast. Instructions are longer as they carry register numbers. ARM and RISC-V processors use this type. The program for $Z = X + Y$ is LOAD R1, X, LOAD R2, Y, ADD R3, R1, R2 and STORE R3, Z.

Stack organization

The CPU works with a LIFO stack, and the operations use the top items. Most instructions are zero-address. For example, ADD pops two items and pushes their sum. The program for $Z = X + Y$ is PUSH X, PUSH Y, ADD and POP Z. It suits expressions in reverse Polish notation, and the instructions are very short. But random access to the middle of the stack is not possible. The Burroughs B5500 used it.

Comparison

Most modern processors use the general register organization along with some stack support for subroutine calls.

A stack is a LIFO structure. It can be built in two ways: as a set of CPU registers (register stack), or in a portion of main memory (memory stack). In both, a stack pointer (SP) points to the top item.

Register stack

It is a small group of CPU registers, for example 64 words, organized as a stack. SP is a 6-bit register. Two flip-flops, FULL and EMPTY, signal the end conditions. The push and pop are

$$\text{PUSH: } SP \leftarrow SP + 1,\ M[SP] \leftarrow DR$$

$$\text{POP: } DR \leftarrow M[SP],\ SP \leftarrow SP - 1$$

The test for full or empty is done by checking whether SP has wrapped round to 0.

Memory stack

A part of the main memory is reserved for the stack. SP is a register holding a memory address. It usually starts at a high address and moves down as items are pushed. The push and pop are

$$\text{PUSH: } SP \leftarrow SP - 1,\ M[SP] \leftarrow DR$$

$$\text{POP: } DR \leftarrow M[SP],\ SP \leftarrow SP + 1$$

To find overflow and underflow, SP is compared with the upper and lower limit addresses of the stack area.

Differences

Because main memory is cheap and big, general purpose computers use the memory stack. A register stack is used only where speed matters and a very small stack is enough, for example in a small embedded processor or for a stack of intermediate results.

A stack is a storage structure in which items are inserted and removed only at one end, called the top of the stack. The last item put in is the first one taken out. This is the last-in, first-out (LIFO) rule. A processor keeps a register called the stack pointer (SP) that always holds the address of the top item.

Two operations work on a stack. PUSH inserts a new item on the top, and POP removes the top item. The stack can be built inside the CPU as a set of registers, or as a part of main memory.

Uses of stack in processors

• Evaluation of arithmetic expressions in reverse Polish notation, using zero-address instructions.
• Saving the return address and the local data when a subroutine is called, so that nested and recursive calls work.
• Saving the state of the processor when an interrupt occurs.

For example, to compute $(A+B)*C$ the stack machine runs PUSH A, PUSH B, ADD, PUSH C, MUL. Each operator takes the top two items and leaves the result on the top. No address is given for the operators.

Register stack

A register stack is a small group of registers organized as a stack. Take a stack of 64 words. The stack pointer SP has 6 bits and holds the address of the top. Two flip-flops, FULL and EMPTY, show whether the stack is full or empty. DR is the data register that holds the word to be pushed or the word that is popped.

At the start, $SP = 0$, $EMPTY = 1$ and $FULL = 0$. A push is done by

$$SP \leftarrow SP + 1$$

$$M[SP] \leftarrow DR$$

$$\text{if } SP = 0 \text{ then } FULL \leftarrow 1,\ EMPTY \leftarrow 0$$

After the push of the 63rd item, SP is 63. One more push makes SP wrap round to 0, which sets FULL. A pop is done by

$$DR \leftarrow M[SP]$$

$$SP \leftarrow SP - 1$$

$$\text{if } SP = 0 \text{ then } EMPTY \leftarrow 1,\ FULL \leftarrow 0$$

A push when FULL is set, or a pop when EMPTY is set, is an error and is not allowed. Register stacks are very fast, as no memory access is needed, but they are small.

Memory stack

The same idea works with part of main memory. Then SP points to a memory word. The stack grows toward lower addresses. A push does $SP \leftarrow SP - 1$ and $M[SP] \leftarrow DR$. A pop does $DR \leftarrow M[SP]$ and $SP \leftarrow SP + 1$. This stack can be large, but each access is slower.

In short, a register stack is a fast hardware stack made of registers, with FULL and EMPTY flags to guard its limits.

The effective address (EA) is the actual memory address of the operand. An instruction has an opcode and an address field. In some modes the address field is already the address, but in others it has to be changed by adding a register, or by reading memory, before the true address is known. The addressing mode tells the CPU how to do this. The EA is found by the CPU at execution time.

Calculation in the common modes

In direct addressing the address field gives the address, so

$$EA = A$$

In indirect addressing, the address field gives the location of a word that holds the address, so

$$EA = M[A]$$

In register indirect addressing, a register holds the address, so

$$EA = (R)$$

In relative addressing, the address field is added to the program counter, so

$$EA = PC + A$$

In indexed addressing, the address field is added to an index register, so

$$EA = A + (XR)$$

In base register addressing, an offset is added to a base register, so

$$EA = (BR) + A$$

In immediate addressing there is no effective address, as the operand is in the instruction. In register addressing, the operand is in the register, so no memory address is needed either. In autoincrement mode, EA is the register's value, and then the register is increased.

Worked example

Take an instruction located at 200, with the address field 500 at location 201. Let the register $R = 400$, the index register $XR = 100$, and $M[500] = 800$. After the fetch, $PC = 202$.

$$\text{Direct: } EA = 500$$

$$\text{Indirect: } EA = M[500] = 800$$

$$\text{Register indirect: } EA = 400$$

$$\text{Relative: } EA = 202 + 500 = 702$$

$$\text{Indexed: } EA = 500 + 100 = 600$$

Therefore the same instruction reads from five different locations, depending on the mode.

A note on the mode with autoincrement: it is useful when a loop reads one array element after another. The register points to the element, the instruction uses it, and the register moves on to the next element by itself. This saves a separate add instruction each time.

Direct addressing is simple. Indirect addressing gives a bigger address range and allows pointers, but it is slow. Indexed and relative modes help with arrays and branches. The right mode makes the program shorter and flexible.

In a stack organized computer with zero-address instructions, the arithmetic instructions have no address field. They take their operands from the top two items of the stack and push the result back. Only PUSH and POP name a memory address. So we first write the expression in reverse Polish notation (RPN), where each operator comes after its operands.

The expression is $X = (A-B) * (((C - D * E) / F) / G)$. We convert it by taking the innermost bracket first.

$$A - B \rightarrow AB-$$

$$D * E \rightarrow DE*$$

$$C - DE \rightarrow CDE-$$

$$(C-DE)/F \rightarrow CDE-F/$$

$$((C-DE)/F)/G \rightarrow CDE-F/G/$$

The last operation is the product of the two big brackets.

$$AB-;CDE*-F/G/;*$$

I checked this RPN with a small program. Each letter of the string becomes a PUSH, and each operator becomes one instruction. The program is:

PUSH A      ; stack: A
PUSH B      ; stack: A, B
SUB         ; stack: (A-B)
PUSH C      ; stack: (A-B), C
PUSH D      ; stack: (A-B), C, D
PUSH E      ; stack: (A-B), C, D, E
MUL         ; stack: (A-B), C, (D*E)
SUB         ; stack: (A-B), (C-D*E)
PUSH F      ; stack: (A-B), (C-D*E), F
DIV         ; stack: (A-B), ((C-D*E)/F)
PUSH G      ; stack: (A-B), ((C-D*E)/F), G
DIV         ; stack: (A-B), (((C-D*E)/F)/G)
MUL         ; stack: (A-B)*(((C-D*E)/F)/G)
POP X       ; X <- result

Each SUB, DIV and MUL takes the top item as the second operand and the item below it as the first operand. For example, at the first SUB the top is $DE$ and below it is $C$, so the result is $C - DE$ and not the reverse.

Why the order matters

The operands of a subtraction or a division must be pushed in the right order. The first operand goes in first, so that it lies below the second operand. If $F$ were pushed before the bracket $C - DE$ is complete, the division would give $F/(C-DE)$ instead of the intended one. The RPN form takes care of this automatically.

Check with numbers

Let $A=10, B=4, C=20, D=2, E=3, F=7, G=2$. The stack program works as follows.

$$A-B = 10-4 = 6$$

$$DE = 6,\quad C-DE = 20-6 = 14$$

$$14/F = 14/7 = 2,\quad 2/G = 2/2 = 1$$

$$6 \times 1 = 6$$

The direct calculation of $(10-4)(((20-23)/7)/2)$ also gives 6, so the program is right.

The program has 14 instructions, of which 7 are PUSH, one is POP and 6 are arithmetic. The arithmetic instructions are short because they need no address. The stack never holds more than 4 items at once. This is how a stack computer runs an expression without using any general registers.

Therefore the required program is the 14 instruction sequence given above, ending with POP X. Reading it again from the top, the first three lines compute the value of $(A-B)$, the next nine lines compute the big bracket on the right, and the last MUL joins them.

The effective address (EA) is the memory address from which the operand is finally taken. It depends on the addressing mode. Here the instruction is at location 400 and its address field is at location 401, with value 500. The processor register R1 holds 200.

While the instruction is being fetched, the program counter (PC) moves on. The opcode is read from 400 and the address field from 401. So when the instruction is executed, PC holds the address of the next instruction.

$$PC = 401 + 1 = 402$$

We now go through each mode.

(i) Direct addressing

In direct mode the address field is itself the effective address. There is no calculation.

$$EA = 500$$

The operand is the word stored at memory location 500.

(ii) Immediate addressing

In immediate mode the address field is not an address at all. It is the operand. So the operand is the number 500 and no effective address exists. The processor does not go to memory for the operand, which makes this mode the fastest of all memory-type modes. We may say that the value used is found at location 401, the address field itself.

(iii) Relative addressing

In relative mode the address field is added to the content of the program counter. The PC already holds the address of the next instruction, which is 402.

$$EA = PC + 500$$

$$EA = 402 + 500 = 902$$

The operand is at location 902. This mode is used in branch instructions, because a jump is described as a distance from the present position.

(iv) Register indirect addressing

In register indirect mode the register named in the instruction holds the address of the operand. Here that register is R1.

$$EA = (R1) = 200$$

The operand is at location 200. The value 500 in the address field is not used in this mode.

(v) Indexed addressing with R1 as index register

In indexed mode the content of the index register is added to the address field.

$$EA = 500 + (R1)$$

$$EA = 500 + 200 = 700$$

The operand is at location 700. This mode is used to reach elements of an array. The address field gives the start of the array, and the index register selects one element.

Summary

Therefore the five modes give five different results from the same instruction, which shows why the addressing mode matters. One small point: if the question wants the PC value as 401 instead of 402, the relative result would be 901. The standard rule is that the PC is incremented after the fetch, so 902 is the accepted answer.

Processor organization means the way the registers, the ALU and the control unit inside the CPU are arranged and connected, and how the instructions use them to hold and process data. The CPU must fetch instructions, fetch operands, process them and store results. So it needs storage for temporary values. How that storage is arranged gives the type of organization.

Based on this, three types of processor organization are used.

(a) Single accumulator organization

All the operations use one special register called the accumulator (AC). One operand is always in AC and the result is also stored back in AC. The instruction has just one address field, for the second operand in memory. For example, ADD X means $AC \leftarrow AC + M[X]$.

  Memory ---> [ ALU ] ---> [ AC ] ---+
                 ^                   |
                 +-------------------+

This organization is simple and cheap and needs short instructions. But every result must pass through AC, so the program has many load and store instructions, and it is slow. Early computers such as the IBM 701 used it.

(b) General register organization

Here a set of registers, say R1 to R7, is available. Any of them can hold an operand or a result. A multiplexer chooses two source registers for the ALU inputs, a decoder chooses the destination register, and the ALU result goes back to the register file. The control word has the fields for source 1, source 2, destination and the ALU operation. An example instruction is ADD R1, R2, R3, which means $R1 \leftarrow R2 + R3$.

  R1 R2 R3 ... R7
   |  |  |      |
  [MUX A]   [MUX B]
      \       /
       [ ALU ]  <- operation select
          |
   (to registers via decoder)

This organization is fast, because the data stays inside the CPU and fewer memory accesses are needed. Instructions are longer, since they hold two or three register numbers. Most modern CPUs, such as the ARM and RISC-V, use it.

(c) Stack organization

Here the CPU has a stack (LIFO) in memory or in registers, and the operations work on the top of the stack. Most instructions are zero-address. For example, ADD pops two values, adds them and pushes the result. Other instructions are PUSH X and POP X.

This is very good for evaluating expressions written in reverse Polish notation, and it gives very short instructions. It is also used for subroutine calls. However, random access to items in the middle of the stack is hard. Burroughs B5500 used it.

Comparison

In short, the choice depends on cost, speed and the program length that the designer wants.

In infix notation the operator is written between its two operands, as in $A + B$. In reverse Polish notation (RPN), also called postfix, the operator comes after its operands, as in $A,B,+$. RPN needs no brackets because the order of operators is fixed by their position. This is why stack machines use it.

A computer can evaluate a postfix string in one left-to-right scan, without looking back or worrying about priorities. This makes the compiler's work simple and the hardware fast. Humans find infix easier to read, so the compiler converts infix to postfix before generating code.

To convert, we follow the normal precedence rules. Multiplication and division are done before addition and subtraction. Operators of equal rank are done from left to right. Brackets are done first.

(i) $AB+CD+E*F$

There are three products and two additions. The products are done first, so we write each of them in postfix form.

$$AB \rightarrow AB$$

$$CD \rightarrow CD$$

$$EF \rightarrow EF$$

The expression is now (AB*) + (CD*) + (EF*). The additions go from left to right. The first addition joins the first two products.

$$AB*;CD*;+$$

The second addition joins this result with the third product.

$$AB*;CD*;+;EF*;+$$

Therefore the RPN is $ABCD+EF*+$.

(ii) $A[B+CD+E]/F*(G+H)$**

The question has a printed typing error in the middle ("CCD"). We take the intended expression as $A[B+CD+E]/F(G+H)$.

Inside the square bracket, the product is done first, so $CD$ becomes $CD$. Then the two additions go from left to right.

$$B+CD+E \rightarrow B,CD,+,E,+$$

Call this bracket $X$. The brackets $(G+H)$ become $GH+$. The remaining expression is $AX/F(GH+)$. Multiplication and division have the same rank, so they go from left to right. First comes $A*X$, then the division by $F$, then the product with $GH+$.

$$AX \rightarrow A,X,$$

$$AX*/F \rightarrow AX*,F,/$$

$$AXF/(GH+) \rightarrow AXF/,GH+,$$

Putting $X = BCD*+E+$ back, we get the final answer.

$$ABCD*+E+F/GH+$$

I checked both results with a small stack-based conversion program, and they match.

A quick check of part (ii) also works. Take $A=2, B=1, C=2, D=3, E=4, F=2, G=5, H=1$. The infix value is $2*(1+6+4)/26 = 66$. Scanning $2,1,2,3,,+,4,+,,2,/,5,1,+,$ with a stack also leaves 66.

Let us check part (i) with numbers. Take $A=2, B=3, C=4, D=5, E=6, F=7$. The infix value is $23 + 45 + 67 = 6 + 20 + 42 = 68$. Now evaluate $2345*+67*+$ with a stack.

$$\text{push }2,3 \rightarrow \text{multiply} \rightarrow 6$$

$$\text{push }4,5 \rightarrow \text{multiply} \rightarrow 20 \rightarrow \text{add} \rightarrow 26$$

$$\text{push }6,7 \rightarrow \text{multiply} \rightarrow 42 \rightarrow \text{add} \rightarrow 68$$

Both methods give 68, so the conversion is correct. The same idea gives zero-address instructions in a stack computer.

To verify an RPN string by hand, scan from left to right. Push each operand on a stack. When an operator comes, pop two operands, apply the operator and push the result back. At the end one value remains, which is the value of the expression.

The addressing mode tells the CPU how to find the operand of an instruction from the address field. An instruction has an opcode and an address field. The mode decides whether the address field itself is the operand, or a memory address, or a register number. The final address of the operand in memory is called the effective address (EA).

Main addressing modes

In the implied mode, the operand is fixed by the opcode. For example, "complement accumulator" works on AC without any address field. Stack instructions such as ADD also use this mode.

In the immediate mode, the address field contains the operand itself. No memory access is needed to get it, so it is fast. It is used for constants. For example, ADD #5 adds the number 5.

In the register mode, the operand is inside a CPU register named in the instruction. For example, ADD R1 uses the value in R1. It is very fast and needs few bits.

In the register indirect mode, the register holds the memory address of the operand. So $EA = (R1)$. This is useful for pointers.

In the autoincrement or autodecrement mode, the register works as in register indirect, but its value is increased (or decreased) automatically after (or before) the access. It is used to walk through an array.

In the direct mode, the address field is the effective address. So $EA = A$. One memory access reaches the operand.

In the indirect mode, the address field gives the location where the real address is stored. So $EA = M[A]$. It needs two memory accesses and allows pointers.

In the relative mode, the address field is added to the program counter. So $EA = PC + A$. It is used for branches and makes code position independent.

In the indexed mode, the address field is added to an index register. So $EA = A + (XR)$. It is used to access array elements.

In the base register mode, a base register holds the starting address of a block, and the address field is an offset from it. So $EA = (BR) + A$. It is used to move programs in memory.

Example

Take an instruction at address 200 whose address field (at 201) is 500. Let $R1 = 400$ and $XR = 100$. The PC has already moved to 202 after fetching.

The table shows that the same address field gives different operands in different modes. Modes make a program shorter, more flexible and easier to relocate, at the cost of more complex hardware and extra memory accesses for some modes.

A stack is a list of data items in which an item is added or removed only at one end, called the top. It works on the last-in, first-out (LIFO) rule. A register called the stack pointer (SP) always holds the address of the top item. Adding an item is a PUSH and removing one is a POP. Stack organization is used for subroutine calls, interrupts and expression evaluation.

(i) Register stack

Here the stack is a set of CPU registers. Suppose it has 64 words, so SP is a 6-bit register. A word is moved through the data register DR. Two flip-flops, FULL and EMPTY, show the state of the stack.

   +----------+
 63|          |
   |   ...    |
  3|   C      |  <- SP = 3, top is C
  2|   B      |
  1|   A      |
  0|          |
   +----------+

Initially $SP = 0$, $EMPTY = 1$ and $FULL = 0$. The PUSH operation is

$$SP \leftarrow SP + 1$$

$$M[SP] \leftarrow DR$$

$$\text{if } SP = 0 \text{ then } FULL \leftarrow 1,\ EMPTY \leftarrow 0$$

SP becomes 0 again only after the last location (63) is filled, because the 6-bit counter wraps around. The POP operation is

$$DR \leftarrow M[SP]$$

$$SP \leftarrow SP - 1$$

$$\text{if } SP = 0 \text{ then } EMPTY \leftarrow 1,\ FULL \leftarrow 0$$

A push is not allowed when FULL is 1, and a pop is not allowed when EMPTY is 1. A register stack is very fast, but its size is small and fixed.

(ii) Memory stack

Here a part of main memory is used as the stack. Three segments exist in memory: the program, the data and the stack. The program counter points to the program, an address register points to the data, and SP points to the top of the stack. The stack usually grows towards lower addresses. Suppose SP starts at 4001 and the stack uses the addresses 4000 down to 3000. The PUSH operation is

$$SP \leftarrow SP - 1$$

$$M[SP] \leftarrow DR$$

The POP operation is

$$DR \leftarrow M[SP]$$

$$SP \leftarrow SP + 1$$

Here the limits are checked by comparing SP with the two end addresses. The stack can be large and the size can be changed, but every push and pop needs a memory access, so it is slower than a register stack.

Example of memory stack use

Start with $SP = 4001$. Push the values 10 and then 20. After the first push SP is 4000 and M[4000] holds 10. After the second push SP is 3999 and M[3999] holds 20. A pop now returns 20, the last item pushed, and SP goes back to 4000. This shows the LIFO rule.

Difference in short

Both kinds help to evaluate expressions written in reverse Polish notation. Operands are pushed. An operator pops two values and pushes the result. No address field is needed, so the instructions are zero-address instructions.