Field-Programmable Gate Arrays: Reconfigurable Logic for Rapid Prototyping and Implementation of Digital Systems

5.5   SYSTOLIC SORTER*

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.

Figure 5–24. Schematic for state machine.

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