ALGORITHMS FOR MATRIX TRANSPOSITION ON BOOLEAN N-CUBE CONFIGURED ENSEMBLE ARCHITECTURES

作     者：JOHNSSON, SL HO, CT 

作者机构：THINKING MACHINE CORPCAMBRIDGEMA 02142 YALE UNIVDEPT COMP SCINEW HAVENCT 06520 

出 版 物：《SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS》 (工业与应用数学会矩阵分析和应用杂志)

年 卷 期：1988年第9卷第3期

页      面：419-454页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：65F30 68P99 68Q20 68Q25 matrix transpose Boolean cubes personalized communication routing data encoding 

摘      要：In a multiprocessor with distributed storage the data structures have a significant impact on the communication complexity. In this paper we present a few algorithms for performing matrix transposition on a Boolean n-cube. One algorithm performs the transpose in a time proportional to the lower bound both with respect to communication start-ups and to element transfer times. We present algorithms for transposing a matrix embedded in the cube by a binary encoding, a binary-reflected Gray code encoding of rows and columns, or combinations of these two encodings. The transposition of a matrix when several matrix elements are identified to a node by consecutive or cyclic partitioning is also considered and lower bound algorithms given. Experimental data are provided for the Intel iPSC and the Connection Machine.