Outstanding Transactions and Bursts

Outstanding transactions and bursts are the two techniques that let an SoC move data much faster than its latency would suggest. A manager that waits for each response before sending the next request can never move more than one transaction's worth of data per round trip. Allowing several transactions in flight hides the wait, and bursts let one request move many bytes. This article explains why latency limits a simple interface, derives the bandwidth from Little's law, shows with a model how much each technique gains, and explains what they cost.

11 min read | Intermediate

What You'll Learn

• Explain why one transaction at a time limits bandwidth
• Use Little's law to find how many transactions must be in flight
• Calculate the gain from bursts and outstanding transactions
• Describe what supporting outstanding transactions costs in hardware

The Problem: Waiting for Each Answer

Consider a manager that reads memory one word at a time, and waits for each response before sending the next request. If each round trip takes L cycles and moves B bytes, the most it can move is B / L bytes per cycle. In one small SoC with such a port, a read from on-chip SRAM took 4 cycles, so 4-byte reads reached at most 1 byte per cycle. A TCM read took 1 cycle and reached 4. Latency and Bandwidth measures this.

Now take a larger system. DRAM might take 100 cycles to answer. One 4-byte read every 100 cycles is 0.04 bytes per cycle, which on a 1 GHz chip is 40 MB/s, from a memory that could deliver many gigabytes per second. Nearly all the time, the wires sit idle, waiting. The latency itself is hard to reduce, because it comes from distance, clock crossings and the memory's own timing. The solution is to stop waiting.

Two Ways to Stop Waiting

A burst moves many bytes for one request. Instead of asking for one word, the manager asks for, say, 64 bytes at consecutive addresses, and the subordinate returns them back to back. The latency is paid once for the whole burst. Caches are natural users of bursts, since they fetch whole lines, as Cache Organization explains.

Outstanding transactions mean that a manager may send a new request before earlier ones have finished. With N requests in flight, N round trips overlap, and the waits overlap with them. Protocols such as AXI support this: each transaction carries an ID, so responses can be matched to requests, and with different IDs responses may even return in a different order.

Little's Law

How many transactions must be in flight? A rule from queueing theory, Little's law, gives the answer. For any system in a steady state:

items in flight = throughput x time each item spends in the system

For memory traffic, the items are bytes or transactions, and the time is the latency. To move 16 bytes per cycle through a memory with 100 cycles of latency, 16 x 100 = 1,600 bytes must be in flight at any moment. With 64-byte transactions, that's 25 outstanding transactions. With 4-byte transactions, it would be 400, far more than any real interface can track.

The same law explains why bursts and outstanding transactions work together. Larger transactions mean fewer of them are needed in flight.

A Model

A simple model makes this concrete. A link can move at most 16 bytes per cycle. Each transaction occupies its latency plus the cycles needed to transfer its data. The bandwidth is the smaller of the link's peak and the data in flight divided by the time per transaction:

bandwidth = min(peak, N x bytes per transaction / (latency + transfer cycles))

Here is that model at 50 cycles of latency, for 4-byte and 64-byte transactions:

With one 4-byte transaction at a time, the link moves under 0.1 bytes per cycle, less than one percent of its peak. With 64-byte bursts, one at a time, it moves about 1.2 bytes per cycle, about 15 times more. With 16 bursts outstanding, it reaches the full peak of 16 bytes per cycle. Even 32 outstanding 4-byte transactions reach only about 2.5. The two techniques multiply, and together they turn an idle link into a full one.

The model leaves out real effects, such as bank conflicts in DRAM and other managers competing for the link, so real systems reach somewhat less. Memory Controllers and Scheduling looks at DRAM's own limits.

What It Costs

Outstanding transactions are not free. Every transaction in flight needs storage somewhere along its path:

• The manager must remember what each pending request was for, and where to put its data, using a table of entries, for example the miss status holding registers of a cache.
• The interconnect needs buffers to hold requests and responses, and logic to track IDs.
• If responses can arrive out of order, someone must reorder them, or the manager must accept them in any order.
• The subordinate must be able to accept a new request while earlier ones are still being served.

Each of these grows with the number of outstanding transactions. Designers therefore size them from Little's law, for the latency and bandwidth the use case needs, plus a margin, and not more.

The manager side is often the real limit. A simple in-order processor that waits for each load can't issue a second one, whatever the bus supports. That is why such a core reaches only a small part of a memory system's bandwidth, and why DMA engines, which can issue many requests, are used for bulk data, as DMA Engines explains. Large processor cores use non-blocking caches and prefetchers precisely to put more requests in flight, as Multi-Level Caches and Prefetching describes.

Bursts in Detail

A burst is described by its start address, its length, the size of each beat (one data transfer, as wide as the bus) and its type. In AXI, the common types are:

• INCR: addresses increase by the beat size, the normal case.
• WRAP: addresses wrap within an aligned block, so a cache can fetch the word it needs first and then the rest of the line.
• FIXED: the address stays the same, for writing to a FIFO register.

Bursts have limits. AXI forbids a burst from crossing a 4 KB boundary, so that it never spans two pages or two subordinates. Long bursts hold a path for many cycles, which can delay other managers, so interconnects may limit their length. And bursts only help when data really is consecutive. Random accesses gain nothing from a burst, and pay for fetching data they don't use.

Ordering

When many transactions are in flight, their order matters. AXI's rule is that transactions with the same ID complete in order, and those with different IDs may complete in any order. A manager that needs results in order uses one ID, and accepts that a slow response blocks the ones behind it. A manager that can handle any order uses many IDs, and gets more parallelism. The interconnect must also keep writes and reads to the same address in a consistent order, so that a read after a write returns the new data.

Software sees this too. On a processor, a store may still be in flight when a later load is sent to a different device. If the program needs the store to reach the device first, it must use a fence, as Memory-Mapped I/O and Registers describes.

Putting Numbers on a Design

Here is how an architect uses all this. A video decoder must read 2 GB/s from DRAM at 500 MHz, which is 4 bytes per cycle. The latency from the decoder to DRAM and back is assumed to be 120 cycles. Little's law gives 4 x 120 = 480 bytes in flight. With 64-byte bursts, that is 7.5, so the decoder needs at least 8 outstanding reads, and a design would allow 12 or 16 for margin, because latency rises when DRAM is busy. If the vendor's decoder supports only 4, it will reach about half the required bandwidth, and the problem must be fixed before the chip is built.

Writes Are Different

Writes can often be handled more cheaply than reads. A write doesn't need data to come back, only an acknowledgment, so many systems let the interconnect or the memory controller accept a write early, store it in a buffer, and send the response at once. This is called a posted or early-response write, and it makes write latency appear very short to the manager. The price is that the write is not yet in memory when the response arrives, which matters when another agent must see the data, or when the system must be sure the write has really happened before going on. AXI lets a manager ask for the response only once the write has reached its final destination, for the cases that need it.

Reads can't be hidden this way, because the manager needs the data. That is why read latency, and the number of reads in flight, usually decide how fast a block can process data.

Common Mistakes