PROCESSOR ALLOCATION IN 2D MESH-CONNECTED MULTICOMPUTERS

Abstract

Massively mesh-connected parallel machines are an efficient and scalable class of computer systems used to execute supercomputing applications. In such systems, a number of independent smaller tasks (from the same or different applications) come in, each requiring at run time a separate subsystem (or partition to execute). There is a need for the operating system to dynamically partition the computer system to allocate resources to incoming tasks, as well as to deallocate resources (and recombining partitions) as soon as they become available when a task completes. A number of processor allocation and deallocation techniques have been proposed in past, with various degrees of time complexity and system performance. The processor allocation schemes are broadly divided into two categories: Contiguous and Non-contiguous. In this dissertation only contiguous processor allocation schemes are considered. The contiguous processor allocation schemes studied_rre 2D Buddy, Best Fit Bit Map, Quick Allocation, First Fit Quad Tree, Best Fit Quad Tree, and Stack Based schemes. This dissertation work aims at comparing the performance of different processor allocation schemes so as to better understand the implementation issue and tradeoff's involved. A generalized simulation framework was developed in C++ on which three processor allocation schemes are implemented. The simulation implementation is also discussed so as to give an idea of how to implement any further processor allocation scheme on it. Computer simulation results reveal that Best-Fit processor allocation scheme results in improvement in system performance (in term of system utilization and average task completion time) than other contiguous processor allocation schemes.