算法导论 第三版 第27章 答案 英

Chapter27

MichelleBodnar,AndrewLohr

April12,2016

Exercise27.1-1

Thismodificationisnotgoingtoaffecttheasymptoticvaluesofthespan

workorparallelism.Allitwilldoisaddanamountofoverheadthatwasn’t

therebefore.ThisisbecauseassoonastheFIB(n−2)isspawnedthespawn-

ingthreadjustsitsthereandwaits,itdoesnotaccomplishanyworkwhileit

iswaiting.Itwillbedonewaitingatthesametimeasitwouldofbeenbefore

becausetheFIB(n−2)callwilltakelesstime,soitwillstillbelimitedbythe

amountoftimethattheFIN(n−1)calltakes.

Exercise27.1-2

Thecomputationdagisgivenintheimagebelow.Thebluenumbersby

eachstrandindicatethetimestepinwhichitisexecuted.Theworkis29,span

is10,andparallelismis2.9.

Exercise27.1-3

1

Supposethattherearexincompletestepsinarunoftheprogram.Since

eachofthesestepscausesatleastoneunitofworktobedone,wehavethat

thereisatmost(T1−x)unitsofworkdoneinthecompletesteps.Then,we

supposebycontradictionthatthenumberofcompletestepsisstrictlygreater

than󰀌(T1−x)/P󰀍.Then,wehavethatthetotalamountofworkdoneduringthe

completestepsisP·(󰀌(T1−x)/P󰀍+1)=P󰀌(T1−x)/P󰀍+P=(T1−x)−((T1−x)

modP)+P>T1−x.Thisisacontradictionbecausethereareonly(T1−x)

unitsofworkdoneduringcompletesteps,whichislessthantheamountwe

wouldbedoing.NoticethatsinceT∞isaboundonthetotalnumberofboth

kindsofsteps,itisaboundonthenumberofincompletesteps,x,so,

TP≤󰀌(T1−x)/P󰀍+x≤󰀌(T1−T∞)/P󰀍+T∞

Wherethesecondinequalitycomesbynotingthatthemiddleexpression,asa

functionofxismonotonicallyincreasing,andsoisboundedbythelargestvalue

ofxthatispossible,namelyT∞.

Exercise27.1-4

Thecomputationisgivenintheimagebelow.Letvertexuhavedegreek,

andassumethattherearemverticesineachverticalchain.Assumethatthis

isexecutedonkprocessors.Inoneexecution,eachstrandfromamongthek

ontheleftisexecutedconcurrently,andthenthemstrandsontherightare

executedoneatatime.Ifeachstrandtakesunittimetoexecute,thenthetotal

computationtakes2mtime.Ontheotherhand,supposethatoneachtimestep

ofthecomputation,k−1strandsfromtheleft(descendantsofu)areexecuted,

andonefromtheright(adescendantofv),isexecuted.Ifeachstrandtake

unittimetoexecuted,thetotalcomputationtakesm+m/k.Thus,theratio

oftimesis2m/(m+m/k)=2/(1+1/k).Askgetslarge,thisapproaches2asdesired.

2

Exercise27.1-5

TheinformationfromT10appliedtoequation(27.5)giveusthat

42≤T1−T∞10+T∞

whichtellusthat

420≤T1+9T∞

Subtractingthesetwoequations,wehavethat100≤8T∞.

IfweapplythespanlawtoT64,wehavethat10≥T∞.Applyingthework

lawtoourmeasurementforT4getsusthat320≥T1.Now,lookingattheresult

ofapplying(27.5)tothevalueofT10,wegetthat

420≤T1+9T∞≤320+90=410

acontradiction.So,oneofthethreenumbersforruntimesmustbewrong.

However,computersarecomplicatedthings,anditsdifficulttopindownwhat

canaffectruntimeinpractice.ItisabitharshtojudgeprofessorKarantoo

poorlyforsomethingthatmayofbeenoutsidehercontrol(maybetherewasjust

agarbagecollectionhappeningduringoneofthemeasurements,throwingitoff).

Exercise27.1-6

We’llparallelizetheforloopoflines6-7inawaywhichwon’tincurraces.

WiththealgorithmP−PRODgivenbelow,itwillbeeasytorewritethecode.

Fornotation,letaidenotetheithrowofthematrixA.

Algorithm1P-PROD(a,x,j,j’)

1:ifj==j󰀃then

2:returna[j]·x[j]

3:endif

4:mid=󰀉j+j󰀂2󰀊

5:a’=spawnP-PROD(a,x,j,mid)

6:x’=P-PROD(a,x,mid+1,j’)

7:sync

8:returna’+x’

Exercise27.1-7

Theworkisunchangedfromtheserialprogrammingcase.Sinceitisflipping

Θ(n2)manyentries,itdoesΘ(n2)work.ThespanofitisΘ(lg(n))thisisbe-

causeeachoftheparallelforloopscanhaveitschildrenspawnedintimelg(n),

sothetotaltimetogetalloftheconstantworktasksspawnedis2lg(n)∈Θ(lg).

3Algorithm2MAT-VEC(A,x)

1:n=A.rows

2:letybeanewvectoroflengthn

3:parallelfori=1tondo

4:yi=0

5:end

6:parallelfori=1tondo

7:yi=P-PROD(ai,x,1,n)

8:end

9:returny

Sincetheworkofeachtaskiso(lg(n)),thatdoesn’taffecttheT∞runtime.The

parallelismisequaltotheworkoverthespan,soitisΘ(n2/lg(n)).

Exercise27.1-8

TheworkisΘ(1+󰀆nj=2j−1)=Θ(n2).ThespanisΘ(n)becauseinthe

worstcasewhenj=n,thefor-loopofline3willneedtoexecutentimes.The

parallelismisΘ(n2)/Θ(n)=Θ(n).

Exercise27.1-9

WesolveforPinthefollowingequationobtainedbysettingTP=T󰀃P.

T1P+T∞=T󰀃1P+T󰀃∞2048

P+1=1024

P+81024

P=71024

7=P

Sowegetthatthereshouldbeapproximately146processorsforthemto

havethesameruntime.

Exercise27.2-1

Seethecomputationdagintheimagebelow.Assumingthateachstrand

takesunnittime,theworkis13,thespanis6,andtheparallelismis136

4