并行计算时间模型和并行机系统性能new

《并行计算时间模型和并行机系统性能new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据第21卷第5期计算机学报V01．21No．51998年5月CHINESEJ．COMPUTERSMay1998===％=======≈；====；％======{=========================一一一并行计算时间模型和并行机系统性能乔香珍(中国科学院计算技术研究所北京100080)(国家智能计算机研究开发中心北京100080)摘要本文重点从共享存储器式并行机系统体系结构中的新技术和并行软件系统的新特点分析了影响并行算法和应用程序性能的各种因素，并提出改进的并行计算时间模型，给出了提高并行算法和应用软件性能的原则和实例．从理论和实践两方面证明

2、并行处理性能依赖于算法、体系结构和系统软件等多方面因素．关键词并行算法，并行计算时间模型，Cache，并行机性能．分类号：TP302AbstractATIMINGMoDELANDPARALLELCoMPUTERPERFoRMANCEQIAOXiang—Zhen(InstituteofComputingTechnology，ChineseAcademyofSciences，Belting100080)(NationalResearchCenterforIntelligentComputingSystems，Beifing100080)Themodelsforpara

3、llelcomputationaresurveyedanddiscussedinthispaper，theemphasesisputonthemodelforsharedmemorymuhiprocessors．Theperformanceofaparallelalgorithmandapplicationonasharedmemorymultipr0～cessorisaffectedbyfactorssuchassequentialcode，parallelarchitectureandsys—temsoftware．Amodifiedtimingmodelis

4、presentedandanalyzedinthispaper．Thistimingmodeltakesaccountsoftheeffectsofcacheperformance，processcre-ationandsynchronization，andtheeffectofsystemsoftware．Theexamplestoil—lustratethesecharacteristicsaregiven．SomeefficientmethodstoaidtheUsertoimprovetheiralgorithmsforhigherperformancea

5、represented．Bothanalyticalandexperimentalresultsaregiven．Theseexamplesaretestedonsomesharedmemorymultiprocessors．Theseprinciplesareimportantfortheeffectiveuseofsharedmem—orymultiDrocessors．KeywordsParallelalgorithm，timingmodelforparallelcomputation，cache，mul～tiprocessorperformance．本文1

6、996—08—19收到，修改文1997—11—08收到．本课题得到国家自然科学基金(编号69573033)和国家863高科技基金资助．乔番珍，女，1943年生，研究员，主要研究兴趣为并行处理、并行算法与应用．万方数据414计算机学报1引言随着并行处理技术的发展，实用并行机系统的结构也越来越复杂卟]．人们逐渐发现，在理论上具有较好性能的并行算法，在实际并行机系统实现时不一定高效．有些在某类并行机上高效的算法在另一类并行机系统不一定高效．这一现实激发了对并行计算时间模型和加速比评价的重新研究o“’5’7]．并行处理中衡量性能的一个重要参数是并行加速比：S，一T，／Tp

7、，在理论上分析算法性能时往往只考虑算法所需要执行的基本操作数或步数，即丁。，丁，仅代表了一个算法中算术运算的时间．Amdahl[23定律也给出了这一问题的基本描述：Sp一(瓦+tp)／(以+tp／P)．其中t，+t，是某一算法在单机上的运行时间，t。是这一算法中不可并行部分的运行时间，t，为可并行部分的运行时间，P表示并行机中处理器个数．在实用的并行机系统问世之前，或进行并行算法的理论研究时，上述运行时间往往也仅考虑算术运算量．Ware[93曾给出一个简单的并行时间模型：T，一t；+tp／P．事实上此公式即是Amdahl公式中的分母．以上两个模型都是在真正的并行机

8、系统问世前