| 并行无存储冲突的邻接矩阵算法 |
| |
| 引用本文： | 李朝鹏,成运.并行无存储冲突的邻接矩阵算法[J].数字社区&智能家居,2009,5(9):7201-7202. |
| |
| 作者姓名： | 李朝鹏 成运 |
| |
| 作者单位： | 湖南人文科技学院通控系,湖南娄底417000 |
| |
| 基金项目： | 国家自然科学基金项目（90715029）;湖南省自然科学基金项目（07JJ6116）,湖南省教育项目,湖南省重点建设学科资助 |
| |
| 摘 要： | 邻接矩阵算法在科学计算与信息处理方面有着极为重要的应用，是图论的基础研究之一。针对目前邻接矩阵算法多是基于串行，或并行SIMD模型而无法解决存储冲突的问题，提出一种基于SIMD—EREW共享存储模型的并行邻接矩阵算法，算法使用O（p）个并行处理单元，在O（n^2／p）的时间内完成对n个数据点邻接矩阵的计算。将提出算法与现有算法进行的性能对比分析表明：本算法明显改进了现有文献的研究结果，是一种并行无存储冲突的邻接矩阵算法。
|
| 关 键 词： | 邻接矩阵 并行算法 存储冲突 |
An Parallel Adjacent Matrix Algorithm without Memory Conflicts |
| |
| LI Zhao-peng,CHENG Yun.An Parallel Adjacent Matrix Algorithm without Memory Conflicts[J].Digital Community & Smart Home,2009,5(9):7201-7202. |
| |
| Authors: | LI Zhao-peng CHENG Yun |
| |
| Affiliation: | (Hunan University, of Humanities, Science and Technology, Loudi 417000, China) |
| |
| Abstract: | 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. |
| |
| Keywords: | adjacent matrix parallel algorithms memory conflicts |
| 本文献已被 维普 等数据库收录！ |
|
