The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
A classificação de dados é uma operação importante na ciência da computação. É amplamente utilizado em diversas aplicações, como banco de dados e pesquisa. Embora haja demanda por aceleradores de classificação de alto desempenho, é muito importante prestar atenção aos recursos de hardware para esse tipo de classificadores de alto desempenho. Neste artigo, propomos três arquiteturas baseadas em FPGA para acelerar a operação de classificação baseada no algoritmo de classificação por mesclagem. Chamamos nossas propostas de WMS: Wide Merge Sorter, EHMS: Efficient Hardware Merge Sorter e EHMSP: Efficient Hardware Merge Sorter Plus. Nosso alvo é o dispositivo Virtex UltraScale FPGA. Os resultados da avaliação mostram que nossos mescladores propostos mantêm propriedades de alto desempenho e econômicas. Embora utilizem muito menos recursos de hardware, nossos mescladores propostos alcançam desempenho superior em comparação com o estado da arte. Por exemplo, com 256 registros classificados produzidos por ciclo, os resultados da implementação do EHMS proposto mostram uma redução significativa no número necessário de Flip Flops (FFs) e Look-Up Tables (LUTs) para cerca de 66% e 79%, respectivamente, ao longo do período. classificador de mesclagem de última geração. Além disso, embora exija menos recursos de hardware, o EHMS atinge um rendimento cerca de 1.4x maior do que o classificador de mesclagem de última geração. Para o mesmo número de registros produzidos, o WMS proposto também alcança uma melhoria de rendimento de cerca de 1.6x em relação ao estado da arte, ao mesmo tempo que requer cerca de 81% de FFs e 76% de LUTs necessários para o classificador de última geração.
Elsayed A. ELSAYED
Tokyo Institute of Technology,Aswan University
Kenji KISE
Tokyo Institute of Technology
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copiar
Elsayed A. ELSAYED, Kenji KISE, "High-Performance and Hardware-Efficient Odd-Even Based Merge Sorter" in IEICE TRANSACTIONS on Information,
vol. E103-D, no. 12, pp. 2504-2517, December 2020, doi: 10.1587/transinf.2020PAP0017.
Abstract: Data sorting is an important operation in computer science. It is extensively used in several applications such as database and searching. While high-performance sorting accelerators are in demand, it is very important to pay attention to the hardware resources for such kind of high-performance sorters. In this paper, we propose three FPGA based architectures to accelerate sorting operation based on the merge sorting algorithm. We call our proposals as WMS: Wide Merge Sorter, EHMS: Efficient Hardware Merge Sorter, and EHMSP: Efficient Hardware Merge Sorter Plus. We target the Virtex UltraScale FPGA device. Evaluation results show that our proposed merge sorters maintain both the high-performance and cost-effective properties. While using much fewer hardware resources, our proposed merge sorters achieve higher performance compared to the state-of-the-art. For instance, with 256 sorted records are produced per cycle, implementation results of proposed EHMS show a significant reduction in the required number of Flip Flops (FFs) and Look-Up Tables (LUTs) to about 66% and 79%, respectively over the state-of-the-art merge sorter. Moreover, while requiring fewer hardware resources, EHMS achieves about 1.4x higher throughput than the state-of-the-art merge sorter. For the same number of produced records, proposed WMS also achieves about 1.6x throughput improvement over the state-of-the-art while requiring about 81% of FFs and 76% of LUTs needed by the state-of-the-art sorter.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2020PAP0017/_p
Copiar
@ARTICLE{e103-d_12_2504,
author={Elsayed A. ELSAYED, Kenji KISE, },
journal={IEICE TRANSACTIONS on Information},
title={High-Performance and Hardware-Efficient Odd-Even Based Merge Sorter},
year={2020},
volume={E103-D},
number={12},
pages={2504-2517},
abstract={Data sorting is an important operation in computer science. It is extensively used in several applications such as database and searching. While high-performance sorting accelerators are in demand, it is very important to pay attention to the hardware resources for such kind of high-performance sorters. In this paper, we propose three FPGA based architectures to accelerate sorting operation based on the merge sorting algorithm. We call our proposals as WMS: Wide Merge Sorter, EHMS: Efficient Hardware Merge Sorter, and EHMSP: Efficient Hardware Merge Sorter Plus. We target the Virtex UltraScale FPGA device. Evaluation results show that our proposed merge sorters maintain both the high-performance and cost-effective properties. While using much fewer hardware resources, our proposed merge sorters achieve higher performance compared to the state-of-the-art. For instance, with 256 sorted records are produced per cycle, implementation results of proposed EHMS show a significant reduction in the required number of Flip Flops (FFs) and Look-Up Tables (LUTs) to about 66% and 79%, respectively over the state-of-the-art merge sorter. Moreover, while requiring fewer hardware resources, EHMS achieves about 1.4x higher throughput than the state-of-the-art merge sorter. For the same number of produced records, proposed WMS also achieves about 1.6x throughput improvement over the state-of-the-art while requiring about 81% of FFs and 76% of LUTs needed by the state-of-the-art sorter.},
keywords={},
doi={10.1587/transinf.2020PAP0017},
ISSN={1745-1361},
month={December},}
Copiar
TY - JOUR
TI - High-Performance and Hardware-Efficient Odd-Even Based Merge Sorter
T2 - IEICE TRANSACTIONS on Information
SP - 2504
EP - 2517
AU - Elsayed A. ELSAYED
AU - Kenji KISE
PY - 2020
DO - 10.1587/transinf.2020PAP0017
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E103-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2020
AB - Data sorting is an important operation in computer science. It is extensively used in several applications such as database and searching. While high-performance sorting accelerators are in demand, it is very important to pay attention to the hardware resources for such kind of high-performance sorters. In this paper, we propose three FPGA based architectures to accelerate sorting operation based on the merge sorting algorithm. We call our proposals as WMS: Wide Merge Sorter, EHMS: Efficient Hardware Merge Sorter, and EHMSP: Efficient Hardware Merge Sorter Plus. We target the Virtex UltraScale FPGA device. Evaluation results show that our proposed merge sorters maintain both the high-performance and cost-effective properties. While using much fewer hardware resources, our proposed merge sorters achieve higher performance compared to the state-of-the-art. For instance, with 256 sorted records are produced per cycle, implementation results of proposed EHMS show a significant reduction in the required number of Flip Flops (FFs) and Look-Up Tables (LUTs) to about 66% and 79%, respectively over the state-of-the-art merge sorter. Moreover, while requiring fewer hardware resources, EHMS achieves about 1.4x higher throughput than the state-of-the-art merge sorter. For the same number of produced records, proposed WMS also achieves about 1.6x throughput improvement over the state-of-the-art while requiring about 81% of FFs and 76% of LUTs needed by the state-of-the-art sorter.
ER -