高级检索

    基于FPGA的排序加速方法综述

    Survey of Sort Acceleration Methods on FPGA

    • 摘要: 对于FPGA排序加速来说,各类性能指标的选取与优化至关重要,如延时、吞吐率、功耗、硬件利用率和带宽利用率等. 梳理了性能驱动下的排序加速发展脉络,在数据规模、数据类型、算法支持、软硬件协同和新型硬件等方面均取得了进展;分析了在设计、实现、测试等各不同阶段所面临的问题及优化策略,其中归并排序因其自身优良的硬件并行性、可扩展性和控制逻辑简单等特性成为主流. 排序加速是与特定应用场景深度绑定的架构设计,进一步从数据库系统加速角度出发,针对数据库排序所面临的资源竞争、数据组织方式、特有操作以及用户请求多样性等问题,分析了其所进行的架构调整. 最后针对现有研究的问题及缺陷,从分布式排序加速、数据处理器、高层次综合辅助工具链等方面对未来的发展方向进行了展望.

       

      Abstract: For sort acceleration on FPGA, the selection and optimization of various performance metrics, such as latency, throughput, power efficiency, hardware utilization and bandwidth efficiency, etc., are of critical importance. We compare the evolution of performance-driven sort acceleration, with advances in larger data size, more data types, more algorithm support, hardware-software cooperation and new hardware-based design; we analyze the problems and optimization strategies faced at different stages of design, implementation, testing and so on. Among the numerous sorting algorithms, merge sort becomes mainstream due to its excellent hardware parallelism, scalability and simple control logic. Sort acceleration is an architectural design that is deeply tied to specific application scenarios. We analyze the architectural adjustments made from the perspective of database system acceleration for resource competition, data arrangement, unique operations and diversity of user requests problems faced in databases. At last, to address the problems and shortcomings of existing studies, we provide an outlook on future directions in terms of distributed sort acceleration for very large data scale, the introduction of new hardware devices such as data processing unit, and the improvement of auxiliary tool chains such as high level synthesis to drive the iterative update of sort acceleration design.

       

    /

    返回文章
    返回