2009第二屆一階段優(yōu)秀1176隊(duì)題

2009年第二屆“數(shù)學(xué)中國杯” 關(guān)鍵 數(shù)據(jù)相關(guān)控制相關(guān)依賴方向向量仿真測試負(fù)載平 基本結(jié)構(gòu)順序、分支、循環(huán)進(jìn)行分析，探究它們可并發(fā)執(zhí)行的判據(jù)，并把可并發(fā)的程序段的計(jì)算量，運(yùn)用0－1規(guī)劃，分配到兩個(gè)處理器上。環(huán)結(jié)構(gòu)中各層循環(huán)是否可并行化的判據(jù)，并推導(dǎo)出了循環(huán)結(jié)構(gòu)的計(jì)算量。（填寫（填寫 Intransformingaserialalgorithmintoaparallelstructure,weneedtocheckthevalidityofngsoinadvance.Wediscussthecriterionofitthroughyzingthreestructuresofaregularserialprogram:sequence,embranentandcycle.Wedevelopadescriptivemodelanduseitintoseparatingandtransformingtheserialpartintotheparallelform.Finally,weputforwardanequationtoestimatethecalculatingtimeofeachCPU,applyittogettheresultanduse0-1layouttodistributedifferenttasksintotwoCPUs.Thereasonoffailureofparallelingexecutingtwoprogramsentencesismainlybecausetheyvisitthesamememoryunitforreadingorwritingadata.Thentheypossessthedatadependence.WeturntoBernsteinCriteriontojudgethedatadependenceoftwosentences.Thenwedeviseasimplemethodtoparallelaserialstructure.Theexecutionofeverybranchofanembranentstructurereliesonthetestresultofthefunctionif(),itiscalledcontroldependence.Twosentencescouldbeparallelingexecutediftheydon’thavecontrolreliedrelativity.Inbenefitforintuitionisticjudgment,weintroducecontroldependencegraphbasedonthetheoryofgraphs.Onlyiftwosentencesaredataindependentandcontrolindependentcanthembeparallelingexecuted.Asforcyclestructure,wedefinerelydirectionvectoranddevelopacriterionbasedonthevalueofthisrelydirectionvector.Thetotalcalculatingtimemainlydependsonthemcalculatingtimeofthecyclepartofaprogram,thusweillustrateanequationLQ(Ni)atwhichQisthecalculatingtyofthecyclepartandlayerofthecircular

istheupperlimitoftheUptonow,wehavegotseveralpiecesofprogramtobeparallelingexecuted.AssumetheyhavethecalculatingtyL1,L2,...,Lnrespectively.TheremainproblemistoassignthemtotwoCPUsandttrytoletthesetwoCPUshavethesamecalculatingty,avoidingthatoneCPUisbutincontrasttheotherisbusytodeath.Thus,weapply0-1layouttoobtainthebestallottingscheme.Lastbutnottheleast,wecarryoutcomputersimulationtesttowardstheabovethreearithmeticandcometothefinalconclusion.Toparallelasimplesequencestructurewillnotmakeabigdifferenceintheprogramexecutingtime.Infact,itismainlybecausethisarithmeticforsequencestructurehasgoodeffectsonsomeregularcode,butisratherdifficultinguaranteeingthebalanceofloadtowardscomplexanderraticcode.Theeffectofparallelinganif-elsestructuredepends.Itwillhaveawesomeresultonsometasksthatcouldbeeasilyparalleled.The eofparallelingacyclestructurecouldbethebestbecauseitsavesalmosthalfthetimeoftheregularserialexecutingprocess.一、問題重CPU資源，因此速度快、實(shí)時(shí)性好，在現(xiàn)代科學(xué)計(jì)算中優(yōu)勢 C語句，循環(huán)語句（while語句。不包括其他語句。二、題分Ax=a+bB“y=c+dCPU上按順序1兩個(gè)CPU來分別處理。相當(dāng)于可以建立兩個(gè)隊(duì)列，存放兩個(gè)CPU所要處理的代碼。當(dāng)兩S:if（i==0T：j=a+b；T可能執(zhí)行也可能不執(zhí)行，取決于語句S的即語句T控制依賴于語句S當(dāng)判斷兩個(gè)語句沒有控制依賴性時(shí)，就可數(shù)值特征判定某層循環(huán)是否可以并行化（這一部分要涉及一些新的概念，因此結(jié)構(gòu)。對一個(gè)串行程序并行化處理之后，應(yīng)該盡量使兩個(gè)的運(yùn)算量相當(dāng)，兩個(gè)核心的計(jì)算量應(yīng)該接近總的可并行的計(jì)算量的一半。才能使負(fù)載均衡，不讓其中一個(gè)CPU空閑等著。三、模型假假設(shè)程序中只有簡單的代數(shù)運(yùn)算，賦值運(yùn)算，條件分支語句ifelse語句），循環(huán)語句（while語句）。2四、模型建入的單元集。如：P:x=y+1;那么I(P)={y},O(P)={x}。P1P2P1、P2的數(shù)據(jù)不相關(guān)，可以并行執(zhí)行。兩個(gè)程序段能夠并行執(zhí)行的根本原因就在于它們所的單元不同，不會(huì)彼此P1P2的輸出變量集不相交，表某個(gè)輸入的單元就是P2的輸出寫入的單元。此時(shí)如果P1、P2順序顛倒執(zhí)行的話，那么P2先將運(yùn)算結(jié)果存入共同的單元中，而再運(yùn)行P1時(shí)從此單元讀入的數(shù)同理可分析條件2和3。當(dāng)這三個(gè)條件同時(shí)滿足時(shí)，P1和P2的單元沒有任何先建立兩個(gè)隊(duì)列A和B,CPU的執(zhí)行語句。在理想情況下，程序具（P1，P2…Pn3AS3:C=B+1S4:D=A+1S5:if-else結(jié)構(gòu)（即if-else中不再嵌套if-else，不能也沒有必要對它進(jìn)行并4if-else結(jié)構(gòu)進(jìn)行討論。在這種復(fù)雜的情況下，可以在編譯原理XYYX的后必經(jīng)YPDOMX，若YPDOMX且XYYX的嚴(yán)格后必經(jīng)結(jié)點(diǎn)，記作YSPDOMX。當(dāng)YSPDOMX∧（W|WSPDOMX）[WPDOMX]時(shí)稱YX的緊密后必YIPDOMX?？梢园裀DOM看作CFG可用PDOM樹表示以這種關(guān)系。記為X△Y：Y是X從X從XYY是XY不是X的緊密后必經(jīng)結(jié)點(diǎn)X到Ｙ的邊為Ｘl控制依賴于X的所有結(jié)點(diǎn)。 Y=IPDOM（Xelseifgotoelse5（CDG：ａｂｃａｂｃｄＦｅｆＴｇｈｉｊｊａｉｃｂｈｇｅｆｄＰＤＯＭ6引起控制關(guān)系的CFG控制關(guān)a△Tb,a△Tcc△Td,c△Tg,c△Th,g△Td,7各自之間又沒有連線，表明它們彼此不控制依賴。因此，我們可以根據(jù)CDG圖，判斷出不其帶標(biāo)記的控制依賴關(guān)系圖（CDG。4.1.3思m

m的元素iiii是維數(shù)m的整向量 1 定義符號函數(shù)sign(x) sign(x) ii1i2im)sign(i)sign(i)(sign(i1sign(i2sign(im設(shè)ii1i2imjj1j2jm，向量ij當(dāng)且僅當(dāng)存在整數(shù)l(1lmi1j1,i2j2,...,il1jl1,il12...l10,l1,l1...m這里*1，0或－1FORi=2TON /*方便描述起見，用[S]表示該語句的序號為 /*方便描述起見，用[T]表示該語句的序號為T*/8(S(i),T(j)):ji1,1iNFORi1=0TO100FORi2=0TO100FORi3=0TO100 Af1if2if3iA[g1ig2ig3 /*A是三維數(shù)組其中ii1i2i3figi(1i3)均是線性整數(shù)函數(shù)。當(dāng)i1i2i3S，稱S的一個(gè)實(shí)例，記為Si)。x在S(i)中與y在T(j)中為同一單元程序串行執(zhí)行時(shí)，S(i)先于T(j)而執(zhí)S(i)先執(zhí)行結(jié)束到T(j)開始執(zhí)行前，沒有對M的寫操作S和TmS(i)T(j)S和T的實(shí)例(ij是m個(gè)循環(huán)變量組成的m維整數(shù)向量)，若T(j)的執(zhí)行依賴于S(i)（T(j)只能S(i)之后執(zhí)行dji,sign(d，稱向量是依賴方向向量。FORi=0TO5FORj=0TO4 這是一個(gè)2層循環(huán)，它的實(shí)例可以表示成S(i1,j1),S(i2,j2)，則有i2i11,j2 （1，1 9j1證明：假若依賴方向向量0（在一層循環(huán)中是標(biāo)量），則循環(huán)體中必有形如A(ikA(id（其中kd任意）A的第ik個(gè)單元的計(jì)算要依賴于第i個(gè)單元的結(jié)果，顯然這個(gè)循環(huán)不能并發(fā)執(zhí)行。循環(huán)嵌套LL1L2Lm)中的第l層循環(huán)Ll可以并行化的條件是：不存在12l10l1l1,...,m任意的方向向量【1定第l層循環(huán)Ll是否可以并行化。L1：FORi=2TONL2：FORj=2TOMA(i,j)=A(i, A(i,j+1)=2*A(i,j)L1并發(fā)的條件：不存在（1，*）的依賴方向向量。 因此，L1可以并發(fā)，L2不能。首先對各層循環(huán)進(jìn)行并行性分析,通過計(jì)算各個(gè)依賴性方向向量(1,2,3 (L,

)最外層可并發(fā)執(zhí)行的循環(huán)（

11條件分支語句i-else語句），循環(huán)語句（while語句），故可根據(jù)模型中的分類L1：FORi1=1TON1L2

i2=1TON2Lm FORim=1TONmm設(shè)循環(huán)中的計(jì)算量為QLQ(NiiL1,L2Lnn個(gè)可以并發(fā)執(zhí)行的程序段的計(jì)算量。為了將它們合理地分配到12個(gè)處理器上并使二者的計(jì)算時(shí)間相當(dāng)，這就要讓兩個(gè)處理器的計(jì)算量接近Li2xi

Li不在ALi在A 12minxiLi 2 xi1Ax0五、仿真測 QueueA和QueueBS8A，B處理器執(zhí)行完畢之后才能級，必須將該程序執(zhí)行次才能看到結(jié)果）QueueAQueueB的分支結(jié)構(gòu)T1=CLOCK(F