Research And Implementation Of Parallel Computer Architecture For Graph Search

With the innovation and popularisation of new generation information technologies such as cloud computing,mobile internet and internet of things,human beings have entered ‘the era of big data',and China has announced and implemented the national strategy for big data recently.Graph search,a typical challenge of big data applications,has been an international standard test for rating the computing capability for big data processing,i.e.Graph 500.Big data applications are distinct to traditional intensive-computing applications,and research on the architecture of parallel computing system for big data applications is still at an early stage.Supported by the High-efficiency Parallel Computer System Architecture and Technology for Big Data project(the Key Programme of National Natural Science Fund)and the Key Techniques of Parallel Computer Systems for Big Data Processing project funded by State Key Laboratory of High Performance Computing,this thesis studies the architecture design of the parallel computing system for big data processing,particularly for the graph search application.It investigates several research tasks including the parallel computing model,macro-architecture,micro-architecture and parallel computing prototype system.The main contributions include:1.A quantitative performance model of parallel computing for graph search application(Chapter 2)Graph search application has multiple features such as data-driven,global synchronisation and random access.Thus,exploiting both theoretical analysis and experimental verification,this thesis proposes a comprehensive quantitative performance model for computing,storage and communication,considering factors such as data size,parallelism,memory access and communication delay.The research can guide the design of parallel computing system for graph search application and other big data applications.2.A scalable heterogeneous parallel computing architecture for graph search application(Chapter 3)The thesis designs a scalable heterogeneous parallel computing architecture for graph search application,which is based on general CPU combined with FPGA stream acceleration processor.It utilises a master-slave model in each node where a host computer connects with the stream processor through the PCIE bus;it implements the communication between nodes through Ethernet,while the streaming processors are connected through a high-speed InfiniBand network.It also designs techniques such as the hardware-support global addressable distributed shared accelerators,the architecture memory access and global thread synchronisation,which can effectively solve the issues of random access and global synchronisation in graph search application.3.Architecture design of a vector cross-threading multi-thread stream processor for graph search application(Chapter 4)The thesis designs a vector cross-threading multi-thread stream processor architecture for graph search application and proposes a stream processing execution mechanism and its instruction set.It builds a three-layer LRF-SRF-MEM storage framework that can explicitly control the data flow and capture the spatio-temporal locality of the data.It also designs the vector cross-threading multi-thread stream processor with a 5-stage pipeline,which can effectively increase the parallel efficiency of microprocessors for the big-data graph search application.4.A stream processing chip and heterogeneous parallel computing prototype system for graph search application(Chapter 5)Using Verilog language,the thesis designs and implements the 200 MHz stream processing prototype system on a Xilinx VC709 FPGA,which includes a Virtex-7 XC7VX690T-2FFG1761 CFPGA chip,two 4GB SODIMM memory and an 8-channel PCI-E interface.A combination of the FPGA board and a host computer with general microprocessor chip produces a heterogeneous node,and the heterogeneous parallel computing prototype system is constructed with eight nodes.The experimental results demonstrate and verify the proposed macro and micro-architecture and related techniques.