Abstract
With the advancement in technology these days, we need our work to be done in a faster and efficient way, especially in the areas of telecommunication and VLSI technologies. We need our problems to be rapidly resolved. Hence, in the world of computing, a new concept of parallelism in CPU was introduced. The computer hardware is made to perform a task more resourcefully either using a CPU or a GPU. We can achieve better performance on CPU’s by parallelizing the workload using multiple thread, utilizing several processors to execute different stages. It can be done by data parallelism, by creating and distributing threads to cores. Each processor executes various threads or processes on same or different data. For instance, if in 2 core processor, we can ask CPU1 to perform Task1, simultaneously with the CPU2 performing task2. Multiple tasks are done at the same time by quickly switching between various CPU cores. The same code runs independently on different machines by data sharing embedded in the code. One of the challenges faced here is to make sure that no data in lost in the process of sharing data amongst different CPU cores. This parallelization helps reducing run time execution, thus scaling up the performance of hardware. In this project, a single source shortest path Bellman – Ford Algorithm is implemented using an execution model, POSIX threads in C. In a given shortest path problem, we need to determine the path between 2 nodes or vertices in a graph, such that the sum of weights on each edge is minimum. For example, if a salesman has to travel from place A to B which has various intermediate points and different cost, we deal with shortest path problem. Here, weight will not only be the physical distance, but time and monetary cost as well. For the project, this algorithm has been executed both in series (1 processor) and in parallel (multiple processors), performances were compared to calculate the speed-up. Performance was tested on bigger graphs to see how well larger workloads would benefit from parallelism. A speed up of 18 was achieved using 16 processors. To ensure the correctness, the execution on 1 processor versus 16 processor was tracked and verified the correctness of the results. As noted, there’s scope for improvement by employing node-based workload distribution as groups of outgoing edges and also dynamic load balancing. As seen in results, the solution is scalable with both the size of input graph and the number of processors.