OTIS网络结构的并行矩阵乘算法
DOI: 10.11830/ISSN.1000-5013.2008.03.0357
Keywords: 矩阵乘法, 并行算法, 光交换互连系统, 映射策略, 拓扑结构
Abstract:
提出基于光交换互连系统(OTIS)网络结构的矩阵乘并行算法,分析它的时间复杂性.采用一种新映射策略来处理一般OTIS网络结构上的矩阵映射,即矩阵映射策略是根据基图中的哈密尔顿路径来分配处理器的.通过OTIS网络的拓扑结构模拟实验,结果表明,OTIS网络矩阵乘算法的性能优于Cannon算法,更加优于O(n3)串行矩阵乘算法.
| [1] | MARSDEN G, MARCHAND P, HARVEY P. Optical transpose interconnection system architectures [J]. Optics Letters, 1993, (13):1083-1085.
|
| [2] | 孙家昶, 张林波, 迟学斌. 网络并行计算与分布式编程环境 [M]. 北京:科学出版社, 1996.
|
| [3] | 陈国良. 并行计算结构、算法、编程 [M]. 北京:高等教育出版社, 2003.
|
| [4] | 吴建平, 迟学斌. 分布式系统上并行矩阵乘法 [J]. 计算数学, 1999(1):99-108.doi:10.3321/j.issn:0254-7791.1999.01.012.
|
| [5] | WANG C F, SAHNI S. Matrix multiplication on the OTIS-Mesh optoelectronic computer [J]. IEEE Transaction on Computer, 2001(7):635-645.
|
| [6] | PARHAMI B. The Hamiltonicity of swapped (OTIS) networks built of Hamiltonian component networks [J]. Information Processing Letters, 2005(4):441-445.
|
Full-Text
