Chapter 12 of 39

Bus Structure & Bus Arbitration

Imagine a small town where every house is connected to every other house by its own private road. It would be perfect for traffic, and impossible to build. Real towns have a main road that everyone shares. Sharing saves a huge amount of construction, but now there are new problems: what are the traffic rules, and who goes first when two cars want the same stretch of road?

A computer has the same problem. The processor, memory and I/O devices all need to exchange data. Instead of wiring each one to every other one, they share a set of wires called a bus. In Register Transfer & Micro-operations we saw a bus that links registers inside the CPU. This chapter looks at the bus that links the major components of the computer: how it is organised, how a transfer is timed, and how the bus decides who gets to use it (bus arbitration).

A bus is a shared communication pathway made of a group of wires (lines) that connects two or more devices, where only one device can send data on the bus at a time.


The System Bus: Three Groups of Lines

The bus that connects the CPU, main memory and I/O is called the system bus. Its lines fall into three groups:

   +-------+        +---------+        +---------+        +---------+
   |  CPU  |        | Memory  |        |  I/O 1  |        |  I/O 2  |
   +---+---+        +----+----+        +----+----+        +----+----+
       |                 |                  |                  |
 ======+=================+==================+==================+====  Address bus
 ======+=================+==================+==================+====  Data bus
 ======+=================+==================+==================+====  Control bus

Group

Carries

Direction

What its width decides

Address bus

The address of the memory location or I/O port being accessed

Usually one-way: from the bus master (e.g. CPU) to memory / I/O

How many locations can be addressed: m lines → 2m addresses

Data bus

The actual data or instruction being transferred

Two-way (bidirectional)

How many bits move per transfer

Control bus

Commands and timing/status signals

Each line is usually one-way, but some lines run from the master and others back to it, so the group as a whole carries signals in both directions

What operations and coordination are possible

Typical control lines include: Memory Read, Memory Write, I/O Read, I/O Write, clock, reset, transfer acknowledge (or "ready"), interrupt request and acknowledge, and bus request and bus grant (used for arbitration, later in this chapter).

Worked Example: Address and Data Bus Widths

For a byte-addressable memory, each address names one byte, so an address bus with m lines can reach 2m bytes.

Address lines

Addressable bytes

Example

16

216 = 65,536 = 64 KB

Intel 8085

20

220 = 1,048,576 = 1 MB

Intel 8086

32

232 = 4 GB

Classic 32-bit systems

36

236 = 64 GB

32-bit x86 with PAE

Problem. A byte-addressable memory has 256 MB. How many address lines are needed? If the data bus is 32 bits wide, how many bus transfers are needed to read a 64-byte block?

Solution. 256 MB = 28 × 220 = 228 bytes, so 28 address lines. A 32-bit data bus moves 4 bytes per transfer, so 64 / 4 = 16 transfers.

Note that the width of the data bus and the "bitness" of the processor need not match. The original 8088 processor in the IBM PC was internally 16-bit but had an 8-bit external data bus.

Multiplexed Address and Data Lines

Pins on a chip are expensive. Some processors time-share the same pins between address and data. The Intel 8085 sends the low byte of the address on pins AD0-AD7 at the start of a bus cycle, then uses the same pins for data. A signal called ALE (Address Latch Enable) tells an external latch to capture the address before the pins switch to data. The 8086 does the same with AD0-AD15. This saves pins but makes each bus cycle a little longer, because address and data cannot be on those lines at the same time.


Bus Masters, Slaves and Bus Cycles

  • A bus master is a device that can start a transfer: it places the address and the command on the bus. The CPU is the usual master; a DMA controller is another.

  • A slave is a device that responds to the master: memory is always a slave.

  • A bus cycle (or bus transaction) is one complete transfer: master sends address and command, then data is sent (write) or received (read).

Two questions arise immediately. First, how do master and slave agree on when the data is valid? That is bus timing. Second, what if two masters want the bus at the same time? That is bus arbitration.


Single-Bus and Multiple-Bus Structures

Single Bus

All units sit on one bus. It is cheap, simple and flexible: adding a device just means connecting it. The disadvantage is that only one transfer can happen at a time, and the bus must be slow enough for its slowest and farthest device. Long buses with many devices also suffer from signal delay and electrical loading. Early minicomputers (such as the DEC PDP-11's Unibus) used this design.

Multiple Buses (Bus Hierarchy)

Modern systems separate traffic by speed. A fast, short bus (or link) connects the processor and memory, and slower I/O buses hang off it through bridges:

   +-----+  fast processor-memory link  +-------------------+
   | CPU |<---------------------------->| Memory controller |<--> Main memory
   +-----+                              +---------+---------+
                                                  |
                                              [ Bridge ]
                                                  |
          ===============================================================  I/O bus
              |                |                 |                |
           Disk ctrl.       Network          USB ctrl.        Graphics

Aspect

Single bus

Multiple buses

Cost and simplicity

Low cost, simple

More hardware (bridges, controllers)

Concurrency

One transfer at a time

Transfers on different buses can overlap

Speed

Limited by the slowest device on the bus

Fast devices are not slowed by slow ones

Scalability

Poor: more devices = more load and delay

Better

(How buses are arranged inside the CPU, as one-, two- or three-bus datapaths, is covered in ALU & Datapath.)


Bus Timing: Synchronous vs Asynchronous

Synchronous Bus

A synchronous bus has a clock line. Every event happens at a fixed clock edge, and both sides know the schedule in advance. A simple read looks like this:

Clock     __|‾‾|__|‾‾|__|‾‾|__|‾‾|__
             t0    t1    t2    t3
Address   ==X  address valid   X=====
Command   ==X  Read            X=====
Data      ==========X data valid X===

t0 : master puts address and Read command on the bus
t1, t2 : slave decodes address and fetches the data
t2 : slave puts data on the bus
t3 : master latches (captures) the data at this clock edge

It is simple and fast, because there is no extra signalling: both sides just count clock cycles. The catch is that the clock period (or the fixed number of cycles per transfer) must be long enough for the slowest device. A common fix is to let a slow device request extra cycles, called wait states, by holding a "ready" line inactive. Also, clock skew limits how long a synchronous bus can be at a high clock rate.

Asynchronous Bus

An asynchronous bus has no clock. Instead, master and slave coordinate with a handshake on two control lines, which we will call Master-ready and Slave-ready. In the full (four-phase) handshake for a read:

Step 1: Master puts address and Read command on the bus, then raises Master-ready.
Step 2: Slave sees Master-ready, decodes the address, puts the data on the bus,
        then raises Slave-ready.
Step 3: Master sees Slave-ready, latches the data, then drops Master-ready.
Step 4: Slave sees Master-ready drop, removes the data, then drops Slave-ready.
        (The bus is now free for the next transfer.)

Master-ready  ____|‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾|________
Slave-ready   __________|‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾‾|___
                  1     2          3     4

Each signal change is a response to the other side's change, so the transfer automatically takes exactly as long as the devices need. A fast memory answers quickly; a slow one answers slowly; no one has to plan for the worst case.

Aspect

Synchronous

Asynchronous

Timing reference

Common clock

Handshake signals

Logic

Simpler

More complex (handshake state machines)

Speed of a transfer

Fixed number of cycles, set by the slowest device (unless wait states are used)

Adapts to each device's actual speed

Overhead

Low

Each handshake step adds signal round-trip delay

Bus length / mixed devices

Limited by clock skew

Handles mixed-speed devices and longer distances well


Worked Example: Bus Bandwidth and Burst Transfers

Bus bandwidth is the amount of data the bus can move per second. In the ideal case where one data transfer happens every clock cycle:

Bandwidth = (data bus width in bytes) × (transfers per second)

A 64-bit (8-byte) bus at 100 MHz, one transfer per cycle: 8 × 100 × 106 = 800 MB/s (using 1 MB = 106 bytes, as is usual for rates).

Problem. A synchronous bus has a 10 ns clock and a 32-bit data bus. To read from memory, the master sends the address in one cycle; memory then needs 40 ns before data is ready; then each data word takes one cycle on the bus. Find the time and bandwidth for (a) reading one word per transaction, (b) a burst read of 4 consecutive words in one transaction (memory needs the 40 ns only for the first word, then delivers one word per cycle).

Solution. The 40 ns wait is 40 / 10 = 4 cycles.

  • (a) 1 (address) + 4 (wait) + 1 (data) = 6 cycles = 60 ns per 4 bytes. Bandwidth = 4 B / 60 ns ≈ 66.67 MB/s. Reading 4 words this way takes 4 × 60 = 240 ns.

  • (b) 1 (address) + 4 (wait) + 4 (data) = 9 cycles = 90 ns per 16 bytes. Bandwidth = 16 B / 90 ns ≈ 177.78 MB/s.

(a) one word:  | A | w | w | w | w | D |                     6 cycles
(b) burst:     | A | w | w | w | w | D1 | D2 | D3 | D4 |     9 cycles
               A = address,  w = wait,  D = data word

The burst is about 2.7 times faster because the address and the memory's start-up latency are paid only once. This is exactly why caches fetch whole blocks using burst transfers (see Cache Memory).


Bus Arbitration

A bus can carry only one transfer at a time, but there may be several devices able to act as masters: the CPU, one or more DMA controllers, or several processors. When two of them want the bus at the same moment, someone must decide who goes first.

Bus arbitration is the process of selecting which of the devices requesting the bus becomes the next bus master.

A good arbitration scheme should (1) give the bus to exactly one master at a time, (2) respect priorities (a device with tight timing, like a disk transfer that would lose data, needs the bus soon), and (3) be fair, so that low-priority devices do not starve forever.

Arbitration schemes come in two families:

  • Centralized arbitration: a single hardware unit, the bus arbiter (often part of the CPU or chipset), decides.

  • Distributed arbitration: all devices take part equally, and the decision emerges from their combined signals. There is no central arbiter.


Centralized Arbitration

1. Daisy Chaining

All devices share one Bus Request (BR) line, wired so that any device can activate it. The Bus Grant (BG) signal is passed from device to device like a baton, in a chain. A third shared line, Bus Busy (BBSY), shows that the bus is in use.

               BR (shared, any device can activate it)
   +--------+  <-------------+---------------+---------------+
   |        |                |               |               |
   |  Bus   |  BG1      +---------+  BG2  +---------+  BG3  +---------+
   | arbiter|--------->| Device 1|------>| Device 2|------>| Device 3|
   |        |           +---------+       +---------+       +---------+
   |        |  <-------------+---------------+---------------+
   +--------+       BBSY (shared)

How it works:

  1. One or more devices activate BR.

  2. When the bus is free, the arbiter activates BG1 to the first device.

  3. If device 1 requested the bus, it keeps the grant (does not pass it on), activates BBSY and becomes master. If not, it passes the grant to device 2 on BG2, and so on.

  4. When the master finishes, it releases BBSY.

The priority is fixed by position: the device closest to the arbiter always wins.

  • Advantages: very simple, only about 3 arbitration lines no matter how many devices; easy to add devices.

  • Disadvantages: fixed priority, so devices far down the chain can starve; the grant ripples through each device, so it is slow for long chains; if one device fails (does not pass the grant on), every device after it is cut off.

2. Polling (Rotating Priority)

Devices still share a BR line, but instead of a grant chain, the arbiter has a set of poll lines carrying a device number. For n devices, ⌈log2n⌉ poll lines are enough.

  1. When BR is active, the arbiter puts device numbers on the poll lines one after another (using a counter).

  2. When a requesting device sees its own number, it activates BBSY. The arbiter stops counting, and that device uses the bus.

  3. When the bus is released, the arbiter can resume counting from the next number instead of starting from 0.

Continuing from the next number gives rotating priority, which is fair. Priority can also be changed by software by changing the counting order. A failed device does not block the others. The cost is extra lines and the time spent counting through devices that did not request.

3. Independent Requests

Each device has its own request line BRi and its own grant line BGi to the arbiter. The arbiter sees all requests at once and grants the highest-priority one immediately, using a priority encoder plus a decoder.

               BR1 --------->            +-----------+
  Device 1  <--------- BG1               |           |
               BR2 --------->            |    Bus    |
  Device 2  <--------- BG2               |  arbiter  |
               BR3 --------->            | (priority |
  Device 3  <--------- BG3               |  encoder) |
                                         +-----------+

This is the fastest scheme, and the priority logic can be anything (fixed, rotating, or programmable). The cost is 2n lines for n devices plus a more complex arbiter.

Comparing the Centralized Schemes

Aspect

Daisy chaining

Polling

Independent requests

Arbitration lines for n devices

3 (BR, BG chain, BBSY)

⌈log2n⌉ poll lines + BR + BBSY

2n (one BR and one BG per device)

Speed

Slow (grant ripples through chain)

Medium (counting through devices)

Fastest

Priority

Fixed by physical position

Flexible, can rotate

Flexible, decided by arbiter logic

Fairness

Poor: far devices may starve

Good with rotation

Depends on arbiter policy

Effect of one failed device

Devices after it are cut off

Others unaffected

Others unaffected

Cost

Lowest

Medium

Highest

Worked example. For 16 devices: daisy chaining needs 3 arbitration lines; polling needs log216 = 4 poll lines + BR + BBSY = 6 lines; independent requests need 2 × 16 = 32 lines. (Some textbooks also count a shared BBSY line with independent requests, giving 33; read the question's assumptions carefully.)


Distributed Arbitration

In distributed arbitration there is no central arbiter, which removes a single point of failure. A widely taught method gives each device a unique ID number, and all devices compete at the same time using a set of shared arbitration lines, one per ID bit.

The lines are built with open-collector (or open-drain) drivers, so a line is 1 if any device drives a 1 on it: the line acts as a wired-OR. The rule each competing device follows:

Compare your ID with the lines, starting from the most significant bit. At the first bit where the line shows 1 but your ID has 0, stop driving that bit and all lower bits. Start driving them again if that condition goes away.

The pattern on the lines settles to the highest ID among the competitors, and that device wins.

Worked Example: Devices 9, 6 and 11 Compete

Four arbitration lines (4-bit IDs). IDs: 9 = 1001, 6 = 0110, 11 = 1011. The table shows what each device drives and the resulting wired-OR on the lines, step by step (real hardware settles continuously; steps make it easy to follow).

Step

Device 9 drives

Device 6 drives

Device 11 drives

Lines (OR)

0

1001

0110

1011

1111

1

1000

0000

1000

1000

2

1001

0000

1011

1011

3

1000

0000

1011

1011 (stable)

  • Step 0 → 1: Lines show 1111. Device 6 has 0 in the top bit where the line shows 1, so it withdraws completely. Devices 9 and 11 have 0 in bit 2 where the line shows 1, so both withdraw bits 2, 1, 0.

  • Step 1 → 2: Lines show 1000. Now neither 9 nor 11 sees a conflict, so both drive their full IDs again.

  • Step 2 → 3: Lines show 1011. Device 9 (1001) has 0 in bit 1 where the line shows 1, so it withdraws bits 1 and 0. Device 11 sees its own ID on the lines.

  • Result: the lines settle at 1011 = 11. Device 11, the highest ID, wins and becomes bus master.

This simple rule works for any set of competitors: the settled value always equals the largest ID. Since IDs are fixed, the scheme gives fixed priority; fairness can be added by, for example, not letting the last winner compete again until others have had a turn. A closely related bit-by-bit idea is used in the CAN bus found in cars; there the line behaves as a wired-AND (a "dominant" 0 overrides a 1), so the lowest ID has the highest priority.

Other Distributed Methods

  • Self-selection: each device places its request on the bus and, by looking at all requests, decides for itself whether it has the highest priority.

  • Collision detection: devices just start transmitting; if two collide, both detect it, back off for a random time and try again. Classic shared Ethernet (CSMA/CD) worked this way.

Centralized vs Distributed

Aspect

Centralized

Distributed

Decision made by

One bus arbiter

All competing devices together

Single point of failure

Yes, the arbiter

No

Hardware

Simpler devices, one smart arbiter

Every device needs arbitration logic

Examples

Daisy chain, polling, independent requests

ID-based (wired-OR), CAN bus, CSMA/CD


The shared parallel bus is the classic textbook model, and it is still the right model for exam questions. Modern high-speed systems, however, have largely replaced long shared parallel buses with point-to-point serial links. At very high clock rates, many parallel wires are hard to keep in step (skew), and every extra device on a shared wire adds electrical load.

PCI Express (PCIe) is the main example. Each device gets its own link made of one or more lanes (x1, x4, x8, x16), each lane being a pair of one-way serial connections. Switches route packets between links, so arbitration happens inside the switches rather than on one shared wire.

PCIe generation

Raw rate per lane

Encoding

Approx. data per lane, each direction

1.0

2.5 GT/s

8b/10b

250 MB/s

2.0

5 GT/s

8b/10b

500 MB/s

3.0

8 GT/s

128b/130b

≈ 985 MB/s

4.0

16 GT/s

128b/130b

≈ 1.97 GB/s

5.0

32 GT/s

128b/130b

≈ 3.94 GB/s

These figures follow from the formula (rate × encoding efficiency ÷ 8 bits per byte); for example, PCIe 3.0 gives 8 × 109 × 128/130 ÷ 8 ≈ 985 MB/s. Real throughput is a bit lower because of packet headers. A x16 PCIe 4.0 slot therefore carries about 16 × 1.97 ≈ 31.5 GB/s each way. The ideas of this chapter (masters and slaves, request and grant, burst transfers, bandwidth) all still apply; they have just moved into packets and switches.


Common Mistakes

  • Using bits instead of bytes for address capacity. In a byte-addressable memory, m address lines reach 2m bytes. In a word-addressable memory they reach 2m words.

  • Thinking the address bus is bidirectional. The data bus is bidirectional; addresses normally flow only from the master.

  • Saying asynchronous buses are always faster. They adapt to each device, but each handshake step costs round-trip delay. A synchronous bus is often faster when all devices are fast.

  • Getting daisy-chain priority backwards. The device nearest the arbiter has the highest priority.

  • Counting lines in independent requests as n. Each device needs both a request and a grant line: 2n.

  • Assuming distributed arbitration has no priority. In the ID-based scheme the highest ID always wins.


GATE and Interview Questions

A processor has 24 address lines and a byte-addressable memory. What is the maximum memory size?

224 bytes = 16 MB.

Which centralized arbitration scheme is the fastest, and which uses the fewest lines?

Independent requests is the fastest (all requests are seen in parallel). Daisy chaining uses the fewest lines (about 3, independent of the number of devices).

In daisy chaining, why can a device far from the arbiter starve?

The grant always reaches devices closer to the arbiter first. If any of them keeps requesting, it keeps capturing the grant, and the grant never travels further down the chain.

A synchronous bus has a 5 ns clock. A read takes 1 cycle for the address, 3 cycles of memory latency and then 1 cycle per 8-byte word. What is the bandwidth for a burst of 8 words?

Cycles = 1 + 3 + 8 = 12, i.e. 60 ns for 64 bytes. Bandwidth = 64 / 60 ns ≈ 1066.7 MB/s (about 1.07 GB/s).

How many lines does polling need for 32 devices?

log232 = 5 poll lines, plus the shared Bus Request and Bus Busy lines, so 7 lines in total.

Explain the four-phase handshake of an asynchronous bus.

(1) Master places address/command and raises Master-ready. (2) Slave responds with data and raises Slave-ready. (3) Master latches the data and drops Master-ready. (4) Slave removes data and drops Slave-ready. Each step waits for the previous signal change, so the transfer adapts to the device's speed.

In ID-based distributed arbitration, devices with IDs 5 (0101) and 6 (0110) compete. Which wins and what do the lines show?

At first the lines show 0111. Device 5 sees a 1 on bit 1 where it has 0, so it withdraws bits 1 and 0 and drives only 0100. The lines settle at 0110, so device 6 wins.

Why have modern computers moved from shared parallel buses to point-to-point serial links like PCIe?

At high frequencies, keeping many parallel wires in sync (skew) and driving many devices on one wire (loading, reflections) become very hard. Point-to-point serial lanes avoid sharing, can run much faster, and bandwidth scales by adding lanes. Switches handle routing and arbitration.


Summary

  • A bus is a shared set of wires; only one device can drive it at a time.

  • The system bus has an address bus (m lines → 2m locations), a bidirectional data bus (bits per transfer) and a control bus (read/write, timing, interrupts, arbitration).

  • A single bus is cheap but becomes a bottleneck; multiple-bus hierarchies connected by bridges separate fast and slow traffic.

  • Synchronous buses use a clock and a fixed schedule (with wait states for slow devices); asynchronous buses use a Master-ready/Slave-ready handshake.

  • Burst transfers pay the address and latency cost once, giving much higher bandwidth.

  • Centralized arbitration: daisy chaining (3 lines, fixed priority, slow), polling (log2n poll lines, rotating priority), independent requests (2n lines, fastest).

  • Distributed arbitration: devices drive their IDs on wired-OR lines and withdraw when they see a higher bit; the highest ID wins. No central point of failure.

  • Modern systems use point-to-point serial links (PCIe), but the same concepts of masters, grants, bursts and bandwidth still apply.

A bus trades wires for rules: sharing one road is cheap, but it only works if everyone agrees on timing and on who goes next.