情報処理学会 第78回全国大会講演要旨
1H-04
Fast Merge Network for Sorting on FPGA
Sorting has wide applications in various areas, and thus a high performance sorting system provides many benefits.
In recent years, in addition to the conventional approach of using general purpose processors, leveraging GPUs or FPGAs to improve sorting performance is becoming a promising solution.
Casper and Olukotun have recently proposed a sorting accelerator on FPGA which is the fastest one known so far. In that study, a merge network which merges six data records per clock cycle and runs at 200MHz was proposed.
The aim of this work is to achieve higher performance than the prior study.
We propose a novel merge network architecture which replaces multistage connected 2-input multiplexers with a multi-input one to shorten critical paths.
We used the proposed architecture to implement a 4-input merge network. The evaluation results show that the implemented merge network achieves a high operating frequency of 273MHz.
In recent years, in addition to the conventional approach of using general purpose processors, leveraging GPUs or FPGAs to improve sorting performance is becoming a promising solution.
Casper and Olukotun have recently proposed a sorting accelerator on FPGA which is the fastest one known so far. In that study, a merge network which merges six data records per clock cycle and runs at 200MHz was proposed.
The aim of this work is to achieve higher performance than the prior study.
We propose a novel merge network architecture which replaces multistage connected 2-input multiplexers with a multi-input one to shorten critical paths.
We used the proposed architecture to implement a 4-input merge network. The evaluation results show that the implemented merge network achieves a high operating frequency of 273MHz.
