On hiding latency in reconfigurable systems: the case of merge-sort for an FPGA-based system

Recursive solutions are effective software techniques that are difficult to map into hardware due to their dependency on input size and data values. As a result, most high-level design tools do not allow for recursive calls. In this paper we present a technique for mapping the merge-sort algorithm, as a case study, into a reconfigurable system. Our mapping employs an on-line prediction method to reconfigure the necessary hardware only when the need arises, and to hide the reconfiguration delay. As a result, our implementation uses the smallest possible size hardware to sort an input data stream without prior knowledge of its length and eliminates the reconfiguration delay penalty. We outline a reconfigurable system with self-organizing multiple-buses as the communication subsystem. The processing elements and memory modules are connected to the multiple-buses as a linear array. We also demonstrate the effectiveness of adding simple LUTs to the multiple-buses in improving the throughput by allowing for pipelining at the word level.