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 ...

Start Free Trial

No credit card required