Computer Architecture and Parallel Processing - Exhaustive Course Notes

Faculty Profile and Course Context

• Instructor Details

  • Name: Mr. Ankur Kumar Varshney
  • Designation: Assistant Professor, IT Department
  • Qualification: B.Tech(CSE), M.Tech(CSE), pursuing Ph.D. from Invertis University, Bareilly.
  • Area of Expertise: Data Structure and Algorithms, Theory of Automata & Formal Languages, Computer Architecture and Parallel Processing.

• Course Metadata

  • Subject Name: Computer Architecture and Parallel Processing (CAPP).
  • Subject Code: CCSE0304 (also referenced as BCSE0305X in external exam documents).
  • Department: Information Technology (IT).
  • Semesters: B.Tech IT 3rd Semester.
  • Institute: Noida Institute of Engineering and Technology (NIET), Greater Noida (Autonomous Institute).

Syllabus and Module Breakdown

• Unit 1: Introduction (09 Hours)

  • Covers Computer Organization and Architecture.
  • Functional units of digital systems and their interconnections.
  • Buses: architecture, types, and bus arbitration (including various types).
  • Transfer Logic: Register, bus, and memory transfer.
  • CPU Design: Processor organization, general register organization, stack organization, and addressing modes.

• Unit 2: ALU Unit (09 Hours)

  • Arithmetic and Logic Unit: Multiplication algorithms (Signed operand, Booth’s algorithm, array multiplier).
  • Division and logic operations.
  • Floating point arithmetic operation and design.
  • IEEE Standard for Floating Point Numbers.

• Unit 3: Control Unit (09 Hours)

  • Detailed study of control unit techniques and instruction cycles.

• Advanced Topics (Unit 4 & 5 Context)

  • Pipelining and RISC/CISC architectures.
  • Parallel architectures: memory hierarchy, cache coherence (MSI, MESI, Dragon protocols).
  • Scalable shared memory systems: Directory coherence protocols, memory consistency models (sequential and relaxed), and synchronization mechanisms.
  • Real-world case studies: Origin and Sequent NUMA systems.

Branch-Wise Applications of CAPP

• Computer Science Engineering (CSE)

  • CPU Design & Optimization using control unit and ALU design principles.
  • Operating System design based on memory hierarchy and bus architecture.
  • Compiler Design utilizing instruction formats and pipelining.
  • Parallel Programming focusing on cache coherence and memory models.

• Information Technology (IT)

  • Data Centers utilizing parallel architectures and memory hierarchy.
  • Network & Cloud Systems involving memory consistency and multiprocessor design.
  • Performance Analysis Tools based on cache miss and coherence protocols.
  • Virtualization Techniques based on memory and processor organization.

• Electronics & Communication Engineering (ECE)

  • Embedded Systems using ALU design and instruction cycles.
  • VLSI Design including Booth's algorithm, array multiplier, and stack organization.
  • Signal Processing Hardware with optimized arithmetic logic units.
  • Microprocessor/Microcontroller Design utilizing instruction sets and control units.

• Artificial Intelligence / Data Science

  • AI Accelerators involving parallel processing architectures.
  • Hardware for ML Algorithms using SIMD/MIMD models from Flynn’s classification.
  • High-Performance Computing (HPC) with shared memory system optimizations.

Computer Architecture vs. Computer Organization

• Computer Architecture

  • Refers to attributes of a system visible to the programmer (logical execution).
  • Focuses on "What the system does."
  • Includes instruction sets, number of bits used for data representation, addressing techniques, and data types.
  • It serves as the abstract model of the system.

• Computer Organization

  • Refers to the operational units and their interconnections that realize architectural specifications.
  • Focuses on "How to implement the system."
  • Includes hardware details like physical units, circuit designs, peripherals, adders, and control signals.
  • Indicates the physical performance of the system.

Functional Units of a Computer System

• Input Unit

  • Consists of devices (keyboard, mouse, scanner, joystick) that take user input and convert it into binary language understandable by the computer.

• Central Processing Unit (CPU)

  • The "brain" of the computer; interprets instructions fetched from memory.
  • Arithmetic and Logic Unit (ALU): Performs mathematical calculations ($+$, $-$, $\times$, $/$) and logical decisions (identifying greater than, less than, or equal to).
  • Control Unit (CU): Coordinates data flow in/out of the CPU and controls ALU, memory registers, and I/O units. It decodes instructions and sends control signals.
  • Memory Unit (MU): Attached directly to the CPU for high-speed storage of instructions currently being processed.

• Memory Types

  • Primary / Main Memory: Known as RAM (Random Access Memory). Establishes direct communication with the CPU.
  • Secondary Memory / Mass Storage / Auxiliary Memory: Used for backup storage (magnetic disks, tapes). Information must be transferred to primary memory before CPU access.

• Output Unit

  • Converts binary results from the CPU into human-understandable forms using devices such as monitors, printers, and plotters.

Bus Systems and Architectures

• Definition of a BUS

  • A common pathway or subsystem through which information flows between computer components (CPU, memory, and I/O devices).

• The System Bus

  • A single bus that combines the functions of the data, address, and control buses.

• Types of Buses

  • Data Bus: Bidirectional; carries actual data to and from main memory. Width can be $8$, $16$, $32$, or more bits.
  • Address Bus: Unidirectional; carries the memory address (not the data) where information is to be read or written. Sent from CPU to Memory/IO.
  • Control Bus: Bidirectional; carries timing and control signals (Memory Read/Write, I/O Read/Write) to coordinate system activities.

• Bus Connectivity Structures

  • Single Bus Structure: All units are connected to a single common bus. Simple but limited.
  • Traditional Multiple Bus Configuration: Features a Local Bus (Processor to Cache), a System Bus (Cache to Main Memory), and an Expansion Bus (for low-speed I/O like modems, serial ports, and SCSI).
  • High-Speed Bus Configuration: Integrates a High-Speed Bus for demand-heavy devices (Fast Ethernet at $100\,Mbps$, Video, Graphics) via a bridge controller, insulating them from processor changes.

Bus Arbitration

• Definition: The process where a "Bus Master" (controller with current access) yields control to another requesting unit. A "Bus Arbiter" decides which unit becomes the next master.

• Centralized Arbitration

  • A single arbiter (Processor or DMA controller) handles requests.
  • Daisy Chaining: Simple/cheap. Bus grant signals propagate serially through devices. If a device fails, the whole chain fails. Priority depends on physical position.
  • Polling (Rotating Priority): Control lines generate master addresses. If a requesting master recognizes its address, it takes control. Failure of one device does not stop the system.
  • Independent Request (Fixed Priority): Each master has a private request/grant line pair. Fast response but high hardware cost due to many control lines.

• Distributed Arbitration

  • All devices participate in selecting the next bus master; no central controller exists.

Register and Memory Transfer Logic

• Core Registers and Functions

  • DR (Data Register): $16$-bit; holds memory operands.
  • AR (Address Register): $12$-bit; holds memory addresses.
  • AC (Accumulator): $16$-bit; general processor register.
  • IR (Instruction Register): $16$-bit; holds the current instruction code.
  • PC (Program Counter): $12$-bit; holds the address of the next instruction.
  • TR (Temporary Register): $16$-bit; holds temporary data.
  • INPR (Input Register): $8$-bit; holds input characters.
  • OUTR (Output Register): $8$-bit; holds output characters.

• Register Transfer Language (RTL) Symbols

  • Denoting a Register: Capital letters (e.g., $MAR$, $R2$).
  • Parts of a Register: Parentheses (e.g., $R2(0-7)$).
  • Information Transfer: Arrow (e.g., $R2 \leftarrow R1$).
  • Conditional Transfer: $P: R2 \leftarrow R1$ (Transfer occurs if control function $P=1$).
  • Simultaneous Operations: Comma (e.g., $R2 \leftarrow R1, R1 \leftarrow R2$).

• Bus Transfer Implementation

  • Using Multiplexers: A bus for $k$ registers of $n$ bits each requires $n$ multiplexers. Each multiplexer is of size $k \times 1$. Number of select lines required is $\log_2(k)$.
  • Using Three-State Buffers: Provides three states (Logic $0$, Logic $1$, and High-Impedance). High-impedance acts as an open circuit. Decoders are used to ensure only one register drives the bus at a time.

• Memory Transfer Operations

  • Read: $DR \leftarrow M[AR]$. Data from memory word at address $AR$ is placed into $DR$.
  • Write: $M[AR] \leftarrow R1$. Data from register $R1$ is stored in the memory word at address $AR$.

Processor and Stack Organization

• Processor Organization Categories

  1. Single Accumulator Organization: Uses one address field. Instruction example: $ADD\,X$ (implies $AC \leftarrow AC + M[X]$).
  2. General Register Organization: Uses two or three address fields. Example: $MULT\,R1, R2, R3$ (means $R1 \leftarrow R2 \times R3$). High efficiency due to large register set; requires intelligent compilers.
  3. Stack Organization: Uses PUSH and POP instructions with zero-address instructions for arithmetic (LIFO structure).

• Stack Logic

  • Stack Pointer (SP): Pointer to the top of the stack.
  • Register Stack Operations:
    • PUSH: $SP \leftarrow SP + 1$, followed by $M[SP] \leftarrow DR$. Check $FULL$ flag ($SP=0$).
    • POP: $DR \leftarrow M[SP]$, followed by $SP \leftarrow SP - 1$. Check $EMPTY$ flag ($SP=0$).
  • Memory Stack: A portion of main memory is assigned to stack usage. In some implementations, the stack grows toward decreasing addresses ($PUSH$: $SP \leftarrow SP - 1$).

• Polish Notation (Arithmetic Evaluation)

  • Infix: $A \times B + C \times D$
  • Prefix (Polish): $+ \times AB \times CD$
  • Postfix (Reverse Polish Notation / RPN): $AB \times CD \times +$. RPN is the preferred form for stack-based execution.

Addressing Modes

Addressing modes define how the address field of an instruction is interpreted to find the operand.

• Implied Mode: No address field; operand is defined by the instruction (e.g., Complement Accumulator).
• Immediate Mode: The operand is explicitly specified in the instruction (e.g., $Address = 500$ as data).
• Register Mode: Operands are stored in specific CPU registers.
• Register Indirect Mode: The instruction specifies a register that holds the effective address of the operand.
• Direct Address Mode: The instruction field contains the effective address of the operand memory location.
• Indirect Address Mode: The address field points to a memory location that contains the actual effective address.
• Relative Address Mode: Effective Address ($EA$) = Address part of instruction + Content of Program Counter ($PC$).
• Indexed Addressing Mode: $EA$ = Address part of instruction + Content of Index Register ($XR$).
• Base Register Mode: $EA$ = Address part of instruction + Content of Base Register.
• Auto-increment/Auto-decrement: Similar to register indirect but automatically updates the register value after/before use.

Evaluation and Exam Schemes

• Credit Structure: Total of $23$ credits for 3rd semester.

• CAPP Evaluation (CCSE0304):

  • Internal Assessment: $50$ marks (includes $30$ for CT and $20$ for TA).
  • End Semester Exam: $100$ marks.
  • Total Marks: $150$.
  • Schedule: Exam Duration of $3\,Hours$.

• Question Paper Template (100 Marks Total)

  • Section A (20 Marks): 10 parts of 1 mark each (MCQs/True-False) + 5 parts of 2 marks each.
  • Section B (30 Marks): Choice-based questions, 5 parts of 6 marks each.
  • Section C (50 Marks): Choice-based deep-dive questions, 5 parts of 10 marks each.

Daily Quizzes and Knowledge Assessment

• Architecture vs. Organization

  • Q1: Computer Architecture deals with functional behavior.
  • Q2: Computer Organization is concerned with hardware implementation.
  • Q3: Architecture is visible to the programmer.
  • Q4: Cache memory design is an example of organization.

• Functional Units

  • Q1: ALU performs arithmetic operations.
  • Q2: Control Unit manages system operations.
  • Q3: Input Unit accepts user data.
  • Q4: Output Unit displays results.

• Bus Systems

  • Q1: A bus transfers information.
  • Q2: The data bus is bidirectional.
  • Q3: The address bus carries addresses and is unidirectional.
  • Q19: Pipelining improves execution speed.

• Registers and Stack

  • Q1: A register is high-speed CPU storage.
  • Q2: Program Counter ($PC$) stores the address of the next instruction.
  • Q3: Stack follows Last-In First-Out ($LIFO$) logic.
  • Q4: The stack insert operation is called $PUSH$.

• General Logic

  • Q1: $RTL$ stands for Register Transfer Language.
  • Q6: A flip-flop stores $1\,bit$ of information.
  • Q26: The standard for floating-point arithmetic is $IEEE\,754$.
  • Q28: Booth's Algorithm is applied to binary numbers.