《并行程序設(shè)計(jì)》實(shí)驗(yàn)指導(dǎo)書(shū)之四

《并行程序設(shè)計(jì)》實(shí)驗(yàn)指導(dǎo)書(shū)之四實(shí)驗(yàn)4.1構(gòu)建基于WINDOWS平臺(tái)的MPI并行集群環(huán)境實(shí)驗(yàn)?zāi)康?．掌握面向IntelMPILibrary建立Windows并行集群環(huán)境的方法;2．掌握VisualStudio*.NET*集成開(kāi)發(fā)環(huán)境開(kāi)發(fā)MPI程序配置方法；3．掌握MPI程序設(shè)計(jì)的基本編寫(xiě)、編譯與運(yùn)行方法實(shí)驗(yàn)要求1．熟練掌握C++語(yǔ)言；。2、掌握VisualStudio*.NET*集成開(kāi)發(fā)環(huán)境的使用；3、掌握MPI程序設(shè)計(jì)的基本概念。實(shí)驗(yàn)內(nèi)容實(shí)驗(yàn)步驟：一、配置電腦環(huán)境。1.基本網(wǎng)絡(luò)設(shè)置：關(guān)閉殺毒軟件、計(jì)算機(jī)防火墻，將小組里所有計(jì)算機(jī)連接到同一個(gè)交換機(jī)上，查看每臺(tái)計(jì)算機(jī)ip，使用ping命令測(cè)試，保證互相之間能夠ping通。2.網(wǎng)絡(luò)連接設(shè)置：由于需要在cluster上運(yùn)行同一個(gè)程序，為了實(shí)現(xiàn)相互之間能連接成功，要在每臺(tái)電腦上登錄同一個(gè)管理員帳號(hào)。先到計(jì)算機(jī)管理下的本地用戶(hù)和組里創(chuàng)建一個(gè)賬戶(hù)haomeng，設(shè)置密碼為haomeng，（默認(rèn)賬戶(hù)也可以，需要設(shè)置密碼）接下來(lái)將其設(shè)置成管理員帳號(hào)：進(jìn)入控制面板\用戶(hù)帳戶(hù)和家庭安全\用戶(hù)帳戶(hù)\管理帳戶(hù)\更改帳戶(hù)，將賬戶(hù)類(lèi)型修改為管理員，讓這個(gè)賬戶(hù)進(jìn)入登錄狀態(tài)(并不是一定要在這個(gè)賬戶(hù)下進(jìn)行實(shí)驗(yàn)，只需讓其進(jìn)入登錄狀態(tài))。要注意需要保證小組內(nèi)每臺(tái)電腦有相同的管理員賬戶(hù)和密碼。二、單機(jī)上編譯運(yùn)行簡(jiǎn)單的test程序1.打開(kāi)test工程2.在庫(kù)中添加C:\ProgramFiles\Intel\MPI\3.1\ia32\lib;3.將C:\ProgramFiles\Intel\MPI\3.1\ia32\lib里面的.dll文件添加到C:\WINDOWS\system32中4.使用intel編譯器編譯，生成.exe文件5．執(zhí)行smpd–installsmpd-starthydra_service–installhydra_service–startmpiexec–register設(shè)置電腦賬戶(hù)和密碼。6.使用mpiexec.exe-n<#ofprocesses>test.exe執(zhí)行命令，執(zhí)行成功的話(huà)能看到相應(yīng)的HelloWorld輸出信息。//mpiexec.exe-n1test.exe7.運(yùn)行mpi程序（共有窗口和命令行兩種方式，但本次實(shí)驗(yàn)主要使用命令行方式運(yùn)行）。Intel(R)MPI提供一個(gè)命令行工具程序mpiexec.exe，該程序幫助用戶(hù)以非常靈活的方式支持MPI應(yīng)用。本節(jié)對(duì)這個(gè)工具的使用進(jìn)行簡(jiǎn)要說(shuō)明。mpiexec的命令行常見(jiàn)格式（詳細(xì)格式可以參考mpiexec-?返回的幫助，下面格式的尖括號(hào)為解釋?zhuān)焊袷?：mpiexec-n<#ofprocesses>myprog.exe格式2：mpiexec-host<hostname>myprog.exe格式3：mpiexec-machinefile<machinefile>myprog.exe用-n設(shè)置本地機(jī)上的進(jìn)程數(shù)，myprog.exe指可執(zhí)行文件（可包含路徑），若程序還有別的命令行參數(shù)，根據(jù)需要添加到該命令行后面。用-host設(shè)置程序執(zhí)行的主機(jī)，如以下命令將會(huì)運(yùn)行可執(zhí)行文件a.exe在主機(jī)lab01上：mpiexec-hostlab01a一個(gè)machinefile是一個(gè)包含集群中所有主機(jī)名，各主機(jī)運(yùn)行進(jìn)程數(shù)等信息的列表，空行和以“#”開(kāi)頭的行都將被忽略。通過(guò)重復(fù)主機(jī)名將會(huì)在該主機(jī)上增加一個(gè)進(jìn)程，或者直接按格式：<hostname>:<numberofprocesses>.描述每個(gè)主機(jī)所包含的進(jìn)程數(shù)。如以下file1和file2是等效的。file1:file2:host1host1：2host1host2：2host2host3host2host3注：上面運(yùn)行命令作為參考。具體在運(yùn)行的時(shí)候建議通過(guò)以下兩種方式運(yùn)行：mpiexec-hosts2LAB012LAB023myporg.exe其中，hosts后的參數(shù)為主機(jī)數(shù)，后面必須跟著特定數(shù)目的主機(jī)名稱(chēng)（像這里2個(gè)主機(jī)，LAB01和LAB02）。主機(jī)后面的可選參數(shù)為該主機(jī)上運(yùn)行的進(jìn)程數(shù)目。主機(jī)名稱(chēng)可以在cmd中使用hostname命令獲得。要注意，多機(jī)運(yùn)行時(shí)每臺(tái)機(jī)器上的.exe文件必須放到相同的目錄下。8.編譯并運(yùn)行test程序，成功后記錄結(jié)果并進(jìn)行檢查：mpiexec-n<#ofprocesses>d:\test.exe9．除了使用wmpiexec窗口程序運(yùn)行mpi程序，還可以使用BuildEnvironmentforIntel(R)ClusterToolkit3.1命令行運(yùn)行。要求嘗試多種命令形式，如：mpiexec-hosts4LAB012LAB022LAB032LAB043d:\test.exe//mpiexec-hosts2192.168.xx.xx2192.168.xx.xx2d:\test.exe等等。實(shí)驗(yàn)4.2N體問(wèn)題MPI并行程序剖析與性能分析實(shí)驗(yàn)?zāi)康?．掌握MPI程序設(shè)計(jì)的基本編寫(xiě)、編譯與運(yùn)行方法;2．掌握Window群機(jī)環(huán)境下N體問(wèn)題的并行程序設(shè)計(jì)方法；3．掌握利用加速比、運(yùn)行時(shí)間、效率等測(cè)度分析并行程序性能實(shí)驗(yàn)要求1．熟練掌握C++語(yǔ)言；。2、掌握VisualStudio*.NET*集成開(kāi)發(fā)環(huán)境的使用；3、掌握MPI程序設(shè)計(jì)的基本概念。實(shí)驗(yàn)原理N體問(wèn)題是研究物體之間相互作用力產(chǎn)生的效果的問(wèn)題（例如天體間通過(guò)引力相互吸引）。這個(gè)問(wèn)題的目標(biāo)是確定太空中通過(guò)引力相互作用的天體的位置和運(yùn)動(dòng)，涉及到的物理知識(shí)是牛頓定律。質(zhì)量為ma和mb的兩個(gè)物體相互間的引力由下式給出：其中G是引力常數(shù)，r是物體間的距離。每個(gè)物體都會(huì)依據(jù)這個(gè)定律受其它物體的影響，所有力都會(huì)被累加（要考慮每個(gè)力的方向）。在受力的情況下，一個(gè)物體將根據(jù)牛頓第二定律加速：其中m是物體質(zhì)量，F(xiàn)是物體所受的力，a是得到的加速度。因此所有物體都會(huì)由于這些力的作用移動(dòng)到新的位置并獲得新的速度。要得到精確的數(shù)值描述，需要使用微分方程。然而，對(duì)于超過(guò)三個(gè)物體的系統(tǒng)的N體問(wèn)題還沒(méi)有確切的近似解。使用計(jì)算機(jī)仿真時(shí)，我們使用特定時(shí)間的值，t0，t1，t2等等，時(shí)間間隔取得盡可能短以獲得最精確的解。不妨設(shè)時(shí)間間隔為△t，則對(duì)于一個(gè)質(zhì)量為m的特定物體，其所受力為：新的速度為：其中vt+1為物體在時(shí)刻t+1的速度，vt為物體在時(shí)刻t的速度。如果物體以速度v移動(dòng)了△t時(shí)間，則位置變化為：其中xt為物體在時(shí)刻t的位置。一旦物體移動(dòng)到新的位置，所受的力就會(huì)發(fā)生變化，計(jì)算過(guò)程也要重復(fù)。在一個(gè)時(shí)間間隔△t內(nèi)的速度實(shí)際上并不是一個(gè)準(zhǔn)確的常數(shù)，因此得到的僅是一個(gè)近似解。要注意以上所涉及的力F，位置x和速度v都是向量。在進(jìn)行計(jì)算時(shí)必須被分解為三個(gè)方向。N體問(wèn)題的串行算法研究：總的引力N體算法可以由以下算法描述：for(t=0;t<tmax;t++){/*foreachtimeperiod*/for(i=0;i<n;i++){/*foreachbody*/F=Force_routine(i);/*computeforceonithbody*/v[i]new=v[i]+F*dt/m;/*computenewvelocityand*/x[i]new=x[i]+v[i]new*dt;/*newposition*/}for(i=0;i<n;i++){/*foreachbody*/x[i]=x[i]new;/*updatevelocityandposition*/v[i]=v[i]new;}}外層的for循環(huán)計(jì)算每一個(gè)時(shí)間步，在每個(gè)時(shí)間步內(nèi)n個(gè)物體更新了速度和位置。內(nèi)層的兩個(gè)for循環(huán)計(jì)算每一個(gè)物體所受到的力及其新的位置和速度。內(nèi)層第一個(gè)for循環(huán)內(nèi)的函數(shù)Force_routine(i)計(jì)算其它所有物體作用于第i個(gè)物體的引力之和，它的時(shí)間復(fù)雜性是O(n)。因此在這個(gè)算法中n個(gè)物體更新一次時(shí)間復(fù)雜性是O（n2）。N體問(wèn)題的并行實(shí)現(xiàn)：這個(gè)算法使用SPMD（單程序多數(shù)據(jù)流）計(jì)算模型，每個(gè)進(jìn)程將執(zhí)行相同的代碼。假設(shè)有m個(gè)計(jì)算資源，每個(gè)資源上啟動(dòng)一個(gè)進(jìn)程，表示進(jìn)程的標(biāo)號(hào)是0、1、2、……m-1，每個(gè)進(jìn)程分配的物體數(shù)是n0、n1、n2、……n(m-1)，其中n0+n1+n2+……+n(m-1)=n。每個(gè)進(jìn)程主要有兩個(gè)數(shù)組localparticles、allparticles、sendbuf、recvbuf，其中l(wèi)ocalparticles用于保存分配給本進(jìn)程的物體的信息；allparticles用于保存應(yīng)用程序中所有物體的信息；sendbuf用于保存發(fā)送到下一個(gè)進(jìn)程的物體；recv用于保存從前一個(gè)進(jìn)程接受的物體。算法描述獲取分配給本進(jìn)程的物體的初始信息localparticles獲取應(yīng)用程序中所有物體的信息allparticlesfor(每一個(gè)時(shí)間步){計(jì)算所有物體對(duì)分配給本進(jìn)程的物體的作用力并據(jù)此更新localparticles的本進(jìn)程的物體的信息將本進(jìn)程信息localparticles保存到發(fā)送緩沖區(qū)sendbuffor(i=0;i<m-1;i++)//對(duì)每個(gè)進(jìn)程{sendsendbufto本進(jìn)程的下一個(gè)進(jìn)程；用sendbuf中的信息更新allparticles中的部分信息；recvrecvbuffrom本進(jìn)程的前一個(gè)進(jìn)程；}使所有進(jìn)程在此處同步}算法中外層for循環(huán)計(jì)算每一個(gè)時(shí)間步，在每個(gè)時(shí)間步內(nèi)所有參與的進(jìn)程并行執(zhí)行，所有進(jìn)程都結(jié)束時(shí)所有n個(gè)物體速度和位置都被更新了。在外層for的循環(huán)體內(nèi)，首先計(jì)算所有物體對(duì)本地物體的作用力，據(jù)此更新關(guān)于本地物體的信息；內(nèi)層for循環(huán)使得每個(gè)進(jìn)程都獲得了所有物體的更新后的信息，實(shí)現(xiàn)了進(jìn)程之間的合作，為下一次迭代做好準(zhǔn)備；最后通過(guò)顯示設(shè)置柵欄使所有進(jìn)程同步。加速比和效率加速比和效率是最傳統(tǒng)的并行算法評(píng)價(jià)標(biāo)準(zhǔn)，它們體現(xiàn)了在并行機(jī)上運(yùn)用并行算法求解實(shí)際問(wèn)題所能獲得的好處。并行算法的加速比定義為:Sp=Ti/TpTi表示最優(yōu)串行算法在單處理機(jī)上的運(yùn)行時(shí)間，Tp表示p臺(tái)處理機(jī)的計(jì)算時(shí)間。并行算法的效率定義為:Ep=Sp/PP為處理機(jī)臺(tái)數(shù)。如果按照某種條件，如保持每臺(tái)處理機(jī)的計(jì)算規(guī)模，并行算法加速比與處理機(jī)的臺(tái)數(shù)成正比，則稱(chēng)該并行算法在該條件下，在該并行機(jī)上具有線(xiàn)性加速比實(shí)驗(yàn)內(nèi)容1.在VS中打開(kāi)nbody工程，配置好MPI運(yùn)行環(huán)境，編譯并運(yùn)行項(xiàng)目；2.進(jìn)行如下實(shí)驗(yàn)并記錄數(shù)據(jù)（實(shí)驗(yàn)報(bào)告中給出數(shù)據(jù)并繪圖）實(shí)驗(yàn)一：?jiǎn)螜C(jī)上，數(shù)據(jù)規(guī)模為4000時(shí)，隨每機(jī)進(jìn)程數(shù)變化的運(yùn)行時(shí)間；進(jìn)程數(shù)12345時(shí)間1.3485941.0802150.9986610.6720420.815603實(shí)驗(yàn)二：相同數(shù)據(jù)規(guī)模為4000，隨每機(jī)進(jìn)程數(shù)變化的運(yùn)行時(shí)間每機(jī)進(jìn)程數(shù)單機(jī)雙機(jī)三機(jī)四機(jī)11.3485940.6813210.6338900.44366221.0802150.3773660.3066290.23207830.9986610.4618960.3972140.30591640.6720420.5015730.4606100.468220實(shí)驗(yàn)三：每機(jī)1個(gè)進(jìn)程，隨數(shù)據(jù)規(guī)模變化的n-body并行程序運(yùn)行時(shí)間。粒子數(shù)n單機(jī)雙機(jī)三機(jī)四機(jī)100.0000180.0002140.0022470.003273500.0003230.0043210.0049630.0007011000.0008770.0023470.0024750.0025475000.0213020.0147560.0132460.00814210000.0836580.0412250.0411720.03241520000.3325860.1954210.1475230.11472330000.7541070.4014730.3653110.22714240001.3314600.7132880.6210470.4153673.根據(jù)記錄的數(shù)據(jù)計(jì)算加速比與效率（給出數(shù)據(jù)并繪圖）實(shí)驗(yàn)一：?jiǎn)螜C(jī)上，粒子數(shù)為4000，隨進(jìn)程數(shù)變化加速比（Sp）統(tǒng)計(jì)進(jìn)程數(shù)2345678910加速比1.251.352.011.652.121.962.202.312.25實(shí)驗(yàn)二：粒子數(shù)為4000，隨每機(jī)進(jìn)程數(shù)變化的加速比每機(jī)進(jìn)程數(shù)雙機(jī)三機(jī)四機(jī)422.863.524.6532.162.513.2641.341.461.44實(shí)驗(yàn)三：每機(jī)1個(gè)進(jìn)程，隨數(shù)據(jù)規(guī)模變化的n-body并行程序加速比和效率n-body并行算法的加速比（Sp）統(tǒng)計(jì)表粒子數(shù)n雙機(jī)三機(jī)四機(jī)100.0841120.0080100.005499500.0747510.0650810.4607701000.3736680.3543430.3443265001.4436161.6081832.61631010002.0293022.0319142.58084220001.7018942.2544682.89903530001.