Graph algorithms can be implemented as a sequence of basiclinear algebraic operations (BLAS) on a sparse adjacency matrix.Analytics, e.g. centralities, are computed fast through stochasticapproaches employing a few SPMM operations. Edgetraversals is an important operation for knowledge discovery,which can be implemented as a sequence of (SPMV) operations.Both, SPMV and SPMM, are notorious for being memorybound, cache demanding operations, and difficult to parallelize;(SPMM) suffering the least in terms of operations per byte. When the graph structure is fully known at runtime we canaddress in an off-line manner, memory overhead, and cachemiss ratio by respectively using a smaller type for indexes,and a cache friendly sorting to reduce cache misses on thedense input vector. Parallelism is achieved by blocking thematrix. This work is the core of our HPC Knowledge Graph(HPC-KG) employed in production settings; among first suchimplementations.
By: Leonidas Georgopoulos, Aleksandros Sobczyk, Dimitrios Christofidellis, Michele Dolfi, Christoph Auer, Peter W J Staar, Costas Bekas
Published in: RZ3953 in 2019
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .