Processor scheduling and allocation for 3D torus multicomputer systems

Multicomputer systems achieve high performance by utilizing a number of com puting nodes. Recently, by achieving significant reductions in communicatio n delay, the three-dimensional (3D) torus has emerged as a new candidate in terconnection topology for message-passing multicomputer systems. In this p aper, we propose an efficient processor allocation scheme-scan search schem e-for the 3D torus based on a first-fit approach. The scan search scheme mi nimizes the average allocation time for an incoming task by effectively man ipulating the 3D information on a torus as 2D information using a data stru cture called the CST (Coverage Status Table). Comprehensive computer simula tion reveals that the allocation time of the scan search scheme is always s maller than that of the earlier scheme based on a best-fit approach. The di fference gets larger as the input load increases, and it is as much a facto r of 3 for high load. To investigate the performance of the proposed scheme in different scheduling environments, we also consider a non-FCFS scheduli ng policy along with the typical FCFS policy. The allocation time complexit y of the scan search scheme is O((LWH2)-H-2). This is significantly smaller than that of the existing scheme which is O((LWH4)-W-4-H-4). Here, L, W, a nd H represent the length, width, and height of 3D torus, respectively.