A fast and efficient processor management scheme for k-ary n-cubes

Job scheduling and processor allocation are two key components of processor management technique in a multiprocessor operating system. We propose a fa st and efficient processor management technique, called virtual cube (VC), for k-ary n-cubes in this paper. The proposed scheme supports spatial alloc ation of jobs to the virtual cubes of the system and multiprograms the virt ual cubes in a round-robin fashion. The objective here is to reduce job wai ting lime and fragmentation. The VC scheme uses a fast sub-cube allocation algorithm called enhanced k-ary buddy. A novel approach, called paging, is proposed for fast submesh allocation. When used with the first fit algorith m, the paging scheme is shown to be extremely fast and efficient compared t o other contemporary submesh allocation algorithms for k-ary n-cubes. We al so study the impact of page size on performance and illustrate a methodolog y to compute optimal page size. Simulation results show that the VC scheme with its multiprogramming capability can boost system performance considera bly and outperforms all existing policies while incurring minimal run-time overhead. (C) 1998 Academic Press.