Department of Computer Science Course: CS 3725

Direct memory access

In most mini- and mainframe computer systems, a great deal of input and output occurs between the disk system and the processor. It would be very inefficient to perform these operations directly through the processor; it is much more efficient if such devices, which can transfer data at a very high rate, place the data directly into the memory, or take the data directly from the processor without direct intervention from the processor. I/O performed in this way is usually called direct memory access, or DMA. The controller for a device employing DMA must have the capability of generating address signals for the memory, as well as all of the memory control signals. The processor informs the DMA controller that data is available (or is to be placed into) a block of memory locations starting at a certain address in memory. The controller is also informed of the length of the data block.

There are two possibilities for the timing of the data transfer from the DMA controller to memory:

• The controller can cause the processor to halt if it attempts to access data in the same bank of memory into which the controller is writing. This is the fatest option for the I/O device, but may cause the processor to run more slowly because the processor may have to wait until a full block of data is transferred.
• The controller can access memory in memory cycles which are not used by the particular bank of memory into which the DMA controller is writing data. This approach, called ``cycle stealing,'' is perhaps the most commonly used approach. (In a processor with a cache that has a high hit rate this approach may not slow the I/O transfer significantly).

DMA is a sensible approach for devices which have the capability of transferring blocks of data at a very high data rate, in short bursts. It is not worthwhile for slow devices, or for devices which do not provide the processor with large quantities of data. Because the controller for a DMA device is quite sophisticated, the DMA devices themselves are usually quite sophisticated (and expensive) compared to other types of I/O devices.

One problem that systems employing several DMA devices have to address is the contention for the single system bus. There must be some method of selecting which device controls the bus (acts as ``bus master'') at any given time. There are many ways of addressing the ``bus arbitration'' problem; three techniques which are often implemented in processor systems are the following (these are also often used to determine the priorities of other events which may occur simultaneously, like interrupts). They rely on the use of at least two signals (bus_request and bus_grant), used in a manner similar to the two-wire handshake:

Daisy chain arbitration Here, the requesting device or devices assert the signal bus_request. The bus arbiter returns the bus_grant signal, which passes through each of the devices which can have access to the bus, as shown in Figure . Here, the priority of a device depends solely on its position in the daisy chain. If two or more devices request the bus at the same time, the highest priority device is granted the bus first, then the bus_grant signal is passed further down the chain. Generally a third signal (bus_release) is used to indicate to the bus arbiter that the first device has finished its use of the bus. Holding bus_request asserted indicates that another device wants to use the bus.

  
Figure: Daisy chain bus arbitration

Priority encoded arbitration Here, each device has a request line connected to a centralized arbiter that determines which device will be granted access to the bus. The order may be fixed by the order of connection (priority encoded), or it may be determined by some algorithm preloaded into the arbiter. Figure  shows this type of system. Note that each device has a separate line to the bus arbiter. (The bus_grant signals have been omitted for clarity.)

  
Figure: Priority encoded bus arbitration

Distributed arbitration by self-selection Here, the devices themselves determine which of them has the highest priority. Each device has a bus_request line or lines on which it places a code identifying itself. Each device examines the codes for all the requesting devices, and determines whether or not it is the highest priority requesting device.

These arbitration schemes may also be used in conjunction with each other. For example, a set of similar devices may be daisy chained together, and this set may be an input to a priority encoded scheme.

There is one other arbitration scheme for serial busses -- distributed arbitration by collision detection. This is the method used by the Ethernet, and it will be discussed later.