Smaller and Faster: Parallel Processing of Compressed Graphs with Ligra+
Smaller and Faster: Parallel Processing of Compressed Graphs with Ligra+
复制标题
DOI：
10.1109/dcc.2015.8
复制
发表时间：
2015-04
期刊：
影响因子：
--
通讯作者：
Julian Shun;Laxman Dhulipala;G. Blelloch
中科院分区：
文献类型：
--
作者：
Julian Shun;Laxman Dhulipala;G. Blelloch
我们研究了并行内存图算法的压缩技术，并表明与在未压缩的图上运行算法相比，我们可以减少空间使用，同时获得具有竞争力或改进的性能。我们将压缩技术集成到最近的共享内存图形处理系统Ligra中。这个系统，我们称之为Ligra+，能够平均使用大约一半的未压缩图的空间来表示图。此外，在具有超线程的40核机器上，Ligra+的平均速度略快于Ligra。我们的实验研究表明，Ligra+能够使用更少的内存处理图形，同时性能与Ligra一样好或更快。
We study compression techniques for parallel in-memory graph algorithms, and show that we can achieve reduced space usage while obtaining competitive or improved performance compared to running the algorithms on uncompressed graphs. We integrate the compression techniques into Ligra, a recent shared-memory graph processing system. This system, which we call Ligra+, is able to represent graphs using about half of the space for the uncompressed graphs on average. Furthermore, Ligra+ is slightly faster than Ligra on average on a 40-core machine with hyper-threading. Our experimental study shows that Ligra+ is able to process graphs using less memory, while performing as well as or faster than Ligra.