Efficient Processor Allocation for 3D Tori

Efficient allocation of distinct subsets of processors to different jobs (i.e., space sharing) is critical to the performance of parallel computers, especially large scale parallel computers. This paper presents an efficient and lookahead strategy for processor allocation in 3D torus-connected systems, such as the Cray T3D, where each job requests for an exclusive allocation of a 3D submesh. The proposed processor allocation scheme has the following features: complete recognition of all maximal free submeshes, compact representation of submeshes, fairness with FCFS scheduling discipline, higher system utilization with lookahead scheduling, no restriction on the submesh orientation, and low allocation and scheduling overhead. The performance of the proposed strategy is demonstrated through simulation. Keywords: Processor allocation, Job scheduling, Lookahead scheduling, Torus, Mesh, Performance evaluation, Parallel computer. This work was supported in part by NSF grants CDA-9121641 a..