Parallelizing Depth-First Search for Pathway Finding: A Comprehensive Investigation

In recent years, search algorithms and their parallelization have been subjects of significant research interest in computer science. We review several relevant studies that have explored parallelization techniques for tree traversal and path finding, as well as investigations into load balancing and performance evaluation of parallel algorithms.

Sequential Algorithms for Tree Traversal:

Traditional sequential algorithms, such as Depth-First Search (DFS) and Breadth-First Search (BFS), have long been employed for tree traversal and path finding. Lai et al. [5] proposed an optimized recursive DFS algorithm with memory-efficient data structures for path finding in trees. Despite their widespread use, these sequential algorithms face limitations when dealing with large-scale datasets, motivating the need for parallel approaches.

Parallel Search Algorithms:

In the domain of parallel algorithms, there have been notable efforts to address tree traversal and related problems. Wodziński and Krzyżanowska [6] introduced a parallel BFS algorithm that utilizes a multi-threaded approach to achieve faster exploration of tree structures. Additionally, Uenoet al. [7] presented a parallel DFS variant employing task parallelism and synchronization techniques for graph traversal, demonstrating improved scalability on multi-core architectures.

Parallelization Techniques:

Researchers have explored various parallelization techniques that are relevant to our problem domain. Acar al. [8] discussed the challenges of load balancing in parallel graph search algorithms and introduced a work-stealing strategy for distributing tasks efficiently among processing units. Thwe and Kyi [9] proposed a hybrid parallelization method combining task-level parallelism and data-level parallelism to enhance the performance of search operations in complex data structures.

Performance Evaluation in Parallel Algorithms:

In evaluating the efficiency and scalability of parallel algorithms. Grama and Kumar [10] conducted a comprehensive study comparing parallel BFS, DFS, and A*search on multi-core processors. Their findings indicated that parallelization significantly improved the search throughput on various tree structures. However, load imbalance and communication overhead were identified as potential bottlenecks in certain cases.

Also Weiss [11] proposes the Amdhals effects in comparing the performance of parallel algorithm with the best sequential algorithm.

Applications of Parallel Algorithms in Tree Structures:

While parallel algorithms have been explored in various search domains, their specific application to tree structures has garnered interest. Riansantiet al. [12] proposed a parallel algorithm for finding all paths in a tree, using a combination of task-level and data-level parallelism. Their approach showed promising results on large-scale trees, providing insights into the potential advantages of parallelization.

The present work builds upon and extends the findings of these related studies. Our focus lies in developing a parallel algorithm specifically tailored for finding all paths in a tree, with a particular emphasis on load balancing and efficient task distribution. By addressing the challenges posed by tree structures and leveraging the computational capabilities of modern multi-core processors, we aim to achieve significant reductions in processing time while ensuring effective resource utilization.

2.1 Parallel approach in finding all paths in a binary tree

We can parallelize this algorithm by finding the path through left child and right child simultaneously using two processors. Two Functions called print_pathsl and print_pathsr will be executed simultaneously. The function print_pathsl will initiate to find the paths in left sub tree and the function print_pathsr will initiate to find all paths in a right sub tree. If these algorithms are executed simultaneously then our time complexity will be approximately O(n/2). This algorithm uses maximum two processors because we can split the tree as Left Sub tree and Right sub tree. But in our laptop or desktop more than two processors are available [9].

For implementing these functions we are using two single dimensional arrays called pathl and pathr which are used by the functions print_pathsl and print_pathsr respectively.

2.2 Parallel algorithm for finding all paths in a binary tree

Step 1: Declare a node with data, Left child address and Right child Address.

Step 2: Create a tree using the function

struct node* newnode (int data).

Step 3: Call the functions

Void print_pathsl (struct node*node) and Void print_pathsr (struct node*node) in parallel to process the left sub tree and right sub tree simultaniouly.

Step 4: Both the functions calls the Void print_paths_recur (struct node*node, int path [], intpath_len) recursively to print all the paths in left sub tree and right sub tree using the function void print_array (intints [], intlen).

A. Declaration of a node as in Step 1.

struct node {int data; struct node*left; struct node*right;};

B. Function to Create a tree as in Step 2.

struct node*newnode (int data) {struct node*node=(struct node*) malloc (sizeof (struct node)); node->data=data; node->left=NULL; node->right=NULL; return (node);}

C. Function to store all the paths in left sub tree from the root node to all terminal nodes in an array as in the Step 3.

Void print_pathsl (struct node*node) {intpathl []; pathl [0]=node->data; print_paths_recur (node->left, pathl, 1);}

D. Function to store all the paths in right sub tree from the root node to all terminal nodes in an array as in the Step 3.

Void print_pathsr (struct node*node) {intpathr []; pathr [0]=node->data; print_paths_recur (node->right, pathr, 1);}

E. A recursive function which findsall the path from given node as in Step 4.

Void print_paths_recur (struct node*node, int path [], intpath_len) {if (node==NULL) return; path [path_len]=node->data; path_len++; if (node->left==NULL && node->right==NULL) {printf(“\n”); print_array (path, path_len);} else {print_paths_recur (node->left, path, path_len); //recursively calls the left node of the tree print_paths_recur (node->right, path, path_len); //recursively calls the right node of the tree}}

F. Function to print all the paths as in Step 4.

Void print_array (intints [], intlen) {int i; for (i=0; i<len; i++) {printf (“->%d”, ints [i]);} printf (“\n”);}

In the main program create a tree by calling the function newnode. After creating the tree call the functions in parallel environment.

print_pathsl (root);

print_pathsr (root);

4.1. Symmetricbinary tree

In a symmetric binary tree height of the tree can be ignored because all the terminals of the tree will be in the same height. So the time taken to travel from the root node to terminal node will be the same for all paths. For finding the all paths of a tree it is necessary to visit the entire node once. The time complexity of sequential algorithm to find all paths in DFS is O(|V|+|E|) where V is the Vertices and E is the edges in a binary tree. For the symmetric binary tree, the number of vertices in our Example 1 (Figure 2) is 7 and the edges are 6. Hence the time complexity of sequential algorithm is O (7+6) i.e., 13.

Figure 4 shows our parallel algorithm process the tree by starting in sequential and then by parallel. Hence the time taken for sequential portion is O (1+2) (1 vertices and 2 Edges) and time taken for one parallel portion is O (3+2) (3 vertices and 2 Edges). Hence the total time taken for the Example 1 is O (3+5) i.e., O (8).

Now the speedup by Amdahl’s Law is [10, 11]:

Speedup $=\frac{\text { Sequential Execution Time }}{\text { Parallel Execution Time }}$

Now efficiency of the parallel algorithm is given as:

Efficiency $=\frac{\text { Sequential Execution Time }}{\text { Parallel Execution Time } X \text { Processor used }}$

Similarly, we can prove if the level of the binary tree increases the speed and efficiency also increases as shown in the Table 1 [10, 11].

Table 3 shows the speedup (1) and efficiency (2) of the parallel algorithm of Figure 4. Both the speedup and efficiency [10, 11] are satisfying the Amdahl’s Law. Figure 5 graphically represents the time taken for Sequential and Parallel algorithms.

17-4.png

Figure 4. Sequential and parallel portions of balanced binary tree

Table 3. Speedup and efficiency of parallel algorithm for balanced binary tree

S. No	Tree Levels	No. of Vertices	No. of Edges	Sequential Time	Parallel Time	Speedup (1)	Efficiency (2)
1	2	7	6	13	8	1.60	0.81
2	3	15	14	29	16	1.81	0.90
3	4	31	30	61	32	1.90	0.95

17-5.png

Figure 5. Comparing parallel and sequential time of balanced binary tree

17-6.png

Figure 6. Speedup and efficiency of balanced binary tree

Figure 6 shows that the if the level of a balanced binary tree increases then the speedups and efficiency also increases.

A. Asymmetrical binary tree

17-7.png

Figure 7. Sequential and parallel portions of unbalanced binary tree

17-8.png

Figure 8. Sequential program execution

17-9.png

Figure 9. Parallel program execution

In Figure 7, the height of left and right trees differs from each other. Note that number of edges and vertices are same in left sub tree and right sub tree. Height of left sub tree is 3 and height of right sub tree is 4. Hence the height is Max (3, 4)=4. Time complexity with branching factor and height of the tree for DFS is O (bm) [9] where b is he branching factor and m is the height of the tree. Hence the time taken for sequential algorithm is O (24)=16. From the Figure 7 time taken for parallel portion left tree is O (22)=4 and the parallel portion of the right sub tree is O (23)=8. Among these two parallel portions maximum of 8 is taken. Time complexity of sequential portion is O (21)=2. Therefore total time taken for parallel algorithm is 8+2=10. Table 4 shows the speedup and efficiency of the parallel execution of Figure 7.

Table 4. Speedup and efficiency of parallel algorithm for unbalanced binary tree

From the Table 3 and Table 4 speedup and efficiency satisfies the Amdahl’s Law. i.e., Amdahl’s Law says that Criterium for Speedup (Sn) is 0<Sn<=n and Criterium for Efficiency (Es) 0<Es<=1. We can see that both the Tables 3 and 4 satisfies these criterium.

The OPENMP sequential and parallel programs were executed on Intel® Core (TM) i3-5005U CPU @2.00GHz (4 CPUs) machine using Code block software and gcc compiler with windows 10 operating system. The output of sequential program is shown in the Figure 8 and the output of the parallel program is shown in the Figure 9. An unbalanced tree in Figure 2 is given as input. From the Figures 8 and 9 the time taken for the parallel algorithm (0.047 Seconds) is less than the time taken for the sequential algorithm (0.094 Seconds).