Topic — Command streams: Tetris on a column

Needs: Lesson 7 — Tasks: code that runs when a wavelet arrives, Lesson 9 — Broadcast and reduce along a row.

A column of PEs holds a Tetris board, one row of the board per PE. A stream of fixed-size command packets flows down the column. Every PE forwards each packet to the PE below and applies it to its own row. The PEs never decide anything about the game: the host plays it. The host program, init.py, chooses the moves, checks every collision, computes the rotated pieces and the rows where they land, decides when a piece locks, and finds the full rows. The PEs keep the board and a copy of the falling piece, and change them exactly as the commands say. Every row PE receives the same sequence of commands. Only a CLEAR changes on the way down: each PE puts its own row's state into the packet as it forwards it.

The animation is drawn by animate.py on the host from a command stream; it shows a longer game than the test rows run.

What you will be able to do

• Design fixed-size command packets and stream them through a column of PEs that each forward and apply them.
• Change a field of a packet as it passes a PE.
• Send results sideways to a column of collector PEs, and end every PE's run by a count.
• Say which work a command stream leaves to the host and which it gives the PEs.

Who does what

Work	Done by
Choosing pieces, moves and rotations	the host
Checking that a move, rotation or drop fits on the board	the host
The rotated piece's shape, and the row a hard drop lands on	the host, sent in the packet
Deciding when the piece locks, and which rows are full	the host
The score	the host, sent in SNAP packets
Moving the piece left, right and down one row	each row PE, on its own copy
Merging the piece into the board, and deleting a full row	each row PE, on its own row
Recording the board at each SNAP	each row PE and each moat PE

The program

                x=0          x=1
  y=H+1                     input       streams the command words down
  y=H                       ctrl        relays them to the rows
  y=H-1      moat H-1  <--  row H-1     top row of the board
   ...         ...          ...
  y=0        moat 0    <--  row 0       bottom row

Three colorpairs carry the data. cmd takes the stream from input to ctrl, dn takes it down the column of row PEs, and lx carries each row PE's snapshots left to its moat PE. All three use the colorpair swap of lesson 8, so each region has one rule per color.

init.py plays a game on the host and writes cmds.bin, the command stream, which the Makefile loads into input with miset. Each row PE also gets its row number. ref.py replays the same commands with the meaning the row PEs give them, and display.py compares every snapshot that the row PEs and the moat PEs recorded with the replay. The rows of test.rc:

Row	Board height H	Command words	Seed	Packets	Snapshots	Rows cleared
tutorial	8	900	379	100	47	1
taller	10	1800	138	200	86	1

The packets

Every command is 9 words (xp, 16 bits each):

Word	Field	Meaning
0	cmd	the command, below
1	w1	SPAWN: the piece's row · DROP: the landing row · CLEAR: the row to delete · START: the number of SNAPs
2	w2	SPAWN, ROTATE: the piece's height · CLEAR: the state of the row above
3–6	w3–w6	SPAWN, ROTATE: the piece's four rows as bit masks
7–8	w7–w8	SNAP: the score, low and high word

Code	Command	What a row PE does
0	TICK	moves its copy of the piece down one row
1	LOCK	ORs its row of the piece into its board row
2	CLEAR	deletes row w1: every row from w1 up takes w2, the state of the row above
3	SPAWN	sets the piece from w1–w6
4	SNAP	records its row and sends it, with the score, to its moat PE
5	GAMEOVER	nothing
6	LEFT	shifts the piece's masks right by 1 (bit c is column c)
7	RIGHT	shifts the piece's masks left by 1
8	ROTATE	replaces the piece's height and masks from the packet
9	DROP	sets the piece's row to w1
10	START	sends w1, the number of SNAPs, to its moat PE

The host pads the stream with GAMEOVER packets to exactly NCMDS words, and puts START first.

The code

input.w and controller.w

input holds the whole stream in memory and sends it word by word:

xp cmds[n=NCMDS];

{
    let i in [0, NCMDS);
    ∀i {
        cmd[] <- cmds[i];
    }
}

ctrl only relays: it receives each word on cmd and sends it on dn. A different source of commands, such as a live input, would replace input without a change to the column below.

row.w: receive, forward, apply

A row PE runs one loop iteration per packet. It receives all 9 words into variables, then forwards the packet, then applies it:

    let i in [0, NCMDS / 9);
    ∀i {
        cmd_type <- dn[];
        w1       <- dn[];
        w2       <- dn[];

        w2_out <- w2;
        if (cmd_type == 2) w2_out <- row_state[0];
        dn[] <- cmd_type;
        dn[] <- w1;
        dn[] <- w2_out;

The bottom row forwards too; its route dnp [CXD|D] drops those wavelets at the bottom edge. Forwarding before applying lets the next PE start on the packet while this one works.

The commands are a chain of ifs on cmd_type. For example:

        // LOCK (1): merge the tracked piece into the board
        if (cmd_type == 1) {
            piece_top <- cur_y + cur_h;
            if (my_idx >= cur_y && my_idx < piece_top) {
                offset <- my_idx - cur_y;
                if (offset == 0) my_mask <- cur_row0;
                if (offset == 1) my_mask <- cur_row1;
                if (offset == 2) my_mask <- cur_row2;
                if (offset == 3) my_mask <- cur_row3;
                row_state[0] <- row_state[0] | my_mask;
            }
            cur_h <- 0;
        }

This is a dispatch written in software. Lesson 7's dispatch picks a handler in hardware, from the wavelet that starts a task. A packet here is 9 words that must stay together, so the PE reads the whole packet on the main thread, forwards it, and then branches on its first word. Forwarding changes only a CLEAR, as the next section shows.

CLEAR: rewriting a field in flight

When row w1 is full, the host sends a CLEAR. Every row from w1 up must take the state of the row above it. A row PE knows only its own row, but the packet passes the rows from the top down. So each row PE puts its own state into w2 as it forwards the packet: the PE below receives the state of the row above it. The top row receives the 0 that the host sends, and becomes empty. The host sends one CLEAR per full row, highest first, so each row number is still valid when its CLEAR arrives.

moat.w and the end of the run

On SNAP a row PE records its row in history and sends its row and the two score words left on lx. Its moat PE collects them. The moat needs to know how many to expect, so the first packet, START, carries the number of SNAPs, and each row PE passes it on to its moat:

{
    nsnap <- lx[];

    ∀i in [0, nsnap) {
        row_val         <- lx[];
        slo             <- lx[];
        shi             <- lx[];
        history[i]      <- row_val;
        score_lo_buf[i] <- slo;
        score_hi_buf[i] <- shi;
    }
}

nsnap arrives at run time, and a ∀ range can end at a run-time value.

Every PE's work is fixed by a count: input and ctrl move NCMDS words, each row PE handles NCMDS / 9 packets, and each moat PE takes nsnap snapshots. So every PE's program ends by itself.

What the hardware does

The column is a pipeline. Each row PE holds one packet at a time. While it applies a packet, the PE below works on the previous one, so many packets are in the column at once. The run takes about 120 cycles per packet: the tutorial row's last memory write is at cycle 12,075 and the taller row's at 23,229, for 100 and 200 packets. Twice the packets took about twice the time.

A slow PE slows everything above it. A row PE that has not finished a packet does not receive the next one. Its input queue and the routers above fill, and the PE above stops at its send. The same holds for lx: if a moat PE fell behind, its row PE would stop at a SNAP, and the column above with it.

The stream lives in one PE's memory. input holds all NCMDS words, so a longer game takes more of its 48 KB: 9000 words, a long game, take 18 KB. A real application would stream the commands in from outside the region instead.

Budget. 6 colors of 24. A row PE receives on one input queue and sends on two output queues.

Run it

In your copy of the tutorial (see Lesson 1):

cd tutorial/ext-algorithms/command-streams
make TEST=tutorial               # the 8-row game
make TEST='*'                    # both rows
make test-tutorial/test          # runs the tutorial row again and prints every snapshot

A passing row prints one line, such as command-streams : 0:16.20 PASS tutorial [ H=8 NCMDS=900 SEED=379 ARCH=sdr ], and its make-log ends with

PASS: All 47 grid.history snapshots match (8 rows each)
PASS: All 47 fan.history snapshots match (8 rows each)

A failing row prints FAIL. Its make-log has a MISMATCH line for each snapshot row that differs, with both values in hexadecimal, and prints the first differing board as the simulator left it and as the replay expects it. make test-tutorial/animate writes tetris.gif for the row's game when Pillow is installed.

Pitfalls

• The PEs trust the host. A row PE applies a LEFT even when the piece is at the wall, and a LOCK wherever the piece is. The test compares the PEs with a replay of the same commands, so it checks that they follow the commands, not that the game is legal.
• Every packet is exactly 9 words. A PE that read 8 or 10 would take every later packet out of step, and every PE below it would too.
• NCMDS must be a multiple of 9, and the same in every kernel. Paint passes the one variable to all four kernels.
• A changed seed needs make clean. cmds.bin does not depend on SEED in the Makefile, so make reuses the old stream.
• Run init.py only through make. Each row builds in its own test-*/ directory, and make also looks for its files in the topic directory. A cmds.bin left there by running init.py by hand takes the place of every row's own stream, and the rows fail or run the wrong game.
• Both sides of && are evaluated. The LOCK test my_idx >= cur_y && my_idx < piece_top computes both comparisons. That is harmless here; it is not when a side indexes an array (lesson 2).

Exercise

In init.py, make the host send LEFT without checking the move. In the 'left' branch, move add(6) and snap() out of the if can_place(...) block, so that the packet goes out even when the move does not fit; the host's own record of the piece still moves only when it fits. Run make clean and make TEST=taller. The row still passes: why? Then look through the snapshots in test-taller/make-log for a piece that locked with fewer than four cells, and work out where its other cells went.

Next

This is the last topic of the group. The next group, Layouts and Debugging, starts with Topic — Large layouts: geovars, terminals and transports, link, which builds layouts too large to paint PE by PE, with geovars, terminals and transports.

References

• Color pairs
• Boundary operators
• Bitwise operators
• If / else
• Receiving data