分布存储并行机上的自动数据布局优化模型.pdf

《分布存储并行机上的自动数据布局优化模型.pdf》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第37卷第1O期计算机研究与发展VOl.37NO.1O2OOO年1O月JOURNALOFCOMPUTERRESEARC~SDEVELOPMENTOct.2OOO分布存储并行机上的自动数据布局优化模型谢幸陈国良武继刚(中国科学技术大学计算机科学技术系合肥23OO27D(国家高性能计算中心合肥23OO27D摘要在分布式并行机上数据布局的质量极大的影响着应用程序的执行性能.以往的研究一般将自动数据布局优化问题近似分解为数据对准优化和数据分布优化两步来解决且对两者的结合只研究了一维的情况.在相关研究工作的基础上在多维情况下将数据对准优化与数据分布优化结合在一个模型当中提出了一个数据对准优

2、化与数据分布优化统一的多维静态数据布局模型避免了采用启发式策略从而更加精确地描述了自动数据布局优化问题.同时给出了将模型形式化为O-1整数规划问题的方法并通过示例演示了模型的构造和形式化过程.关键词数据布局并行化编译数据对准数据分布中图法分类号TP311MODELOFAUTOMATICDATALAYOUTOPTIMIZATIONONDISTRIBUTEDMEMORYPARALLELCOMPUTERSXIEXingC~ENGuO-LiangandWUJi-Gang(DePa7tHentofCoHP/te7SczenceanCTechnolog}Unze7Szt}ofSczencea

3、nCTechnolog}ofChznaHefez23OO27D(NatzonalHzghPe7fo7HanceCoHP/tzngCente7Hefez23OO27DAbstractThegualityOfdatalayOutgreatlyaffectStheperfOrmanceOfapplicatiOnSOndiStributedmemOryparallelcOmputerS.PreviOuSreSearcheffOrtSOntheOptimiZatiOnOfdatalayOutuSuallydividetheOptimiZatiOnintOdataalignmentOptim

4、iZatiOnanddatadiStributiOnOptimiZatiOnandOnlyOnedimenSiOnaldatalayOutiSStudiedfOrtheircOmbinatiOn.InthiSpaperdataalignmentOptimiZatiOnanddatadiStributiOnOptimiZatiOnarecOmbinedinaSinglemOdelundermulti-dimen-SiOnalcircumStance.AmOdelfOrStaticmulti-dimenSiOnaldatalayOutthatcanSOlvedataalign-men

5、tanddatadiStributiOnprObleminOnlyOneStepiSprOpOSedanditcandeScribetheautOmaticdatalayOutOptimiZatiOnmOreaccurately.AO-1integerprOgrammingfOrmulatiOnOfthiSmOdeliSalSOpreSented.KeywordsdatalayOutparalleliZingcOmpilerdataalignmentdatadiStributiOn1引言在大规模分布式并行计算环境中由于存储系统的分布性访问本地存储器的开销要比访问远程存储器的开销小

6、一个数量级以上.为了在提高数据局部性的同时尽量提高程序的并行性数据的布局策略成为提高并行计算性能的一个关键性问题.自动数据布局优化也是在分布式并行机上研制高效的并行编译系统或辅原稿收到日期:1999-O9-2O;修改稿收到日期:1999-12-24.本课题得到国家八六三高技术研究发展计划基金资助(项目编号863-3O6-ZD11-O1-2D.谢幸男1977年生博士研究生主要研究方向为并行处理~组合优化和随机算法.陈国良男1938年生教授博士生导师主要研究方向为并行分布计算~算法设计.武继刚男1963年生博士研究生主要研究方向为并行分布计算~计算智能.1174计算机研究与发展Z00

7、0年助工具的一项关键技术.对于数据布局的优化问题一般是将其分解为数据对准的优化和数据分布的优化两部分.数据对准是指对每一个代码段中出现的数组找出其相互之间各维的对应关系<维间对准)及各对应维之间的错位关系<维内对准).而数据分布则是指将对准后的数组指定的一个或多个维分布到处理器上的操作这里的分布方式可以是块分布~循环分布或块循环分布等.一个好的数据布局应该能在提高数据局部性的同时尽量提高程序的并行性最优数据布局策略的选择与许多因素有关如机器结构~编译系统~问题规模和可用处理器数等