LecNote_9_并行計算中的任務分配

1、第九講 并行計算中的任務分配n任務分配方法n靜態(tài)任務分配n動態(tài)任務分配n動態(tài)任務分配的實現(xiàn)n對等協(xié)同：peer-to-peer collaboratingn集中調度：master-slavenPOSIX并行程序中的計算任務劃分n對等協(xié)同n鎖n信號量nCELL BE上的計算任務劃分n集中調度n郵箱nDMA數(shù)據(jù)傳輸并行算法設計：BSP與PCAMnBSP：子任務在時間和空間上的規(guī)劃n時間上的規(guī)劃：整個算法由若干個串行執(zhí)行的superstep組成n空間上的規(guī)劃：每個superstep上包含一組互相獨立的子任務nPCAM：發(fā)現(xiàn)問題中的子任務、產(chǎn)生規(guī)劃的方法nP：通過功能分解、數(shù)據(jù)分解，尋找并行性。解決兩

2、方面的問題n并行程序的伸縮性n并行計算任務劃分的負載均衡性nC：檢查子任務間的依賴關系，發(fā)現(xiàn)規(guī)劃必須滿足的約束條件nA：選擇合適的子任務粒度，減小并行計算的額外開銷n子任務分配開銷n子任務間的通信開銷n子任務間的同步開銷nM：將子任務組織成若干個superstep并行計算中的任務分配方法n并行算法設計的結果: BSP模型n若干個順序執(zhí)行的superstepn每個superstep上是一組互相獨立的子任務n這些子任務是通過功能分解功能分解發(fā)現(xiàn)的：子任務的數(shù)量有限、與被處理數(shù)據(jù)的規(guī)模無關n這些子任務是通過數(shù)據(jù)分解數(shù)據(jù)分解發(fā)現(xiàn)的：被處理的數(shù)據(jù)規(guī)模越大，子任務的數(shù)量越多n在每個superstep上，如

3、何確定各個處理器/執(zhí)行內核上的子任務n靜態(tài)任務分配：在開始superstep上的數(shù)據(jù)處理之前，已經(jīng)確定了需要執(zhí)行其中的哪些子任務n例如N-Body問題的實現(xiàn)n動態(tài)任務分配：superstep的數(shù)據(jù)處理過程中，動態(tài)確定每個處理器/執(zhí)行內核上的子任務。n例如求素數(shù)問題靜態(tài)任務分配：通過功能分解得到superstep上的一組子任務n每個子任務分別實現(xiàn)一個子功能，子任務的數(shù)量有限n一個處理器/執(zhí)行內核負責一個子任務n并行程序伸縮性(scalability)不好n負載均衡難以控制：取決于子任務算法的復雜性、所涉及的數(shù)據(jù)規(guī)模等n子任務之間的關系n形式1：互相獨立，各自處理不同的數(shù)據(jù)集合n形式2：構成一個流

4、水，依次對一組數(shù)據(jù)集合進行處理。數(shù)據(jù)集合的數(shù)量很大子任務1子任務2子任務3子任務4數(shù)據(jù)集合1數(shù)據(jù)集合2數(shù)據(jù)集合3數(shù)據(jù)集合4數(shù)據(jù)集合數(shù)據(jù)集合1 1數(shù)據(jù)集合數(shù)據(jù)集合1 1數(shù)據(jù)集合數(shù)據(jù)集合2 2數(shù)據(jù)集合數(shù)據(jù)集合2 2數(shù)據(jù)集合數(shù)據(jù)集合3 3數(shù)據(jù)集合數(shù)據(jù)集合3 3數(shù)據(jù)集合數(shù)據(jù)集合4 4數(shù)據(jù)集合數(shù)據(jù)集合5 5數(shù)據(jù)集合數(shù)據(jù)集合4 4數(shù)據(jù)集合數(shù)據(jù)集合1 1數(shù)據(jù)集合數(shù)據(jù)集合2 2數(shù)據(jù)集合數(shù)據(jù)集合3 3數(shù)據(jù)集合數(shù)據(jù)集合1 1數(shù)據(jù)集合數(shù)據(jù)集合2 2子任務的計算復雜性形式1的數(shù)據(jù)劃分形式2的數(shù)據(jù)劃分靜態(tài)任務分配：通過數(shù)據(jù)分解得到superstep上的一組子任務n各個子任務的數(shù)據(jù)處理功能相同，各自處理不同的數(shù)據(jù)集合n子

5、任務之間互相獨立n子任務的數(shù)量大n一個處理器/執(zhí)行內核在開始superstep上的數(shù)據(jù)處理之前，先確定需要處理其中哪些子任務n并行程序有好的伸縮性(scalability)n負載均衡問題n子任務具有相同的運算量、且處理器/執(zhí)行內核的性能相同，具有好的負載均衡性n例如在Intel多核處理器上執(zhí)行Laplace計算n子任務的運算量不一致、或者處理器/執(zhí)行內核的性能不一致時，難以控制負載均衡。例如n在Intel多核處理器上執(zhí)行求素數(shù)計算n在CELL處理器上執(zhí)行Laplace計算，讓PPE和8個SPE分別負責一部分數(shù)據(jù)處理靜態(tài)任務分配在POSIX線程并行程序中的實現(xiàn)nsuperstep上的子任務是通過

6、功能分解發(fā)現(xiàn)的：每個子任務分別處理不同的數(shù)據(jù)集合n為每個子任務各編寫一個函數(shù)，分別由一個并發(fā)線程執(zhí)行nsuperstep上的子任務是通過功能分解發(fā)現(xiàn)：每個數(shù)據(jù)集合要經(jīng)過這些子任務依次處理流水并行流水并行n每個子任務分別開發(fā)一個函數(shù)，各由一個線程執(zhí)行n子任務之間通過條件信號進行同步nsuperstep上的子任務是通過數(shù)據(jù)分解發(fā)現(xiàn)的：數(shù)據(jù)并行數(shù)據(jù)并行子任務的數(shù)量確定、子任務的復雜性一致n編寫一個函數(shù)n根據(jù)并發(fā)線程的數(shù)量和自己的ID，計算自己負責哪些子任務n實現(xiàn)子任務的數(shù)據(jù)處理功能n創(chuàng)建多個并發(fā)線程，同時執(zhí)行這個函數(shù)動態(tài)任務分配n動態(tài)任務分配：處理器/執(zhí)行內核完成一個子任務后，再分配一個新的子任務n

7、什么樣的并行子任務能夠動態(tài)分配動態(tài)分配？基于數(shù)據(jù)分解發(fā)現(xiàn)的子任務基于數(shù)據(jù)分解發(fā)現(xiàn)的子任務n各個處理器/執(zhí)行內核運行的算法要相同：都能實現(xiàn)子任務需要的數(shù)據(jù)處理功能n子任務要互相獨立，分別處理不同的數(shù)據(jù)集合n為什么需要動態(tài)任務分配動態(tài)任務分配？平衡負載平衡負載n子任務的計算量不一致。例如求素數(shù)問題n處理器/執(zhí)行內核的性能不一致。例如：在CELL處理器上，讓PPE和8個SPE分別負責一部分子任務的處理n子任務的數(shù)量不確定。例如n圖書館查詢、銀行記帳等大規(guī)模并發(fā)用戶的計算問題n處理一個數(shù)據(jù)文件中的記錄，每個記錄作為一個子任務分別處理。各個記錄不定長，讀到文件末尾才知道總的記錄數(shù)。例如：一個稀疏矩陣與向

8、量的乘法運算，部分行中全部是0元素。稀疏矩陣按照行優(yōu)先存儲在文件中NiC1 Val1C2 Val2C2 Val3Cni ValniNi+1第I行非0元素的數(shù)量第I行第2個非0元素所在的列號第I行第2個非0元素的值第I+1行非0元素的數(shù)量動態(tài)任務分配的實現(xiàn)n可以將整個superstep看做一個“子任務池”( pool)n每次從“子任務池”中取一個出來，交給當前空閑的某個處理器/執(zhí)行內核去執(zhí)行n實現(xiàn)方式1：對等協(xié)同的(peer-to-peer collaborating)動態(tài)任務分配n全部處理器/執(zhí)行內核扮演的角色都是相同角色都是相同的n負責處理“子任務池”中若干個子任務n與其他處理器/執(zhí)行內核協(xié)

9、作，實現(xiàn)“子任務池”中子任務的分配n采用“鎖”機制實現(xiàn)“子任務池”操作的確定性n任何時刻，只有一個處理器/執(zhí)行內核操作“子任務池”n例如求素數(shù)問題的pthread并行程序n實現(xiàn)方式2：集中調度的(master-slave)動態(tài)任務分配n各處理器扮演不同的角色不同的角色：一個處理器/執(zhí)行內核(master)專門負責“子任務池”的維護，其他處理器/執(zhí)行內核(slave)負責子任務的數(shù)據(jù)處理nmaster和slave采用“消息交換”機制實現(xiàn)子任務的分配n當一個slave空閑時，通過消息告訴masternmaster從“子任務池”中取出一個任務，通過消息通知slave執(zhí)行該子任務POSIX并行程序中的

10、動態(tài)任務分配nsuperstep是數(shù)據(jù)并行的：子任務的數(shù)量不確定、或者子任務的復雜性不一致npeer-to-peer collaborating的動態(tài)任務劃分n開發(fā)一個函數(shù)，同時由各個并發(fā)線程分別執(zhí)行n鎖機制，實現(xiàn)線程之間對“子任務池”操作的同步CELL處理器上的計算任務分配nPCAM：將問題表示成若干個superstepn四類superstepn只有一個子任務：PPE做、還是SPE做？n流水并行nMailbox：子任務間的同步nDMA：子任務間的數(shù)據(jù)交換n數(shù)據(jù)并行，子任務的數(shù)量確定、子任務的復雜性一致：還能靜態(tài)任務劃分嗎？還能靜態(tài)任務劃分嗎？n數(shù)據(jù)并行，但子任務的數(shù)量不確定、或者子任務的復雜

11、性不一致：master-slave的動態(tài)任務劃分n無論是流水并行、還是數(shù)據(jù)并行，無論是流水并行、還是數(shù)據(jù)并行，PPE扮演什么樣的角扮演什么樣的角色？色？Cell programming modelsnSingle Cell environment:nPPE programming modelsnSPE Programming modelsnSmall single-SPE modelsnLarge single-SPE modelsnMulti-SPE parallel programming modelsnCell Embedded SPE Object Format (CESOF)nMul

12、ti-tasking SPEsnLocal Store resident multi-taskingnSelf-managed multi-taskingnKernel-managed SPE scheduling and virtualizationPPE programming modelnPPE is a 64-bit PowerPC core, hosting operating systems and hypervisornPPE program inherits traditional programming modelsnCell environment: a PPE progr

13、am serves as a controller or facilitatornCESOF support provides SPE image handles to the PPE runtimenPPE program establishes a runtime environment for SPE programsn e.g. memory mapping, exception handling, SPE run controlnIt allocates and manages Cell system resourcesn SPE scheduling, hypervisor CBE

14、A resource managementnIt provides OS services to SPE programs and threadsn e.g. printf, file I/OSmall single-SPE modelsnSingle tasked environmentnSmall enough to fit into a 256KB- local storenSufficient for many dedicated workloadsnSeparated SPE and PPE address spaces LS / EAnExplicit input and outp

15、ut of the SPE programnProgram arguments and exit code per SPE ABI (application binary interface)nDMAnMailboxesnSPE side system callsSmall single-SPE models tools and environmentnSPE compiler/linker compiles and links an SPE executablenThe SPE executable image is embedded as reference-able RO data in

16、 the PPE executable (CESOF)nA Cell programmer controls an SPE program via a PPE controlling process and its SPE management libraryni.e. loads, initializes, starts/stops an SPE programnThe PPE controlling process, OS/PPE, and runtime/(PPE or SPE) together establish the SPE runtime environment, e.g. a

17、rgument passing, memory mapping, system call service.outputSmall single-SPE models a sample/* spe_foo.c: A C program to be compiled into an executable called “spe_foo” */int main( int speid, addr64 argp, addr64 envp) char i;/* do something intelligent here */i = func_foo (argp);/* when the syscall i

18、s supported */printf( “Hello world! my result is %d n”, i);return i;nABI: application binary interfaceABISmall single-SPE models PPE controlling programextern spe_program_handle spe_foo; /* the spe image handle from CESOF */int main() int rc, status;speid_t spe_id;/* load & start the spe_foo pro

19、gram on an allocated spe */spe_id = spe_create_thread (0, &spe_foo, 0, NULL, -1, 0);/* wait for spe prog. to complete and return final status */rc = spe_wait (spe_id, &status, 0);return status;Large single-SPE programming modelsnData or code working set cannot fit completely into a local sto

20、renThe PPE controlling process, kernel, and libspe runtime set up the system memory mapping as SPEs secondary memory storenThe SPE program accesses the secondary memory store via its software-controlled SPE DMA enginenMemory Flow Controller (MFC)Large single-SPE programming models I/O datanSystem me

21、mory for large size input / output datane.g. Streaming modelLarge single-SPE programming models - DMAnDMA latency handling is critical to overall performance for SPE programs moving large data or codenData pre-fetching is a key technique to hide DMA latencyne.g. double-bufferingn在此策略下，SPE上每個子任務的數(shù)據(jù)規(guī)模

22、要更小Large single-SPE programming models Job QueuenCode and data packaged together as inputs to an SPE kernel programnA multi-tasking modelnmore discussion laterCELL上的計算任務劃分：superstep上只有一個子任務nPPE控制：決定何時開始子任務的執(zhí)行n與上、下的superstep同步nSPE做子任務的數(shù)據(jù)處理n子任務足夠“小”：數(shù)據(jù)+代碼256KBn代碼不可拆、數(shù)據(jù)可拆：流計算模式(streaming model) nLarge

23、single-SPE programming models I/O datan開發(fā)一個SPE程序：取一部分數(shù)據(jù)，做完后回寫結果，再取一部分數(shù)據(jù)n可采用雙緩沖技術，降低DMA延遲對性能的影響n代碼和數(shù)據(jù)要同時拆nLarge single-SPE programming models Job Queuen開發(fā)多個SPE程序，構成一個SPE的執(zhí)行隊列n執(zhí)行完一個SPE程序后，在執(zhí)行另一個SPE程序Multi-tasking：站在PPE的角度，如何看SPEsnSPE as a device resourcenSPE as a heterogeneous processornSPE resource r

24、epresented as a file systemnPPE按照Function offloading模式，利用SPE提高計算效率nPPE維護一個子任務池，通過CESOF機制，建立每個子任務與SPE程序的對應關系n需要執(zhí)行子任務池中的某個子任務時，通過SPE Management Runtime Libraryn分配一個SPU、啟動SPE程序運行nPPE和SPE之間通過MFC通信nMailbox：同步、任務描述數(shù)據(jù)nDMA：任務數(shù)據(jù)到LS的數(shù)據(jù)傳輸Parallel programming models StreamingnSPE initiated DMAnLarge array of da

25、ta fed through a group of SPE programsnA special case of job queue with regular datanEach SPE program locks on the shared job queue to obtain next jobnFor uneven jobs, workloads are self-balanced among available SPEsCELL上的計算任務劃分：基于數(shù)據(jù)分解發(fā)現(xiàn)superstep上的子任務n動態(tài)任務分配n無所謂靜態(tài)任務分配，SPE只有256KBn開發(fā)一個SPE程序，在各個SPU上運行n

26、PPE通過Mailboxn分派SPE需要執(zhí)行的子任務：輸入數(shù)據(jù)、輸出數(shù)據(jù)的EAn獲得子任務的執(zhí)行進度：一個子任務完成后，再分配一個新的子任務nSPE/PPE通過DMAn將子任務處理的數(shù)據(jù)傳輸?shù)絃Sn將子任務的結果從LS傳輸?shù)組emoryParallel programming models PipelinenUse LS to LS DMA bandwidth, not system memory bandwidthnFlexibility in connecting pipeline functionsnLarger collective code size per pipelinenLoa

27、d-balance is harderCELL上的計算任務劃分：流水并行的superstepn為每個子任務，分別開發(fā)一個SPE程序，運行在一個SPU上nPPE通過Mailboxn向其中一個SPE分派需要處理的數(shù)據(jù)集合：輸入數(shù)據(jù)、輸出數(shù)據(jù)的EAn獲得數(shù)據(jù)集合在該SPE上的執(zhí)行進度：一數(shù)據(jù)集合完成后，再分配一個新的數(shù)據(jù)集合nSPE之間n通過DMA：將上一個子任務的結果傳遞到下一個子任務所在的LSn通過Mailbox：實現(xiàn)SPE之間的進度同步CELL處理器：PCAMnP：通過功能分解、數(shù)據(jù)分解，尋找并行性。解決三方面的問題n并行程序的伸縮性n并行計算任務劃分的負載均衡性n每個子任務足夠“小”：數(shù)據(jù)+

28、代碼256KBnC：檢查子任務間的依賴關系，發(fā)現(xiàn)規(guī)劃必須滿足的約束條件nA：選擇合適的子任務粒度，減小并行計算的額外開銷：合并后的子任務必須足夠“小”n子任務分配開銷n子任務間的通信開銷n子任務間的同步開銷nM：將子任務組織成若干個superstepn在相鄰的superstep上，如果都只有一個子任務，不要輕易將他們合并成一個superstep：每個子任務要足夠“小”CELL處理器：并行計算的實現(xiàn)n總有一個Master：PPEn每個superstep至少一個slavensuperstep上的所有子任務都由slave執(zhí)行nslave是運行在SPU上的SPE程序n可以有多個slaven流水并行時，

29、各個slave分別運行不同的SPE程序n數(shù)據(jù)并行時，各個slave運行相同的SPE程序n并行程序：CESOFn一個PPE程序n多個SPE程序nSPE程序被嵌在PPE程序中并行計算機體系結構對并行程序開發(fā)的影響n從PCAM看，針對Intel多核處理器和IBM CELL處理器，并行算法的設計結果是不同的n靠編譯技術實現(xiàn)串行程序的自動并行化成了一個不可能實現(xiàn)的夢想n從并行程序中數(shù)據(jù)并行的計算任務分配方法看nIntel多核處理器采用對等協(xié)作的計算模式nIBM CELL處理器采用集中調度的計算模式n從并行程序中對處理器/執(zhí)行內核資源的管理方法看nIntel多核處理器采用POSIX線程庫管理處理器/執(zhí)行內核資源，實現(xiàn)子任務到處理器/執(zhí)行內核資源的分配nIBM CELL處理器采用SPE Management runtime library管理處理器/執(zhí)行內核資源，實現(xiàn)子任務到處理器/執(zhí)行內核資源的分配不同并行計算機體系結構下的并行程序開發(fā)為什么會有這么大的差別？n串行編程時，為Power PC寫的C語言程序可以直接在X8