Computer Organization and Architecture

Assignment Solutions

Q1. Functional Blocks of a Computer

A computer is a system built from five functional units that work together to accept input, process it, and produce output.
These are the Input Unit, Output Unit, Memory Unit, Arithmetic Logic Unit (ALU) and Control Unit (CU). The ALU and
CU together (along with registers) form the Central Processing Unit (CPU), the "brain" of the computer.

Fig 1.1: Functional block diagram of a computer

Role of each unit

• Input Unit: Converts data from the outside world (keyboard, mouse, scanner) into a binary form the computer can
understand, and sends it to memory.
• Memory Unit: Stores both the program instructions and data. It is organised as a set of numbered locations; the CPU
reads instructions/data from memory and writes results back.
• Control Unit (CU): Does not process data itself — it directs and coordinates all other units. It fetches instructions from
memory, decodes them, and generates the timing/control signals that tell the ALU, memory and I/O units what to do and
when.
• Arithmetic Logic Unit (ALU): Performs all arithmetic (add, subtract, multiply, divide) and logical (AND, OR, NOT,
comparison) operations on data brought from memory or registers.
• Output Unit: Converts the binary results produced by the CPU back into a human-readable form (screen display,
printout, sound).

How they cooperate to execute a program

When a program runs, the Control Unit fetches an instruction from the Memory Unit, decodes it to find out what operation is
needed, and activates the ALU (if computation is needed) or the I/O units (if data transfer is needed). The Memory Unit
continuously supplies instructions/data and stores results. This fetch → decode → execute cycle repeats for every instruction
until the program finishes — this is explained in detail in Q2.
Q2. CPU Registers, Instruction Cycle, and Addressing Modes
CPU Registers
Registers are very small, very fast storage locations built directly into the CPU. They hold data that the CPU is currently
working on, so the CPU does not have to wait for slower main memory. The important registers are:

Register Function

Program Counter (PC) Holds the address of the NEXT instruction to be fetched

Instruction Register (IR) Holds the instruction that is currently being decoded/executed

Memory Address Register Holds the address of the memory location to be read from or written to
(MAR)

Memory Buffer/Data Temporarily holds the data being transferred to or from memory
Register (MBR/MDR)

Accumulator (AC/ACC) General register that holds intermediate arithmetic/logic results

General Purpose Registers Used to hold operands and results during program execution
(GPRs)

Status/Flag Register Holds condition flags such as Carry, Zero, Sign, Overflow, set after ALU
operations

Stack Pointer (SP) Points to the top of the stack, used for function calls and interrupts

Instruction Execution Cycle

Every instruction is executed in a repeating cycle:

• Fetch: The address in PC is copied into MAR. The instruction at that memory address is read into MBR and then into
IR. PC is incremented so it points to the next instruction.
• Decode: The Control Unit examines the opcode in IR to determine which operation is required and which
registers/memory locations (operands) are involved.
• Execute: The Control Unit sends signals to the ALU, registers or memory to actually carry out the operation (e.g. add
two numbers, load a value, store a value).
• Store/Write-back (if needed): The result is written back to a register or memory location.
This Fetch-Decode-Execute cycle repeats continuously, and is driven by the CPU clock, until the program ends.

Addressing Modes (with examples)

An addressing mode is the method used to specify where an instruction's operand (data) is located. Common addressing
modes:

Mode How operand is found Example

Immediate Operand value is given directly in the MOV R1, #5 (R1 <- 5)
instruction

Direct Instruction gives the memory address MOV R1, 2000 (R1 <- M[2000])
of the operand

Indirect Instruction gives an address that itself MOV R1, @2000 (R1 <-
contains the address of the operand M[M[2000]])
 Register Operand is inside a CPU register ADD R1, R2 (R1 <- R1+R2)

Register Indirect Register holds the address of the MOV R1, (R2) (R1 <- M[R2])
operand in memory

Indexed Address = Base register/value + Index MOV R1, 200(R2) (R1 <-
register (useful for arrays) M[200+R2])

Relative Address = Program Counter + offset JMP +10 (PC <- PC+10)
given in instruction (used in branches)
Addressing modes give flexibility: immediate mode is fast for constants, indirect/indexed modes make pointer and array
handling possible, and relative mode makes programs relocatable (position independent).

Q3. Data Representation in Computers

Computers store everything — numbers, characters, instructions — as binary digits (0s and 1s). How a given bit pattern is
interpreted depends on the data representation scheme used.

Signed Number Representation

To represent both positive and negative integers, the leftmost (Most Significant) bit is normally used as the sign bit (0 =
positive, 1 = negative). Three common schemes for an n-bit number:

Scheme Rule Example (8-bit, value -5)

Sign-Magnitude Sign bit + plain binary magnitude of 1000 0101

the number

1's Complement Invert every bit of the positive 1111 1010

number

2's Complement Invert every bit of the positive 1111 1011

number and add 1
• Sign-Magnitude: simple to understand, but has two representations of zero (+0 and −0) and needs separate add/subtract
logic.
• 1's Complement: also has two zeros (0000 0000 and 1111 1111), and addition may need an "end-around carry"
correction.
• 2's Complement: has only ONE representation of zero, and ordinary binary addition automatically handles subtraction
— this is why virtually all modern computers use 2's complement (see Q4).

Fixed-Point Representation
In fixed-point representation, the position of the binary (radix) point is fixed and assumed — it is not actually stored. A
number is split into an integer part and a fractional part, e.g. in a Q notation "Q8.8" format, 8 bits represent the integer part
and 8 bits represent the fraction, with the point assumed between them.

• Advantage: simple, fast hardware (just integer arithmetic units are needed).
• Disadvantage: limited range and precision — the point cannot shift to represent very large or very small numbers, unlike
floating-point (Q7).
Q4. Binary Addition using 2's Complement; Ripple Carry & Carry
Look-Ahead Adders
Binary Addition using 2's Complement
2's complement lets a computer perform subtraction using only an adder: to compute A − B, the CPU takes the 2's
complement of B (invert all bits and add 1) and simply adds it to A. Any carry out of the most significant bit is discarded.

Example (8-bit): 12 − 5 = 12 + (2's complement of 5)

• 12 = 0000 1100
• 5 = 0000 0101 -> 1's complement = 1111 1010 -> 2's complement (+1) = 1111 1011
• 0000 1100 + 1111 1011 = 1 0000 0111 -> discard final carry -> 0000 0111 = 7 (correct)

Ripple Carry Adder (RCA)

A Ripple Carry Adder adds two n-bit numbers using n Full Adders connected in a chain. Each Full Adder computes a sum bit
and a carry-out; that carry-out becomes the carry-in of the NEXT (more significant) Full Adder.

Fig 4.1: 4-bit Ripple Carry Adder

• Advantage: very simple and uses minimum hardware (just n Full Adders).
• Disadvantage: SLOW for large n, because Full Adder i cannot produce its correct output until Full Adder (i-1) has
produced its carry — the carry must "ripple" through every stage, so worst-case delay grows linearly with the number of
bits.

Carry Look-Ahead Adder (CLA)

A Carry Look-Ahead Adder removes the ripple delay by computing all carries in advance, directly from the input bits, using
extra logic gates. For each bit position i, it defines:

• Generate: Gi = Ai · Bi (a carry is generated here regardless of incoming carry)

• Propagate: Pi = Ai ⊕ Bi (an incoming carry would be passed through)
• Then every carry can be written directly as: Ci+1 = Gi + Pi·Ci, which can be expanded and computed in parallel for all
bits using two levels of gates.
 Fig 4.2: Carry Look-Ahead Adder concept

• Advantage: Much faster than RCA — carry generation no longer ripples bit by bit.
• Disadvantage: Needs more hardware (extra AND/OR gates), and the look-ahead logic becomes very complex for a large
number of bits, so in practice CLA blocks of 4 bits are chained together for wider adders.

Q5. Binary Multiplication Techniques

Shift-and-Add Multiplier
This mimics the way we do multiplication by hand in decimal. To multiply a multiplicand (M) by a multiplier (Q):

• Start with a Product register initialised to 0.

• Examine the least significant bit of Q. If it is 1, add the multiplicand M to the partial product; if it is 0, add nothing.
• Shift the partial product (and the multiplier) right by one bit position.
• Repeat this Add-then-Shift step once for every bit of the multiplier.
Example: Multiply 1011 (11) x 0011 (3): each 1 bit of the multiplier causes M to be added at the correct shifted position,
giving a final product of 0010 0001 (33).

Booth's Multiplier
Booth's algorithm speeds up multiplication of signed numbers (in 2's complement) by reducing the number of additions
needed, especially when the multiplier has long runs of consecutive 1s or 0s. It examines the multiplier two bits at a time (the
current bit Qi and the previous bit Qi-1, with an extra bit Q-1 initialised to 0):

Qi Qi-1 Action on the partial product

00 No arithmetic operation — just shift right

01 Add multiplicand M to partial product, then shift right

10 Subtract multiplicand M from partial product, then shift right

11 No arithmetic operation — just shift right

Because runs of 1s are handled with only one subtraction and one addition (at the ends of the run) instead of one addition per
bit, Booth's algorithm reduces the number of add/subtract steps, making it efficient in hardware — and it naturally handles
negative numbers in 2's complement form.
Q6. Binary Division Algorithms
Binary division algorithms repeatedly subtract the divisor from a running remainder and shift, generating one quotient bit per
step, exactly like long division. The two hardware-oriented approaches differ in how they treat a negative (unsuccessful)
subtraction.

Restoring Division
• Shift the Remainder-Quotient register left by 1 bit.
• Subtract the Divisor from the Remainder.
• If the result is non-negative, the quotient bit is set to 1 (the subtraction is kept).
• If the result is negative, the quotient bit is set to 0, and the Divisor is added back to RESTORE the remainder to its value
before subtraction (hence the name).
• Repeat for as many bits as needed.
Example concept: Divide 1011 (11) by 0011 (3) — at each step we subtract 3 (shifted appropriately); whenever the
remainder goes negative we restore it by adding the divisor back before continuing, finally obtaining quotient 3 and
remainder 2.

Non-Restoring Division
Non-restoring division avoids the extra "restore" addition, making it faster:

• Shift the Remainder-Quotient register left by 1 bit.

• If the previous remainder was non-negative, subtract the Divisor; if the previous remainder was negative, ADD the
Divisor instead (no separate restore step).
• If the new remainder is non-negative, quotient bit = 1; if negative, quotient bit = 0.
• Repeat for all bits; if the FINAL remainder is negative, one final restoring addition of the divisor is done to get the
correct remainder.
Non-restoring division needs only one add/subtract operation per bit (versus up to two in restoring division), so it is generally
faster in hardware, at the cost of slightly more complex control logic.

Q7. Floating-Point Arithmetic and IEEE-754

Floating-point representation lets the position of the binary point "float", so a single format can represent both very large and
very small numbers with reasonable precision. A floating-point number is expressed as: Value = (−1)^Sign × [Link] ×
2^(Exponent − Bias).

IEEE-754 Format
Field Single Precision (32-bit) Double Precision (64-bit)

Sign 1 bit 1 bit

Exponent 8 bits (bias = 127) 11 bits (bias = 1023)

Mantissa (Fraction) 23 bits 52 bits

The mantissa stores only the bits after the leading 1 (which is assumed/"hidden" for normalised numbers), which effectively
gives one extra bit of precision for free.
Floating-Point Addition
To add two floating-point numbers:

• Align exponents: compare the two exponents; shift the mantissa of the number with the smaller exponent right until
both exponents are equal (this may lose some low-order mantissa bits — rounding).
• Add the mantissas using ordinary fixed-point addition.
• Normalise the result: if the sum overflows (e.g. becomes ≥ 2.0), shift right and increment the exponent; if it needs a
leading zero removed, shift left and decrement the exponent.
• Round the mantissa to fit the available bits, and check for exponent overflow/underflow.
Example: adding 1.25 x 2^1 and 1.5 x 2^0 requires shifting the second number's mantissa right by 1 (to 0.75 x 2^1) before
the mantissas 1.25 and 0.75 can be added directly, giving 2.0 x 2^1, which is then renormalised to 1.0 x 2^2.

Q8. Hierarchical Memory Organization

No single memory technology is simultaneously fast, large, AND cheap. Memory Hierarchy solves this by arranging several
kinds of storage in layers: the fastest and most expensive (but smallest) memory is placed closest to the CPU, and slower,
cheaper, larger memory is placed further away. This gives the illusion of a memory that is as fast as the top layer and as
large/cheap as the bottom layer, because frequently used data automatically tends to stay in the faster layers (principle of
locality).

Fig 8.1: The Memory Hierarchy

Why a hierarchy is needed

• Fast memory (like registers/cache) is very expensive per byte, so it can only be built in small sizes.
• Slow memory (like disks) is very cheap per byte, so huge capacities are affordable.
• Programs exhibit locality of reference — they repeatedly access a small set of instructions/data — so keeping that "hot"
data in fast memory gives most of the speed benefit of fast memory at a fraction of the cost.
Characteristics of each level
Level Speed Size Notes

Registers Fastest (≈ CPU A few Built inside the CPU; hold

clock speed) bytes/words operands currently in use

Cache Memory Very fast (few KB to few MB Sits between CPU and RAM;
ns) stores recently/frequently used
data (SRAM)

Main Memory (RAM) Moderate (tens GBs Holds the currently running
of ns) program and data (DRAM);
volatile

Secondary Storage Slow (ms for TBs Non-volatile, holds programs/files

HDD, faster for permanently
SSD)

Q9. Cache Mapping Techniques

Cache mapping decides WHERE a block of main memory can be placed inside the cache.

Direct Mapping
Each main memory block can go into exactly ONE specific cache line, usually computed as (Block Number) mod (Number
of Cache Lines). A tag field stored with each cache line identifies which particular memory block currently occupies that
line.

Fig 9.1: Direct Mapping — each block maps to one fixed line

Advantages Disadvantages

Direct Mapping Simple and cheap to implement; fast High chance of conflict misses — two
lookup (only one line to check) frequently used blocks that map to the
SAME line repeatedly evict each
other even if other cache lines are free

Associative Mapping (Fully Associative)

A memory block can be placed in ANY available cache line. Every line's tag must be compared simultaneously (in parallel,
using comparator hardware) with the requested address to check for a hit.
 Fig 9.2: Associative Mapping — a block may go to any free line

Advantages Disadvantages

Associative Mapping Very flexible — best use of available Expensive hardware (needs a
cache space, lowest conflict misses comparator per line) and slower for
large caches since every tag must be
checked

Note: A middle ground called Set-Associative Mapping (dividing the cache into sets, each acting like a small fully-
associative cache) is commonly used in real processors to balance these trade-offs.

Q10. Cache Replacement Algorithms and Write Policies

Replacement Algorithms
When a new block must be loaded into a cache that has no free line (common in associative/set-associative caches), a
replacement algorithm decides which existing block to evict.

Algorithm How it works

FIFO (First-In- Evicts the block that has been in the cache the LONGEST,
First-Out) regardless of how often it is used — simple to implement using a
queue, but can evict a still-popular block.

LRU (Least Evicts the block that has not been accessed for the LONGEST time.
Recently Used) Assumes recently used data is likely to be used again soon
(temporal locality) — gives better hit rates than FIFO but needs
extra hardware/bits to track usage order.

Random Evicts a randomly chosen block. Very cheap to implement (no

tracking needed) and surprisingly avoids the worst-case pathological
patterns that can occasionally hurt FIFO or LRU.

Write Policies
A write policy decides how the cache handles a CPU write, and how/when main memory is updated:

• Write-Through: Every write to the cache is immediately also written to main memory. Simple, keeps memory always
up-to-date and consistent, but generates more memory traffic and is slower.
• Write-Back: A write only updates the cache line and sets a "dirty bit"; the line is written to main memory only when it is
evicted. Faster (fewer memory writes) but memory is temporarily inconsistent with cache, and control logic is more
complex.
Q11. Organization and Operation of a Modern Computer System
A modern computer system is organised so that the CPU, memory, cache, arithmetic unit and I/O subsystems cooperate over
a common set of buses (address, data and control lines) under the direction of the Control Unit.

Step-by-step operation during program execution

• 1. Fetch: The CPU's Control Unit places the address held in the Program Counter onto the address bus. This address
usually first reaches the cache; if the instruction is already present (a cache hit) it is returned quickly, otherwise the
request goes on to main memory (a cache miss), and the fetched block is also copied into cache for future use.
• 2. Decode: The fetched instruction, now in the Instruction Register, is decoded by the Control Unit to identify the
operation and the operands required.
• 3. Operand Fetch: Any operands needed are obtained from registers, or requested from memory/cache in the same way
as instruction fetch.
• 4. Execute: The Control Unit enables the Arithmetic/Logic Unit to perform the required computation, or enables an I/O
subsystem to transfer data (e.g. read a file, print output).
• 5. Write-back: Results are written back into a register, or sent through the memory/cache hierarchy back to main
memory (respecting the write policy in use — Q10).
• 6. This entire cycle repeats continuously for every instruction, with the cache reducing average memory access time,
and I/O subsystems (often working through interrupts or DMA) allowing input/output to proceed largely independently
of the CPU.
In short, the CPU orchestrates computation, the cache and memory hierarchy supply instructions/data at manageable speed,
the ALU performs the actual computation, and the I/O subsystem connects the whole system to the outside world — together
carrying out the fetch-decode-execute cycle that runs every program.