This example is included to suggest that FPGAs may provide novel ways of solving well-known problems. Sorting is required in many computer applications, particularly commercial ones. Here we look at a high-speed sorter, but one confined to miniscule amounts of data. It is described as systolic because it uses a repetitive block structure, and has a regular data flow. In general, each item to be sorted consists of a number of fields, of which one is selected as a key, on which to sort. For simplicity we regard the key as a nonnegative integer, and assume that we wish to sort items in ascending order of their keys. For simplicity, we concentrate on sorting the keys.
Knuth [Knuth73] distinguishes some basic sorting methods:
Sort by insertion: Find the correct place to insert an item in an already-ordered list
Sort by exchange: Consider pairs of keys, and swap them if out of order
Sort by enumeration: Find the smallest (or largest) key and remove the item to a new list. Repeat until the original list is empty.
The scheme described here is a combination of the first two methods. We assume that the items to be sorted arrive individually, so it makes sense to keep previous arrivals in order—we choose ascending. Borrowing a technique from full-custom VLSI design, we make up blocks of cells, and arrange for simple connections ...