Making it faster

The 6502 from Synthesis runs at up to 18.5 MHz on the UP5K. The counter from Inside an FPGA runs at 95. This page is about what decides that, and the tricks a designer has for changing it. Most of them trade one thing for another: speed for size, or the time an answer takes for how many answers come out.

1 · What sets the clock

Clocked circuits set the rule: between one clock edge and the next, every signal leaving a flip-flop has to get through the logic to the next flip-flop, and arrive there a little before the next edge (the flip-flop’s setup time). The slowest route between two flip-flops is the critical path, and the clock can’t go faster than it allows.

On an FPGA, a path has these delays:

The flip-flop it starts from takes a moment after the clock edge to change its output.
Each LUT and each step along a carry chain takes its own time.
So do the wires and switches between them.
The flip-flop at the end needs its setup time.

nextpnr knows each delay for the UP5K, adds them up along every path in the design, and reports the slowest.

Here’s a small job to time: the largest of eight numbers. Written the obvious way, each comparison keeps the larger of the best so far and the next number, so there are seven comparisons in a row, each waiting for the one before. (The design takes its eight numbers into flip-flops and puts its answer into one, so the path that counts is the comparisons in between.)

The critical path through seven comparisons in a row, as nextpnr reports it after placing and routing the design on the UP5K: a block for each delay along it, coloured by kind (hover over one for its time). It’s 69.5 ns, so the clock can go up to 14.4 MHz. More than half of it, 36.8 ns, is wiring.

The wiring is the surprise. On an FPGA, the signal goes through switches as well as along wires, and here that takes longer than the logic itself.

2 · A tree instead of a chain

The seven comparisons don’t have to wait for each other. Compare the numbers in pairs: four comparisons side by side, then two, then one. It’s still seven comparisons, but only three in a row. That’s a tree.

The chain and the tree, to the same scale. The tree’s critical path is 31.9 ns, so up to 31.4 MHz: more than twice as fast, from the same seven comparisons, rearranged.

This only works because the order doesn’t matter: the largest of eight is the same whichever pairs are compared first. Addition is like that too, and there’s a twist with addition: Yosys rearranges it by itself.

Four 16-bit numbers added, written as a chain, ((a + b) + c) + d, and as a tree, (a + b) + (c + d). At stage 1 the two are different shapes: three adders in a row, or two side by side and one after. At stage 4 they’re the same: 79 LUTs and 16 carry cells each. Yosys gathers a sum of several numbers into one cell before building it, and arranges it itself, so the brackets make no difference. (The tests check the two finished netlists are identical.)

Yosys does this for sums, but not for comparisons, or most other things, so a designer still has to think about the shape of their logic.

3 · Pipelining

The tree still does three comparisons in one clock cycle. Pipelining splits them up: a row of flip-flops after each level, so that each clock cycle only has to fit one comparison. The answer now takes more clocks to come out, but a new set of numbers can go in every clock, while the ones before are still on their way through.

A laundry works the same way. A load spends an hour washing, then an hour drying, then an hour being folded. Doing one load at a time, you finish a load every three hours. Once the second load goes into the washer while the first is drying, you finish one every hour, though each still takes three hours from start to finish. Two numbers describe it:

Latency: how long from a set of inputs going in to its answer coming out.
Throughput: how many answers come out a second.

Pipelining makes the latency a little longer, in clocks, and the throughput much higher.

Each design simulated gate by gate, as Yosys builds it, and fed a new set of eight numbers every clock: A, B, C and so on, listed below. Click Clock to step, or Run for 16 clocks. The answer for row says which set the output y is the answer to. The chain and the tree give each answer 2 clocks after its numbers go in (one clock into the input flip-flops, one through the comparisons). The pipeline takes 4, and its rows ab and abcd show the levels in between, each a clock behind the one before. All three give a new answer every clock. The speed and size are nextpnr’s and Yosys’s for the UP5K; edit the Verilog and it’s simulated again, but not timed.

The largest of eight	Comparisons in a row	Fastest clock	Latency	Answers a second
A chain	7	14.4 MHz	2 clocks = 139 ns	14.4 million
A tree	3	31.4 MHz	2 clocks = 64 ns	31.4 million
The tree, pipelined	1	76.3 MHz	4 clocks = 52 ns	76.3 million

The pipeline is more than five times as fast as the chain. Its latency is twice as many clocks as the tree’s, but its clocks are so much shorter that, in nanoseconds, its answers here even come out sooner.

All three critical paths. The pipeline’s is 13.1 ns: one comparison and its wiring, from one row of flip-flops to the next.

The cost is flip-flops: the pipeline has 120, against the tree’s 72. On an FPGA they’re cheap, because every logic cell has one beside its LUT, so a LUT and the flip-flop it feeds fit in one cell. That’s why FPGA designs are often pipelined heavily. Most fast hardware works this way. A modern CPU, for one, works on several instructions at once, each at a different stage.

4 · The other way: one part, used in turn

Sometimes the speed is there to spare, and it’s room on the chip that’s short. Then the trade goes the other way: one part does several jobs, one after another.

Take four voices of a synthesiser, mixed: each voice’s sample is multiplied by its volume, and the four are added up. Four multipliers can do it all at once, a new mix every clock. Or one multiplier can take each voice in turn, a voice a clock, with a counter i saying whose turn it is: a little state machine. Then a mix takes four clocks.

The four voices fed a new set of samples and volumes every clock (four multipliers), or every 4 clocks (one multiplier, in turn), simulated gate by gate. With one multiplier, i counts round the voices and total adds up the mix so far. Each mix comes out 6 clocks after its samples go in (one clock to take the voice in, one to multiply and add, for each of four voices, and one more to hand the total to y), and a new one every 4. Its product p is written once, on a wire of its own: write s * v twice and Yosys may build two multipliers.

Mixing four voices	Size	Fastest clock	Mixes a second
Four multipliers, made of LUTs	745 LUTs	24.7 MHz	24.7 million
One multiplier, in turn	227 LUTs	35.1 MHz	8.8 million
Four DSP blocks	4 DSP blocks, nothing else	50.5 MHz	50.5 million
One DSP block, in turn	1 DSP block and 69 LUTs	90.1 MHz	22.5 million

Four multipliers made of LUTs take 745 of the UP5K’s 5,280 LUTs, a seventh of the chip. Sharing one takes less than a third of that.

The last two rows use the UP5K’s DSP blocks, its ready-made multipliers, of which it has eight. With four of them, Yosys fitted the whole mixer inside the blocks: the input flip-flops, the multiplies, the additions (each block’s adder passing its total to the next) and the output flip-flop, with no LUTs at all.

For sound, sharing wins easily. A mix is needed 48,000 times a second. Even at the board’s 12 MHz clock, one multiplier can do 250 multiplications in the time between two samples, enough for 250 voices, or for one voice’s filter as well as its volume. Many sound chips work this way: Yamaha’s FM chips of the 1980s, for one, worked out their voices one after another, through the same hardware.

5 · Why the 6502 stops at 18.5 MHz

The 6502 core’s critical path on the UP5K: 54.0 ns, so up to 18.5 MHz, with 33.5 ns of it in wiring.

nextpnr’s report says where the path goes. It starts at the instruction register, which holds the opcode, and goes through the decoding that picks the ALU’s inputs. Then comes a decimal-mode ADC: add the low digits, correct them if they went past 9, add the high digits, correct those. It ends at the Z flag. It’s the longest piece of arithmetic the 6502 does in one cycle, with everything that decides what to add in front of it.

It could be pipelined: decode in one clock, add in the next. But this core matches the real chip cycle for cycle, every bus access in the same cycle as the original, and a pipeline would change which cycle does what. A core that didn’t have to match could split its work differently and run faster. This one doesn’t need to: on the board, its clock enable runs it at 1 MHz, about the speed of the home computers it was built into, from the board’s 12 MHz clock.

Summary

The critical path, the slowest route from one flip-flop to the next, sets the fastest clock. On an FPGA, much of it is wiring.
A tree instead of a chain makes the path shorter with the same logic, when the order doesn’t matter. Yosys does it for sums by itself.
Pipelining adds flip-flops along the path: more clocks of latency, but a much faster clock, and so more throughput. On an FPGA, flip-flops are nearly free.
Sharing one part between several jobs, in turn, goes the other way: less throughput, much less space. For sound, there’s speed to spare.