Blog
Computer Architecture Past Paper 2018 – BS 4th Term UOS (CS-4240)
University of Sargodha (UOS) BS 4th term Computer Architecture (CS-4240) past paper 2018, with the full question paper in text form and solved answers, including the set-associative cache address format and the Amdahl’s law calculation.
Print / download (A4, high quality): Full-size paper
Computer Architecture Past Paper 2018 (text version)
University of Sargodha – BS 4th Term Examination 2018, Subject: Computer Science
Paper: Computer Architecture (CS-4240) · Time: 2:30 Hours · Maximum marks: 80
Note: Objective part is compulsory. Attempt any three questions from subjective part.
Objective part – Q1: Write short answers of the following in 2-3 lines each on your answer sheet. (16*2)
- Where does tape drive fall in Memory hierarchy?
- What are exceptions?
- How we can measure performance of a microprocessor or a system?
- What does ISA stands for?
- What are addressing modes?
- What is instruction level parallelism?
- What is Request level parallelism?
- What is thread level parallelism
- What is Amdhal’s law?
- Give atleast three pipeline hazards.
- What is Virtual Memory? And why it is called virtual?
- What are Benchmarks?
- Differentiate between RISC and CISC architecture.
- Why we need Non Uniform Memory access?
- What are Branch predictions?
- What is principle of locality?
Subjective part (3*16)
Q2. A set-associative cache has a block size of four 16-bit words and a set size of 4. The cache can accommodate a total of 8190 words. The main memory size that is cacheable is 2048000 bits. Show how the processor’s addresses are interpreted
Q3. Suppose that we want to enhance the processor used for Web serving. The new processor is 10 times faster on computation in the Web serving application than the original processor. Assuming that the original processor is busy with computation 40% of the time and is waiting for I/O 60% of the time, what is the overall speedup gained by incorporating the enhancement?
Q4. Write a brief note on Intel and MIPS architecture. Also give similarities and differences of both architectures.
Q5. Explain Parallel and Multiprocessor Architectures in detail also explain alternative parallel processing approaches.
Q6. What are deep pipelines, branch prediction and superscalar processor?
Original paper (scanned copy)
The clean paper above is retyped by Shining Study from this original University of Sargodha question paper. Click the scan to view it full size.
Solved answers
Q1 – Short questions
(i) Tape drives are at the bottom of the memory hierarchy (tertiary/offline storage): largest capacity and cheapest per bit, but slowest with sequential access. Order: registers → cache → main memory → disk/SSD → optical/tape.
(ii) Exceptions: unexpected events that change the normal flow of instruction execution, e.g. arithmetic overflow, divide by zero, undefined opcode, page fault, or a system call. The CPU saves the PC (in EPC), records the cause and jumps to an exception handler in the OS. (Interrupts are the external kind.)
(iii) Measuring performance: by execution time (response time) and throughput. CPU time = Instruction count × CPI × clock cycle time = (IC × CPI)/clock rate. Also MIPS, FLOPS, and standard benchmarks (SPEC).
(iv) ISA: Instruction Set Architecture – the interface between hardware and software: instructions, registers, data types, addressing modes, memory model and I/O, e.g. x86, MIPS, ARM.
(v) Addressing modes: ways an instruction specifies where its operand is: immediate, register, direct (absolute), register indirect, displacement/base, indexed, PC-relative, auto-increment, etc.
(vi) ILP: instruction-level parallelism – executing several instructions of one program at the same time, using pipelining, superscalar issue, out-of-order execution and VLIW.
(vii) Request-level parallelism: parallelism among largely independent requests from many users, e.g. a web server or warehouse-scale computer handling thousands of search requests simultaneously on different servers.
(viii) Thread-level parallelism: running multiple threads (from one or several programs) in parallel on multiple cores or with hardware multithreading (SMT/Hyper-Threading).
(ix) Amdahl’s law: the overall speedup from improving part of a system is limited by the fraction that is not improved: Speedup = 1 / [(1 − F) + F/S], where F is the fraction enhanced and S the speedup of that part.
(x) Pipeline hazards: (1) structural hazards – two instructions need the same hardware unit; (2) data hazards – an instruction needs a result not yet produced (RAW, WAR, WAW); (3) control hazards – branches change the PC before the outcome is known.
(xi) Virtual memory: a technique that uses main memory as a cache for secondary storage, giving each program a large private address space split into pages that are mapped to physical frames by page tables (with a TLB). It is “virtual” because the addresses a program uses do not exist physically; parts of the program may be on disk and the space can be larger than real RAM.
(xii) Benchmarks: standard programs used to measure and compare computer performance on realistic workloads, e.g. SPEC CPU, TPC (transactions), Linpack, Geekbench.
(xiii) RISC vs CISC: RISC – few simple fixed-length instructions, load/store architecture, many registers, mostly one cycle each, easy to pipeline, hardwired control (MIPS, ARM). CISC – many complex variable-length instructions, memory operands in many instructions, many addressing modes, multi-cycle, often microcoded (x86).
(xiv) Why NUMA: in large multiprocessors a single shared memory bus becomes a bottleneck. NUMA gives each processor (node) its own local memory that it accesses quickly, while still allowing access to remote memory (slower), so the system scales to many processors with higher bandwidth.
(xv) Branch prediction: guessing the outcome of a branch (taken / not taken and target) before it is resolved, so the pipeline can keep fetching instructions. Static (always not-taken, backward-taken) or dynamic (1-bit/2-bit predictors, branch history tables, BTB). Wrong guesses flush the pipeline.
(xvi) Principle of locality: programs access a small part of their address space at any time. Temporal locality – recently used items are likely to be used again soon (loops). Spatial locality – items near recently used addresses are likely to be used soon (arrays, sequential code). Caches exploit both.
Q2 – Interpreting processor addresses for the set-associative cache
Assumptions: memory is word-addressable with 16-bit words. The figures in the paper are rounded powers of two: 8190 ≈ 8192 = 213 words, and 2,048,000 bits ÷ 16 = 128,000 ≈ 128K = 217 words.
- Block size = 4 words = 22 → word field = 2 bits.
- Main memory = 217 words → address = 17 bits; number of memory blocks = 217/22 = 215.
- Cache lines = 8192/4 = 2048 = 211 lines. Set size 4 (4-way), so number of sets = 2048/4 = 512 = 29 → set field = 9 bits.
- Tag = 17 − 9 − 2 = 6 bits.
|<-- Tag (6) -->|<-- Set (9) -->|<- Word (2) ->|
bits 16..11 bits 10..2 bits 1..0How an address is used: the 9-bit set field selects one of 512 sets; the 6-bit tag is compared in parallel with the tags of the 4 lines in that set; on a match (and valid bit set) it is a hit and the 2-bit word field picks one of the 4 words in the block; otherwise it is a miss, the block is fetched from memory and placed in one of the 4 lines of that set (using LRU replacement). Each set holds 4 × 4 = 16 words; tag storage = 2048 lines × 6 bits.
Q3 – Overall speedup (Amdahl’s law)
Fraction enhanced F = 0.4 (computation), speedup of that part S = 10.
Overall speedup = 1 / [(1 − F) + F/S] = 1 / [0.6 + 0.4/10] = 1 / 0.64 = 1.5625 ≈ 1.56.
Even with a 10× faster processor, the overall speedup is only about 1.56 because 60% of the time is I/O waiting that is not improved (the maximum possible would be 1/0.6 = 1.67).
Q4 – Intel (x86) and MIPS architectures
Intel x86: a CISC ISA that began with the 8086 (1978) and evolved to IA-32 and x86-64. It has variable-length instructions (1–15 bytes), many complex instructions and addressing modes, instructions that can operate directly on memory, relatively few general-purpose registers (8 in IA-32, 16 in x86-64), condition codes (flags) and backward compatibility over decades. Modern Intel processors decode x86 instructions into RISC-like micro-operations executed by deep, superscalar, out-of-order pipelines.
MIPS: a RISC ISA from Stanford/MIPS Technologies (1980s). Fixed 32-bit instructions in three formats (R, I, J); 32 general-purpose registers ($zero always 0); load/store architecture – only lw/sw access memory; few addressing modes (register, immediate, base+displacement, PC-relative, pseudo-direct); simple 5-stage pipeline (IF, ID, EX, MEM, WB); used in embedded systems, routers, game consoles and teaching.
| Aspect | Intel x86 | MIPS |
|---|---|---|
| Type | CISC | RISC |
| Instruction length | Variable, 1–15 bytes | Fixed, 32 bits |
| Registers | 8/16 GPRs | 32 GPRs |
| Memory operands | Arithmetic instructions can use memory | Only load/store |
| Addressing modes | Many, complex | Few, simple |
| Decoding/pipelining | Complex decoding into micro-ops | Simple decoding, easy pipelining |
| Branches | Condition flags | Compare registers in branch (beq/bne) |
| Use | PCs, laptops, servers | Embedded, networking, education |
Similarities: both are general-purpose, stored-program, register-based ISAs with 32/64-bit versions; both use pipelining, caches, virtual memory, branch prediction and support integer and floating-point operations; both are byte-addressable; high-performance implementations of both use superscalar, out-of-order execution.
Q5 – Parallel and multiprocessor architectures
Flynn’s classification: SISD (single processor), SIMD (one instruction on many data – vector processors, GPUs, SSE/AVX), MISD (rare), MIMD (many processors running different instructions on different data – multicores, clusters).
Multiprocessor architectures (MIMD):
- Shared-memory multiprocessors (SMP/UMA): several processors share one physical memory through a bus or interconnect with uniform access time; communicate through shared variables; need cache-coherence protocols (snooping, MESI) and synchronization (locks). Scales to a limited number of processors.
- NUMA / distributed shared memory: memory is physically distributed among nodes but shares one address space; local access is faster than remote; coherence is kept with directory-based protocols. Scales further.
- Message-passing multicomputers / clusters: each node has private memory; processors communicate by sending messages (MPI) over a network. Very scalable (supercomputers, data centers).
- Multicore chips: several cores on one chip sharing the last-level cache.
Alternative parallel processing approaches:
- Pipelining and superscalar / ILP: overlap and issue multiple instructions per cycle.
- VLIW / EPIC: the compiler packs independent operations into long instruction words.
- Vector processors and SIMD extensions: one instruction operates on whole vectors.
- Hardware multithreading: fine-grained, coarse-grained and simultaneous multithreading (SMT) to hide latency.
- GPUs / GPGPU: thousands of simple cores running SIMT threads for data-parallel work.
- Dataflow and systolic arrays, neural/accelerator processors: execution driven by data availability or specialized arrays (e.g. TPUs).
- Interconnection networks: bus, crossbar, mesh, torus, hypercube determine how processors communicate.
Q6 – Deep pipelines, branch prediction, superscalar processors
Deep pipelines (superpipelining): the instruction pipeline is split into many more, shorter stages (e.g. 20–31 stages in Pentium 4) so each stage does less work and the clock rate can be higher. Drawbacks: larger penalty for branch mispredictions and hazards (more stages to flush), more pipeline-register overhead and power; so modern CPUs use moderate depth (~14–20 stages).
Branch prediction: because the branch outcome is known late in a deep pipeline, the processor predicts it to keep fetching. Static prediction: always not taken, or backward-taken/forward-not-taken, or compiler hints. Dynamic prediction: a branch history table with 1-bit or 2-bit saturating counters (a 2-bit counter changes prediction only after two mispredictions), correlating/two-level and tournament predictors, plus a branch target buffer (BTB) giving the target address and a return-address stack. On a misprediction, speculative instructions are flushed and fetching restarts at the correct address. Modern predictors are over 95% accurate.
Superscalar processor: a processor that can fetch, decode and issue more than one instruction per clock cycle to multiple parallel functional units (several ALUs, FPUs, load/store units), achieving CPI below 1 (IPC above 1). It needs dependency checking, register renaming (to remove WAR/WAW hazards), out-of-order execution with reservation stations (Tomasulo) and a reorder buffer for in-order commit. Examples: Intel Core, AMD Ryzen, ARM Cortex-A series. Its performance is limited by the available ILP, branch mispredictions and memory latency.
Answers prepared by Shining Study for revision. Check them against your class notes and teacher’s guidance.

