CS704 — Midterm Summary (Lectures 1–22)

📘 Lecture 1 — Introduction

📖 Overview: This lecture introduces the course on Advanced Computer Architecture, establishing the prerequisite knowledge required and defining core concepts like architecture versus organization. It provides a detailed historical timeline of computer development from the 1940s through the microprocessor era, outlines the course focus on quantitative design principles, and explains the fundamental perspectives and design cycle of computer architecture.

🗂️ Topics Covered

The lecture begins by defining computer architecture vs. organization and then presents a comprehensive academic and commercial history of computing from ENIAC/EDVAC through modern microprocessors. It introduces the course focus on quantitative principles, the textbook, and course style. The four perspectives of computer architecture (processor design, memory hierarchy, I/O and storage, multiprocessors and networks) are explained. Finally, the computer design cycle is discussed, covering technology trends, performance measurement, cost analysis, and computer generations.

📝 Lecture Summary

Introduction

This course of Advanced Computer Architecture assumes students have basic knowledge of digital logic design, computer organization and design, programming model of microprocessor, memory and input/output interfacing, and fundamentals of computer architecture. The instructor, Dr. Muhammad Ashraf Chughtai, completed his Ph.D. from the University of Manchester (UMIST) UK in 1986 and spent 32 years at UET Lahore.

Computer System

A computer system is a collection of Central Processing Unit, memory system, and peripheral devices, all interconnected by groups of conductors called buses.

Computer Architecture Versus Organization

Architecture refers to those attributes of a computer visible to a programmer or compiler writer, such as instruction set, addressing techniques, and I/O mechanisms. Members of each family (e.g., Intel x86 family and IBM family) share the same basic architecture and have code compatibility. Organization refers to how the features of a computer are implemented; i.e., control signal generation as FSM or microprogramming, memory technology (SRAM, DRAM), and hardware or software-based realization of operations (multiplication by hardware or algorithmically). The organization of the same architecture may differ between different versions.

Academic History

In 1944, John von Neumann introduced the concept of the stored-program computer, referred to as Electronic Discrete Variable Automatic Computer (EDVAC). In 1945/46, the world‘s first operational electronic general-purpose computer, Electronic Numerical Integrator And Calculator (ENIAC), was built at the Moore School of the University of Pennsylvania. ENIAC used 18,000 vacuum tubes, was 80 feet long, and could perform 1900 additions per second. In 1946, the Institute for Advanced Study (IAS) at Princeton introduced the IAS machine which was roughly 10 times faster than ENIAC. In 1948, a small prototype stored-program machine, Mark-I, was built at the University of Manchester, followed by Harvard computers (Mark-II, III, IV) known as Harvard Architecture, which had separate memories for instructions and data. In 1949, Maurice Wilkes of Cambridge University built the world‘s first full-scale, operational stored program computer, Electronic Delay Storage Automatic Calculator (EDSAC).

In 1949, the Eckert-Mauchly Computer Corporation built the first machine BINAC. The company was acquired by Remington-Rand, where the first general-purpose Universal Automatic Computer UNIVAC-I was produced in 1951, sold for $1 million. In 1952, IBM produced its first stored-program computer, the IBM-701. In 1963, Seymour Cray announced the first supercomputer, CDC 6600, from Control Data Corporation (CDC). In 1964, CDC announced the System/360 series with models 40, 50, 65, and 75, varying in clock rate (1.6-5.1 MHz), memory size (32KB-1 MB), cost ($0.225M – 1.900M), and performance. In 1965, Digital Equipment Corporation (DEC) introduced the first low-cost minicomputer, the PDP-8, for under $0.02M. In 1976, Cray Research Inc. (formed by Seymour Cray when he left CDC in 1970) announced the world‘s fastest, most expensive, and best cost-versus-performance supercomputer, the Cray-I.

Microprocessors 1971 – 2006

In 1971, while Cray was creating the world‘s most expensive machines, Intel introduced the first cheap microprocessor, the 4004. In 1977, the personal computer Apple-II was introduced by Steve Jobs and Steve Wozniak. In 1981, IBM announced personal computers employing Intel's microprocessor 80x86 and running the Microsoft operating system. With the introduction of personal computers, the era of supercomputers could not last more than two decades. In 1996, Cray Research was handed over to Silicon Graphics. In 1998, more than 350 million microprocessors with different instruction set architectures were in use, and by 2006, this number had risen to more than a billion.

Course Focus: Quantitative Principles of Computer Design

The primary aim of this course is an in-depth study of computer architecture concepts relevant for professional computer scientists, engineers, and architects. Emphasis is given to exposing advances in the field through cost-performance-power trade-offs and good engineering design. The course covers: quantitative principles of computer design, instruction set architecture, datapath and control (implementation and performance), advanced pipelining concepts, memory hierarchy design (main memory, cache, hard drives), multiprocessor architecture, storage and input/output systems, and computer clusters.

The textbook is Hennessy J. L. and Patterson D. A., Computer Architecture: A Quantitative Approach, 3rd Edition, Morgan Kaufmann publishers, 2003. The course includes a "research in the small" project where students pick a topic, work full time for 3 weeks, meet with faculty/TA, give an online presentation, and submit a written report like a conference paper.

Four Perspectives of Computer Architecture

Computer Architecture can be considered from four perspectives:

• Processor Design: Instruction set architecture (addressing modes and protections), datapath designs (multiple cycles and pipelines, ILP, hazards), and L1 caches (design, blocks, and associativity).
• Memory Hierarchy: L2 caches (coherence, bandwidth, and latency), main memory (DRAM, interfacing, and protocols), and virtual memory (interfacing and protocols).
• I/O and Storage: Disks and tapes, and Redundant Array of Inexpensive Disks (RAID).
• Multiprocessor and Networks: Shared memory, interconnecting networks, network switches, and routing, bandwidth, and latency.

Computer Design Cycle

The computer design and developments have been under the influence of technology, performance, and cost. The new trends in technology are used to reduce the cost and enhance the performance. The computer design is evaluated for bottlenecks using certain benchmarks to achieve optimum performance. Time is the key measurement of performance: a desktop user defines performance in terms of response time or execution time (time between start and completion of an event), while a data processing center manager defines it in terms of throughput (number of jobs completed in a specified time). Benchmarks are programs that try to average the frequency of operation and operands of a large set of programs. Standardized benchmark tools are available from the Standard Performance Evaluation Corporation (SPEC).

Design evaluation involves hardware cost/delay/area/power estimation, simulation at different levels of abstraction (ISA, RT, Gate, Circuit), queuing theory (to calculate response time and throughput of entire I/O systems), rules of thumb, and fundamental laws/principles. New designs are simulated to evaluate performance for different levels of workloads, and simulation helps keep result verification cost minimum. The cost-performance is optimized for workloads.

1: Technology Trends: Computer Generations

The generations are identified by dominant implementation technologies:

• 1st Generation (Vacuum tube): 1946-1957
• 2nd Generation (Transistor): 1958-1964
• 3rd Generation (SSI/MSI): 1965-1971 (up to 3,000 devices/chip)
• Large Scale Integration (LSI): 1972-1977 (3,000 - 100,000 devices/chip)
• 4th Generation (VLSI): 1978 onwards (100,000 - 100,000,000 devices/chip)
• Ultra Large Scale Integration (ULSI): Over 100,000,000 devices/chip

The first generation (1950-59) used vacuum tube technology. The second generation (1960-68) used transistors. The third generation (1969-77) was the age of minicomputers using integrated circuits. The fourth generation (1978 to date) is the result of VLSI and ULSI technology. The gateway to the fifth generation is not clear as no revolutionary technology has been proclaimed. Present transistor technology integrates up to 15 million transistors on one VLSI chip for PowerPC and Pentium processors.

In 1980, supercomputer performance was 50 times that of microprocessors, 20 times that of minicomputers, and 10 times that of mainframe computers. By 1992, microprocessor performance was equivalent to that of supercomputers, and it was much higher from 1995 onwards.

3: Cost

Systems are implemented using the latest technology to obtain cost-effective high-performance solutions, with due consideration given to implementation complexities.

Price Versus Cost

The relationship between cost and price is complex. Cost is the total amount spent to produce a product, while price is the amount for which a finished good is sold. Cost passes through different stages before it becomes price, and a small change in cost may have a big impact on price.

Component Costs

• Direct Costs (add 25% to 40%): Recurring costs such as labor, purchasing, scrap, and warranty.
• Gross Margin (add 82% to 186%): Nonrecurring costs such as R&D, marketing, sales, equipment maintenance, rental, financing cost, pretax profits, and taxes.
• Average Discount to get List Price (add 33% to 66%): Volume discounts and/or retailer markup.

Summary

1. A computer system's development is viewed with reference to computer architecture and computer system organization. Architecture refers to attributes visible to a programmer (instruction set, addressing, I/O mechanisms). Organization refers to how features are implemented (FSM or microprogramming, memory technology). Architecture of processor family members is the same, while organization may differ.

2. Computer development has been discussed with academic and commercial perspectives. Academically, it started in 1944-49 with von Neumann's EDVAC and Wilkes' EDSAC. Commercially, the first machines were BINAC and UNIVAC-I ($1 million in 1951), and the Cray-I (1976) was the world‘s fastest supercomputer.

3. Decisive factors for rapid changes in computer development are performance enhancements, price reduction, and functional improvements.

4. Technological developments from vacuum tubes to VLSI circuits gave birth to four computer generations. At present, no revolutionary technology has been proclaimed for a fifth generation.

5. Computer Architecture is viewed from four perspectives: Processor Design, Memory Hierarchy, Input/Output and Storage, and Multiprocessor and Network Interconnection.

6. The course focuses on in-depth study of computer architecture concepts, exposing advances through cost-performance-power trade-offs and good engineering design.

7. The computer design cycle is influenced by technology, performance, and cost; new trends in technology enhance performance and reduce cost.

⭐ Key Takeaways

The most critical distinction to remember is that architecture refers to the programmer-visible attributes (instruction set, addressing, I/O mechanisms) which are shared across a processor family for code compatibility, while organization refers to how those features are physically implemented (control signal generation, memory technology), which can differ between versions. The historical timeline is crucial, from von Neumann's stored-program concept (EDVAC) and the first operational machines (ENIAC, EDSAC) through the commercial era (UNIVAC-I), the first supercomputer (CDC 6600), and the microprocessor revolution (Intel 4004, 80x86). Computer performance is measured by response time (for desktop users) or throughput (for data centers), and standardized benchmarks like those from SPEC are used for evaluation. The computer design cycle is driven by technology, performance, and cost, with technology generations progressing from vacuum tubes to VLSI. Finally, the four perspectives of computer architecture (processor design, memory hierarchy, I/O and storage, multiprocessors and networks) provide the framework for analyzing and designing computer systems.

🧠 Quick Revision Questions

1. What is the fundamental difference between computer architecture and computer organization? Provide an example of each.
2. Name the first operational stored-program computer and the institution where it was built.
3. What are the three primary influences on the computer design cycle?
4. What are the four perspectives from which computer architecture can be considered?
5. How does the definition of "performance" differ between a desktop user and a data processing center manager?

📘 Lecture 2 — Quantitative Principles

📖 Overview: This lecture continues the discussion on the growth in processor performance and introduces the key concepts of quantitative design and analysis in computer architecture. It covers the critical relationship between cost and performance, the metrics for measuring CPU performance, and the use of benchmark suites for comparing computer systems. Understanding these principles is essential for making informed design and purchasing decisions in computing.

🗂️ Topics Covered

The lecture begins with a review of architecture vs. organization and the historical computer development timeline from von Neumann to modern microprocessors. It then delves into the price-performance design, explaining the complex relationship between manufacturing costs and list price, including the cost of integrated circuits and die yield calculations. The discussion moves to performance metrics, defining execution time, throughput, and CPU time with the fundamental CPI equation. Finally, the lecture covers CPU performance measurement using MIPS, MFLOPS, and detailed benchmark suites including the SPEC benchmarks, concluding with design trends and the importance of execution time as the real measure of performance.

📝 Lecture Summary

1: Architecture vs. Organization

Architecture refers to those attributes of a computer visible to a programmer or compiler writer, e.g., instruction set, addressing techniques, I/O mechanisms. Organization refers to how the features of a computer are implemented, i.e., control signals are generated using the principles of finite state machine (FSM) or microprogramming.

2: Historical Computer Development

Computer development was discussed with academic and commercial perspectives. Academically, modern computer developments have their infancy in 1944-49, when John von Neumann introduced the concept of stored-program computer, referred to as EDVAC, and Maurice Wilkes of Cambridge University built the world‘s first full-scale, operational stored program computer, EDSAC. Commercially, the first machine BINAC was built by Eckert-Mauchly Computer Corporation in 1949, and UNIVAC-I by Remington-Rand in 1951, sold for $1 million. In 1976, Cray Research Inc. announced the world‘s fastest, most expensive supercomputer Cray-I. Technological developments from vacuum tubes to VLSI circuits gave birth to four generations of computers. In 1971, Intel introduced the first cheap microprocessor 4004 and then the 80 x 86 series, which was used by IBM in personal computers. By 2006, more than a billion microprocessors were in use.

3: Perspectives of Computer Architecture

Computer Architecture was viewed from four perspectives: Processor Design, Memory Hierarchy, Input/output and storages, and Multiprocessor and Network interconnection.

4: Computer Design Cycle and Growth in Processor Performance

The computer design and development has been under the influence of technology, performance, and cost. The growth in processor performance since mid-1980s has been substantially high. Prior to the mid-1980s, microprocessor performance growth averaged about 35% per year. By 2001, the growth raised to about 1.58 per year. Supercomputers and mainframes of the 1960s were replaced with minicomputers in the 1970s, and then by low-cost microprocessor-based PCs and workstations in the 1980s.

Price-Performance Design

Technology improvements are used to lower the cost and increase performance. The cost is the total amount spent to produce a product, while the price is the amount for which a finished good is sold. A small change in cost may have a big impact on price.

Manufacturing Costs include:

• Component Cost: 40% to 50% of list price
• Recurring costs: Labor, purchasing scrap, warranty – 4% to 16% of list price
• Gross margin – Non-recurring cost: R&D, marketing, sales, equipment, rental, maintenance, financing cost, pre-tax profits, taxes

List Price includes an Average Discount of 15% to 35% for volume discounts and/or retailer markup.

Cost-effective IC Design depends on:

• Yield: Percentage of manufactured components surviving testing
• Volume: Increases manufacturing, decreases list price, improves purchasing efficiency
• Feature Size: The minimum size of a transistor or wire in either x or y direction

Reduction in feature size from 10 microns in 1971 to 0.18 in 2001 resulted in a quadratic rise in transistor count, linear increase in performance, and the evolution from 4-bit to 64-bit microprocessors.

Cost of Integrated Circuits

The Integrated circuit manufacturing passes through stages: Wafer growth and testing, Wafer chopping into dies, Packaging the dies to chips, and Testing a chip.

A die is the square area of the wafer containing the integrated circuit.

The cost of an integrated circuit is determined as: Cost of IC = (die cost + die testing cost + packaging cost + final testing cost) / final test yield

The cost of a die is: Cost of die = Cost of wafer / (dies per wafer x die yield)

The number of dies per wafer is: Dies per wafer = [ π (wafer diameter/2)² / die area ] – [ π (wafer diameter) / √(2 x die area) ]

📐 Formula: Dies per wafer = [Wafer area / Die Area] - Wafer Waist area

📌 Example Calculating Number of Dies: For a die of 0.7 cm on a side, find the number of dies per wafer of 30 cm diameter. Answer: [π (30/2)² / 0.49] - [π (30) / √(2 x 0.49)] = 1347 dies

Die yield is the fraction or percentage of good dies on a wafer. Wafer yield accounts for completely bad wafers. A good estimate for CMOS is α = 4.0.

📐 Formula: Die yield = Wafer yield x (1 + (defects per unit area x die area) / α)^(-α)

📌 Example: Calculating Die Yield The yield of a die, 0.7 cm on a side, with defect density of 0.6/cm². Answer: (1 + [0.6 x 0.47] / 4.0)^(-4) = 0.75

Performance Metrics: Time and Throughput

CPU performance is measured by Execution time (response time, latency) or Throughput (bandwidth) - tasks per day, hour, week, sec, ns.

📌 Example: Cost-Performance Comparison (Train vs. Plane) To carry 2400 passengers from Lahore to Islamabad:

• Train: completes the task in 4:00 hours, carries 2400 passengers/trip (6.0 sec/person), cost 300 Rs/person. Cost-performance = 1,800 Rs-sec/person.
• Plane: completes the task in 6.00 hours, carries 300 passengers/trip (9.0 sec/person), cost 3000 Rs/person. Cost-performance = 27,000 Rs-sec/person.

The plane is 10 times faster but takes 50% more time to complete the job, so the throughput and performance of the train is 50% more than the airplane. The cost-performance per person by train vs. airplane is 1:15.

Metrics of Performance: CPU Time

Execution time or latency includes everything - processing, disk access, memory access, I/O, OS overheads. This is the wall-clock time, elapsed time, or response time.

CPU time is different from response time in multiprogramming. It is divided into user CPU time (time spent in the program) and system CPU time (time spent in the operating system).

Aspects of CPU Performance

📐 Formula: CPU time = Seconds / Program = (Instructions / Program) x (Cycles / Instruction) x (Seconds / Cycle)

All computers run at a constant rate determined by discrete time events called ticks, clock ticks, clock periods, clocks, cycles, or clock cycles.

The CPI (Cycles Per Instruction) is: CPI = CPU clock cycles for program / Instruction count

CPU Time = CPU clock cycles for program / clock rate CPU time = instruction count x clock cycle time x cycles per instruction sec. / program = (instructions/program) x (clock cycles/instructions) x (seconds/clock cycles)

Cycles Per Instruction (CPI)

CPI = CPU Clock Cycles for program / Instruction Count = (CPU Time * Clock Rate) / Instruction Count

Instruction Frequency for a given instruction mix: FICi = IC of i-th instruction / Total Instruction count

Average Cycles Per Instruction: CPI = (1/Instruction count) Σi=1 to n ICi x CPIi = Σi=1 to n FICi x CPIi

📌 Example: Calculating average CPI Base Machine (Reg/Reg):

• ALU: Freq 50%, Cycles 1, CPI(i) 0.5 (33% of time)
• Load: Freq 20%, Cycles 2, CPI(i) 0.4 (27% of time)
• Store: Freq 10%, Cycles 2, CPI(i) 0.2 (13% of time)
• Branch: Freq 20%, Cycles 2, CPI(i) 0.4 (27% of time)
• Average CPI = 1.5

Total Execution Time for n Programs

• Arithmetic mean time: (1/n) Σi=1 to n Timei (each program runs once)
• Weighted arithmetic mean time: Σi=1 to n wi x Timei (with weighting factor wi for unequal mix)
• Geometric mean time: ⁿ√(πi=1 to n Execution time ratioi) (normalized to a reference machine)

Instruction Execution Rate – MIPS and MFLOPS

MIPS (Millions of Instructions Per Second): MIPS = (instruction count) / (execution time x 10⁶)

Relative MIPS (RMIPS) for a machine ‘M’ based on a reference machine: RMIPS = [Performance M / Performance reference] x MIPS reference = [Time reference / Time M] x MIPS reference

MFLOPS is defined for floating-point-intensive programs as millions of floating-point operations per second.

CPU Benchmark Suites

Benchmarks are programs specifically chosen to measure performance. Five levels in decreasing order of accuracy:

1. Real Applications: Scientific programs like MatLab, C compiler, Photoshop - most suitable as users can select input and options.
2. Modified Applications: Real applications used as building blocks with certain blocks modified to focus on desired aspects.
3. Kernels: Small key pieces extracted from real programs, run to evaluate performance by isolating individual features.
4. Toy benchmarks: Small codes (10-100 lines) producing known results.
5. Synthetic benchmarks: Small sections of program created artificially to match average frequency of operations.

SPEC: System Performance Evaluation Cooperative

Founded in late 1980s to improve benchmarking.

• First Round (1989): SPEC89 - 10 programs yielding a single number – SPECmarks.
• Second Round (1992): SPEC92 - SPECInt92 (6 integer programs) and SPECfp92 (14 floating point programs).
• Third Round (1995): SPEC95 - new set of programs: SPECint95 (8 integer) and SPECfp95 (10 floating point). Single flag setting for all programs: SPECint_base95, SPECfp_base95.

Desktop benchmarks are divided into CPU-intensive (SPEC89, SPEC92, SPEC95, SPEC2000) and Graphic-intensive (SPECviewperf, SPECapc).

Server benchmarks include SPEC CPU2000 (throughput benchmarks for multiprocessors), SPECsfs (fileserver benchmark for I/O systems), and SPECweb (simulates multiple clients requesting static and dynamic pages).

Designing and Performance Comparison Summary

Design Trends:

• Logic: Capacity 2x in 3 years, Speed 2x in 3 years
• DRAM: Capacity 4x in 3 years, Speed 2x in 10 years
• Disk: Capacity 4x in 3 years, Speed 2x in 10 years

"X is n times faster than Y" means: ExTime(Y) / ExTime(X) = Performance(X) / Performance(Y)

CPI Law: CPU Time = (Instructions / Program) x (Cycles / Instruction) x (Seconds / Cycle)

Execution time is the REAL measure of computer performance!

Die Cost goes roughly with die area⁴.

⭐ Key Takeaways

Execution time is the definitive measure of computer performance, and the CPI Law (CPU time = Instructions x CPI x Cycle time) is the fundamental equation for analyzing CPU performance. The cost-performance design involves a complex balance between manufacturing cost and price, where small changes in cost can have a big impact on price; die cost scales roughly with die area to the fourth power. Benchmark suites like SPEC are essential for comparing performance without running actual programs, using five levels from real applications to synthetic benchmarks. Finally, understanding the difference between execution time (latency) and throughput is crucial, as different users (desktop vs. server) prioritize different metrics.

🧠 Quick Revision Questions

1. Explain the key difference between architecture and organization in computer design.
2. Write down the full CPI Law equation and define each of its three components.
3. What is the difference between cost and price in the context of computer manufacturing, and what are the main components of manufacturing cost?
4. Calculate the number of dies per wafer for a 30 cm diameter wafer if the die area is 0.49 cm², using the provided formula.
5. List the five levels of benchmarks in decreasing order of accuracy and briefly describe the SPEC organization's role in benchmarking.

📘 Lecture 3 — Quantitative Principles Design for Performance

📖 Overview: This lecture examines quantitative principles for evaluating and improving computer system performance, with a focus on I/O systems. It introduces queuing theory fundamentals via Little’s Law and presents Amdahl’s Law as a critical tool for calculating the maximum achievable speedup when enhancing only a portion of a system.

🗂️ Topics Covered

The lecture begins with a recap and introduces I/O performance concepts, including the producer-server model for computer I/O systems. It covers I/O performance parameters like diversity, capacity, latency, and bandwidth, then explains I/O transaction time divided into entry time, system response time, and think time. The relationship between throughput versus response time is examined, followed by the derivation and application of Little’s Law from queuing theory. The lecture concludes with Amdahl’s Law, including its formula and an example showing the speedup when floating-point instructions are improved.

📝 Lecture Summary

Computer I/O System

The I/O system is modeled using a Producer-Server model, where the producer is the device generating tasks to be serviced, a queue is the area where tasks accumulate waiting for service, and the server is the device performing the requested service. The Response Time is defined as the time a task takes from the moment it is placed in the buffer to the time the server finishes the task.

💡 Why this matters: Understanding this model helps analyze bottlenecks in computer systems where I/O devices interact with the CPU.

I/O Performance Parameters

There are four key I/O performance parameters. Diversity refers to which I/O devices can connect to the CPU. Capacity refers to how many I/O devices can connect to the CPU. Latency is the overall response time to complete a task. Bandwidth is the number of tasks completed in a specified time, also known as throughput.

I/O Transaction Time

The transaction time of a computer is the sum of three distinct times. Entry Time is the time for the user to enter a command — this averages 0.25 seconds, but from a keyboard it takes 4.0 seconds. System Response Time is the time between when the user enters the command and when the system responds. Think Time is the time from reception of the command until the user enters the next command.

Little’s Law – A Little queuing theory

If the system is in steady state, then the number of tasks entering the system must equal the number of tasks leaving the system. Little’s Law states that the mean number of tasks in the system equals the mean response time multiplied by the arrival rate.

The mathematical derivation uses three components:

• Mean number of tasks in system = (Time accumulated) / (Time observe)
• Mean response time = (Time accumulated) / (Number tasks)
• Arrival rate λ = (Number tasks) / (Time observe)

🔑 Definition — Little’s Law: Mean number of tasks in system = Mean response time × Arrival rate

📐 Formula: Mean number of tasks = Mean response time × λ → The average number of tasks waiting or being processed equals how long they wait times how fast new tasks arrive

📌 Example: If the average response time is 2 seconds and the arrival rate is 5 tasks per second, then the mean number of tasks in the system = 2 × 5 = 10 tasks.

Amdahl’s Law

Amdahl’s Law provides the speedup due to an enhancement. Suppose that enhancement E accelerates a fraction F of the task by a factor S, while the remainder of the task is unaffected. The overall speedup is calculated using the execution time with and without the enhancement.

🔑 Definition — Amdahl’s Law: The performance improvement to be gained from using a faster mode of execution is limited by the fraction of the time the faster mode can be used.

📐 Formula:

• Speedup (E) = Execution Time without E / Execution Time with E = Performance with E / Performance without E
• Execution Time_new = Execution Time_old × [(1 – Fraction_enhanced) + Fraction_enhanced / Speedup_enhanced]
• Speedup_overall = ExecutionTime_old / ExecutionTime_new = 1 / [(1 – Fraction_enhanced) + Fraction_enhanced / Speedup_enhanced]

📌 Example: Floating point instructions are improved to run 2 times faster, but only 10% of actual instructions are FP.

• ExecutionTime_new = ExecutionTime_old × (0.9 + 0.1/2) = 0.95 × ExecutionTime_old
• Speedup_overall = 1 / 0.95 = 1.053

This shows that even if we double the speed of the 10% of instructions that are FP, the overall speedup is only 5.3%.

⭐ Key Takeaways

The I/O system must be analyzed using the producer-server model with queue, server, and response time concepts. The four critical I/O performance parameters are diversity, capacity, latency, and bandwidth — each addressing a different aspect of I/O capability. Little’s Law provides a fundamental relationship in queuing theory: the mean number of tasks in a system equals the mean response time multiplied by the arrival rate, enabling performance prediction in steady-state systems. Amdahl’s Law is the most critical formula for understanding the limitations of performance enhancement — it shows that the overall speedup is severely limited by the fraction of the task that can be improved, regardless of how much that fraction is accelerated. The floating-point example demonstrates that improving only 10% of instructions by a factor of 2 yields a meager 5.3% overall speedup.

🧠 Quick Revision Questions

1. What are the three components of I/O transaction time, and what are the typical values for entry time?
2. State Little’s Law in words and write its mathematical formula.
3. If the mean response time is 3 seconds and the arrival rate is 4 tasks per second, what is the mean number of tasks in the system?
4. Write Amdahl’s Law formula for overall speedup in terms of Fraction_enhanced and Speedup_enhanced.
5. If 20% of a program can be sped up by a factor of 4, what is the overall speedup?

📘 Lecture 4 — Instruction Set Principles

📖 Overview: This lecture provides a comprehensive introduction to the Instruction Set Architecture (ISA) — the critical interface between hardware and software. It categorizes different ISA types (Stack, Accumulator, GPR), explains memory addressing modes and operand types, and details the various categories of operations a processor must support. Understanding ISA is essential because it forms the foundation upon which both hardware implementation and software compilation are built.

🗂️ Topics Covered

The lecture recaps key performance and design principles from Chapters 1-3, then defines the three pillars of computer architecture and the evolving focus of the field. It introduces the ISA taxonomy with Stack, Accumulator, and General Purpose Register architectures, compares their advantages and disadvantages, and details the types and sizes of operands. Finally, it covers categories of instruction set operations and a comprehensive range of memory addressing modes, including immediate, register, direct, indirect, special, and control flow modes.

📝 Lecture Summary

Recap: Lec. 1-3 Chapter 1

The decisive factors for rapid changes in computer development have been performance enhancements, price reduction, and functional improvements. Processor performance is compared by the factor n, which determines how much lower the execution time one machine takes compared to another. Price-Performance Design understands the complex relationship between cost (the total amount to produce a product) and price (the amount for which a finished good is sold), which is controlled by die yield and volume. Supercomputers and mainframes have been replaced with low-cost microprocessor-based desktop machines. A benchmark is a program developed to evaluate performance; good products require proficient benchmarks and expert ways to summarize performance. An I/O system works on the producer-server model, which comprises a queue where tasks accumulate and a server that performs the requested service. The response time is the time from when a task arrives in the buffer to when the server finishes it.

Changing Definitions of Computer Architecture

The three pillars of computer architecture are: hardware, instruction set, and software. Hardware facilitates running the software, and the instruction set is the interface between them. The focus of Computer Architecture courses has changed over time: from 1950s to 1960s it was Computer Arithmetic; from 1970s to mid 1980s it was Instruction Set Design (the portion visible to the programmer and compiler writer); and from 1990s to date it is the design of CPU, memory system, I/O system, and Multiprocessors based on quantitative principles for price-performance.

Instruction Set Architecture – ISA

Instruction Set Architecture (ISA) is the interface between hardware and software. It plays a vital role in understanding computer architecture because the design of hardware and software cannot be initiated without defining it. The ISA describes the instruction word format and identifies the memory addressing for data manipulation and control operations.

💡 Why this matters: A good interface lasts through many implementations (portability, compatibility), is used in many different ways (generality), provides convenient functionality to higher levels, and permits an efficient implementation at lower levels.

Taxonomy of Instruction Set

Major advances are typically associated with landmark instruction set designs: stack, accumulator, and general purpose register. Design decisions must take into account technology, machine organization, programming languages, compiler technology, and operating systems. The basic differentiator is the type of internal storage of the operand. The major choices of ISA are:

• Stack Architecture
• Accumulator Architecture
• General Purpose Register Architecture: Register-memory, Register-Register (load/store), and Memory-Memory (obsolete)

Stack Architecture

In a Stack Architecture, both operands are implicitly on the Top of Stack (TOS). It is also called a Zero-Address machine because instructions have no explicit address field. All operands are implicit (implied or inherited); the first operand is removed from the stack, and the second operand is replaced by the result.

🔑 Definition — Stack Architecture: An ISA where operands are implicitly on the top of the stack, requiring no explicit operand addresses in the instruction.

📌 Example: To execute C = A + B:

PUSH A
PUSH B
ADD      ; implicitly uses the two top-of-stack values
POP C

Accumulator Architecture

An accumulator is a special register within the CPU that serves as both the implicit source of one operand and the result destination for arithmetic and logic operations. It accumulates data and does not serve as an address register. Accumulator-based machines are called 1-address machines because the second operand is in memory.

🔑 Definition — Accumulator: A special CPU register used as both an implicit source operand and the result destination for arithmetic/logic operations.

📌 Example: To execute C = A + B:

Load A      ; accumulator ← Mem[A]
ADD B       ; accumulator ← accumulator + Mem[B]
Store C     ; Mem[C] ← accumulator

General Purpose Register Architecture

General Purpose Register (GPR) Architecture has many CPU registers that do not have dedicated functions and can be used for variety of purposes (address, data, control). It has explicit operands either in register or memory. The three types are:

• Register-Memory: One explicit operand is in a register, one in memory, and the result goes into the register.
• Register-Register (Load/Store): Explicit operands are first loaded into registers temporarily and transferred to memory by Store instruction. Both explicit operands are not accessed from memory directly.
• Memory-Memory: This architecture is obsolete.

📌 Example (Register-Memory): C = A + B

Load R1, A
ADD R3, R1, B    ; result goes into register R3
Store R3, C

📌 Example (Register-Register): C = A + B

Load R1, A
Load R2, B
ADD R3, R1, R2
Store R3, C

Comparison of three GPR Architectures

Register-Register advantages: simple, fixed-length instruction decoding; simple code generation; similar number of clock cycles per instruction. Disadvantages: higher instruction count than memory reference; lower instruction density leads to larger programs.

Register-Memory advantages: data can be accessed without separate Load first; instruction format is easy to encode. Disadvantages: operands are not equivalent since a source operand (in a register) is destroyed in operation; encoding a register number and memory address in each instruction may restrict the number of registers; CPI varies by operand location.

Memory-Memory advantages: most compact; doesn't waste registers for temporary storage. Disadvantages: large variation in instruction size; large variation in work per instruction; memory bottleneck by memory access.

Types and Size of Operands

Types of an operand include Integer, Single-precision floating point, and Character. Sizes include: Character (8-bit), Half word (16-bit), Single precision FP or Word (32-bit), Double precision FP or (64-bit), and double word.

Categories of Instruction Set Operations

All computers provide a full set of operational instructions for:

• Arithmetic and Logic: Integer add, sub, and, or, multiply, divide
• Data Transfer: Load, store, and move instructions with memory addressing
• Control: Branch, Jump, procedure call and return

Support instructions may include: System (OS call, Virtual Memory Management), Floating point (add, multiply, divide, compare), Decimal (BCD add, multiply, Decimal to Character Conversion), String (move, compare, search), and Graphics (Pixel and vertex operations, compression/decompression).

Operand Addressing Modes

An effective address is the binary bit pattern issued by the CPU to specify the location of operands in CPU (register) or memory. Addressing modes are the ways of providing access paths to CPU registers and memory locations. Commonly used addressing modes are:

🔑 Immediate: Data for the instruction is part of the instruction itself. 📐 Example: ADD R4, #24H → Reg[R4] ← Reg[R4] + 24H Used to hold source operands only; cannot be used for storing results.

🔑 Register: Operand is contained in a CPU register. No memory access needed, therefore fast. 📐 Example: ADD R4, R3 → Reg[R4] ← Reg[R4] + Reg[R3]

🔑 Direct (or Absolute): The address of the operand is specified as a constant, coded as part of the instruction. Limited address space (2^operand field size) locations. 📐 Example: ADD R1, (1000) → Reg[R1] ← Reg[R1] + Mem[1000]

🔑 Indirect: The address of the memory location where the data is to be found is stored in the instruction as the operand (operand is the address of an address). Large address space (2^memory word size) available. Two or more memory accesses are required.

Types of Indirect addressing modes:

• Register Indirect: ADD R4, (R1) → Reg[R4] ← Reg[R4] + Mem[Reg[R1]]
• Register Indirect Indexed: ADD R4, (R1+R2) → Reg[R4] ← Reg[R4] + Mem[Reg[R1]+Reg[R2]]
• Register Indirect plus displacement: ADD R4, 100(R1) → Reg[R4] ← Reg[R4] + Mem[100+Reg[R1]]
• Memory Indirect: ADD R4, @(R1) → Reg[R4] ← Reg[R4] + Mem[Mem[Reg[R1]]]

Special Addressing Modes

Used for stepping within loops; R2 points to the start of the array; each reference increments/decrements R2 by 'd' (the size of the elements in the array).

• Auto-increment: ADD R1, (R2)+ → (i) Reg[R1] ← Reg[R1] + Mem[Reg[R2]] (ii) Reg[R2] ← Reg[R2] + d
• Auto-decrement: ADD R1, (R2)- → (i) Reg[R2] ← Reg[R2] - d (ii) Reg[R1] ← Reg[R1] + Mem[Reg[R2]]
• Scaled: ADD R1, 100(R2)[R3] → Reg[R1] ← Reg[R1] + Mem[100 + Reg[R2] + R3 * d]

Addressing Modes of Control Flow Instructions

• Branch (conditional): A sort of displacement, in number of instructions, relative to the Program Counter (PC).
• Jump (Unconditional): Jump to an absolute address, independent of the position of PC.
• Procedure call/return: Control transfer with some state and return address saving, sometimes in a special link register or in some GPRs.

⭐ Key Takeaways

A student must understand that the ISA is the fundamental interface between hardware and software, and its design decisions (stack, accumulator, or GPR) critically impact performance, code size, and hardware complexity. The three main ISA types differ in where operands are stored: stack (implicit on TOS), accumulator (one implicit operand), and GPR (explicit operands in registers/memory). For GPR architectures, the Register-Register (load/store) model offers simplicity and fixed instruction length at the cost of higher instruction count, while Register-Memory trades this for fewer loads but operand asymmetry. The various addressing modes (immediate, register, direct, indirect, and special modes like auto-increment) determine how the effective address of an operand is calculated, with each mode offering trade-offs between address space, speed, and flexibility.

🧠 Quick Revision Questions

1. What are the three major types of ISA based on internal operand storage, and what is the "address" characteristic of each (e.g., zero-address, one-address)?
2. Explain the difference between Register-Register and Register-Memory architectures in terms of how operands are accessed and the resulting pros and cons.
3. What is the difference between Direct and Indirect addressing modes in terms of where the operand's address is found and the address space each can access?
4. How does the Auto-increment addressing mode work, and why is it useful for looping through arrays?
5. List the three main categories of instruction set operations and give one example instruction for each category.

📘 Lecture 5 — Instruction Set Principles (Encoding instructions and MIPS Instruction format)

📖 Overview: This lecture explores the principles of instruction set encoding, including different instruction word lengths and formats. It details the essential elements of computer instructions, compares variable, fixed, and hybrid length formats, and introduces the MIPS instruction set architecture with its specific formats (R-type, I-type, J-type) and operations.

🗂️ Topics Covered

The lecture begins with a recap of instruction set taxonomy from Lecture 4, then covers instruction set encoding, including essential elements like op-code, operand locations, and next instruction address. It classifies instruction word types as variable, fixed, or hybrid length, and explores the hybrid length taxonomy (4-address through 0-address). A detailed comparison of these formats is provided using code size and memory access parameters. Finally, the MIPS ISA is introduced, covering its characteristics and the R-type, I-type, and J-type instruction word formats with examples.

📝 Lecture Summary

Recap: Lecture 4

The lecture begins with a quick review. The three pillars of Computer Architecture are Hardware, Software, and Instruction Set. The Instruction Set acts as an interface between hardware and software. The taxonomy includes Stack, Accumulator, and General Purpose Register architectures. Operand types include Integer, FP, and Character, with sizes like Half word, word, and double word. Operations are classified as arithmetic, data transfer, control, and support. Addressing modes include immediate, register, direct (absolute), and indirect, with special modes like auto-increment, auto-decrement, and scaled. Control instruction addressing covers branch, jump, and procedure call/return.

Instruction set Encoding

The essential elements of computer instructions are four-fold. First, the type of operation is encoded in the operation code, or op-code, field (e.g., add, mov). Second, the place to find the source operand(s) can be CPU registers, memory cells, I/O locations, or part of the instruction itself. Third, the place to store the result is similarly in CPU registers, memory cells, or I/O locations. Fourth, the place to find the next instruction is either the address of the next instruction in sequence (default) or the address of the instruction at the branch target location.

Instruction Word Types are categorized into three main formats. Variable Length format specifies the operation in one field (op-code) and can support any number of operands. It generally generates the smallest code representation as unused fields need not be included. Typical examples are VAX and Intel 80x86.

The Fixed Length Format always has the same number of operands, and addressing modes are specified in the op-code. It generally generates the largest code size. Typical examples are Alpha, MIPS, PowerPC, and SPARC.

The Third Alternative: Hybrid Length specifies multiple formats by the op-code, with one or two fields for addressing mode. It generally generates the optimum code size. Typical examples include IBM 360/370, MIPS16, and TI-TMS320c54x.

Hybrid Length Taxonomy

This taxonomy is based on the number of address fields. 4-address instructions specify the two source operands, the destination operand, and the address of the next instruction. 3-address instructions specify addresses for both operands as well as the result. 2-address instructions overwrite one operand with the result, so one field serves two purposes. 1-address instructions use a dedicated CPU register, the accumulator, to hold one operand and the result, while the address of the other operand is specified. 0-address instructions use a stack to hold both operands and the result; operations are performed between the value on the top of the stack (TOS) and the second value on the stack (SOS), with the result stored on the TOS.

🔑 Definition — TOS: Top of Stack 🔑 Definition — SOS: Second value on the stack

📌 Example: Evaluate the expression: F = (B + C)*D – E, using 0-address through 3-address format.

📌 Example: Using different instruction formats, write pseudo-code to evaluate the following expression: Z = 4(A+B) – 16(C+58). Your code should not change the source operands.

Comparison of instruction formats

A comparison is made assuming: a single byte for the op code, a 16 Mbyte memory address space, a single addressable memory unit of a byte, operands of 24 bits, and an 8-bit data bus. The parameters compared are code size and number of memory accesses.

The 4-address instruction has a code size of 1(op) + 3(src1) + 3(src2) + 3(dest) + 3(next) = 13 bytes. The number of bytes accessed from memory is 13 (fetch) + 6 (source operands) + 3 (store destination) = 22 bytes.

The 3-address instruction has a code size of 1 + 3 + 3 + 3 = 10 bytes. The number of bytes accessed from memory is 10 + 6 + 3 = 19 bytes.

The 2-address instruction has a code size of 1 + 3 + 3 = 7 bytes. The number of bytes accessed from memory is 7 + 6 + 3 = 16 bytes.

The 1-address instruction has a code size of 1 + 3 = 4 bytes. The number of bytes accessed from memory is 4 + 3 (source operand fetch) + 0 (destination operand) = 7 bytes.

The 0-address instruction has a code size of 1 byte. The number of bytes accessed from memory is 1 + 6 (source operands) + 3 (store destination) = 10 bytes.

Result Summary:

RISC and MIPS ISA

RISC and MIPS is a fixed length, 64-bit LOAD/STORE Architecture. It contains 32 GPR (General Purpose Registers), each of 32-bit. It supports 3-address, reg-reg arithmetic instructions; displacement instructions with address offset 12-16 bits; immediate data 8-bit and 16-bit; register indirect addressing; data size 8-, 16-, 32-, and 64-bit integer; and 64-bit IEEE 754 floating point. Instructions include data transfer (load, store, register-register move), simple arithmetic (add, subtract, shift), compare (equal, not-equal, less), and branch (PC-relative, jump, call/return). It is designed for pipelining efficiency.

💡 Why this matters: The trade-offs between code size and memory accesses in instruction formats directly impact program size and execution speed, and understanding the fixed-length format of MIPS is crucial for appreciating its pipelining advantages.

MIPS Instruction Word format

Recap: MIPS types and size of operands: Operand types are Integer, Single-precision floating point, and Character. Sizes are Character (8-bit), Half word (16-bit), Single precision FP or Word (32-bit), Double precision FP or double word (64-bit).

Register-Register (R-Type) format has an op-code of 000000. Rs and Rt are source operand registers, Rd is the result carrying register, Sht is the number of bit-shift, and Func is the ALU function to encode the data path operation. Execution: Rd <- Rs func Rt.

🔑 Definition — R-Type: A MIPS instruction format where all operands are in registers. 📐 Format: Op-code (6), Rs (5), Rt (5), Rd (5), Sht (5), Func (6) -> total 32 bits.

📌 Example Encoding MIPS64 Arithmetic Instruction: DADD R1, R2, R3 (Add word signed) means Reg[R1] ← Reg[R2] + Reg[R3]. 📌 Example Shift Instruction: DSLL R1, R2, # 30 (Shift Left Logical) means Reg[R1] ← Reg[R2] << 30.

Register-Immediate (I-Type) format uses Rt as the destination field for immediate data instructions (Rt <- Rs op immediate). This same format is used for Load/Store instructions: for Load (Rt <- Mem[immediate + [Rs]]), for Store (Mem[immediate + [Rs]] <- Rt).

🔑 Definition — I-Type: A MIPS instruction format used for operations with an immediate operand or for load/store instructions. 📐 Format: Op-code (6), Rs (5), Rt (5), Immediate (16) -> total 32 bits.

📌 Example Immediate Arithmetic Instruction: DADDIU R1, R2, # 30 (Add unsigned Immediate) means Reg[R1] ← Reg[R2] + Reg[R3]. 📌 Example Load/Store Instruction: LW R1, 30(R2) (Load word) means Reg[R1] ← Mem[30+Reg[R2]]. SW R1, 30(R2) (Store word) means Mem[30+Reg[R2]] ← Reg[R1].

Branch/Jump Register format is used for conditional branch instructions (e.g., BEQZ tests Rs for zero; BNE compares Rs and Rt) and for jump register instructions (JR and JALR).

📌 Example Branch/Jump Register Instruction: BEQZ R4, name (Branch equal zero) means If Reg[R4] = 0 then PC ← name. BNE R4, R3, name means If Reg[R4]!=Reg[R3] then PC <- name. JR R4 (jump register) means PC ← Reg[R4]. JALR R4 (Jump and Link Register) means Reg[R31] ← PC+4; PC ← Reg[R4].

Jump / Call format uses a 26-bit offset that is shifted 2 bits and then replaces the lower 28 bits of the PC. Jump and Link (JAL) places the return address in R31 for use in returning from a procedure.

🔑 Definition — J-Type: A MIPS instruction format used for jump and jump-and-link instructions. 📐 Format: Op-code (6), Address offset (26) -> total 32 bits.

📌 Example Jump/Call Instruction: J name (Jump) means PC[36..63] ← name. JAL R4 (Jump and Link) means Reg[R31] ← PC+4; PC[36..63] ← name.

⭐ Key Takeaways

A student must understand that instruction set encoding determines the trade-off between code size and number of memory accesses, with 1-address (accumulator) format requiring the fewest memory bytes per instruction. The three main instruction word types are variable, fixed, and hybrid length, with MIPS being a prime example of a fixed-length, 64-bit LOAD/STORE architecture. The MIPS ISA uses three primary formats: R-type (register-register), I-type (immediate and load/store), and J-type (jump/call), each with a specific bit layout. For R-type, op-code 000000 requires the Func field to specify the operation, while I-type uses the immediate field for data or address offset. Finally, the ability to hand-translate arithmetic expressions into MIPS assembly instructions (e.g., DADD, DADDIU, LW, SW) for different address formats is a core skill.

🧠 Quick Revision Questions

1. What are the four essential elements that must be encoded in a machine language instruction?
2. Compare and contrast variable-length and fixed-length instruction formats, giving one advantage of each.
3. For a given expression, why does a 0-address (stack) format require more instructions than a 3-address format?
4. In the MIPS R-type instruction format, what is the purpose of the func field, and why is it necessary when the op-code is 000000?
5. Describe the three MIPS instruction formats (R-type, I-type, J-type) and provide the specific purpose of the Rt field in each.

📘 Lecture 6 — Instruction Set Principles (ISA Performance Analysis, Fallacies and Pitfalls)

📖 Overview: This lecture concludes the discussion on Instruction Set Architecture by examining ISA performance, the role of compilers, and media/signal processing operations. It covers DSP multimedia operations, compiler optimization techniques, and the historical evolution of architectures, while also addressing key fallacies and pitfalls in ISA design.

🗂️ Topics Covered

The lecture begins with a recap of Lecture 5 covering instruction encoding, word length, and MIPS format. It then explores media and signal processing operands including 3D data types, SIMD operations, and DSP issues like saturating add/subtract, result rounding, and multiply-accumulate operations. The role of compilers in ISA performance is examined through optimization classifications and data allocation areas. Finally, the lecture presents a historical perspective on architecture evolution and concludes with a comprehensive summary of ISA principles.

📝 Lecture Summary

Recap: Lecture 5

The recap covers essential elements of computer instruction words including operand types, source/destination locations, and next instruction placement. Instruction word length categories include variable length, fixed length, and hybrid formats. The hybrid length taxonomy uses 4, 3, 2, 1, and 0 address formats. In comparison, the minimum number of memory bytes is required in the 1-address (accumulator) format, while the maximum is required for the 4-address format. The MIPS Instruction word format is a RISC fixed-length, 64-bit LOAD/STORE architecture supporting 8-, 16-, 32-, and 64-bit operands, with R-type, I-type, and J-type formats for arithmetic/logic, data transfer, and control flow operations.

🔑 Definition — Hybrid Format: A combination of variable and fixed length instruction encoding that uses different numbers of address fields (from 0 to 4) to balance code density and instruction complexity.

📐 Formula: Memory bytes required: 1-address format (minimum) < 4-address format (maximum)

Media and Signal Processing Operands

Graphic applications deal with 2D and 3D images. The 3D data type is called a vertex, which has a 4-component structure: x-coordinate, y-coordinate, z-coordinate, and w-coordinate. Three vertices specify a graphic primitive like a triangle, and the fourth (w) helps with color and hidden surfaces. Vertex values are usually 32-bit floating-point values. DSP adds fixed point to the data types, with the binary point placed just to the right of the sign bit.

A triangle is visible when depicted as filled with pixels. Pixels are typically 32-bits, usually consisting of four 8-bit channels: R (red), G (green), B (blue), and A (transparency).

💡 Why this matters: Understanding 3D data types is critical for graphics processing because modern multimedia applications rely heavily on vertex and pixel manipulation.

🔑 Definition — Vertex: A 4-component data structure (x, y, z, w) used in 3D graphics to specify points in space, with the fourth component aiding color and hidden surface calculations.

Media and Signal Processing Operations

Data for multimedia operations is usually much narrower than the 64-bit data word of modern processors. Thus, 64-bit may be partitioned into four 16-bit data values so that the 64-bit ALU can perform four 16-bit operations (like add) in a single clock cycle. Extra hardware is added to prevent the 'CARRY' between the four 16-bit partitions of the 64-bit ALU. These operations are called Single-Instruction Multiple-Data (SIMD) or vector operations.

Most graphic multimedia applications use 32-bit floating-point operations, allowing a single instruction to launch two 32-bit operations on operands found side-by-side in double precision registers. All SIMD instructions are fixed-width operations performing multiple narrow operations on either 64-bit or 128-bit ALUs. The narrow operations are shown as B (byte), H (half word), W (word), and 8B (double word).

🔑 Definition — SIMD: Single-Instruction Multiple-Data operations where a single instruction performs the same operation on multiple data elements simultaneously by partitioning a wider ALU.

Digital Signal Processing Issues

Three main DSP issues are identified:

1. Saturating Add/Subtract: When the result is too large and overflow occurs
2. Result Rounding: Choosing from IEEE 754 mode algorithms
3. Multiply Accumulate (MAC): Vector and matrix dot product operations

Saturating Add/Sub: DSP cannot ignore overflow results as it may miss an event, so it uses saturating arithmetic. If the result is too large to be represented, it is set to the largest representable number based on the sign of the number. Result Rounding: IEEE 754 has several algorithms to round the wider accumulator into a narrower one; DSPs select the appropriate mode. Multiply-Accumulate (MAC): MAC operations are key to dot product operations of vector and matrix multiply, which need to accumulate a series of products.

🔑 Definition — Saturating Arithmetic: An arithmetic mode where overflow results are clamped to the maximum or minimum representable value instead of wrapping around, commonly used in DSP to prevent missed events.

📌 Example: In saturating addition for an 8-bit signed number (range -128 to 127), if adding 100 + 40 = 140 (overflow), the result is clamped to 127 instead of wrapping to -116.

ISA Performance – Role of Compiler

The interaction of compiler and high-level languages significantly affects how a program uses an ISA. Optimizations performed by compilers are classified as:

• High-level optimization: Often done on the source with output fed to later optimization passes
• Local Optimization: Done within a straight-line code fragment (basic block)
• Global Optimization: Extends optimization across branches
• Register Allocation: Associates registers with operands
• Processor-dependent optimization: Uses specific architecture features

Two important questions regarding compiler technology impact are:

1. How are variables allocated?
2. How many registers are needed to allocate variables appropriately?

These questions are addressed using three areas where high-level language allocates data:

1. Local Variable area – Stack: Used to allocate local variables; grows or shrinks on procedure call/return. Objects are primarily scalar (single variables) addressed by stack-pointer. Register allocation is much more effective for stack-allocated objects.
2. Global Data Area: Used to allocate statically declared objects like global variables and constants. Objects are mostly arrays and other aggregate data structures. Register allocation is relatively less effective for global variables. Global variables are aliased (multiple ways to address them), making it illegal to put them in registers.
3. Dynamic Object Allocation: Heap: Used to allocate objects that do not adhere to stack. Objects are accessed with pointers but are not scalars. Most heap variables are aliased, so register allocation is almost impossible.

ISA Performance – MIPS Floating-point Operations

The instructions manipulate floating-point registers and indicate whether the operation is single or double precision:

• MOV.S: Copies a single precision register to another of the same type
• MOV.D: Copies a double precision register to another of the same type

To get greater performance for graphic routines, MIPS64 offers Paired-Single Instructions. These instructions perform two 32-bit floating-point operations on each half of the 64-bit floating-point register. Examples include ADD.PS, SUB.PS, MUL.PS, and DIV.PS.

🔑 Definition — Paired-Single Instructions: MIPS64 instructions that perform two simultaneous 32-bit floating-point operations on a 64-bit register, doubling throughput for graphics applications.

Putting it All Together

The historical evolution of architectures is traced:

• Earliest architectures: Limited instruction sets by hardware technology of that time
• 1960s: Stack architecture became popular, viewed as a good match for high-level languages
• 1970s: Main concern was reducing software cost, producing high-level architectures like VAX
• 1980s: Return to simpler architecture due to sophisticated compiler technology
• 1990s: New architectures introduced with:
  1. Address size doubling (32-bit to 64-bit)
  2. Optimization of conditional branches via conditional execution (e.g., conditional move)
  3. Optimization of cache performance via pre-fetch
  4. Multimedia support
  5. Faster floating-point instructions
  6. Long Instruction Word

Concluding the Instruction Set Principles

The three pillars of computer architecture are Hardware, Software, and Instruction Set. The instruction set is the interface between hardware and software.

The taxonomy of instruction sets includes Stack, Accumulator, and General Purpose Register. Types and sizes of operands include types like Integer, FP, and Character, with sizes of Half word, Word, and Double word.

Operations are classified as Arithmetic, Data transfer, Control, and Support. Operand addressing modes include Immediate, Register, Direct (Absolute), and Indirect. Classification of indirect addressing includes Register, Indexed, Relative (with displacement), and Memory. Special addressing modes include Auto-increment, Auto-decrement, and Scaled. Control instruction addressing modes include Branch, Jump, and Procedure call/return.

During the 1950s-1960s, computer architecture focused on computer arithmetic. From 1970s to mid-1980s, the focus was instruction set design. In the 1990s, focus became multi-dimensional, emphasizing CPU design, memory system, I/O system, and multi-processor systems based on quantitative principles.

⭐ Key Takeaways

The instruction set architecture serves as the critical interface between hardware and software, and its design fundamentally impacts computer performance. For modern multimedia applications, SIMD operations and DSP-specific features like saturating arithmetic and MAC operations are essential for efficient processing. Compiler technology plays a pivotal role in ISA performance through various optimization levels and data allocation strategies (stack, global, heap). The historical evolution shows a cycle from simple to complex architectures and back to simplicity, driven by compiler capabilities. Understanding instruction encoding formats, addressing modes, and the relationship between instruction count and CPI is crucial for evaluating and comparing different ISA designs.

🧠 Quick Revision Questions

1. What are the three areas of data allocation in high-level languages, and which one is most suitable for register allocation?
2. Explain the difference between saturating arithmetic and standard overflow handling in DSP operations.
3. How does a paired-single instruction in MIPS64 achieve higher performance for graphics routines?
4. What are the five classifications of compiler optimizations, and where is each applied?
5. Which instruction format (0, 1, 2, 3, or 4 address) requires the minimum number of memory bytes, and why?

📘 Lecture 7 — Computer Hardware Design (Single Cycle Data path and Control Design)

📖 Overview: This lecture reviews the fundamental hardware design of a computer, focusing on the sub-systems of the CPU (datapath and control). It introduces the concept of a Single Cycle Datapath, where each instruction is executed in one clock cycle, and details the RTL micro-operations for different datapath implementations (Unibus, 2-bus, 3-bus). Understanding these concepts is crucial for designing a functional processor, as the datapath and control directly impact performance metrics like CPI and clock cycle time.

🗂️ Topics Covered

The lecture begins with a recap of instruction set principles, including encoding, multimedia/ DSP operations, and ISA performance. It then reviews the basic building blocks of a computer and the sub-systems of the CPU (datapath and control). The core of the lecture covers the processor design steps, followed by a detailed explanation of datapath implementations (Unibus, 2-bus, 3-bus) and their RTL micro-operations. It concludes with an introduction to Single Cycle Datapath design, its timing, and the control signals required for executing instructions like Add.

📝 Lecture Summary

Recap: Instruction Set Principles

The lecture starts by revisiting the three pillars of computer architecture. It covers instruction encoding, which can be fixed, variable, or hybrid in word length, using the MIPS format as an example. It also reviews Multimedia and Digital Signal Processor (DSP) operations, such as saturating add/subtract, result rounding, and the multiply accumulate operation. Finally, it discusses Instruction Set Performance, emphasizing the role of the compiler and how it affects the use of the ISA by a program, specifically in allocating variables to the stack (local variables), global data area, and heap (dynamic objects).

Basics of Hardware Design

The computer's basic building blocks are the Central Processing Unit (CPU), Memory, Input/Output (Peripherals), and Buses. The CPU itself has two main sub-systems: the Datapath, which facilitates the transfer of information, and the Control, which generates signals to control the sequence of steps and direct data flow. Design is a creative process involving top-down decomposition of complex functions into primitive ones and bottom-up composition of primitive building blocks into complex assemblies.

Processor Design Steps

The design process follows these steps: 1) Design the Instruction Set Architecture (ISA). 2) Use RTL (Register Transfer Language) to describe the processor's static and dynamic behavior. 3) Select a suitable datapath implementation. 4) Map the behavioral RTL of each instruction to structural RTL, based on the chosen implementation and synchronous clocking signals. 5) Prepare a list of control signals for each structural RTL statement. 6) Develop logic circuits for the control signals. 7) Tie the datapath and control together. Key goals are to minimize the amount of control hardware and development time. Each instruction is performed in two phases: Instruction Fetch and Instruction Execute, which are divided into micro-operations completed in fixed time intervals.

Datapath Implementations

The datapath is the arithmetic organ of the stored-program computer. It consists of registers, internal buses, arithmetic units, and shifters, and can be implemented as a Unibus, 2-bus, or 3-bus structure.

🔑 Definition — Datapath: The arithmetic organ of the Von-Neumann’s stored-program organization that facilitates the transfer of information from one part (register/memory/IO) to the other.

Unibus Datapath Structure: Has a single internal bus connecting a register file (32 registers of 32-bit each), an arithmetic and shifter unit, and other registers (PC, IR, MAR, MBR, A, C). Each register has a load control line and tri-state buffers for bus access.

RTL micro-operations of Unibus structure:

• Instruction Fetch: T0 MAR ← PC, C ← PC + 4 T1 MBR ← M[MAR], PC ← C T2 IR ← MBR
• R-type Arithmetic/Logical (Add/Sub/And/OR ra, rb, rc): T3 A ← R[rb] T4 C ← A op R[rc] T5 R[ra] ← C
• Load/Store (ld/st ra, c2(rb)): T3 A ← ((rb = 0): 0, (rb ≠ 0): R[rb]) T4 C ← A + (sign extended and shifted c2) T5 MAR ← C T6 MBR ← M[MAR] (load); MBR ← R[ra] (store) T7 R[ra] ← MBR (load); M[MAR] ← MBR (store)

2-bus Datapath Structure: Contains two internal buses (in-bus and out-bus). The ALU output connects directly to the in-bus, speeding up execution.

• R-type Arithmetic/Logical (Add/Sub/And/OR ra, rb, rc): T3 A ← R[rb] T4 R[ra] ← A op R[rc] (Completed in 2 steps, instead of 3)

3-bus Datapath Structure: Contains three internal buses (A-bus, B-bus, C-bus). The register file has two read ports (to A and B buses) and one write port (from C bus). This allows an R-type instruction to be completed in a single execute step.

• Example for sub ra, rb, rc: R[ra] ← R[rb] - R[rc] is done in one step.

📐 Formula: Execution time (ET) = IC x CPI X T → The total time to run a program is the number of instructions (IC) multiplied by the clock cycles per instruction (CPI) multiplied by the clock cycle time (T). The datapath implementation directly affects CPI and T.

Single Cycle Datapath

In a Single Cycle Datapath, an instruction's fetch and execute phases are completed in a single clock cycle. The cycle length is constant, but the number of internal micro-operations may vary. The timing step generator returns to T0 on cycle completion.

🔑 Definition — Single Cycle Datapath: A datapath where an instruction is fetched and executed in one clock cycle, so CPI = 1.

Worst Case Timing (Load): The load instruction uses the most time resources. The clock cycle must be long enough to accommodate all the delays in this path:

1. Clock-to-Q time for the PC.
2. Instruction Memory access time.
3. Control Logic delay (generating signals like ALUctr), Register File access (to put Rs on busA), and Sign Extension (for immediate). We assume register file access takes longer than sign extension.
4. ALU delay for address calculation.
5. Data Memory access time.
6. Setup time for writing result (busW) into the register file at the next clock tick.

Single Cycle Memory Structure: Since the instruction and data memory addresses are available simultaneously, a structural hazard occurs. To solve this, the memory unit is partitioned into Instruction Memory and Data Memory.

Single Cycle Datapath during Add: For an Add instruction, the Rs and Rt fields are used to read registers onto busA and busB. The ALUctr signals are set to "Add". With MemtoReg set to 0, the ALU output is placed on busW. RegWr is set to 1 to write the result to the register file. ALUSrc is 0 (using busB), so ExtOp is a "don't care". MemWr is set to 0.

Instruction Fetch Unit at the End of Add: For instructions other than Branch and Jump, the Branch and Jump control signals are set to 0. This causes the output of the first adder (PC + 4) to be selected via the multiplexers and placed into the PC, which is updated at the next clock tick. The PC does not have a Write Enable signal as it is updated every cycle.

⭐ Key Takeaways

A student must understand the fundamental CPU subsystems: the datapath (for data transfer and computation) and the control unit (which generates signals to orchestrate operations). The processor design process starts with the ISA and uses RTL to formally describe instruction behavior. The choice of datapath (Unibus, 2-bus, 3-bus) directly impacts the number of micro-operations and, consequently, the CPI. The Single Cycle datapath achieves a CPI of 1 but has a long clock cycle, determined by the worst-case path (the Load instruction). Finally, the control signals (e.g., RegWr, ALUSrc, MemtoReg, MemWr) are the key to routing data and controlling functional units.

🧠 Quick Revision Questions

1. What are the two main sub-systems of a CPU, and what is the primary function of each?
2. Describe the key difference between a Unibus and a 3-bus datapath in terms of how many clock cycles are needed for an R-type instruction.
3. Why is the memory unit partitioned into "Instruction Memory" and "Data Memory" in a single-cycle datapath?
4. Explain why the Load instruction determines the minimum clock cycle time for a single-cycle processor.
5. For an R-type Add instruction, what must be the values of the control signals RegWr, ALUSrc, and MemtoReg?

📘 Lecture 8 — Computer Hardware Design (Multi Cycle Datapath and Control Design)

📖 Overview: This lecture critically reviews the single-cycle datapath design, demonstrating how control signals are set for various instruction types (R-type, I-type, J-type). It then introduces the motivation for multi-cycle design, showing how hardware utilization can be improved by reusing components across multiple clock cycles instead of requiring a single long cycle.

🗂️ Topics Covered

This lecture begins with a recap of the single-cycle datapath and its control signals, using detailed examples for the Add, Or Immediate, Load, Store, and Branch instructions. It then analyzes hardware utilization inefficiencies, introduces the concept of local decoding for the ALU control, presents the multi-cycle datapath architecture, discusses controller FSM specification and sequencer-based control, and concludes with an introduction to exceptions including interrupts, traps, and precise interrupts.

📝 Lecture Summary

Recap: Single cycle datapath and control signals

The lecture begins by reviewing the 3-bus based single-cycle MIPS datapath, where every instruction completes in one clock cycle. The key micro-operations of the fetch phase are: MBR ← M[PC]; PC ← PC+4; IR ← MBR. The execute phase involves: ID (instruction decode), operand read, execution, memory access, and writeback. Control signals are generated by a main controller that decodes the instruction's op field. The lecture then examines how control signals are set for different instruction types, starting with R-type instructions like Add and Subtract.

Example of Single Cycle Design

Control Signals for Add rd, rs, rt (R[rd] ← R[rs] + R[rt])

During execution of an Add instruction, the Rs and Rt fields are fed to the Ra and Rb address ports of the register file, placing register contents on busA and busB. The ALUctr signals are set to Add, and MemtoReg is set to 0 so the ALU output goes onto busW. RegWr is set to 1 to write the result to the register file. ExtOp is a don‘t care because ALUSrc is 0 (using busB). MemWr must be 0, and Branch and Jump must be 0.

🔑 Definition — Control Signal: A binary signal generated by the control unit that selects the operation of a datapath component (e.g., MUX selection, ALU operation, register write enable).

For the Instruction Fetch Unit at the end of Add, PC is updated to PC+4. Both Branch and Jump signals are 0, so the output of the first adder (PC+4) is selected through the two 2-to-1 MUXes and placed into the Program Counter register. The PC updates every cycle (no Write Enable signal).

The Single Cycle Datapath during Or Immediate (R[rt] ← R[rs] OR ZeroExt[imm16])

The OR Immediate instruction ORs the content of Rs with the Zero Extended immediate field and writes the result to Rt. The Rs field goes to Ra. ExtOp is set to 0 for Zero Extend. ALUSrc is set to 1 to select the immediate field over busB. ALUctr is set to OR. The key difference from R-type: RegDst must be 0 because the destination is specified by the Rt field (not Rd). RegWr is 1.

📌 Example: For instruction ORI $t0, $s1, 100:

• Op field = ORI, Rs = $s1, Rt = $t0, Imm16 = 100
• ExtOp = 0 (zero extend 100 to 0x00000064)
• Rs ($s1) value placed on busA
• ALUSrc = 1, so ALU input B = 0x00000064
• ALUctr = OR → output = R[$s1] OR 0x00000064
• RegDst = 0, so write address is Rt ($t0)
• MemtoReg = 0, so result from ALU goes to busW
• RegWr = 1 → R[$t0] = result

The Single Cycle Datapath during Load (R[rt] ← Data Memory[R[rs] + SignExt[imm16]])

The Load instruction reads the contents of Rs and adds it to the Sign Extended immediate field to form the data memory address. ExtOp is set to 1 (SignExtend). ALUSrc = 1, ALUctr = Add. The effective address is sent to Data Memory, and the read data goes to busW via MemtoReg = 1. RegDst = 0 (destination is Rt). RegWr = 1. MemWr = 0.

The Single Cycle Datapath during Store

Store is the inverse of Load. It reads Rs for the base address and Rt for the data to be stored. ExtOp = 1 (SignExtend), ALUSrc = 1, ALUctr = Add (for address calculation). The Rt field is fed to the Rb port of the register file to place the store data on busB. MemWr = 1 to write to Data Memory. Store does not update the register file, so RegWr = 0, making RegDst and MemtoReg don‘t cares.

The Single Cycle Datapath during Branch (if R[rs] == R[rt] then PC = PC + 4 + SignExt[imm16]*4)

The Branch instruction subtracts Rs from Rt to set the Zero condition. Rs goes to Ra, Rt goes to Rb. ALUSrc = 0 (using busB). ALUctr = Subtract. Zero bit is set to 1 if the difference is 0 (branch taken). RegWr = 0, MemWr = 0. Branch signal is set to 1. In the Instruction Fetch Unit, when Branch = 1 and Zero = 1, the output of the second adder (PC+4 + SignExt[imm16]*4) is selected and written to PC. If Zero = 0, PC+4 is selected (boring case).

A Summary of the Control Signals

A table summarizes control signals for seven instructions: Add, Subtract, Ori, Lw, Sw, Branch on Equal, and Jump. The first two (Add, Sub) are R-type instructions, requiring both the op field and func field to be identified. Ori, Lw, Sw, and Branch are I-type, and Jump is J-type — these are identified by the op field alone. Note that Add and Sub have identical control signals except the last row (ALUctr), which motivates the concept of local decoding.

Local Decoding Concept

Instead of the Main Control generating ALUctr signals directly, it generates a set of signals called ALUop. For I-type and J-type instructions, ALUop directly tells the ALU what to do. For R-type instructions, the Main Control signals "I don't know what the ALU has to do but I know it is R-type," and a separate ALU Control block (local decoder) uses the func field to generate the correct ALUctr. This saves columns in the control table and allows the same ALUop encoding to work for ALL R-type instructions, not just Add/Subtract.

📐 Formula: ALUctr = f(ALUop, func_field) — The ALU control generates the exact ALU operation code using ALUop from Main Control and the instruction's func field.

Multi Cycle Design - Datapath

How Effectively are we utilizing our hardware? In the single-cycle design, hardware is used inefficiently. For example, memory is used twice at different times (instruction fetch and data access). The average memory access per instruction = 1 + F_lw + F_sw ≈ 1.3. If CPI were 4.8 (hypothetical), instruction memory utilization = 1/4.8 and data memory utilization = 0.3/4.8 — very low. We could reduce hardware without hurting performance by using an alternative datapath: Multiple Cycle Datapath that immunizes hardware — using 1 memory unit and 1 adder shared across multiple cycles.

💡 Why this matters: Multi-cycle design allows each clock cycle to be shorter (just the time for one functional unit operation) and reuses expensive components like memory and ALU, reducing hardware cost while still maintaining correct execution.

Controller FSM Spec and Sequencer-based control unit are introduced as the method to manage the multi-cycle datapath. The control unit is implemented as a Finite State Machine that sequences through states corresponding to different cycles of instruction execution (fetch, decode, execute, memory, writeback).

Two Types of Exceptions

• Interrupts: Caused by external events, asynchronous to program execution, may be handled between instructions. Simply suspend and resume the user program.
• Traps: Caused by internal events (exceptional conditions like overflow, errors like parity, faults like non-resident page). Synchronous to program execution. The condition must be remedied by the handler. The instruction may be retried, simulated, and program continued, or the program may be aborted.

Precise Interrupts: A precise interrupt preserves the state of the machine as if the program executed up to the offending instruction. This means the same system code will work on different implementations of the architecture. This position is clearly established by IBM and taken by MIPS. Precision is difficult in the presence of pipelining and out-of-order execution. Imprecise interrupts force system software to figure out what is where and put everything back together. Performance goals often lead designers to forsake precise interrupts, though developers and users usually wish they had not.

⭐ Key Takeaways

The single-cycle datapath requires a unique set of control signals for each instruction type, with R-type instructions needing both the op and func fields decoded, while I-type and J-type are identified by the op field alone. The concept of local decoding separates ALU control generation into two stages: the Main Control produces ALUop, and a dedicated ALU Control uses the func field to generate ALUctr for R-type instructions, making the design scalable. Multi-cycle design improves hardware utilization by sharing components like memory and ALU across multiple shorter clock cycles, allowing a single memory unit and adder to serve all instruction phases. The transition to multi-cycle design requires a sequencer-based control unit or controller FSM to manage the sequence of micro-operations. Finally, exceptions are classified as interrupts (external, asynchronous) and traps (internal, synchronous), with precise interrupts being crucial for software portability across different implementations.

🧠 Quick Revision Questions

1. Compare the control signal settings for an R-type instruction (Add) and an I-type instruction (Or Immediate). Which control signals are the same, and which differ, and why?
2. Explain the concept of "local decoding" for ALU control. What signals does the Main Control generate, and what does the ALU Control block use to produce the final ALUctr?
3. How does the hardware utilization differ between single-cycle and multi-cycle datapath designs? Give a specific example using memory utilization.
4. Describe how the Branch instruction affects the Instruction Fetch Unit. What signals are involved when the branch is taken versus not taken?
5. What is the difference between a precise interrupt and an imprecise interrupt? Why is this distinction important for system software compatibility?

📘 Lecture 9 — Computer Hardware Design (Multi Cycle and Pipeline - Datapath and Control Design)

📖 Overview: This lecture explores the transition from single-cycle to multi-cycle datapath design, emphasizing how sharing hardware components reduces overall cost while potentially improving performance. It introduces control design methodologies using Finite State Machines and Microprogramming, and provides a foundation for understanding pipelining.

🗂️ Topics Covered

The lecture begins by recapping the single-cycle datapath and its inefficiencies, then introduces the multi-cycle approach which breaks instruction execution into five steps using shared memory and ALU. It details the multi-cycle datapath architecture, including control signals for each cycle, and compares FSM-based versus microprogrammed control design. The lecture concludes with an introduction to pipelining as a performance enhancement technique.

📝 Lecture Summary

Recap: Lecture 8

The single-cycle datapath executes instructions using a fixed-length clock cycle that must accommodate the longest instruction—the Load instruction. Analysis shows that hardware components are used inefficiently: memory is used twice (instruction fetch and data access), adders in the fetch unit are used only briefly, and the ALU operates only during execution or address calculation. This underutilization leads to the conclusion that hardware can be reduced without sacrificing performance by adding more control logic.

Multiple Cycle Approach

In the multi-cycle approach, each instruction is executed in up to five sequential steps: Instruction Fetch, Instruction Decode and Register Read, Execute (for R-type, I-type, or address calculation), Memory (read/write), and Write (to register file).

🔑 Definition — Cycle Time: The length of one clock period in a processor. In a single-cycle implementation, the cycle time equals the time to execute the longest instruction (Load). In a multi-cycle implementation, the cycle time equals the time to complete the longest single step (typically memory read/write).

📐 Formula: For single cycle, T_single = longest instruction time. For multi cycle, T_multi = longest step time. Example: If T_multi = 1 μSec, then T_single ≈ 5 μSec.

📌 Example: Consider three instructions: Load, Store, R-type (Add). Single cycle: 3 × 5 μSec = 15 μSec. Multi cycle: Load takes 5 cycles, Store and R-type take 4 cycles each → 5+4+4=13 cycles × 1 μSec = 13 μSec. Multi-cycle is 15/13 ≈ 1.24 times faster.

Single Cycle vs. Multiple Cycle

Multi-cycle implementations can take 3, 4, or 5 cycles per instruction depending on the instruction class. The key advantage is that cycle time is shorter because it is set to the longest step, not the longest instruction. However, more cycles are needed per instruction. For the example program segment, the multi-cycle design's shorter cycle time offsets the extra cycles, making it 1.24 times faster overall.

High Level View of Multiple Cycle Datapath

The multi-cycle datapath uses a single shared memory (since instruction fetch and data access occur in different cycles) and a single shared ALU (used for fetch, execute, and address calculation in different cycles). To support sharing, additional multiplexers and temporary registers are added: Instruction Register (IR), Memory Data Register (MDR), A and B operand registers, and ALUOut register. These hold intermediate results for use in later cycles. 💡 Why this matters: Sharing reduces hardware cost but requires careful sequencing and extra multiplexing logic.

Multiple Cycle Datapath Architecture

• Cycle 1 – Instruction Fetch: MUX-1 selects input IorD=0, connecting PC to memory read address. Instruction is fetched and stored in IR by asserting IRWr. Simultaneously, ALUSelA=0, ALUSelB=00 to add 4 to PC; PCSrc=0 and PCWr is asserted, loading PC+4.
• Cycle 2 – ID and Register Read: Instruction is decoded. Rs, Rt, Rd, and Imm16 fields become available. Registers at Rs and Rt are read onto buses A and B.
• Cycle 3 – Execute: ALUSelA and ALUSelB are set based on instruction type. For R-type: ALUSelA=1, ALUSelB=01 (bus A and B to ALU). For I-type/Memory: ALUSelA=1, ALUSelB=11 (bus A and sign-extended Imm16). For J-type: if condition test (sub) gives Zero=1, assert PCWrCond; then compute branch target: ALUSelA=0, ALUSelB=10, assert BrWr, PCSrc=1.
• Cycle 4 – Memory (Load/Store): For Load: IorD=1, passing ALUOut to memory read address; data appears at Dout. For Store: MemWr is asserted; ALUOut provides write address, bus B provides data.
• Cycle 5 – Write Back: For R-type: RegDest=1 (select Rd), MemToReg=0 (ALUOut to Bus-W), RegWr asserted. For I-type: RegDest=0 (select Rt), MemToReg=0. For Load: RegDest=0, MemToReg=1 (Dout to Bus-W), RegWr asserted.

🔑 Definition — Control Signals: Boolean values that determine the operation of datapath components in each cycle. Examples: ALUSelA, ALUSelB, RegDest, MemToReg, RegWr, MemWr, IorD, PCWr, IRWr, PCSrc.

Multi Cycle Control Design

Control can be designed using two primary approaches:

1. Finite State Machine (FSM): The sequence of control states is defined by next state functions. Logic is represented through logic equations and typically implemented with Programmable Logic Arrays (PLAs).
2. Micro-programming: A micro-program counter and a dispatch ROM define the sequence of control steps. Logic is represented by a truth table and control is implemented using ROM.

Microprogram Controller

A "macroinstruction" (e.g., an assembly instruction like ADD or LOAD) is interpreted by a sequence of microinstructions stored in control memory. The microprogram controller fetches each microinstruction, executes the specified datapath control signals, and determines the next microinstruction address.

Designing a Microinstruction Set

The design process involves:

1. Start with the list of all control signals.
2. Group related signals into logical fields (e.g., ALU operation, ALU operands).
3. Place fields in a logical order (ALU first, sequencing last).
4. Create a symbolic legend for the microinstruction format, showing field names, possible values, and how they set control signals. Use computer-aided design tools.
5. To minimize microinstruction width, encode operations that never occur simultaneously, using fewer bits.

🔑 Definition — Microprogramming: A control design technique where a simple processor interprets macroinstructions by executing a sequence of microinstructions stored in control memory. It is fundamental for complex instruction sets and when few register transfers are possible per instruction.

Microprogramming: Inspiration for RISC

The lecture explains that if simple instructions can execute at very high clock rates, compilers can produce microinstructions, most programs use simple instructions, and microcode is stored in RAM for bug fixes, then why not skip instruction interpretation entirely? This reasoning leads to RISC (Reduced Instruction Set Computer) architectures, where instructions are compiled directly into the machine's lowest language, avoiding the overhead of microprogram interpretation. 💡 Why this matters: RISC philosophy emerged from recognizing that microprogramming is overkill when the ISA matches the datapath directly (1-to-1).

⭐ Key Takeaways

The multi-cycle datapath shares memory and ALU across instruction cycles, reducing hardware cost compared to single-cycle designs while often improving performance due to shorter cycle times. Control is critical, implemented either through Finite State Machines (hardware-based logic) or microprogramming (ROM-based sequencer). The five-cycle execution model (Fetch, Decode/RegRead, Execute, Memory, WriteBack) is the foundation for understanding pipelining. Microprogramming, while powerful for complex ISAs, inspired the RISC movement by showing that simpler instructions can be executed more efficiently without micro-interpretation overhead.

🧠 Quick Revision Questions

1. What are the five steps in which a multi-cycle processor executes an instruction?
2. Why is the multi-cycle approach faster than the single-cycle approach for the given example (Load, Store, R-type)?
3. Name the three temporary registers added in the multi-cycle datapath and state the purpose of each.
4. What are the two main methods for designing a multi-cycle control unit, and how do they differ in implementation?
5. How did the concept of microprogramming inspire the development of RISC architectures?

📘 Lecture 10 — Computer Hardware Design (Pipeline Datapath and Control Design)

📖 Overview: This lecture introduces the fundamental concept of pipelining in computer architecture, comparing it to sequential processing using a laundry analogy. It explains the five-stage pipeline datapath, control design, performance benefits over single-cycle and multi-cycle machines, and introduces the concept of pipeline hazards that can degrade performance.

🗂️ Topics Covered

The lecture covers the concept of pipelining and its natural analogy, features of pipelined processors, the five steps of the datapath (IF, ID, EX, MEM, WB), pipelined processor design with registers and control, performance comparison between single-cycle, multi-cycle, and pipelined machines through numerical examples, pipeline execution representation, and an introduction to structural, data, and control hazards along with their impact on CPI and speedup.

📝 Lecture Summary

What is pipelining?

Pipelining is a fundamental concept that utilizes the capabilities of the Datapath by allowing multiple instructions to overlap in execution. It doesn't help the latency of a single task, but it improves the throughput of the entire workload. The potential speedup equals the number of pipe stages.

🔑 Definition — Pipelining: A technique where multiple instructions are overlapped in execution by breaking them into sequential stages, each handled by independent hardware units.

Pipelining is Natural! — Laundry Example

The lecture uses a laundry example with four loads (A, B, C, D) and four operations: Wash (30 min), Dry (30 min), Fold (30 min), and Stash (30 min). In sequential laundry, each load goes through all four operations before the next load starts, taking 8 hours for 4 loads. In pipelined laundry, work starts as soon as possible — while load A is drying, load B is being washed, etc. This takes only 3.5 hours for 4 loads.

📌 Example: Sequential laundry for 4 loads takes 30 min × 4 operations × 4 loads = 480 min (8 hours). Pipelined laundry takes (4 loads × 30 min) + (3 remaining stages × 30 min) = 120 + 90 = 210 min (3.5 hours).

Features of Pipelined Processor

• All the functional units operate independently
• Multiple tasks operating simultaneously using different resources
• Pipelining doesn't help latency of single task, it helps throughput of entire workload
• Potential speedup = Number of pipe stages

Pipelining Lessons

• Pipeline rate is limited by the slowest pipeline stage
• Time to "fill" pipeline and time to "drain" it reduces speedup
• Unbalanced lengths of pipe stages reduces speedup
• If washer takes longer than dryer, then dryer has to wait
• Stall for Dependences is required when instructions depend on each other

Five Steps of Datapath

1. Instruction Fetch (IF)
2. Instruction Decode/Register Read (ID/Reg)
3. Execute (EX)
4. Memory Access (Mem)
5. Write Back (Wr)

Pipelined Registers Included

Pipeline registers are inserted between each stage to hold intermediate results and control signals as instructions move through the pipeline stages.

Multiple Cycle vs Pipeline – Pipeline enhances performance

The lecture compares a 3-instruction program (Load, Store, R-type ADD) across three machine types.

📌 Example 1: The cycle time of a single cycle machine is 45 ns, and of multi-cycle and pipelined machines is 10 ns; average CPI due to instruction mix on multi-cycle machine is 4.6. What is the execution time on each type of machine for 100 instructions?

Solution:

• Single Cycle Machine: 45 ns/cycle × 1 CPI × 100 inst = 4500 ns
• Multi Cycle Machine: 10 ns/cycle × 4.6 CPI × 100 inst = 4600 ns
• Pipelined Machine: 10 ns/cycle × (1 CPI × 100 inst + 4 cycle drain) = 1040 ns

📌 Example 2: Consider a multicycle, unpipelined processor requires 4 cycles for the ALU and Branch operations and 5 cycles for the memory operation. Assume the relative frequency of these operations is 40%, 25% and 35% respectively; and the clock cycle is of 1 n sec. In pipelined implementation, due to clock skew and setup processor adds 0.2 n sec to the clock.

Solution:

• Unpipelined Processor: Average Execution Time/Instruction = Clock Cycle × Average CPI = 1 n sec × [{(0.4 + 0.25)} × 4 + 0.35 × 5] = 1 n sec × (0.65 × 4 + 0.35 × 5) = 1 n sec × (2.60 + 1.75) = 4.35 n sec
• Pipelined Processor: Average Execution Time/Instruction = Clock cycle + overhead = 1 n sec + 0.2 n sec = 1.2 n sec
• Speed up = 4.35 / 1.2 = 3.62 times

💡 Why this matters: Pipelining achieves significant speedup even with a small clock overhead, because it processes one instruction per cycle after the pipeline is filled, rather than requiring multiple cycles per instruction.

Why Pipeline? Because the resources are there!

Pipelining exploits the fact that different functional units (instruction memory, register file, ALU, data memory) are idle during different phases of a single instruction's execution. Pipelining keeps these resources busy simultaneously.

Can pipelining get us into trouble?

Yes, through hazards:

• Structural hazards: Hardware cannot support the combination of instructions in the pipeline
• Data hazards: An instruction depends on the result of a previous instruction still in the pipeline
• Control hazards: Pipelining makes wrong decisions on branch predictions

🔑 Definition — Hazard: A situation in pipelining that prevents the next instruction in the instruction stream from executing during its designated clock cycle.

How Stall degrades the performance?

• The pipelined CPI with stalls = Ideal CPI + Stall clock cycles per instruction

How Stall degrades the performance? (Speedup formulas)

1. Speedup w.r.t unpipelined = CPI Unpipelined / (1 + stall cycles per instruction)
2. Speedup w.r.t. pipeline depth = Pipeline depth / (1 + stall cycles per instruction)

📐 Formula: Speedup = Pipeline Depth / (1 + Stall Cycles per Instruction) → This shows that stalls reduce the ideal speedup equal to the number of pipeline stages.

⭐ Key Takeaways

Pipelining dramatically improves throughput by overlapping instruction execution across multiple stages, achieving a potential speedup equal to the number of pipeline stages. The five-stage pipeline (IF, ID, EX, MEM, WB) is the standard model, and numerical examples show pipelined processors can be 3.6 to 4.3 times faster than non-pipelined alternatives. However, hazards (structural, data, and control) introduce stalls that degrade performance, and the actual speedup is reduced to (Pipeline Depth) / (1 + Stall Cycles per Instruction). The pipeline rate is always limited by the slowest stage, making balanced stage design critical.

🧠 Quick Revision Questions

1. What are the five stages of a pipelined datapath, and what does each stage do?
2. Using the laundry analogy, explain why pipelining improves throughput but not latency of a single task.
3. What is the execution time for 100 instructions on a pipelined machine with 10 ns cycle time and 4 cycle drain?
4. What are the three types of pipeline hazards, and what causes each one?
5. How do you calculate the speedup of a pipelined processor compared to an unpipelined processor when stalls are present?

📘 Lecture 11 — Computer Hardware Design (Pipeline and Instruction Level Parallelism)

📖 Overview: This lecture covers the three primary types of hazards that can occur in a pipelined datapath: structural, data, and control hazards. It explains the causes of these hazards and presents multiple solutions for each, including stalling, forwarding, and branch prediction techniques, which are critical for maintaining performance in modern processors.

🗂️ Topics Covered

This lecture begins with a recap of multi-cycle versus pipeline datapaths and performance enhancement. It then delves into structural hazards, caused by resource conflicts like a single memory port, and presents solutions like inserting bubbles or adding functional units. Next, it covers data hazards, which arise from instruction dependencies, and explains solutions like stalling and forwarding/bypassing, with special attention to loads. Finally, it addresses control hazards caused by branch instructions, detailing several handling methods including stalling, re-fetching, delayed branching, and branch prediction.

📝 Lecture Summary

Recap: Lecture 10

The lecture reviews the transition from a multi-cycle datapath to a pipelined datapath and the key components involved. It reiterates how pipelining enhances performance and introduces the concept of hazards that can disrupt the pipeline flow.

Structural Hazards

A structural hazard occurs when the hardware attempts to use the same resource in two different ways at the same time. For example, a single memory port being accessed for both an instruction fetch and a data read in the same clock cycle creates a structural hazard.

💡 Why this matters: Structural hazards force the pipeline to stall, reducing the performance benefit of pipelining. A common example is a LOAD instruction accessing data memory while the next instruction is being fetched from the same single-ported memory. This conflict is resolved by inserting a stall (or a "bubble") into the pipeline.

🔑 Definition — Structural Hazard: An attempt to use the same resource two different ways at the same time. 📐 Solution: Insert a "bubble" (stall) or add multiple functional units (e.g., dual-ported memory).

Pipelining the Load Instruction The five independent functional units used per instruction are: Instruction Memory (IF), Register File's Read ports (ID), ALU (EX), Data Memory (MEM), and Register File's Write port (WB). Because each unit is used only once per instruction, no conflicts arise when pipelining only load instructions. Performance improves dramatically; three loads take 7 cycles pipelined versus 15 cycles in a multi-cycle processor, achieving an effective CPI of 1.

The Four Stages of R-type An R-type instruction does not access data memory, so it completes in four stages: IF, ID, EX, and WB. During the EX stage, the ALU operates on register operands, and the result is written back in the WB stage.

🔑 R-type instruction: An instruction that uses registers for all operands and results, completing in four stages (IF, ID, EX, WB) in a 5-stage pipeline.

Pipelining the R-type and Load Instruction Mixing R-type and Load instructions creates a structural hazard because the R-type instruction writes to the register file in its 4th stage (WB), while the Load instruction writes in its 5th stage (WB). This leads to two instructions trying to write to the single write port of the register file at the same time.

🔑 Important Observation: Each functional unit must be used at the same stage for all instructions to prevent structural hazards.

Solution 1: Insert "Bubble" into the Pipeline Insert a stall cycle after the Load instruction to delay the R-type instruction's write, preventing the conflict. This solution is complex to implement and degrades performance because the effective CPI for a load becomes 2.

Solution 2: Delay R-type's Write by One Cycle Add a "No-OP" (MEM) stage to the R-type instruction pipeline, making it take 5 stages (same as Load). The R-type now uses the register file's write port at its 5th stage, eliminating the conflict. This simpler solution maintains an effective CPI of 1.

Eliminating Structural Hazards Structural hazards can be minimized by using stalls (bubbles) or by adding multiple functional units (e.g., separate instruction and data caches, or dual-ported register files).

📐 Example: Dual-port vs. Single-port

• Machine A: Dual-ported memory, ideal CPI = 1.
• Machine B: Single-ported memory, 1.05x faster clock, ideal CPI = 1, loads are 40% of instructions.
• SpeedUp_A = Pipeline Depth
• SpeedUp_B = (Pipeline Depth / (1 + 0.4)) * 1.05 = 0.75 * Pipeline Depth
• SpeedUp_A / SpeedUp_B = 1.33, meaning Machine A is 1.33 times faster.

Data Hazards

A data hazard occurs when an instruction attempts to use an operand before the previous instruction that produces it is ready. This happens because pipelining overlaps instruction execution, changing the relative timing of read/write operations.

🔑 Definition — Data Hazard: A situation where an instruction depends on the result of a prior instruction still in the pipeline, occurring because of a change in the order of operand read/write.

Example Data Hazard on R1

Add R1, R2, R3   ; R1 = R2 + R3
Sub R4, R1, R3   ; Needs R1 from Add
And R6, R1, R7   ; Needs R1 from Add
Or  R8, R1, R9   ; Needs R1 from Add
Xor R10, R1, R11 ; Needs R1 from Add (safe if after write)

Data Hazard Solution #1 – Stall Insert stalls into the pipeline to wait until the required data is available. This effectively "freezes" the dependent instructions until the producing instruction's result is written back.

Data Hazard Solution – Forwarding (or Bypassing) Also known as forwarding, this technique resolves data hazards by directly feeding the result from a previous instruction's EX or MEM stage to the dependent instruction's ALU input, bypassing the register file. This avoids stalls for ALU-to-ALU dependencies.

Forwarding (or Bypassing): What about Loads? Load instructions introduce a "use" data hazard because the data from memory (MEM stage) is needed in the next instruction's EX stage. Since the data is not available early enough for forwarding, a stall (often called a "load-use stall") is required when an instruction immediately uses the result of a load.

Control Hazards

A control hazard (or branch hazard) occurs when the pipeline makes a decision about which instruction to fetch next before the condition of a branch instruction is evaluated.

🔑 Definition — Control Hazard: A hazard that arises when a branch instruction may change the Program Counter (PC) to something other than PC+4, and the next instruction has already been fetched.

Example BEQ Taken If a branch instruction (e.g., BEQ) is taken, the next instruction address is determined in the EX stage. However, the next instruction (a LOAD) is already fetched in the ID stage, leading to a control hazard. The simple solution is to freeze the pipeline (hold instructions after the branch) and flush (delete) incorrectly fetched instructions if the branch is taken.

Dealing with Branches There are five main methods:

1. Stall
2. Redo Fetch after branch
3. Delayed branching
4. Branch prediction
5. Multiple Streams

Solution #1: Stall The simplest approach. Stall the pipeline until the branch condition is evaluated (EX stage) and the target address is known (next stage). This introduces 3 stall cycles per branch.

Reducing Number of Stall By moving the branch decision logic to the end of the ID stage (2nd stage) and adding hardware to compare registers, the number of stalls can be reduced to 2 clock cycles per branch instruction. This can be further reduced to 1 for BEQZ/BNEZ if a zero register is tested.

Solution #2: Redo Fetch after Branch Since a branch is detected in the ID stage, the next instruction fetch is a stall. The incorrectly fetched instruction is ignored, and the correct successor instruction is refetched. The impact is 1 clock cycle per branch instruction if the branch is untaken.

Solution #3: Delayed Branch – S/W Method This software technique redefines the branch behavior to take place after the next instruction (the delay slot). The instruction in the delay slot is always executed, regardless of whether the branch is taken or not. The impact is 0 clock cycles per branch if a useful instruction can be placed in the slot (approximately 50% of the time).

Solution #4: Prediction The processor guesses the direction of the branch and starts fetching from that path. If the guess is wrong, the pipeline is flushed and restarted.

• Predict Branch Not Taken: Assume the branch is not taken and continue fetching sequentially. If taken, flush the fetched instructions and fetch from the target.
• Predict Branch Taken: Assume the branch is taken and start fetching from the target address as soon as it's computed. This is more effective for loops where the branch is taken most of the time.

Solution #5: Multiple Streams Have two separate pipelines. One pipeline pre-fetches instructions sequentially, while the other pre-fetches from the branch target. The appropriate pipeline is used when the branch is resolved. This leads to bus and register contention and is more complex.

⭐ Key Takeaways

The three primary hazards in pipelined datapaths are structural (resource conflicts), data (operand dependencies), and control (branch decisions). Structural hazards are solved by stalling or adding more hardware. Data hazards are mitigated using forwarding for ALU results, but a stall is still needed for "load-use" dependencies. Control hazards can be handled through stalls, delayed branching, or sophisticated branch prediction schemes, which are essential for high-performance processors. The goal of all these techniques is to maintain an effective CPI as close to 1 as possible by minimizing pipeline stalls.

🧠 Quick Revision Questions

1. What is the primary difference between a structural hazard caused by a single memory vs. a data hazard?
2. Explain the concept of "forwarding" as a solution for data hazards and why it is not always sufficient for load instructions.
3. What are the performance implications (in terms of stall cycles) for the "stall" and "delayed branch" solutions to control hazards?
4. Describe the "predict branch not taken" strategy for handling control hazards. What happens if the prediction is wrong?
5. Why is it necessary for every instruction in a pipeline to use each functional unit at the same stage to avoid structural hazards?

📘 Lecture 12 — Instruction Level Parallelism (Introduction to multi cycle pipelined datapath)

📖 Overview: This lecture extends basic pipelining concepts to handle floating-point (FP) instructions with longer latencies in MIPS architecture. It explores how instruction-level parallelism (ILP) can be enhanced through deeper pipelines, examines the hazards that arise from longer FP operations, and introduces both static and dynamic scheduling techniques to overcome these hazards.

🗂️ Topics Covered

The lecture begins with a recap of pipelining basics and three generic data hazards (RAW, WAR, WAW), then moves into longer pipelines specifically for FP instructions. It covers loop-level parallelism, FP loop hazards including structural, data, and control hazards, and presents the MIPS FP adder flow diagram with step-by-step addition. The lecture details functional unit latency and initiation intervals, shows two versions of MIPS FP pipelines (with unpipelined and pipelined functional units), and concludes with scheduling techniques and exception handling in out-of-order execution.

📝 Lecture Summary

Recap: Pipelined datapath and control

The previous lecture reviewed the pipelined datapath to understand ILP basics – overlapping instruction execution to enhance performance. Key components of the pipeline datapath were examined. Performance enhancement from pipelining helps instruction bandwidth but not latency. Three types of pipeline hazards were identified: structural hazards, data hazards, and control hazards.

🔑 Definition — Pipeline hazard: A situation that prevents the next instruction in the instruction stream from executing during its designated clock cycle.

Three Generic Data Hazards

Read After Write (RAW): A true data dependence where instruction J tries to read an operand before instruction I writes it. Example: i: add r1,r2,r3 followed by j: sub r4,r1,r3 (j needs r1 before i writes it).

Write After Read (WAR): An anti-dependence (name dependence) where instruction J writes to a register before instruction I reads it. Example: i: sub r4,r1,r3 followed by j: add r1,r2,r3. This can be resolved through register renaming.

Write After Write (WAW): A name dependence where instruction J writes to a register before instruction I writes to it. Example: i: sub r1,r4,r3 followed by j: add r1,r2,r3.

🔑 Definition — Name dependence: A hazard that occurs when two instructions use the same register or memory location but do not have a true data flow relationship; can be eliminated by register renaming.

How to remove Hazards?

• Structural Hazard: Use multiple functional units to avoid resource conflicts.
• Data Hazard: Use forwarding or bypassing to send results directly to dependent instructions without waiting for register write.
• Control Hazards: Use predict (branch prediction) or delay branch (branch delay slots) techniques.

Instruction Level Parallelism

ILP is achieved through two main factors: clock speed and the number of instructions that can execute in parallel. A superscalar processor achieves ILP by pre-fetching and decoding multiple instructions, starting several branch instruction streams, and finally discarding all but the correct stream.

🔑 Definition — Instruction Level Parallelism (ILP): The degree to which instructions in a program can be executed simultaneously or overlapped.

MIPS Longer Pipelines – FP Instructions

For FP addition, minimum four steps are performed. The MIPS FP Adder flow diagram shows the processing stages.

Steps for FP Addition:

1. Step 1: Compare exponents of two numbers; shift the smaller number to the right until its exponent matches the larger exponent.
2. Step 2: Add the significands.
3. Step 3: Normalize the sum – shift right and increment or shift left and decrement.
4. Step 4: If no overflow or underflow, round the significand to the required number of bits. Stop if further normalization is not required; otherwise go to step 3.

Latency of Functional Unit

🔑 Definition — Latency: The number of cycles between the instruction that produces a result and the one that uses the result of the operation.

🔑 Definition — Initiation (Repeat) Interval: The number of cycles that must elapse between issuing two operations of the same type.

📐 Latency and Initiation Interval Table:

💡 Why this matters: The FP divide has an initiation interval of 25 cycles, meaning you cannot issue another divide operation for 25 cycles after starting one, creating a structural hazard.

Typical MIPS FP Pipeline

A typical MIPS FP pipeline uses three un-pipelined FP functional units. This means each functional unit (FP adder, FP multiplier, FP divider) processes one instruction at a time without internal pipelining.

MIPS FP Pipeline with Pipelined FUs

The previous FP pipeline can be extended by adding additional pipeline stages in the functional units. Additional pipeline registers are inserted between intervening stages (e.g., A1/A2, A2/A3, etc.). The ID/EX register must be expanded to connect the ID stage to A1, M1, EX, and DIV functional units. The FP divide unit is not pipelined and requires 24 clock cycles to complete.

Hazards in Longer Latency Pipeline

1. Structural hazard: All functional units are not fully pipelined, so resource conflicts may occur.
2. WAW data hazard: Instructions have varying running time and are no longer reaching the WB stage in order, so WAW hazards may occur.
3. WAR hazards are not possible because registers are read in the ID stage before any writes occur.
4. RAW data hazard stalls may be more frequent because of longer latency of operations.

📌 Example – FP Pipeline RAW Hazard:

       Clock: 1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17
L.D    F4,0(R2): IF ID EX Me WB
MUL.D F0,F4,F6: IF ID st M1 M2 M3 M4 M5 M6 M7 Me WB
ADD.D F2,F0,F8:    IF st ID st st st st st st A1 A2 A3 A4 Me WB
S.D   F2,0(R2):       IF st st st st st st ID st st st EX Me

The MUL.D must stall for L.D result (RAW hazard), and ADD.D stalls for MUL.D result, causing multiple stall cycles.

📌 Example – FP Pipeline Structural Hazard:

       Clock: 1  2  3  4  5  6  7  8  9  10 11
MUL.D F0,F4,F6: IF ID M1 M2 M3 M4 M5 M6 M7 Me WB
...              IF ID Ex Me WB
...                 IF ID Ex Me WB
ADD.D F2,F0,F8:       IF ID A1 A2 A3 A4 Me WB
...                      IF ID Ex Me WB
...                         IF ID Ex Me WB
L.D   F4,0(R2):             IF ID EX Me WB

Multiple instructions compete for the same functional unit, causing structural hazards.

Conclusion about FP Pipeline

1. Structural Hazard: Wait until the required functional unit is available.
2. RAW Data Hazard: Wait until source registers are not listed as pending destination registers that will not be available.
3. WAW Hazard: Determine if any instruction in A1, A2, ... D, M1, M2, ... has the same destination as this instruction.

Precise Exceptions: Out-of-order Completion

In the program:

DIV.D    F0,F2,F4
ADD.D   F10,F10,F8
SUB.D   F12,F12,F14

Instructions complete out of order, causing potential exception problems.

🔑 Definition — Precise exception: An exception where all instructions before the faulting instruction have completed and none after have modified any state, allowing the program to restart cleanly.

Overcoming the Data Hazard by Scheduling

• Static Scheduling: Compiler-based scheduling where the compiler rearranges instructions to avoid hazards.
• Dynamic Scheduling: Hardware-based scheduling that reorders instructions at runtime.

Dynamic Scheduling Advantages

• Allows handling cases where dependence is unknown at compile time.
• Allows code compiled for one pipeline to run on another pipeline.

In the program:

DIV.D    F0,F2,F4
ADD.D   F10,F0,F8
SUB.D   F12,F8,F14

Problems of Out-of-order execution: WAR and WAW

In the program:

DIV.D     F0,F2,F4
ADD.D    F6,F0,F8
SUB.D    F8,F10,F14
MUL.D    F6,F10,F8

Out-of-order execution introduces WAR and WAW hazards that must be managed.

Overcoming Exceptions

Split the ID pipe stage into two:

• Issue: Decode instructions and check for structural hazard.
• Read Operand: Wait until no data hazards exist, then read operands.

⭐ Key Takeaways

The most critical concept is understanding that longer FP pipelines introduce new challenges beyond basic integer pipelines: RAW stalls become more frequent due to increased latencies, WAW hazards emerge because instructions complete out of order (unlike integer pipelines where all reach WB in order), and structural hazards arise when functional units like FP divide are not fully pipelined. The latency and initiation interval values (FP ADD=3/1, FP Multiply=6/1, FP Divide=24/25) are essential for hazard analysis. To overcome these hazards, two scheduling approaches exist: static (compiler-based) and dynamic (hardware-based), with dynamic scheduling splitting the ID stage into Issue and Read Operand to handle unknown dependencies and enable cross-platform compatibility. Finally, out-of-order completion creates exception-handling challenges requiring precise exception mechanisms.

🧠 Quick Revision Questions

1. What are the three generic data hazards, and which one represents a true data dependence?
2. What is the difference between latency and initiation interval for a functional unit?
3. Why do WAW hazards occur in longer FP pipelines but not in simple integer pipelines?
4. In the MIPS FP adder, what are the four steps for adding two floating-point numbers?
5. What are the two advantages of dynamic scheduling over static scheduling?

📘 Lecture 13 — Instruction Level Parallelism (Dynamic Scheduling - Scoreboard Approach)

📖 Overview: This lecture introduces dynamic scheduling as a hardware approach to exploit instruction-level parallelism by allowing out-of-order execution. It focuses on the Scoreboard technique from the CDC 6600, detailing how it resolves data hazards (RAW, WAR, WAW) through a centralized hardware structure that manages instruction issue, operand reading, execution, and result writing.

🗂️ Topics Covered

The lecture begins by recapping in-order execution limitations and the problems of out-of-order execution. It then defines dynamic scheduling versus static scheduling. The core of the lecture explains the Scoreboard technique, including its three main data structures (Instruction Status, Functional Unit Status, Register Result Status) and the four pipeline stages it controls (Issue, Read Operand, Execute, Write Result). A detailed, cycle-by-cycle example of scoreboard operation is provided to show how instructions are issued in-order but executed and completed out-of-order, with specific attention to structural, RAW, and WAR hazard handling.

📝 Lecture Summary

Recap: Lecture 12

The recap reviews that in the standard FP pipeline, only one instruction is issued per clock cycle. Integer ADD instructions have zero latency and pass through the pipeline normally. However, FP add, multiply, and divide instructions have longer latencies, causing them to loop in the EX-stage and increasing stalls. RAW and WAR hazards can occur because instructions of varying lengths may reach the Write Back (WB) stage out-of-order. The WAW hazard occurs when the j-th instruction writes before the i-th instruction, and the i-th instruction overwrites the result. WAW hazards are resolved by either delaying the issue of the j-th instruction until i-th writes, or by stalling the i-th instruction's write.

In-Order Execution

In a simple pipelined datapath, In-order execution is enforced: instructions are fetched, decoded, and issued strictly in program sequence. If an instruction stalls due to a structural hazard or data dependence, no later instruction can proceed. In the MIPS 5-stage pipeline, both structural and data hazards are checked during the Instruction Decode (ID) stage. The issue process at ID is separated into two parts: checking for structural hazards and waiting for the absence of data hazards.

For example, in the code:

DIV.D F0, F2, F4
ADD.D F10, F0, F8
SUB.D F12, F8, F14

ADD.D must wait for DIV.D because of the RAW hazard on F0.

Basic Problems of Out-of-order Execution

Out-of-order execution allows instructions to execute when their operands are available, not necessarily in program order. This introduces problems like WAR and WAW hazards and complicates precise exceptions. Consider this FP code:

DIV.D F0, F2, F4
ADD.D F6, F0, F8
SUB.D F8, F10, F14
MUL.D F6, F10, F8

Here, SUB.D writes F8 (a source for MUL.D), creating a possible WAR. MUL.D writes F6 (the same destination as ADD.D), creating a WAW.

Dynamic Scheduling

• Static Scheduling: The compiler rearranges instruction execution to avoid hazards.
• Dynamic Scheduling: The hardware rearranges instruction execution at runtime to avoid stalls. This allows the processor to issue instructions while previous ones are stalled, handling hazards that are not known at compile time.

💡 Why this matters: Dynamic scheduling is critical for modern processors because it can deal with unpredictable runtime conditions (like cache misses) that static scheduling cannot.

Dynamic Scheduling: Scoreboarding Technique

The Scoreboard technique was introduced in the CDC 6600, which contained 4 FP units, 5 Memory Reference Units, and 7 integer operation units. In the MIPS processor, a Scoreboard is a centralized hardware structure that tracks all instructions and functional units.

Features of the Scoreboard: The Scoreboard maintains all necessary information to control and coordinate instruction execution.

Components of Scoreboard:

1. Instruction Status: Tracks which of four stages each instruction is in.
2. Functional Unit Status: Tracks the state of each functional unit (FU).
3. Register Result Status: Tracks which functional unit will write to each register.

Instruction Status

Each instruction goes through four stages, controlled by the Scoreboard:

• Issue: If a functional unit for the instruction is free and no other active instruction has the same destination register, the Scoreboard issues the instruction to the FU and updates its internal data structure. This guarantees that WAW hazards cannot occur.
• Read Operand: The Scoreboard monitors the availability of source operands. It checks if no earlier issued active instruction is going to write to the source register. This resolves RAW hazards.
• Execute: The FU begins execution and notifies the Scoreboard when it has completed.
• Write Result: The Scoreboard checks for WAR hazards. If a stall is necessary, the result write is delayed. Otherwise, the result is written.

The Instruction Status data structure is a table with rows for each instruction and columns for each stage (Issue, Read, Execution complete, Write result). Checkmarks (√) indicate the stage is complete. For example:

Functional Unit Status

This table tracks the state of each FU. Its fields are:

• Busy: A single bit indicating if the FU is busy (Y or N).
• OP: Specifies the operation (ADD, SUB, etc.).
• Registers: Fi (Destination register), Fj (first source register), Fk (second source register).
• Qj and Qk: The name of the FU that will produce source registers Fj and Fk. A value of "--" means the register is already available.
• Rj, Rk: Flags indicating whether source registers Fj and Fk are ready and not yet read. Set to "No" when the operands are read.

Example of a functional unit status table:

In the DIVIDE row, Qj = MUL1 indicates that the first source register (F0) is waiting for the result from the MUL1 unit. Rj = No means the operand has not been read yet (or is waiting). Rk = Yes means the second source register (F6) is ready and has not been read.

🔑 Definition — Qj/Qk: These fields hold the identifier of the functional unit that will write the result needed by the source registers (Fj, Fk). This is the key mechanism for resolving RAW hazards dynamically.

Register Result Status

This table has rows for each functional unit and columns for each register (F0 to F30). The entry indicates which functional unit (if any) will write its result to that register. For example:

This shows that MUL1 will write to F0, Add will write to F6, and Divide will write to F10.

Detailed Scoreboard Pipeline Control

The lecture presents a diagram showing how the Scoreboard sits between the instruction fetch/decode stage and the functional units. The Scoreboard reads the instruction from the ID stage, checks for hazards using its data structures, and either issues the instruction to a FU (if safe) or stalls it. The FUs then communicate back to the Scoreboard when execution is complete and when writing results.

Scoreboard Example

The lectures run a detailed example using a code sequence with FP Add latency = 2 clocks, Multiply = 10 clocks, and Divide = 40 clocks. The example traces the pipeline state cycle by cycle.

Scoreboard Example Code:

LD  F6, 34(R2)
LD  F2, 45(R3)
MULTD F0, F2, F4     ; Multiply
SUBD F8, F6, F2       ; Subtract
DIVD F10, F0, F6      ; Divide
ADDD F6, F8, F2       ; Add

The following is a summary of the cycle-by-cycle trace:

🔑 Definition — Structural hazard: Occurs when a required functional unit is already busy.

• Cycle 1: LD F6 issues to the load unit.
• Cycle 2: LD F2 issues to the load unit.
• Cycle 3: The Scoreboard tries to issue MULTD. However, note that the code is LD, MULTD, SUBD... The issue attempt for MULTD might stall if the FU (MUL1) is busy? No, in this cycle, the issue for MULTD is checked. The example shows that in Cycle 3, the issue of MULTD is stalled on a structural hazard because the MUL unit is not yet available? Wait, the cycle-by-cycle trace in the lecture shows:
  • Cycle 3: Issue MULT? No, stall on structural hazard. This is because the MULTD instruction requires a FU, but the scoreboard assumes only one MUL unit. Since MULTD needs the MUL unit, and it might be free, why the stall? The lecture text for Cycle 3 states: "Issue MULT? No, stall on structural hazard". Let's follow the exact sequence.
• Cycle 4: The MULTD instruction is now issued to the MUL1 unit. The Functional Unit Status and Register Result Status are updated to reflect that MUL1 is busy with MULTD, writing to F0.
• Cycle 5: SUBD issues to the Add unit. LD F2 writes its result (or passes to the next stage). The example shows the flow of instructions to their respective FUs.
• Cycle 6: DIVD issues to the Divide unit. The example shows how the scoreboard tracks the WAW hazard? No, there is no WAW here yet. The FUs are all busy.
• Cycle 7: The scoreboard checks if it can read multiply operands. Since F2 and F4 are ready (from the load), the operands for MULTD are read.
• Cycle 8a (first half): The scoreboard checks if the next instruction (SUBD) can read its operands. F6 is still being loaded? In this cycle, SUBD's source F6 might be waiting. The scoreboard also tries to issue ADDD? No, ADDD's destination is F6, which will be written by SUBD, so this creates a WAW hazard on F6.
  • Cycle 8b (second half): The scoreboard decides to stall the issue of ADDD due to the WAW hazard.
• Cycle 9: The scoreboard checks if it can read operands for MULT and SUBD. It attempts to issue ADDD, but it is still stalled.
• Cycle 11: SUBD's operands (F6, F2) become available. The scoreboard reads operands for SUBD.
• Cycle 12: The scoreboard tries to read operands for DIVD (F0, F6). F0 is waiting on MULTD. DIVD's operand read is blocked (RAW hazard).
• Cycle 13: ADDD's issue is still stalled due to the WAW hazard.
• Cycle 14: The MULTD instruction completes execution (having taken its latency). The scoreboard is notified.
• Cycle 15: MULTD is ready to write its result. The scoreboard checks for WAR hazards. Is there any instruction that needs to read F0 (the destination)? Yes, DIVD needs F0. If MULTD writes F0 now, and DIVD has not yet read it, DIVD would get the old value of F0, causing a WAR hazard. Therefore, MULTD's write result is stalled.
• Cycle 16: The stall continues. The scoreboard waits for all instructions that need to read F0 to do so.
• Cycle 17: SUBD (which does not need F0) might be ready to write its result. The scoreboard again checks for WAR on F8 (SUBD's destination). If any instruction needs F8 (like ADDD), the write could be stalled. In this cycle, the lecture asks: "Write result of ADDD?" but ADDD is still stalled in issue. The example shows SUBD writing its result.
• Cycle 18: The WAR hazard on MULTD is resolved (DIVD has read its operands). MULTD now writes its result to F0. The Register Result Status for F0 is cleared.
• Cycle 19: Now that F0 is available, DIVD can read its operands (F0 is now ready). The scoreboard reads operands for DIVD.
• Cycle 20-21: The pipeline progresses. ADDD might finally be issued (since the WAW hazard with SUBD is resolved after SUBD writes).
• Cycle 22: ADDD is issued. Its operands are available.
• Cycle 61: DIVD completes execution (after 40 cycles). It notifies the scoreboard.
• Cycle 62: DIVD writes its result. The scoreboard checks for WAR hazards. Since all subsequent instructions have been issued, there is no WAR, and the write completes.

📐 Formula/Key Concept: Hazard Resolution Rules in Scoreboard

• WAW: Prevented by checking the destination register against the Register Result Status table during the Issue stage. If another active instruction will write to the same register, the issue is stalled.
• RAW: Handled by monitoring Qj/Qk fields in the Functional Unit Status. An instruction cannot read its operands (Read Operand stage) until the FU producing the operand (identified by Qj/Qk) has written the result (or the operand is ready).
• WAR: Handled during the Write Result stage. A result write is stalled if the destination register is needed as a source by any instruction that has not yet read its operands.

📌 Example (RAW hazard): DIVD F10, F0, F6. F0 is produced by MULTD. Qj for DIVD is set to MUL1. DIVD's Read Operand stage stalls until MUL1 writes F0. This happens at Cycle 18, allowing DIVD to read at Cycle 19.

📌 Example (WAW hazard): ADDD F6, F8, F2 wants to write to F6. However, SUBD F8, F6, F2 is already active and will also write to F8 (No, SUBD writes F8). Wait, the lecture example shows ADDD F6, F8, F2 and SUBD F8, F6, F2. The WAW is on F6? No, SUBD writes F8. The WAW in this code is: Before ADDD, there is no other instruction writing to F6? Actually, there is no WAW on F6 in this code from the load? Let's re-check. The code is:

1. LD F6, 34(R2)
2. LD F2, 45(R3)
3. MULTD F0, F2, F4
4. SUBD F8, F6, F2
5. DIVD F10, F0, F6
6. ADDD F6, F8, F2 Here, LD F6 writes to F6 (the first load). ADDD F6 also writes to F6. This is a WAW hazard between LD F6 and ADDD F6. The scoreboard stalls the issue of ADDD (instruction 6) until the previous write to F6 (from LD F6) is no longer active in the pipeline.

📌 Example (WAR hazard): MULTD F0, F2, F4 completes execution and is about to write F0. But DIVD F10, F0, F6 still needs to read F0 as a source. If MULTD writes F0 now, DIVD would read the old F0? No, it would read the new F0, but that is a RAW, not a WAR. Wait. The WAR in this code is actually on F6. SUBD F8, F6, F2 writes to F8. ADDD F6, F8, F2 wants to read F8. But DIVD F10, F0, F6 wants to read F6. The WAR occurs when an earlier instruction (DIVD) reads a register (F6) that a later instruction (ADDD) will write. So, when ADDD is ready to write F6, the scoreboard stalls that write until DIVD (which was issued earlier but still executing) reads its source F6. In the cycle-by-cycle, the WAR on MULTD's write of F0 is that DIVD needs F0. If MULTD writes F0 (Cycle 15-17), DIVD (which hasn't read F0 yet due to its own RAW) would get the new F0, but DIVD is an earlier instruction that should read the old F0. So yes, MULTD's write is stalled because DIVD (an earlier instruction) hasn't read its source F0 yet.

⭐ Key Takeaways

The Scoreboard technique enables in-order issue but out-of-order execution and out-of-order completion. It uses three tables to track all instructions and functional units, resolving WAW hazards by stalling issue, RAW hazards by stalling the read of operands, and WAR hazards by stalling the write of results. The critical design point is that a result write is delayed until all earlier instructions that need to read that destination register have done so, preventing WAR. This lecture demonstrates through a cycle-by-cycle example that dynamic scheduling with a scoreboard can significantly reduce pipeline stalls compared to in-order execution, but it still incurs penalties from structural, RAW, and WAR hazards. The key trade-off is the increased hardware complexity and the need for sophisticated control logic.

🧠 Quick Revision Questions

1. What are the four stages that the Scoreboard controls for each instruction?
2. How does the Scoreboard detect and prevent a WAW hazard?
3. How does the Scoreboard handle a RAW hazard? Explain the role of the Qj/Qk fields.
4. Describe exactly when a WAR hazard is detected and resolved in the Scoreboard pipeline.
5. In the example, why was MULTD's write result stalled in Cycle 15, even though MULTD had finished execution at Cycle 14?

📘 Lecture 14 — Instruction Level Parallelism (Dynamic Scheduling – Tomasulo’s Approach)

📖 Overview: This lecture introduces Tomasulo's Algorithm, a hardware-based dynamic scheduling technique that overcomes limitations of the Scoreboard method. It explains how register renaming and reservation stations enable out-of-order execution while eliminating WAW and WAR hazards, and demonstrates the algorithm through detailed cycle-by-cycle examples and loop unrolling.

🗂️ Topics Covered

The lecture begins with a recap of the Scoreboard method and its limitations, then introduces Tomasulo's Algorithm as an alternative dynamic scheduling approach. It covers the organizational structure including reservation stations, load/store buffers, and the Common Data Bus. The three stages of Tomasulo's algorithm (Issue, Execution, Write Result) are explained through a detailed step-by-step example, followed by a comparison with Scoreboard execution. A second example demonstrates loop unrolling and register renaming in action.

📝 Lecture Summary

Recap - Lecture 13

The Scoreboard method divides the ID stage into two parts: Issue (in-order) and Read Operands (out-of-order). It has three parts: Instruction status, Functional unit status (with 9 fields including Busy, Op, Fi, Fj, Fk, Qj, Qk, Rj, Rk), and Register result status. The method enables out-of-order execution resulting in out-of-order completion.

However, Scoreboard has several limitations: no forwarding (first write register then read it), limited to instructions in basic block (small window), number of functional units (structural hazards), waiting for WAR hazards, and preventing WAW hazards. A comparison example showed Scoreboard completing at cycle 62 while Tomasulo completed earlier.

Dynamic Scheduling

Dynamic scheduling allows hardware to reorder instructions at runtime to exploit ILP when dependencies cannot be determined at compile time. This is accomplished by dividing instruction processing into stages that allow instructions behind stalls to proceed.

Tomasulo's Approach

Tomasulo's Algorithm was introduced for the IBM 360/91 about 3 years after CDC 6600 (1966), with the goal of high performance without special compilers. Key differences from Scoreboard include: IBM has only 2 register specifiers per instruction vs. 3 in CDC 6600; IBM has 4 FP registers vs. 8 in CDC 6600.

The algorithm uses distributed control and buffers with functional units instead of centralized control in Scoreboard. The FU buffers are called reservation stations which hold pending operands. Register renaming replaces registers in instructions with values or pointers to reservation stations, which avoids WAR and WAW hazards. More reservation stations than registers enable optimizations that compilers cannot achieve.

Results go from FU to reservation stations over the Common Data Bus (CDB) which broadcasts results to all FUs, unlike Scoreboard where results go through registers. The CDB differs from a normal bus: normal data bus has data + destination ("go to" bus), while CDB has data + source ("come from" bus). The CDB carries 64 bits of data + 4 bits of Functional Unit source address.

🔑 Definition — Reservation Station: A buffer at each functional unit that holds the operation, actual operands, and information to resolve hazards. Components include Op, Busy, Vj/Vk (value of source operands), Qj/Qk (reservation stations producing source values), and Qi (for store buffers only). Note: No ready flags as in Scoreboard; Qj,Qk=0 means ready.

Load Buffers have three functions: hold components of effective address until computed, track outstanding loads waiting on memory, and hold the result of completed load waiting for CDB.

Store Buffers have three functions: hold components of effective address until computed, hold destination memory address of outstanding store instructions, and hold address and value of store until memory unit is available.

Three Stages of Tomasulo's Algorithm

1. Issue — Get instruction from FP Op Queue. If reservation station is free (no structural hazard), control issues instruction and sends operands to the RS (renames registers).
2. Execution — Operate on operands (EX). When both operands ready then execute; if not ready, watch Common Data Bus for result.
3. Write Result — Finish execution (WB). Write on Common Data Bus to all awaiting units; mark reservation station available.

Tomasulo Example Cycles 0-16

The example sequence shows instructions: L.D F6, 34(R2); L.D F2, 45(R3); MULT.D F0, F2, F4; SUB.D F8, F6, F2; DIV.D F10, F0, F6; ADDD F6, F8, F2.

Key observations from the cycle-by-cycle execution:

• Cycle 1: L.D F6 issues and uses Load1
• Cycle 2: L.D F2 issues and uses Load2; unlike Scoreboard, can have multiple loads outstanding
• Cycle 3: MULT.D issued (vs. Scoreboard stalled); registers names removed ("renamed") in Reservation Stations
• Cycle 4-5: Loads completing; broadcasts on CDB to waiting units
• Cycle 6: ADDD issued (vs. Scoreboard where it was delayed)
• Cycle 7: Add1 completing; broadcasts result
• Cycle 10-11: Add2 completing; writes result (vs. Scoreboard where WAW hazard prevented writing)
• Cycle 14-16: MULT1 completing; broadcasts result faster than Scoreboard's cycle 62

The algorithm demonstrates in-order issue, out-of-order execution and completion.

Comparing to Scoreboard Cycle 62

Tomasulo completes earlier because it eliminates WAW and WAR hazards through register renaming, allows multiple loads outstanding, and uses CDB broadcast for forwarding. Scoreboard takes longer due to no forwarding, waiting for WAR hazards, and preventing WAW hazards.

Another Example: Loop Unrolling

This example multiplies an array (F0) by a scalar F2 using a loop. Tomasulo's algorithm eliminates WAW and WAR hazards through register renaming. The reservation stations allow multiple executions of the loop by dynamic unrolling when branches are predicted taken.

The loop shows two active iterations based on branch prediction taken. Key observations:

• Cycle 3: MULT1 has no register names in RS
• Cycle 6: F0 never sees Load1 result (register renaming prevents WAW)
• Cycle 7: MULT2 has no register names in RS
• Cycle 9-10: Load1 and Load2 completing; broadcasting results
• Cycle 14-15: MULT1 and MULT2 completing
• Cycle 16-21: Remaining instructions complete with CDB broadcasting results

💡 Why this matters: Register renaming prevents the WAW hazard that would occur when multiple iterations try to write to F0, and prevents WAR hazards when instructions read registers that later iterations modify.

⭐ Key Takeaways

Tomasulo's Algorithm is a dynamic scheduling technique that uses reservation stations for distributed control and register renaming to eliminate WAW and WAR hazards. The three-stage pipeline (Issue, Execution, Write Result) enables in-order issue with out-of-order execution and completion, where the Common Data Bus broadcasts results to all awaiting units. Unlike Scoreboard, Tomasulo supports multiple outstanding loads, forwarding through CDB, and more reservation stations than registers for compiler-like optimizations. The algorithm achieves faster execution than Scoreboard by eliminating structural hazards for independent operations and allowing parallel execution across multiple iterations through dynamic loop unrolling. Register renaming replaces architectural register names with pointers to reservation stations, effectively removing name dependencies and enabling greater ILP exploitation.

🧠 Quick Revision Questions

1. What are the three stages of Tomasulo's Algorithm and what happens in each?
2. How does register renaming eliminate WAW and WAR hazards?
3. What is the difference between the Common Data Bus and a normal data bus?
4. Why can Tomasulo issue MULT.D in cycle 3 while Scoreboard had to stall?
5. How does Tomasulo's algorithm achieve dynamic loop unrolling?

📘 Lecture 15 — Instruction Level Parallelism (Dynamic Branch Prediction)

📖 Overview: This lecture explores dynamic branch prediction techniques essential for high-performance pipelined processors. It introduces Branch History Tables (BHT) with 1-bit and 2-bit predictors, explains correlating branch predictors that exploit relationships between branches, and discusses accuracy improvements and implementation through Branch Target Buffers (BTB).

🗂️ Topics Covered

The lecture begins with a recap of Tomasulo's approach, then covers Dynamic Branch Prediction through Branch History Table concepts, 1-bit and 2-bit dynamic branch prediction with their accuracy limitations, Branch Prediction Buffer (BPB) implementation, correlating branches using (m,n) predictors, and concludes with Branch Target Buffer techniques and accuracy comparisons across different schemes.

📝 Lecture Summary

Recap: Lecture 14

Tomasulo's approach for IBM 360/91 achieves high performance without special compilers by distributing control and buffers with Function Units (FU). Registers in instructions are replaced by values or pointers to reservation stations (RS) , implementing register renaming. Unlike Scoreboard, Tomasulo can have multiple loads outstanding. These properties allow issuing instructions with name dependence (e.g., MULT issued with name dependence on register F2). Tomasulo eliminates WAR hazards (ADD.D writes result at Cycle 11 even though DIV.D starts execution at Cycle 16). Tomasulo issues instructions in-order but may execute them out-of-order. Integer instructions SUBI and BNEZ are executed out-of-order to evaluate conditions, and branch-taken prediction is implemented by repeating loop instructions.

Introduction to Dynamic Branch Prediction

In the previous lecture, a loop-based example demonstrated Tomasulo's approach for overcoming WAW and WAR hazards. Dynamically scheduled pipelines can yield high performance provided branches are predicted accurately.

🔑 Definition — Branch History Table (BHT) : A small memory structure that stores prediction bits for recently executed branches. If the prediction is wrong, the prediction-bit is inverted.

1-bit Dynamic Branch Prediction

Problem: In a loop, a 1-bit BHT causes two mispredictions in a row. A 1-bit predictor mispredicts at twice the rate that the branch is not-taken.

📌 Example: Consider a loop branch (For i=1 to 10): the branch is taken 9 times and not-taken once. Performance = ƒ(accuracy, cost of mispredictions). The expected accuracy should match the taken-branch frequency (9 out of 10 = 90%). But the 1-bit prediction achieves only 8 out of 10 (80%).

💡 Why this matters: The 1-bit predictor fails because after the loop exits (not-taken), on the next loop iteration it predicts not-taken again, causing two mispredictions per loop completion.

2-bit Dynamic Branch Prediction

Two bits encode four states in a saturating counter system:

• States 00 and 01: Predict Not-Taken
• States 10 and 11: Predict Taken

In a saturating counter implementation, the 2-bit counter saturates at 00 (Predict Taken) or 11 (Predict Not Taken). The counter is incremented when a branch is taken and decremented when it is not taken.

🔑 Definition — Saturating Counter: A counter that stops incrementing or decrementing when it reaches its minimum (00) or maximum (11) value.

📌 Example: State transitions:

• 00 → 01 for Taken when predicted not taken
• 10 → 11 for Taken when predicted taken

When the counter is ≥ ½ of its maximum value (≥10, meaning states 01 and 11), the branch is predicted as taken. Otherwise (<10: states 10 and 00), the branch is predicted as not taken.

📌 Example: Loop For i=1 to 10 with 2-bit predictor:

Prediction fails only once. This is a major improvement over the 1-bit predictor which failed twice.

Branch Prediction Buffer (BPB) or BHT Implementation: If prediction is wrong, prediction bits are changed. In case of predicted taken, state changes 11→10. In case of predicted not taken, state changes 00→01.

Branch History Table Accuracy

For SPEC89 benchmark, a branch prediction buffer with 4096 entries results in prediction accuracy ranging from 99% to 82%, or misprediction rates of 1% to 18%.

Impact of Size on Accuracy of BHT

As we try to exploit more ILP, the accuracy of the branch predictor becomes critical. Accuracy is shown by increasing buffer size:

• 4096 Entries with 2-bit BHT
• Unlimited Entries with 2-bit BHT

💡 Why this matters: Simply increasing the number of bits per predictor without changing the predictor structure has little impact. Alternative methods are needed to increase prediction accuracy.

Correlating Branches

The 2-bit predictor scheme uses only the recent behavior of a single branch to predict future behavior. In practice, the behavior of other branches may also influence prediction accuracy.

📌 Example: SPEC92 benchmark worst case for 2-bit predictor:

Assume aa is assigned R1 and bb is assigned R2
IF (aa==2)          DSUBUI R3, R1, #2
   aa=0;            BNEZ   R3, L1    ; branch b1 (aa!=2)
                    DADD   R1, R0, R0 ; aa=0 Not Branch
IF (bb==2)   L1:   DSUBUI R3, R2, #2
   bb=0;            BNEZ   R3, L2    ; branch b2 (bb!=2)
                    DADD   R2, R0, R0 ; bb=0 Not Branch
IF (aa!=bb)  L2:    DSUBU  R3, R1, R2
{                   BEQZ   R3, L3    ; branch b3 (aa=bb)

Here, the behavior of b3 (L2) is correlated with the behavior of b1 and b2. If b1 and b2 are both not-taken (aa=0, bb=0), then b3 is taken. A predictor using only single branch behavior cannot capture this.

Correlating Branch Predictors

Hypothesis: Recent branches are correlated; behavior of recently executed branches affects prediction of current branch.

🔑 Definition — (m,n) Predictor: A predictor that records the last m branches to select between 2^m history tables, each with n-bit counters. The old 2-bit BHT is a (0,2) predictor.

📌 Example: Illustrative code (d is assigned to R1):

IF (d==0)           BNEZ   R1, L1      ; branch b1 (d!=0)
     d=1;           DADDIU R1,R0,#1    ; branch not taken, d=1
IF (d==1)  L1:     DADDIU R3, R1, #-1
                    BNEZ   R3, L2      ; branch b2 (d!=1)

Working of correlating predictor:

If b1 is not taken, b2 will not be taken. Prediction bits are written as: Prediction if last branch is not-taken / Prediction if last branch is taken.

Four possible combinations:

For the (1,1) predictor (1-bit predictor with 1-bit of correlation), the only misprediction is on the first iteration when d=2, as this is not correlated with the previous prediction.

📌 Example: A (2,2) branch prediction buffer uses 2-bit global history to choose from among 4 predictors for each branch address. Behavior of recent branches selects between four predictions of the next branch, updating just that prediction.

💡 Why this matters: Correlating predictors significantly reduce misprediction rates by capturing patterns that single-branch predictors cannot detect.

Dynamic Branch Prediction Summary

• Branch History Table: Uses 2 bits for loop accuracy
• Correlation: Recently executed branches are correlated with the next branch
• Branch Target Buffer: Includes both branch address and prediction
• Predicated Execution: Can reduce the number of branches and number of mispredicted branches

⭐ Key Takeaways

The 1-bit branch predictor causes two mispredictions per loop completion (one for exit, one for re-entry), achieving only 80% accuracy compared to the expected 90%. The 2-bit saturating counter predictor improves this to a single misprediction per loop using four states (00, 01, 10, 11) and saturating behavior. Correlating branch predictors, represented as (m,n) predictors, use the history of the last m branches to select between 2^m tables of n-bit counters, capturing relationships between branches that single-branch predictors cannot. The accuracy of predictors depends on both the size of the Branch History Table and the predictor structure, with simply increasing bits per predictor having little impact. Branch Target Buffers combine branch address storage with prediction information to further improve performance.

🧠 Quick Revision Questions

1. Why does a 1-bit dynamic branch predictor cause two mispredictions in a row for a loop branch?
2. How many states does a 2-bit saturating counter predictor have, and what are the state transitions when a branch is taken vs. not taken?
3. In the correlating branch example with branches b1, b2, and b3, why can't a single-branch predictor correctly predict b3?
4. What does the notation (m,n) mean in the context of correlating branch predictors?
5. What is the prediction accuracy range reported for a 4096-entry 2-bit BHT on SPEC89 benchmarks?

📘 Lecture 16 — Instruction Level Parallelism (Dynamic Branch Prediction .... Cont’d)

📖 Overview: This lecture continues the exploration of dynamic branch prediction techniques in instruction-level parallelism. It covers correlating branch predictors, tournament predictors, and the Branch Target Buffer (BTB) for high-performance instruction delivery. These concepts are critical for reducing branch penalties in modern pipelined processors.

🗂️ Topics Covered

The lecture recaps dynamic scheduling and branch prediction, then examines correlating branch predictors with (m,n) notation and examples. It introduces multilevel tournament predictors with state transition diagrams, followed by a detailed discussion of the Branch Target Buffer (BTB) including its structure, operation flow, penalty calculations, and improvement techniques.

📝 Lecture Summary

Recap: Dynamic Scheduling and Branch Prediction

• Static scheduling relies on the software (compiler), while dynamic scheduling uses hardware-intensive approaches for branch prediction.

Important questions: Branch-Prediction Buffer

Q1: What is the impact of increasing the size of branch-prediction buffer on two branches in a program?

• A single predictor predicting a single branch is generally more accurate than the same predictor serving more than one instruction.
• It is less likely that two branches in a program share a single predictor.
• Therefore, increasing the size of predictor buffer does not have significant effect on two branches in a program.

Q2: How does sharing a predictor affect the misprediction rate?

Example: Sequence 1

• Here, branches B1 and B2 share a 1-bit predictor.
• B1 is always TAKEN, and B2 is always NOT-TAKEN.

Example: Sequence 2

• Another sequence of branches sharing the same predictor.

Example: Conclusion

• Why does sharing a predictor increase misprediction rate?
• If a predictor is shared by a set of branch instructions, then the members of the set of branch instructions may change over the course of execution of a long program.
• Hence, the branch action history changes and the predictor is likely to mispredict more often.

Correlating Branch Predictors Re-visited

• In the program segment: IF (d==0) Branch b1 for d!=0 d=1; IF (d==1) Branch b2 for b!=1 d=2;
• This problem may be resolved in a Correlating-Branch Predictor by recording the m most recently executed branches as taken or not taken (in 2^m branch-history tables for 1-, 2-, or n-bit predictors), and using the branch-pattern to select the proper branch history table for the current branch.

🔑 Definition — (m, n) predictor: Records the last m branches to select between 2^m history tables, each with n-bit counters (2^m n-bit predictors).

• A 2-bit BHT is regarded as a (0,2) correlating predictor.

Example:

• A 1-bit predictor with 1-bit correlation is written as (1,1) predictor.

• Here, we have two (2^1) separate prediction bits (i.e., two 1-bit BHTs):

  • One prediction bit is used if the last branch executed was not-taken.
  • The other prediction bit is used if the last branch executed was taken.

• Denoted as: (New prediction when last NT / New prediction when last T).

  • E.g., T/NT stands for: New prediction is TAKEN if previous was NOT-TAKEN, and is NOT-TAKEN if previous was TAKEN.

• In an (m,n) predictor, the global history of the most recent m branches is recorded in an m-bit shift register.

• Each bit records whether the branch was taken or not taken.

• The branch-prediction buffers are indexed using concatenation of low-order bits from branch-address with m-bit global history.

(2, 2) Correlating Branches Predictor:

• The buffer is drawn as a 2-dimensional object; each buffer is 2 bits wide. In reality, they are arranged linearly.
• A (2, 2) branch prediction buffer uses 2-bit global history to choose from among 4 predictors for each branch address of 4-bit (among the 16 entries in each of the 4 predictors).
• Behavior of recent branches selects between four predictions of the next branch, updating just that prediction.
• Indexing is done by concatenation of 4 lower-order address bits of the branch (word address) and 2 global bits to form a 6-bit address to select a 2-bit prediction from 64 entries in 4 buffers, each of 16 entries.

Comparison of (0,2) and (2,2) predictors — The (2,2) predictor shows higher prediction accuracy (e.g., 99.7% for eqntott benchmark vs. 96.5% for (0,2)), demonstrating that correlating predictors perform better than non-correlating ones.

Multilevel Branch Predictors (Tournament Predictors)

• Multilevel branch prediction (nested branches) involves information at local and global levels to predict correctly.
• It uses several levels of Branch-Prediction Tables and an algorithm to choose among different predictors.

🔑 Definition — Tournament Predictor: A multilevel branch predictor that uses a selector (often a 2-bit saturating counter) to choose between two or more different predictors (e.g., a global predictor and a local predictor) based on which one has been more accurate recently.

State Transition Diagram of Tournament Predictor

• The transition for the predicted predictor is specified by:
  • Correct = 1
  • Incorrect = 0
• The state transition diagram shows that from the saturating state:
  • The counter is incremented whenever the predicted predictor is correct and the other is incorrect (i.e., for 1/0).
  • The counter is decremented in the reverse direction (i.e., for 0/1).
• The counter does not change for all other predictions for non-saturating present state.
• For the saturating state 00 (Use predictor 1):
  • It increments to state 01 (use predictor 1) for 1/0.
  • It decrements to state 11 (use predictor 2) for 0/1.
• For the saturating state 11 (Use predictor 2):
  • It increments to state 00 (use predictor 1) for 1/0.
  • It decrements to state 10 (use predictor 2) for 0/1.

💡 Why this matters: Tournament predictors can achieve higher prediction accuracy by dynamically selecting the best predictor based on recent behavior, reducing misprediction penalties.

High Performance Instruction Delivery

• In the MIPS 5-stage pipeline, we need to know the address of the next instruction fetch at the end of the current IF cycle.
• For zero branch penalty, we need to know whether the as-yet undecoded instruction is a branch, and if yes, then what is the next-PC.

Branch Target Buffer

• This is accomplished by introducing a Cache that contains the address of the next instruction if a branch is taken, as well as not-taken.
• This cache is known as the Branch-Target Cache or Branch-Target Buffer (BTB).

Branch-Prediction Buffer vs. Branch-Target Buffer

• Recall that a branch-prediction buffer is accessed during the ID stage, after instruction decode.
• We know the branch-target address at the end of the ID stage to fetch the next predicted instruction.

Branch Target Buffer

• The BTB has three fields:
  1. Lookup: addresses of the known branch instructions (predicted as taken).
  2. Predicted PC: PC of the fetched instruction predicted taken-branch.
  3. Prediction State: Optional extra prediction state bits.

Complications:

• Complications arise in using a 2-bit predictor because it uses information for both the branches taken and not-taken.
• This complication is resolved in PowerPC processors by using both the Target-buffer and Prediction-buffer.

Steps involved in using Branch Target Buffer at IF, ID, and EXE pipeline stages:

1. IF Stage
2. ID Stage
3. EXE Stage

Branch-Target Buffer – Flow Chart Explanation

IF Stage:

• The PC of an instruction is compared with the contents of the buffer.
• If it is found, then the instruction must be a branch instruction predicted taken.
• Else, it may be a branch predicted not-taken or a normal instruction.

ID Stage:

1. Decode the instruction. If, in the IF Stage, an entry was found in the Target-buffer as predicted-branch, then begin fetching immediately from the predicted PC.
2. Check the decoded instruction. If it is a Taken-branch...

EX Stage performs one of four possible functions:

i. Where in the IF stage, entry was not found in the target buffer, and in the ID stage:

• If it is found to be Taken-branch:
  • (i-a) Enter branch-instruction address and next PC into branch-target buffer.
• Else:
  • (i-b) Proceed as normal instruction execution.

ii. Where in the IF stage, the entry was found in the target-buffer, and in the ID stage:

• If it is found to be Taken-branch:

  • (ii-a) Correctly predicted, so execute normally without stall.

• Else:

  • (ii-b) It is mispredicted, so kill the fetched instruction, restart fetching at another address, and delete the entry from the target-buffer.

• If the correctly predicted branch entry is found in the buffer, there will be no branch penalty.

• Else, it suffers at least 2 clock cycle delay as a misprediction penalty:

  • One clock delay for fetching the wrong instruction.
  • One clock cycle to restart the fetch.

Branch-Target Buffer – Examples

Branch-Target Buffer – Solution We can compute the penalty by looking at the probability of two events:

• i) Branch predicted taken but ends up not taken: = % buffer hit rate × % incorrect prediction = 0.95 × 0.1 = 0.095
• ii) Branch is taken but is not found in the buffer: = % incorrect prediction = 0.1

The penalty in both cases is 2 cycles, therefore: Branch Penalty = (0.095 + 0.1) × 2 = 0.195 × 2 = 0.39

Example: Branch-Target Buffer Problem: Consider a branch-target buffer implemented for conditional branches only for a pipelined processor.

Assuming that:

• Misprediction penalty = 4 cycles
• Buffer miss-penalty = 3 cycles
• Hit rate and accuracy each = 90%
• Branch Frequency = 15%

Solution: The speedup with Branch Target Buffer versus no BTB is expressed as: Speedup = CPI_no_BTB / CPI_BTB = (CPI_base + Stalls_no_BTB) / (CPI_base + Stalls_BTB)

The stalls are determined as: Stalls = Σ (Frequency_s × Penalty_s) for all s in stall cases.

The sum over all the stall cases as the product of frequency of the stall cases and the stall-penalty:

i. Stalls_no_BTB = 0.15 × 2 = 0.30

ii. To find Stalls_BTB, we consider each output from BTB. There exist three possibilities:

a) Branch misses the BTB:

• Frequency = 15% × 0.1 = 1.5% = 0.015
• Penalty = 3
• Stalls = 0.045

b) Branch can hit and correctly predicted:

• Frequency = 15% × 0.9 (hit) × 0.9 (prediction) = 12.1% = 0.121
• Penalty = 0
• Stalls = 0

c) Branch can hit but incorrectly predicted:

• Frequency = 15% × 0.9 (hit) × 0.1 (misprediction) = 1.3% = 0.013
• Penalty = 4
• Stalls = 0.052

Stalls_BTB = 0.045 + 0 + 0.052 = 0.097

Speedup = (CPI_base + Stalls_no_BTB) / (CPI_base + Stalls_BTB) = (1.0 + 0.3) / (1.0 + 0.097) = 1.3 / 1.097 = 1.2

Improvement in BTB

• To achieve more instruction delivery, one possible variation in the Branch Target Buffer is:
• To store one or more target instructions, instead of, or in addition to, the predicted Target Address.

Advantages:

• It possibly allows a larger BTB as it permits access to take longer than the time between successive instruction fetches.
• Buffering the actual Target-Instructions allows Branch Folding, i.e., ZERO cycle Unconditional Branching or sometimes ZERO cycle conditional branching.

⭐ Key Takeaways

Correlating branch predictors use history of recent branches to improve accuracy, with (m,n) notation indicating how many past branches are recorded and how many bits per predictor. Tournament predictors dynamically select between multiple predictors using a saturating counter, achieving superior accuracy. The Branch Target Buffer (BTB) caches branch targets to enable zero-cycle branch prediction when hits occur, but mispredictions or misses incur penalties (typically 2-4 cycles). The performance benefit of BTB can be quantified through speedup calculations considering hit rates, accuracy, and branch frequencies, with branch folding offering potential for zero-cycle branching.

🧠 Quick Revision Questions

1. What does the notation (m, n) mean in correlating branch predictors, and how does a (2,2) predictor differ from a (0,2) predictor?
2. How does a tournament predictor decide which predictor to use, and what is the role of the saturating counter in its state transition?
3. What are the three fields in a Branch Target Buffer, and what are the penalty cycles for the four possible BTB scenarios?
4. Calculate the branch penalty given a 90% hit rate, 90% accuracy, 3-cycle miss penalty, and 4-cycle misprediction penalty with 15% branch frequency.
5. What is branch folding, and what advantage does storing target instructions instead of target addresses provide in BTB design?

📘 Lecture 17 — Instruction Level Parallelism (High-performance Instructions delivery - Multiple Issue)

📖 Overview: This lecture explores advanced techniques for delivering instructions to high-performance processors, focusing on integrated branch prediction and multiple instruction issue mechanisms. It explains how modern processors overcome the limitations of single-issue pipelines through superscalar and VLIW architectures, with detailed analysis of Tomasulo's algorithm extended for dual-issue execution.

🗂️ Topics Covered

The lecture covers branch penalty reduction through Branch Target Buffer, Integrated Instruction Fetch Units, and Return Address Predictors. It then introduces multiple instruction-issue processors, comparing superscalar and VLIW approaches. The statically scheduled superscalar MIPS processor is examined with an example pipeline, followed by dynamic scheduling in superscalar processors using extended Tomasulo's concept. Two detailed examples demonstrate dual-issue execution loops with resource usage tables and performance metrics.

📝 Lecture Summary

Reducing branch penalties for High-Performance Processors

Control hazards limit instruction throughput in pipelined processors. Three key hardware techniques reduce branch penalties: Branch Target Buffer stores previously taken branch addresses; Integrated Instruction Fetch Units combine branch prediction with instruction prefetch; and Return Address Predictors handle indirect jumps from procedure calls and select statements.

🔑 Definition — Branch Target Buffer (BTB): A hardware structure that caches the target address of previously taken branches to predict the next instruction address. 📐 Formula: No explicit formula — BTB operates as a cache lookup. 📌 Example: When a branch instruction is fetched, the BTB is checked; if a match is found (hit), the stored target address is used as the next PC, avoiding pipeline bubbles.

Integrated Instruction Fetch Units (IIFU)

The IIFU integrates three critical functions for high-performance instruction delivery. Integrated Branch Prediction places the predictor inside the fetch unit to drive the fetch pipeline proactively. Instruction Prefetch maintains a queue holding multiple instructions, enabling delivery of more than one instruction per cycle. Instruction memory access and buffering handles the complexity of fetching across multiple cache lines and hides the cost of crossing block boundaries.

💡 Why this matters: IIFUs are essential for superscalar processors that must deliver multiple instructions per cycle, as they prevent the fetch stage from becoming a bottleneck.

🔑 Definition — Instruction Prefetch Queue: A buffer within the IIFU that holds fetched instructions before they are issued, enabling multiple instructions to be delivered in one clock cycle. 📐 Formula: No formula — queue depth determines lookahead capability. 📌 Example: In a 2-issue processor, the IIFU fetches 64 bits per clock cycle (two 32-bit MIPS instructions), buffering them for simultaneous issue to functional units.

Return Address Predictors

Return Address Predictors specialize in predicting indirect jumps whose target addresses vary at runtime. These are generated by high-level language constructs such as indirect procedure calls and switch/case statements. The predictor typically uses a hardware stack that stores return addresses when CALL instructions execute.

🔑 Definition — Return Address Stack: A specialized hardware structure that pushes the return address on each procedure call and pops it on return, achieving near-perfect prediction for nested procedure calls. 📌 Example: In a recursive function call, each JAL instruction pushes the return address onto the hardware stack; subsequent JR instructions pop the correct address, avoiding pipeline stalls.

Multiple Instruction-Issue Processors

All previously described single-issue pipelines achieve at most 1 instruction per cycle (IPC). To exceed this limit, two approaches exist: Superscalar processors and Very Long Instruction Word (VLIW) processors. Superscalar processors execute multiple instructions per cycle using hardware dynamic scheduling, while VLIW processors rely on the compiler to pack independent operations into wide instruction words.

🔑 Definition — Superscalar Processor: A processor that can issue multiple independent instructions from a conventional instruction stream in each cycle, using hardware to detect and resolve dependencies. 📐 Formula: IPC = Instructions Executed / Cycles Taken → For a 2-issue superscalar, theoretical maximum IPC = 2. 📌 Example: IBM Power2, Sun Ultra SPARC, Pentium III/4, DEC Alpha, and HP 8000 all implement superscalar execution.

VLIW Processors

Very Long Instruction Word (VLIW) processors bundle multiple independent operations into a single long instruction word. They incorporate advanced features like predication, rotating registers, and speculation to expose instruction-level parallelism. Typical implementations include Intel i860, Trimedia, and Itanium.

🔑 Definition — Predication: A technique where instructions are conditionally executed based on a predicate flag, eliminating branches and reducing control hazards. 📐 Formula: No formula — predication uses conditional execution bits within each VLIW instruction. 📌 Example: A VLIW instruction r1 = L r4; r2 = Add r1,M; f1 = Mul f1,f2; r5 = Add r5,4 executes four independent operations simultaneously in one cycle.

Statically Scheduled Superscalar MIPS Processor

As an example, consider a MIPS superscalar that issues 2 instructions per cycle: one FP operation and one Integer operation (load/store to integer/FP register, branch, or integer ALU). This requires fetching and decoding 64 bits per clock cycle. Hazard detection is simplified by the restriction that only one FP and one integer instruction can issue per packet.

🔑 Definition — Issue Packet: The group of instructions fetched simultaneously that could potentially issue in the same clock cycle, ranging from 1 to 4 instructions. 📌 Example: If the issue packet contains ADD.D F4,F0,F2 and S.D F4,0(R1), a RAW hazard exists because the store depends on the add. The simple solution is to issue only one instruction, treating it as a structural hazard.

The issue process follows three steps:

1. Fetch two instructions from the cache
2. Determine whether 0, 1, or 2 instructions can issue
3. Issue them to the correct functional units

Dynamic Scheduling in Superscalar Processors

Extending Tomasulo's algorithm to support dual-issue requires careful handling. Instructions should not be issued to reservation stations out of order to avoid violating program semantics. Two approaches enable simultaneous issue: running the reservation station assignment in half a clock cycle, or building logic to handle two instructions with dependencies. Modern processors issue 4+ instructions per cycle by combining both approaches with hardware-based speculation.

Example 1: Dual-Issue Tomasulo Loop Execution

Consider the loop adding scalar F2 to array elements (from Lecture 16):

Loop: L.D  F0,0(R1)   ; F0=array element
      ADD.D F4,F0,F2  ; add scalar in F2
      S.D  F4,0(R1)   ; store result
      DADDUI R1,R1,#-8 ; decrement pointer
      BNE  R1,R2,LOOP ; branch R1!=R2

Using a 2-issue Tomasulo pipeline:

• Both FP and integer operations can issue every clock cycle
• One integer ALU for ALU+address calculation; separate FP functional units
• Issue=1 cycle, Write result=1 cycle
• Latencies: Integer ALU=1 cycle, Load=2 cycles, FP add=3 cycles

💡 Why this matters: The dual-issue pipeline achieves an IPC of 5/3 ≈ 1.67 (5 instructions in 3 clocks per iteration), significantly better than single-issue.

📌 Example: The resource usage table shows:

• Clock 1: L.D and DADDUI issue simultaneously
• Clock 2: ADD.D and BNE issue; L.D executes
• Clock 3: S.D issues; ADD.D executes
• Completion rate = 15/16 = 0.94 (15 instructions execute in 16 cycles)

Example 2: Overcoming Single Integer Pipe Bottleneck

With a wider CDB (2 CDBs) and separate functional units for Integer ALU and effective address calculation, the same loop executes more efficiently. This configuration eliminates the bottleneck caused by a single integer unit sharing both ALU and address computation.

📌 Example: The activity table for Example 2 shows improved resource utilization where integer ALU operations and effective address calculations proceed in parallel, reducing the total execution time for the loop.

⭐ Key Takeaways

Integrated Instruction Fetch Units combine branch prediction, prefetch queues, and memory access buffering to deliver multiple instructions per cycle while hiding cache block crossing penalties. Superscalar processors achieve higher IPC through hardware dynamic scheduling, with dual-issue Tomasulo pipelines achieving 1.67 instructions per cycle for typical loops. VLIW processors shift complexity to the compiler, bundling independent operations into wide instruction words with features like predication and speculation. The key performance gains come from separating functional units (integer ALU vs. address calculation) and widening CDB bandwidth to handle multiple results per cycle. Hardware-based speculation integrates branch prediction into dynamic scheduling pipelines, enabling sustained instruction throughput beyond single-issue limits.

🧠 Quick Revision Questions

1. What are the three main hardware techniques for reducing branch penalties in high-performance processors?
2. Explain the three integrated functions of an IIFU and how they collectively improve instruction delivery.
3. How does a Return Address Stack predict indirect jumps, and what type of program constructs generate these jumps?
4. Compare the key differences in instruction scheduling between superscalar and VLIW processors.
5. In the dual-issue Tomasulo example, what causes the completion rate of 0.94 (15/16), and how does wider CDB improve this?

📘 Lecture 18 — Instruction Level Parallelism (Hardware-based speculations and exceptions)

📖 Overview: This lecture focuses on hardware-based speculation as a technique to overcome control hazards and improve instruction-level parallelism. It explains how extending Tomasulo’s algorithm with a Reorder Buffer (ROB) allows speculative execution, in-order commitment, and proper handling of exceptions. This is critical for modern superscalar processors to achieve higher performance by executing instructions before branch outcomes are known.

🗂️ Topics Covered

The lecture begins with a recap of branch target buffers, integrated instruction fetch units, return address predictors, and superscalar/VLIW processors. The main focus is on introducing hardware-based speculation, explaining how it combines dynamic branch prediction, speculation, and dynamic scheduling. The implementation details focus on the Reorder Buffer (ROB) and its fields, the extended Tomasulo’s algorithm with four steps (Issue, Execute, Write Result, Commit), and two detailed examples showing status tables for speculative vs. non-speculative execution. The topic of handling exceptions in speculative hardware is also discussed, including how interrupts and mispredictions are managed.

📝 Lecture Summary

Hardware-based Speculation: Introduction

Hardware-based speculation offers many advantages. It can incorporate hardware-based branch prediction, does not require additional bookkeeping code, and does not depend on a compiler. This approach has been implemented in processors like the PowerPC 620, MIPS R10000, Intel P6, and AMD K5.

Hardware Based Speculation: Basics

Exploiting more instruction-level parallelism increases the burden of maintaining control dependence. While branch prediction reduces direct stalls, a multiple-issue processor may need to execute a branch every clock cycle. Hence, overcoming control dependence limitations requires speculation on the outcome of branches and executing the program for speculations. This means we fetch, issue, and execute instructions as if our branch predictions were always correct. Dynamic scheduling without speculation fetches and issues instructions but does not execute them until the prediction is checked.

Hardware Support: Speculative Execution

The main idea is to allow execution of an instruction dependent on a predicted-taken branch such that there are no consequences (including exceptions like memory violation) if the branch is not actually taken. This is achieved if hardware support for speculation buffers the results and exceptions from instructions until it is known that the instruction would execute.

Hardware Based Speculation: Basics

Hardware-based speculation combines three key ideas:

1. Dynamic Branch Prediction: Facilitates choosing which instruction to execute (next in sequence or branch).
2. Speculation: Allows execution of instructions before the control dependence is resolved. The hardware must have the ability to undo the instructions if there are exceptions.
3. Dynamic scheduling: Deals with scheduling different combinations of basic blocks.

Thus, the hardware-based speculation follows the predicted flow of data values to choose when to execute. To do this, we must separate the bypassing of results among instructions from the actual completion of an instruction. By making this separation, we can allow an instruction to execute and bypass its result to other instructions without allowing it to perform any update that cannot be undone, until we know it is no longer speculative. When the instruction is no longer speculative, we allow it to update the register file or memory. This additional step in the instruction execution sequence is called instruction commit. The basic idea is to allow instructions to execute out-of-order but force them to commit in-order.

💡 Why this matters: This separation is the core mechanism that makes speculation safe, preventing incorrect results from speculative code from corrupting the architectural state.

Hardware Based Speculation: Implementation

In a single-issue five-stage pipeline, we can ensure in-order commitment by moving writes to the end of the pipeline. When adding speculation, we need to separate the process of completing execution and instruction-commit, as instructions may finish execution considerably before they are ready to commit. Adding this commit phase requires changes to the sequence and an additional set of hardware buffers (the Reorder Buffer) that holds the result of instructions that have finished execution but have not committed.

Modified hardware including ROB

The figure (provided in the text) shows the modified hardware. Here, the Reorder Buffer (ROB) can be an operand source if the value is not yet committed. Once an operand commits, the result is found in the register file.

Mechanism

• At issue time, allocate an entry in the ROB to hold the result.
• Use the ROB entry number instead of a reservation station to rename registers.
• However, we can use additional registers for renaming, and the ROB only for tracking commits.
• Instruction results commit to the register set in-order.
• If the ROB is implemented as a queue, it is simple to undo speculated instructions on mispredicted branches or on exceptions; it just requires throwing away uncommitted entries.

Extended Tomasulo’s Pipe

Exceptions are not recognized until an instruction becomes ready to commit. The figure shows the Tomasulo's hardware structure including the ROB for a MIPS FP unit, which is extended to handle speculation. The ROB provides additional buffer, in the same way as reservation stations in Tomasulo's, that extends the register set. The ROB holds the result of an instruction between the time the operation completes and the time the instruction commits. The ROB is a source of operands for instructions, just as reservation stations provided operands in Tomasulo's algorithm.

🔑 Definition — Reorder Buffer (ROB): A hardware buffer that holds the results and exceptions from instructions until it is known that the instruction will commit. It allows for in-order commitment while allowing out-of-order execution.

ROB consists of four fields

1. Instruction Type field: Indicates whether the instruction is a branch (no destination), a store (memory address destination), or a register operation (ALU or load, with register destination).
2. Destination field: Supplies the register number (for load and ALU operations) or the memory address (for stores) where the instruction result should be written.
3. Value field: Used to hold the value of the instruction result until the instruction commits.
4. Ready field: Indicates that the instruction has completed execution and the value is ready.

Speculative Tomasulo’s Algorithm

There are four steps:

1. Issue: Get instruction from the head of the instruction queue. If a reservation station and ROB slot are free, allocate and issue the instruction. If operands are available, send them to the reservation station; otherwise, keep track of the ROB entry that will produce the operands.
2. Execute: Operate on operands. If both operands are ready, execute. If not ready, watch the CDB for the result. This checks for RAW hazards. Instructions may take multiple clock cycles here.
3. Write result: Finish execution (WB). Write on the Common Data Bus (CDB), mark the reservation station available. The result is picked up by the ROB entry. For a store, if the value to be stored is available, it is written to the value field of the ROB entry; if not, the CDB is monitored until the value is broadcast.
4. Commit: This can occur when an instruction reaches the head of the ROB and its result is present in the buffer. The commit updates the register or stores to memory with the ROB result and frees the ROB slot. If the ROB head is an incorrectly predicted branch, the ROB is flushed. If the branch was correctly predicted, the branch is finished.

Example 1

Using the same code segment as in the Tomasulo's approach, the status table is shown when the MUL.D is ready to go to commit. The latencies are: add=2, multiply=10, divide=40 clock cycles. The code is:

• L.D F6,34(R2)
• L.D F2,45(R3)
• MUL.D F0,F2,F4
• SUB.D F8,F6,F2
• DIV.D F10,F0,F6
• ADD.D F6,F8,F2

The table shows that although SUB.D has completed execution, it does not commit until MUL.D commits. The reservation station and register status fields contain the same basic information as for Tomasulo's algorithm. At the time MUL.D is ready to execute, only two L.D instructions have committed. SUB.D and ADD.D will not commit until MUL.D commits. DIV.D is in execution but has not completed due to its longer latency.

Comparing with the non-speculation table, in the non-speculation case, ADD.D and SUB.D completed out-of-order (before MUL.D). In the speculative hardware: the reservation station numbers are replaced with ROB entry numbers in Qj, Qk, and in register status fields, and a destination field is added to the reservation station designating the ROB number that is the destination for the result.

📌 Example: The specific code and resulting status table (from the lecture text) demonstrates that in speculation, SUB.D and ADD.D are not allowed to commit (update registers) until MUL.D commits, even though their execution is complete. This preserves the original program order.

Multiple issue with speculation

A speculative processor can be extended to multiple issue. The two challenges are:

1. Instruction issue and monitoring the CDBs for instruction completion.
2. Maintaining throughput of greater than one instruction per cycle.

Example: Loop Execution with and without Speculation

Consider the loop:

Loop: 
  LD    R2,0(R1)    ; R2= array element
  DADDUI R2,R2,#1  ; increment R2
  SD    R2,0(R1)   ; store result
  DADDUI R1,R1,#4  ; increment pointer
  BNE   R2,R3,LOOP ; branch if not last element

• Without speculation: The LD following BNE cannot start execution earlier because it must wait until the branch outcome is determined.
• With speculation: The LD following BNE can start execution early because it is speculative. Comparing the two tables, the third branch in the speculative processor executes in 13 clock cycles, while in the non-speculative processor it executes in 19 clock cycles. The non-speculative pipeline falls behind the issue rate rapidly.

Exceptions to Hardware-based speculation

In the Tomasulo structure with hardware-based speculation, if an exceptional situation occurs while executing an instruction, the ROB doesn't commit and handles exceptions. For example, if MUL.D causes an interrupt, we can wait until this interrupt reaches the head of the ROB, any pending instruction is flushed out, and the speculation is un-done. In the case of dynamic scheduling without speculation, the results in registers F8 (for SUB.D) and F6 (for ADD.D) could be overwritten out-of-order, and the interrupt could not be handled.

Furthermore, exceptions are handled by not recognizing them until the instruction is ready to commit. For example, in a loop, if an exception arises from MUL.D, it is recorded in the ROB. If a misprediction also arises from a speculated BNE, the exception is flushed out along with the speculated instruction when the ROB is cleared.

⭐ Key Takeaways

The most critical idea from this lecture is that hardware-based speculation, implemented through an extended Tomasulo's algorithm with a Reorder Buffer (ROB), allows a processor to execute instructions out-of-order and speculatively (based on branch prediction) while maintaining precise exceptions and in-order commitment. This solves the control hazard problem more aggressively than simple branch prediction because the ROB buffers results until the branch is resolved, allowing execution to proceed without stalling. The key difference from non-speculative dynamic scheduling is the separation of execution from commitment, where the ROB holds all uncommitted results and is flushed on a misprediction. Finally, handling exceptions requires waiting until the faulting instruction reaches the head of the ROB to ensure all previous instructions have committed correctly, and a misprediction can flush a pending exception, which is correct because the faulty instruction should not have been executed.

🧠 Quick Revision Questions

1. What are the three key ideas combined in hardware-based speculation?
2. What is the purpose of the Reorder Buffer (ROB), and what are its four fields?
3. Describe the four steps of the speculative Tomasulo's algorithm (Issue, Execute, Write Result, Commit).
4. In the Example 1 status table, why do SUB.D and ADD.D not commit until after MUL.D commits, even though they have finished executing?
5. How are exceptions and branch mispredictions handled in a processor with hardware-based speculation, and what happens to the ROB?

📘 Lecture 19 — Instruction Level Parallelism (Limitations of ILP and Conclusion)

📖 Overview: This lecture concludes the discussion on dynamic scheduling techniques for Instruction Level Parallelism by introducing an ideal processor model to study the limitations of ILP. It examines how window size, branch prediction accuracy, and finite registers constrain realizable processor performance, and concludes with an analysis of the Intel P6 micro-architecture and its evolution into the NetBurst architecture of the Pentium 4.

🗂️ Topics Covered

Recap of ILP dynamic scheduling concepts including scoreboarding, Tomasulo's algorithm, branch prediction, and multiple instruction issue. Introduction of an ideal processor model to study ILP limitations. Analysis of performance limiting factors including window size and issue count, branch/jump prediction, and finite registers. Examination of performance data from the Alpha 21264 processor using SPEC92 benchmarks. Discussion of Intel P6 micro-architecture implementation in Pentium Pro, Pentium II, and Pentium III, followed by comparison with Pentium 4's NetBurst architecture.

📝 Lecture Summary

Recap: ILP-Dynamic Scheduling

The last few lectures covered hardware methods for instruction level parallelism to execute multiple instructions in pipelined datapaths, referred to as dynamic scheduling techniques. These techniques avoid structural, data, and control hazards while minimizing stalls. The scoreboarding and Tomasulo's algorithm were discussed as basic concepts for dynamic scheduling in integer and floating-point datapaths, facilitating out-of-order execution to minimize data dependencies. Branch-prediction techniques and different types of branch predictors were also covered to reduce stalls due to control hazards. The concept of multiple instruction issue was discussed to reduce CPI to less than one. Extensions to Tomasulo's structure by including hardware-based speculation allow speculation that branches are correctly predicted, enabling out-of-order execution but in-order commit after confirming speculation is correct and no exceptions exist.

Limitations of the ILP – Ideal Processor

To understand ILP limitations, an ideal processor is defined as one without artificial constraints on ILP, where the only limits are those imposed by actual data flows through registers or memory. In an ideal processor, all control dependencies and all but true data dependencies are eliminated. Control dependencies are eliminated by assuming perfect branch and jump predictions (all conditional branches and jumps predicted exactly) with perfect speculation and an unbounded instruction buffer. All but true data dependencies are eliminated by assuming infinite virtual registers (facilitating register renaming to avoid WAW and WAR hazards and simultaneous execution of unlimited instructions) and that all memory addresses are known exactly (allowing loads to move before stores if addresses differ).

🔑 Definition — Ideal Processor: A processor without artificial constraints on ILP, where the only limits are those imposed by actual data flows through registers or memory.

Ideal hardware model

By combining these assumptions, in an ideal processor: unlimited instructions (including loads and stores) can issue in one cycle; all functional units have latencies of one cycle so dependent instructions can issue on successive cycles; any instruction in program execution can be scheduled on the cycle immediately following execution of its predecessors; and the last dynamically executed instruction can be scheduled on the very first cycle.

Performance of a Nearly Ideal Processor

The ILP in the Alpha 21264 superscalar processor is examined. Alpha 21264 features: issues up to 4 instructions/cycle, initiates execution on up to 6 instructions, supports large renaming registers (41-integer and 41 floating-point), and uses a large tournament type predictor. Six SPEC92 benchmarks were compiled on a MIPS optimizing compiler. Three floating-point benchmarks are: Fpppp, Doduc, Tomcatv. Three integer programs are: gcc, espresso, li.

The results show that fpppp and tomcatv have extensive parallelism with high instruction-issues, while doduc parallelism doesn't occur in simple loops. The integer program li, a LISP interpreter with many short dependences, offers the lowest parallelism.

The important parameters that limit ILP are: Window Size and Issue Count, Branch and Jump predictors, and Finite number of registers.

Window size and Issue count

In dynamic scheduling, every pending instruction must look at every completing instruction for its operands. A window in an ILP processor is defined as "a set of instructions which is examined for simultaneous execution." The start of the window is the earliest uncompleted instruction and the last instruction determines its size. Since each instruction in the window must be kept in the processor until execution completion, total window size is limited by storage, number of comparisons, and issue rate.

📐 Formula: Required comparisons per clock cycle = maximum completion rate × window size × number of operands per instruction

📌 Example: If maximum completion rate = 6 IPC, window size = 80 instructions, number of operands per instruction = 2 operands, then maximum comparisons required = 6 × 80 × 2 = 960 comparisons per cycle.

In real processors, the maximum number of instructions that may issue, execute, and commit in the same clock cycle is smaller than the window size. The amount of parallelism uncovered falls sharply with decreasing window size. For benchmark gcc, when window size decreases from 2K to 512, parallelism falls from 35 to 10 IPC, and parallelism reduces to almost zero when window size is 4. Parallelism in integer and FP programs is almost similar for a specific window size.

Branch and jump prediction

The ideal processor assumes perfect branch prediction, but no real processor achieves this. The graph shows five different levels of predictions: Perfect prediction (highest parallelism), Tournament based branch predictor (uses 2-bit correlating and 2-bit non-correlating predictor with a selector; predictor buffer consists of 8K entries each with three 2-bit fields = 48K bits; achieves average accuracy of 97% of six SPEC92 benchmarks), Standard 2-bit predictor with 512 2-bit entries, Profile history of the program, and None (no branch prediction - parallelism limited to within a basic block).

The graph shows extensive difference between programs with loop-level parallelism (tomcatv and fpppp) and those without (integer programs and doduc).

The effect of finite registers

Another important limiting factor is finite registers. The ideal processor eliminates all name dependences assuming infinite physical registers. The Alpha 21264 provides 41 integer and 41 FP extended registers, plus 32 integer and 32 FP architected registers. Having only 32 extra FP and 32 extra GP registers has significant impact on all programs, but the effect is most dramatic on FP programs (fpppp and tomcatv) - instruction-issues increase from 10 to 45 IPC when registers increase from 32 to 128. The reduction in available parallelism is significant when fewer than an unbounded number of renaming registers (less than 32) are available. For integer programs, the impact of having more than 64 registers is not seen due to limitation in window size.

Performance of realizable processors with realistic hardware

A processor with these attributes is considered: up to 64 instructions per clock with no issue restriction, tournament predictor with 1K entries return predictors, perfect memory references done dynamically or through memory dependence predictors, and register renaming with 64 additional integer and 64 additional FP registers. This configuration is more complex and expensive than existing implementations. The results show that the effect of window size for integer programs is not as severe as for FP programs.

Putting it all together

The Intel P6 micro-architecture forms the basis for Pentium Pro, Pentium II, and Pentium III. These processors differ in clock rate, cache architecture, and memory interface. Pentium Pro integrated processor and specialized cache SRAMs into a multichip module. Pentium II uses standard SRAMs as caches. Pentium III has either on-chip 256KB L2 cache or off-chip 512KB cache. The P6 micro-architecture is a dynamically scheduled processor that translates each IA-32 instruction to a series of micro-operations (uops) executed by the pipeline. The maximum number of uops generated per clock cycle is six, with four allocated to the first IA-32 instructions. Uops are executed by an out-of-order speculative pipeline using register renaming and a ROB (Reorder Buffer).

Performance of the Pentium pro implementation

Pentium Pro has the smallest set of primary caches among P6-based microprocessors but has high bandwidth interface to secondary caches.

Branch performance and speculation costs

Branch target addresses are predicted with a 512 entry BTB (Branch Target Buffer). If the BTB does not hit, a static prediction is used. Backward branches are predicted taken (one cycle penalty if correctly predicted). Forward branches are predicted not taken (no penalty if correctly predicted). Branch mispredicts have a direct performance penalty between 10 and 15 cycles, plus indirect penalty from incorrectly speculated instructions. On average, about 20% of branches either miss or are mispredicted and use the simple static predictor rule.

Overall Performance of P6 Pipeline

Overall performance depends on the rate at which instructions complete and commit. On average, one uop commits per cycle. 23% of the time, three uops commit in a cycle. This demonstrates the ability of a dynamically scheduled pipeline to fall behind (55% of cycles, no uops commit) and later catch up (31% of cycles have two or three uops committing).

The Pentium III versus Pentium 4

The Pentium 4 micro-architecture, called NetBurst, is similar to Pentium III's P6 micro-architecture. Both fetch up to three IA-32 instructions per cycle, decode them into micro-ops, and send uops to an out-of-order execution engine executing up to three uops per cycle. However, NetBurst has many differences allowing significantly higher clock rates while maintaining peak to sustained execution throughput.

Differences in Pentium III versus Pentium 4

1. NetBurst has a much deeper pipeline - P6 requires about 10 clock cycles for a simple add instruction from fetch to result availability; NetBurst takes about 20 clock cycles including 2 cycles reserved to drive results across the chip.

2. NetBurst uses register renaming (as in MIPS R10K and Alpha 21264) rather than the reorder buffer used in P6. Register renaming allows up to 128 outstanding results versus 40 permitted in P6.

3. Seven integer execution units in NetBurst versus five in P6, including an additional integer ALU and additional address computation unit. An aggressive ALU operating at twice the clock rate and aggressive data cache lead to lower latencies - basic ALU operations effectively one-half clock cycle in NetBurst versus one in P6; data loads effectively two cycles in NetBurst versus three in P6. These high-speed functional units are critical to lowering potential increase in stalls from the very deep pipeline.

4. NetBurst uses sophisticated trace cache to improve instruction fetch performance, while P6 uses conventional prefetch buffer and instruction cache.

5. NetBurst has a BTB eight times larger with an improved prediction algorithm.

6. NetBurst has 8KB Level-1 data cache compared to P6's 16KB Level-1 data cache, but NetBurst has larger Level-2 cache (256KB) with higher bandwidth.

7. NetBurst implements new SSE2 FP instructions allowing two FP operations per instruction, structured as 12-bit SIMD or short-vector structure, giving Pentium 4 considerable advantage over Pentium III on FP code.

💡 Why this matters: The trade-offs between pipeline depth, cache size, and execution unit count demonstrate how processor designers balance competing constraints to achieve higher clock rates while maintaining performance throughput.

⭐ Key Takeaways

An ideal processor removes all artificial constraints on ILP, but real processors are fundamentally limited by window size, branch prediction accuracy, and finite registers. The number of comparisons required for dynamic scheduling grows as the product of completion rate, window size, and operands per instruction, creating a practical upper bound on window size. Reducing window size from 2K to 512 can drop parallelism from 35 to 10 IPC for integer programs. Finite registers have the most dramatic effect on floating-point programs, where increasing from 32 to 128 renaming registers can boost IPC from 10 to 45. The Intel P6 micro-architecture demonstrates how these concepts are implemented in real processors, while NetBurst shows that deeper pipelines, register renaming instead of ROB, trace caches, and faster ALUs allow higher clock rates but require careful trade-offs to maintain sustained throughput.

🧠 Quick Revision Questions

1. What are the four assumptions of an ideal processor for studying ILP limitations?
2. What is the formula for calculating comparisons required per clock cycle in a window-based dynamic scheduling processor?
3. How does reducing window size from 2K to 512 affect IPC for the gcc benchmark?
4. What accuracy does the tournament-based branch predictor achieve on SPEC92 benchmarks, and how many bits does its predictor buffer contain?
5. List four key differences between the P6 micro-architecture (Pentium III) and the NetBurst micro-architecture (Pentium 4).

📘 Lecture 20 — Instruction Level Parallelism (Static Scheduling)

📖 Overview: This lecture transitions from hardware-based dynamic scheduling to software-based static scheduling techniques for exploiting Instruction Level Parallelism (ILP). It covers basic compiler scheduling, loop unrolling and scheduling, and static branch prediction, explaining how these methods reduce data and control hazards to improve pipeline performance.

🗂️ Topics Covered

This lecture begins with a recap of dynamic scheduling techniques studied in previous lectures, then introduces static scheduling as a software approach to exploit ILP. It covers basic compiler pipeline scheduling to reduce data hazard stalls, explains loop unrolling with and without scheduling using a vector addition example, discusses limits to loop unrolling gains such as code size growth and register pressure, explores loop unrolling and scheduling in superscalar processors with multiple instruction issues per cycle, and concludes with static branch prediction methods and their accuracy rates.

📝 Lecture Summary

Recap: Dynamic Scheduling

Our discussions in the last eight lectures focused on hardware-based approaches to exploit parallelism among instructions. The instructions in a basic block, a straight-line code sequence without branches, are executed in parallel using a pipelined datapath. The performance of pipelined datapath is limited by its structure and data and control dependences, as they lead to structural, data, and control hazards. These hazards are removed by introducing stalls, which degrade performance by increasing the CPI to more than 1. The number of stalls is reduced or eliminated by introducing additional hardware and using dynamic scheduling techniques. Key hardware techniques include forwarding and bypassing (reducing data hazard stalls), delayed branching and branch scheduling (reducing control hazard stalls), basic dynamic scheduling with scoreboarding (reducing data hazard stalls from true dependences), dynamic scheduling with renaming using Tomasulo's approach (reducing stalls from anti-dependences and output dependences), dynamic branch prediction, speculation, and multiple instruction issues per cycle.

Introduction to Static Scheduling in ILP

Multiple-instruction-issue per cycle processors exist as superscalar processors, VLIW processors, and vector processors. Superscalar processors exploit ILP using both static and dynamic scheduling approaches, while VLIW processors use only static scheduling. The major software scheduling techniques under discussion include basic compiler scheduling (reducing data hazard stalls), loop unrolling (reducing control hazard stalls), compiler dependence (reducing ideal CPI and data hazard stalls), trace scheduling (reducing ideal CPI and data hazard stalls), and compiler speculation (reducing ideal CPI and data and control hazard stalls).

Basic Pipeline Scheduling

To exploit ILP, we must keep a pipeline full with a sequence of unrelated instructions that can be overlapped. A dependent instruction must be separated from the source instruction by a distance equal to the latency of that instruction. For example, an FP ALU operation using the result of an earlier FP ALU operation must be kept 3 cycles away, and an FP ALU operation using the result of an earlier load double word operation must be kept 1 cycle away. The assumed latencies are: Integer ALU operation latency = 0, FP Load latency to FP store = 0 (result bypassed without stalling), Integer Load latency = 1, and FP ALU operation latency to FP store = 2. A compiler performing scheduling must consider the latencies of functional units in the pipeline.

🔑 Definition — Latency: The number of intervening clock cycles needed to avoid a stall between a producing instruction and a consuming instruction. 📐 Functional Unit Latencies: Integer ALU (0), FP Load to FP Store (0), Integer Load (1), FP ALU to FP Store (2).

Execution of a Simple Loop with Basic Scheduling

Consider a simple loop: for (i=1000; i>0; i=i-1) x[i] = x[i] + scalar, where a scalar is added to a vector in 1000 iterations, and the body of each iteration is independent at compile time. The MIPS code without scheduling is:

L.D F0, 0(R1)      ;F0 array element
ADD.D F4, F0, F2   ;add scalar in F2
S.D F4, 0(R1)      ;store result
DADDU R1, R1, #-8  ;decrement pointer 8 bytes
BNE R1, R2, LOOP   ;branch R1! =R2

Data dependencies in ADD and STORE operations lead to data hazards, and the BNE instruction causes a control hazard.

📌 Example: Single Loop Execution Without Scheduling Using a standard five-stage pipeline with branch delay of one clock cycle and the given latencies:

Instructions:           Clock cycles:
L.D F0, 0(R1)          1
Stall                   2 (L.D followed by FP ALU op has latency=1)
ADD.D F4, F0, F2       3
Stall                   4 (FP ALU op followed by STORE has latency=2)
Stall                   5
S.D F4, 0(R1)          6
DADDUI R1, R1, #-8     7
Stall                   8 (Double ALU has latency=1)
BNE R1, R2, LOOP       9
Stall                   10 (Branch has latency=1)

This code requires 10 clock cycles per iteration.

📌 Example: Single Loop Execution With Compiler Scheduling

Loop:                   Clock cycles:
L.D F0, 0(R1)          1
DADDUI R1, R1, #-8     2
ADD.D F4, F0, F2       3
Stall                   4
BNE R1, R2, LOOP       5 (delayed branch)
S.D F4, 8(R1)          6 (altered & interchanged with DADDUI)

To schedule the delayed branch, the compiler determined it could swap DADDUI and S.D by changing the destination address of S.D from 0(R1) to 8(R1) because R1 has been decremented by DADDUI. This loop requires 6 clock cycles per iteration. Actual work (load, add, store) takes 3 cycles, and the remaining 3 cycles are loop overhead (condition evaluation, stall, branch), resulting in 100% overhead.

💡 Why this matters: Compiler scheduling reduces execution time from 10 to 6 cycles per iteration, a 40% improvement, by rearranging independent instructions to fill pipeline stalls.

Loop Unrolling

To eliminate or reduce the impact of loop overhead (3 clock cycles per loop), we need more operations within the loop relative to overhead instructions. A simple way is to replicate the loop body for multiple iterations and adjust the loop termination code. This approach is known as loop unrolling.

📌 Example: Loop Unrolling Without Scheduling Unroll the loop to have 4 copies of the body. Assume R1 is initially a multiple of 32, and registers are not reused:

LOOP:
L.D F0, 0(R1)
ADD.D F4, F0, F2
S.D F4, 0(R1)          ;drop ADDUI & BNE
L.D F6, -8(R1)
ADD.D F8, F6, F2
S.D F8, -8(R1)         ;drop ADDUI & BNE
L.D F10, -16(R1)
ADD.D F12, F10, F2
S.D F12, -16(R1)       ;drop ADDUI & BNE
L.D F14, -24(R1)
ADD.D F16, F14, F2
S.D F16, -24(R1)
DADDUI R1, R1, #-32
BNE R1, R2, LOOP

Without scheduling, this loop executes in 28 clock cycles (14 for instruction issue, 7 stalls). This is slower than the scheduled version which completes one iteration in 6 cycles, so 24 cycles for 4 iterations.

📌 Example: Unrolling with Scheduling The unrolled loop is scheduled assuming the same latencies:

Loop:                   Clock cycles:
L.D F0, 0(R1)          1
L.D F6, -8(R1)         2
L.D F10, -16(R1)       3
L.D F14, -24(R1)       4
ADD.D F4, F0, F2       5
ADD.D F8, F6, F2       6
ADD.D F12, F10, F2     7
ADD.D F16, F14, F2     8
S.D F4, 0(R1)          9
S.D F8, -8(R1)         10
DADDUI R1, R1, #-32    11
S.D F12, -16(R1)       12
BNE R1, R2, LOOP       13
S.D F16, -24(R1)       14

The 4 LOAD instructions are executed sequentially without stalls. The STORE of iteration 1 is issued in clock cycle 5 without stall. DADDUI is issued in cycle 11 to avoid stall before BNE (cycle 13). STORE of iteration 4 is issued in cycle 14, eliminating stall after branch. Execution time drops to 14 cycles total, or 3.5 clocks per element, compared to 7 cycles per iteration before scheduling.

Loop Unrolling and Scheduling: Conclusion

The key to performing loop unrolling and scheduling is knowing when and how to change instruction ordering. Decisions must: determine legality of moving S.D after DADDUI and BNE and adjust offset; determine loop iterations are independent except for maintenance code; use different registers to avoid unnecessary constraints; eliminate extra test and branch instructions and adjust termination code; determine that loads and stores from different iterations are independent; and schedule code preserving dependencies.

Limits to the Gains of Loop Unrolling and Scheduling

1. Loop Overhead: After unrolling, overhead was only 2 cycles (DADDUI and BNE), reduced to 2/4 or ½ cycles per iteration. This could be reduced to 2/8 or ¼ cycles with 8 times unrolling.
2. Growth in Code Size: For larger loops, code size growth may decrease cache miss rate.
3. Register Pressure: Aggressive unrolling may result in shortfall of registers, called Register Pressure, making it impossible to allocate registers to live values. The compiler must take care of these limitations.

🔑 Definition — Register Pressure: The shortfall of registers that occurs after aggressive unrolling and scheduling, when it may not be possible to allocate registers to live values.

Loop Unrolling and Scheduling with Multiple Issues in Superscalar

Consider the same loop example with two issues per cycle (one load/store/branch or integer ALU and one FP). The loop is unrolled 5 times. After unrolling, the loop contains 5 L.D, ADD.D, S.D, and one each DADDUI and BNE:

Integer instruction:    FP instruction:     Clock cycle:
Loop: LD F0,0(R1)                          1
LD F6,-8(R1)                               2
LD F10,-16(R1)        ADDD F4,F0,F2       3
LD F14,-24(R1)        ADDD F8,F6,F2       4
LD F18,-32(R1)        ADDD F12,F10,F2     5
SD 0(R1),F4           ADDD F16,F14,F2     6
SD -8(R1),F8          ADDD F20,F18,F2     7
SD -16(R1),F12                             8
SD -24(R1),F16                             9
SUBI R1,R1,#40                             10
BNEZ R1,LOOP                               11
SD -32(R1),F20                             12

The unrolled superscalar loop runs in 12 clocks, or 2.4 clocks per iteration, compared to 14/4 = 3.5 for scheduled and unrolled on simple 5-stage MIPS pipeline, exhibiting an improvement factor of 1.5.

Static Branch Prediction

Dynamic branch predictors predict branches based on run-time behavior. Delayed Branch was introduced as a static branch prediction technique that exposes a pipeline hazard so the compiler can reduce penalty. Static branch predictors are used when branch behavior is highly predictable at compile time, which is helpful for scheduling data hazards like loop unrolling.

📌 Example: Static Branch Prediction Consider an example from conditional selection branches:

LD R1, 0(R2)
DSUBU R1, R1, R3
BEQZ R1, L
OR R4, R5, R6
DADDU R10, R4, R3
L: DADDU R7, R8, R9

The dependence of DSUBU and BEQZ on L.D shows a stall is needed after L.D. If the branch (BEQZ) is predicted almost always taken, and the value of R7 is not needed on the fall-through path, then moving L: DADDU R7, R8, R9 after the L.D improves speed. If the branch is rarely taken, and R4 is not needed on the taken path, moving the OR instruction after L.D could be considered. Scheduling depends on knowing branch behavior.

Methods to statically predict branch behavior: A. Predict a branch as taken: Average misprediction rate equals untaken branch frequency (34% for SPEC), ranging from 59% to 9%. B. Predict on basis of branch direction: Choose backward going branches as taken and forward going as not taken. For SPEC, more than half of forward branches are taken, so predicting all as taken is better. C. Predict on basis of profile information: More accurate, using profile data from earlier runs. Branch behavior is often bi-modal (highly biased toward taken or not taken).

For FP benchmarks on SPEC 92, misprediction rate varies from 4% to 9%, and for integer programs from 5% to 15%.

⭐ Key Takeaways

This lecture teaches that static scheduling is a software approach to exploit ILP where the compiler rearranges instructions to reduce pipeline stalls. Basic compiler scheduling reduces data hazard stalls by separating dependent instructions by their latency distance. Loop unrolling replicates the loop body multiple times to reduce loop overhead and increase parallelism, and when combined with scheduling, can dramatically reduce execution time from 10 cycles per iteration to 3.5 cycles. The key limits to loop unrolling are loop overhead, code size growth, and register pressure. Multiple instruction issue in superscalar processors, combined with loop unrolling and scheduling, can further improve performance by a factor of 1.5. Finally, static branch prediction methods (predict taken, predict by direction, or use profile information) achieve misprediction rates of 4% to 15%, significantly enhancing superscalar processor performance.

🧠 Quick Revision Questions

1. What are the three main limits to the gains of loop unrolling and scheduling, and how does each affect performance?
2. For the single loop example, compare the clock cycles per iteration for unscheduled execution, scheduled execution, unrolled without scheduling, and unrolled with scheduling. What improvement factor does scheduling provide?
3. What is the difference between register pressure and code size growth as limits to loop unrolling?
4. How does static branch prediction using profile information differ from the simple "predict taken" strategy, and what are the typical misprediction rates for each?
5. In the superscalar loop example with two issues per cycle, why is the loop unrolled 5 times instead of 4, and what is the final improvement factor over the simple pipelined scheduled version?

📘 Lecture 21 — Instruction Level Parallelism (Static Scheduling – Multiple Issue Processor)

📖 Overview: This lecture extends the discussion of static scheduling to VLIW (Very Long Instruction Word) processors. It covers how compilers schedule multiple instructions in VLIW architectures, including loop unrolling for VLIW, detection of loop-carried dependences, and advanced compiler techniques like the GCD test and tree-height reduction to enhance instruction-level parallelism.

🗂️ Topics Covered

The lecture begins with a recap of static scheduling and branch prediction, then introduces static multiple issue using the VLIW approach. It covers VLIW/EPIC processor architecture and compares overhead with superscalar processors. A detailed example demonstrates VLIW loop unrolling with performance analysis. The lecture then shifts to detecting and enhancing loop-level parallelism, covering loop-carried dependence, the GCD test for dependence detection, and techniques like back substitution and tree-height reduction to eliminate dependent computations.

📝 Lecture Summary

Recap: Static Scheduling and Branch Prediction

In superscalar processors, inserting stalls is the basic compiler approach to avoid data and control hazards. The compiler schedules instructions to reduce or eliminate stalls. For loops, unrolling enhances performance, and scheduling the unrolled loop by repeating each instruction for multiple iterations further reduces stalls, though additional registers are needed. In superscalar processors with multiple issues, static branch prediction results in a lower misprediction rate (4% to 15%) compared to dynamic branch prediction.

Static Multiple Issue: VLIW Approach

A VLIW (Very Long Instruction Word) processor contains a fixed set of instructions (typically 4-16 instructions per word). A VLIW is formatted either as one large instruction or a fixed instruction packet with explicit parallelism among instructions. VLIW is also referred to as EPIC (Explicitly Parallel Instruction Computing) because explicit parallelism exists among instructions.

🔑 Definition — VLIW processor: A processor that initiates multiple instructions per cycle by having the compiler pack operations into a wide template or packet (64-128 bytes), and the hardware simply issues the complete packet.

💡 Why this matters: In VLIW, the overhead does not grow with issue-width, unlike superscalar processors where overhead grows with issue-width. Early VLIW machines required recompilation for different hardware versions, but recent innovations eliminate this need.

Example: VLIW Processor with Loop Unrolling

Consider a VLIW processor that can perform up to five operations per cycle: one integer operation, two floating-point operations, and two memory reference operations. Instructions have 16-bit to 24-bit fields per unit, with instruction length ranging from 112 to 168 bits.

For the MIPS loop x[i] = x[i] + s:

Loop: L.D F0, 0(R1)        ;load array element
      ADD.D F4, F0, F2     ;add scalar in F2
      S.D F4, 0(R1)        ;store result
      DADDU R1, R1, #-8    ;decrement pointer 8 bytes
      BNE R1, R2, LOOP     ;branch if R1 != R2

Assumptions: Compiler uses local scheduling; processor has sufficient registers (15 vs. 6 in superscalar); loop is unrolled 7 times to eliminate all stalls.

VLIW Schedule (9 cycles for 7 iterations):

Clock 1: LD F0,0(R1) | LD F6,-8(R1)
Clock 2: LD F10,-16(R1) | LD F14,-24(R1)
Clock 3: LD F18,-32(R1) | LD F22,-40(R1) | ADDD F4,F0,F2 | ADDD F8,F6,F2
Clock 4: LD F26,-48(R1) | (empty) | ADDD F12,F10,F2 | ADDD F16,F14,F2
Clock 5: (empty) | (empty) | ADDD F20,F18,F2 | ADDD F24,F22,F2
Clock 6: SD 0(R1),F4 | SD -8(R1),F8 | ADDD F28,F26,F2
Clock 7: SD -16(R1),F12 | SD -24(R1),F16
Clock 8: SD -32(R1),F20 | SD -40(R1),F24 | SUBI R1,R1,#48
Clock 9: SD -0(R1),F28 | BNEZ R1,LOOP

🔑 Definition — Issue rate: The average number of operations issued per cycle.

📐 Formula: Average issue rate = Total instructions issued / Total cycles → Plain meaning: How many operations the processor completes on average each clock cycle.

📌 Example: 23 instructions (7×3 loop instructions + 1 condition evaluation + 1 branch) issued in 9 cycles = 23/9 = 2.5 operations per cycle (compared to 3.5 for superscalar).

📐 Formula: VLIW efficiency = (Operations issued) / (Total available slots) = 23/45 = 0.51 or 51%

📌 Example: Each VLIW instruction has 5 slots, so 9 instructions provide 45 total slots; only 23 contain operations.

📐 Formula: Cycles per iteration = Total cycles / Number of iterations = 9/7 = 1.29 cycles per iteration

💡 Why this matters: VLIW code runs twice as fast as superscalar scheduled code for this example, despite lower efficiency.

Detecting and Enhancing Loop Level Parallelism

LLP (Loop Level Parallelism) emphasizes determining the type of dependence among operands across loop iterations, while ILP (Instruction Level Parallelism) focuses on dependence among instructions within a loop.

Loop Carried Dependence (LCD) occurs when data accessed in a later iteration depends on the data value produced in a previous iteration.

🔑 Definition — Loop Carried Dependence (LCD): A data dependence where the value computed in one iteration is used in a later iteration of the same loop.

Example 1 — LLP without LCD:

For (i=1000; i>0; i=i-1)
    x[i] = x[i] + s;

Here, dependence exists between two uses of x[i] within the same iteration (not loop-carried), but successive uses of i in different iterations is loop-carried. This can be eliminated by loop unrolling.

Example 2 — LCD Preventing ILP:

For (i=1; i<=100; i=i+1) {
    A[i+1] = A[i] + C[i];     // S1
    B[i+1] = B[i] + A[i+1];   // S2
}

• First dependence (loop-carried): S1 uses A[i] computed in previous iteration; S2 uses B[i] computed in previous iteration
• Second dependence (not loop-carried): S2 uses A[i+1] computed by S1 in the same iteration

Example 3 — LCD not preventing parallelism:

For (i=1; i<=100; i=i+1) {
    A[i] = A[i] + B[i];     // S1
    B[i+1] = C[i] + D[i];   // S2
}

S1 depends on S2 (uses B[i] from previous iteration), but S2 does not depend on S1. No cycle exists, so the loop can be parallelized by reordering statements.

Reorganized code:

A[1] = A[1] + B[1];
for (i=1; i<99; i=i+1) {
    B[i+1] = C[i] + D[i];
    A[i+1] = A[i+1] + B[i+1];
}
B[101] = C[100] + D[100];

Finding Dependences: Greatest Common Divisor (GCD) Test

An affine index can be written as a × i + b, where a and b are constants and i is the loop index variable.

🔑 Definition — Affine index: An array index of the form a×i+b, where a and b are constants.

Two references to the same array have a dependence if:

1. Two iteration indices j and k are both within loop bounds (m ≤ j ≤ n, m ≤ k ≤ n)
2. The values are equal: a×j + b = c×k + d

📐 Formula: GCD Test — If a loop-carried dependence exists, then GCD(c, a) must divide (d-b)

📌 Example: Check for dependence in for (i=1; i<=100; i=i+1) { X[2*i+3] = X[2*i] * 5.0; }

• For X[2*i+3]: a=2, b=3
• For X[2*i]: c=2, d=0
• GCD(a,c) = 2
• d-b = 0-3 = -3
• 2 does NOT divide -3, so no dependence exists

⚠️ Limitation: The GCD test is sufficient to guarantee no dependence, but there are cases where GCD test succeeds but no dependence exists (because GCD test does not consider loop bounds).

Classifying Dependences and Enhancing ILP

Compilers classify dependence types to recognize name dependences and eliminate them through renaming and copying.

Back Substitution increases parallelism by replacing dependent computations with equivalent expressions, though it may increase the total amount of computation.

Tree-Height Reduction increases parallelism by reorganizing operations using associativity, potentially increasing the number of operations while reducing the critical path.

🔑 Definition — Tree-Height Reduction: An optimization that reorganizes a sequence of dependent operations into a tree structure that can be evaluated in fewer steps using associativity.

📌 Example: Original code (3 cycles)

ADD R1,R2,R3
ADD R4,R1,R6
ADD R8,R1,R7

Transformed using associativity (2 cycles):

ADD R1,R2,R3
ADD R4,R6,R7
ADD R8,R1,R4

The first two ADD instructions can be issued in parallel.

📌 Example: Recurrence sum = sum + x Unrolled 5 times with values x1 through x5:

• Original: sum = sum + x1 + x2 + x3 + x4 + x5 (5 dependent operations)
• Optimized: sum = ((sum + x1) + (x2 + x3)) + (x4 + x5) (3 dependent operations)

⭐ Key Takeaways

VLIW processors achieve static multiple-issue by having the compiler pack operations into wide instruction packets, eliminating the hardware overhead that grows with issue-width in superscalar processors. Loop unrolling is essential for VLIW to fill all operation slots, and the average issue rate (2.5 for the example) may be lower than superscalar (3.5), but VLIW achieves fewer cycles per iteration (1.29 vs. 2.67), making it twice as fast. Loop-carried dependence (LCD) is the primary obstacle to loop-level parallelism, where data from one iteration is needed in a later iteration; compilers detect these using the GCD test on affine indices. Compiler techniques like back substitution and tree-height reduction can eliminate or reduce dependent computations, transforming sequential code into more parallel forms, even at the cost of increasing the total number of operations.

🧠 Quick Revision Questions

1. What is the key architectural difference between VLIW and superscalar processors in terms of who schedules instructions?
2. In the VLIW loop unrolling example, why were the ADD.D operations scheduled in cycle 3 instead of cycle 2?
3. What does the GCD test determine, and what is its limitation regarding loop bounds?
4. In the example A[i] = A[i] + B[i]; B[i+1] = C[i] + D[i]; — why is this loop parallelizable despite the loop-carried dependence?
5. How does tree-height reduction increase parallelism, and what is the trade-off in terms of total operations?

📘 Lecture 22 — Instruction Level Parallelism (Software Pipelining and Trace Scheduling)

📖 Overview: This lecture explores advanced compiler techniques for enhancing Instruction Level Parallelism beyond basic loop unrolling. It covers software pipelining as a space-efficient alternative to loop unrolling, and global code scheduling methods (trace scheduling and superblocks) for handling loops with internal control flow. These techniques are critical for maximizing performance in VLIW and superscalar processors.

🗂️ Topics Covered

The lecture begins with a recap of eliminating dependent computations through copy propagation and tree-height reduction, then introduces software pipelining as a technique that interleaves instructions from different iterations without full loop unrolling. It explains symbolic loop unrolling and compares software pipelining with traditional loop unrolling. The second half covers global code scheduling complexities, trace scheduling with its two-step process of trace selection and compaction, and superblocks as an improvement over traces by allowing multiple exits but only a single entry point.

📝 Lecture Summary

Recap: Lecture 21

Last time, the discussion covered Static Scheduling for VLIW (Very Long Instruction Word) processors, where a VLIW is formatted as one large instruction or a fixed instruction packet with explicit parallelism among instructions in a set. Multiple operations are initiated in a cycle by the compiler which places them in a packet. Wider processors with multiple independent functional units are used to eliminate recompilation.

The compiler finds dependence and schedules instructions for parallel execution, resulting in improvement over superscalar processors in:

• ✓ Average issue rate (operations issued per cycle)
• ✓ Execution speed (time to complete execution of code)

However, VLIW efficiency (percentage of available slots containing an operation) ranges from 40% to 60%. The lecture distinguished between ILP (Instruction Level Parallelism) and LLP (Loop Level Parallelism), noting that loop-carried dependence prevents LLP but not ILP. The affine-based GCD (Greatest Common Divisor) algorithm detects dependence in loops.

Reducing Dependent Computations

To achieve more ILP, the compiler reduces dependent computations using Back Substitution technique, resulting in algebraic simplification and optimization that eliminates operations which copy values to simplify the sequence.

Copy Propagation

The approach of simplification and optimization is also called Copy Propagation. For example, in the sequence:

DADDUI R1,R2,#4
DADDUI R1,R1,#4

The net use of R1 is to hold the result of the second DADDUI operation. Substituting the result of the first DADDUI operation into the second results in:

DADDUI R1,R2,#8

This eliminates the multiple use of register R1 during loop unrolling.

🔑 Definition — Copy Propagation: A compiler optimization technique where the result of one operation is substituted directly into subsequent operations to eliminate redundant computations and simplify code sequences.

Conclusion: Particularly in memory access, this technique eliminates multiple increments of array indices during loop unrolling and moves increments across memory addresses.

Tree-Height Reduction — Optimization

The copy-propagation technique reduces the number of operations or code length. However, optimization to increase parallelism of the code is possible by restructuring the code.

Tree-Height Reduction (Restructuring) increases the number of operations while reducing execution cycles. This optimization is called tree-height reduction because it reduces the height of the tree structure representing a computation, making it wider but shorter.

📐 Formula: Original sequence (3 cycles):

ADD  R1,R2,R3
ADD  R4,R1,R6
ADD  R8,R1,R7

📌 Example: Using associativity, the code can be transformed to:

ADD  R1,R2,R3
ADD  R4,R6,R7
ADD  R8,R1,R4

This sequence executes in 2 cycles by issuing the first two instructions in parallel, compared to 3 cycles for the original.

💡 Why this matters: Tree-height reduction trades off increased operation count for decreased execution time, exploiting associativity of operations to create more parallel execution opportunities.

Conclusion: Detecting and Enhancing LLP

The analysis of LLP focuses on determining data dependence of some later iteration on an earlier iteration. This dependence is referred to as Loop-Carried Dependence. The GCD test detects existence of dependence. Compiler techniques such as Copy Propagation and Tree-Height Reduction eliminate dependent computations.

Uncovering Instruction Level Parallelism

Loop Unrolling is the basic compiler technique to uncover ILP. Loop unrolling with compiler scheduling enhances the overall performance of Superscalar and VLIW processors. It generates a sequence of straight-line code uncovering parallelism among instructions. To avoid pipeline stalls, dependent instructions are separated from source instructions by a distance in clock cycles equal to the pipeline latency of that source instruction. The compiler determines:

1. ✓ The amount of ILP available in the program
2. ✓ The latencies of the functional units in the pipeline

Advanced Compiler Techniques

Two new compiler techniques to uncover ILP are discussed:

• Software pipelining
• Global Code Scheduling (Trace scheduling and Superblock)

Software Pipelining

Software pipelining is a technique where the loop is reorganized such that the code for each iteration is made by choosing instructions from different iterations of the original loop. A software-pipelined loop interleaves instructions from different iterations without unrolling the loop.

The instructions are chosen from different loop iterations, separating the dependent instructions within one iteration of the original loop.

📌 Example Code: Adding constant F2 to array R1:

Loop: L.D  F0,0(R1)
      ADD.D  F4,F0,F2
      S.D  0(R1),F4
      DADDUI R1,R1,#-8
      BNE  R1,R2, LOOP

For software pipelining, the compiler symbolically unrolls the loop and schedules them. It selects instructions from each iteration that do not have dependence among each other. The overhead instructions (DADDUI and BNE) are not replicated.

Symbolic Loop Unrolling for three iterations shows instructions selected from each iteration (shown in yellow in the original):

• Iteration i: L.D F0,0(R1) | ADD.D F4,F0,F2 | S.D F4,0(R1)
• Iteration i+1: L.D F0,0(R1) | ADD.D F4,F0,F2 | S.D F4,0(R1)
• Iteration i+2: L.D F0,0(R1) | ADD.D F4,F0,F2 | S.D F4,0(R1)

Resulting Software Pipeline:

Loop: S.D    F4,16(R1)    ; stores in M[i]
      ADD.D  F4,F0,F2     ; adds to M[i-1]
      L.D    F0,0(R1)     ; loads M[i-2]
      DADDUI R1,R1,#-8
      BNE    R1,R2, Loop

For start-up and finish-up, additional code is needed. The loop takes 5 clock cycles to execute per result. L.D and ADD.D are separated by offset of 16 to run the loop for three iterations (i.e., two iterations less than simple loop unrolling and scheduling). Registers F4, F0, and R1 are reused as there is no data dependence, thus WAR (Write-After-Read) hazard is avoided.

Software Pipelining vs. Loop Unrolling

Software pipelining can be thought of as symbolic loop unrolling because some algorithms use loop unrolling techniques to software-pipeline loops.

Key differences:

• ✓ Software pipelining consumes less code space compared to loop unrolling
• ✓ Software pipelining reduces overhead (fill & drain pipe) to once per loop at the beginning and end, versus once per each unrolled iteration in loop unrolling

For example, if a loop is to do 100 iterations with 4 iterations symbolically unrolled, overhead is paid for 100/4 = 25 times instead of 100 times with loop unrolling.

Global Code Scheduling

Loop unrolling and code scheduling work well when the loop body is straight-line code. Software pipelining works well when the body is a single basic block. Global Code is one where the loop body has internal control flow, such as if-then-else conditional blocks.

Effective scheduling of such code is complex since it involves moving instructions across branches into the shortest possible sequence to compact a code fragment. Global code involves both data dependence and control dependence.

Commonly used compiler-based approaches to schedule global code:

1. ✓ Trace scheduling (critical path approach)
2. ✓ Superblock approach

Complexities of Global Code Scheduling

Consider a typical global code fragment representing an iteration of an unrolled inner loop. Moving assignments to B or C prior to condition evaluation requires complex analysis.

Code sequence example:

LD    R4, 0(R1)    ; Load A
LD    R4, 0(R1)    ; Load B
DADDU R4, R4, R5   ; A+B
SD    R4, 0(R1)    ; A=A+B
BNEA  R4, Else_part ; Is A=0?
: :                ; THEN part
SD    ...., 0(R2)  ; store to B
J     Join         ; jump to F
Else_part:
    x  .....       ; x code
Join:
SD    ...., 0(R3)  ; store c[i]

Effect of moving assignment to B before BNEA: If B is referenced in X or after the IF statement, moving B before IF will change the data flow. This can be overcome by making a shadow copy of B before IF and using the shadow copy in x. However, such a copy is avoided as it slows down the program.

Moving assignment to C before the first branch is more complex and requires two steps:

1. Step 1: Assignment is moved over the join point of the ELSE part into the THEN part. This movement makes instructions for C control-dependent - they are not executed if the ELSE path is chosen. To ensure correct execution, a copy of the instruction is made in the ELSE part.
2. Step 2: If C assignment is moved to before the IF Test, provided it does not affect any data flow, the copy of instruction in the ELSE part can be avoided.

💡 Why this matters: Global code scheduling is extremely complex because moving instructions across branches can change both data flow and exception behavior. Compilers must carefully manage compensation code to ensure correctness.

Trace Scheduling

Trace is a sequence of basic blocks whose operations could be put together into smaller numbers of instructions. Trace scheduling is a way to organize the global code motion process such that the cost of code motion is incurred by the less frequent paths.

🔑 Definition — Trace Scheduling: A compiler technique for scheduling global code by focusing on the most frequently executed path (trace), moving operations early in the sequence, and using compensation code for less frequent paths.

Use cases: Useful for processors with a large number of issues per clock where:

• ✓ Conditional or predicted execution is inappropriate or unsupported
• ✓ Simple loop unrolling is not sufficient to uncover ILP to keep the processor busy

Two steps of Trace Scheduling:

1. Trace Selection: Find likely sequence of basic blocks whose operations could be put together into smaller numbers of instructions
2. Trace Compaction: Squeeze the trace into a small number of wide instructions

Trace Generation: Since the probability of loop branches-taken is usually high, trace is generated by loop unrolling. Additionally, static branch prediction is employed as taken or not-taken to obtain straight-line code by concatenating many basic blocks.

In the earlier global code fragment, if the true path is taken as most frequent, the primary trace could be generated by unrolling the true path n- (say 4-) times. Here, Trace Exit is jump-off the frequent path and Trace Enter is return to trace.

Code Compaction is the code scheduling where the compiler attempts to:

• ✓ Move operations as early as it can in a sequence (trace)
• ✓ Pack the operations into as few wide instructions (or issue packets) as possible

Advantages of Trace Scheduling:

• ✓ Simplifies the decision concerning global code motion
• ✓ Branches are viewed as jumps into (Trace Entrance) or jump out of (Trace Exit) the selected trace which is the most probable path

Overhead of Trace Scheduling:

• When code is moved across a trace, additional bookkeeping code is needed on entry or exit points
• When an entry or exit point is in the middle of a trace, significant overheads of compensation code may make trace scheduling unattractive

Superblocks

The drawback of Trace scheduling is that entries into and exit out of a trace in the middle cause significant complications, and the compiler requires to generate and track compensation code.

🔑 Definition — Superblocks: A form of extended basic blocks that have a single entry point but allow multiple exits. This makes compaction easier compared to traces.

Superblocks overcome the trace scheduling drawback. In the earlier global code example, superblocks with one entrance can be constructed by moving C appropriately.

Tail Duplication is used to create a separate block that corresponds to the portion of the trace after the entry. Each unrolling of the loop creates an exit from the superblock to the residual loop that handles the remaining iterations. The residual loop handles the iterations that occur when the unpredicted path is selected.

Advantages of Superblocks:

• ✓ Reduces the cost of bookkeeping and scheduling compared to general trace generation
• ✓ However, code size may enlarge more than a trace-based approach
• ✓ Like trace scheduling, superblocks scheduling may be most appropriate when other techniques fail

Conclusion — Enhancing ILP

All four approaches—Loop Unrolling, Software Pipelining, Trace Scheduling, and Superblocks—aim to increase the amount of ILP that can be exploited by a processor issuing more than one instruction on every clock cycle.

Numerical Problems

Example 1: Find dependences in the loop:

For (i=2; i<100; i= i+1) {
    a[i]      = b[i] + a[i];   /* s1 */
    c[i-1]    = a[i] + d[i];   /* s2 */
    a[i-1]    = 2 * b[i];      /* s3 */
    b[i+1]    = 2 * b[i];      /* s4 */
}

Six dependences identified:

1. Antidependence from s1 to s1 on a
2. True dependence from s2 to s1 (value of a in s2 depends on result of a in s1)
3. Loop-carried true dependence from s4 to s1 on b
4. Loop-carried true dependence from s4 to s3 on b
5. Loop-carried true dependence from s3 to s3 on b
6. Loop-carried output dependence from s3 to s3 on a

True dependences 3, 4, and 5 are loop-carried and cannot be removed by renaming. These factors imply the loop is not parallel as written. The loop can be made parallel by rewriting to find a functionally equivalent loop.

Example 2: Dot product loop with recurrence (running sum in F2 initially 0):

Foo:
L.D    F0,0(R1)     ; load X[i]
L.D    F4,0(R2)     ; load Y[i]
MUL.D  F0,F0,F4     ; X[i]*Y[i]
ADD.D  F2,F0,F2     ; sum = sum + X[i]*Y[i]
DADDUI R1,R1,#-8    ; decrement X index
DADDUI R2,R2,#-8    ; decrement Y index
BNEZ   R1,foo       ; loop if not done

Part a): Unrolling twice results in:

foo:
L.D    F0,0(R1)
L.D    F4,0(R2)
L.D    F6,#-8(R1)
MUL.D  F0,F0,F4      ; 1 from L.D F4,0(R2)
L.D    F8,#-8(R2)
DADDUI R1,R1,#-16
MUL.D  F6,F6,F8      ; 1 from L.D F8,-8(R2)
ADD.D  F2,F0,F2      ; 3 from MUL.D F0,F0,F4
DADDUI R2,R2,#-16
Stall
BNEZ   R1,foo
ADD.D  F2,F6,F2      ; in slot, 3 from ADD.D F2,F0,F2

The dependence chain from one ADD.D to the next forces a stall.

To eliminate the stall: Use commutativity and associativity of dot product with two running sums (one for even elements, one for odd elements):

foo:
L.D    F0,0(R1)
L.D    F6,-8(R1)
L.D    F4,0(R2)
L.D    F8,-8(R2)
MUL.D  F0,F0,F4      ; 1 from L.D F4,0(R2)
MUL.D  F6,F6,F8      ; 1 from L.D F8,-8(R2)
DADDUI R1,R1,#-16
DADDUI R2,R2,#-16
ADD.D  F2,F0,F2      ; 3 from MUL.D F0,F0,F4
BNEZ   R1,foo
ADD.D  F2,F0,F2      ; 3 from MUL.D F6,F6,F8, fill delay slot
ADD.D  F2,F0,F2      ; combine even and odd elements

Part b): The unrolled and scheduled code (loop body takes 10 cycles):

Example 3: GCD test for loop dependence

For (i=2; i<=100; i+=2)
    a[i] = a[50*i+1]

Normalized version (start index at 1, increment by 1):

For (i=1; i<=50; i++) {
    a[2*i] = a[(100*i)+1]
}

GCD Test: a=2, b=0; c=100, d=1

• gcd(2,100) = 2
• d - b = 1
• Since 1 is a factor of 2, GCD test indicates there IS a dependence

Reality: There is no actual dependence because the loop loads values from a[101], a[201]...a[5001] and stores to a[2], a[4]...a[100]. The GCD test gives a false positive in this case.

⭐ Key Takeaways

The four compiler techniques—loop unrolling, software pipelining, trace scheduling, and superblocks—all aim to increase the amount of ILP that can be exploited by processors issuing multiple instructions per cycle. Software pipelining is more code-space efficient than loop unrolling because it interleaves instructions from different iterations without replicating the entire loop body, paying the fill/drain overhead only once per loop rather than once per iteration. Global code scheduling addresses the challenge of loops with internal control flow, where trace scheduling focuses on the most frequent execution path and uses compensation code for less frequent paths, while superblocks improve upon traces by allowing only a single entry point with multiple exits, reducing bookkeeping complexity. The GCD test is a useful but imperfect tool for detecting loop-carried dependences—it can yield false positives when the actual array indices accessed never overlap. In dot product reduction problems, exploiting associativity and commutativity to compute partial sums (e.g., even and odd elements separately) can eliminate pipeline stalls that would otherwise be forced by the recurrence.

🧠 Quick Revision Questions

1. What is the key difference between software pipelining and traditional loop unrolling in terms of code space and overhead?

2. Explain the two steps of trace scheduling and describe why compensation code may be needed when moving instructions across trace boundaries.

3. How do superblocks differ from traces, and what advantage does the single-entry point provide?

4. In the dot product example, why does computing two partial sums (even and odd elements) eliminate the stall caused by the recurrence?

5. Given the GCD test result (d-b mod gcd(c,a) = 0 indicates dependence), explain why the test can produce false positives and why this matters for compiler optimization.