Efficient FPGA-based graph processing with hybrid pull-push computational model

来源 :计算机科学前沿 | 被引量 : 0次 | 上传用户:zsh188667787
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
Hybrid pull-push computational model can provide compelling results over either of single one for processing real-world graphs.Programmability and pipeline parallelism of FPGAs make it potential to process different stages of graph iterations.Nevertheless,considering the limited onchip resources and streamline pipeline computation,the efficiency of hybrid model on FPGAs often suffers due to wellknown random access feature of graph processing.In this paper,we present a hybrid graph processing system on FPGAs,which can achieve the best of both worlds.Our approach on FPGAs is unique and novel as follow.First,we propose to use edge block (consisting of edges with the same destination vertex set),which allows to sequentially access edges at block granularity for locality while still preserving the precision.Due to the independence of blocks in the sense that all edges in an inactive block are associated with inactive vertices,this also enables to skip invalid blocks for reducing redundant computation.Second,we consider a large number of vertices and their associated edge-blocks to maintain a predictable execution history.We also present to switch models in advance with few stalls using their state statistics.Our evaluation on a wide variety of graph algorithms for many realworld graphs shows that our approach achieves up to 3.69× speedup over state-of-the-art FPGA-based graph processing systems.
其他文献
目前,我国已有260多个地级市。这些地市级政府是我国政府层级中的重要组成部分之一,数量巨大、影响也大,而且受地域、经济、文化、社会等因素的影响,具体情况也是千差万别。这些
河北省成人高等教育研究会成立大会暨河北省成人高等教育工作会议于2003年11月23日24日在河北大学召开.河北省委教育工委副书记杨建广、河北省高教学会会长原河北省教委副主
各省、自治区、直辖市人民政府,国务院各部委、各直属机构:rn城镇老旧小区改造是重大民生工程和发展工程,对满足人民群众美好生活需要、推动惠民生扩内需、推进城市更新和开
期刊
本文针对中国岩彩画创作的当代性及发展走向进行了研究.采用文献研究等方法首先分析了中国当代岩彩画创作的观念性、抒情性、平面性和装饰性的特性,并具体研究了如何通过创新
改革开放以来,我国大部分城市经济迅速发展,规模不断扩大,城市建设向郊区蔓延,进入令人眩目的快速城市化时期。“城中村”是我国特有的土地所有制和文化背景下,在快速推进城市化进
近年来,施工现场工作的安全性已经得以提升,但由于影响因素复杂多变,施工现场在安全管理方面仍然存在一些漏洞,并威胁到工人的生命安全、家庭“支柱”和建筑企业的利益.因此,
Principal component analysis (PCA) is a widely used method for multivariate data analysis that projects the original high-dimensional data onto a low-dimensiona
党史工作会议是个非常重要的会议。党的十五大召开以后,胡锦涛等中央领导同志已从全党工作大局对党史工作作了重要指示,中央党史研究室又对新时期党史工作作了新的部署,我们一定
本文引入实证分析、定量和定性等分析方法,并综合运用安全文化、水上交通事故“人为因素”、水上交通事故统计分析等相关理论,对长江海事安全文化建设开展研究,尝试建立了一个具