并行无存储冲突的邻接矩阵算法  

An Parallel Adjacent Matrix Algorithm without Memory Conflicts

作　　者：李朝鹏[1] 成运[1] LI Zhao-peng, CHENG Yun （Hunan University, of Humanities, Science and Technology, Loudi 417000, China）

机构地区：[1]湖南人文科技学院通控系,湖南娄底417000

出　　处：《电脑知识与技术》2009年第9期7201-7202,共2页Computer Knowledge and Technology

基　　金：国家自然科学基金项目（90715029）;湖南省自然科学基金项目（07JJ6116）,湖南省教育项目,湖南省重点建设学科资助

摘　　要：邻接矩阵算法在科学计算与信息处理方面有着极为重要的应用，是图论的基础研究之一。针对目前邻接矩阵算法多是基于串行，或并行SIMD模型而无法解决存储冲突的问题，提出一种基于SIMD—EREW共享存储模型的并行邻接矩阵算法，算法使用O（p）个并行处理单元，在O（n^2／p）的时间内完成对n个数据点邻接矩阵的计算。将提出算法与现有算法进行的性能对比分析表明：本算法明显改进了现有文献的研究结果，是一种并行无存储冲突的邻接矩阵算法。Adjacent matrix algorithm plays a very important role in scientific computing and information processing, which is one of the most extensively studied branch in data mining. Presently the adjacent matrix algorithms based on serial or SIMD which can not process memory conflicts among different processors. To overcome this shortcomings, a new parallel algorithm based on SIMD-EREW is proposed in this paper. The proposed algorithms can compute adjacent matrix of n objects with O（p） processors in O（n2/p） time. Performance comparisons show that it is an improved result over the past researches.

关 键 词：邻接矩阵 并行算法 存储冲突 

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