Comprehensive Exercises

Approach: Work upward from the bottom of the stack, naming each layer, its responsibility, and a representative example, then summarise the property that the layering buys.

Steps:

1. Hardware level:
   • Provides the basic physical devices
   • Performs the most elementary electronic operations
   • Examples: CPU, main memory, hard disk
2. Microprogram level:
   • Decomposes machine instructions into micro-operations
   • Coordinates the hardware components
   • Invisible to programmers
3. Operating system level:
   • Manages hardware resources
   • Provides a user interface
   • Examples: Windows, Linux
4. System software level:
   • Provides development tools
   • Manages databases
   • Examples: compilers, database systems
5. Application software level:
   • Serves the user directly
   • Implements a specific function
   • Examples: a browser, an office suite

Answer: The layered structure of a computer system consists, from bottom to top, of the hardware level, the microprogram level, the operating system level, the system software level, and the application software level. Its advantages are modularity, ease of maintenance, extensibility, and portability.

Approach: List the five components in the order in which the data flows through them and attach the one-line responsibility of each.

Steps:

1. Arithmetic logic unit (ALU):
   • Performs arithmetic operations (addition, subtraction, multiplication, division)
   • Performs logical operations (AND, OR, NOT)
   • Performs shift operations
2. Controller:
   • Fetches and decodes instructions
   • Issues control signals
   • Controls the order in which the program executes
3. Memory:
   • Stores programs and data
   • Includes main memory (RAM/ROM) and secondary storage (hard disk)
   • Provides the read and write operations
4. Input devices: convert external information into digital signals; examples: keyboard, mouse, scanner.
5. Output devices: convert the computed results into a form a human can understand; examples: monitor, printer, speakers.

Answer: The five components are the arithmetic logic unit, the controller, memory, input devices, and output devices. The core idea behind them is the stored program: instructions and data share one memory, and the controller fetches and executes them in order.

Approach: State the principle in one sentence, then list the four consequences that follow from it and the historical effect it had.

Steps:

1. Automatic execution: once a program is loaded it needs no human intervention, and the computer executes the instructions in order.
2. The program can be modified: because the program is stored in memory it can be patched, which even allows self-modifying programs.
3. Generality: the same machine can run different programs, and switching tasks only means loading a different program into memory.
4. Flexibility: programs and data are stored in the same way, so a program can be handled just like data.

Answer: The stored-program principle means that both program instructions and data are kept in the same memory and that the computer executes the instructions automatically in the order in which they are stored. It is historically decisive because it turned a special-purpose machine into a general-purpose one, and it remains the basis of every modern computer.

Approach: Compare the two kinds of storage on the same five axes (speed, capacity, price, volatility, and how the CPU reaches them), then explain why a machine needs both.

Steps:

1. Primary storage (main memory):
   • Fast
   • Smaller capacity
   • More expensive per byte
   • Volatile (lost when the power is cut)
   • Directly accessible by the CPU
   • Examples: RAM (DDR4 and DDR5 modules), ROM (the BIOS chip), and cache (the L1/L2/L3 levels)
2. Secondary storage (auxiliary storage):
   • Slower
   • Large capacity
   • Cheaper per byte
   • Non-volatile (retains data when the power is cut)
   • Not directly accessible by the CPU, so the data has to be loaded into main memory first
   • Examples: a mechanical hard disk (HDD), a solid state drive (SSD), and USB flash drives or optical discs
3. Why both are needed:
   • Primary memory is fast but expensive, so it holds the program and data currently in use
   • Secondary storage is large but slow, so it holds data over the long term
   • The two together balance speed against capacity

Answer: Primary storage is fast, small, expensive, volatile, and directly reachable by the CPU (RAM, ROM, cache), while secondary storage is slow, large, cheap, non-volatile, and reached only by loading into main memory (HDD, SSD, flash drives). A practical computer needs both, because neither the speed of primary memory nor the capacity of secondary storage is available anywhere else.

Approach: Walk through the cycle in order, naming the five stages and the concrete work each one performs, then state the property that ties them together.

Steps:

1. Fetch (IF - Instruction Fetch):
   • The instruction is read from memory at the address held by the PC
   • It is stored in the IR
   • The PC is incremented so that it points at the next instruction
2. Decode (ID - Instruction Decode):
   • The operation code is analysed
   • The instruction class and the location of the operands are determined
   • The operands are read out of the registers
   • The control signals are prepared
3. Execute (EX - Execute):
   • The ALU performs the arithmetic or logic operation
   • For a memory access instruction the memory address is computed
   • For a branch instruction the target address is computed
4. Memory access (MEM - Memory Access): a LOAD instruction reads data from memory and a STORE instruction writes data to memory; every other instruction skips this stage.
5. Write back (WB - Write Back):
   • The result of the operation is written to the target register
   • The status flags (zero flag, carry flag, and so on) are updated
   • The machine is prepared for the next instruction

Answer: The five stages are instruction fetch, instruction decode, execute, memory access, and write back. Together they form one complete instruction cycle, which repeats over and over until the program finishes.

Approach: Apply the relation between clock frequency and clock period, substitute the given period, and convert the result into GHz.

Steps:

1. The formula is: clock frequency = 1 / clock period
2. Substitute the period of 0.5 ns and convert nanoseconds to seconds.

Answer:

The clock frequency is 2 GHz.

Approach: Use the weighted-average formula for a mixture of instruction types, weighting each CPI by the share of instructions that has it.

Steps:

1. The weighted average formula is:

2. Substitute the three instruction classes:

3. Add up the contributions:

Answer: The average CPI is 2.4. This means that on average each instruction takes 2.4 clock cycles to execute.

Approach: Use the CPU time formula with the instruction count, the CPI, and the clock frequency.

Steps:

1. The CPU time formula is:

2. Substitute the given values:

3. Simplify:

Answer: The CPU execution time is 2.4 ms.

Approach: Define the ISA as an interface, enumerate what it fixes down, and then spell out the three consequences of having one.

Steps:

1. Definition: the interface between software and hardware; it fixes the instruction formats, their functions, and the way they are executed.
2. What it contains:
   • (a) Instruction format — how instructions are encoded
   • (b) Instruction function — what each instruction does
   • (c) Registers — how many, how wide, and what they are for
   • (d) Data types — which formats are supported
   • (e) Addressing modes — how an operand is located
3. Its role:
   • (a) As the software/hardware interface, software is written to the ISA and hardware executes to the ISA
   • (b) As a compatibility guarantee, different CPUs that implement the same ISA run the same programs — every x86 CPU can run Windows
   • (c) As a standard, it lets hardware and software evolve independently, so a hardware upgrade does not break the software

Answer: An ISA is the interface between software and hardware that defines a processor’s instruction formats, its registers, its data types, and its addressing modes. It exists so that software written to it stays portable across implementations and so that hardware can be replaced without rewriting the programs.

Approach: Justify the cache from three directions — the raw speed gap, the principle of locality that makes caching worthwhile, and the way the levels are tuned — then show the effect and give a concrete analogy.

Steps:

1. The speed gap: the CPU runs at 3-5 GHz, while a main memory access takes 10-100 ns; without a cache the processor would spend most of its time waiting.
2. The principle of locality: temporal locality means data that was just accessed is likely to be accessed again, and spatial locality means nearby data is likely to be accessed next.
3. The levels:
   • L1 is the fastest (1-2 clock cycles) and the smallest (32-64 KB), and is private to each core
   • L2 is faster (10-20 cycles) and larger (256 KB to 1 MB)
   • L3 is the slowest (30-50 cycles) and the largest (8-36 MB), and is shared by all cores
4. The effect: with a hit rate above 90%, the average access time is close to that of L1, which lifts overall CPU performance dramatically.
5. An analogy: your desk (L1), a bookshelf (L2), a library (L3), and an online bookstore (main memory) — the books you use often sit on the desk, the ones you use now and then sit on the shelf, the rare ones need a trip to the library, and only what is unavailable has to be bought.

Answer: Modern CPUs use a multi-level cache because processor speed has far outrun memory speed, because locality of reference makes caching effective, and because splitting the cache into levels lets each one trade capacity against latency optimally. The result is an average access time close to L1 while still backing a working set far larger than the cache itself.

Approach: Compute the CPU time of each processor from the instruction count, the CPI, and the clock frequency, then take the ratio to obtain the speedup.

Steps:

1. The execution time of CPU A:

2. The execution time of CPU B:

3. The speedup:

Answer: CPU B is faster, by 20% (or 2 ms).

Analysis:

• CPU B has the higher CPI (that is, lower efficiency), but it also has the higher clock frequency and the smaller instruction count
• Compiler optimisation removed about 17% of the instructions, and that turned out to be the key factor
• This shows that performance is not only about hardware; software optimisation matters just as much!

Approach: Apply Amdahl’s law with the given parallel fraction, then compute the limit as the number of processors tends to infinity.

Steps:

1. The Amdahl’s law formula is:

2. Here P = 0.7 (the parallelisable part), 1-P = 0.3 (the serial part), and N = 8.
3. Substitute:

4. The theoretical limit, with an infinite number of processors:

Answer:

• 8 processors: a speedup of about 2.58
• The theoretical limit: 3.33

Analysis:

• The 30% serial part caps the speedup
• Even with infinitely many processors the program can at best become 3.33 times faster
• This is why the serial part has to be optimised first!

Approach: Define the bottleneck, show its two concrete symptoms, and then list the mitigations with the mechanism each one uses.

Steps:

1. Definition: because instructions and data share one memory and travel over one bus, the transfer of data between the CPU and memory becomes the performance bottleneck.
2. Symptom one, bus bandwidth: the CPU runs far faster than memory, so the bus saturates.
3. Symptom two, instruction and data conflict: fetching an instruction and fetching a data item compete for the bus and cannot proceed at the same time.
4. Mitigations:
   • (a) Cache technology, a fast cache between the CPU and memory that reduces the number of main memory accesses
   • (b) The Harvard architecture, separate stores and separate buses for instructions and data so both can be fetched at once
   • (c) Pipelining, which splits instruction execution into stages so several instructions are in flight
   • (d) A multi-level memory system of registers, L1/L2/L3 cache, main memory, and disk that balances speed against capacity
   • (e) Prefetching, which predicts the data that will be needed and loads it into the cache early
   • (f) More bus bandwidth, a wider data bus and a higher bus frequency, which is why DDR5 is faster than DDR4
5. The modern solution: a modern CPU combines all of the above and greatly reduces the bottleneck.

Answer: The von Neumann bottleneck is the contention that arises when instructions and data share a single memory and a single bus, so that the CPU-to-memory transfer, rather than the CPU itself, sets the pace. It is mitigated by caches, the Harvard separation of instruction and data paths, pipelining, multi-level memory, prefetching, and wider or faster buses — techniques a modern processor uses together.

Approach: Compute the new total time and the speedup for each option, then compare the absolute time saved.

Steps:

1. Option A (optimise the memory operations):
   • Memory time: 10 seconds × 40% = 4 seconds (6 seconds saved)
   • Computation time: 10 seconds (unchanged)
   • Total time: 4 + 10 = 14 seconds
   • Speedup: 20 / 14 ≈ 1.43
2. Option B (optimise the computation):
   • Memory time: 10 seconds (unchanged)
   • Computation time: 10 seconds × 20% = 2 seconds (8 seconds saved)
   • Total time: 10 + 2 = 12 seconds
   • Speedup: 20 / 12 ≈ 1.67

Answer: Option B gives the better result (2 seconds faster).

Analysis: Option A applies the smaller percentage improvement (60% against 80%), but because the two parts have the same share (50% each), the option with the larger improvement wins.

Conclusion:

• When the shares of the parts are similar, the larger percentage improvement wins
• When the shares differ a lot, optimising the larger part wins
• Make the common case fast!

Approach: Treat each architecture as a set of choices with a payoff and a cost, and finish with the state of the art.

Steps:

1. CISC (Complex Instruction Set Computer):
   • Many instructions (hundreds)
   • Powerful instructions that accomplish complex operations in one step
   • Variable instruction length
   • Many addressing modes
   • Advantages: short code, simpler compilers, good compatibility
   • Disadvantages: complex hardware, inconsistent instruction timing, low pipeline efficiency
   • Representatives: Intel x86, x86-64
2. RISC (Reduced Instruction Set Computer):
   • Few instructions (tens)
   • Simple instructions
   • Fixed instruction length
   • Simple addressing modes
   • Advantages: simple hardware, uniform instruction timing, high pipeline efficiency, low power consumption
   • Disadvantages: longer code, more complex compilers
   • Representatives: ARM, RISC-V, MIPS
3. The present state: modern processors are mostly hybrid — CISC on the outside for compatibility, translated internally into RISC-like micro-operations for performance.

Answer: CISC buys code density and compatibility with a large instruction repertoire at the cost of complex decoding and uneven timing, while RISC buys simple, uniform, pipeline-friendly execution at the cost of code length and compiler complexity. Modern designs claim both sides of the trade-off by exposing a CISC interface and executing a RISC core.

Approach: Map every part of the specification onto one of the five components, then assess what the resulting machine is good at and where it might fall short.

Steps:

1. ALU: the ALUs inside the Intel i7-13700K — 16 cores (8 performance cores plus 8 efficiency cores), each core with its own ALU, supporting the AVX-512 instruction set for advanced arithmetic.
2. Controller: the control units inside the same CPU — one controller per core, responsible for fetching, decoding, and issuing control signals, with hyper-threading giving 24 threads.
3. Memory:
   • Primary storage of 32 GB DDR5 at DDR5-4800 or better (volatile)
   • Cache built into the CPU at roughly 1.25 MB of L1, 16 MB of L2, and 30 MB of L3
   • Secondary storage of a 1 TB NVMe SSD reading and writing at 3000-7000 MB/s (non-volatile)
4. Input devices: not listed in the configuration; the usual ones are a keyboard, a mouse, a microphone, and a camera.
5. Output devices: not listed either; the usual ones are a monitor, speakers, and a printer.
6. Performance assessment: a high-end PC suited to gaming (with a discrete GPU added), video editing, 3D rendering, software development, and multitasking.
7. Its strengths:
   • Strong CPU performance (16 cores, 24 threads)
   • Large and fast memory (32 GB DDR5)
   • Fast storage (NVMe SSD)
8. Possible bottlenecks: gaming or 3D rendering would need a discrete GPU, and professional video editing might want more memory (64 GB).

Answer: The CPU package supplies both the arithmetic logic units and the controllers, the 32 GB DDR5 module and the on-chip cache supply the memory hierarchy together with the NVMe SSD, and the peripherals not listed would provide the input and output functions. The machine is a strong general-purpose platform whose limits are graphics capability and, for heavy video work, the amount of memory.

Approach: Answer the “why” with the four shared properties, then show where the idea is exploited deliberately and where it turns into a security problem.

Steps:

1. Same storage form:
   • Programs and data are both stored in binary
   • Both live in the same memory
   • Both can be read and modified
   • The CPU cannot tell them apart by form alone
2. Mutual convertibility: a program can be read and patched as if it were data, and data can be executed as if it were a program.
3. Uniform handling: both can be loaded into memory, processed by the CPU, and written back to disk.
4. Deliberate applications:
   • Compilers read source code (data) and emit an executable (program)
   • JIT compilers turn code (data) into machine code (program) at run time
   • Dynamic loading turns a plugin (data) into a program
   • Self-modifying code rewrites its own instructions
5. Security consequences:
   • Viruses disguise themselves as data files and become malicious code once executed
   • Buffer overflows let data overwrite program code
   • Code injection writes malicious code into a data area and then runs it
6. Virtual machines: a virtual machine treats a program as data in order to emulate a program written for another platform.

Answer: Programs and data are essentially the same because both are bit patterns stored in the same memory and processed by the same unit, so the CPU itself cannot distinguish them. The concept is what makes compilers, JIT compilation, dynamic loading, and virtual machines possible — and it is exactly why modern operating systems must mark memory regions as executable or not.

Approach: Characterise the workload, weigh the strengths of each server against it, estimate the parallel performance of each, and only then apply the cost consideration.

Steps:

1. Workload characteristics: web serving (80%) is highly concurrent and can make full use of many cores; data analysis (20%) is only partly parallelisable and still benefits from single-core performance.
2. Server A’s strengths:
   • Strong single-core performance at 3.2 GHz
   • $3000 cheaper
   • Suited to single-threaded work
3. Server B’s strengths:
   • Twice the core count (48 against 24)
   • Twice the memory (256GB against 128GB)
   • Suited to high-concurrency scenarios
4. Performance estimate for web serving (assuming it parallelises fully):
   • Server A: 24 cores × 3.2 GHz = 76.8 GHz·cores
   • Server B: 48 cores × 2.5 GHz = 120 GHz·cores
   • Server B is about 57% faster here
5. Performance estimate for data analysis (assuming 50% parallelisable): by Amdahl’s law the multi-core advantage is discounted, but Server B still has the edge.
6. Future growth: more cores and more memory are worth more as the business grows.

Answer: Choose Server B. It matches the workload, because 80% of the traffic is highly concurrent web serving that uses all 48 cores; its 256GB of memory serves both the web tier and the analysis jobs; it leaves more headroom for growth; and even though it costs $3000 more, the performance gain exceeds 50%. If the budget were tight, if the work were predominantly single-threaded, or if the highest possible single-core performance were the priority, Server A would be the better choice. There is no absolute “best” here — only the better fit for a stated requirement.

Approach: Compute the new total time and the speedup for each option, then compare the gain per unit of cost.

Steps:

1. Option A (upgrade the CPU):
   • CPU time: 8 seconds × 50% = 4 seconds
   • I/O time: 2 seconds (unchanged)
   • Total time: 4 + 2 = 6 seconds
   • Speedup: 10 / 6 ≈ 1.67
2. Option B (upgrade the SSD):
   • CPU time: 8 seconds (unchanged)
   • I/O time: 2 seconds × 20% = 0.4 seconds
   • Total time: 8 + 0.4 = 8.4 seconds
   • Speedup: 10 / 8.4 ≈ 1.19
3. Option C (upgrade both):
   • CPU time: 4 seconds
   • I/O time: 0.4 seconds
   • Total time: 4.4 seconds
   • Speedup: 10 / 4.4 ≈ 2.27

Answer:

• Option A: a speedup of 1.67 (the best value for money)
• Option B: a speedup of 1.19
• Option C: a speedup of 2.27 (the fastest, but at twice the cost)

Analysis: This is Amdahl’s law in practice. Option A gives the best return because the CPU time is 80% of the total and is therefore the main bottleneck, and optimising the main bottleneck has the most visible effect — make the common case fast!. Option B has limited effect because the I/O time is only 20% of the total, so even an 80% improvement there barely moves the total. Option C is the fastest overall but its cost per unit of gain is worse than option A.

Conclusion:

• With a limited budget: choose option A
• When absolute performance is the goal: choose option C
• Option B is not recommended (the worst value for money)

The lesson: when you optimise performance, find the main bottleneck first — optimising the part that carries the largest share gives the best result.

Approach: Structure the plan in four parts — the metrics, the method for each, the aggregation, and a worked example of the aggregation with a weight per metric.

Steps:

1. The metrics to test:
   • CPU performance: single-core performance, multi-core performance, floating-point capability
   • Memory performance: read and write speed, latency, bandwidth
   • Storage performance: sequential read and write speed, random read and write speed, IOPS (I/O operations per second)
   • Graphics performance (if a discrete GPU is fitted): 3D rendering performance, game frame rate
   • Overall performance: system response time, multitasking ability
2. The test methods:
   • CPU: tools such as Cinebench R23 or Geekbench; run a single-threaded benchmark for the single-core score and a multi-threaded benchmark for the multi-core score, and record the scores.
   • Memory: tools such as AIDA64 or MemTest; measure read and write speed, measure latency, record the bandwidth.
   • Storage: tools such as CrystalDiskMark or AS SSD; run a sequential read and write test and a 4K random read and write test, and record the speeds and the IOPS.
   • Graphics: tools such as 3DMark or Unigine; run the standard test scenes and record the frame rates and the scores.
   • Real applications: measure video encoding time for 1 GB of footage, archive time for a large file, and build time for a large project.
3. The overall assessment:
   • Weighted scoring: set the weights according to the use case, for example a high weight on graphics for a gaming machine and a high weight on CPU and memory for a developer.
   • Performance per dollar:
   $$\text{Performance per Dollar} = \frac{\text{Overall Score}}{\text{Price}}$$
   • Real experience: system boot time, application launch time, and how smooth multitasking feels.
   • Energy efficiency:
   $$\text{Energy Efficiency} = \frac{\text{Performance}}{\text{Power Consumption}}$$
4. A worked example:

The overall score is then computed by multiplying each score by its weight and summing.

Answer: A complete plan tests CPU, memory, storage, graphics, and end-to-end responsiveness, measures each with a standard benchmark tool under the same conditions, and then combines the results through a weighted score that reflects the intended use case, checked against performance per dollar and energy efficiency. The recommendation that follows should state which machine suits which workload, not simply which machine has the higher number.