并行算法研究方法学

《并行算法研究方法学》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第31卷第9期计算机学报Vol.31No.92008年9月CHINESEJOURNALOFCOMPUTERSSept.2008并行算法研究方法学陈国良孙广中徐云吕敏(中国科学技术大学计算机科学与技术系合肥230027)(国家高性能计算中心(合肥)合肥230027)(安徽省高性能计算重点实验室合肥230027)摘要并行算法是计算机科学中重要的研究内容,已有几十年的发展历程.回顾一下其研究历程,既有高潮也有低谷,究其原因是,它没有形成自身的一套研究方法学.为此文中提出并行算法研究要建立起一套完整的“理论2设计2实现2应用”的学科体系,也就是所谓的并行算法研究的生态环境.只有这样才能够保持并

2、行算法研究稳定、可持续发展,并使得并行算法的研究成果更加实用,从而更富有生命力.关键词方法学;并行算法理论;并行算法设计与分析;并行算法实现;并行应用中图法分类号TP301MethodologyofResearchonParallelAlgorithmsCHENGuo2LiangSUNGuang2ZhongXUYunLUMin(DepartmentofComputerScience,UniversityofScienceandTechnologyofChina,Hefei230027)(NationalHighPerformanceComputingCenteratHefei,Hefe

3、i230027)(AnhuiProvincialKeyLaboratoryofHighPerformanceComputing,Hefei230027)AbstractParallelAlgorithmisanimportantresearchareaincomputerscience,withadevelop2menthistoryofseveraldecades.Basedontheresearchhistorywithdownturnandclimax,theau2thorsfigureoutthereasonforthatisabsentofaresearchmethodolo

4、gyonparallelalgorithms.Thispaperconcludesresearchonparallelalgorithmsshouldestablishacompletesystemof"Theory2Design2Implementation2Applications",whichisecologicalenvironmentofparallelalgo2rithmsresearch.Onlyinthiswaycanwemaintainthesteadyandsustainabledevelopmentofpar2allelalgorithmsresearch.Mor

5、eover,theresultsofresearchonparallelalgorithmswillbemorepracticalandmorefullofvitality.Keywordsmethodology;parallelalgorithmtheory;designandanalysisofparallelalgorithms;implementationofparallelalgorithms;parallelapplications题,然后使用多台计算机同时求解它.在现实世界中1引言存在着大量的并行性,在日常生活中,人们可能自觉或不自觉地都在运用着并行,只不过人们往往习惯简

6、单地讲,并行算法就是用多台处理机联合求了串行方式,而对并行性似有陌生之感而已.同时就解问题的方法和步骤,其大致的执行过程是将给定计算科学而言,并行计算理论仍处于发展阶段,特别的计算问题首先分解成若干个尽量相互独立的子问是早期并行机均很昂贵,编写并行软件又很难,所以收稿日期:2008206203.本课题得到国家自然科学基金重点项目(60533020)资助.陈国良,男,1938年生,教授,博士生导师,中国科学院院士,研究领域为并行计算模型、并行算法.E2mail:glchen@ustc.edu.cn.孙广中,男,1978年生,博士,讲师,研究方向为并行计算、组合优化.徐云,男,1960年生

7、,博士,副教授,研究方向为并行算法、生物信息学.吕敏,女,1977年生,博士,讲师,研究方向为并行算法、组合图论.1494计算机学报2008年并行性的优点尚未被普遍地认同.代.这一阶段,在各种不同互连结构的SIMD模型上人们对并行性的需求是很明显的.首先,对于那和共享存储的SIMD模型上设计出了很多优秀的非些要求快速计算的应用问题,单处理机由于器件受数值并行算法.相应的在这一时期,也出版了几部非[129]物理速度的限制而无法满足要求,所以使用多