Abstract | ||
---|---|---|
An efficient processor allocation policy is presented for hypercube computers. The allocation policy is called free list since it maintains a list of free subcubes available in the system. An incoming request of dimension k (2k nodes) is allocated by finding a free subcube of dimension k or by decomposing an available subcube of dimension greater than k. This free list policy uses a top-down allocation rule in contrast to the bottom-up approach used by the previous bit-map allocation algorithms. This allocation scheme is compared to the buddy, gray code (GC), and modified buddy allocation policies reported for the hypercubes. It is shown that the free list policy is optimal in a static environment, as are the other policies, and it also gives better subcube recognition ability compared to the previous schemes in a dynamic environment. The performance of this policy, in terms of parameters such as average delay, system utilization, and time complexity, is compared to the other schemes to demonstrate its effectiveness. The extension of the algorithm for parallel implementation, noncubic allocation, and inclusion/exclusion allocation is also given |
Year | Venue | Keywords |
---|---|---|
1991 | Interconnection networks for high-performance parallel computers | parallel processing,bottom-up approach,efficient processor allocation policy,time complexity,inclusion/exclusion allocation,dimension k,hypercube computers,allocation policy,system utilization,allocation scheme,previous bit-map allocation algorithm,buddy allocation,exclusion allocation,gray code,hypercube computer,free list,average delay,parallel implementation,top-down allocation rule,noncubic allocation,free list policy,top-down processor allocation scheme,modified buddy allocation policy,hypercube networks,hypercubes,computer architecture,topology,indexing terms,bottom up,resource management,concurrent computing,top down |
Field | DocType | ISBN |
Static memory allocation,Free list,Computer science,Parallel computing,Top-down and bottom-up design,Parallel processing,Gray code,Time complexity,Hypercube,Mathematical logic,Distributed computing | Journal | 0-8186-6197-6 |
Citations | PageRank | References |
58 | 3.93 | 8 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Jong Kim | 1 | 471 | 49.30 |
Chita R. Das | 2 | 258 | 28.49 |
Woei Lin | 3 | 137 | 24.80 |