Computer Organization and Architecture important questions

Hardwired control unit

A hardwired control unit makes the control signals with a fixed network of logic gates, decoders and flip-flops. There is no control memory. The signals depend on the opcode, the timing pulse and the status flags.

Design

 IR (opcode) -> [Instruction decoder] -> D0 ... D7 --+
                                                     v
 Clock -> [Sequence counter] -> [Timing decoder] --> [Control logic] -> control signals
              ^   T0 ... T15                          ^   (AND, OR gates)
              |                                       |
         clear (end of instruction)           Flags, mode bit I, interrupt R

The parts are:

• Instruction register and decoder. The opcode bits go to a decoder, for example 3 to 8. It makes one line $D_0$ to $D_7$ high for the current instruction.
• Sequence counter and timing decoder. The counter counts clock pulses. A 4 to 16 decoder makes the timing signals $T_0$ to $T_{15}$. Each signal gives one time slot for a micro operation.
• Control logic network. AND and OR gates combine the decoder lines, the timing signals and the flags. There is a Boolean equation for each control signal. For example, the signal to load AR is

$$AR\text{ load} = R'T_0 + R'T_2,D_7,I'$$

• Flags and condition bits. The zero flag, the carry flag and the mode bit I affect some of the signals.

Working

At $T_0$, $T_1$ and $T_2$ the same fetch signals appear for every instruction. After decoding, the line $D_i$ of the instruction and the later timing signals $T_3$, $T_4$, ... create the signals for the execute part. At the end, a signal clears the sequence counter, and the next instruction is fetched.

Advantages

• Very fast, since the signals come straight from gates.
• Good for RISC and pipelined designs.
• No control memory is needed.

Disadvantages

• The design is complex for a large instruction set, as every signal needs its own equation.
• It is hard to change. A new instruction means a new circuit.
• Error fixing is difficult and costly.
• Less regular, and it takes a long design time.

Use. Hardwired control is chosen in RISC processors, where the instructions are few and simple, so the equations are small and the speed matters more than flexibility.

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.

Working of DMA

In Direct Memory Access, an I/O device exchanges a block of data with main memory without the CPU copying each word. The CPU sets up the transfer and then does other work. The steps in the working are as follows.

The CPU writes the starting memory address, the number of words and the direction into the DMA controller. The device then raises a DMA request. The controller sends a bus request to the CPU. The CPU finishes its current cycle, releases the buses and sends a bus grant. The controller puts the address on the address bus and sends the memory and device control signals, and one word moves directly between the device and memory. The controller increases the address and decreases the count. This repeats until the count is zero. At that point the controller returns the bus to the CPU and sends an interrupt to say that the transfer is complete.

The DMA controller

The controller has these main parts:

• Address register: it holds the address of the next memory word.
• Word count register: it holds the number of words still to be moved.
• Control register: it holds the direction and the mode (burst or cycle stealing).
• Data buffer: it connects the controller to the data bus.
• Bus request and bus grant lines: these connect it to the CPU for taking the buses.
• DMA request and acknowledge lines: these connect it to the I/O device.

The CPU can read and write these registers through the register select input, in the same way as for any other interface.

Advantages over other I/O methods

The main advantages of DMA are that it gives the highest data rate, since words are not routed through the CPU, and it frees the CPU for other tasks. It has far less overhead than interrupts because only one interrupt is used for a complete block. Its disadvantages are the extra hardware and the need to share the memory bus, which can slow the CPU a little during the transfer.

Booth's algorithm multiplies signed 2's complement numbers. For each bit pair $Q_0Q_{-1}$: $10$ subtracts $M$, $01$ adds $M$, otherwise nothing. Then it shifts right (ASR).

Here $M = -5 = 1011$, $-M = 0101$ and $Q = 3 = 0011$.

$AQ = 11110001 = -15$. Therefore $(-5) \times 3 = -15$.

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.

Hardwired control unit

A hardwired control unit makes the control signals with a fixed network of logic gates, decoders and flip-flops. There is no control memory. The signals depend on the opcode, the timing pulse and the status flags.

Design

 IR (opcode) -> [Instruction decoder] -> D0 ... D7 --+
                                                     v
 Clock -> [Sequence counter] -> [Timing decoder] --> [Control logic] -> control signals
              ^   T0 ... T15                          ^   (AND, OR gates)
              |                                       |
         clear (end of instruction)           Flags, mode bit I, interrupt R

The parts are:

• Instruction register and decoder. The opcode bits go to a decoder, for example 3 to 8. It makes one line $D_0$ to $D_7$ high for the current instruction.
• Sequence counter and timing decoder. The counter counts clock pulses. A 4 to 16 decoder makes the timing signals $T_0$ to $T_{15}$. Each signal gives one time slot for a micro operation.
• Control logic network. AND and OR gates combine the decoder lines, the timing signals and the flags. There is a Boolean equation for each control signal. For example, the signal to load AR is

$$AR\text{ load} = R'T_0 + R'T_2,D_7,I'$$

• Flags and condition bits. The zero flag, the carry flag and the mode bit I affect some of the signals.

Working

At $T_0$, $T_1$ and $T_2$ the same fetch signals appear for every instruction. After decoding, the line $D_i$ of the instruction and the later timing signals $T_3$, $T_4$, ... create the signals for the execute part. At the end, a signal clears the sequence counter, and the next instruction is fetched.

Advantages

• Very fast, since the signals come straight from gates.
• Good for RISC and pipelined designs.
• No control memory is needed.

Disadvantages

• The design is complex for a large instruction set, as every signal needs its own equation.
• It is hard to change. A new instruction means a new circuit.
• Error fixing is difficult and costly.
• Less regular, and it takes a long design time.

Use. Hardwired control is chosen in RISC processors, where the instructions are few and simple, so the equations are small and the speed matters more than flexibility.

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.

Working of DMA

In Direct Memory Access, an I/O device exchanges a block of data with main memory without the CPU copying each word. The CPU sets up the transfer and then does other work. The steps in the working are as follows.

The CPU writes the starting memory address, the number of words and the direction into the DMA controller. The device then raises a DMA request. The controller sends a bus request to the CPU. The CPU finishes its current cycle, releases the buses and sends a bus grant. The controller puts the address on the address bus and sends the memory and device control signals, and one word moves directly between the device and memory. The controller increases the address and decreases the count. This repeats until the count is zero. At that point the controller returns the bus to the CPU and sends an interrupt to say that the transfer is complete.

The DMA controller

The controller has these main parts:

• Address register: it holds the address of the next memory word.
• Word count register: it holds the number of words still to be moved.
• Control register: it holds the direction and the mode (burst or cycle stealing).
• Data buffer: it connects the controller to the data bus.
• Bus request and bus grant lines: these connect it to the CPU for taking the buses.
• DMA request and acknowledge lines: these connect it to the I/O device.

The CPU can read and write these registers through the register select input, in the same way as for any other interface.

Advantages over other I/O methods

The main advantages of DMA are that it gives the highest data rate, since words are not routed through the CPU, and it frees the CPU for other tasks. It has far less overhead than interrupts because only one interrupt is used for a complete block. Its disadvantages are the extra hardware and the need to share the memory bus, which can slow the CPU a little during the transfer.

Booth's algorithm multiplies signed 2's complement numbers. For each bit pair $Q_0Q_{-1}$: $10$ subtracts $M$, $01$ adds $M$, otherwise nothing. Then it shifts right (ASR).

Here $M = -5 = 1011$, $-M = 0101$ and $Q = 3 = 0011$.

$AQ = 11110001 = -15$. Therefore $(-5) \times 3 = -15$.

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.

2D organization

In 2D organization, the memory cells are arranged as an array in which each row is one word. A single decoder takes all $n$ address bits and activates one of the $2^n$ word lines. Then all the bits of that word are read or written together.

 Address (n bits) --> [ n to 2^n decoder ] --> word lines
                                                 |
                                       [ cell array: 2^n words ]
                                                 |
                                             data bits

Advantages: the structure is simple, the design is easy, and a whole word is accessed at once, so it is fast for small memories. Disadvantages: the decoder needs $2^n$ output lines. For $64\text{K}$ words, that is 65536 lines and gates. The decoder is large, costly and slow, so it is unsuitable for big memories.

2 1/2D organization

In 2 1/2D organization the cells are arranged in a square-like array. The address is split into a row part and a column part. A row decoder selects one row and a column decoder (with a multiplexer) selects one column. The cell at the crossing is accessed.

 Row address (n/2)  --> [ row decoder ] --> rows
                                              |
                                        [ cell array ]
                                              |
 Col address (n/2)  --> [ column decoder / mux ] --> data

For $64\text{K} \times 1$ bits, the array is $256 \times 256$. Each decoder has 256 outputs, so the total is

$$256 + 256 = 512$$

instead of 65536 in 2D.

Advantages: the decoder size is very small, so the cost and area are low. It suits large chips, and refresh of a whole row is easy for DRAM. Disadvantages: two decoding steps are needed, so the access control is a little more complex. One cell is selected at a time per array, so several arrays must be used in parallel to get a wider word.

Types of instructions

An instruction tells the CPU one operation. By their job, instructions fall into these groups.

• Data transfer: move data between registers and memory, for example LOAD, STORE, MOV, PUSH, POP.
• Arithmetic: ADD, SUB, MUL, DIV, INC, DEC.
• Logical and shift: AND, OR, XOR, NOT, shifts and rotates.
• Program control: JMP, conditional branches such as JZ, CALL and RET. They change the value of PC.
• Input and output: IN and OUT, which move data to and from devices.

Instruction formats

An instruction word has an opcode, which tells the operation, and operand fields, which tell where the data is. It may also have a mode field for the addressing mode. The number of address fields decides the format.

Take the statement $X = (A + B) \times (C + D)$ to see each format.

Three-address format. Each instruction has two sources and one destination.

ADD R1, A, B      ; R1 = A + B
ADD R2, C, D      ; R2 = C + D
MUL X, R1, R2     ; X = R1 * R2

The program is short, but the instructions are long.

Two-address format. The first operand is also the destination.

MOV R1, A
ADD R1, B
MOV R2, C
ADD R2, D
MUL R1, R2
MOV X, R1

This is the common format in x86 processors.

One-address format. The accumulator AC is the second operand and the destination.

LOAD A
ADD B
STORE T
LOAD C
ADD D
MUL T
STORE X

Zero-address format. Operands are taken from the top of a stack, so the instruction names no address. Only PUSH and POP name a memory address.

PUSH A
PUSH B
ADD
PUSH C
PUSH D
ADD
MUL
POP X

The programs use 3, 6, 7 and 8 instructions. More address fields mean fewer instructions, but longer ones. A zero-address instruction is the shortest, but it needs more of them.

Choosing a format. The three-address format is used in RISC machines such as MIPS, where registers hold the operands, so the fields are short. The two-address format is common in CISC machines such as x86. The one-address format was used in early machines with a single accumulator. The zero-address format is used in stack machines, for example in the evaluation of expressions and in the Java virtual machine. The choice is a balance between program length, instruction length and speed.

Instruction length. For example, if the opcode is 8 bits and each register field is 5 bits, a three-register instruction needs $8 + 3 \times 5 = 23$ bits, and it fits in a 32 bit word with room for a mode field.

RISC architecture

RISC means Reduced Instruction Set Computer. Its idea is that most programs use a few simple instructions most of the time. So the processor is built to run these very fast, and complex jobs are made from many simple instructions.

Features

• A small set of simple instructions, of fixed length, such as 32 bits.
• Each instruction takes one clock cycle, in most cases.
• Only LOAD and STORE instructions access memory. All other instructions work on registers. This is the load-store architecture.
• A large set of registers, often with overlapping register windows, which makes the procedure calls fast.
• Few and simple addressing modes.
• A hardwired control unit, with no microcode.
• A pipeline that is easy to build and keep full, as all the instructions are alike.

Advantages

• Higher speed, because of one-cycle instructions and good pipelining.
• A simple control unit, so a smaller chip, lower design time and lower cost.
• Less power use, which is the reason ARM is used in phones.
• Easier for compilers to optimize, as the instructions are regular.

Disadvantages. The programs are longer, as more instructions are needed, and they need more memory for code.

Comparison of RISC and CISC

In short, RISC moves the complexity from the hardware to the software, and CISC does the reverse.

The cache is small, so the memory block that goes into a cache line must be decided by a rule. This rule is the mapping technique. To compare the three, take a 16-bit address, a block of 4 words, and a cache of 256 lines.

i. Direct mapping

Each memory block goes to one fixed cache line:

$$\text{line} = \text{block number} \bmod 256$$

The address has three fields: tag, line and word. The word field has 2 bits, the line field has 8 bits and the tag has the remaining bits:

$$16 - 8 - 2 = 6 \text{ bits}$$

The line field selects the cache line, and its stored tag is compared with the tag of the address. If they are equal, it is a hit. This needs only one comparator and no replacement rule, so it is simple and fast. But blocks that map to the same line replace each other again and again, so the hit ratio can be poor.

ii. Associative mapping

A memory block can be placed in any cache line. The address has only a tag and a word field. Here the tag has $16 - 2 = 14$ bits and the word has 2 bits. The tag is compared with the tags of all 256 lines at the same time, using associative memory. This is the most flexible and gives the highest hit ratio, because there are no conflict misses. But it needs 256 comparators, so it is costly and slow, and it needs a replacement algorithm such as LRU or FIFO.

iii. Set-associative mapping

The lines are grouped into sets. A block maps to one fixed set, but it can go to any line in that set. For a 4-way cache, there are $256/4 = 64$ sets. The set field has 6 bits, the word field has 2 bits and the tag has

$$16 - 6 - 2 = 8 \text{ bits}$$

Only the 4 tags of one set are compared. It reduces conflict misses and costs less than the associative method. A replacement rule is needed only inside the set.

I/O interface

An I/O interface is the hardware circuit between the CPU buses and an I/O device. It contains registers (data, status and control), an address decoder, and timing and interrupt logic. The CPU reads and writes these registers to control the device.

Functions of an I/O interface

• Device selection: it decodes the address on the address bus and selects the correct device.
• Data buffering: it holds data in a register so that the fast CPU and the slow device can each work at their own speed.
• Data conversion: it changes the format of the data, for example parallel to serial and serial to parallel.
• Signal conversion: it matches the voltage levels and the timing of the device to those of the CPU.
• Control and timing: it gives commands to the device, and makes the read, write and handshake signals in the right order.
• Status reporting: it tells the CPU if the device is ready, busy or in error.
• Interrupt generation: it sends an interrupt request when the device needs service.
• Error detection: it can check for parity or framing errors in the data.

 CPU buses          I/O interface           Device
 Data    <==>   [data buffer      ]  <==>   data
 Address  ==>   [address decoder  ]
 Control <==>   [control / status ]  <==>   signals
 Interrupt <==  [interrupt logic  ]

Why an interface is needed

The CPU and the I/O devices are very different, so a direct connection is not possible.

Devices also differ from each other in the form of data and the operations they accept. Without an interface, the CPU would have to know the details of each device and would waste time waiting for slow ones. An interface gives the CPU one simple and uniform way to deal with every device. It also protects the CPU from the electrical and timing problems of the device.

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 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.

Virtual memory is a technique that gives a program the feeling of a very large main memory, bigger than the real RAM. The program uses virtual addresses. The system keeps the active parts in main memory and the rest on the disk, and it moves parts in and out as needed. The address translation is done by hardware, using a page table, so the programmer does not need to manage it.

A carry look-ahead adder finds all carries at once. It uses $G_i = A_iB_i$ and $P_i = A_i \oplus B_i$, with $C_{i+1} = G_i + P_iC_i$ and $S_i = P_i \oplus C_i$.

Example: add $A = 1011$ and $B = 0110$ with $C_0 = 0$. Here $G = 0010$ and $P = 1101$ (bit 3 to bit 0). The look-ahead equations give $C_1 = 0$, $C_2 = G_1 = 1$, $C_3 = G_2 + P_2G_1 = 1$ and $C_4 = 1$. The sums $P_i \oplus C_i$ are $S_3S_2S_1S_0 = 0001$, so the result is $10001 = 17$, which equals $11 + 6$.

Serial communication sends the bits of data one after another over a single line. For the receiver to understand the bits, it must know where each bit and character starts and ends. There are two ways to do this.

Synchronous communication

The sender and the receiver work with the same clock. Either the clock is sent on a separate line, or it is recovered from the data signal. Data is sent in large blocks (frames), which start with one or more synchronising characters (SYN) and end with an end marker. There are no start and stop bits for each character. Examples are the HDLC and SDLC protocols, SPI and Ethernet.

Asynchronous communication

The sender and the receiver have no common clock. Each character is sent in its own frame, with a start bit (0) in front and one or two stop bits (1) at the end. A parity bit may be added. The receiver synchronises on the falling edge of each start bit and reads the following bits at the agreed baud rate. Examples are the RS-232 serial port, a UART and a keyboard link.

 Idle  Start  D0 D1 D2 D3 D4 D5 D6 D7  Parity  Stop  Idle
 ‾‾‾‾|_____|   data bits (8)              |‾‾‾‾‾|‾‾‾

For example, to send the character "A" (ASCII 01000001) with one start bit, 8 data bits and one stop bit, the frame is 10 bits long. Only 8 of these carry data.

Differences

In short, synchronous communication is better for fast, steady transfer of large amounts of data, and asynchronous communication is better for slow, irregular transfers such as typing on a keyboard.