Maximum Utilization of Parallel Computers
Vitus J. Leung, J.M. DeLaurentis · 2002
Two GAO reports have questioned the utilization of computing resources in the Department of Energy.While Jones and Nitzberg have observed that utilization peaks at 60-80% for a variety of architectures and allocation policies.This investigation examines the theoretical and observed average maximum efficiencies of massively parallel computers, and shows that the observed efficiency at Sandia is very nearly optimal.Here, the average maximum efficiency is defined as the expected utilization or efficiency when the queue is nonempty.We have developed a model that allows us to compare the observed efficiency with the average maximum efficiency, and allows us to forecast the expected maximum efficiency given the average size of the smallest task, S, waiting in the queue.The model predictions are in excellent agreement with the measured efficiencies obtained from the Sandia data.The average number of idle processors may be estimated by analyzing the embedded renewal process.We let Y ( t ) denote the number of idle processors, and we set S equal to the random variable representing the size of the smallest task in the queue.The stopping time T* denotes the time when exactly S processors become available; the process Y ( t ) is reset to zero when the level S is attained.Also, we let N denote the number of processors, y = E [ S / N ] , and'we set p ( y ) equal to the efficiency when E [ S / N ] = y; that is, p(y) is the maximum efficiency when the smallest waiting task requires, on average, y N nodes.We show that p(y) = X -' E [ S / N ] / E [ T * ] ,where X-' is the mean of the exponentially distributed completion times.