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.
其他文献
各省、自治区、直辖市人民政府,国务院各部委、各直属机构: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