Resource management techniques for multiprogrammed distributed systems
Luís Miguel Campos, Isaac D. Scherson · 1999
This research addresses the problem of how to efficiently manage the resources of a parallel/distributed system in a multiprogrammed environment. In particular I studied techniques to maximize the utilization of what is arguably the most important component of such systems: the processor. For this purpose, I implemented a discrete-event simulator and evaluated the performance of three novel algorithms in the areas of static scheduling, dynamic scheduling and dynamic load balancing. Interest in parallel computers has been propelled by both the economics of commodity priced microprocessors and a growth rate in computational requirements exceeding processor speed increases. Massively Parallel Processor (MPP) architectures have been proven quite efficient when dedicated to production computing. However they suffer significant shortcomings when applied to large scale problems in multiprogrammed environments. In order to allow the sharing of the expensive and scarce resources of a MPP to be shared among a large community of users in an efficient manner, two techniques are often employed: parallel job scheduling and load balancing. These two techniques aim to achieve one or more of the following performance goals: maximizing resource utilization, maximizing throughput, minimizing execution time and improving overall system responsiveness. My main focus, in this thesis, is on maximizing processor utilization without degrading the remaining performance goals. To effectively test the proposed algorithms, I developed a complete simulating environment. The environment provides support for most, if not all, characteristics found in today's MPP systems. We grouped those characteristics into four models, namely the architectural model, the machine execution model, the communication model and the computational model. In terms of workload modeling I provide an integrated set of tools that allow for three different descriptive models: the probabilistic model, the algorithmic model and the directed acyclic model. In this dissertation I introduce and characterize three novel algorithms, one in each of the following research areas: static scheduling, dynamic scheduling and load balancing and I demonstrate their competitiveness against previously proposed algorithms across a wide range of parallel architectures and workload choices. In addition I provide an integrated simulation environment that facilitated the performance evaluation of algorithms in each of the research areas covered by this thesis.