Hardware-software Co-design and Implementation for Large Scale Hash Tables
CSTR:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    Hash tables play an important role in network message processing, especially in the processing of messages with states. With the rapid growth of network traffic, the hash tables of traditional software can hardly meet the needs of network performance, and search is one of the key factors affecting the performance of hash tables. In addition, the improvement in the search rate of hash tables has always been a difficult problem. The research reveals that the existing network traffic presents the characteristics of Pareto distribution, namely that there is a small number of massive traffic data—elephant flow. On the basis of the computing mode of software-hardware co-design used in the current data center, a large-scale hash table architecture with software-hardware co-design is proposed on the basis of DPDK+FPGA. According to the characteristics of existing network traffic, this method divides the traffic into elephant flow and background flow, and meanwhile, the hash table is divided into a hardware table and a software table. A small-scale hardware table is constructed in FPGA to unload the hash calculation of all messages and the hash search of elephant flow. In the software, a large-scale software table is constructed on the basis of DPDK, and the hash calculation is unloaded by FPGA to speed up the search of background flow. As the software has all the flow information, the sampling method is used to identify the elephant flow and update the key-value pair of the elephant flow to the hardware table of FPGA, so as to accelerate the search rate of the large-scale software table in the software. The Xilinx U200 accelerator card and general server are employed as the hardware platform to realize the large-scale hash table with software-hardware co-design, and the traffic data in line with the current network characteristics is constructed by the tester. The accurate forwarding of DPDK is used as an example to verify the performance of the hash table with hardware-software co-design. The results reveal that when the hash search of elephant flow is completely unloaded, its performance is 64%–75% higher than the original accurate forwarding of DPDK; when the elephant flow is not unloaded, its performance is improved by 5%–48%.

    Reference
    Related
    Cited by
Get Citation

杨文韬,张士军,张进,唐寅,于洪涛.大规模软硬协同哈希表设计与实现.计算机系统应用,2023,32(1):61-74

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:February 21,2022
  • Revised:March 23,2022
  • Adopted:
  • Online: October 28,2022
  • Published:
Article QR Code
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-3
Address:4# South Fourth Street, Zhongguancun,Haidian, Beijing,Postal Code:100190
Phone:010-62661041 Fax: Email:csa (a) iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063