Subhajit Sahu wolfram77

Highlighted notes on:
Incremental Page Rank Computation on Evolving Graphs.
While doing research work with:
Prof. Dip Sankar Banerjee and Prof. Kishore Kothapalli:
https://dl.acm.org/doi/10.1145/1062745.1062885

This paper describes a simple method for computing dynamic pagerank, based on the fact that change of out-degree of a node does not affect its pagerank (first order markov property). The part of graph which is updated (edge additions / edge deletions / weight changes) is used to find the affected partition of graph using BFS. The unaffected partition is simply scaled, and pagerank computation is done only for the affected partition.

Highlighted notes on:
I/O-Efficient Techniques for Computing Pagerank.
While doing research work with:
Prof. Dip Sankar Banerjee and Prof. Kishore Kothapalli:
https://dl.acm.org/doi/10.1145/584792.584882

This paper describes a technique to partition the link file of the whole file into blocks of a range of destination nodes, with partial source nodes, so that it is possible to run power iteration of pagerank of massive graphs which do not fit in memory. The graphs must be stored on disk, and partitions of the graphs are scanned in every iteration until the ranks converge. Unlike Haveliwala's technique, this is similar to pull based pagerank. Both methods have similarities with join techniques in database systems. Topic-sensitive pagerank is also discussed which finds pagerank of graphs related to a specific keywords beforehand, and merges them together based upon the query (might return better results than global pagerank). This requires small adjustments to the random jump probability factor (1-d).

[![

Highlighted notes while research with Prof. Dip Sankar Banerjee, Prof. Kishore Kothapalli:
PageRank on an evolving graph - Yanzhao Yang.
https://theory.utdallas.edu/seminar/G2S13/YY/Pagerank%20on%20evolving%20graph-Yanzhao%20Yang.pdf

Pagerank may be always imprecise, due to lack of knowledge of up-to-date/complete graph. Millions of hyperlinks/social-links modified each day. Which portions of the web should a crawler focus most (probing strategy)? Probing techniques discussed are Random probing, Round-robin probing, Proportional probing (random, proportional to node's pagerank), Priority probing (deterministic, pick node with highest cumulative pagerank sum), Hybrid probing (proportional + round-robin).

This is my report on:
Adjusting CSR format for graph (v1).
While doing research work with Prof. Dip Banerjee, Prof. Kishore Kothapalli.

Compressed Sparse Row (CSR) is an adjacency-list based graph representation that is commonly used for efficient graph computations. However, given N vertices, M edges, and a 32-bit / 4-byte vertex-id, it occupies a space of 4(N + M) bytes. Note however that a 32-bit unsigned integer is limited to just 4 billion ids, and thus massive graphs would need to use a 64-bit / 8-byte vertex-id. This further raises the occupied space to 8(N +M) bytes. Since large memories are difficult to make and tend to be slower than smaller ones (?) it makes

Exploring Optimizations for Dynamic Graph Algorithms on the GPU

While doing research work with [Prof. Kishore Kothapalli], and [Prof. Dip Sankar Banerjee].

Abstract — The Königsberg bridge problem, which was posed and answered in the negative by Euler in 1736 represents the beginning of graph theory. Graph is a generic data structure and is a superset of lists, and trees. Binary search on sorted lists can be interpreted as a balanced binary tree search. Database tables can be thought of as indexed lists, and table joins represent relations between columns. This can be modeled as graphs instead. Assignment of registers to variables (by compiler), and assignment of available channels to a radio transmitter are also graph problems. Neural networks are graphs too. Interaction between messenger molecules in the body, interaction between people on social media, and spreading of infectious diseases, are also modeled as graphs. Finding the shortest path between two points, and sorting web pages in order of

Dead End handling strategies for PageRank algorithm

While doing research work with [Prof. Kishore Kothapalli], [Prof. Dip Sankar Banerjee].

Abstract — Presence of dead ends, which are vertices without any out-edges, in a graph under PageRank computation can cause importance to leak out. This is undesirable since this can cause ranks of all vertices to converge to zero, which is a valid, but useless solution. Four different dead end handling strategies for static, incremental, and dynamic PageRank are studied here. These include: teleport, loop, loop-all, and remove. Results indicate that the remove strategy performs best, on average. This however is suitable only if it is possible to keep track of the dead-end free version of the graph, as otherwise the cost of recursively removing dead ends from the graph is significant. The loop and loop-all strategies perform similarly. Additionally, loop-all is a fair strategy and may be a better choice for networks associated with people. Teleport strategy pe

Rank adjustment strategies for Incremental / Dynamic PageRank

While doing research work with [Prof. Kishore Kothapalli], and [Prof. Dip Sankar Banerjee].

Abstract — To avoid calculating ranks of vertices in a dynamic graph from scratch for every snapshot, the ones computed in the previous snapshot of the graph can be used, with adjustment. Four different rank adjustment strategies for dynamic PageRank are studied here. These include zero-fill, 1/N-fill, scaled zero-fill, and scaled 1/N-fill. Results indicate that both 1/N-fill and scaled 1/N-fill strategies require the least number of iterations, on average. As long as the graph has no affected dead ends (including dead ends in the previous snapshot), unaffected vertices can be skipped with the scaled 1/N-fill adjustment strategy. (🎞️ [slides])

Index terms — Temporal graph, Incremental / Dynamic PageRank, Rank adjustment, Initial ranks, Affected vertices, Scaled 1/N-fill strategy.

Highlighted notes on:
Introduction to Level Zero API for Heterogeneous Programming by Juan Fumero
While doing research work with Prof. Dip Sankar Banerjee, Prof. Kishore Kothapalli.

Level-Zero appears quite similar to CUDA, but is very verbose. AS Juan has said, it is quite similar to OpenCL and Vulkan. It has command queues to commands to device for compute or copy. Shared memory (unified memory in CUDA) is used. Synchronization is done with events and fences (need to read what fences are). You can take an OpenCL kernel, compile with clang to SPIRV (used by Vulkan too) and load it up and build to native, and submit in a command list. Similar to CUDA, synchronize is needed to wait for kernel to complete as execution is asynchronous (its just submit to queue).

Like OpenCL, Level-Zero assumes multiple drivers, and devices, queues. Some picking needed for these (atleast for queues=compute).

![](https://ga-beacon

Highlighted notes on:
NVIDIA Tesla V100 GPU Architecture Whitepaper
While doing research work with Prof. Dip Sankar Banerjee, Prof. Kishore Kothapalli.

Here is a my short summary of NVIDIA Tesla GV100 (Volta) architecture from the whitepaper:

84 SMs, each with 64 independent FP, INT cores.
Shared mem. size config. up to 96KB / SM.
4 512-bit mem. controllers (total 4096-bit).
Upto 6 Bidirectional NVLink, 25 GB/s per direction (w/ IBM Power 9 CPUs).
4 dies / HBM stack, 4 stacks. 16 GB w/ 900 GB/s HBM2 (Samsung).

 @echo off
 setlocal enableextensions
 setlocal enabledelayedexpansion
 set file=HKEY_CLASSES_ROOT\*\shell\VsCode
 set dirc=HKEY_CLASSES_ROOT\Directory\shell\VsCode
 set back=HKEY_CLASSES_ROOT\Directory\Background\shell\VsCode
 set default=Open: Code
 if not "%~1"=="" set default="%~1"