Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

FPGA graph processing acceleration method and system based on OpenCL

A technology of graph computing and basic instructions, applied in the field of big data processing, can solve the problems of system performance degradation, limited FPGA chip cache, waste of the advantages of high parallelism of FPGA, etc., to reduce memory access delay, reduce memory access times, The effect of improving system efficiency

Active Publication Date: 2020-02-28
HUAZHONG UNIV OF SCI & TECH
View PDF6 Cites 5 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

However, this method has great disadvantages: (1) The above-mentioned decision-making strategy is a static method, and it is impossible to judge the scattered nodes generated in the dynamic process.
Compared with the above-mentioned heterogeneous execution mode, the communication overhead is removed, but it also brings many problems: (1) For tasks that are not very intensive in calculation or memory access, the advantages of FPGA's high parallelism are wasted
(2) FPGA on-chip cache is limited, how to achieve high performance under the premise of limited resources, which is very unfriendly to development users
The use of this type of development language has high requirements for development users; although the use of HLS language, a C-like language, to develop FPGAs reduces the difficulty of development users, but because the HLS language itself is not capable of expressing pipelines, it cannot give full play to the advantages of FPGAs; The use of OpenCL to develop FPGA not only maintains the characteristics of low difficulty in HLS language development, but also makes good use of the advantages of FPGA pipeline because OpenCL uses fine-grained pipeline mode for compilation in the compilation process.
However, due to common problems in graph computing: the Power-Law characteristics of graphs, communication between graph nodes, random memory access, etc., will lead to system performance degradation

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • FPGA graph processing acceleration method and system based on OpenCL
  • FPGA graph processing acceleration method and system based on OpenCL

Examples

Experimental program
Comparison scheme
Effect test

Embodiment 1

[0100] The energy management system EMS mainly provides grid dispatchers with various real-time information of the grid, including: frequency, generator power, line power, bus voltage, etc., and conducts scheduling decision-making management of the grid to realize centralized monitoring and control of power production and transmission , to ensure the safe, high-quality and economical operation of the power grid. The power system needs to realize real-time / ultra-real-time EMS, and all calculations need to be completed within the sampling time, which generally includes two types: transient calculation and steady-state calculation. The core of steady-state calculation is power flow calculation. At present, power system applications are mainly implemented on the CPU, but power flow calculations have very fine-grained parallelism, which is not supported by general-purpose CPUs and cannot meet real-time requirements.

[0101] An annotated power flow distribution graph is a directed ...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention discloses an FPGA graph processing acceleration method and system based on OpenCL, and belongs to the field of big data processing. The method comprises the following steps: generating acomplete control data flow diagram CDFG according to an intermediate code IR obtained by disassembling; partitioning the complete CDFG graph again according to Load and Store instructions to obtain new CDFG instruction blocks, and determining a parallel mode between the CDFG instruction blocks; analyzing Load and Store instructions in all the new CDFG instruction blocks, and determining a division mode of the BRAM on the FPGA chip; and reorganizing an on-chip memory of the FPGA by adopting a BRAM division mode, translating all new CDFG instruction blocks into corresponding hardware description languages according to a parallel mode among the instruction blocks, compiling and generating a binary file capable of running on the FPGA, and burning the binary file to the FPGA for running. By adopting a pipeline technology and readjusting the instruction in the instruction block, the memory access frequency is reduced, and the memory access delay is reduced; on-chip storage partitioning is adopted, writing conflicts of different assembly lines on the same memory block are reduced, and therefore the system efficiency is improved.

Description

technical field [0001] The invention belongs to the technical field of big data processing, and more particularly relates to an OpenCL-based FPGA graph processing acceleration method and system. Background technique [0002] Graph is a classic data structure, which has the field of graph theory in theory, and in real life, many relationships can be abstracted into graphs. For example, power data analysis, social network, transaction network, transportation network and so on. People obtain the desired information by analyzing the characteristics of the network. For example, to obtain which characters are "Internet celebrities" in the design network, to obtain the optimal route between two places in the transportation network, and so on. Graph computing is to abstract the above-mentioned common practical problems into several classic problems, such as the SSSP algorithm to obtain the shortest distance between two points, and the PageRank algorithm to obtain the importance of...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Applications(China)
IPC IPC(8): G06T1/20G06F15/78G06F9/30G06F9/38
CPCG06F9/30047G06F9/3814G06F15/781G06F15/7871G06T1/20
Inventor 廖小飞赵杰山郑龙金海王庆刚
Owner HUAZHONG UNIV OF SCI & TECH
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products