Blog

Sorting networks in RTL and in HLS: SNpy

Written from chapters 6 to 8 of my PhD thesis (EPFL, 2021).

Este post está disponível apenas em inglês.Cet article n'existe qu'en anglais.

The upgraded muon interface of ATLAS (MUCTPI) has to pick the 16 muon candidates with the highest transverse momentum out of 352, in every bunch crossing, 40 million times per second, always with the same delay. The method used in the previous system could not be scaled to that size. This post describes how I arrived at a sorting network of 32 steps, the Python package that made the search possible, and what happened when I implemented the same network twice, once in VHDL and once in C++ for high-level synthesis.

Why the old method stops working

The Run 2 firmware chose 2 candidates out of 26 by making every pairwise comparison at once: 325 comparators, then logic that finds the candidate that wins all its comparisons. For 352 inputs the same scheme needs 61,776 comparators. Worse, the outputs cannot be found in parallel, because finding the second highest requires knowing the first, and so on sixteen times.

I tried it anyway, to have numbers. Above 104 inputs synthesis had not finished after a week. Above 88 the design could not be routed. At 88 inputs the combinational delay was already 120 ns, 60% of the latency budget of the whole board.

Block diagram of the muon sector data processing in the MUCTPI, with sorting and multiplicity blocks, next to a plot of resources and delay growing steeply with the number of inputs for the Run 2 algorithm
Where sorting sits in the MUCTPI, and why the Run 2 method cannot be stretched from 26-to-2 to 352-to-16 (PhD technical defence slides).

Sorting networks

A sorting network is built from one element, the compare-exchange: two values go in, the larger comes out on one line and the smaller on the other. The network is a fixed list of such operations on fixed pairs of lines. Operations that do not share a line can run at the same time and form one step. In hardware the delay is set by the number of steps, not by the number of comparisons.

Two properties make this a good fit for a trigger. The sequence of operations does not depend on the data, so the latency is the same for every input. And a network can be checked with the zero-one principle: if it sorts every sequence of zeros and ones, it sorts every sequence of numbers.

Knuth diagrams: a small sorting network with three stages and a compare-exchange block, next to larger sorting and merging networks shaded in blue and pink
Sorting networks are drawn as Knuth diagrams: horizontal lines are the values, vertical connectors are compare-exchange operations. A sorting network sorts any sequence; a merging network merges two sorted ones (PhD technical defence slides).

Batcher's constructions from the 1960s give a network for any number of inputs and are still the fastest practical general method.

SNpy

To work with networks of this size I wrote SNpy, a Python package that generates sorting and merging networks, optimises them, combines them, draws them as Knuth diagrams, and writes them out as VHDL and as C.

The optimisations remove compare-exchange elements that are not needed in a particular application: those connected only to unused inputs or outputs, those made redundant because part of the input is already sorted, and those that only put in order outputs that need not be in order. SNpy also extracts the number of steps and of comparators from a generated network, which allows candidates to be compared before any of them is implemented.

A first study with it compared Batcher's three constructions for every size from 2 to 512 inputs. Merge-exchange always gives the lowest delay and never needs more comparators than the other two.

Plots of delay and number of comparisons against number of inputs for Batcher odd-even merge, bitonic merge and merge-exchange networks, with input and output optimisations
The study of Batcher's constructions with SNpy. Within these methods, merge-exchange has the minimum delay without needing more comparators (PhD technical defence slides).

Divide and conquer

A 352-input Batcher network has 45 steps and, after removing what is not needed for 16 outputs, 4,446 comparators. Most of that work is wasted. Before its final merge, such a network has fully sorted two halves of 176, of which only the top 16 of each can matter.

So the input is split into R groups. Each group is sorted in parallel by a small network that outputs only its top 16. The groups are then merged two by two in a binary tree of merging networks, each taking two sorted lists of 16 and returning the top 16. Candidates that cannot be among the final 16 are dropped early.

The number of groups can be anything from 1 to 22. Beyond that a group would have fewer than 16 inputs. SNpy generated and optimised the networks for all 22 options and tabulated steps and comparators. Two effects pull in opposite directions: more groups means smaller and faster sorters, but the merging tree is most efficient when the number of groups is a power of two. The two best options were 16 groups of 22 and 22 groups of 16, both with 35 steps.

The table that SNpy produced for this search is on the slide below, with the two winners circled. The left column of the drawing shows the reasoning in pictures: a plain merge sort of 352 inputs ends with a merger of two lists of 176, while the divide-and-conquer version only ever merges lists of 16.

Three ways to split 352 inputs drawn as block diagrams, next to a table of steps and comparators for every number of groups from 1 to 22, with the rows for 16 and 22 groups circled
The divide-and-conquer options, all evaluated before any hardware was built (PhD technical defence slides).

For exactly those two sizes, networks faster than Batcher's are known: a 16-input network by Van Voorhis (1972) and a 22-input network by Sherenaz Al-Haj Baddar (2009), which takes 12 steps where merge-exchange takes 15. With the Baddar network, the option with 16 groups comes down to 32 steps: 12 for sorting and four levels of 5-step mergers. The merging part cannot be improved, because Batcher's odd-even merger is optimal for two lists of equal power-of-two length.

The complete 352-input network drawn as a Knuth diagram, and the tree of sorters S and mergers M that it implements
The final network: 22-input Baddar sorters followed by a tree of (16,16) mergers, 32 steps in total. The slide counts 2,496 compare-exchanges; the final count in the thesis, after the last optimisations, is 2,528 (PhD technical defence slides).

The result has 32 steps where the Batcher network has 45, and 2,528 comparators where it has 4,446. Prof. Al-Haj Baddar later sat on my thesis jury.

Checking the network

With the zero-one principle, the 22-input sorter was tested with all 222 binary inputs and the merger with every pair of sorted 16-element lists. That is sufficient. The complete network cannot be tested exhaustively, since it has 2352 binary inputs, so a random sample of 230 was run as well, without an error.

The same network, twice

SNpy produces the list of 2,528 compare-exchange pairs. From there the two implementations go separate ways.

Flow chart: the list of compare-exchange pairs feeds two branches. The RTL branch groups pairs into stages, generates pipelining configurations and VHDL. The HLS branch generates C++ and runs the vendor HLS flow. Both end in the vendor RTL flow and the FPGA
The two design flows. Yellow blocks are done by SNpy (PhD thesis, Fig. 8.1).

For RTL, the pairs are grouped into the 32 steps, and I wrote configurable VHDL in which a generic selects after which steps a pipeline register is placed. I had hoped to let the tools distribute the registers by retiming. With two different synthesis tools the registers never moved more than a few logic levels from where they started, so the pipelining is described explicitly.

For HLS, the C++ applies a compare-exchange function to a constant array holding the 2,528 pairs. Parallelism and pipelining are not written down. The tool infers them from the data dependencies and from a directive that sets the latency.

The logic runs at 160 MHz, four times the bunch-crossing rate. For each approach an automated flow built 64 variants, differing in latency, in whether the full candidate data or only the sort key travels through the network, and in a few tool options.

Both approaches meet timing with five clock cycles: 31.25 ns, about 15% of the budget. The best HLS variant has a worst negative slack of 540 ps against 370 ps for the best RTL one, uses 54,216 look-up tables against 63,593, and 23,144 flip-flops against 20,281, at the same estimated 6.3 W.

Comparison table of the best RTL and HLS implementations with timing slack, power, LUTs and flip-flops, and notes on the advantages of HLS
The comparison in one table: HLS with better timing slack and fewer LUTs, slightly more flip-flops, the same power (PhD technical defence slides).

The difference was in the effort. I estimate that the RTL design took at least ten times longer. The HLS test bench is ordinary software and can find functional errors before synthesis. RTL variants took up to a day to build where the HLS equivalent took under an hour, and some RTL variants had not finished after 30 days.

What I conclude, and what I do not

This comparison covers one design: wide, regular, feed-forward, with no control logic. For that kind of block, HLS gave slightly better results for much less work. I would not extend the numbers to other kinds of design without measuring again.

SNpy is open source on GitHub and PyPI. The complete network, with the table of pairs for each step, is in chapter 7 of the thesis (PDF).