Sequential And Parallel Implementations for the Dynamic Programming Approach to Solve the Activity Selection Problem: A Comparison

Abstract

Dynamic programming is a popular approach for solving computational problems that can be broken down into overlapping sub-problems or problems that exhibit optimal substructure. That is, if an optimal solution for a problem can be formed from optimal solutions of its sub-problems, it is considered to exhibit optimal substructure. We aim to assess the results of utilizing the increasing ability of modern computers to distribute the computational workload across multiple threads by executing our program using multiple threads. A dynamic programming algorithm can be used to solve the well-known activity selection problem, a classic optimization problem in which the goal is to select the maximum number of activities from a set of activities by comparing the activities’ start and end times to find the largest set of activities whose times do not overlap. This paper investigates the possibility of parallelizing the algorithm, discussing the effects of parallelization on the correctness of the algorithm's output, the occurrence of race conditions - which happen when shared data is modified by multiple threads simultaneously - within the algorithm and exploring strategies to address and resolve them, the resulting overhead of these strategies, and the possibility of achieving speedup. By parallelizing the bottom-up implementation of the dynamic programming algorithm to solve the activity selection problem, we were able to detect and solve a race condition on a std::vector container that caused the code to only be able to run if elements are only pushed into it within an OpenMP critical section. This resulted in synchronization overhead as the number of threads used in the program increased. Furthermore, we were able to achieve sub-linear speedups, of 1.2025 in the overall algorithm execution time, and of 2.0256 in the parallel section’s execution time using eight threads.