IEEE Transactions on Computers
Due to its topological generality and flexibility, the k-ary n-cube architecture has been actively researched for various applications. However, the processor allocation problem has not been adequately addressed for the k-ary n-cube architecture, even though it has been studied extensively for hypercubes and meshes. The earlier k-ary n-cube allocation schemes based on conventional slice partitioning suffer from internal fragmentation of processors. In contrast, algorithms based on job-based partitioning alleviate the fragmentation problem but require higher time complexity. This paper proposes a new allocation scheme based on isomorphic partitioning, where the processor space is partitioned into higher dimensional isomorphic subcubes. The proposed scheme minimizes the fragmentation problem and is general in the sense that any size request can be supported and the host architecture need not be isomorphic. Extensive simulation study reveals that the proposed scheme significantly outperforms earlier schemes in terms of mean response time for practical size k-ary and n-cube architectures. The simulation results also show that reduction of external fragmentation is more substantial than internal fragmentation with the proposed scheme.
Kang, Moonsoo; Yu, Chansu; Youn, Hee Yong; Lee, Ben; and Kim, Myungchul, "Isomorphic Strategy for Processor Allocation in k-Ary n-Cube Systems" (2003). Electrical Engineering & Computer Science Faculty Publications. 98.
Moonsoo, K., Chansu, Y., Hee, Y. Y., Ben, L., & Myungchul, K. (May 01, 2003). Isomorphic strategy for processor allocation in k-ary n-cube systems. IEEE Transactions on Computers, 52, 5, 645-657.
© 2003 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.