CS501 — Final Term Summary (Lectures 23–45)

📘 Lecture 23 — I/O Subsystems

📖 Overview: This lecture introduces I/O subsystems, which are critical for computer performance. It explains the major components, interface types, design considerations, data transfer methods, and I/O buses, highlighting why improving I/O performance is as important as CPU performance.

🗂️ Topics Covered

The lecture covers an introduction to I/O subsystems and their differences from memory subsystems, major components including the I/O interface and peripherals, the computer interface and I/O ports, memory-mapped I/O versus isolated I/O, considerations during I/O subsystem design including data location, transfer, and synchronization, serial and parallel transfers with their types and error conditions, and I/O buses including arbitration and bandwidth issues, illustrated with examples.

📝 Lecture Summary

Introduction to I/O Subsystems

The terms "input" and "output" are from the CPU's point of view. In an input cycle, the CPU receives data from a peripheral device; in an output cycle, the CPU sends data to a peripheral device. I/O subsystems are similar to memory subsystems in that both exchange bits/bytes under CPU control, with the CPU sending address information that is decoded to select the appropriate device.

Memory and I/O subsystems differ in four key ways:

1. Wider range of data transfer speed: I/O devices can be very slow (e.g., keyboard with seconds between keystrokes) or very fast (e.g., disk drive with microseconds/nanoseconds between bytes). Memory devices have a narrower speed range relative to the CPU.
2. Asynchronous activity: Memory subsystems are almost always synchronous (governed by the CPU's clock). I/O subsystems generally require handshaking signals for asynchronous transfers.
3. Larger degradation in data quality: I/O data can carry more noise (e.g., telephone line noise for modems, media defects on hard drives), requiring effective error detection and correction techniques.
4. Mechanical nature of many I/O devices: Many I/O devices have mechanical parts with higher failure rates, causing interruptions that reduce throughput (e.g., a printer running out of paper requires CPU data to be buffered).

To deal with these differences, special software programs called device drivers are made part of the operating system, usually written in assembly language. Unlike memory subsystems where each location has a unique address from the CPU's address space, I/O devices typically use a group of contiguous addresses, with data exchanged byte-by-byte and stored in internal buffers if needed.

I/O subsystems were historically called the "orphans" of computer architecture because performance improvement was neglected. However, I/O performance is critical, especially for transaction processing systems like airline reservation systems or ATMs. The lecture provides an example: if a program takes 200 seconds (180 CPU + 20 I/O), and CPU performance improves 40% per year while I/O stays the same, after 7 years I/O time becomes 54.05% of elapsed time—making I/O improvement as important as CPU improvement.

💡 Why this matters: Neglecting I/O performance can dramatically limit overall system performance, even with a fast CPU.

Major Components of an I/O Subsystem

I/O subsystems have two major parts:

• The I/O interface: Electronic circuitry connecting the CPU to the I/O device.
• Peripherals: Devices used to communicate with the CPU (e.g., keyboard, monitor).

Computer Interface

A Computer Interface is a piece of hardware whose primary purpose is to connect computer elements (processor unit, memory subsystem, peripheral devices, buses/links) so that signal levels and timing requirements are matched.

An interface that connects the microcomputer bus to peripheral devices is called an I/O Port. I/O ports serve three purposes:

1. Buffering data (holding temporarily) to and from the computer bus.
2. Holding control information that dictates how a transfer is conducted (e.g., telling a printer to start a new page, telling a tape drive to rewind).
3. Holding status information so the processor can monitor activity (e.g., printer out of paper, hard drive crash).

The term buffer refers to I/O registers in an interface where data, status, or control information is temporarily stored. A block of memory locations in main memory or peripheral devices can also be called a buffer. Special circuits for voltage/current matching are also called buffers.

The system bus (consisting of address bus, data bus, and control bus) serves as a backbone, connecting memory subsystems and I/O subsystems. I/O modules (examples: keyboard/mouse module, monitor module, hard disk module, modem module) are examples of I/O ports.

Memory Mapped I/O versus Isolated I/O

In isolated I/O, a separate address space of the CPU is reserved for I/O operations, totally different from the memory address space. The CPU has two distinct address spaces, and unique CPU instructions are associated with the I/O space. The x86 family (Pentium) with in and out instructions is a well-known example. The Pentium's I/O space is 64 Kbytes, organized as eight banks of 8 Kbytes each.

In memory-mapped I/O (used by processors like the SRC), there is no separate I/O space. Some address space from the memory address space is used to map I/O devices. The benefit is that all memory-accessing instructions can be used for I/O devices, eliminating the need for separate I/O instructions. The disadvantage is that the I/O interface becomes more complex, and if partial decoding is used, many memory addresses are consumed.

The CPU differentiates between the two address spaces using signals from the control bus. For the Pentium: during an in instruction, the IOR# signal becomes active and MEMR# is deactivated; during a mov instruction, MEMR# becomes active.

🔑 Definition — Isolated I/O: A scheme where the CPU has a separate address space for I/O operations, distinct from the memory address space, accessed using unique I/O instructions. 🔑 Definition — Memory-Mapped I/O: A scheme where I/O devices share the memory address space, allowing all memory-accessing instructions to be used for I/O operations.

Considerations during I/O Subsystem Design

Data location: The designer must identify the device where the data to be accessed is available, its address, and how to collect the data. For example, if a record is stored in the fourth sector of the second track of the third platter on a hard drive, the particular hard drive must be selected and the address (platter, track, sector) must be provided.

Data transfer: This includes the direction of transfer (out of CPU or into CPU), the destination/source device, the amount of data (e.g., one bit for a mouse click, several kilobytes for a hard drive block), and the transfer rate (different for printers vs. hard drives).

Data synchronization: The CPU should input data only when the device is ready to provide it, and send data only when the device is ready to receive it. There are three basic schemes:

1. Synchronous transmission: The master (M) and slave (S) are permanently connected. The slave can transfer at the master's speed—no handshaking needed. The master activates the Read signal, data is provided by the slave, and the master uses the Enable signal to latch it. All activity is synchronous with the system clock. Example: register-to-register transfer within a CPU.

2. Semi-synchronous transmission: All activity is synchronous with the system clock, but when the slave cannot provide data within the allotted time, additional clock periods are added. The slave indicates readiness by activating the complete signal. Upon receiving this, the master activates the Enable signal to latch the data. Example: transfers between the CPU and main memory.

3. Asynchronous transmission: No common clock is required. The master and slave operate at different speeds. Handshaking signals coordinate the transfer: the master activates its Ready signal; the slave detects this, provides data, and activates its Acknowledge signal; the master latches data with the Enable signal; the master deactivates Ready; the slave removes data and deactivates Acknowledge.

🔑 Definition — Handshaking signals: Additional signals used to coordinate asynchronous data transfers between devices operating at different speeds.

Serial and Parallel Transfers

Serial Transfer: Data bits in a "piece of information" (usually a byte or word) are transferred one bit at a time over a single pair of wires.

• Advantages: Easy to implement (using UARTs or USARTs), low cost (fewer wires), longer distance between transmitter and receiver.
• Disadvantages: Slow by nature, inefficient due to overhead.

Parallel Transfer: All data bits (usually 8 or 16) are transferred over separate lines simultaneously.

• Advantages: Fast compared to serial.
• Disadvantages: High cost (more lines), cost increases with distance, increased noise with distance.

💡 Why this matters: The terms "serial" and "parallel" are with respect to the computer I/O ports, not the CPU—the CPU always transfers data in parallel.

Types of serial communication:

• Asynchronous: Special bit patterns separate characters; "dead time" between characters can be any length; clocks at both ends need not have the same frequency (within limits).
• Synchronous: Characters are sent back-to-back; must include special "sync" characters at the beginning of each message and "idle" characters to fill gaps; characters must be precisely spaced; activity at both ends must be coordinated by a single clock (must be transmitted with data).

The maximum information rate of a synchronous line is higher than that of an asynchronous line with the same bit rate because asynchronous transmission uses extra bits with each character. A protocol is a set of rules understood by both sender and receiver.

Error conditions related to serial communication:

• Framing Error [A]: Occurs when a 0 is received instead of a stop bit (always a 1)—the appropriate number of stop bits was not detected after the start bit.
• Parity Error [B]: Occurs when the parity of the received data does not match the expected parity. (Parity is the number of 1's—even or odd. A parity bit is an extra bit added for error detection/correction. For even parity, the total number of 1's including the parity bit is even.)
• Overrun Error [A]: The prior character was not yet read from the USART's "receive data register" by the CPU and was overwritten by the new received character—the first character is lost and must be retransmitted.
• Under-run Error [S]: If a character is not available at the beginning of an interval, the transmitter inserts an idle character until the end of the interval.

I/O Buses

Modern computers often use two separate buses: a memory bus for connecting the CPU to memory, and an I/O bus for connecting peripherals and I/O devices to the system. Examples of I/O buses include the PCI bus and the ISA bus. These provide an "abstract interface" that can be standardized for connecting a variety of peripherals.

Earlier generation computers used a single bus for both memory and I/O, sharing bandwidth. Modern architectures use separate buses for greater flexibility and upgradeability.

A main disadvantage of I/O buses is that every bus has a fixed bandwidth shared by all devices. Electrical constraints (transmission line effects, bus length) further reduce bandwidth. Designers must decide whether to sacrifice interface simplicity (connecting more devices) at the cost of bandwidth, or connect fewer devices for better bandwidth.

📌 Example #1: An I/O bus transfers 4 bytes per bus cycle at a maximum frequency of 30 MHz. Maximum bandwidth = 30 × 4 = 120 Mbytes/sec. A hard drive (40 Mbytes/sec) and video card (128 Mbytes/sec) together demand 168 Mbytes/sec—exceeding the bus bandwidth. One or both components will operate at reduced bandwidth.

Bus arbitration: Most I/O buses have protocols defining how many devices can access the bus and what happens when multiple devices request it simultaneously. An arbitration scheme must be established. In SCSI, every device has an ID, and the device with the highest priority gets bus access first. This is easy to implement but can cause starvation (low-priority devices never get access). An alternative is to give highest priority to the device waiting the longest.

📌 Example #2: A bus requires 10 nsec for bus requests, 10 nsec for arbitration, and 15 nsec to complete an operation after access is granted. Total time = 35 nsec per I/O operation. Maximum IOPS = 1 / (35 × 10⁻⁹) = 28.6 million IOPS. Therefore, the bus cannot perform 50 million IOPS.

⭐ Key Takeaways

I/O subsystems differ fundamentally from memory in speed range, synchrony, data quality, and mechanical nature, requiring special device drivers and careful design. There are two main I/O addressing schemes: isolated I/O with separate instructions and address space, and memory-mapped I/O that uses memory instructions but creates more complex interfaces. Data synchronization is achieved through synchronous, semi-synchronous, or asynchronous transmission—each with different handshaking requirements and speed capabilities. Serial transfer sends bits one at a time (cheaper, longer distance, slower), while parallel sends all bits simultaneously (faster, more expensive, shorter distance). I/O buses have fixed bandwidth that must be shared among all connected devices, requiring careful design and arbitration to avoid bottlenecks and starvation.

🧠 Quick Revision Questions

1. What are the four key differences between memory subsystems and I/O subsystems?
2. Explain the difference between isolated I/O and memory-mapped I/O, giving an example processor for each.
3. Describe the handshaking signals used in asynchronous transmission and their sequence.
4. What are the four types of errors related to serial communication, and which ones are associated with asynchronous (A) and synchronous (S) transmission?
5. In Example #2, why can the bus not perform 50 million IOPS, and what is the maximum number of IOPS it can achieve?

📘 Lecture 24 — Designing Parallel Input and Output Ports

📖 Overview: This lecture focuses on designing parallel I/O ports that interface the computer bus with peripheral devices. It covers the essential building blocks of address decoding and data isolation/capturing, explains the practical implementation of a skeleton address decoder (SAD), introduces the NUXI problem caused by endianness differences, and discusses variations in address decoder design based on CPU architecture. Understanding these concepts is critical for building functional and reliable I/O interfaces.

🗂️ Topics Covered

The lecture covers the design of parallel I/O ports, starting with the two key functions of address decoding and data isolation/capturing. It then provides a practical example of designing a 16-bit parallel output port for the FALCON-A CPU, including the implementation of the SAD and the use of LED branches for output display. The NUXI problem arising from endianness differences is introduced, followed by a detailed discussion on variations in address decoder implementation based on ISA design decisions, including examples for both FALCON-A and Pentium CPUs. Finally, a method for estimating delay intervals in software loops is presented.

📝 Lecture Summary

Designing Parallel I/O Ports

An I/O port is an interface that connects the computer bus (system bus or I/O bus) with I/O devices. During an I/O bus cycle, the CPU places a device address on the address bus, activates control signals for read or write, and then data is transferred over the data bus. The timing and voltage/current requirements of the I/O port must match those of the CPU. There are two important functions built into I/O ports: address decoding and data isolation (for input) or data capturing (for output).

🔑 Definition — Address Decoder: An "Address Decoder" is a combinational (logic) circuit with n + r inputs and a single output, where n = the number of address lines into the decoder, and r = the number of control lines into the decoder. The output fD is active only when the corresponding address is present on the n address lines and the corresponding r control lines hold the "proper" (active or inactive) value. fD is inactive for all other situations.

📐 Formula/Analogy — Skeleton Address Decoder (SAD): Think of the address decoder as a “big AND gate” called a Skeleton Address Decoder or SAD. Its output is active only when the correct address is present and control signals hold proper values.

Suggestions for Address Decoder Design:

1. Start by thinking of the address decoder as a “big AND gate” (SAD).
2. Always write the port address in binary. Address lines that are 0 will be inverted before feeding into the “big AND gate”; other address lines will not be inverted.
3. List relevant control signals. If the “proper” value of a signal is 0, invert it before applying to the SAD.
4. Determine if the decoder output should be active high or low based on the latch/buffer type. If active low is needed, invert the output of the “big AND gate”.
5. Implement the SAD using any available method (e.g., HDL code, PLDs, or SSI building blocks).

Data Isolation or Capturing:

• For Input Ports: Use tri-state buffers to place data on the data bus only during the I/O read bus cycle. Their enable line is driven by the SAD output.
• For Output Ports: Use latches (or registers) to capture data from the data bus during the I/O write bus cycle and hold it for the peripheral device. Their clock/latch enable line is driven by the SAD output.

Example #1 — Designing a 16-bit Parallel Output Port for FALCON-A

Problem Statement: Design a 16-bit parallel output port mapped on address DEh of the I/O space of the FALCON-A CPU.

Solution:

1. Start with a “big AND gate” (SAD) and write the address DEh in binary: 1101 1110.
2. Associate CPU address lines: A7=1, A6=1, A5=0, A4=1, A3=1, A2=1, A1=1, A0=0.
3. Since the I/O space is 256 bytes, address lines A15..A8 are don’t cares. A0 and A5 (which are 0) will be inverted before being applied to the SAD.
4. The relevant control signal is IOW#. A logic 0 on this line indicates it is active, so it should be inverted before being applied to the SAD.
5. For a 16-bit output port, two 8-bit registers are used. The SAD output connects to their enable inputs. D-inputs connect to the data bus, Q-outputs to the peripheral device.

📐 Formula — SAD Implementation: The SAD is an AND gate with 9 inputs (7 address lines + 2 inverted address lines + 1 inverted control signal). It can be implemented using an 8-input AND gate and a 2-input AND gate.

Example #2 — Displaying Output Data with LED Branches

Problem Statement: Given a 16-bit parallel output port at address DEh with 16 LED branches (LED on for 1, off for 0), which LEDs will be ON when the instruction out r2, 222 executes, assuming r2 contains 1234h?

Solution:

1. 1234h in binary: 0001 0010 0011 0100
2. Data bus bit associations: D15..D0 are associated with this bit pattern.
3. The FALCON-A uses a byte-wide address space, a 16-bit data bus, and the big-endian data format. The upper byte (MSB) is transferred using address DEh, and the lower byte (LSB) using address DFh.
4. The register mapped on address DEh uses D15..D8. The relevant bits are D12=1, D9=1, D5=1, D4=1, and D2=1.
5. Therefore, LEDs L12, L9, L5, L4, and L2 will turn on.

The NUXI Problem

The NUXI problem arises from endianness differences. In the big-endian format, the least significant byte is transferred over the most significant side of the data bus, and vice versa for the little-endian format. When a little-endian computer exchanges data with a big-endian computer over a 16-bit parallel port, the data is received in a “swapped” form. For example, the string “UNIX” would be received as “NUXI”. Special software is used to resolve this problem.

Variation in the Implementation of the Address Decoder

The previous implementation assumed the FALCON-A does not allow using part of its data bus during a transfer and that all port addresses are divisible by 2 (A0 is always 0). If a CPU allows using part of its data bus (e.g., 8 bits), the design changes.

In an alternate design, the enable inputs of the two 8-bit registers are not connected together. Since a 16-bit port uses two addresses (DEh and DFh), address line A0 cannot be used at the input of the big AND gate. Instead, A0 is used with two 2-input AND gates. The output of the AND gate where A0 is inverted enables the register at address DEh, and the gate where A0 is not inverted enables the register at address DFh.

If the assembler did not restrict port addresses to even values, the implications are significant. For example, executing out r2, 223 (address DFh) would not enable registers in the original design, but in the modified design, the high data byte would be sent to the register at address DFh over data lines D7..D0. The low data byte would be sent to address E0h in the next bus cycle, but it will be lost if no port exists there.

Pentium Example: The Pentium allows using part of its 32-bit data bus and accumulator. An 8-bit parallel output port at address FEF2h can be designed using the BE2# signal. The instruction sequence mov dx, 0FEF2h; mov al, 12h; out dx, al will send the data byte 12h to the 8-bit register over lines D23..D16.

💡 Why this matters: ISA design decisions (e.g., address space organization, data bus width, endianness, and alignment restrictions) have a strong bearing on the implementation details and working of the computer.

Example #3 — Assembly Program to Turn on LEDs One by One

Problem Statement: Write an assembly language program to turn on 16 LEDs one by one on the output port from Example #1. Each LED should stay on for a noticeable duration.

Solution:

; Example_3.asmfa
mov r1, 0
out r1, 222          ; Turn all LEDs off
again:
delay1:
movi r2, 0
again1:
subi r2, r2, 1
jnz r2, [again1]     ; Delay loop
out r1, 222          ; Turn on current LED
movi r5, 15          ; Loop counter for 15 remaining LEDs
again2:
shiftl r1, r1, 1
out r1, 222          ; Turn on next LED
delay2:
movi r2, 0
again3:
subi r2, r2, 1
jnz r2, [again3]     ; Delay loop
subi r5, r5, 1
jnz r5, [again2]     ; Loop for next LED
j [again]            ; Start over from first LED

Estimating the Delay Interval

To estimate the delay introduced by a loop like again1, we can use the formula:

📐 Formula — Execution Time (ET): $$ ET = CPI \times IC \times T = \frac{CPI \times IC}{f} $$ Where:

• CPI = clocks per instruction
• IC = instruction count
• T = time period of the clock
• f = frequency of the clock

Example: Assuming FALCON-A operates at 1 MHz, subi takes 3 clock periods, and jnz takes 4 clock periods, the execution time for the again1 loop (executing 65,535 times) is: $$ ET = (3+4) \times 65535 / (1 \times 10^6) = 0.459 \text{ sec} $$

⭐ Key Takeaways

The two essential building blocks of a parallel I/O port are an address decoder and data isolation/capturing logic. The address decoder, often implemented as a "big AND gate" (SAD), enables the port only when the correct address and control signals are present. Endianness (big-endian vs. little-endian) causes the NUXI problem when data is transferred between computers with different formats, requiring software resolution. ISA design decisions, such as data bus width, address alignment constraints, and the ability to use partial data buses, directly affect the complexity and feasibility of I/O port implementations. The execution time of software delay loops can be estimated using the formula ET = (CPI × IC) / f.

🧠 Quick Revision Questions

1. What are the two key functions that must be built into an I/O port, and how are they typically implemented for input and output ports?
2. Explain the role of tri-state buffers in an input port and registers/latches in an output port.
3. What is the NUXI problem, and why does it occur?
4. In Example #2, if the FALCON-A used little-endian format instead of big-endian, which bits from D15..D0 would correspond to the MSB and LSB data bytes, and how would this change the calculation of which LEDs are on?
5. Using the formula for execution time, calculate the delay for a loop that executes a subi instruction (3 clocks) and a jnz instruction (4 clocks) 10,000 times on a CPU running at 2 MHz.

📘 Lecture 25 — Input Output Interface

📖 Overview: This lecture continues the design of I/O interfaces for the FALCON-A CPU, focusing on parallel input ports, memory-mapped I/O, and the Centronics printer interface. It covers critical concepts like partial decoding, data bus multiplexing, and the "wrap around" effect, showing how to connect real-world peripherals to a CPU.

🗂️ Topics Covered

This lecture begins by designing a 16-bit parallel input port at address 7Eh, including a complete assembly language program to monitor switches and blink LEDs. It then covers memory-mapped I/O ports, explaining the changes needed to map ports onto memory space. The concept of partial decoding and the resulting "wrap around" effect is explained in detail, followed by data bus multiplexing for connecting 8-bit peripherals to a 16-bit data bus. A generic I/O interface is introduced, and the lecture concludes with a thorough explanation of the Centronics Parallel Printer Interface, including its signals, timing, and a complete design example for the FALCON-A CPU.

📝 Lecture Summary

Designing a parallel input port

Designing a parallel input port is similar to an output port, but with key differences. The address decoder inverts A7 and A0 (for address 7Eh), uses the IOR# control signal instead of IOW#, and uses tri-state buffers for data isolation instead of a register. The common enable line of the tri-state buffers is connected to the output of the address decoder's AND gate. The input of these buffers connects to the input device (like switches S15...S0), and the output connects to the FALCON-A's data bus.

📌 Example #1: Design a 16-bit parallel input port mapped on address 7Eh of the FALCON-A I/O space.

• Address decoder has A7 and A0 inverted.
• IOR# is used.
• Sixteen tri-state buffers with common enable are used.

📌 Example #2: Write a program for a FALCON-A with a 16-bit input port at 7Eh and a 16-bit output port at DEh that blinks LEDs corresponding to switches set to logic 1.

• The program reads the input port, sends the value to the output port, waits, turns off all LEDs, waits again, and repeats indefinitely. This continuously monitors the switches and blinks the corresponding LEDs.
• The flowchart and assembly code (filename: Example_2) illustrate this process step-by-step.

🔑 Definition — Single Address I/O Port: It is possible to use a single address for both input and output by using an address decoder that differentiates between the register (for output) and the tri-state buffer (for input) using the IOW# and IOR# control bus signals. A diagram shows a 16-bit parallel input/output port at address 2Ch using this technique.

Memory mapped I/O ports

Memory-mapped I/O maps I/O ports onto the CPU's memory space instead of a separate I/O space. For the FALCON-A, this requires: replacing IOW# with MEMW#, using the entire CPU address bus in the address decoder (e.g., addresses 00DEh and 00DFh for the previous example), and using store and load instructions instead of out and in instructions.

📌 Example: Rewriting the program from Example #2 for memory-mapped I/O.

• The advantage is that more than 256 ports are available (up to the full memory space).
• The disadvantage is that the address decoder becomes more complex, increasing hardware costs.

Partial decoding and the “wrap around” effect

Partial decoding is a technique where some of the CPU's address lines are ignored in the address decoder, reducing complexity and cost. For example, ignoring address lines A8...A15 from the FALCON-A saves eight inverters and two AND gates. However, it has a trade-off known as the "wrap around" effect.

🔑 Definition — Wrap Around Effect: When address lines are unused (don't cares), the single intended address is accessed by multiple addresses. For example, if upper eight address lines are unused, address 00DEh is also accessed at 01DEh, 02DEh, ..., FFDEh. The 64 Kbyte address space "wraps around" itself 256 times, effectively reducing it to 256 bytes. 💡 Why this matters: Partial decoding saves hardware but can cause aliasing, where multiple addresses map to the same port. This is acceptable in small systems with lots of unused memory space.

Data bus multiplexing

Data bus multiplexing connects one part of the CPU's data bus to the peripheral at one time and another part at a different time, ensuring only one 8-bit portion is connected at any time. This is used to attach 8-bit peripherals to a 16-bit (or larger) CPU data bus that has a byte-wide address space.

🔑 Definition — Data Bus Multiplexing: A technique using tri-state buffers to connect different halves of a CPU's data bus to an 8-bit peripheral at different times, controlled by address bit A0.

• For an even address (A0=0), the upper group of tri-state buffers is enabled, connecting D<15..8> to the peripheral.
• For an odd address (A0=1), the lower group is enabled, connecting D<7..0> to the peripheral.
• An 8-bit parallel output port using addresses DCh and DDh is shown as an example.
• The instruction out r1H,220 accesses the peripheral using D<15..8>, while out r1L,221 uses D<7..0>. 📌 Example: The instruction out r1,220 sends r1H to the peripheral, but the contents of r1L are lost. This is because for address 220 (even), only D<15..8> are connected; D<7..0> (r1L) are not connected.
• Advantage: All addresses are utilized, none wasted.
• Disadvantage: Increased complexity and cost of the interface.

A generic I/O interface

Most parallel I/O ports are mapped onto a range of contiguous addresses. A block diagram shows an interface using eight consecutive addresses (56 to 63) for a typical parallel device. Registers within the interface have predefined functions, like a "data out" register at addresses 56 and 57 for sending data, and a "control" register at addresses 60 and 61 for sending control bits. An address decoder at the bottom receives address/control information and generates enable signals for these registers.

The Centronics Parallel Printer Interface

The Centronics Parallel Printer Interface is an industry-standard set of signal specifications used by most printers. It provides a uni-directional, byte-wide parallel interface. The interface uses a 25-pin connector on the CPU side and a 36-pin connector on the printer side.

Key Signals:

• STROBE#: A control signal (active low) from the CPU to the printer indicating data is ready.
• BUSY: A status signal from the printer indicating it cannot accept more data.
• ACKNLG#: A status signal from the printer indicating data has been received and it is ready for new data.
• D<7..0>: The 8-bit data bus.
• PE#: Paper End status signal.
• SLCT: Select (online) status signal.
• ERROR#: Error status signal.
• INIT#: Control signal to reset the printer.
• AUTO FEED XT#: Control signal for auto line feed.
• SLCT IN#: Control signal to enable data entry.

Data Transfer Handshake:

1. CPU places 8-bit data on the printer's data bus.
2. CPU applies a negative pulse (≥0.5μs) to the STROBE# pin.
3. Printer activates BUSY (high) to indicate it cannot accept more data.
4. Printer receives the byte, then activates ACKNLG# (low) to signal completion.
5. Printer deactivates BUSY (low) to indicate readiness for new data.

• BUSY is suitable for level-triggered systems; ACKNLG# is better for edge-triggered systems.
• The interface typically uses two 8-bit output ports (data and control) and one 8-bit input port (status).

📌 Example #3: Design a Centronics parallel printer interface for the FALCON-A CPU starting at address 38h.

• Since the FALCON-A has a 16-bit data bus, three contiguous even addresses (38h, 3Ah, 3Ch) are used to simplify the design.
• Data bus lines D7...D0 are connected to the printer's 8-bit data bus; D15...D8 are left unconnected. (The FALCON-A uses big-endian format, so the low byte of CPU registers is transferred to the printer.)
• The address decoder logic diagram is provided in the lecture.

Centronics Bit Assignment for I/O Ports (Table 2):

• Address 0 (DATA): 8-bit output port for data byte (D7...D0).
• Address 1 (STATUS): 8-bit input port for status: BUSY (bit 7), ACKNLG# (bit 6), PE# (bit 5), SLCT (bit 4), ERROR# (bit 3), unused (bits 2-0).
• Address 2 (CONTROL): 8-bit output port for control: unused (bits 7-6), DIR (bit 5, enables bidirectional mode), IRQEN (bit 4), SLCT IN# (bit 3), INIT# (bit 2), Auto Feed XT# (bit 1), STROBE# (bit 0).

⭐ Key Takeaways

The most critical concepts for the exam are the distinction between input and output port design (tri-state buffers vs. registers, IOR# vs. IOW#), the difference between isolated and memory-mapped I/O, and the trade-offs of partial decoding (lower cost vs. wrap-around effect). Data bus multiplexing is essential for connecting 8-bit peripherals to a 16-bit bus, enabling byte-wide transfers. Finally, the Centronics printer interface is a practical example of parallel communication, requiring careful consideration of handshaking signals (STROBE#, BUSY, ACKNLG#) and bit assignments for data, status, and control registers.

🧠 Quick Revision Questions

1. What are the three key differences between designing a parallel input port and a parallel output port for the FALCON-A?
2. Explain the "wrap around" effect caused by partial decoding. Why might an engineer still choose to use partial decoding?
3. In data bus multiplexing, how does the CPU's A0 line determine which half of the data bus is connected to an 8-bit peripheral?
4. List the three handshaking signals used in the Centronics parallel printer interface and describe their function during a data transfer.
5. For the FALCON-A Centronics interface example, why are addresses 39h, 3Bh, and 3Dh considered valid for accessing the interface even though the designed addresses are 38h, 3Ah, and 3Ch?

📘 Lecture 26 — Programmed I/O

📖 Overview: This lecture continues the discussion of the Centronics Parallel Printer Interface and introduces Programmed I/O, the first of three main I/O techniques. It provides detailed examples of programmed I/O implementation for both the FALCON-A and SRC processors, including timing analysis, and compares the two approaches. The lecture highlights the inefficiency of polling and sets the stage for interrupt-driven I/O.

🗂️ Topics Covered

This lecture covers the continuation of the Centronics Parallel Printer Interface specification, a detailed example of programming the interface on the FALCON-A processor to print an 80-character line, the concept and definition of Programmed I/O, a timing analysis of the FALCON-A example program, an improved approach using a printer buffer, programmed I/O examples for the SRC processor, and a comparison of the FALCON-A and SRC examples.

📝 Lecture Summary

The Centronic Parallel Printer Interface (Cont.)

The Centronics interface uses multiple control and status signals. The STROBE# signal (active low) tells the printer to read in the data byte on the data lines. The ACKNLG# signal goes low to indicate that the transfer of a character is complete. The BUSY signal is high when the printer cannot accept data (e.g., during data entry, printing, offline state, or error). The BUSY signal is more suitable for level-triggered systems, while the ACKNLG# signal is better for edge-triggered systems. The interface typically uses two 8-bit parallel output ports (for DATA and CONTROL) and one 8-bit input port (for STATUS). Table 2 shows the bit assignments for these I/O ports, where logical addresses 0, 1, and 2 correspond to the DATA, STATUS, and CONTROL registers, respectively.

Example # 1

The problem is to write an assembly language program for the FALCON-A processor to send an 80-character line to a Centronics printer, with the character data starting at memory address 1024. The solution involves initializing the printer by resetting the INIT# control bit (bit 2) to 0 and then back to 1, and setting the STROBE# signal high. The program then enters a polling loop to check the BUSY flag (bit 7 of the status register). When the printer is ready (BUSY=0), the program loads the next character from memory, outputs it to the data port, generates the necessary STROBE# pulse, advances the buffer pointer, decrements the loop counter, and repeats.

Programmed Input/Output

Programmed I/O refers to a technique where all I/O operations are performed under the direct control of a program running on the CPU. The program, often a "tight loop," handles all I/O activity, including device status sensing, issuing read/write commands, and transferring data. The I/O device has no direct access to memory or the CPU, and data transfer uses CPU registers. A subsequent I/O operation cannot begin until the current one is complete, causing the CPU to wait and making the scheme extremely inefficient. The examples from lectures 24, 25, and 26 are all examples of Programmed I/O.

🔑 Definition — Programmed I/O: All I/O operations are performed directly by a program running on the CPU, which controls all aspects of the I/O process, including status checking, command issuing, and data transfer.

Timing analysis of the program in Example # 1(lec26)

The main loop of the FALCON-A example executes 80 times. The STROBE# signal generation takes 5 clock periods to go low and 5 clock periods to go high. For a 10MHz FALCON-A CPU, this corresponds to 0.5µsec each, satisfying the printer's timing requirements. The polling loop (in r1, statusp; and r1, r1, r3; jnz r1, [again]) takes 10 clock periods (1µsec). One pass of the main loop takes 38 clock periods (3.8µsec). For a 1000 character-per-second (cps) printer, the printer takes 1msec per character. After sending a character in 3.8µsec, the CPU waits ~996µsec, executing the polling loop about 996 times per character. This demonstrates the extreme inefficiency of Programmed I/O.

💡 Why this matters: The timing analysis shows that a 10MHz CPU spends over 99% of its time just waiting for the printer, highlighting why programmed I/O is unsuitable for slow devices.

An improved approach uses a buffer memory within the printer. A modified program eliminates the STROBE# pulse generation instructions, but the polling loop remains to check if the buffer is full (BUSY=1). The main loop now takes 28 clock periods (2.8µsec). While the first 64 characters can be sent quickly (filling the buffer), the remaining 16 characters still face the same polling overhead. Increasing buffer size only delays the problem, not solves it. This issue led to the invention of interrupt-driven I/O.

Programmed I/O in SRC

For the SRC processor, which uses memory-mapped I/O, a program to output a character uses a 2-instruction polling loop to test the ready signal (checked by its sign bit). The program waits for the ready signal to become logic 1, then writes the character to the device data register. A 10 MIPS SRC would execute 10,000 instructions waiting for a 1,000 character/sec printer. A program to print an 80-character line has an inner loop to wait for ready and an outer loop to output a character, advance the pointer, decrement the counter, and repeat, followed by instructions to issue the print command.

Comparisons of the SRC and FALCON-A Examples

The FALCON-A and SRC examples are similar but differ in the control signal checked: the SRC checks the ready signal (active high), while the FALCON-A checks the BUSY signal (active low). Other differences include the instruction set, address width, and number of address lines. Despite different techniques, overhead due to polling cannot be completely eliminated in Programmed I/O.

⭐ Key Takeaways

The key concept of this lecture is Programmed I/O, where the CPU is entirely responsible for all I/O operations, including continuous status checking (polling). The detailed timing analysis of the FALCON-A printer example clearly demonstrates the severe inefficiency of this technique, as the CPU wastes most of its time in a polling loop while waiting for a slow device. While introducing a printer buffer can slightly improve efficiency by allowing burst transfers, it does not eliminate the polling overhead and is only a partial solution. The examples for both the FALCON-A and SRC processors illustrate the universal structure of programmed I/O—a polling loop followed by a data transfer—highlighting the need for more efficient methods like interrupt-driven I/O.

🧠 Quick Revision Questions

1. What is the fundamental characteristic of Programmed I/O that makes it inefficient for slow peripherals?
2. In the FALCON-A example, how many clock periods does one pass of the polling loop take, and what does this imply for a 1000 cps printer?
3. What is the purpose of the STROBE# signal in the Centronics interface, and how is it generated in the FALCON-A program?
4. How does the SRC program determine if the printer is ready to accept a new character?
5. Why does increasing the size of the printer's buffer not completely solve the inefficiency problem of Programmed I/O?

📘 Lecture 27 — Interrupt Driven I/O

📖 Overview: This lecture covers the fundamental concepts of interrupt-driven I/O, contrasting it with programmed I/O polling. It explains how interrupts enable efficient CPU utilization by allowing the processor to respond to events from peripherals only when necessary. The lecture details interrupt types, handling mechanisms, priority schemes, and the system layers involved in I/O software.

🗂️ Topics Covered

The lecture begins with a review of the programmed I/O driver for the SRC processor. It then introduces the concept of interrupts and their advantages over polling. The main discussion categorizes interrupts into internal, external, hardware, and software types. The lecture explains the structure of the I/O software system layers, the Interrupt Service Routine (ISR), and methods for determining the branch address (vectored vs. non-vectored). It covers interrupt handling in the Intel 8086/8088, including the interrupt vector table and branch address calculation. The lecture concludes with concepts of interrupt latency, response deadlines, and methods for handling simultaneous interrupt requests through daisy-chaining and parallel priority.

📝 Lecture Summary

Programmed I/O Driver for SRC

The lecture references Figure 8.10 of the text and its explanation for the programmed I/O driver for the SRC processor. This method involves the CPU continuously polling the I/O device to check its status, which is inefficient for devices with slow data rates.

Interrupt Driven I/O: Introduction

An interrupt is a request to the CPU to suspend normal processing and temporarily divert the flow of control through a new program. This new program to which control is transferred is called an Interrupt Service Routine (ISR) or Interrupt Handler. Interrupts are used to demand attention from the CPU. They are asynchronous breaks in program flow that occur as a result of events outside the running program, usually hardware related, stemming from events such as a key or button press, timer expiration, or completion of a data transfer.

The basic purpose of interrupts is to divert CPU processing only when it is required. For example, in a word-processing program on a multi-tasking OS, polling the keyboard wastes processor cycles because user input is much slower than the CPU. With interrupts, a peripheral device signals the processor only when it has data to exchange. The processor saves its state, executes the interrupt handler, and then resumes its task. A modern processor like the Pentium can execute up to 300,000,000 instructions in the 500 ms it takes for an average user to press consecutive keys.

Advantages of interrupts:

• Useful for interfacing I/O devices with low data transfer rates.
• CPU is not tied up in a tight loop for polling the I/O device.

Types of Interrupts

The general categories of interrupts are: Internal Interrupts, External Interrupts, Hardware Interrupts, and Software Interrupts.

Internal Interrupts:

• Internal interrupts are generated by the processor.
• These are used by the processor to handle the exceptions generated during instruction execution.
• Internal interrupts are used to handle conditions such as stack overflow or a divide-by-zero exception. They are also referred to as traps and are mostly used for exception handling.

External Interrupts: External interrupts are generated by devices other than the processor. They are of two types:

• Hardware interrupts are generated by the external hardware.
• Software interrupts are generated by the software using some interrupt instruction.

As the name implies, external interrupts are generated by devices external to the CPU, such as the click of a mouse or pressing a key on a keyboard. These events require quick service by the software.

Hardware interrupts: Hardware interrupts are generated by external events specific to peripheral devices. Most processors have at least one line dedicated to interrupt requests. When a device signals on this specific line, the processor halts its activity and executes an interrupt service routine. Such interrupts are always asynchronous with respect to instruction execution and are not associated with any particular instruction. They do not prevent instruction completion as exceptions like arithmetic overflow does. Thus, the control unit only needs to check for such interrupts at the start of every new instruction.

There are two types of hardware interrupt: Maskable Interrupts and Non-maskable Interrupts.

Maskable Interrupts:

• These interrupts are applied to the INTR pin of the processor.
• These can be blocked by resetting the flag bit for the interrupts.

Non-maskable Interrupts:

• These interrupts are detected using the NMI pin of the processor.
• These can not be blocked or masked.
• Reserved for catastrophic event in the system.

Software interrupts: Software interrupts are usually associated with the software. A simple output operation in a multitasking system requires software interrupts to be generated so that the processor may temporarily halt its activity and place the data on its data bus for the peripheral device. Software interrupts are also used with system calls. When the operating system switches from user mode to supervisor mode it does so through software interrupts. For example, when a user program makes a system call to delete a file, a software interrupt is generated, causing the processor to halt its current activity and switch to supervisor mode.

I/O Software System Layers

At the bottom lies the actual hardware itself, i.e., the peripheral device. The peripheral device uses hardware interrupts to communicate with the processor. The processor responds by executing the interrupt handler for that particular device. The device drivers form the bridge between the hardware and the software. The operating system uses the device drivers to communicate with the device in a hardware independent fashion. The user programs run at top of the operating system.

Interrupt Service Routine (ISR)

• It is a routine which is executed when an interrupt occurs.
• Also known as an Interrupt Handler.
• Deals with low-level events in the hardware of a computer system, like a tick of a real-time clock.

Branch Address of the ISR

There are two ways used to choose the branch address of an Interrupt Service Routine: Non-vectored Interrupts and Vectored Interrupts.

Non-vectored Interrupts: In non-vectored interrupts, the branch address of the interrupt service routine is fixed. The code for the ISR is loaded at a fixed memory location. Non-vectored interrupts are very easy to implement but not flexible at all. In this case, the number of peripheral devices is fixed. Once the interrupt is generated, the processor queries each peripheral device to find out which device generated the interrupt.

Vectored Interrupts: Interrupt vectors are used to specify the address of the interrupt service routine. The code for ISR can be loaded anywhere in the memory. This approach is much more flexible as the programmer may easily locate the interrupt vector and change its addresses to use custom interrupt servicing routines. Using vectored interrupts, multiple devices may share the same interrupt input line to the processor. A process called daisy chaining is then used to locate the interrupting device.

Interrupt Vector: An interrupt vector is a fixed size structure that stores the address of the first instruction of the ISR.

Interrupt Vector Table:

• All of the interrupt vectors are stored in the memory in a special table called Interrupt Vector Table.
• Interrupt Vector Table is loaded at the memory location 0 for the 8086/8088.

Interrupts in Intel 8086/8088

• Interrupts in 8086/8088 are vector interrupts.
• Interrupt vector is of 4 bytes to store IP and CS.
• Interrupt vector table is loaded at address 0 of main memory.
• There is provision of 256 interrupts.

Branch Address Calculation:

• The number of the interrupt is the number of the interrupt vector in the interrupt vector table.
• Since the size of each vector is 4 bytes and the interrupt vector table starts from address 0, the address of the interrupt vector can be calculated by simply multiplying the number by 4.

🔑 Definition — Interrupt Vector Address Calculation: The address of the interrupt vector = Interrupt Number × 4. 📐 Formula: Address = Interrupt Number × 4 → This gives the memory location where the 4-byte pointer (IP and CS) for the ISR is stored. 📌 Example: For interrupt number 5, the interrupt vector address = 5 × 4 = 20 (0x14). The CPU reads the 4 bytes starting at memory address 20 to get the IP and CS of the ISR.

Returning from the ISR

Every ISA should have an instruction, like the IRET instruction, which should be executed when the ISR terminates. This means that the IRET instruction should be the last instruction of every ISR. This is, in effect, a FAR RETURN in that it restores a number of registers, and flags to their value before the ISR was called. Thus the previous environment is restored after the servicing of the interrupt is completed.

Interrupt Handling

The CPU responds to the interrupt request by completing the current instruction, and then storing the return address from PC into a memory stack. Then the CPU branches to the ISR that processes the requested operation. In general, the following sequence takes place.

Hardware Interrupt Handling:

1. Hardware issues interrupt signal to the CPU.
2. CPU completes the execution of current instruction. CPU acknowledges interrupt.
3. Hardware places the interrupt number on the data bus.
4. CPU determines the address of ISR from the interrupt number available on the data bus.
5. CPU pushes the program status word (flags) on the stack along with the current value of program counter.
6. The CPU starts executing the ISR.
7. After completion of the ISR, the environment is restored; control is transferred back to the main program.

Interrupt Latency

Interrupt Latency is the time needed by the CPU to recognize (not service) an interrupt request. It consists of the time to perform the following:

• Finish executing the current instruction.
• Perform interrupt-acknowledge bus cycles.
• Temporarily save the current environment.
• Calculate the IVT address and transfer control to the ISR.

If wait states are inserted by either some memory module or the device supplying the interrupt type number, the interrupt latency will increase accordingly. Interrupt Latency for external interrupts depends on how many clock periods remain in the execution of the current instruction. On the average, the longest latency occurs when a multiplication, division or a variable-bit shift or rotate instruction is executing when the interrupt request arrives.

Response Deadline

It is the maximum time that an interrupt handler can take between the time when interrupt was requested and when the device must be serviced.

Expanding Interrupt Structure

When there is more than one device that can interrupt the CPU, an Interrupt Controller is used to handle the priority of requests generated by the devices simultaneously.

Interrupt Precedence

Interrupts occurring at the same time (i.e., within the same instruction) are serviced according to a pre-defined priority.

• In general, all internal interrupts have priority over all external interrupts; the single-step interrupt is an exception.
• NMI has priority over INTR if both occur simultaneously.
• The above priority structure is applicable for the recognition of (simultaneous) interrupts. For servicing, the single-step interrupt gets the highest priority, then the NMI, and finally those interrupts that occur last.

Simultaneous Hardware Interrupt Requests

The priority of the devices requesting service at the same time is resolved by using two ways: Daisy-Chained Interrupt and Parallel Priority Interrupt.

Daisy-Chaining Priority:

• The daisy-chaining method to resolve the priority consists of a series connection of the devices in order of their priority.
• Device with maximum priority is placed first and device with least priority is placed at the end.
• The devices interrupt the CPU. The CPU sends acknowledgement to the maximum priority device. If the interrupt was generated by that device, it is serviced. Otherwise, the acknowledgement is passed to the next device.
• If the higher priority devices interrupt continuously, the device with the lower priority is not serviced. So some additional circuitry is also needed to introduce fairness.

Parallel Priority:

• Parallel priority method uses individual bits of a priority encoder.
• The priority of the device is determined by the position of the input of the encoder used for the interrupt.

⭐ Key Takeaways

The central concept of this lecture is that interrupt-driven I/O is far more efficient than polling for interacting with slow peripheral devices, freeing the CPU for other work. A student must understand the different categories of interrupts (internal/external, hardware/software, maskable/non-maskable) and their specific roles. The distinction between vectored and non-vectored interrupts is crucial, especially the use of the Interrupt Vector Table (IVT) and the formula for calculating the IVT address (Interrupt Number × 4) in the 8086/8088. The hardware and software sequence for handling an interrupt, from the signal to execution of the ISR and final restoration via IRET, must be memorized. Finally, the concepts of interrupt latency and response deadline, along with the two priority resolution methods (daisy-chaining and parallel priority), are essential for understanding system performance.

🧠 Quick Revision Questions

1. What is the fundamental difference between how a CPU handles I/O in polling vs. interrupt-driven I/O, and which one is more efficient for keyboards?
2. List the four general categories of interrupts and provide an example of a specific event that would generate each type.
3. How does a vectored interrupt differ from a non-vectored interrupt in determining the starting address of the Interrupt Service Routine?
4. In the Intel 8086/8088, if interrupt number 0x10 (16) occurs, what is the memory address where the CPU finds the pointer to the ISR?
5. Explain the sequence of steps a CPU performs in hardware interrupt handling, starting from the device issuing the interrupt signal to the CPU resuming the main program.

📘 Lecture 28 — Interrupt Hardware and Software

📖 Overview: This lecture covers the hardware and software aspects of interrupt-driven I/O, comparing it with polling and exploring design issues like device identification and priority mechanisms. It provides detailed examples using the SRC and FALCON-A processors to illustrate interrupt handling, including the implementation of interrupt service routines (ISRs) and the hardware logic for interrupt requests and acknowledges.

🗂️ Topics Covered

The lecture begins with a comparison of interrupt-driven I/O and polling, then moves into two key design issues: device identification and priority mechanisms. Device identification is explored through multiple interrupt lines, software poll, and daisy chain techniques, with hardware implications for each. The second half focuses on interrupt handler software, using a detailed FALCON-A example covering both the interrupt hardware and the software components: a dummy calling program, a printer driver, and an interrupt service routine (ISR), including memory maps and RTL for int/iret instructions.

📝 Lecture Summary

Comparison of Interrupt driven I/O and Polling

Interrupt-driven I/O is superior to polling because it saves CPU time that would otherwise be wasted polling the peripheral device for readiness. In polling, the CPU repeatedly questions the device, consuming valuable processing cycles. With interrupts, the device signals the CPU only when it needs service, allowing the CPU to perform other tasks in the meantime.

Design Issues

There are two primary design issues in implementing interrupts: device identification and priority mechanism. Device identification addresses how the CPU knows which device initiated an interrupt. Priority mechanism resolves which interrupt to service first when multiple interrupts occur simultaneously.

Device Identification

Three different mechanisms can be used for device identification:

1. Multiple Interrupt Lines: This is the most straightforward approach, using several dedicated interrupt lines between the CPU and I/O modules. However, it is impractical to have more than a few bus lines or CPU pins for interrupts, so each line often still needs to handle multiple I/O modules, requiring additional techniques to identify the specific device on that line.

2. Software Poll: In this method, the CPU polls to identify the interrupting module and then branches to an interrupt service routine (ISR) once detected. Identification can be done using special commands like a test I/O (where the CPU places the address of a specific I/O module on the address line and checks for a positive response) or by reading the device's status register. Once the correct module is found, the CPU branches to its specific device service routine.

3. Daisy Chain: The wired-OR interrupt signal allows multiple devices to request an interrupt simultaneously, but only one device must receive the acknowledge signal to avoid data bus contention. In a daisy chain, the acknowledge signal passes from one device to the next. For a jth device to receive an acknowledge, the previous device (j-1) must not have an enabled interrupt request. The logic is represented by the equation: 📐 Formula: iack_j = iack_(j-1) ^ ¬(req_(j-1) ∧ enb_(j-1)) → The acknowledge signal passes to the next device only if the previous device did not generate an interrupt (i.e., its interrupt was not enabled). 🔑 Definition — Daisy Chain: A method for handling multiple interrupt requests where the acknowledge signal propagates serially from one device to the next, giving highest priority to the device physically closest to the CPU.

Disadvantages of Software Poll and Daisy Chain

Software poll has the disadvantage of consuming a lot of time because the CPU must individually check each device. Daisy chain is more efficient but has the disadvantage that the device nearest the CPU has the highest priority. To provide fair access, mechanisms like cyclic priority (starting the chain from the device where the CPU finished its last interrupt) can be used.

Interrupt Handler Software

The lecture provides examples using SRC and FALCON-A processors. The FALCON-A example is detailed, with several assumptions: only one interrupt pin is available, so no NMI, nesting, priority, arbitration, or vectored interrupts are possible. The address of the ISR is stored at absolute memory address 2. The printer activates ACKNLG# only when not BUSY.

Interrupt Hardware (FALCON-A Example)

The interrupt request is synchronized using handshaking signals IREQ and IACK. The printer asserts IREQ when ACKNLG# goes low (printer ready for new data) and IRQEN=1. The processor completes the current instruction and then executes the ISR. An inverting tri-state buffer at the D flip-flop's clock input, enabled by IRQEN, ensures additional requests are disabled after the current print job is complete. The CPU's IACK line is connected to the flip-flop's asynchronous reset (R) to prevent the same interrupt request from being presented again. The flip-flop's asynchronous set (S) is permanently connected to logic 1, and its D input is also connected to logic 1, so it is always set synchronously in response to ACKNLG# when IRQEN=1. 💡 Why this matters: This hardware design ensures that interrupts are properly synchronized and that the same interrupt request is not serviced multiple times, preventing spurious or duplicate events.

Interrupt Software (FALCON-A Example)

The software consists of three parts: a Dummy Calling Program, a Printer Driver, and an ISR. The calling program (main program) passes parameters (number of bytes and buffer start address) to the printer driver. The printer driver initializes the printer, sets up the ISR, and ensures no previous print job is in progress. The ISR is invoked to print the first character and subsequent characters, saving and restoring the CPU's environment (registers) using memory locations starting at temp. The int instruction saves the PC into the invisible IPC register and loads the ISR address from memory location 2, setting the interrupt flag (IF) to 0. The iret instruction restores the PC from IPC and sets IF back to 1.

🔑 Definition — Interrupt Service Routine (ISR): A special subroutine invoked by a hardware or software interrupt to service the requesting device. It must save and restore the CPU's environment (registers) and end with an iret instruction. 📐 Formula: int IPC ← PC, PC ← M[2], IF ← 0 → The int instruction stores the current program counter, loads the ISR address from memory location 2, and disables further interrupts. 📐 Formula: iret PC ← IPC, IF ← 1 → The iret instruction restores the program counter and re-enables interrupts. 📌 Example: In the FALCON-A interrupt-driven printer example, the ISR is invoked when the printer is ready for the next character. The ISR tests the BUSY flag once, outputs a character, and updates the buffer pointer and byte count. The memory map shows the ISR can be loaded anywhere, but its address must be stored at memory location 2.

⭐ Key Takeaways

Interrupt-driven I/O is more efficient than polling because it eliminates wasted CPU polling cycles. The two critical design issues are identifying the interrupting device and managing priority among simultaneous interrupts, with techniques like multiple lines, software poll, and daisy chain offering trade-offs in speed and complexity. Hardware handshaking using IREQ/IACK signals is essential for synchronization, and the interrupt hardware must prevent spurious re-triggering using mechanisms like the D flip-flop and reset logic. The interrupt software structure requires a calling program, a driver, and an ISR, with the ISR saving/restoring the CPU environment and using int/iret instructions for context switching. The FALCON-A example demonstrates a practical, simplified interrupt system where only one interrupt is possible, highlighting the essential steps of initialization, first character printing, and subsequent byte-by-byte transfer.

🧠 Quick Revision Questions

1. What is the primary advantage of interrupt-driven I/O over polling?
2. Describe the three methods for device identification discussed in the lecture.
3. What is the formula for the daisy chain acknowledge signal, and what does it represent?
4. What are the two RTL operations of the int and iret instructions in the FALCON-A example?
5. In the FALCON-A printer driver example, what is the purpose of the PB flag and the IRQEN signal?

📘 Lecture 29 — FALSIM

📖 Overview: This lecture introduces FALSIM, the software application combining the FALCON-A assembler and simulator. It covers how to prepare source files for FALSIM, how to use the assembler and simulator features, and essential FALCON-A assembly language programming techniques to overcome addressing limitations.

🗂️ Topics Covered

The lecture covers the introduction to FALSIM including the FALCON-A Assembler and Simulator with their graphical user interfaces and features, preparing source files with proper directives and structure, step-by-step usage of FALSIM for assembling and simulating programs, and FALCON-A assembly language techniques for handling large values, register operations, and bit manipulation.

📝 Lecture Summary

Introduction to FALSIM:

FALSIM is the name of the software application which consists of the FALCON-A assembler and the FALCON-A simulator. It runs under Windows XP.

FALCON-A Assembler:

This tool loads a FALCON-A assembly file with a (.asmfa) extension and parses it. It shows the parsed results in an error log, lets the user view the assembled file’s contents in the file listing and also provides the features of printing the machine code, an Instruction Table and a Symbol Table to a FALCON-A listing file. It also allows the user to run the FALCON-A Simulator.

The FALCON-A Assembler source code has two main modules, the 1st-pass module and the 2nd-pass module. The 1st-pass module takes an assembly file with a (.asmfa) extension and processes the file contents. It then generates a Symbol Table which corresponds to the storage of all program variables, labels and data values in a data structure at the implementation level. The Symbol Table is used by the 2nd-pass module. Failures of the 1st-pass are handled by the assembler using its exception handling mechanism.

The 2nd-pass module sequentially processes the .asmfa file to interpret the instruction op-codes, register op-codes and constants using the Symbol Table. It then produces a list file with a .lstfa extension independent of successful or failed pass. If the pass is successful a binary file with a .binfa extension is produced which contains the machine code for the program contained in the assembly file.

FALCON-A Simulator:

This tool loads a FALCON-A binary file with a (.binfa) extension and presents its contents into different areas of the simulator. It allows the user to execute the program to a specific point within a time frame or just executes it, line by line. It also allows the user to view the registers, I/O port values and memory contents as the instructions execute.

FALSIM Features:

The FALCON-A Assembler provides its user with the following features:

Select Assembly File: Labeled as “1” in Figure 1, this feature enables the user to choose a FALCON-A assembly file and open it for processing by the assembler.

Assembler Options: Labeled as “2” in Figure 1.

• Print Symbol Table: If selected, writes the Symbol Table (produced after the execution of the 1st-pass of the assembler) to a FALCON-A list file with an extension of (.lstfa). The Symbol Table includes variables, addresses and labels with their respective values.
• Print Instruction Table: If selected, writes the FALCON-A instructions along with their op-codes at the end of the list file.

List File: Labeled as “3” in Figure 1, gives a detailed insight of the FALCON-A listing file, produced as a result of the execution of the 1st and 2nd-pass. It shows the Program Counter value in hexadecimal and decimal formats along with the machine code generated for every line of assembly code. These values are printed when the 2nd-pass is completed.

Error Log: Labeled as “4” in Figure 1. It informs the user about the errors and their respective details, which occurs in any of the two passes of the assembler. The size of this window can be changed by dragging the boundary line up or down.

Highlight: Labeled as “5” in Figure 1, helps the user to search for a certain input with the options of searching with “match whole” and “match any” parts of the string. The search also has the option of checking with/without considering “case-sensitivity”. It searches the List File area and highlights the search results using the yellow color. It also indicates the total number of matches found.

Start Simulator: Labeled as “6” in Figure 1. The FALCON-A Simulator is run using the FALCON-A Assembler’s “Start Simulator” option. Its features are detailed as follows:

Load Binary File: The button labeled as “11” in Figure 6, allows the user to choose and open a FALCON-A binary file with a (.binfa) extension. When a file is being loaded into the simulator all the register, constants (if any) and memory values are set.

Registers: The area labeled as “12” in Figure 6 enables the user to see values present in different registers before, during and after execution.

Instruction: This area is labeled as “13” in Figure 6 and contains the value of PC, address of an instruction, its representation in Assembly, the Register Transfer Language, the op-code and the instruction type.

I/O Ports: I/O ports are labeled as “14” in Figure 6. These ports are available for the user to enter input operation values and visualize output operation values whenever an I/O operation takes place in the program. The input value for an input operation is given by the user before an instruction executes. The output values are visible in the I/O port area once the instruction has successfully executed.

Memory: The memory is divided into two areas and is labeled as “15” in Figure 6, to facilitate the view of data stored at different memory locations before, during and after program execution.

Processor’s State: Labeled as “16” in Figure 6, this area shows the current values of the Instruction Register and the Program Counter while the program executes.

Highlight: The highlight option for the FALCON-A simulator is labeled as “17” in Figure 6. It offers to highlight the search string which is entered as an input, with the “All“ and “Part“ option. The results of the search are highlighted using the yellow color. It also indicates the total number of matches.

The following is a description of the options available on the button panel labeled as “18” in Figure 6:

Single Step: Lets the user execute the program, one instruction at a time. The next instruction is not executed unless the user does a “single step” again. By default, the instruction to be executed will be the one next in the sequence. It changes if the user specifies a different PC value using the Change PC option.

Change PC: This option lets the user change the value of PC (Program Counter). By changing the PC the user can execute the instruction to which the specified PC points. The value in the PC must be an even address.

Execute: By choosing this button, the user is able to execute the loaded program with the options of execution with/without breakpoint insertion. In case of breakpoint insertion, the user has the option to choose from a list of valid breakpoint values. It also has the option to set a limit on the time for execution. This “Max Execution Time” option restricts the program execution to a time frame specified by the user.

Change Register: Using the Change Register feature, the user can change the value present in a particular register.

Change Memory Word: This feature enables the user to change values present at a particular memory location.

Display Memory: Shows an updated memory area, after a particular memory location other than the pre-existing ones is specified by the user.

Change I/O: Allows the user to give an I/O port value if the instruction to be executed requires an I/O operation. Giving in the input in any one of the I/O ports areas before instruction execution, indicates that a particular I/O operation will be a part of the program and it will have an input from some source. The value given by the user indicates the input type and source.

Display I/O: Works in a manner similar to Display Memory. Here the user specifies the starting index of an I/O port. This features displays the I/O ports stating from the index specified.

2. Preparing Source Files for FALSIM:

In order to use the FALCON-A assembler and simulator, FALSIM, the source file containing assembly language statements and directives should be prepared according to the following guidelines:

• The source file should contain ASCII text only. Each line should be terminated by a carriage return. The extension .asmfa should be used with each file name. After assembly, a list file with the original filename and an extension .lstfa, and a binary file with an extension .binfa will be generated by FALSIM.

• Comments are indicated by a semicolon (;) and can be placed anywhere in the source file. The FALSIM assembler ignores any text after the semicolon.

• Names in the source file can be of one of the following types:

  • Variables: These are defined using the .equ directive. A value must also be assigned to variables when they are defined.
  • Addresses in the “data and pointer area” within the memory: These can be defined using the .dw or the .sw directive. The difference between these two directives is that when .dw is used, it is not possible to store any value in the memory. The integer after .dw identifies the number of memory words to be reserved starting at the current address. (The directive .db can be used to reserve bytes in memory.) Using the .sw directive, it is possible to store a constant or the value of a name in the memory. It is also possible to use pointers with this directive to specify addresses larger than 127. Data tables and jump tables can also be set up in the memory using this directive.
  • Labels: An assembly language statement can have a unique label associated with it. Two assembly language statements cannot have the same name. Every label should have a colon (:) after it.

• Use the .org 0 directive as the first line in the program. Although the use of this line is optional, its use will make sure that FALSIM will start simulation by picking up the first instruction stored at address 0 of the memory. (Address 0 is called the reset address of the processor). A jump [first] instruction can be placed at address 0, so that control is transferred to the first executable statement of the main program. Thus, the label first serves as the identifier of the “entry point” in the source file. The .org directive can also be used anywhere in the source file to force code at a particular address in the memory.

• Address 2 in the memory is reserved for the pointer to the Interrupt Service Routine (ISR). The .sw directive can be used to store the address of the first instruction in the ISR at this location.

• Address 4 to 125 can be used for addresses of data and pointers. However, the main program must start at address 126 or less, otherwise FALSIM will generate an error at the jump [first] instruction.

• The main program should be followed by any subprograms or procedures. Each procedure should be terminated with a ret instruction. The ISR, if any, should be placed after the procedures and should be terminated with the iret instruction.

• The last line in the source file should be the .end directive.

• The .equ directive can be used anywhere in the source file to assign values to variables.

• It is the responsibility of the programmer to make sure that code does not overwrite data when the assembly process is performed, or vice versa. As an example, this can happen if care is not exercised during the use of the .org directive in the source file.

3. Using FALSIM:

• To start FALSIM (the FALCON-A assembler and simulator), double click on the FALSIM icon. This will display the assembler window, as shown in Figure 1.
• Select one or both assembler options shown on the top right corner of the assembler window labeled as “2”. If no option is selected, the symbol table and the instruction table will not be generated in the list (.lstfa) file.
• Click on the select assembly file button labeled as “1”. This will open the dialog box as shown in Figure 2.
• Select the path and file containing the source program that is to be assembled.
• Click on the open button. FALSIM will assemble the program and generate two files with the same filename, but with different extensions. A list file will be generated with an extension .lstfa, and a binary (executable) file will be generated with an extension .binfa. FALSIM will also display the list file and any error messages in two separate panes, as shown in Figure 3.
• Double clicking on any error message highlights and displays the corresponding erroneous line in the program listing window pane for the user. This is shown in Figure 4. The highlight feature can also be used to display any text string, including statements with errors in them. If the assembler reported any errors in the source file, then these errors should be corrected and the program should be assembled again before simulation can be done. Additionally, if the source file had been assembled correctly at an earlier occasion, and a correct binary (.binfa) file exists, the simulator can be started directly without performing the assembly process.
• To start the simulator, click on the start simulation button labeled as “6”. This will open the dialog box shown in Figure 6.
• Select the binary file to be simulated, and click Open as shown in Figure 7. (It is also possible to open the file by double clicking on the file name in the “Open” window).
• This will open the simulation window with the executable program loaded in it as shown in Figure 8. Notice that the first instruction at address 0 is ready for execution. All registers are initialized to 0. The memory contains the address of the ISR (i.e., 64h which is 100 decimal) at location 2 and the address of the printer driver at location 4. These two addresses are determined at assembly time in our case. In a real situation, these addresses will be determined at execution time by the operating system, and thus the ISR and the printer driver will be located in the memory by the operating system (called re-locatable code). Subsequent memory locations contain constants defined in the program.
• Click single step button labeled as “19”. FALSIM will execute the jump [main] instruction at address 0 and the PC will change to 20h (32 decimal), which is the address of the first instruction in the main program (i.e., the value of main).
• Clicking on the single step button twice, executes the next two instructions.
• The execution of the call instruction simulates the event of a print request by the user. This transfers control to the printer driver. Thus, when the call r4, r6 instruction is single stepped, the PC changes to 32h (50 decimal) for executing the first instruction in the printer driver.
• Double click on memory location 000A, which is being used for holding the PB (printer busy) flag. Enter a 1 and click the change memory button. This will store a 0001 in this location, indicating that a previous print job is in progress. Now click single step and note that this value is brought from memory location 000E into register r1. Clicking single step again will cause the jnz r1, [message] instruction to execute, and control will transfer to the message routine at address 0046h.
• Click again on the single step button. Note that when the ret r4 instruction executes, the value in r4 (i.e., 28h) is brought into the PC. The blue highlight bar is placed on the next instruction after the call r4, r6 instruction in the main program. In case of the dummy calling program, this is the halt instruction.
• Double click on the value of the PC labeled as “20”. This will open a dialog box. Enter a value of the PC (i.e. 26h) corresponding to the call r4, r6 instruction, so that it can be executed again. A “list” of possible PC values can also be pulled down using, and 0026h can be selected from there as well.
• Click single step again to enter the printer driver again.
• Change memory location 000A to a 0, and then single step the first instruction in the printer driver. This will bring a 0 in r1, so that when the next jnz r1, [message] instruction is executed, the branch will not be taken and control will transfer to the next instruction after this instruction. This is movi r1, 1 at address 0036h.
• Continue single stepping.
• Notice that a 1 has been stored in memory location 000A, and r1 contains 11h, which is then transferred to the output port at address 3Ch (60 decimal) when the out r1, controlp instruction executes. This can be verified by double clicking on the top left corner of the I/O port pane, and changing the address to 3Ch. Another way to display the value of an I/O port is to scroll the I/O window pane to the desired position.
• Continue single stepping till the int instruction and note the changes in different panes of the simulation window at each step.
• When the int instruction executes, the PC changes to 64h, which is the address of the first instruction in the ISR. Clicking single step executes this instruction, and loads the address of temp (i.e., 0010h) which is a temporary memory area for storing the environment. The five store instructions in the ISR save the CPU environment (working registers) before the ISR change them.
• Single step through the ISR while noting the effects on various registers, memory locations, and I/O ports till the iret instruction executes. This will pass control back to the printer driver by changing the PC to the address of the jump [finish] instruction, which is the next instruction after the int instruction.
• Double click on the value of the PC. Change it to point to the int instruction and click single step to execute it again. Continue to single step till the in r1, statusp instruction is ready for execution.
• Change the I/O port at address 3Ah (which represents the status port at address 58) to 80 and then single step the in r1, statusp instruction. The value in r1 should be 0080.
• Single step twice and notice that control is transferred to the movi r7, FFFF instruction, which stores an error code of –1 in r1. (Note: The instruction was originally movi r7, -1. Since it was converted to machine language by the assembler, and then reverse assembled by the simulator, it became movi r7, FFFF. This is because the machine code stores the number in 16-bits after sign-extension. The result will be the same in both cases.)

4. FALCON-A assembly language programming techniques:

• If a signed value, x, cannot fit in 5 bits (i.e., it is outside the range -16 to +15), FALSIM will report an error with a load r1, [x] or a store r1, [x] instruction. To overcome this problem, use movi r2, x followed by load r1, [r2].

🔑 Definition — Memory-register-indirect addressing: A technique using two loads where the address is first stored in memory using .sw, then loaded into a register, then used as a pointer for the final load.

• If a signed value, x, cannot fit in 8 bits (i.e., it is outside the range -128 to +127), even the previous scheme will not work. FALSIM will report an error with the movi r2, x instruction. The following instruction sequence should be used to overcome this limitation of the FALCON-A. First store the 16-bit address in the memory using the .sw directive. Then use two load instructions as shown below:

  a:  .sw x
  load r2, [a]
  load r1, [r2]
  

  This is essentially a “memory-register-indirect” addressing. It has been made possible by the .sw directive. The value of a should be less than 15.
• A similar technique can be used with immediate ALU instructions for large values of the immediate data, and with the transfer of control (call and jump) instructions for large values of the target address.

📐 Formula: Technique for large 16-bit values → Use multiplication and addition to construct the value in a register.

📌 Example: To bring a 201 in register r1:

movi r2, 10
movi r3, 20
mul r1, r2, r3    ; r1 contains 200 after this instruction
addi r1, r1, 1   ; r1 now contains 201

• Moving from one register to another can be done by using the instruction addi r2, r1, 0.
• Bit setting and clearing can be done using the logical (and, or, not, etc) instructions.
• Using shift instructions (shiftl, asr, etc.) is faster than mul and div, if the multiplier or divisor is a power of 2.

⭐ Key Takeaways

The FALSIM tool consists of a two-pass assembler and a simulator for FALCON-A architecture. Students must remember the proper file structure: source files use .asmfa extension, produce .lstfa list files and .binfa binary executables. The memory map is critical — address 0 is the reset address, address 2 holds the ISR pointer, addresses 4-125 are for data/pointers, and the main program must start at address 126 or less. For handling large values that exceed the 5-bit or 8-bit immediate fields, programmers must use memory-indirect addressing with .sw directives or construct values using multiplication and addition. The simulator provides single-step execution, register/memory/I/O viewing, breakpoints, and PC modification for debugging.

🧠 Quick Revision Questions

1. What are the two main modules of the FALCON-A Assembler, and what does each produce?
2. What is the difference between the .dw and .sw directives when preparing a FALSIM source file?
3. Why must the main program start at address 126 or less in FALCON-A?
4. How would you load a 16-bit value (e.g., 5000) into a register when movi cannot accommodate it?
5. What is the purpose of address 2 in the FALCON-A memory map?

📘 Lecture 30 — Interrupt Priority and Nested Interrupts

📖 Overview: This lecture examines how interrupt systems handle multiple I/O devices through priority mechanisms and nested interrupts. It quantifies the performance trade-offs between different I/O methods—polling, interrupt-driven, and Direct Memory Access (DMA)—through a series of detailed numerical examples, demonstrating why DMA is essential for high-speed data transfers.

🗂️ Topics Covered

The lecture begins with Nested Interrupts and Interrupt Masks, then presents six worked examples comparing CPU overhead for polling versus interrupt-driven I/O across different device speeds (hard drive, floppy drive, keyboard). It concludes with a detailed explanation of Direct Memory Access (DMA), its advantages and disadvantages, and how it eliminates the CPU as a bottleneck for high-speed block transfers.

📝 Lecture Summary

Nested Interrupts

(Read from Book, Jordan Page 391)

Interrupt Mask

(Read from Book, Jordan Page 391)

Priority Mask

(Read from Book, Jordan Page 392)

Examples

Example #1 — Polling Overhead for Three Devices

Three I/O devices are connected to a 32-bit, 10 MIPS CPU. A hard drive (1MB/sec, 32-bit bus), a floppy drive (25KB/sec, 16-bit bus), and a keyboard (polled 30 times/sec). Each polling operation requires 20 instructions per device.

Hard Drive: Transfers 1MB/sec = 250 × 2¹⁰ 32-bit words/sec. Polling requires 250 × 2¹⁰ × 20 = 5,120,000 instructions/sec. CPU time = (5.12 × 10⁶) / (10 × 10⁶) = 51.2%.

Floppy Drive: Transfers 12.5 × 2¹⁰ half-words/sec. Polling requires 12.5 × 2¹⁰ × 20 = 256,000 instructions/sec. CPU time = (0.256 × 10⁶) / (10 × 10⁶) = 2.56%.

Keyboard: 30 × 20 = 600 instructions/sec. CPU time = 600 / (10 × 10⁶) = 0.006%.

💡 Why this matters: Polling is acceptable for low-speed devices (keyboard, floppy) but consumes over half the CPU for a hard drive, making it impractical for high-data-rate devices.

Example #2 — Polling Frequency and Delay

a. To achieve an average delay of at most 10 ms, the processor polls every 20 ms (50 times/sec) because average wait = half the polling interval.

b. With 10,000 cycles per poll and a 100 MHz processor: 50 × 10,000 = 500,000 cycles/sec. CPU time = (0.5 × 10⁶) / (100 × 10⁶) = 0.5%.

c. For 1 ms average delay: poll every 2 ms (500 times/sec). 500 × 10,000 = 5,000,000 cycles/sec. CPU time = 5 / 100 = 5%.

Example #3 — Printer Polling in a Busy Wait Loop

A 20 MIPS processor drives an 80-character line printer (1 ms/char). Total 565 instructions to print a line, with 2 instructions in the polling loop per character (80 × 2 = 160 instructions for polling).

Remaining 405 instructions take 405 / (20 × 10⁶) = 20.25 μsec. Printing 80 chars takes 80 ms. Time spent in polling loop = 80 - 0.02025 = 79.97 ms. This is 79.97/80 = 99.96% of total time.

Example #4 — Maximum Devices with Interrupts

A 20 MIPS processor has devices at 1000 chars/sec. Interrupt handling takes 17 instructions + 1 μsec hardware response.

Service time per character = 17/(20 × 10⁶) + 1 μsec = 1.85 μsec. Each device requires 1.85 ms handling per second. Maximum devices = 1 / (1.85 × 10⁻³) = 540.

Example #5 — Interrupt Overhead for Floppy Drive

A floppy (25KB/sec, 16-bit bus) on a 32-bit, 10 MIPS CPU using interrupt-driven I/O. Interrupt overhead = 20 instructions. Transfer rate = 12.5 × 2¹⁰ half-words/sec. Overhead = 12.5 × 2¹⁰ × 20 = 256,000 instructions/sec.

Example #6 — Interrupts vs. Polling Comparison

A 500 MHz processor requires 1000 cycles per context switch. ISR = 10,000 cycles. Device makes 200 interrupts/sec. Polling every 0.5 ms during idle, 500 cycles per poll.

a. Cycles/sec with only interrupts: each interrupt = 10,000 + 2 × 1000 = 12,000 cycles. Total = 200 × 12,000 = 2,400,000 cycles/sec.

b. Fraction of CPU = 2,400,000 / (500 × 10⁶) = 0.48%.

c. With interrupts + polling: Each interrupt takes 12,000 cycles / (500 × 10⁶) = 24 μsec. For 200 interrupts: 4.8 ms. Remaining 995.2 ms for polling = 1990 polls × 500 cycles = 995,000 cycles. Total = 2,400,000 + 995,000 = 3,395,000 cycles/sec.

d. Interrupt overhead = 200 × 2000 = 400,000 cycles/sec. Polling overhead = 500 cycles/poll. Equal overhead → 400,000/500 = 800 polls/sec, or every 1.25 ms.

Direct Memory Access (DMA)

Direct Memory Access (DMA) is a technique where the CPU passes control of the system bus to a memory subsystem or peripheral, enabling direct transfer of a contiguous block of data between peripherals and memory without CPU intervention.

Advantage of DMA

The transfer rate is very fast because the system bus is isolated via tri-state buffers, establishing a direct connection between I/O and memory while the CPU is free. DMA is ideal for large data transfers (e.g., hard disk to printer). Compared to interrupt-driven I/O or programmed I/O, DMA is much faster. It requires a DMA controller, which acts as a specialized CPU for synchronizing data transfer.

Example of DMA

The instruction load [2], [9] is illegal in SRC because it requires two steps: load r1, [9] then store r1, [2]. Similarly, out [6], datap must be done as load r1, [6] then out r1, datap. The CPU acts as an unnecessary middleman, causing every data word to travel over the system bus twice, limiting transfer speed.

DMA Approach

The DMA approach electrically disconnects the CPU from the system bus (via tri-state buffers), allowing a peripheral or memory subsystem to communicate directly. This achieves higher transfer rates, approaching the memory's own speed limit.

Disadvantage of DMA

An additional DMA controller is required, making the system more complex and expensive. DMA requests have priority over all other bus activities, including interrupts—no interrupts are recognized during a DMA cycle.

🔑 Definition — Direct Memory Access (DMA): A technique where the CPU passes bus control to allow direct data transfer between I/O and memory without CPU intervention, using a DMA controller for synchronization.

⭐ Key Takeaways

For exam purposes, you must remember that polling is only practical for slow devices (like keyboards) and becomes prohibitively expensive for high-speed devices (like hard drives), where it can consume over 50% of CPU time. Interrupt-driven I/O reduces overhead but still requires CPU cycles for context switching and service routines. DMA eliminates the CPU bottleneck entirely for block transfers, achieving the highest data rates at the cost of additional hardware complexity. The key formulas to master involve calculating CPU utilization as (instructions or cycles for I/O) divided by (total instructions or cycles per second). Always account for both polling frequency (delay = half the interval) and interrupt overhead (context switch + ISR execution) when solving these performance problems.

🧠 Quick Revision Questions

1. What is the average delay between a device request and its servicing when polling is used every 20 ms?
2. For a 20 MIPS processor, what percentage of CPU time is spent polling a floppy drive requiring 256,000 instructions per second?
3. How many cycles per second does a single device interrupt consume if the ISR takes 10,000 cycles and each context switch takes 1000 cycles?
4. What is the primary advantage of DMA over interrupt-driven I/O for high-speed data transfers?
5. Why does polling become impractical for devices with high data transfer rates (e.g., hard drives)?

📘 Lecture 31 — Direct Memory Access (DMA)

📖 Overview: This lecture introduces Direct Memory Access (DMA), a technique that allows peripherals to transfer data directly to/from memory without CPU intervention. It explains why DMA achieves higher transfer rates than programmed or interrupt-driven I/O, and covers DMA configurations, protocols, cycle stealing, and I/O channels. Understanding DMA is critical for designing high-performance I/O systems.

🗂️ Topics Covered

The lecture covers DMA definition, advantages and disadvantages, the reason for DMA (CPU as unnecessary middleman), master/slave component definitions, cycle stealing, the three-step data transfer process, DMA transfer protocol with bus request/grant, DMA priority over interrupts, three DMA configurations (single bus detached, single bus integrated, I/O bus), worked examples calculating CPU time with and without DMA, I/O processors vs. I/O channels, types of channels (selector, multiplexer with byte/block multiplexer), virtual and physical addresses, DMA and memory system problems, and three hardware/software solutions for cache coherence.

📝 Lecture Summary

Introduction

Direct Memory Access (DMA) is a technique that allows a peripheral to read from and/or write to memory without intervention by the CPU. It is a simple form of bus mastering where the I/O device is set up by the CPU to transfer one or more contiguous blocks of memory. After the transfer is complete, the I/O device gives control back to the CPU. Possible DMA transfer combinations include: memory to memory, memory to peripheral, peripheral to memory, and peripheral to peripheral.

The DMA approach is to "turn off" (tri-state and electrically disconnect) the CPU and let a peripheral device communicate directly with memory or another peripheral.

🔑 Advantage: Higher transfer rates (approaching that of memory) can be achieved.
🔑 Disadvantage: A DMA Controller (DMAC) is needed, making the system complex and expensive.

Generally, DMA requests have priority over all other bus activities, including interrupts. No interrupts may be recognized during a DMA cycle.

💡 Why this matters: DMA offloads the CPU from time-consuming I/O data transfers, freeing it to perform other computation.

Reason for DMA

The instruction load [2], [9] is illegal. Symbols [2] and [9] represent memory locations. This transfer must be done in two steps: load r1, [9] then store r1, bx. Thus, it is not possible to transfer from one memory location to another without involving the CPU. The same applies to transfers between memory and peripherals connected to I/O ports. For example, out [6], datap is illegal; it requires: load r1, [6] then out r1, datap. Similar comments apply to the in instruction.

Thus, the real cause of the limited transfer rate is the CPU itself. It acts as an unnecessary "middleman". Every data word travels over the system bus twice.

Some Definitions

🔑 Master Component: A component connected to the system bus and having control of it during a particular bus cycle.
🔑 Slave Component: A component connected to the system bus with which the master component can communicate during a particular bus cycle. Normally the CPU with its bus control logic is the master component.
🔑 Qualifications to Become a Master: Must have the capability to place addresses on the address bus and direct bus activity during a bus cycle.
🔑 Qualified Components: Processors with their associated bus control logic, and DMA controllers.
🔑 Cycle Stealing: Taking control of the system bus for a few bus cycles.

Data Transfer Using DMA

Data transfer using DMA takes place in three steps:

1st Step: The processor issues a command to the DMA controller with: operation to be performed (read or write), address of I/O device, address of memory block, and size of data to be transferred. After this, the processor becomes free and may perform other tasks.

2nd Step: The entire block of data is transferred directly to or from memory by the DMA controller.

3rd Step: At the end of the transfer, the DMA controller informs the processor by sending an interrupt signal.

The DMA Transfer Protocol

Most processors have a separate line over which an external device can send a request for DMA. Common names include HOLD, RQ, or Bus Request (BR).

The DMA cycle begins with the alternate bus master requesting the system bus by activating the Bus Request line. The CPU completes the current bus cycle (as in interrupts) and responds by floating the address, data, and control lines. A Bus Grant pulse is then output by the CPU to the requesting device. After receiving the Bus Grant pulse and waiting for the CPU's "float delay", the requesting device may drive the system bus to prevent bus contention. To return control to the CPU, the alternate bus master relinquishes bus control and issues a release pulse on the same Bus Request line.

DMA Has Priority Over Interrupt Driven I/O

In interrupt driven I/O, the transfer depends on the speed at which the processor tests and services a device, and many instructions are required per I/O transfer. These factors become a bottleneck for large data blocks. In DMA, I/O transfers occur without CPU intervention; the CPU pauses for only one bus cycle. Therefore, DMA is more efficient for I/O transfers.

DMA Configurations

Single Bus Detached DMA: A single bidirectional bus connects processor, memory, DMA module, and all I/O modules. When an I/O module needs DMA, it requests permission; if granted, it sends read/write address and data size to the DMA module. The I/O module then transfers its contiguous block to/from main memory. The processor cannot execute during the transfer (single bus), but DMA is much faster than processor-mediated transfers.

Single Bus Integrated DMA: The DMA and one or more I/O modules are integrated without the system bus; the DMA may function as part of an I/O module or as a separate module controlling the I/O module.

I/O Bus: The DMA and I/O modules are integrated through an I/O bus, reducing the number of I/O interfaces required between the DMA and I/O modules.

Example 1

An I/O device transfers data at 10MB/s over a 100MB/s bus. Data is transferred in 4KB blocks. The processor operates at 500MHz, and it takes 5000 cycles to handle each DMA request. Find the fraction of CPU time handling the data transfer with and without DMA.

📐 Without DMA: The processor copies data into memory as sent over the bus. Since the I/O device sends data at 10MB/s over the 100MB/s bus, 10% of each second is spent transferring data. Thus, 10% of CPU time is spent copying data.

📐 With DMA:
Number of DMA requests per second = 10MB / 4KB = 10,000,000 bytes / 4096 bytes = 2441.41 ≈ 2500 requests/sec
Total cycles for DMA handling = 2500 requests × 5000 cycles/request = 12,500,000 cycles
CPU clock = 500 MHz = 500 × 10⁶ cycles/sec
Fraction of CPU time = 12,500,000 / (500 × 10⁶) = 0.025 = 2.5%

Example 2

A hard drive with max transfer rate 1MB/s is connected to a 32-bit, 10MIPS CPU at 100 MHz. The DMA-based I/O interface takes 500 clock cycles for CPU to set up DMA, plus 300 clock cycles for interrupt handling at end. Data transfer uses 2KB blocks. Calculate percentage of CPU time consumed handling the hard drive.

📐 Solution:
Blocks transferred per second = 1MB / 2KB = 1000 KB / 2 KB = 500 blocks/sec
Cycles per DMA transfer = 500 + 300 = 800 cycles
Total cycles per second = 500 × 800 = 400,000 cycles/sec
CPU clock = 100 MHz = 100 × 10⁶ cycles/sec
Percentage = (400 × 10³) / (100 × 10⁶) = 4 × 10⁻³ = 0.4%

💡 Why this matters: In real scenarios, the drive is not active all the time, so actual CPU consumption is much smaller than 0.4%. If cache memory is used, it can free up main memory for the DMAC.

Cycle Stealing

The DMA module takes control of the bus to transfer data to/from memory by forcing the CPU to temporarily suspend its operation. This is called Cycle Stealing because the DMA steals a bus cycle. The CPU suspends for one bus cycle, transfers data, then returns control to the CPU.

I/O Processors

When an I/O module has its own local memory to control a large number of I/O devices without CPU involvement, it is called an I/O processor.

I/O Channels

When an I/O module can execute a specific set of instructions for specific I/O devices in memory without CPU involvement, it is called an I/O channel.

Types of I/O Channels

🔑 Selector Channel: A DMA controller that can do block transfers for several devices but only one at a time.
🔑 Multiplexer Channel: A DMA controller that can do block transfers for several devices at once.

Types of Multiplexer Channel

Byte Multiplexer: Accepts or transmits characters; interleaves bytes from several devices; used for low-speed devices.
Block Multiplexer: Accepts or transmits blocks of characters; interleaves blocks from several devices; used for high-speed devices.

Virtual Address vs. Physical Address

🔑 Virtual Address: Generated logically by the memory management unit for translation.
🔑 Physical Address: The actual address in memory.

DMA and Memory System

DMA disturbs the relationship between the memory system and CPU. Without DMA, all memory accesses are handled by the CPU using address translation and cache mechanisms. With DMA, memory accesses can occur without CPU address translation and cache access, creating problems in virtual memory and cache systems.

Hardware Software Interface Solutions

Solution 1: All I/O transfers are made through the cache to ensure modified data are read and updated in the cache on I/O write. This can decrease processor performance due to infrequent I/O data usage.

Solution 2: Cache is invalidated for I/O read; for I/O write, write-back (flushing) is forced by the operating system. This is more efficient because flushing large cache portions only occurs on DMA block accesses.

Solution 3: Flush cache entries using a hardware mechanism, used in multiprogramming systems to keep cache coherent.

Some Clarifications

• "Serial" and "parallel" refer to computer I/O ports, not the CPU. The CPU always transfers data in parallel.
• "Programmed I/O", "Interrupt driven I/O", and "DMA" refer to how the CPU handles I/O or controls data flow through ports.
• "Simplex" and "duplex" refer to the transmission medium or communication link.
• "Memory mapped I/O" and "Independent I/O" refer to mapping of the interface (CPU control lines used in the interface).

⭐ Key Takeaways

1. DMA allows peripherals to transfer data directly to/from memory without CPU intervention, achieving higher transfer rates by eliminating the CPU as a "middleman" and reducing data bus travel from two passes to one.
2. The DMA transfer process consists of three steps: CPU setup (providing operation, addresses, and block size), block transfer by DMAC, and interrupt notification upon completion. During setup, the CPU becomes free for other tasks.
3. DMA configurations include single bus detached, single bus integrated, and I/O bus architectures; DMA has priority over interrupt-driven I/O, and uses cycle stealing where the CPU suspends for one bus cycle per transfer.
4. DMA introduces cache coherence and virtual memory problems because it bypasses CPU address translation and cache mechanisms; solutions include transferring through cache, OS-managed invalidation/flushing, and hardware cache flushing.
5. I/O channels extend DMA capability: selector channels handle one device at a time, while multiplexer channels (byte or block) handle multiple devices simultaneously, with byte multiplexers for low-speed and block multiplexers for high-speed devices.

🧠 Quick Revision Questions

1. What are the three possible data transfer directions in DMA?
2. In the three-step DMA transfer process, what information does the CPU provide to the DMA controller in the first step?
3. What is cycle stealing and how does it affect CPU operation during a DMA transfer?
4. Calculate the percentage of CPU time used for DMA if a device transfers 5MB/s in 1KB blocks, each DMA request takes 2000 cycles, and the CPU runs at 400 MHz.
5. What is the difference between a selector channel and a multiplexer channel in I/O channel architecture?

📘 Lecture 32 — Magnetic Disk Drives

📖 Overview: This lecture covers the fundamental structure and operation of magnetic hard disk drives, including their static and dynamic properties. It explains how data is organized on disks, the mechanical delays involved in reading and writing data, and compares hard disks with flash memory and semiconductor memory.

🗂️ Topics Covered

The lecture covers hard disk structure including platters, tracks, and sectors; static properties like storage capacity; dynamic properties including seek time, rotational latency, and transfer rate; overhead time and controller delays; several worked examples calculating disk access times; mechanical delays in embedded systems and flash memory as an alternative; and a comparison between semiconductor memory and hard disks based on cost and latency.

📝 Lecture Summary

Hard Disk

A hard disk is the most frequently used peripheral device. It consists of a set of platters. Each platter is divided into tracks, and each track is subdivided into sectors. To identify each sector, an address is needed. Before the actual data, there is a header consisting of a few bytes (e.g., 10 bytes). Along with the header there is a trailer. Every sector has three parts: a header, a data section, and a trailer.

Static Properties

The storage capacity can be determined from the number of platters and the number of tracks. To keep the density the same for the entire surface, the trend is to use more sectors for outer tracks and fewer sectors for inner tracks.

Dynamic Properties

When data needs to be read from a particular location on the disk, the head moves toward the selected track. This process is called seek. The disk is constantly rotating at a fixed speed. After a short time, the selected sector moves under the head. This interval is called the rotational delay. On average, the data may be available after half a revolution. Therefore, the rotational latency is half a revolution.

The time required to seek a particular track is defined by the manufacturer. Maximum, minimum, and average seek times are specified. Seek time depends upon the present position of the head and the position of the required sector. For calculations, the average value of the seek time is used.

Transfer rate: When a particular sector is found, the data is transferred to an I/O module. This depends on the transfer rate, typically between 30 and 60 MBytes/sec, as defined by the manufacturer.

Overhead time: A request may not find the hard disk immediately available, causing a queuing delay. The hard disk controller (electronics on a printed circuit board on the hard disk) takes time called overhead time.

Example 1

Find the average rotational latency if the disk rotates at 20,000 rpm. Solution: Average latency to the desired data is halfway around the disk. Average rotational latency = 0.5 / (20,000 / 60) = 1.5 ms

Example 2

A magnetic disk has an average seek time of 5 ms. Transfer rate is 50 MB/sec. Disk rotates at 10,000 rpm. Controller overhead is 0.2 msec. Find the average time to read or write 1024 bytes. Solution: Average Tseek = 5 ms. Average Trot = 0.5 * 60 / 10,000 = 3 ms. Ttransfer = 1KB / 50MB = 0.02 ms. Tcontroller = 0.2 ms. Total time = Tseek + Trot + Ttransfer + Tcontroller = 5 + 3 + 0.02 + 0.2 = 8.22 ms

Example 3

A hard disk with 5 platters has 1024 tracks per platter, 512 sectors per track, and 512 bytes/sector. What is the total capacity? Solution: 512 bytes × 512 sectors = 0.2 MB/track. 0.2 MB × 1024 tracks = 0.2 GB/platter. Total capacity = 5 × 0.2 = 1 GB

Example 4

How many platters are required for a 40 GB disk if there are 1024 bytes/sector, 2048 sectors per track, and 4096 tracks per platter? Solution: Capacity of one platter = 1024 × 2048 × 4096 = 8 GB. For 40 GB, need 40 / 8 = 5 platters

Example 5

Consider a hard disk that rotates at 3000 rpm. Seek time to move between adjacent tracks is 1 ms. There are 64 sectors per track stored in linear order. Read/write head is initially at start of sector 1 on track 7. a. How long to transfer sector 1 on track 7 to sector 1 on track 9? Solution: Time for one revolution = 60/3000 = 20 ms. Time to read or write one sector = 20 / 64 = 0.31 ms/sector. Head movement time from track 7 to track 9 = 1 ms × 2 = 2 ms. After reading sector 1 on track 7 (0.31 ms), an additional 19.7 ms rotational delay is needed to line up with sector 1 again. Total time = 0.31 + 19.7 + 0.31 = 20.3 ms

b. How long to transfer all sectors on track 12 to corresponding sectors on track 13? Solution: Time to read or write an entire track = 20 ms. Head movement time = 1 ms (time for approximately 4 sectors to pass under head). After reading track 12 and repositioning, head is on track 13 at 4 sectors past initial sector read. Total transfer time = 20 + 1 + 20 = 41 ms (or 60 ms if writing starts at first sector)

Example 6

Calculate time to read 64 KB (128 sectors) with these parameters: 180 GB, 3.5 inch disk, 12 platters, 24 surfaces, 7,200 RPM (4 ms avg. latency), 6 ms avg. seek, 64 to 35 MB/s (internal), 0.1 ms controller time. Solution: Disk latency = 6 ms + 0.5 × 1/(7200 RPM/(60000 ms/M)) + 64 KB/(64 MB/s) + 0.1 ms = 6 + 4.2 + 1.0 + 0.1 = 11.3 ms

Mechanical Delay and Flash Memory

Mechanical movement in data transfer causes mechanical delays, undesirable in embedded systems. To overcome this, flash memory is used. Flash memory is a type of electrically erasable PROM. Each cell consists of two MOSFETs with a control gate between them; the presence or absence of charge indicates a 0 or 1.

The basic idea is to reduce control overheads, which are low for flash chips. Flash memory has low power dissipation. For embedded devices, flash is a better choice than hard disk. Read time is small for flash, but write time may be significant because memory must first be erased before writing. However, in embedded systems, the number of write operations is less, so flash remains a good choice.

Example 7

Calculate time to read 64 KB for the previous disk, using 1/3 of quoted seek time and 3/4 of internal outer track bandwidth. Solution: Disk latency = (0.33 × 6 ms) + 0.5 × 1/(7200 RPM) + 64 KB/(0.75 × 64 MB/s) + 0.1 ms = 2 + 4.2 + 1.3 + 0.1 = 7.6 ms

Semiconductor Memory vs. Hard Disk

At one time, developers thought semiconductor memory would completely replace hard disks. Two important features to consider:

1. Cost: Lower for hard disk compared to semiconductor memory.
2. Latency: Hard disk latency is in milliseconds. For SRAM, latency is 10⁵ times lower than hard disk.

⭐ Key Takeaways

The average time to access data on a hard disk is the sum of seek time, rotational latency, transfer time, and controller overhead. Seek time depends on head movement distance, while rotational latency averages half a revolution. Transfer rates depend on the internal bandwidth of the disk. For calculations, use the average seek time and compute rotational latency as 0.5 divided by rotations per second. When comparing technologies, hard disks are cheaper per byte than semiconductor memory but have significantly higher latency (milliseconds vs. nanoseconds). Flash memory offers lower power and better mechanical reliability for embedded systems, though write operations are slower due to the erase-before-write requirement.

🧠 Quick Revision Questions

1. What are the three parts of every sector on a hard disk?
2. Why is average rotational latency equal to half a revolution?
3. What is the formula for total disk access time?
4. Why is flash memory preferred over hard disks in embedded systems?
5. How does the latency of a hard disk compare to that of SRAM memory?

📘 Lecture 33 — Error Control

📖 Overview: This lecture covers the Operating System interface for disk operations, followed by a detailed examination of error control techniques including parity codes, Hamming codes, and CRC mechanisms. It then introduces RAID (Redundant Array of Independent Disks) and compares various RAID levels, their performance characteristics, and their underlying approaches to data redundancy and access.

🗂️ Topics Covered

This lecture explores the Operating System interface that defines logical blocks for disk communication and insulates users from hardware details. It then delves into error control mechanisms—parity code, Hamming code, and CRC—covering detection and correction capabilities. Finally, RAID is introduced, with descriptions of RAID Level 0, comparisons between RAID Levels 2 and 3, and details of RAID Levels 4 and 5, including their independent access techniques and write penalty considerations.

📝 Lecture Summary

Operating System Interface

The Operating System interface plays an important role for disk operation. The operating system defines a logic block telling the controller about the track, sector, etc. There are different ways to define logic blocks. For example, we can define 5 bytes containing this information such that: the first 4 bits contain the disk number (in case of a system having more than one disk), the next 4 bits contain the address of a particular track followed by a sector number and at the end, the number of bytes to be transferred. So this defines a logical block transferred by the controller. Along with this, we have additional information about control and status of the controller. The operating system essentially insulates the users from the hardware details of the disk.

Error Control

There are two main issues in error control:

1. Detection of Error
2. Correction of Error

For detection of error, we just need to know that there exists an error. When the error is detected, the next step is to ask the source to resend that information. This process is called automatic request for repeat. In some cases, there is also the possibility that redundancy is enough and we reconstruct and find out exactly which particular bits are in error. This is called error correction.

There are three schemes commonly used for error control:

1. Parity code
2. Hamming code
3. CRC mechanism

1. Parity code

Along with the information bits, we add another bit, which is called the parity bit. The objective is to make the total number of 1's either even or odd. If the parity at the receiving end is different, an error is indicated. Once error is found, the CPU may request to repeat that data. The concept of the parity bit could be enhanced. In such a case, we would like to increase the distance between different code words. Consider a code word consisting of four bits, 0000, and a second code word consisting of 1111. The distance between the two codes is four. The distance between two codes is the number of bits in which they differ from each other. The concept of introducing redundancy is to increase this distance. Larger the distance, higher will be the capacity of the code. For single parity, the distance is two, we can only detect the parity. But if the distance is three, we could also correct these single errors.

If D = minimum distance between two code words then D-1 errors could be detected and D/2 errors could be corrected.

📌 Example: For a single parity bit, D=2, then D-1=1 error can be detected, and D/2=1 error can be corrected only if D>=3.

2. Hamming code

Hamming code is an example of block code. We have an encoder which could be a program or a hardware device. We feed k inputs to it. These are k information input bits. We also feed some extra bits. Let r be the number of redundant bits. So at output we have r+k = m bits. As an example, for parity bit, we have k=7 and r=1 and m=8. So for 7 bits we get eight output bits. 💡 Why this matters: Hamming codes allow for single-bit error correction and multi-bit error detection, which is essential for reliable data transmission and storage systems.

For any positive integer m<=3, a Hamming code with the following parameters exists:

🔑 Definition — Code Length: n = 2ᵐ - 1 🔑 Definition — Number of information symbols: k = 2ᵐ - 1 - m 🔑 Definition — Number of parity-check symbols: n – k = m

📐 Formula: n = 2ᵐ - 1 → Code length in bits 📐 Formula: k = 2ᵐ - 1 - m → Number of actual data bits 📐 Formula: n - k = m → Number of redundant parity bits

3. CRC (Cyclic Redundancy Check)

The basic principle for CRC is very simple. We divide a particular code word and make it divisible by a prime number, and if it is divisible by a prime number then it is a valid code word.

CRC does not support error correction but the CRC bits generated can be used to detect multi-bit errors. At the transmitter, we generate extra CRC bits, which are appended to the data word and sent along. The receiving entity can check for errors by re-computing the CRC and comparing it with the one that was transmitted.

CRC has lesser overhead as compared to Hamming code. It is practically quite simple to implement and easy to use. 💡 Why this matters: CRC is widely used in network communications and storage systems because of its efficiency in detecting burst errors with minimal computational overhead.

RAID

The main advantage of having an array of disks is that we could have simultaneous I/O requests. Latency could also be reduced.

RAID Level 0

• Not a true member of the RAID family.
• Does not include redundancy to improve performance.
• In few applications, capacity and performance are primary concerns than improved reliability. So RAID level 0 is used in such applications.
• The user and system data are distributed across all the disks in the array.
• Notable advantage over the use of a single large disk.
• Two requests can be issued in parallel, reducing the I/O queuing time.

Performance of RAID Levels

Performance of RAID Levels depends upon two factors:

• Request pattern of the host system
• Layout of the data

Similarities between RAID Levels 2 and 3

• Make use of parallel access techniques.
• All member disks participate in execution of every request.
• Spindles of the individual drives are synchronized.
• Data striping is used.
• Strips are as small as a single byte or word.

Differences between RAID 2 and RAID 3

• In RAID 2, error-correcting code is calculated across corresponding bits on each data disk.
• RAID 3 requires only a single redundant disk.
• Instead of an error-correcting code, a simple parity bit is computed for the set of individual bits in RAID 3.

RAID Level 4

• Makes use of independent access technique.
• Data striping is used.
• A bit-by-bit parity strip is calculated across corresponding strips on each data disk.
• Involves a write penalty when an I/O write request of small size is performed.
• To calculate the new parity, the array management software must read the old user parity strip.

RAID Level 5

• Organized in a similar fashion to RAID 4.
• The only difference is that RAID 5 distributes the parity strips across all disks, eliminating the write bottleneck associated with a dedicated parity disk.

⭐ Key Takeaways

Error control is achieved through detection (knowing an error exists) and correction (reconstructing the exact erroneous bits). The minimum distance D between code words determines error detection (D-1) and correction (D/2) capabilities. Hamming codes use block coding with m parity bits for a code length of 2ᵐ-1 bits, enabling single-bit correction, while CRC uses division by a prime number to detect multi-bit errors without correction. RAID levels differ in their approach to redundancy and access: RAID 0 has no redundancy, RAID 2 and 3 use parallel access with error-correcting codes and simple parity respectively, RAID 4 uses dedicated parity strips with a write penalty, and RAID 5 improves upon RAID 4 by distributing parity strips across all disks.

🧠 Quick Revision Questions

1. What are the two main issues in error control, and what is the process called when the source is asked to resend information after error detection?
2. If the minimum distance D between two code words is 3, how many errors can be detected and corrected?
3. What is the code length n and number of information symbols k for a Hamming code with m = 3?
4. What is the key difference between RAID 2 and RAID 3 in terms of the redundant disk and the type of code used?
5. Why does RAID Level 4 involve a write penalty for small I/O write requests, and how does RAID Level 5 address this issue?

📘 Lecture 34 — Number Systems and Radix Conversion

📖 Overview: This lecture introduces the Arithmetic Logic Shift Unit (ALSU) and explains the fundamental concepts of number representation in computer systems. It covers radix conversion between different number bases, fixed-point numbers, various integer representation schemes, and the essential operations of multiplication/division using shifts and unsigned addition. Understanding these concepts is critical for designing and working with computer arithmetic units.

🗂️ Topics Covered

The lecture begins with an introduction to the ALSU as a combinational circuit. It then discusses radix conversion algorithms for converting numbers between base b and base c. Fixed-point numbers and scaling are explained. The lecture covers the four main integer representation schemes: sign magnitude, radix complement, diminished radix complement, and biased representation. It concludes with multiplication and division using shift operations and the design of unsigned addition circuits using half and full adders.

📝 Lecture Summary

Introduction to ALSU

The Arithmetic Logic Shift Unit (ALSU) is a combinational circuit built from AND, OR, NOT, and other logic gates connected together to perform operations like addition, subtraction, and logical functions. Previously, we considered the ALSU as a "black box" with two input operands (a and b), one output (c), and control signals based on the instruction's opcode. To design an ALSU properly, a designer must understand number representation to determine the number of bits needed for source operands and the destination operand to avoid overflow and truncation.

Radix Conversion

Radix conversion is the process of converting a number from one base to another. Since humans work with base 10 (c) and computers with base 2 (b), this is a crucial operation. There are algorithms for converting both integers and fractions between bases.

For integer conversion from base b to base c: The algorithm iteratively processes each digit from the most significant to the least significant, using the formula: X = base * X + digit.

🔑 Definition — Radix Conversion Algorithm (b to c for integers): Start with X=0. For each digit from left to right: X = b × X + digit_value. The final X is the number in base c.

📐 Formula: X = b × X + dᵢ → starting from 0, build the decimal number by repeatedly multiplying by the original base and adding the next digit.

📌 Example 1: Convert B3₁₆ to base 10.

• X = 0
• First digit (B=11): X = 0 + 11 = 11
• Second digit (3): X = 16 × 11 + 3 = 176 + 3 = 179
• Result: B3₁₆ = 179₁₀

For integer conversion from base c to base b: The algorithm uses repeated division by the target base, collecting remainders from least to most significant.

📌 Example 2: Convert 390₁₀ to base 16.

• 390 / 16 = 24 (remainder 6) → x₀ = 6
• 24 / 16 = 1 (remainder 8) → x₁ = 8
• 1 / 16 = 0 (remainder 1) → x₂ = 1
• Read remainders in reverse order: 186₁₆

Fixed Point Numbers

A fixed-point number has a radix point at a fixed position. For example, in 16.12, there are two digits left and two digits right of the decimal point. If the number is an integer, the radix point is at the rightmost position (e.g., 1612.0). If it is a fraction, the point is at the leftmost (e.g., 0.1612). Scaling refers to shifting the radix point left or right, which corresponds to dividing or multiplying by the base, respectively.

For fraction conversion from base b to base c: The algorithm processes digits from right to left (least significant first): F = (F + digit) / base.

📌 Example 3: Convert (.4cd)₁₆ to base 10.

• F = 0
• F = (0 + d(13)) / 16 = 0.8125
• F = (0.8125 + c(12)) / 16 = 0.80078125
• F = (0.80078125 + 4) / 16 = 0.3000488₁₀

For fraction conversion from base c to base b: Repeatedly multiply the fraction by the target base, extracting the integer part as each digit.

📌 Example 4: Convert 0.24₁₀ to base 2.

• 0.24 × 2 = 0.48 → f₋₁ = 0
• 0.48 × 2 = 0.96 → f₋₂ = 0
• 0.96 × 2 = 1.92 → f₋₃ = 1
• 0.92 × 2 = 1.84 → f₋₄ = 1
• 0.84 × 2 = 1.68 → f₋₅ = 1
• Result: 0.24₁₀ = (0.00111)₂ (approximately)

💡 Why this matters: Inexact fraction conversion is common — not all decimal fractions have exact binary representations, which is important for numerical accuracy in computing.

Representation of Numbers

There are four main ways to represent integers:

1. Sign magnitude form
2. Radix complement form
3. Diminished radix complement form
4. Biased representation

Sign magnitude form:

• Simplest form for signed numbers
• A symbol (or sign bit) is appended to the left of the number
• This representation complicates arithmetic operations because the sign and magnitude must be handled separately

Radix complement form:

• The most common representation in computers
• For an m-digit base b number x, the radix complement of x is defined as:
  • x_c = (b^m – x) mod b^m
• This representation makes arithmetic operations much easier because subtraction can be performed as addition

Diminished radix complement form:

• The diminished radix complement of an m-digit number x is:
  • x_c' = b^m – 1 – x
• This complement is easier to compute than the radix complement
• The two complement forms are interconvertible:
  • x_c = (x_c' + 1) mod b^m

Table 6.1 and Table 6.2 from the textbook show complement representations for negative numbers in various forms, including 2's complement and 1's complement for 8-bit numbers.

📌 Example 5: The following table shows decimal values in various representations (2's complement, 1's complement, sign magnitude, 16's complement, and unsigned form) — referenced from the textbook.

Multiplication and Division using Shift Operation

Shift left and shift right operations are used for multiplying or dividing by the base b. However, care must be taken with binary representation size and negative numbers.

📌 Example 6:

• 6 × 4: 00110₂ × 4₁₀ = 11000₂ = 24₁₀ (shift left by 2 bits). Overflow would occur if 4 bits were used instead of 5.
• 60 / 16: 0111100₂ / 16₁₀ = 0000011₂ = 3₁₀ (shift right by 4 bits). The fractional portion is lost.

📌 Example 7:

• -6 × 4: -6 = (11010)₂ in 5-bit 2's complement
  • Using 5 bits: -6×4 = (01000)₂ = 8 (wrong! Sign changed due to overflow)
  • Using 6 bits: -6 = (111010)₂, -6×4 = (101000)₂ = -24 (correct)
• Lesson: Using too few bits might change the sign — always ensure sufficient bit width.

📌 Example 8: Multiplication and division of negative numbers.

• -24 × 2: -24 = (101000)₂ in 6-bit form
  • Wrong: -24×2 = (010100)₂ = 20 (overflow)
  • Correct: -24×2 = (110100)₂ = -12 (when using proper sign extension)
• Size extension: 24 = 011000 (n=6) → 00011000 (n=8); -24 = 101000 (n=6) → 11101000 (n=8). This demonstrates sign extension — replicating the sign bit when increasing word size.

Unsigned Addition Operation

The addition of two m-digit base b numbers, x and y, is performed digit by digit with carry propagation from least significant to most significant digit.

A 1-bit half adder takes two 1-bit inputs (x and y) and produces a 1-bit sum and a 1-bit carry. It is called a "half adder" because it does not accept an input carry.

A 1-bit full adder takes three inputs (x, y, and carry_in) and produces sum and carry_out. By cascading m 1-bit full adders, we can add two m-bit numbers.

Overflow occurs when the addition of two unsigned m-bit numbers results in an m+1 bit number. This is treated as an exception in some processors, and the overflow flag records the status of the result.

🔑 Definition — Half Adder: A logic circuit that adds two 1-bit binary numbers, producing a sum bit and a carry bit, without considering an input carry.

🔑 Definition — Full Adder: A logic circuit that adds two 1-bit binary numbers along with an input carry, producing a sum bit and a carry-out bit.

📐 Formula: Sum = x ⊕ y; Carry = x · y (for half adder)

📌 Example 9: Unsigned addition in base 2 and base 16 (shown in the textbook figure).

⭐ Key Takeaways

The most critical concepts from this lecture are the radix conversion algorithms for both integers and fractions, as they form the foundation for understanding how computers handle different number systems. The four integer representation schemes — especially radix complement (2's complement) which is the industry standard — are essential for designing arithmetic circuits. Understanding shift operations for multiplication/division and the importance of sign extension and overflow detection in fixed-width arithmetic is vital for avoiding errors in computer arithmetic. Finally, the design of half adders and full adders provides the building blocks for constructing ALSUs that perform addition correctly while detecting overflow conditions.

🧠 Quick Revision Questions

1. How do you convert the hexadecimal number 2F₁₆ to decimal using the radix conversion algorithm?
2. What is the difference between a half adder and a full adder, and how can full adders be cascaded to add multi-bit numbers?
3. When converting the fraction 0.3₁₀ to binary, why might you need an infinite number of binary digits, and what practical problem does this create?
4. In 2's complement representation, why is it important to use enough bits when multiplying a negative number by a positive number using shift operations?
5. What is the relationship between radix complement and diminished radix complement, and how can one be derived from the other?

📘 Lecture 35 — Multiplication and Division of Integers

📖 Overview: This lecture covers integer overflow, adder implementations (ripple carry and carry look ahead), unsigned and signed multiplication techniques, integer and fraction division algorithms, and branch architecture. Understanding these concepts is fundamental to designing efficient arithmetic logic units in computer processors.

🗂️ Topics Covered

The lecture covers overflow in fixed-point addition, ripple carry and carry look ahead adder implementations, complement adder/subtractor design for 2's complement, unsigned multiplication using parallel array and series-parallel multipliers, signed multiplication methods including 2's complement multiplication, Booth recoding, and bit-pair recoding, integer and fraction division algorithms, and branch architecture including condition codes and conditional branches.

📝 Lecture Summary

Overflow

When two m-bit numbers are added and the result exceeds the capacity of an m-bit destination, this situation is called an overflow. In the example, adding numbers that produce a result in the fifth bit position (when only four bits are allowed) causes overflow.

🔑 Definition — Overflow: When the result of an arithmetic operation exceeds the storage capacity of the destination register.

📌 Example: Adding two 4-bit numbers that produce a 5-bit result (e.g., 1111 + 0001 = 10000) causes overflow because the fifth position is not allowed.

Different Implementations of the Adder

For a binary adder, the sum bit is obtained by: sj = xj yj cj + xj yj cj + xj yj cj + xj yj cj

The carry bit equation is: cj+1 = xj yj + xj cj + yj cj where x and y are the input bits.

The two methods for computing the sum are:

• Ripple Carry Adder
• Carry Look ahead Adder

Ripple Carry Adder

In this adder circuit, we feed carry out from the previous stage to the next stage. For 64-bit addition, 126 logic levels are required between input and output bits. The logic levels can be reduced by using a higher base (Base 16). This is a relatively slow process.

🔑 Definition — Ripple Carry Adder: An adder where the carry output of each stage becomes the carry input of the next stage, causing propagation delay through all stages.

Complement Adder/Subtractor

We can perform subtraction using an unsigned adder by complementing the second input and supplying overflow detection hardware.

2's Complement Adder/Subtractor

A combined adder/subtractor can be built using a mux to select the second adder input. The mux also determines the carry-in to the adder. The equation for mux output is: qj = yj r + yj r

🔑 Definition — Mux (Multiplexer): A combinational circuit that selects one of several input signals and forwards the selected input to a single output line.

Carry Look ahead Adder

The basic idea in carry look ahead is to speed up the ripple carry by determining whether the carry is generated at the j position after addition, regardless of the carry-in at that stage, or the carry is propagated from input to output in the digit. This results in faster addition and lesser propagation delay of the carry bits.

It divides the carry into two logical variables:

• Gj (Generate): Gj = xj yj
• Pj (Propagate): Pj = xj + yj

Hence the carry out will be: Cj+1 = Gj + Pj cj

Here G and P each require one gate, and the sum bit needs two more gates in the full adder. This results in less complexity i.e. log(m), much less compared to ripple carry adder where complexity is m (m is the number of bits). Ripple carry and look ahead schemes can be mixed by producing a carry-out at the left end of each look ahead module and using ripple carry to connect modules at any level of the look ahead tree.

💡 Why this matters: Carry look ahead adders are essential for high-speed arithmetic in modern processors because they dramatically reduce propagation delay compared to ripple carry adders.

Unsigned Multiplication

The general schema for unsigned multiplication in base b is shown in Figure 6.5 of the textbook.

Parallel Array Multiplier: Each computational block consists of a full adder with an AND gate to form the product xiyj. In binary, m² full adders are required and signals pass through almost 4m gates.

Series Parallel Multiplier: A combination of parallel and sequential hardware is used to build a multiplier, achieving good speed while saving hardware.

Signed Multiplication

The sign of a product is easily computed from the sign of the multiplier and the multiplicand. The product is positive if both have the same sign and negative if different. When two unsigned digits having m and n bits are multiplied, this results in a (m+n)-bit product, and (m+n+1)-bit product for signed digits.

Three methods for signed multiplication:

1. 2's complement multiplier
2. Booth recoding
3. Bit-Pair recoding

2's complement Multiplication

If numbers are represented in 2's complement form, three modifications are required:

1. Provision for sign extension
2. Overflow prevention
3. Subtraction as well as addition of the partial product

Booth Recoding

The Booth Algorithm makes multiplication simple to implement at hardware level and speeds up the procedure:

• Start with LSB; for each 0 of the original number, place a 0 in the recorded number until a 1 is indicated.
• Place a 1 for 1 in the recorded table and skip any succeeding 1's until a 0 is encountered.
• Place a 0 with 1 and repeat the procedure.

📌 Example: Recode the integer 485 according to Booth procedure.

Original number: 00111100101 = 256+128+64+32+4+1 = 485

Recoded Number: 01000101111 = +512-32+8-4+2-1 = 485

Bit-Pair Recoding

Booth recoding may increase the number of additions due to isolated 1s. To avoid this, bit-pair recoding is used where bits are encoded in pairs, resulting in only n/2 additions instead of n.

Division

Two types of division:

• Integer division
• Fraction division

Integer division

Steps for integer division:

1. Clear upper half of dividend register, put dividend in lower half. Initialize quotient counter bit to 0.
2. Shift dividend register left 1 bit.
3. If difference is positive, put it into upper half of dividend and shift 1 into quotient. If negative, shift 0 into quotient.
4. If quotient bits < m, go to step 2.
5. m-bit quotient is in quotient register and m-bit remainder is in upper half of dividend register.

📌 Example: Divide 47₁₀ by 5₁₀. [Detailed step-by-step solution with register operations is shown in the textbook pages 310-311]

Fraction Division

Steps for fractional division:

1. Clear lower half of dividend register, put dividend in upper half. Initialize quotient counter bit to 0.
2. If difference is positive, report overflow.
3. Shift dividend register left 1 bit.
4. If difference is positive, put it into upper half of dividend and shift 1 into quotient. If negative, shift 0 into quotient.
5. If quotient bits < m, go to step 3.
6. m-bit quotient has decimal at the left end and remainder is in upper half of dividend register.

Branch Architecture

The next important function performed by the ALU is branch. Branch architecture is based on:

1. Condition Codes
2. Conditional Branches

Condition Codes

Condition Codes are computed by the ALU and stored in the processor status register. The 'comparison' and 'branching' are treated as two separate operations. This approach is not used in the SRC. Table 6.6 of the textbook shows condition codes after subtraction for signed and unsigned x and y.

Implementation with flags is usually easier but requires status registers. In case of branch instructions, decision is based on the branch itself.

💡 Why this matters: Branch architecture directly impacts processor performance through conditional execution and pipeline efficiency.

⭐ Key Takeaways

The lecture emphasizes that overflow occurs when results exceed register capacity, requiring careful handling in arithmetic operations. Carry look ahead adders significantly outperform ripple carry adders by using generate (G) and propagate (P) signals to reduce propagation delay from O(m) to O(log m). For multiplication, Booth recoding and bit-pair recoding simplify hardware implementation by reducing the number of additions, while signed multiplication requires sign extension and overflow prevention. Division algorithms differ for integer and fraction operations, with fraction division requiring overflow checking before shifting. Branch architecture uses condition codes stored in processor status registers to enable conditional execution.

🧠 Quick Revision Questions

1. What is overflow and how does it occur in fixed-point addition?
2. What are the equations for the sum bit (sj) and carry bit (cj+1) in a binary adder?
3. What are the generate (Gj) and propagate (Pj) variables in carry look ahead addition, and how do they reduce propagation delay?
4. What are the three modifications required for 2's complement multiplication compared to unsigned multiplication?
5. What is the key difference between integer division and fraction division algorithms in terms of initial register setup and overflow checking?

📘 Lecture 36 — Floating-Point Arithmetic

📖 Overview: This lecture covers the design of barrel shifters and ALUs, then transitions into floating-point arithmetic representations and operations. Understanding these concepts is critical for computer architecture as they form the foundation for how computers handle real numbers and perform arithmetic operations efficiently.

🗂️ Topics Covered

The lecture begins with NxN crossbar design for barrel rotators and barrel shifter with logarithmic number of stages, followed by ALU design. It then covers floating-point representations, normalization, the IEEE floating-point standard, and concludes with detailed steps for floating-point addition/subtraction, multiplication, and division with worked examples.

📝 Lecture Summary

NxN Crossbar Design for Barrel Rotator

The NxN crossbar design for a barrel rotator uses a grid structure where inputs x₀,x₁,...,xₙ₋₁ are applied to rows and outputs y₁,y₂,...yₙ₋₁ come from vertical lines, creating N×N cross points. Each input-output connection uses a tri-state buffer. A decoder at the input selects the shift count, with each decoder output connected diagonally to the tri-state buffers.

🔑 Definition — Crossbar Rotator: A circuit that uses N² gates arranged in a grid pattern to rotate an input word by any amount, where each input can connect to any output through tri-state buffers controlled by a decoder.

📐 Formula: Number of cross points = N × N → The total number of possible connections equals the square of the word size.

📌 Example: For an 8-bit word (N=8), the crossbar requires 8×8 = 64 cross points with 64 tri-state buffers and an 8-line decoder.

💡 Why this matters: While simple in concept, the N² gate count becomes impractical for large N, motivating more efficient designs.

Barrel Shifter with Logarithmic Number of Stages

The logarithmic barrel shifter represents a time-space trade-off compared to the NxN crossbar. For a shifter requiring 8 shifts, three stages are needed. Each stage has two possibilities: bypass (pass word unchanged) or shift (shift the word). The first stage provides 1-bit right shift, second stage 2-bit right shift, and so on. A shift count unit controls which stages activate.

🔑 Definition — Shift/Bypass Cell: A combinational logic circuit that, controlled by a shift/bypass signal, either passes the input word unchanged or applies a shift of the stage's specified amount.

📐 Formula: Number of stages = log₂(N), Switch count = O(NlogN), Propagation delay = O(logN) → This design uses fewer switches but has higher propagation delay than the O(1) delay of the crossbar.

📌 Example: For a 3-bit shift (binary 011), signals s₀ and s₁ are 1, meaning stage 1 (1-bit shift) and stage 2 (2-bit shift) both activate, while s₂ (4-bit shift) remains 0.

ALU Design

The ALU (Arithmetic Logic Unit) combines an arithmetic unit, logic unit, and shifter unit with multiplexers and a control unit. Two n-bit inputs (x and y) are simultaneously provided to all three units. The control unit accepts the op-code as input and generates control signals that activate the appropriate unit. Two multiplexers select the result: one mux chooses between arithmetic, logic, and shifter outputs for the final result z, while the other mux provides the status output corresponding to condition codes.

🔑 Definition — ALU: A combinational circuit that performs arithmetic operations (add, subtract), logic operations (AND, OR, XOR), and shift/rotate operations on binary numbers based on the instruction's op-code.

Floating Point Representations

A floating-point number consists of three parts: sign, significand (also called mantissa), and exponent, with a fixed base. In computers, binary numbers encode these components into a single word.

🔑 Definition — Floating-Point Number: A number represented as (-1)ˢ × f × 2ᵉ where s is the sign bit, f is the significand (mantissa), and e is the exponent with a biased representation.

📌 Example: -0.5 × 10⁻³ has sign = -1, significand = 0.5, exponent = -3, base = 10.

📐 Formula: Floating-point form = (-1)ˢ × f × 2ᵉ → If s=1 the number is positive, if s=0 the number is negative. The exponent uses a biased representation where a constant (bias) is added to make the exponent always positive.

Normalization

A normalized floating-point number has a significand whose leftmost digit is non-zero and is a single digit. This ensures a unique representation for each number and maximizes precision.

🔑 Definition — Normalization: The process of adjusting the significand and exponent so that the significand's most significant digit is non-zero and occupies exactly one digit position.

📌 Example: 0.56 × 10⁻³ (not normalized) → 5.6 × 10⁻³ (normalized form). Same principle applies to binary numbers.

IEEE Floating-Point Standard

The IEEE floating-point standard defines two main formats: single-precision and double-precision. Single-precision uses 1-bit sign, 8-bit exponent, 23-bit fraction, with a bias of 127. Double-precision uses 1-bit sign, 11-bit exponent, 52-bit fraction, with an exponent bias of 1023. Special values include NaN (Not-a-Number) and ±∞, represented when the exponent field ê=255 (for single precision).

🔑 Definition — Overflow: A condition where a floating-point number's exponent is too large to be represented in the exponent field. For single precision, representable range is 1.2 × 10⁻³⁸ ≤ x ≤ 3.4 × 10³⁸.

📐 Formula: Actual exponent = stored exponent - bias → For single precision: exponent range = -126 to +127 (stored as 1 to 254, with 0 and 255 reserved)

Floating-Point Addition and Subtraction

The algorithm for floating-point addition/subtraction follows six steps: unpack sign, exponent and fraction fields; shift the significand to align decimal points; perform addition; normalize the sum; round off the result; check for overflow.

📌 Example 1: Add 0.5₁₀ and -0.4375₁₀

• Step 1 - Convert to binary: 0.5₁₀ = 0.1₂ = 1.000 × 2⁻¹, -0.4375₁₀ = -7/16₁₀ = -0.0111₂ = -1.110 × 2⁻²
• Step 2 - Align exponents: -1.110 × 2⁻² → -0.111 × 2⁻¹
• Step 3 - Add significands: 1.000 × 2⁻¹ + (-0.111 × 2⁻¹) = 0.001 × 2⁻¹
• Step 4 - Normalize: 0.001₂ × 2⁻¹ = 0.010₂ × 2⁻² = 1.000₂ × 2⁻⁴

Floating-Point Multiplication

Floating-point multiplication follows five steps: unpack sign, exponent and significands; apply exclusive-or operation to signs (to determine result sign), add exponents, then multiply significands; normalize, round and shift the result; check for overflow; pack the result and report exceptions.

📐 Formula: Result sign = sign₁ XOR sign₂, Result exponent = exponent₁ + exponent₂, Result significand = significand₁ × significand₂

Floating-Point Division

Floating-point division follows five steps: unpack sign, exponent and significands; apply exclusive-or to signs, subtract exponents, then divide significands; normalize, round and shift the result; check for overflow; pack the result and report exceptions.

📐 Formula: Result sign = sign₁ XOR sign₂, Result exponent = exponent₁ - exponent₂, Result significand = significand₁ ÷ significand₂

⭐ Key Takeaways

The most critical concepts from this lecture are the trade-off between N×N crossbar and logarithmic barrel shifter designs, where crossbars use O(N²) gates with O(1) delay while logarithmic shifters use O(NlogN) gates with O(logN) delay. The IEEE floating-point standard defines single-precision (32-bit: 1 sign, 8 exponent, 23 fraction with bias 127) and double-precision (64-bit: 1 sign, 11 exponent, 52 fraction with bias 1023) formats. For floating-point operations, addition/subtraction requires aligning exponents before adding significands, while multiplication uses XOR for sign, addition of exponents, and multiplication of significands, and division uses XOR for sign, subtraction of exponents, and division of significands. Normalization ensures unique representation by making the significand's most significant digit non-zero.

🧠 Quick Revision Questions

1. What are the two alternative designs for barrel rotators/shifters and what are their respective gate counts and propagation delays?
2. In IEEE single-precision floating-point format, what is the bias value and how is it used to determine the actual exponent?
3. What are the six steps required for floating-point addition and subtraction?
4. How does the sign of the result get determined differently for floating-point multiplication versus division?
5. What is normalization and why is it important in floating-point representation?