A unified approach to processor allocation and task scheduling for partitionable parallel architectures
Jeeraporn Srisawat, Nikitas A. Alexandridis · 1999
Massively product network-based partitionable parallel machines are an efficient and scalable class of computer systems, used to execute various parallel 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. In order to provide appropriate free sub-systems for new tasks, an operating system have to dynamically partition the computer system to allocate resources for incoming tasks, as well as to deallocate resources (and recombine partitions) as soon as they become available when a task completes. A number of processor allocation/deallocation techniques have been proposed in the past, with various degrees of time complexity and system performance. However, there are some limitations: (1) most existing processor allocations are developed for a specific interconnection network system such as a mesh system or a hypercube system and (2) it is difficult to design an efficient processor allocation algorithm for various network topologies. In this dissertation, a “unified approach” is introduced to perform processor allocation/deallocation and task scheduling for massively (partitionable) parallel architectures whose interconnection networks are in the product networks class. The “unified model ” includes a k-Tree system state representation and a general methodology for processor allocation/deallocation and task scheduling (which consists of 4 main general procedures: a network partitioning procedure, a sub-system combining procedure, a searching procedure, and a task scheduling procedure). This unified model can be applicable for any network belonging to the product networks class (such as multi-dimensional meshes, multi-dimensional toruses, hypercubes, generalized hypercubes, etc.). The development of the unified model is also presented (on a number of different network configurations such as hypercubes, ring-hypercubes, two-dimensional (2-D) meshes, 3-D meshes, 2-D toruses, and 3-D toruses). For these network configurations, the unified model can (1) “provide efficient (linear) searching time” in order to find the appropriate available sub-system for each incoming task and (2) “yield the comparable system performance” on hypercube and 2-D mesh systems. In simulation studies, the system performance is evaluated in terms of system utilization, system fragmentation, average waiting time, average response time, and throughput, resulted by applying the processor allocation/deallocation and task scheduling algorithm and varying system parameters (i.e., system sizes, distributions of task sizes, workloads, networks, etc.).