Direct memory access

Why it exists

Programmed I/O keeps the processor in a loop, and interrupt-driven I/O still makes the processor handle every word: save state, move one word, restore state. For a disk delivering millions of bytes per second that is far too much. Direct memory access (DMA) removes the processor from the data path. A DMA controller (DMAC) is told once where in memory the block goes and how long it is; after that it moves the words between the device and memory by itself and interrupts the processor once, at the end. GATE asks for the sequence of events, the three transfer modes, the CPU time lost to stolen cycles, and the comparison with interrupt-driven I/O.

Prerequisites

You need the device interface and the three ways of running a transfer from I/O interface and programmed I/O. The comparison with interrupts is part of this page.

Precise definitions

DMA controller. An interface that can act as a bus master: it drives the address bus, the data bus and the read/write lines in place of the processor. The registers a processor programs (idealised):

• address register (AR): the memory address of the next word, incremented after each word;
• word count register (WC): the number of words still to move, decremented after each word; the transfer ends when it reaches 0;
• control/status register: direction (device to memory, or memory to device), mode, start bit, interrupt enable, done and error flags.

Sequence of a DMA transfer.

1. The processor sets up the DMAC: writes AR (start address), WC (count) and the control register (direction, start). It then goes back to other work.
2. The device raises a DMA request (DREQ) when it has a word ready (or can take one).
3. The DMAC raises a bus request to the processor (HOLD in Intel's naming, BR in others).
4. The processor finishes its current bus cycle (not necessarily the current instruction), floats its address, data and control lines and answers with a bus grant (HLDA, BG). The DMAC is now the bus master.
5. The DMAC sends a DMA acknowledge (DACK) to the device, places AR on the address bus and performs the memory read or write. In the usual single-address (fly-by) transfer the word goes between the device and memory in one bus cycle without passing through the DMAC or the processor.
6. The DMAC increments AR and decrements WC.
7. It releases the bus (end of burst, or after each word).
8. When WC reaches 0 the DMAC raises an interrupt to the processor to report that the block is complete.

Transfer modes.

• Burst (block) mode. Once the DMAC has the bus it keeps it for the entire block (or until the device has no more data). The device runs at full speed but the processor cannot use the memory bus for the whole block.
• Cycle stealing. The DMAC takes the bus for one word (one memory cycle) at a time and gives it back. The processor is slowed down only by the stolen cycles, and in the worst case waits one cycle at a time.
• Transparent (hidden) mode. The DMAC transfers only in bus cycles the processor is not using (for example while it computes internally). The processor is not slowed at all, but the DMAC is more complex and the transfer may be slow if the processor uses the bus a lot.

Cost. For a device with word rate $w$ words per second and a memory cycle time $t_m$, cycle stealing takes a fraction

$\text{fraction of memory cycles stolen} = w \cdot t_m.$

A burst of $n$ words holds the bus for $n \cdot t_m$. For a block of $n$ words, DMA costs the processor a fixed setup $S$ and a final interrupt $I$ (in processor cycles) plus the stolen memory cycles; interrupt-driven I/O costs it $n \cdot c_i$ (an interrupt per word of $c_i$ cycles). DMA is cheaper when

$S + I + n\,t < n\,c_i \iff n > \frac{S + I}{c_i - t},$

where $t$ is the stolen time per word in processor cycles.

Several DMA channels share the bus by priority, using the same ideas as interrupt priority: a daisy chain of bus grants or a priority encoder. The processor has the lowest priority for the bus when a DMA request is pending.

How it works

The animation moves four words from a disk controller to memory addresses 512 to 515 by cycle stealing. The CPU only programs AR, WC and the control register, then carries on; for each word the DMAC requests the bus, is granted it for one cycle, writes the word directly into memory, updates AR and WC and releases the bus. After the fourth word WC is 0 and a single interrupt is raised. Watch that AR + WC stays constant (512 + 4) and that memory changes only while the DMAC is the bus master.

The time-axis comparison of polling, interrupts and DMA moving the same three words is on the I/O interface page: the DMA row loses only the setup, one stolen tick per word and the final interrupt, and gets the most useful work (29 of 36 ticks in that model). With more words per block the advantage grows, since the fixed costs are paid once.

Worked examples

#include <stdio.h>
 
int main(void) {
    /* a disk delivers 4-byte words at 4 MB/s into a memory with a 100 ns cycle; the DMA controller steals one memory cycle per word */
    double words_per_s = 4e6 / 4, cycle_ns = 100;
    printf("%.0f words/s, each steals %.0f ns: %.1f%% of the memory cycles\n", words_per_s, cycle_ns, 100.0 * words_per_s * cycle_ns * 1e-9);
    /* a 512-byte sector moved as one burst holds the bus for */
    int words = 512 / 4;
    printf("burst of %d words holds the bus %.1f us\n", words, words * cycle_ns / 1000.0);
    return 0;
}

1000000 words/s, each steals 100 ns: 10.0% of the memory cycles
burst of 128 words holds the bus 12.8 us

#include <stdio.h>
 
int main(void) {
    /* interrupt-driven: every word costs 120 cycles. DMA: 1000 cycles setup + 1 cycle per word + 500 cycles for the final interrupt */
    int n = 1;
    while (1000 + n * 1 + 500 >= n * 120) n++;
    printf("DMA is cheaper from %d words up\n", n);
    int block = 1024;
    printf("block of %d words: interrupts %d cycles, DMA %d cycles\n", block, block * 120, 1000 + block + 500);
    return 0;
}

DMA is cheaper from 13 words up
block of 1024 words: interrupts 122880 cycles, DMA 2524 cycles

Cheat box

Traps and GATE patterns

Connections

DMA takes over the buses that memory interfacing connects the memory to. It is the third scheme after polling and interrupts, and it ends with an interrupt of its own. The effect on the cache is the coherence problem named above, linked to the write policies.

PYQs

Consider a computer with a 4 MHz processor. Its
DMA controller can transfer 8 bytes in 1 cycle from
a device to main memory through cycle stealing at
regular intervals. Which one of the following is the
data transfer rate (in bits per second) of the DMA
controller if 1% of the processor cycles are used for
DMA?

Which one of the following statements is FALSE?

Which one of the following facilitates transfer of
bulk data from hard disk to main memory with the
highest throughput?

Consider a computer system with DMA support.
The DMA module is transferring one 8-bit
character in one CPU cycle from a device to
memory through cycle stealing at regular
intervals. Consider a 2 MHz processor. If 0.5%
processor cycles are used for DMA, the data
transfer rate of the device is
bits per
second.

Consider the following statements.
I. Daisy chaining is used to assign priorities in
attending interrupts.
II. When a device raises a vectored interrupt, the
CPU does polling to identify the source of the
interrupt.
III. In polling, the CPU periodically checks the
status bits to know if any device needs its attention.
IV. During DMA, both the CPU and DMA
controller can be bus masters at the same time.
Which of the above statements is/are TRUE?

The size of the data count register of a DMA controller
is 16 bits.The processor needs to transfer a file of
29,154 kilobytes from disk to main memory.The
memory is byte addressable
The minimum number of times the DMA controller
needs to get the control of the system bus from the
processor to transfer the file from the disk to main
memory is

On a non-pipelined sequential processor, a
program segment, which is the part of the interrupt
service routine, is given to transfer 500 bytes from
an I/O device to memory.
Intialize the address register
Intilatize the count to 500
LOOP: Load a byte from device
Store in memory at address given by address
register
Increment the address register
Decrement the count
If count != 0 go to LOOP
Assume that each statement in this program is
equivalent to a machine instruction which takes one
clock cycle to execute if it is a non-load/store
instruction. The load-store instructions take two
clock cycles to execute.
The designer of the system also has an alternate
approach of using the DMA controller to implement
the same transfer. The DMA controller requires 20
clock cycles for initialization and other overheads.
Each DMA transfer cycle takes two clock cycles to
transfer one byte of data from the device to the
memory.
What is the approximate speed up when the DMA
controller based design is used in a place of the
interrupt driven program based input-output?

Consider the disk drive with the following
specifications: 16 surfaces, 512 tracks/surface, 512
sectors/track, 1 KB/sector, rotation speed 3000
rpm. The disk is operated in cycle stealing mode
whereby whenever one byte is ready it is sent to
memory, similarly, for writing, the disk interface
reads a 4-byte word from the memory in each
DMA cycle. Memory cycle time is 40 nsec The
maximum percentage of time that the CPU gets
blocked during DMA operation is

Self-check

Revision card

References