Computer Architecture: Complete Study Index¶
Priority Marker Guide¶
- ๐ฅ Current teacherโs suggestion
- โญ Previous faculty question
- ๐ Another teacherโs suggestion from the supplied handwritten images
- Two or three emojis together mean that the topic appears in multiple suggestion sets.
The emojis mark priority only. Every unmarked topic is still part of the complete syllabus.
Table of Contents¶
- Fundamentals and Instruction Set Architecture
- Basic Processing Unit and Pipelining
- Advanced ILP, Multicore and GPU
- Arithmetic for Computers
- Memory System
- Input/Output Organization
- Supporting Topics
- Exact Teacher-Suggested Practice Problems
Chapter 1: Fundamentals and Instruction Set Architecture¶
1.1 Introduction to Computer Architecture¶
- Meaning of computer architecture
- Meaning of computer organization
- Meaning of computer design
- Difference among architecture, organization and design
- ๐ฅ Classes of computers
- ๐ฅ Characteristics of different classes of computers
- Personal computers
- Workstations
- Servers
- Mainframe computers
- Supercomputers
- Embedded systems
- Mobile computers
- Cloud and warehouse-scale computers
- General-purpose and special-purpose computers
- Analog, digital and hybrid computers
- โญ๐ Historical development of computer architecture
- โญ Development of computer architecture during the last 30 years
- โญ Evolution of microprocessors
- โญ Intel 80386, 80486 and Pentium processors
- Computer generations and enabling technologies
- Role and importance of computer architecture
1.2 Models and Classes of Computer Architecture¶
- ๐ฅ๐ Von Neumann architecture
- ๐ Harvard architecture
- Modified Harvard architecture
- Stored-program concept
- Program and data memory
- Von Neumann bottleneck
- Comparison of Von Neumann and Harvard architectures
- ๐ฅโญ๐ Flynnโs classification
- ๐ฅโญ๐ SISD architecture
- ๐ฅโญ๐ SIMD architecture
- ๐ฅโญ๐ MISD architecture
- ๐ฅโญ๐ MIMD architecture
- โญ๐ SPMD model
- Shared-memory architecture
- Distributed-memory architecture
- Multiprocessor and multicomputer systems
- Scalar, vector and parallel computers
1.3 Functional Units and System Layers¶
- ๐ฅ Basic functional units of a digital computer
- ๐ฅ Input unit
- ๐ฅ Output unit
- ๐ฅ Memory unit
- ๐ฅ Arithmetic and Logic Unit
- ๐ฅ Control Unit
- ๐ฅ Processor or CPU
- Registers
- Main memory
- Secondary storage
- ๐ฅ Interconnection among functional units
- ๐ฅ System bus
- ๐ฅ Data bus
- ๐ฅ Address bus
- ๐ฅ Control bus
- ๐ฅ Bus width
- ๐ฅ Bus timing
- ๐ฅ Bus arbitration
- ๐ฅ Processor bus structure
- Single-bus organization
- Two-bus organization
- ๐ฅ Three-bus organization
- ๐ฅ Layers of a computer system
- ๐ฅ Application layer
- ๐ฅ High-level language layer
- ๐ฅ Assembly-language layer
- ๐ฅ Operating-system layer
- ๐ฅ Instruction Set Architecture layer
- ๐ฅ Microarchitecture layer
- ๐ฅ Digital-logic layer
- ๐ฅ Hardware layer
- Abstraction in computer systems
- Technology development across hardware generations
1.4 Software¶
- Meaning of software
- System software
- Application software
- Operating system
- Utility software
- Device driver
- Language translator
- ๐ฅ Compiler
- Interpreter
- ๐ฅ Assembler
- ๐ฅ Linker
- ๐ฅ Loader
- Library files
- Firmware
- Difference between hardware and software
1.5 HardwareโSoftware Interface¶
- Meaning of hardwareโsoftware interface
- Role of the operating system
- ๐ฅ Role of Instruction Set Architecture
- System calls
- Device drivers
- Application Binary Interface or ABI
- Registers visible to software
- Memory address space
- Input/output address space
- Interrupt and exception interface
- User mode and supervisor mode
- ๐ฅ Relationship among application, operating system, ISA and hardware
- ๐ฅ Abstraction layers of a computer system
1.6 Translation from High-Level Language to Hardware Language¶
- ๐ฅ High-level language
- ๐ฅ Assembly language
- ๐ฅ Machine language
- ๐ฅ Source program
- ๐ฅ Object program
- ๐ฅ Executable program
- ๐ฅ Compilation process
- ๐ฅ Preprocessor
- ๐ฅ Compiler
- ๐ฅ Assembler
- ๐ฅ Linker
- ๐ฅ Loader
- Static and dynamic linking
- Interpretation process
- Just-In-Time or JIT compilation
- ๐ฅ Translation of statements into assembly instructions
- ๐ฅ๐ Representation of expressions in assembly language
- ๐ฅ Translation of assembly into machine code
- ๐ฅ Instruction encoding
- Binary execution by hardware
- ๐ฅ Complete program-translation diagram
- ๐ฅ Example of translating a C statement into assembly and machine instructions
1.7 Instruction Set Architecture¶
- ๐ฅ Definition of ISA
- ๐ฅ Importance of ISA
- ๐ฅ ISA as the interface between hardware and software
- Programmer-visible components
- ๐ฅ Instruction types
- Data-transfer instructions
- Arithmetic instructions
- Logical instructions
- Shift and rotate instructions
- Comparison instructions
- Branch and jump instructions
- Procedure-call instructions
- Input/output instructions
- System and privileged instructions
- ๐ฅ Instruction formats
- ๐ฅ Instruction length
- ๐ฅ Opcode
- ๐ฅ Operand
- ๐ฅ Register fields
- ๐ฅ Immediate fields
- ๐ฅ Address fields
- ๐ฅ Number of operands
- Zero-address instruction
- ๐ One-address instruction
- Two-address instruction
- ๐ Three-address instruction
- Data types supported by ISA
- Register organization
- General-purpose and special-purpose registers
- Memory organization
- ๐ฅ๐ Endianness
- ๐ฅ๐ Big-endian byte order
- ๐ฅ๐ Little-endian byte order
- Alignment
- ๐ฅ๐ Addressing modes
- Immediate addressing
- Register addressing
- ๐ฅ๐ Direct addressing
- ๐ฅ๐ Indirect addressing
- Register-indirect addressing
- Indexed addressing
- Base addressing
- Relative or PC-relative addressing
- Stack addressing
- Auto-increment and auto-decrement addressing
- ๐ฅ๐ Instruction encoding and decoding
- Orthogonality
- Compatibility and extensibility
1.8 ISA Styles and Features¶
- Accumulator-based architecture
- Stack-based architecture
- General-purpose register architecture
- Registerโmemory architecture
- Loadโstore architecture
- Fixed-length instructions
- Variable-length instructions
- Memory-to-memory operation
- Register-to-register operation
- Condition codes and status flags
- Procedure and function support
- Privileged-operation support
- Interrupt and exception support
- Scalar instructions
- โญ๐ Vector instructions
- ๐ฅโญ๐ Array processing
- ๐ฅโญ๐ Vector processing
- ๐ฅโญ๐ Vector processor
- ๐ฅโญ๐ Array processor
- SIMD instructions
- Atomic instructions
- ISA design principles
- Code density
- Hardware complexity
- Compiler friendliness
1.9 RISC Architecture¶
- ๐ฅ Meaning of RISC
- ๐ฅ Design philosophy
- ๐ฅ Simple instruction set
- ๐ฅ Fixed instruction length
- ๐ฅ Loadโstore operation
- ๐ฅ Large register set
- ๐ฅ Simple addressing modes
- ๐ฅ Few instruction formats
- ๐ฅ Pipeline-friendly design
- ๐ฅ Advantages and disadvantages
- ๐ฅ Examples: MIPS, ARM and RISC-V
1.10 CISC Architecture¶
- ๐ฅ Meaning of CISC
- ๐ฅ Design philosophy
- ๐ฅ Large and complex instruction set
- ๐ฅ Variable-length instructions
- ๐ฅ Multiple addressing modes
- ๐ฅ Memory-to-memory instructions
- ๐ฅ Microprogrammed control
- ๐ฅ Advantages and disadvantages
- ๐ฅ Examples: x86 and VAX
- ๐ฅ Three-bus CISC-style processor organization
1.11 RISC and CISC Comparison¶
- ๐ฅ Instruction complexity
- ๐ฅ Instruction length
- ๐ฅ Number of registers
- ๐ฅ Addressing modes
- ๐ฅ Control-unit design
- ๐ฅ Memory access
- ๐ฅ Pipelining suitability
- ๐ฅ Compiler complexity
- ๐ฅ Code size
- ๐ฅ Execution speed
- ๐ฅ Power consumption
- ๐ฅ Modern combination of RISC and CISC ideas
1.12 Performance Metrics¶
- ๐ฅ๐ Meaning of computer performance
- ๐ฅ๐ Response time or latency
- ๐ฅ๐ Throughput
- ๐ฅ๐ Difference between response time and throughput
- ๐ฅ๐ Execution time
- ๐ฅ CPU execution time
- User CPU time
- System CPU time
- Elapsed time
- ๐ฅ Clock cycle
- ๐ฅ๐ Clock rate
- ๐ฅ Clock-cycle time
- ๐ฅ Instruction count
- ๐ฅ๐ Cycles Per Instruction or CPI
- Instructions Per Cycle or IPC
- ๐ฅ๐ Million Instructions Per Second or MIPS
- Floating-Point Operations Per Second or FLOPS
- Benchmark
- Workload
- ๐ฅโญ๐ Speedup
- ๐ฅ Performance ratio
- Power and energy consumption
- Performance per watt
- Cost-performance ratio
- Reliability and availability
- ๐ฅ CPU performance equation
- ๐ฅ Average CPI calculation
- ๐ฅ Comparison of processors
- Effect of compiler, ISA and implementation on performance
- Common mistakes in performance comparison
Important equations:
\[
\text{CPU Time}
=
\text{Instruction Count}\times\text{CPI}\times\text{Clock Cycle Time}
\]
\[
\text{CPU Time}
=
\frac{\text{Instruction Count}\times\text{CPI}}{\text{Clock Rate}}
\]
\[
\text{Performance}=\frac{1}{\text{Execution Time}}
\]
\[
\text{Speedup}
=
\frac{\text{Old Execution Time}}{\text{New Execution Time}}
\]
1.13 Amdahlโs Law¶
- โญ๐ Meaning and purpose of Amdahlโs Law
- โญ๐ Enhanced and unaffected portions
- โญ๐ Fraction of execution time improved
- โญ๐ Enhancement factor
- โญ๐ Overall speedup
- โญ๐ Maximum possible speedup
- โญ๐ Limitation of parallel improvement
- โญ๐ Sequential bottleneck
- โญ๐ Numerical problems
- โญ๐ Application to processors, memory and parallel systems
- โญ๐ Amdahlโs Law versus ideal speedup
- ๐ Mooreโs Law
- ๐ Mooreโs Law versus Amdahlโs Law
\[
\text{Overall Speedup}
=
\frac{1}
{(1-f)+\frac{f}{S}}
\]
Here, \(f\) is the improved fraction and \(S\) is its speedup.
1.14 Case Studies of ISA¶
- ๐ฅ MIPS ISA
- ๐ฅ MIPS register organization
- ๐ฅ MIPS instruction formats: R, I and J
- ๐ฅ MIPS addressing modes
- ๐ฅ MIPS arithmetic, memory and branch instructions
- ARM ISA
- ARM registers and instruction styles
- Conditional execution in ARM
- โญ x86 ISA
- โญ x86 register organization
- โญ Variable-length x86 instructions
- โญ Intel 80386 architecture
- โญ Intel 80486 architecture
- โญ Pentium architecture
- RISC-V ISA
- RISC-V base instruction formats
- Comparison of MIPS, ARM, x86 and RISC-V
- ๐ฅ๐ Example instruction translation for an ISA
Chapter 2: Basic Processing Unit and Pipelining¶
2.1 Components of the Processor¶
- Processor organization
- ๐ฅ Arithmetic and Logic Unit
- ๐ฅ Control Unit
- ๐ฅ Register file
- Program Counter or PC
- Instruction Register or IR
- Memory Address Register or MAR
- Memory Data Register or MDR
- General-purpose registers
- Stack Pointer
- Status or flag register
- ๐ฅ Instruction decoder
- Clock and timing unit
- ๐ฅ Internal CPU buses
- Multiplexer
- Sign-extension unit
- Shift unit
- Adder
- Pipeline registers
- ๐ฅ Connections among processor components
2.2 Datapath¶
- ๐ฅ Meaning of datapath
- Single-bus datapath
- Two-bus datapath
- ๐ฅ Three-bus datapath
- ๐ฅ Three-bus CISC-style processor organization
- Register-file operation
- ๐ฅ ALU input selection
- ๐ฅ Multiplexer operation
- Immediate-value generation
- Sign extension and zero extension
- PC update circuit
- Branch-target calculation
- Jump-target calculation
- ๐ฅ Memory-access path
- ๐ฅ Single-cycle datapath
- ๐ฅ Multicycle datapath
- ๐ฅ Datapath for R-type instruction
- ๐ฅ Datapath for load instruction
- ๐ฅ Datapath for store instruction
- ๐ฅ Datapath for branch instruction
- Datapath for jump instruction
- ๐ฅ Block diagram of a processor datapath
- ๐ฅ Datapath modifications for data forwarding
2.3 Control Unit¶
- ๐ฅ Purpose of the control unit
- ๐ฅ Control signals
- ๐ฅ Instruction decoding
- ๐ฅ ALU control
- ๐ฅ Register control
- ๐ฅ Memory control
- ๐ฅ Multiplexer control
- ๐ฅ PC control
- Main decoder
- ALU decoder
- ๐ฅ Timing and sequencing
- Control word
- ๐ฅ๐ Control-state diagram
- ๐ฅ๐ Finite State Machine or FSM
- Single-cycle control
- Multicycle control
- Pipelined control
2.4 Execution of a Complete Instruction¶
- ๐ฅ๐ Instruction cycle
- ๐ฅ๐ Instruction-cycle state diagram
- ๐ฅ๐ Instruction fetch
- ๐ฅ๐ Instruction decode
- ๐ฅ๐ Operand fetch
- ๐ฅ๐ Execute
- ๐ฅ๐ Memory access
- ๐ฅ๐ Write-back
- ๐ฅ๐ PC update
- ๐ฅ Register Transfer Language or RTL
- ๐ฅ Micro-operations
- ๐ฅ Fetch-cycle micro-operations
- ๐ฅ๐ Execution of arithmetic instructions
- Execution of logical instructions
- ๐ฅ๐ Execution of load and store instructions
- ๐ฅ Execution of branch and jump instructions
- Procedure call and return
- ๐ฅ๐ Complete instruction-execution examples
- ๐ฅ Single-cycle versus multicycle execution
- ๐ฅ Execution steps for
Load R2, LOC - ๐ฅ Execution steps for
Add (R3), R1 - ๐ One-operand execution such as
MUL BX - ๐ Three-address execution such as
ADD R4, R3, R2
2.5 Hardwired Control¶
- Meaning of hardwired control
- Control-signal generation
- Opcode decoder
- Sequence counter
- Timing signals
- State-machine implementation
- Advantages and disadvantages
- Speed and hardware complexity
- Suitable applications
2.6 Microprogrammed Control¶
- ๐ฅ Meaning of microprogrammed control
- ๐ฅ Control memory
- ๐ฅ Microinstruction
- ๐ฅ Microprogram
- ๐ฅ Control word
- ๐ฅ Microprogram counter
- ๐ฅ Microinstruction register
- ๐ฅ Microprogram sequencer
- Horizontal microprogramming
- Vertical microprogramming
- Microinstruction formats
- Control-store organization
- Nanoprogramming
- Advantages and disadvantages
- Hardwired versus microprogrammed control
- ๐ฅ Microprogrammed control for a branch instruction
2.7 Instruction-Level Parallelism¶
- Meaning of ILP
- Sequential execution
- Overlapped execution
- Dependence between instructions
- Data dependence
- Name dependence
- Control dependence
- Pipeline parallelism
- Multiple-issue parallelism
- Limits of ILP
- Measuring ILP using CPI and IPC
2.8 Basic Concepts of Pipelining¶
- ๐ฅ Meaning of pipelining
- ๐ฅ Laundry or assembly-line analogy
- ๐ฅ Pipeline stages
- ๐ฅ Five-stage instruction pipeline
- ๐ฅ IF: Instruction Fetch
- ๐ฅ ID: Instruction Decode
- ๐ฅ EX: Execute
- ๐ฅ MEM: Memory Access
- ๐ฅ WB: Write Back
- Pipeline registers
- Pipeline clock cycle
- Pipeline latency
- ๐ฅ๐ Pipeline throughput
- Pipeline filling and draining
- ๐ฅ Ideal pipeline speedup
- Pipeline efficiency
- ๐ฅ Pipeline timing diagram
- ๐ฅ Non-pipelined versus pipelined processor
- Balanced and unbalanced pipeline stages
- Pipeline depth
- ๐ฅ Pipeline performance calculations
- ๐ฅ How pipelining increases processor performance
- ๐ฅ Ideal pipelined operation
\[
\text{Pipeline Time}=(k+n-1)t
\]
\[
\text{Ideal Speedup}
=
\frac{\text{Non-pipelined Time}}
{\text{Pipelined Time}}
\]
Here, \(k\) is the number of stages, \(n\) is the number of instructions and \(t\) is the pipeline clock time.
2.9 Pipelined Implementation of Datapath and Control¶
- ๐ฅ Pipelined datapath
- IF/ID pipeline register
- ID/EX pipeline register
- EX/MEM pipeline register
- MEM/WB pipeline register
- Movement of instructions through stages
- Passing data and control signals
- Pipelined control signals
- Register-file timing
- Memory-operation timing
- Branch handling in pipeline
- Pipeline control unit
- ๐ฅ Forwarding unit
- ๐ฅ Hazard-detection unit
- ๐ฅ Stalling and flushing
- Complete pipelined instruction execution
- ๐ฅ Pipeline timing table and diagram
- ๐ฅ Datapath modification to support data forwarding
2.10 Structural Hazards¶
- ๐ฅ Meaning of structural hazard
- ๐ฅ Resource conflict
- Single memory for instruction and data
- Register-file conflicts
- ALU resource conflicts
- Detection of structural hazards
- Pipeline stalling
- Duplication of hardware resources
- Separate instruction and data cache
- Multiport memory
- ๐ฅ Examples and timing diagrams
2.11 Data Hazards¶
- ๐ฅ๐ Meaning of data hazard
- ๐ฅ๐ Read After Write or RAW hazard
- ๐ฅ Write After Read or WAR hazard
- ๐ฅ Write After Write or WAW hazard
- True dependence
- Anti-dependence
- Output dependence
- ๐ฅ Load-use hazard
- ๐ฅ Hazard detection
- ๐ฅ Operand forwarding or bypassing
- ๐ฅ EX-to-EX forwarding
- ๐ฅ MEM-to-EX forwarding
- ๐ฅ Pipeline stall
- ๐ฅ Bubble or NOP insertion
- Compiler instruction scheduling
- Register renaming
- ๐ฅ Side effects of hazards on pipeline performance
- ๐ฅ Examples and timing diagrams
2.12 Control Hazards¶
- ๐ฅ๐ Meaning of control hazard
- ๐ฅ๐ Branch instruction
- Jump instruction
- Branch outcome and branch target
- Branch penalty
- ๐ฅ Pipeline flushing
- Stall until branch decision
- Early branch resolution
- Delayed branch
- Static branch prediction
- Dynamic branch prediction
- One-bit predictor
- Two-bit predictor
- Branch History Table
- Branch Target Buffer
- Return Address Stack
- Prediction accuracy
- Misprediction penalty
- ๐ฅ Examples and timing diagrams
2.13 Exception Handling¶
- Meaning of exception
- Exception versus interrupt
- Synchronous and asynchronous events
- Internal and external exceptions
- Arithmetic overflow
- Divide-by-zero
- Undefined instruction
- Page fault
- Hardware failure
- System call or trap
- Precise exception
- Imprecise exception
- Exception Program Counter
- Cause register
- Status register
- Exception vector
- Saving processor state
- Transferring control to a handler
- Returning from an exception
- Exception handling in a pipeline
- Flushing affected instructions
- Handling multiple simultaneous exceptions
Chapter 3: Advanced ILP, Multicore and GPU¶
3.1 Exploitation of More ILP¶
- Review of instruction-level parallelism
- Basic block
- Loop-level parallelism
- Dependence analysis
- Data dependence
- Name dependence
- Control dependence
- Pipeline limitations
- Multiple functional units
- Increased issue width
- Instruction scheduling
- Register renaming
- Branch prediction
- Speculative execution
- Memory dependence
- Limits of available parallelism
3.2 Hardware Approaches¶
- ๐ฅ Dynamic instruction scheduling
- ๐ฅ Out-of-order execution
- In-order issue and completion
- Out-of-order issue and completion
- Multiple functional units
- Register renaming
- Reorder buffer
- Reservation stations
- Scoreboarding
- ๐ฅ Tomasuloโs algorithm
- Dynamic branch prediction
- Speculative execution
- Load/store queues
- Memory disambiguation
- In-order retirement
- Precise exception support
3.3 Software and Compiler Approaches¶
- Static instruction scheduling
- Code reordering
- Loop unrolling
- Loop interchange
- Loop fusion
- Loop fission
- Software pipelining
- Register allocation
- Trace scheduling
- Predication
- Branch elimination
- Dependency analysis
- Compiler-generated parallel instructions
- Profile-guided optimization
- Advantages and limitations of compiler techniques
3.4 Dynamic Scheduling¶
- ๐ฅ Need for dynamic scheduling
- ๐ฅ Dynamic-scheduler block diagram
- ๐ฅ Handling variable execution latency
- Scoreboarding technique
- ๐ฅ Tomasuloโs algorithm
- ๐ฅ Issue, execute and write-result stages
- Reservation station
- Common Data Bus
- Register-status table
- Operand availability
- Register renaming
- RAW, WAR and WAW handling
- Out-of-order execution
- In-order retirement
- Worked instruction-scheduling example
3.5 Speculation¶
- Meaning of speculation
- Control speculation
- Data speculation
- Hardware speculation
- Software speculation
- Branch prediction
- Speculative instruction execution
- Reorder buffer
- Instruction commit or retirement
- Recovery after wrong speculation
- Exception handling during speculation
- Benefits and risks of speculation
3.6 Multiple-Issue Processors¶
- Meaning of multiple issue
- Issue width
- Superscalar processor
- Statically scheduled multiple issue
- Dynamically scheduled superscalar processor
- Very Long Instruction Word or VLIW
- Explicitly Parallel Instruction Computing or EPIC
- Instruction pairing
- Issue restrictions
- Functional-unit conflicts
- Dependency checking
- In-order versus out-of-order issue
- Superscalar versus VLIW
- CPI below one and IPC above one
- Limitations of multiple-issue execution
3.7 ILP and Thread-Level Parallelism¶
- Instruction-level parallelism
- Thread-level parallelism or TLP
- Process and thread
- Hardware thread
- Fine-grained multithreading
- Coarse-grained multithreading
- Simultaneous Multithreading or SMT
- Hyper-Threading
- Multiprocessing
- Shared-memory multiprocessor
- Distributed-memory system
- ILP versus TLP
- Advantages and limitations of multithreading
- โญ๐ Single Program, Multiple Data or SPMD
- ๐ฅโญ๐ Flynnโs classification in parallel processing
3.8 Multicore Processors¶
- Meaning of multicore processor
- Single-core versus multicore
- Homogeneous and heterogeneous cores
- Shared and private caches
- Inter-core communication
- Cache coherence
- Coherence problem
- Snooping protocol
- Directory-based protocol
- MESI protocol
- Memory consistency
- On-chip interconnection
- Bus, ring, mesh and Network-on-Chip
- Scalability
- Power wall and thermal limitation
- Parallel-programming challenges
- Examples of modern multicore processors
3.9 Graphics and Computing GPUs¶
- CPU versus GPU
- GPU architecture
- Graphics pipeline
- Streaming multiprocessor
- GPU core
- ๐ฅโญ๐ SIMD and SIMT execution
- Warp or wavefront
- Thread, block and grid
- GPU memory hierarchy
- Registers
- Shared memory
- Global memory
- Constant and texture memory
- Coalesced memory access
- Branch divergence
- General-Purpose GPU or GPGPU
- CUDA and OpenCL concepts
- GPU applications
- Advantages and limitations of GPU computing
- Heterogeneous CPUโGPU systems
3.10 Current Processor Trends¶
- Many-core processors
- Heterogeneous computing
- Chiplet-based processors
- System-on-Chip or SoC
- AI and machine-learning accelerators
- Tensor-processing units
- Neural-processing units
- Energy-efficient architecture
- Domain-specific architecture
- Edge-computing processors
- Mobile-processor architecture
- Vector extensions
- Open ISA such as RISC-V
- Advanced packaging
- 3D stacking
- Security-related processor features
- Cloud and data-centre processors
Chapter 4: Arithmetic for Computers¶
4.1 Number Representation Fundamentals¶
- Binary, octal, decimal and hexadecimal systems
- Number-system conversion
- Unsigned integers
- Signed-magnitude representation
- Oneโs complement
- Twoโs complement
- Range of signed and unsigned numbers
- Sign extension
- Fixed-point numbers
- Overflow and underflow
- Binary fractions
- Arithmetic shift and logical shift
4.2 Binary Addition¶
- Rules of binary addition
- Addition of unsigned numbers
- Addition of signed numbers
- Twoโs-complement addition
- Carry and overflow
- Half adder
- Full adder
- Ripple-carry adder
- Parallel binary adder
- Adderโsubtractor circuit
- Examples and numerical problems
4.3 Binary Subtraction¶
- Rules of binary subtraction
- Direct binary subtraction
- Subtraction using oneโs complement
- Subtraction using twoโs complement
- Borrow and overflow
- Signed-number subtraction
- Adderโsubtractor implementation
- Examples and numerical problems
4.4 Fast Adders¶
- Delay in ripple-carry adder
- Carry propagation and carry generation
- Carry Look-Ahead Adder or CLA
- Generate and propagate functions
- Carry-look-ahead equations
- Block carry-look-ahead
- Carry-select adder
- Carry-skip adder
- Carry-save adder
- Parallel-prefix adder
- KoggeโStone adder concept
- Comparison of adder speed, area and complexity
For each bit:
\[
G_i=A_iB_i
\]
\[
P_i=A_i\oplus B_i
\]
\[
C_{i+1}=G_i+P_iC_i
\]
4.5 Binary Multiplication¶
- ๐ฅ๐ Basic multiplication algorithm
- ๐ฅ๐ Multiplication-algorithm flowchart
- ๐ฅ๐ Multiplicand and multiplier
- ๐ฅ๐ Partial products
- ๐ฅ๐ Shift-and-add multiplication
- ๐ฅ๐ Hardware multiplication unit
- ๐ฅ๐ Algorithm and hardware diagram for multiplication
- Sequential multiplication
- ๐ฅ๐ Combinational multiplier
- ๐ฅ๐ Signed multiplication
- ๐ฅ๐ Boothโs multiplication algorithm
- Modified Booth algorithm
- Carry-save multiplication
- ๐ฅ๐ Array multiplier
- Overflow in multiplication
- ๐ฅ๐ Worked numerical problems
- ๐ฅ Detailed design of a 4-bit binary multiplier
4.6 Binary Division¶
- ๐ฅ๐ Dividend, divisor, quotient and remainder
- ๐ฅ๐ Shift-and-subtract division
- ๐ฅ๐ Division-algorithm flowchart
- ๐ฅ๐ Restoring division algorithm
- ๐ฅ๐ Non-restoring division algorithm
- Signed binary division
- ๐ฅ๐ Hardware division unit
- Division by zero
- Overflow condition
- Comparison of restoring and non-restoring division
- ๐ฅ๐ Worked numerical problems
4.7 Floating-Point Numbers¶
- Need for floating-point representation
- Scientific notation
- Normalized and denormalized numbers
- Sign, exponent and significand
- Biased exponent
- ๐ฅ IEEE 754 standard
- ๐ฅ Single-precision format
- ๐ฅ Double-precision format
- Half-precision concept
- Positive and negative zero
- Infinity
- Not a Number or NaN
- Subnormal numbers
- ๐ฅ Conversion from decimal to IEEE 754
- ๐ฅ Conversion from IEEE 754 to decimal
- Range and precision
- Overflow and underflow
- Guard, round and sticky bits
- Rounding modes
- Rounding error
- Floating-point accuracy
\[
N=(-1)^S\times(1.F)\times2^{E-\text{Bias}}
\]
4.8 Floating-Point Addition and Subtraction¶
- Compare exponents
- Align significands
- Add or subtract significands
- Determine result sign
- Normalize result
- Round result
- Check overflow and underflow
- Hardware flowchart
- Worked numerical examples
4.9 Floating-Point Multiplication¶
- Determine sign
- Add exponents
- Subtract exponent bias
- Multiply significands
- Normalize result
- Round result
- Check exceptional conditions
- Hardware flowchart
- Worked numerical examples
4.10 Floating-Point Division¶
- Determine sign
- Subtract exponents
- Add exponent bias
- Divide significands
- Normalize and round
- Check exceptional conditions
- Hardware flowchart
- Worked numerical examples
Chapter 5: Memory System¶
5.1 Need for a Hierarchical Memory System¶
- Difference between processor speed and memory speed
- Memory wall
- Memory hierarchy
- Registers
- Cache memory
- Main memory
- Secondary storage
- Archival storage
- Speed, cost and capacity relationship
- ๐ฅ๐ Locality of reference
- ๐ฅ๐ Temporal locality
- ๐ฅ๐ Spatial locality
- Sequential locality
- Average Memory Access Time
- Principle of inclusion
5.2 Types and Characteristics of Memory¶
- Memory capacity
- ๐ฅ Word and addressable unit
- Access method
- Sequential access
- Direct access
- Random access
- ๐ Associative access
- ๐ฅ Memory access time
- Memory cycle time
- Transfer rate
- Volatile and non-volatile memory
- Read-only and read-write memory
- Semiconductor memory
- Magnetic memory
- Optical memory
- SRAM
- DRAM
- SDRAM and DDR memory
- ROM
- PROM
- EPROM
- EEPROM
- Flash memory
- Hard disk and solid-state drive
- Comparison of different memory types
5.3 Main Memory Organization¶
- ๐ฅ Memory cells
- ๐ฅ Internal organization of bit cells
- ๐ฅ Memory words
- ๐ฅ Memory address
- Byte-addressable memory
- Word-addressable memory
- ๐ฅ๐ Memory chips and memory blocks
- ๐ฅ๐ Address decoding
- ๐ฅ๐ Memory expansion
- ๐ฅ๐ Increasing word length
- ๐ฅ๐ Increasing number of words
- Memory banks
- Memory interleaving
- Low-order interleaving
- High-order interleaving
- Error detection and correction
- Parity bit
- ECC memory
- Hamming-code concept
- ๐ฅ๐ Memory-module design using smaller memory chips
- ๐ Design of a \(1K\times8\) memory
- ๐ฅ Design of a \(2M\times32\) memory with \(512K\times8\) SRAM chips
5.4 Cache Memory Fundamentals¶
- ๐ฅ๐ Meaning and purpose of cache
- ๐ฅ๐ Cache hit
- ๐ฅ๐ Cache miss
- ๐ฅ๐ Hit rate
- ๐ฅ๐ Miss rate
- Hit time
- ๐ฅ๐ Miss penalty
- ๐ฅ๐ Cache line or memory block
- Cache controller
- ๐ฅ๐ Cache mapping
- ๐ฅ๐ Mapping function
- ๐ฅ๐ Direct-mapped cache
- ๐ฅ๐ Fully associative cache
- ๐ฅ๐ Set-associative cache
- ๐ฅ๐ Tag, index and offset fields
- Valid bit
- Dirty bit
- Cache-address calculation
- Cache-size calculation
- Read hit and read miss
- Write hit and write miss
\[
\text{AMAT}
=
\text{Hit Time}
+
(\text{Miss Rate}\times\text{Miss Penalty})
\]
5.5 Cache Replacement and Writing Policies¶
- Need for replacement
- Least Recently Used or LRU
- First In First Out or FIFO
- Random replacement
- Least Frequently Used or LFU
- ๐ฅ Write-through policy
- ๐ฅ Write-back policy
- ๐ฅ Advantages and disadvantages of write-through
- ๐ฅ Advantages and disadvantages of write-back
- Write allocate
- No-write allocate
- Write buffer
- Multilevel cache
- Inclusive, exclusive and non-inclusive cache
- Unified and split cache
- Instruction and data cache
5.6 Improving Cache Performance¶
- Reducing miss rate
- Reducing miss penalty
- Reducing hit time
- Compulsory miss
- Capacity miss
- Conflict miss
- Coherence miss
- Larger block size
- Larger cache
- Higher associativity
- Multilevel cache
- Victim cache
- Prefetching
- Critical-word-first
- Early restart
- Non-blocking cache
- Write buffer
- Cache optimization by compiler
- Loop interchange and loop blocking
- Cache-performance numerical problems
5.7 Virtual Memory¶
- ๐ฅ๐ Meaning and purpose of virtual memory
- ๐ฅ๐ Virtual and physical addresses
- ๐ฅ๐ Address translation
- ๐ฅ๐ Mapping between virtual and physical memory
- Page and page frame
- Page table
- Page Table Entry or PTE
- Valid and dirty bits
- Protection bits
- Page fault
- Page-fault handling
- Demand paging
- Translation Lookaside Buffer or TLB
- TLB hit and miss
- Multilevel page table
- Inverted page table
- Page size
- Internal fragmentation
- Memory protection
- Shared pages
- Virtual-memory access-time calculation
5.8 Memory Management Techniques¶
- Contiguous memory allocation
- Fixed partitioning
- Variable partitioning
- Internal fragmentation
- External fragmentation
- Compaction
- Paging
- Segmentation
- Segmentation with paging
- Page-replacement algorithms
- FIFO replacement
- Optimal replacement
- LRU replacement
- Clock or second-chance replacement
- Working-set concept
- Thrashing
- Memory protection and sharing
- Comparison of paging and segmentation
5.9 Associative Memory¶
- ๐ Meaning of associative memory
- ๐ Content-Addressable Memory or CAM
- ๐ Search by content
- ๐ Match logic
- ๐ Associative-memory organization
- ๐ Read and write operations
- ๐ Mask register
- ๐ Exact and partial matching
- ๐ Applications in TLB and cache
- ๐ Advantages and disadvantages
- ๐ Associative memory versus conventional memory
Chapter 6: Input/Output Organization¶
6.1 Accessing Input/Output Devices¶
- I/O-device characteristics
- Peripheral devices
- I/O module
- I/O controller
- Device controller
- Data register
- Status register
- Control register
- I/O port
- Input and output instructions
- Memory-mapped I/O
- Isolated or port-mapped I/O
- Synchronous and asynchronous transfer
- Handshaking
- Serial and parallel communication
- I/O bus operation
6.2 Programmed Input/Output¶
- Meaning of programmed I/O
- Polling
- Busy-waiting
- Status checking
- Input-operation sequence
- Output-operation sequence
- Processor involvement
- Advantages and disadvantages
- Programmed-I/O flowchart
- Suitable applications
6.3 Interrupts¶
- Meaning of interrupt
- Need for interrupt-driven I/O
- Interrupt-request signal
- Interrupt acknowledgement
- Interrupt Service Routine or ISR
- Interrupt vector
- Vectored and non-vectored interrupts
- Maskable and non-maskable interrupts
- Hardware and software interrupts
- Internal and external interrupts
- Interrupt priority
- Daisy-chain priority
- Parallel priority
- Nested interrupts
- Saving and restoring processor context
- Interrupt latency
- Return from interrupt
- Interrupt-driven I/O sequence
- Polling versus interrupt-driven I/O
6.4 Direct Memory Access¶
- ๐ Meaning and need for DMA
- ๐ DMA controller
- ๐ DMA registers
- ๐ DMA request and acknowledgement
- ๐ Data transfer between I/O and memory
- ๐ Bus arbitration
- ๐ Burst-mode DMA
- ๐ Cycle-stealing DMA
- ๐ Transparent DMA
- ๐ Block transfer
- ๐ Processor involvement
- ๐ DMA operation sequence
- ๐ Advantages and disadvantages
- ๐ Programmed I/O versus interrupt I/O versus DMA
6.5 Interface Circuits¶
- Purpose of an interface circuit
- I/O ports
- Data, status and control registers
- Address decoder
- Buffer register
- Tri-state buffer
- Handshaking circuits
- Strobe control
- Serial interface
- Parallel interface
- Synchronous interface
- Asynchronous interface
- Device-controller connection
- Input-interface circuit
- Output-interface circuit
- Typical interface-circuit diagram
6.6 Standard I/O Interfaces¶
- Need for standard interfaces
- Compatibility
- Data-transfer speed
- Device addressing
- Plug-and-play
- Error detection
- Physical and logical interface
- Serial versus parallel interface
6.7 PCI¶
- Meaning of Peripheral Component Interconnect
- PCI bus architecture
- PCI devices
- Bus master and target
- Address and data transfer
- Bus arbitration
- PCI configuration space
- PCI Express or PCIe
- PCIe lanes
- Point-to-point connection
- PCI versus PCIe
- Applications, advantages and limitations
6.8 SCSI¶
- Meaning of Small Computer System Interface
- SCSI architecture
- Initiator and target
- SCSI bus
- Device identification
- Command and data phases
- Parallel and Serial Attached SCSI
- Storage-device applications
- Advantages and limitations
- SCSI versus other storage interfaces
6.9 USB¶
- Meaning of Universal Serial Bus
- USB architecture
- Host, hub and device
- USB topology
- Endpoint and pipe
- USB transfer types
- Control transfer
- Bulk transfer
- Interrupt transfer
- Isochronous transfer
- Device enumeration
- Plug-and-play
- Power delivery
- USB connectors
- USB generations and speed classes
- Advantages and limitations
6.10 Comparison of I/O Interfaces¶
- PCI, PCIe, SCSI and USB comparison
- Serial versus parallel operation
- Internal versus external connection
- Transfer speed
- Device support
- Communication method
- Cost and complexity
- Common applications
Supporting Topics Required for the Mini-Book¶
- Boolean algebra and logic gates
- Combinational and sequential circuits
- Multiplexers and decoders
- Flip-flops and registers
- Counters
- Binary and hexadecimal conversion
- Signed-number representation
- ๐ฅ Register Transfer Language
- ๐ฅ๐ Assembly-language basics
- ๐ฅ MIPS instruction formats
- ๐ฅ๐ Memory-address calculation
- Basic operating-system concepts
- ๐ฅ Basic compiler and assembler concepts
- ๐ฅ๐ Finite State Machine
- ๐ฅโญ๐ Performance numerical problems
- ๐ฅ Pipeline timing diagrams
- ๐ฅ๐ Cache numerical problems
- ๐ฅ๐ Virtual-memory numerical problems
- ๐ฅ IEEE 754 conversion problems
- ๐ฅ๐ Arithmetic-algorithm flowcharts
Exact Teacher-Suggested Practice Problems¶
Current Teacherโs Exact Priority Problems ๐ฅ¶
- ๐ฅ What are the classes of computers? Explain their characteristics.
- ๐ฅ Explain the layers of computer-system architecture with a neat diagram.
- ๐ฅ Define throughput and response time. Compare them as performance measures.
- ๐ฅ Discuss the basic functional units of a computer.
- ๐ฅ Briefly discuss the bus structure of a processor.
- ๐ฅ Define ISA and explain MIPS instruction formats with examples.
- ๐ฅ Differentiate between RISC and CISC.
- ๐ฅ Write the execution steps of
Load R2, LOC. - ๐ฅ Explain the characteristics of a RISC processor.
- ๐ฅ Draw the three-bus CISC-style processor organization.
- ๐ฅ Write the execution steps and architecture for
Add (R3), R1. - ๐ฅ Explain MIPS addressing modes with examples.
- ๐ฅ Translate
f = (a + b) - (c + d); g = f + A[10];into MIPS assembly. - ๐ฅ Explain the complete compilation process of a C program.
- ๐ฅ Explain various addressing modes with examples.
- ๐ฅ Define an instruction and explain its computer representation.
- ๐ฅ Explain the processor datapath with a block diagram.
- ๐ฅ Explain datapath control signals.
- ๐ฅ Explain a dynamic scheduler with a block diagram.
- ๐ฅ Explain a microprogrammed control unit for a branch instruction.
- ๐ฅ Explain the purpose of a control unit.
- ๐ฅ Define word, address and memory access time.
- ๐ฅ Explain how pipelining increases processor performance.
- ๐ฅ Explain ideal pipelined operation.
- ๐ฅ Explain the issues of pipelined operation.
- ๐ฅ Explain operand forwarding with an example.
- ๐ฅ Show datapath modifications for data forwarding.
- ๐ฅ Define a data hazard, its solutions and its performance effects.
- ๐ฅ Show a processor multiplication algorithm and hardware with an example.
- ๐ฅ Divide \((1010)_2\) by \((0010)_2\), showing all steps.
- ๐ฅ Represent \(-0.625_{10}\) in IEEE 754 single and double precision.
- ๐ฅ Design a 4-bit binary multiplier.
- ๐ฅ Apply Boothโs algorithm to \(16\times(-2)\).
- ๐ฅ Explain performance using clock rate, CPI and MIPS.
- ๐ฅ Solve the P1, P2 and P3 processor-performance problem.
- ๐ฅ Explain Flynnโs classification with examples.
- ๐ฅ Define cache, cache hit, cache miss and miss penalty.
- ๐ฅ Compare write-through and write-back cache policies.
- ๐ฅ Write RTL for MIPS
addu,addi,lw,swandbeq. - ๐ฅ Describe the basic connection of memory to a processor.
- ๐ฅ Explain the internal organization of bit cells in a memory chip.
- ๐ฅ Design a \(2M\times32\) memory using \(512K\times8\) SRAM chips.
- ๐ฅ Explain virtual memory and the need for a cache-mapping function.
Another Teacherโs Exact Priority Topics ๐¶
- ๐ Von Neumann architecture and the two basic computer-architecture models.
- ๐ Throughput and speedup.
- ๐ Multiplication and division algorithms.
- ๐ Boothโs multiplication algorithm with a flowchart and example.
- ๐ Mooreโs Law and Amdahlโs Law.
- ๐ Instruction cycle and its state diagram.
- ๐ Big-endian and little-endian byte ordering.
- ๐ Execution steps for an instruction, including one-operand and three-address forms.
- ๐ Memory mapping, memory blocks and cache-mapping functions.
- ๐ Different cache-mapping techniques.
- ๐ Virtual memory.
- ๐ Associative memory.
- ๐ Cache hit, cache miss, hit rate and miss rate.
- ๐ DMA controller.
- ๐ Vector processing and array processing.
- ๐ Flynnโs classification.
- ๐ SPMD and related parallel-processing models.
- ๐ Data hazards and control hazards.
- ๐ Direct and indirect addressing modes.
- ๐ Design of a \(1K\times8\) memory.
- ๐ Temporal and spatial locality.
- ๐ Representation of an expression such as \((A+B)\times(C+D)\) in assembly language.
Previous Faculty Topics Retained โญ¶
- โญ Historical evolution of computer architecture
- โญ Development during the last 30 years
- โญ Intel 80386, 80486 and Pentium architectures
- โญ Flynnโs classification
- โญ SIMD and SPMD
- โญ Vector and parallel processing
- โญ Performance and speedup
- โญ Amdahlโs Law
Suggested Revision Order¶
- Study all ๐ฅโญ๐ topics first.
- Then study topics carrying any two markers.
- Next complete the remaining single-marker topics.
- Finally revise every unmarked supporting topic.