并行算法研究方法學(xué)

《并行算法研究方法學(xué)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、第31卷第9期計算機學(xué)報Vol.31No.92008年9月CHINESEJOURNALOFCOMPUTERSSept.2008并行算法研究方法學(xué)陳國良孫廣中徐云呂敏(中國科學(xué)技術(shù)大學(xué)計算機科學(xué)與技術(shù)系合肥230027)(國家高性能計算中心(合肥)合肥230027)(安徽省高性能計算重點實驗室合肥230027)摘要并行算法是計算機科學(xué)中重要的研究內(nèi)容,已有幾十年的發(fā)展歷程.回顧一下其研究歷程,既有高潮也有低谷,究其原因是,它沒有形成自身的一套研究方法學(xué).為此文中提出并行算法研究要建立起一套完整的“理論2設(shè)計2實現(xiàn)2應(yīng)用”的學(xué)科體系,也就是所謂的并行算法研究的生態(tài)環(huán)境.只有這樣才能夠保持并

2、行算法研究穩(wěn)定、可持續(xù)發(fā)展,并使得并行算法的研究成果更加實用,從而更富有生命力.關(guān)鍵詞方法學(xué);并行算法理論;并行算法設(shè)計與分析;并行算法實現(xiàn);并行應(yīng)用中圖法分類號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題,然后使用多臺計算機同時求解它.在現(xiàn)實世界中1引言存在著大量的并行性,在日常生活中,人們可能自覺或不自覺地都在運用著并行,只不過人們往往習(xí)慣簡

6、單地講,并行算法就是用多臺處理機聯(lián)合求了串行方式,而對并行性似有陌生之感而已.同時就解問題的方法和步驟,其大致的執(zhí)行過程是將給定計算科學(xué)而言,并行計算理論仍處于發(fā)展階段,特別的計算問題首先分解成若干個盡量相互獨立的子問是早期并行機均很昂貴,編寫并行軟件又很難,所以收稿日期:2008206203.本課題得到國家自然科學(xué)基金重點項目(60533020)資助.陳國良,男,1938年生,教授,博士生導(dǎo)師,中國科學(xué)院院士,研究領(lǐng)域為并行計算模型、并行算法.E2mail:glchen@ustc.edu.cn.孫廣中,男,1978年生,博士,講師,研究方向為并行計算、組合優(yōu)化.徐云,男,1960年生

7、,博士,副教授,研究方向為并行算法、生物信息學(xué).呂敏,女,1977年生,博士,講師,研究方向為并行算法、組合圖論.1494計算機學(xué)報2008年并行性的優(yōu)點尚未被普遍地認同.代.這一階段,在各種不同互連結(jié)構(gòu)的SIMD模型上人們對并行性的需求是很明顯的.首先,對于那和共享存儲的SIMD模型上設(shè)計出了很多優(yōu)秀的非些要求快速計算的應(yīng)用問題,單處理機由于器件受數(shù)值并行算法.相應(yīng)的在這一時期,也出版了幾部非[129]物理速度的限制而無法滿足要求,所以使用多