DISTRIBUTED COMPUTING

PROJECT

BSSE-601

SUBMITTED TO: Sir Saeed

SUBMITTED BY:
Saim Wafa (B17158046)
Maheen Tariq(B20103030)
Hamna Faheem Siddiqui(B20103028)
IMPLEMENTATION OF GRAPH ALGORITHM

We have chosen the Breadth-First Search (BFS) algorithm for graph traversal. BFS is
a fundamental graph algorithm used for various applications such as finding the
shortest path in unweighted graphs, connected components, and more.

TASK #1: SEQUENTIAL IMPLEMENTATION

Implemented the algorithm via python

CODE:

from collections import deque

def bfs_sequential(graph, start):

visited = set()
queue = deque([start])
bfs_order = []

while queue:
vertex = [Link]()
if vertex not in visited:
[Link](vertex)
bfs_order.append(vertex)
[Link](neighbor for neighbor in graph[vertex] if
neighbor not in visited)

return bfs_order
# Example usage
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}

print(bfs_sequential(graph, 'A'))

OUTPUT:
TASK #2: PRAM MODEL

+--------------------------------------+
| Initialization |

| |
| Queue = [start] |
| Visited = [False, False, ..., False] |
| Visited[start] = True |
| Next Queue = [] |
| Next Queue Size = 0 |
+--------------------------------------+

+----------------+ +----------------+
| | | |
+-----v-----+ +-----v-----+ +-v------v-+ +--v------v-+
| Processor | | Processor | | Processor | | Processor |
| 1 | | 2 | | 3 | | P |
+-----------+ +-----------+ +-----------+ +-----------+

+-----------------+ +----------------+
| Process Node 1 | | Process Node 2 |
| Check Neighbors | | Check Neighbors |
+--------^--------+ +--------^--------+
| (Repeat for other processors)
| +-----------------+
| | Add unvisited |
| | neighbors to |
| | Next Queue |
+--------------------> Mark as Visited |
+--------+--------+
|
|
+------+------+
| Synchronize |
+------+------+
|
v
 +------^------+
| Update Queues|
| Copy Next |
| Queue to |
| Queue |
| Reset Next |
| Queue and |
| Size |
+--------------+

TASK #3:IMPLEMENTATION ON GPU CUDA PYTHON

FOR A BETTER UNDERSTANDING

Cell#1: Install the Necessary Library

!pip install numba

Cell#2: Import Libraries and Define the CUDA Kernel

import numpy as np
from numba import cuda, int32

@[Link]
def bfs_kernel(graph, indices, queue, visited, next_queue, next_queue_size,
nodes_per_level, level):
tid = [Link].x + [Link].x * [Link].x
if tid < nodes_per_level[level]:
node = queue[tid]
start = indices[node]
end = indices[node + 1]
for i in range(start, end):
neighbor = graph[i]
if not visited[neighbor]:
visited[neighbor] = True
pos = [Link](next_queue_size, 0, 1)
next_queue[pos] = neighbor

Cell#3: Define the BFS Function and Graph Conversion

Function

def bfs_gpu(graph, indices, start):

n = len(indices) - 1
visited = [Link](n, dtype=np.int32)
queue = [Link](n, dtype=np.int32)
next_queue = [Link](n, dtype=np.int32)
next_queue_size = [Link]([0], dtype=np.int32)
nodes_per_level = [Link](n, dtype=np.int32)

queue[0] = start
visited[start] = 1
nodes_per_level[0] = 1
level = 0
 while nodes_per_level[level] > 0:
threads_per_block = 128
blocks_per_grid = (nodes_per_level[level] + (threads_per_block - 1)) //
threads_per_block
bfs_kernel[blocks_per_grid, threads_per_block](graph, indices, queue, visited,
next_queue, next_queue_size, nodes_per_level, level)

queue[:next_queue_size[0]] = next_queue[:next_queue_size[0]]
nodes_per_level[level + 1] = next_queue_size[0]
next_queue_size[0] = 0
level += 1

return visited

def convert_graph_to_cuda_format(graph):
adjacency_list = []
indices = [0]
for neighbors in graph:
adjacency_list.extend(neighbors)
[Link](len(adjacency_list))
return [Link](adjacency_list, dtype=np.int32), [Link](indices,
dtype=np.int32)

Cell#4: Define the Graph and Run the BFS Function

# Example graph
graph = [
[1, 2], # Node 0 (A)
[0, 3, 4], # Node 1 (B)
[0, 5], # Node 2 (C)
[1], # Node 3 (D)
[1, 5], # Node 4 (E)
[2, 4] # Node 5 (F)
]

# Convert the graph to a format suitable for CUDA

adjacency_list, indices = convert_graph_to_cuda_format(graph)

# Run the BFS function

visited = bfs_gpu(adjacency_list, indices, 0)
print(visited)

TASK#4: PERFORMANCE ANALYSIS

Execution Time
 Sequential BFS:
 Execution Time: The execution time for sequential BFS grows linearly
with the number of nodes and edges in the graph. For large graphs,
this can result in significant computational time as each node and edge
is processed one at a time.
 CPU Bound: Performance is limited by the speed of a single CPU core.
Improvements can only be achieved through better CPU hardware or
algorithmic optimizations.

 GPU BFS:
 Execution Time: GPU BFS can significantly reduce execution time by
processing multiple nodes and edges in parallel. The degree of
improvement depends on the graph's structure and the efficiency of
the parallel implementation.
 Parallelism: Utilizes thousands of GPU cores, allowing for concurrent
processing of many nodes and edges, leading to a substantial
reduction in traversal time for large graphs.
2. Speedup
 Sequential BFS:
 Speedup: No inherent speedup from parallelism. Performance
improvements are mainly dependent on CPU hardware upgrades or
optimized algorithms.

 GPU BFS:
 Speedup: The GPU implementation can achieve considerable speedup
over the sequential version. Speedup factors of 10x to 100x or more
are common, especially for large and dense graphs where parallel
processing can be fully leveraged.

3. Scalability
 Sequential BFS:
 Scalability: Limited scalability. The performance does not improve
significantly with additional CPU cores as the algorithm is inherently
sequential.
 Large Graphs: Performance degrades noticeably as the size of the
graph increases.

 GPU BFS:
 Scalability: Highly scalable. Performance can improve linearly or even
super-linearly with the number of GPU cores.
 Large Graphs: Better suited for large graphs as the parallel nature of
the algorithm allows efficient handling of many nodes and edges
simultaneously.

4. Memory Utilization
 Sequential BFS:
 Memory Utilization: Uses main memory (RAM) efficiently with
predictable access patterns. Memory bandwidth is typically not a
bottleneck.
 Cache Usage: Good cache locality due to sequential access of
memory.

 GPU BFS:
  Memory Utilization: Requires efficient use of GPU global memory.
Memory access patterns need to be optimized for coalesced access to
prevent memory bottlenecks.
 Memory Bandwidth: Higher memory bandwidth of GPUs can be fully
utilized, but requires careful management to avoid conflicts and ensure
high throughput.

5. Synchronization and Overheads

 Sequential BFS:
 Synchronization: No synchronization overhead as there is only a
single thread.
 Overheads: Minimal overhead, limited to the basic operations of the
BFS algorithm.

 GPU BFS:
 Synchronization: Requires synchronization mechanisms (e.g., atomic
operations) to manage concurrent access to shared data structures,
which can introduce overhead.
 Kernel Launch Overheads: The overhead of launching kernels and
managing multiple threads needs to be considered, but these are
generally outweighed by the performance gains from parallelism.

6. Energy Efficiency
 Sequential BFS:
 Energy Efficiency: Consumes less power overall but takes longer to
complete, leading to longer usage of system resources.
 CPU Efficiency: Typically efficient in terms of power per computation,
but not in terms of overall execution time for large graphs.

 GPU BFS:
 Energy Efficiency: Consumes more power due to the large number of
active cores, but completes the task much faster.
 GPU Efficiency: High energy consumption per unit time but reduced
overall energy usage due to significantly shorter execution time.

Conclusion
Sequential BFS:
  Performance: Suitable for small to moderately sized graphs. Limited by the
single-threaded nature of the algorithm.
 Scalability: Poor scalability for large graphs. Performance degrades as the
size of the graph increases.
 Use Case: Suitable for environments where parallel resources are not
available or where the simplicity of implementation is a priority.

GPU BFS:

 Performance: Offers substantial performance improvements for large and

complex graphs due to parallel processing capabilities.
 Scalability: Excellent scalability. Performance improves with the addition of
more GPU cores and can handle large graphs efficiently.
 Use Case: Ideal for large-scale graph traversal problems where GPUs are
available and high performance is required.

In summary, while the sequential BFS is simpler and sufficient for small
graphs, the GPU implementation excels in performance, especially for large
and dense graphs, thanks to its ability to leverage massive parallelism.
However, this comes with increased complexity in implementation and the
need to manage parallel execution effectively.