BSc CSIT (TU) Science Computer Architecture (BSc CSIT, CSC208) Question Paper 2079 Nepal

Binary Adder-Subtractor Circuit

A combined adder-subtractor is built from an n-bit parallel binary adder (a chain of full adders) plus an XOR gate on each B input and a mode-control line $M$.

• Each bit of input $B$ passes through an XOR gate whose other input is $M$.
• The control line $M$ is also fed to the carry-in $C_0$ of the least-significant full adder.

Operation:

• When $M = 0$: each XOR output equals $B_i$ and $C_0 = 0$, so the circuit computes $A + B$ (addition).
• When $M = 1$: each XOR output equals $\overline{B_i}$ (1's complement of B) and $C_0 = 1$ adds one, giving the 2's complement of B. Thus the circuit computes $A + \overline{B} + 1 = A - B$ (subtraction).

The overflow for signed numbers is detected by $V = C_n \oplus C_{n-1}$.

        M ---+----+----+-----------+
             |    |    |           |
   B3  B2  B1  B0   (each XORed with M)
    |    |    |    |
  [FA]<-[FA]<-[FA]<-[FA]<-- C0 = M
    |    |    |    |
   S3   S2   S1   S0      Cout = C4

Booth's Multiplication Algorithm

Booth's algorithm multiplies two signed 2's-complement numbers by examining pairs of bits and reduces the number of add/subtract operations over runs of identical bits.

Registers: $A$ (accumulator, initially 0), $Q$ (multiplier), $Q_{-1}$ (extra bit, initially 0), $M$ (multiplicand). Count = number of bits $n$.

Rule (inspect $Q_0 Q_{-1}$):

After the operation, perform an arithmetic shift right (ASR) of the combined register $A\,Q\,Q_{-1}$. Repeat $n$ times. The result is in $A\,Q$.

Multiply (−5) × (3) using Booth's Algorithm

Use 4-bit 2's complement.

• Multiplicand $M = +3 = 0011$, so $-M = 1101$.
• Multiplier $Q = -5 = 1011$.
• $A = 0000$, $Q_{-1} = 0$, $n = 4$.

Result $A\,Q = 1111\,0001$.

This is an 8-bit 2's complement value. Its 2's complement is $0000\,1111 = 15$, so $1111\,0001 = -15$.

Control Unit

The control unit (CU) is the part of the CPU that directs the operation of the processor. It generates control signals that coordinate the activities of the ALU, registers, memory, and I/O by fetching instructions, decoding them, and generating the timing and sequencing signals needed to execute each micro-operation in the correct order. It does not perform data processing itself; it tells the other units what to do and when.

There are two ways of designing a control unit: hardwired and microprogrammed.

Hardwired Control Unit

The control logic is implemented with fixed digital hardware — combinational logic gates, decoders, flip-flops, counters, and sequential circuits. The control signals are produced directly as Boolean functions of the instruction opcode, status flags, and timing signals.

Advantages:

• Very fast, because control signals are generated directly by hardware.
• Optimized, used in RISC and high-performance processors.

Disadvantages:

• Difficult to design, modify, or extend — adding a new instruction requires redesigning the circuit.
• Complex for processors with large instruction sets; hard to debug.

Microprogrammed Control Unit

Control signals are stored as microinstructions in a special memory called the control memory (control store). Executing an instruction means sequencing through the corresponding microprogram; each microinstruction supplies the control signals for one step. A control address register (CAR) and sequencer select the next microinstruction.

Advantages:

• Flexible — the instruction set can be changed or extended just by modifying the microprogram (firmware), not the hardware.
• Simpler, systematic design; easier to debug and maintain; good for complex CISC instruction sets.

Disadvantages:

• Slower, because each control signal requires fetching a microinstruction from control memory.
• Requires extra control memory; more expensive in time.

Comparison

Cache Memory

Cache memory is a small, very fast memory (usually SRAM) placed between the CPU and main memory. It holds copies of the most frequently/recently used instructions and data so that the CPU can access them without waiting for slower main memory. It exploits the principle of locality (temporal and spatial locality) to reduce average memory access time. When the CPU needs data, it first checks the cache: a hit means the data is found in cache, while a miss means it must be fetched from main memory and copied into the cache.

Main memory is divided into blocks and cache into lines (frames) of the same size. A mapping function decides which main-memory block goes to which cache line.

1. Direct Mapping

Each main-memory block can be placed in exactly one cache line, given by:

The address is split into Tag | Line(Index) | Word(Offset).

  Address:  [   Tag   |  Line  |  Word  ]

• Advantage: simple and cheap to implement; fast lookup (only one line to compare).
• Disadvantage: high conflict misses — two blocks mapping to the same line keep replacing each other.

2. Associative (Fully Associative) Mapping

A main-memory block can be placed in any cache line. The address is split into just Tag | Word. To find a block, the tag is compared (in parallel) with the tags of all lines using associative (content-addressable) memory.

  Address:  [        Tag        |  Word  ]

• Advantage: most flexible; lowest conflict miss rate; full use of cache.
• Disadvantage: expensive — needs a comparator for every line; requires a replacement algorithm (LRU/FIFO).

3. Set-Associative Mapping

A compromise: the cache is divided into sets, each containing $k$ lines (a k-way set-associative cache). A block maps to one set, but can occupy any line within that set:

The address is split into Tag | Set | Word. Only the $k$ tags in the selected set are compared.

  Address:  [   Tag   |  Set  |  Word  ]

• Advantage: fewer conflict misses than direct mapping, cheaper than fully associative.
• Disadvantage: needs $k$ comparators and a replacement policy per set; moderate complexity.

Summary: Direct mapping = 1 possible line; fully associative = any line; set-associative ($k$-way) = any of $k$ lines in one set. Set-associative is the most commonly used because it balances cost and performance.

IEEE 754 Single Precision Floating Point

A single-precision (32-bit) IEEE 754 number is divided into three fields:

The value of a normalized number is:

• S = 0 for positive, 1 for negative.
• E is stored with a bias of 127 (so the actual exponent = $E - 127$).
• M is the fraction; a hidden leading 1 is assumed (the $1.M$ normalized form), giving 24 bits of precision.

Example: Represent $(13.25)_{10}$

1. Binary: $13.25 = 1101.01_2$.
2. Normalize: $1101.01 = 1.10101 \times 2^{3}$.
3. Sign: positive $\Rightarrow S = 0$.
4. Exponent: $E = 3 + 127 = 130 = 10000010_2$.
5. Mantissa: fraction after the point = $10101$, padded to 23 bits: $10101000000000000000000$.

Result:

0 10000010 10101000000000000000000

In hex this is 0x41540000.

Memory Hierarchy

The memory hierarchy organizes a computer's storage into levels arranged by speed, cost per bit, and capacity. As we move down the hierarchy, speed and cost-per-bit decrease while capacity increases; as we move up, memory gets faster, smaller, and more expensive. The goal is to give the CPU the illusion of a large, fast memory at low cost by keeping frequently used data in faster levels (exploiting locality of reference).

            ^  faster, costlier, smaller
            |   +----------------+
            |   |   Registers    |   (inside CPU)
            |   +----------------+
            |   |  Cache (L1/L2/L3) |  (SRAM)
            |   +----------------+
            |   |  Main Memory (RAM) |  (DRAM)
            |   +----------------+
            |   | Secondary Storage |  (SSD/HDD)
            |   +----------------+
            v   | Tertiary/Backup  |  (tape, optical)
                +----------------+
  slower, cheaper, larger

Levels (top to bottom):

1. Registers — fastest, inside the CPU, hold operands currently in use; smallest capacity.
2. Cache memory (L1, L2, L3) — fast SRAM holding recently used data/instructions.
3. Main memory (RAM) — DRAM, holds the programs and data currently running.
4. Secondary storage — SSD/HDD, large, non-volatile, slower; stores files permanently.
5. Tertiary / backup storage — magnetic tape, optical disks for archival.

The registers, cache, and main memory are accessed directly by the CPU (primary memory), while secondary and tertiary storage are non-volatile and accessed via I/O.

Interrupt

An interrupt is a signal to the processor — generated by hardware or software — that temporarily suspends the normal execution of the current program so that the CPU can attend to a higher-priority event. The CPU saves its current state (program counter and registers), transfers control to an interrupt service routine (ISR) through the interrupt vector, services the event, and then restores the saved state to resume the interrupted program. Interrupts allow the CPU to respond to events asynchronously instead of continuously polling devices, improving efficiency.

Types of Interrupts

1. Hardware Interrupts — generated by external hardware devices (keyboard, disk, timer, I/O). Subdivided into:

   • Maskable interrupts: can be ignored/disabled by the CPU (e.g., normal device interrupts via the INTR line).
   • Non-maskable interrupts (NMI): cannot be disabled; used for critical events like power failure or memory errors.

2. Software Interrupts — generated by an instruction within a program (e.g., INT n system calls, traps). Used by programs to request operating-system services.

3. Internal Interrupts / Exceptions (Traps) — caused by error conditions during instruction execution, such as divide-by-zero, overflow, invalid opcode, or page fault. They are synchronous with the program.

(Interrupts may also be classified as vectored — the device supplies the ISR address — vs non-vectored — a fixed ISR address is used.)

System Bus

A system bus is a set of parallel electrical conductors (wires) that connect the major components of a computer — the CPU, main memory, and I/O devices — and carry data, addresses, and control signals between them. It is a shared communication pathway: only one device can drive the bus at a time, so an arbitration scheme controls access. The system bus is logically divided into three functional groups.

1. Address Bus

Carries the address of the memory location or I/O port that the CPU wants to access. It is unidirectional (CPU → memory/I/O). Its width determines the maximum addressable memory: an $n$-bit address bus can address $2^n$ locations (e.g., a 32-bit address bus addresses $2^{32}$ = 4 GB).

2. Data Bus

Carries the actual data being transferred between the CPU, memory, and I/O. It is bidirectional (data flows both to and from the CPU). Its width (e.g., 8, 16, 32, 64 bits) determines how many bits can be transferred at once and strongly affects performance.

3. Control Bus

Carries control and timing signals that coordinate and manage all operations on the bus. It is a mix of signal lines such as Memory Read, Memory Write, I/O Read, I/O Write, clock, interrupt request, bus grant, and reset. These signals indicate the type and direction of the operation and synchronize the components.

Summary: the address bus says where, the data bus carries what, and the control bus tells how/when the transfer happens.

Direct Memory Access (DMA)

DMA is an I/O technique that allows certain hardware subsystems to transfer blocks of data directly between an I/O device and main memory without continuous involvement of the CPU. A dedicated DMA controller (DMAC) manages the transfer. This frees the CPU from the slow, byte-by-byte work of programmed I/O or interrupt-driven I/O, which is essential for high-speed devices like disks and network cards.

How DMA Transfers Data Without CPU Intervention

The DMA controller has registers loaded by the CPU before a transfer:

• Address register — starting memory address.
• Count register — number of words/bytes to transfer.
• Control register — direction (read/write) and mode.

Steps:

1. The CPU initializes the DMA controller with the memory address, byte count, and direction, then continues with other work.
2. When the I/O device is ready, it sends a DMA request (DREQ) to the controller.
3. The DMA controller sends a bus request (HOLD/BR) to the CPU asking to use the system bus.
4. The CPU finishes its current bus cycle, relinquishes the bus, and replies with a bus grant (HLDA/BG). The CPU's address/data/control lines go to high-impedance.
5. The DMA controller now becomes the bus master: it places the address on the address bus and transfers data directly between the device and memory, incrementing the address and decrementing the count for each word.
6. When the count reaches zero, the transfer is complete; the controller releases the bus back to the CPU and raises an interrupt to inform the CPU that the block transfer is done.

Transfer modes: burst (block) mode transfers the whole block at once; cycle-stealing mode transfers one word at a time, releasing the bus between words.

Because the data moves directly over the bus under DMAC control, the CPU is bypassed during the actual transfer — improving throughput and letting the CPU do useful work in parallel.

RISC vs CISC

RISC (Reduced Instruction Set Computer) uses a small set of simple, fixed-length instructions that execute (ideally) in one cycle, relying on the compiler and many registers. CISC (Complex Instruction Set Computer) provides a large set of powerful, variable-length instructions, some doing complex multi-step tasks in a single instruction.

In short: RISC keeps hardware simple and pushes complexity to the compiler for speed and easy pipelining; CISC keeps powerful instructions in hardware for compact, programmer-friendly code.

Register Transfer Language (RTL)

Register Transfer Language (RTL) is a symbolic notation used to describe the micro-operations performed on the data stored in registers of a digital system. It precisely specifies the transfer of information between registers and the operations applied during the transfer. A micro-operation is an elementary operation performed on data in registers in one clock pulse.

Basic notation:

• Registers are denoted by capital letters: $R1$, $R2$, $AR$ (address register), $PC$, $MAR$, etc.
• A transfer is written with an arrow: $R2 \leftarrow R1$ (contents of $R1$ copied into $R2$).
• Conditional (controlled) transfer uses a control function: $P:\; R2 \leftarrow R1$ (transfer occurs only when $P = 1$).
• Memory transfers use the data register: $DR \leftarrow M[AR]$ (read), $M[AR] \leftarrow DR$ (write).

Types of Micro-operations with Examples

1. Register transfer micro-operation — moves data between registers without changing it.

   • $R2 \leftarrow R1$

2. Arithmetic micro-operations — perform add, subtract, increment, decrement.

   • $R3 \leftarrow R1 + R2$ (addition)
   • $R3 \leftarrow R1 + \overline{R2} + 1$ (subtraction via 2's complement)
   • $R1 \leftarrow R1 + 1$ (increment)

3. Logic micro-operations — bitwise operations.

   • $R1 \leftarrow R1 \land R2$ (AND), $R1 \leftarrow R1 \lor R2$ (OR), $R1 \leftarrow \overline{R1}$ (complement)

4. Shift micro-operations — shift bits left or right.

   • $R1 \leftarrow shl\, R1$ (shift left), $R1 \leftarrow shr\, R1$ (shift right)

RTL is hardware-oriented and is used to design and document the data path and control of a CPU.

Restoring Division Algorithm (Unsigned Integers)

Restoring division divides an unsigned dividend by a divisor using repeated shift, subtract, and (conditional) restore steps.

Registers: $A$ (initially 0), $Q$ (dividend), $M$ (divisor), count $n$ = number of bits.

Algorithm (repeat n times):

1. Shift left the combined register A,Q by one bit.
2. A = A - M  (subtract divisor from A).
3. If A < 0 (MSB of A = 1):
        Q0 = 0
        A = A + M    (restore: add divisor back)
   Else (A >= 0):
        Q0 = 1
4. Decrement count; repeat until count = 0.

At the end: Quotient is in $Q$ and Remainder is in $A$.

Example: Divide $7 \div 3$ (4-bit)

$M = 0011$ (3), $-M = 1101$. Dividend $Q = 0111$ (7), $A = 0000$, $n = 4$.

Result: Quotient $Q = 0010 = 2$, Remainder $A = 0001 = 1$.

Check: $3 \times 2 + 1 = 7 \checkmark$.

Microprogrammed Control

In microprogrammed control, the control signals required to execute instructions are not generated by fixed logic gates but are stored as words (microinstructions) in a special memory called the control memory (control store). Each machine instruction corresponds to a microprogram — a sequence of microinstructions; executing the instruction means fetching and interpreting these microinstructions one by one. Each microinstruction, when read out, produces a set of control signals for one micro-operation step.

Key components:

• Control Memory (ROM): stores all microprograms.
• Control Address Register (CAR): holds the address of the current microinstruction.
• Control Data Register (CDR): holds the microinstruction currently being executed.
• Sequencer / Next-address generator: determines the address of the next microinstruction (sequential, branch, or based on conditions).

Working: The CAR points to a microinstruction in control memory → it is read into the CDR → its control field generates control signals → the sequencer computes the next CAR value → the cycle repeats until the instruction's microprogram completes.

Microinstruction Format

A microinstruction is divided into fields:

+-------------+-------------+-------------+----------------+
| Control /   | Control /   | Condition   | Next-Address   |
| Micro-ops   | Micro-ops   | Select (BR) | Field (CD/AD)  |
+-------------+-------------+-------------+----------------+

1. Control field (micro-operation field): specifies the control signals / micro-operations to perform (often grouped/encoded fields, e.g., F1, F2, F3 in Mano's model).
2. Condition field (CD): selects the status condition to test for branching (e.g., zero, carry, sign, unconditional).
3. Branch field (BR): specifies the type of branch (jump, call, map, return).
4. Address field (AD): gives the address of the next microinstruction in control memory.

Horizontal vs vertical: a horizontal microinstruction has one bit per control signal (long word, fast, less decoding); a vertical microinstruction uses encoded fields (short word, needs decoders, slower).