A NEW PRESENTATION OF METACUBES FOR ALGORITHMIC DESIGN AND CASE STUDIES: PARALLEL PREFIX COMPUTATION AND PARALLEL SORTING

作     者：Li, Yamin Peng, Shietung Chu, Wanming 

作者机构：Hosei Univ Dept Comp Sci Tokyo 1848584 Japan Univ Aizu Dept Comp Hardware Aizu Wakamatsu Fukushima 9658580 Japan 

出 版 物：《JOURNAL OF THE CHINESE INSTITUTE OF ENGINEERS》 

年 卷 期：2009年第32卷第7期

页      面：939-949页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 

主　　题：Hypercube Metacube parallel prefix parallel sorting 

摘      要：A versatile family of interconnection networks alternative to hypercubes, called Metacubes, has been proposed for building extremely large scale multiprocessor systems with a small number of links per node. A Metacube MC(k, m) connects 2(2km + k) nodes with only k + in links per node. Metacube can be used to build parallel computing systems of very large scale with a small number of links per node. In this paper, we propose a new presentation of Metacube for algorithmic design. Based on the new presentation, we give efficient algorithms for parallel prefix computation and parallel sorting on Metacubes, respectively. The algorithm for prefix computation runs in 2(k)m (k + 1) + k communication steps and 2(k + 1)m + 2k computation steps on MC(k, m). The sort algorithm runs in O(2(k)m + k)(2) computation steps and O(2(k)m (2k + 1) + k)(2) communication steps on MC(k, m).