Part 3. Data · lesson 19 of 42

19. Circular buffers

A circular buffer is a queue of pages in a core's L1: one side puts tiles in at the end, the other takes them out at the front, and when either side reaches the last page it goes on at the first. This lesson relies on lesson 18, The three kernels.

Why more than one page

In the last lesson the buffer held one tile. reader.cpp put a tile in and writer.cpp took it out, and reader.cpp could not start the next read until writer.cpp had finished with the tile in the only page. The two CPUs took turns when they could have worked together.

With room for two tiles reader.cpp fills the second page while writer.cpp still sends the first. The buffer is the place where the two meet, and the more pages it has, the further the filling kernel may run ahead before it has to wait.

The name comes from how it is built: the pages lie one after the other in L1, and the buffer remembers where the next tile goes and where the oldest tile is. When either reaches the last page, it wraps to the first, as if the pages were in a ring. Your code never sees this: get_write_ptr and get_read_ptr give the right address.

A buffer of four pages with two tiles in it. writer.cpp takes the oldest, page 0; reader.cpp puts the next at page 2.

The general form

km.Buffer(index=INDEX, format=DTYPE, page_bytes=BYTES, pages=PAGES)

reader.reserve(INDEX, 1);   // wait for a free page
...                         // fill get_write_ptr(INDEX)
cb_push_back(INDEX, 1);     // the page is full: the other side may take it

writer.wait_front(INDEX, 1);  // wait for a full page
...                           // use get_read_ptr(INDEX)
cb_pop_front(INDEX, 1);       // the page is free: the other side may fill it

• PAGES is the number of pages: how many tiles may be waiting in the buffer at once.
• reserve(INDEX, 1) returns when at least one page is free. With every page full, it waits.
• cb_push_back hands the page just filled to the other side; cb_pop_front hands back the oldest full page.
• Pages come out in the order they went in.
• One buffer has one side that fills it and one that empties it. A program with more stages has more buffers, each with its own INDEX; the next lesson has three.

One line at a time

program = km.Program(
    "circular_buffers",
    kernels=HERE / "kernels",
    handlers=HERE / "kernels" / "handlers.h",
    buffers=[
        km.Buffer(
            index=0, format="uint32", page_bytes=source.page_bytes, pages=pages
        )
    ],
    compile_args={
        "reader": source.accessor_args(),
        "writer": destination.accessor_args(),
    },
)

This is the only line that changes from the last lesson: pages=pages. The program loads three times, with 1, 2 and 8 pages in the buffer, and each time copies 64 tiles in one command. The kernels are those of lesson 18, The three kernels, unchanged.

The whole program

circular_buffers.py

"""Circular buffers: the same copy with room for 1, 2 and 8 tiles in the buffer."""

from pathlib import Path

import numpy as np

import komorebi as km

HERE = Path(__file__).resolve().parent
TILES = 64

with km.Session() as session:
    numbers = np.arange(TILES * 32 * 32, dtype=np.uint32).reshape(TILES * 32, 32)
    source = session.tensor(numbers, "uint32", "tile")
    destination = session.tensor(np.zeros_like(numbers), "uint32", "tile")

    for pages in (1, 2, 8):
        destination.write(np.zeros_like(numbers))
        program = km.Program(
            "circular_buffers",
            kernels=HERE / "kernels",
            handlers=HERE / "kernels" / "handlers.h",
            buffers=[
                km.Buffer(
                    index=0, format="uint32", page_bytes=source.page_bytes, pages=pages
                )
            ],
            compile_args={
                "reader": source.accessor_args(),
                "writer": destination.accessor_args(),
            },
        )
        run = session.load(program)
        arguments = [source.address, 0, destination.address, 0, TILES]
        handle = run.submit("copy", group=(0, 1), args=arguments)
        microseconds = run.wait(handle, timeout=10.0).microseconds
        run.stop()
        print(
            f"buffer pages {pages}: {TILES} tiles copied in "
            f"{microseconds:5.1f} microseconds"
        )

        (source_pages,) = session.read(source)
        (destination_pages,) = session.read(destination)
        assert (destination_pages == source_pages).all()

The kernel files and the header are those of lesson 18.

buffer pages 1: 64 tiles copied in  54.6 microseconds
buffer pages 2: 64 tiles copied in  32.9 microseconds
buffer pages 8: 64 tiles copied in  32.6 microseconds

With one page the copy took 55 microseconds. With two pages it took 33, and with eight it took 33: room for a second tile made the loop faster by a third, and more room did not help, since room was no longer what held it back. The script checks after every run that all 64 tiles arrived.

Common mistakes

• Thinking that more pages are always faster. Two were enough here. Pages take L1, 1.4 MB in all, and a program needs its L1 for other things.
• Forgetting cb_pop_front. The buffer fills up and reader.cpp waits for ever, as in lesson 16, Reading from DRAM: more pages only make that happen a command or two later.
• Letting the two kernels disagree on how many tiles pass. Each tile pushed is one that has to be popped, or the buffer is left with tiles in it for the next command.

Next: lesson 20, Computing on a tile puts the compute kernel between the two data-movement kernels.