基于直径为2的摩尔图网络的并行矩阵乘算法  

A Parallel Matrix Multiplication Algorithm Based on Network of Moore Graph of Diameter 2

作　　者：张冰[1] 

机构地区：[1]深圳大学计算机与软件学院,广东深圳518060

出　　处：《计算机学报》2013年第9期1843-1849,共7页Chinese Journal of Computers

基　　金：国家自然科学基金(90207012);深圳市科技研发资金基础研究基金(JC201005280459A)资助~~

摘　　要：提出了一个并行矩阵乘算法IPBPMM(Interconnected Processor-Based Parallel Matrix Multiplication).该算法运行在以五角形、Petersen图和Hoffman-Singleton图等直径为2的摩尔图(满足n=d2+1,n为节点数,d为度)为拓扑结构的由n个独立处理器构成的机群并行计算环境中.与基于二维环绕网孔阵列拓扑结构的Cannon和Fox等并行矩阵乘法算法相比较,IPBPMM算法通信开销较小,加速比更高,同时还具有矩阵分块可随机分布在各个节点中,无需事先按一定规律装入各节点中的特点.同时IPBPMM算法也能很好地扩充到由多个直径为2的摩尔图为拓扑结构组合构成的并行计算环境中,且随着网络的扩大,算法的并行加速比更高.A parallel matrix multiplication algorithm called IPBPMM （interconnected processorbased parallel matrix multiplication） algorithm is presented. The algorithm runs on parallel computing environment consisting of clusters of n independent processors connected using topology of Moore graph of diameter 2（satisfy n=d^2＋1, n is number of nodes, d is degree）, such as Pentagon, Petersen and Hoffman-Singleton graph. Compared with Canon and Fox parallel matrix multiplication algorithm which are based on the 2-D mesh ring interconnection network, the commu- nication cost is low and the divided sub-matrix can be randomly distributed among the processors in IPBPMM algorithm, without the need to load the sub-matrices into processors according to a specific rule. In addition, IPBPMM algorithm can be well scaled onto larger parallel computing networks with topological structure composed by combining multiple basic networks of Moore graph of diameter 2, and as network size grows, the parallel speed up of IPBPMM algorithm becomes even high.

关 键 词：并行算法 并行矩阵乘法 摩尔图 网络拓扑结构 并行与分布式计算 高性能计算 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]