大規(guī)模并行計(jì)算通信可擴(kuò)展性

1、大規(guī)模并行計(jì)算通信可擴(kuò)展性分析、優(yōu)化與模擬隨著系統(tǒng)規(guī)模的擴(kuò)大和結(jié)點(diǎn)計(jì)算能力的提高， 通信已經(jīng)成為制約并行計(jì)算可 擴(kuò)展性的重要瓶頸。 通信可擴(kuò)展性問題， 即分析通信受何種因素影響并且該影響 增大到何種程度會限制系統(tǒng)的可擴(kuò)展性， 是并行計(jì)算領(lǐng)域最具挑戰(zhàn)性的理論問題 之一。本文針對通信可擴(kuò)展性問題， 首次從性能加速比的角度量化了并行計(jì)算的通 信墻，并建立了通信可擴(kuò)展性模型。 基于通信可擴(kuò)展性模型的分析結(jié)論， 本文分 別針對程序優(yōu)化和任務(wù)分配優(yōu)化， 提出了消息獨(dú)立性指導(dǎo)下的程序優(yōu)化技術(shù)和面 向多作業(yè)的分配優(yōu)化技術(shù)。最后，設(shè)計(jì)和實(shí)現(xiàn)了一款針對大規(guī)模并行計(jì)算的性能預(yù)測模擬器， 該模擬器 可用于驗(yàn)證通信可擴(kuò)

2、展性模型的正確性以及并行系統(tǒng)的各種相關(guān)優(yōu)化技術(shù)的可 擴(kuò)展性。具體而言， 本文的主要工作和創(chuàng)新點(diǎn)體現(xiàn)在： 1. 建立了通信可擴(kuò)展性模 型（第二章）目前，國際上對于通信可擴(kuò)展性問題大多是感性上的認(rèn)識，并未對 其進(jìn)行系統(tǒng)的定量研究。本文首次提出了通信墻的定量化描述， 給出了通信墻存在性定理。 由此，本 文建立了通信可擴(kuò)展性模型， 提出了系統(tǒng)度量方法及基于通信可擴(kuò)展性模型的并 行系統(tǒng)分類方法，量化了系統(tǒng)的通信可擴(kuò)展性強(qiáng)弱和廣義通信可擴(kuò)展性強(qiáng)弱。最后結(jié)合具體案例， 分析了程序、 并行機(jī)拓?fù)湟约俺Ｒ妰?yōu)化方法對通信可擴(kuò) 展性的影響， 比較了常見的巨型機(jī)拓?fù)涞膹V義通信可擴(kuò)展性強(qiáng)弱， 指出優(yōu)化系統(tǒng) 通信可擴(kuò)展性

3、和廣義通信可擴(kuò)展性的方向。 2. 提出了消息獨(dú)立性指導(dǎo)下的程序優(yōu) 化技術(shù)（第三章）基于指令重排的通信隱藏技術(shù)是優(yōu)化程序性能的主要手段之一， 然而除去該技術(shù)自身面臨的問題，它還會導(dǎo)致消息間產(chǎn)生嚴(yán)重的網(wǎng)絡(luò)資源競爭本文通過分析網(wǎng)絡(luò)資源競爭的產(chǎn)生原因， 首次提出了消息獨(dú)立性的概念并研 究了其具體涵義；然后針對 MPI( Message Passing Interface )程序，建立了 基于指令重排的消息獨(dú)立性指導(dǎo)下的程序優(yōu)化模型； 基于上述優(yōu)化模型， 設(shè)計(jì)并 實(shí)現(xiàn)了基于指令重排的消息獨(dú)立性指導(dǎo)下的程序優(yōu)化方法， 該方法可以在保證通 信隱藏最大化的前提下減少消息間的網(wǎng)絡(luò)資源競爭；針對并行 CFD(Co

4、mputational Fluid Dynamics)應(yīng)用的實(shí)驗(yàn)表明，該方法能夠很好的減少程 序的通信開銷并提升程序的性能。 3. 提出了面向多作業(yè)的分配優(yōu)化技術(shù) (第四章) 合理地為多個作業(yè)分配計(jì)算資源以滿足作業(yè)的性能需求， 對于那些使用大規(guī)模并 行計(jì)算系統(tǒng)的用戶來說十分重要。本文首次提出將多作業(yè)分配優(yōu)化問題分解為多作業(yè)分布優(yōu)化和單作業(yè)任務(wù) 映射優(yōu)化兩個子問題。 針對多作業(yè)分布優(yōu)化問題， 本文首次提出閉合最小圖劃分 模型，將多作業(yè)分布優(yōu)化問題轉(zhuǎn)化為閉合最小圖劃分問題； 針對單作業(yè)任務(wù)映射 優(yōu)化問題，本文分析了通信協(xié)議對通信開銷的影響， 首次為MPI程序提出了協(xié)議 感知的進(jìn)程映射模型 PaPP

5、。基于上述兩個模型， 本文設(shè)計(jì)并實(shí)現(xiàn)了面向多作業(yè)的分配優(yōu)化方法。 實(shí)驗(yàn)表 明，對于 NPB(NAS Parallel Benchmarks )測試集，面向多作業(yè)的分配優(yōu)化方 法有很好的性能優(yōu)化效果。4.設(shè)計(jì)并實(shí)現(xiàn)虛實(shí)結(jié)合的執(zhí)行驅(qū)動模擬器一VACED-SI(第五章)離散事件 模擬是大規(guī)模并行計(jì)算常用的性能預(yù)測方法之一。 本文基于對離散事件模擬方法 的深入分析， 提出了虛模擬和實(shí)模擬的概念； 通過對虛模擬和實(shí)模擬以及軌跡驅(qū) 動和執(zhí)行驅(qū)動方法的對比，首次從兩個正交的角度(模擬機(jī)制和事件驅(qū)動方法) 將基于離散事件模擬的性能預(yù)測方法分為四類； 針對大規(guī)模并行計(jì)算可擴(kuò)展性預(yù)測的特點(diǎn)，首次提出了第四類模擬方法虛實(shí)結(jié)合執(zhí)行驅(qū)動（VACE）D 模擬方法的模型。基于該模型，本文設(shè)計(jì)和實(shí)現(xiàn)了一款輕量級的虛實(shí)結(jié)合執(zhí)行驅(qū)動模擬器VACED-SIM在該模擬