Boosting heapsort performance of processing Big Data streams
Usamah Algemili, Adi Alhudhaif · 2016
Real-time processing is one aspect of the Big Data situation, and it requires an unconventional approach to solve the recent problems that appear at both software and hardware levels. The continuous increase of data velocity has placed a tremendous pressure on the existing systems, and the current volumes of Big Data limit the efforts of storing everything at a pre-processing stage. Hence, on-the-fly processing is necessary more than before in order to support the collective efforts towards Big Data advancement. Many sorting algorithms have been intensively studied, and sorting on-the-fly is another problem that may need different hardware models. Heapsort is a sorting algorithm that requires less memory traffic. In ideal cases, heapsort may not be the best performing algorithm; however, streaming applications are designed to keep memory operation at its minimum which introduces heapsort as a suitable proposition. Hardware architecture plays an important role in improving the efficiency of streams processing. The variance of hardware performance on different HW architectures is quite interesting. Based on previous literature that studied frameworks such as CPUs, GPUs, and FPGAs on specific applications, we observed that GPUs outperformed the other platforms in terms of execution time. CPUs outperformed in overall execution combined with transfer time. FPGAs outperformed for fixed algorithms using streaming [1]. Accordingly, this paper investigates a reconfigurable pipeline architecture that is specially designed to improve the performance of real-time processing using an improved heapsort algorithm. It compares the performance of three different HW platforms followed by experimental result that confirms a noticeable improvement of heap sorting by pipelined reconfigurable FPGA design.