#11 New strategies

[Vinz]

Hi,

I'd like to implement a new strategy to improve the performance of the Gather and Scatter phases.

Anybody have any suggestions about this?

I know that there are good strategies implemented already (CTA-based, Scan-based and Warp-based) but I can't locate them in source code.
Does anyone know in which file are implemented?

Thank you in advance for your answers.

[Bryan Thompson]

The different strategies are invoked from GASEngine/enactor_vertex_centric.cuh. There are a variety of kernels in the GASEngine/vertex_centric directory, e.g., "contract_atomic", "expand_atomic", "gather", the "mgpukernel", etc.

For a given kernel, the logic is divided up between the kernel.cuh file and the cta.cuh file.

I will ask Zhisong to comment in some more depth on how these are structured.

Thanks,
Bryan

[Bryan Thompson]

The CTA-based, Scan-based, and warp-based policies are based on the b40c package as bundled (and modified) with MapGraph. THe best reference for that is Merrill's paper on Scalable and Efficient Graph Traversal

• http://dl.acm.org/citation.cfm?id=2145832
• https://research.nvidia.com/publication/high-performance-and-scalable-gpu-graph-traversal (tech report version)
• https://research.nvidia.com/publication/scalable-gpu-graph-traversal

The b40c library explored work efficient approaches to fast breadth first search on a GPU, and included a multi-GPU version for a single node based on UVA (Unified Virtual Addressing).

MapGraph significantly extends this work to support a generalized vertex-centric abstraction for high performance parallel graph algorithms on both a single GPU and large GPU clusters. The multi-GPU (cluster) work is currently just BFS, but we will be extending it to generalized graph algorithms shortly.

Thanks,
Bryan

[Vinz]

Thank a lot, Bryan.
I found lots of interesting information on that reference.

If Zhisong commented in some more depth on how these are structured, I would be grateful.

Thanks,
Vinz