Load Balancing Run-Times and Space Usage for Computing the Power Set
Roger L Goodwin · 2020
This paper discusses load balancing the number of sets on multiple processors to compute the power set. The algorithm complexity measures (e.g. run-time and space usage) are merely functions of the load balance.This paper presents two approaches to computing the power set in a parallel environment. Both approaches use different round robin load balancing algorithms. Because of the load balance assignments, both approaches have different production algorithms for computing the power set. This paper covers both the run-time analyses and the space usage analyses of the parallel algorithms. We present mathematical formulas for the space usage analyses.We present a third, non-parallel algorithm for benchmark purposes. The purpose of the algorithm is to give the total amount of space needed to save the power set. The non-parallel algorithm also gives some idea of the maximum run-time an algorithm should take to find any of the sub-sets to the power set on any given processor in a parallel environment.