Evaluating Heuristic Scheduling Algorithms for High Performance Parallel Processing

Most cluster systems used in high performance computing do not allow process relocation at run-time. Finding an allocation that results in minimal completion time is NP-hard and (non-optimal) heuristic algorithms have to be used. One major drawback with heuristics is that we do not know if the result is close to optimal or not. Here, we present a method for finding an upper bound on the minimal completion time for a given program. The bound helps the user to determine when it is worth-while to continue the heuristic search for better allocations. Based on some parameters derived from the program, as well as some parameters describing the hardware platform, the method produces the minimal completion time bound. A practical demonstration of the method is presented using a tool that produces the bound.