> For the complete documentation index, see [llms.txt](https://sliu583.gitbook.io/blog/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://sliu583.gitbook.io/blog/specific-work/shivarams-group/group-papers/accelerating-graph-sampling-for-graph-machine-learning-using-gpus.md).

# Accelerating Graph Sampling for Graph Machine Learning using GPUs

#### Requirement for GPU performance 

* *thread*: fundamental unit of computation in a GPU 
* *thread block*: threads are statically grouped into thread blocks and assigned a unique id within a block 
* *streaming multiprocessors* (SMs): each of which executes one or more thread blocks 
* Types of memory 
  * *shared memory*: each SM's private memory, which is only available to the thread blocks assigned to that SM 
  * *global memory*: the GPU has global memory, which is accessible to all SMs 
  * Accessed latency of global memory >> shared memory
* To run a thread block, an SM schedules a subset of threads from the thread block, known as *warp* 
  * Warp typically consists of 32 threads with consecutive thread IDs 
  * GPU employs: Single Instruction Multiple Threads (SIMT) execution model 
    * All threads in a warp runs the same instruction in lock-step 
    * Consequence 
      * Two threads cannot execute two sides of the branch concurrently 
      * Warp divergence: when the threads in a warp encounter a branch, the subset of threads that do not take the branch must wait for other threads to complete the branch 
    * Goal: **minimize warp divergence**  
* Another goal: **balance resource usage across thread blocks** 
* the GPU can provide high-bandwidth access to global memory by coalescing several memory accesses from the same warp
  * only possible when concurrent memory accesses from threads in the same warp access consecutive memory segments. 

#### Presentation 

{% embed url="<https://www.youtube.com/watch?v=GsffY0j6tVE>" %}