59 O VZPOREDNEM MNOŽENJU MATRIK INFORMATICA 1/91 ' Borut Robič, Polona Blaznik Keywords: parallel algorithm, matrix multiplication, parallel Institut Jožef Stefan computer architecture. ¿> Ljubljana Opisani so trije časovno optimalni algoritmi za vzporedno množenje kvadratnih matrik na modelih SIMD-MC2, SIMD-CC ter SIMD-PŠ vzporednega računanja. Podane so ustrezne časovne zahtevnosti. Izpeljan je formalni dokaz pravilnosti algoritma na SIMD-PS. ON PARALLEL MATRIX MULTIPLICATION: .We describe three parallel matrix multiplication algorithms which are known to be time optimal on underlying models of parallel computation: SIMD-MC2, SIMD-CC, and SIMD-PS. Their time complexities are analized. Also, a formal proof of the algorithm correctness for SIMD-PS is derived. Keywords: parallel algorithm, matrix multiplication, parallel computer architecture. 1. Uvod Množenje matrik je operacija, ki se zelo pogosto pojavlja v nu-meričnih ter nenumeričnih problemih, zato je bila in še vedno je predmet intenzivnih raziskav. Osnovni zaporedni algoritem za množenje dveh kvadratnih matrik reda n ima časovno zahtevnost 0(ns) aritmetičnih operacij. Slednji je veljal za najboljšega vse do odkritja Strassenovega algoritma leta 1969 s kompleksnostjo 0(nJil), kar je sprožilo plaz raziskav, usmerjenih v iskanje časovno Se učinkovitejših algoritmov. Poznan je že algoritem s kompleksnostjo 0(n.u), kjer je u> < 2.4955 [3]. Ker ni znano, ali je H(nJ) hkrati tudi največja spodnja meja za časovno kompleksnost zaporednega množenja matrik, je iskanje časovno optimalnega zaporednega algoritma še vedno aktualno. Žal pa se prednost teh algoritmov pokaže šele pri razmeroma velikih matrikah, zato imajo predvsem teoretični pomen. Po drugi strani pa hkrati z razvojefn vzporednih arhitektur postajajo zanimivi tudi vzporedni algoritmi za množenje matrik. Vzporedno množenje matrik se pojavlja celo v problemih, ko jih običajno ne rešujemo z uporabo zaporednega matričnega množenja [4]. V nadaljevanju se bomo osredotočili na družino SIMD računalnikov (Single Instruction stream, Multiple Data stream). Družina SIMD modelov vzporednega računanja obsega dve poddružini. V prvo spada model SIMD-SM (Shared Memory) skupaj z različnimi variantami, ki se med seboj razlikujejo po stopnji omejevanja in izvedbe sočasnega čitanja/vpisovanja v skupni pomnilnik. Modeli iz te poddružine omogočajo lažji razvoj vzporednih algoritmov, ker se ni potrebno ozirati na arhitekturne značilnosti. Uporabni so predvsem pri določanju spodnjih meja za časovne kompleksnosti algoritmov. V drugo poddružino pa spadajo realnejši modeli, pri katerih so izpostavljene nekatere arhitekturne značilnosti - predvsem način povezovanja procesorjev ter porazdelitev pomnilnika. Mednje spadajo tudi modeli SIMD-MC (Mesh Con- nected), SIMD-CC (Cube Connected), ter SIMD-PS (Perfect Shuffle), ki so poimenovani po različnih medprocesorskih povezovalnih shemah. Pri razvoju algoritma za reševanje danega problema moramo upoštevati vse značilnosti modela, na katerem bo potekalo računanje. Zato lahko obstaja za dani problem več časovno različnih optimalnih algoritmov, ki so pač razviti za različne računske modele. V nadaljevanju bomo opisali problem vzporednega množenja dveh kvadratnih matrik na omenjenih modelih. Matriki označimo z A in B; obe sta reda n x n. Produkt naj bo matrika C z elementi C"J = £?=0 Oi.kbkj- 2. Množenje na SIMD-SM-CRCW Najprej določimo spodnjo mejo za časovno kompleksnost vzporednega množenja matrik. Vzemimo model SIMD-SM-CRCW, kjer imajo vsi procesorji skupni pomnilnik, v katerega lahko sočasno vpisujejo ali iz njega čitajo. Reševanje konftiktnih situacij pri sočasnem posegu (vpisovanju, čitanju) v skupni pomnilnik je prepuščeno modelu (nekateri pristopi so opisani v (lj); algoritem bo zato enostavnejši, model pa toliko bolj skrivnosten. Pri analizi ne upoštevamo operacije prenašanja podatka iz enega procesorja v drugi. Prav tako predpostavljamo, da število procesorjev ni vnaprej omejeno: če se pri razvoju algoritma pojavi potreba po večjem številu procesorjev, lahko smatramo, da so že na voljo. Kljub svoji nerealnosti pa ta model omogoča določitev spodnje meje za časovno kompleksnost vzporednega množenja matrik, saj se pri razvoju algoritma osredotočimo le na bistvene operacije. Denimo torej, da je na voljo vsaj ns procesorjev. V prvem koraku se sočasno izračuna vseh ns produktov a, t6t j, 0 < t,J, fc < n — 1. Nato se sočasno izračuna vseh nJ vsot c,j = £k=o Gt.fc^k,)» 0 < »,/.< n - 1. Vsako vsoto lahko izračunamo z j procesorji v flogn] korakih, če izvršimo seštevanje v obliki binarnega drevesa. Skupaj je potrebnih flogn] + 1 korakov, kar je spodnja meja za časovno kompleksnost vzporednega množenja matrik [2]. 60 Za razvoj praktitno uporabnega algoritma pa moramo izbrati enega izmed realnejših modelov vzporednega računanja. Obravnavali bomo vzporedno množenje matrik na modelih SIMD-MC2, SIMD-CC in SIMD-PS. 3. Množenje matrik na SIMD-MC2 SIMD-MC2 vsebuje n' procesorjev P,j, 0 < i, j < n - 1, ki so ciklično povezani v dvodimenzionalno mrežo (Slika 1). Vsak procesor P,j- ima Štiri sosede Pimj, Pijel, P,eij in P.-jei, kjer smo s ffi in © označili operaciji seštevanja in odštevanja po modulu n. Vsak P,j- vsebuje tri registre A,j, B,j ter C,y. 1 if I i; t» ij ifl U ii it U i; ifi ix 4; i* Slika 1 Ob ustreznem ukazu lahko procesorji sočasno pošljejo vsebine izbranega registra v dani smeri svojim sosedom. Na primer, kadar se prenažajo vsebine registrov A v levo (oziroma navzgor), to zapišemo z A,j «—AliJ(S)1 (oziroma A,j «— A,©ij). 3.1 Spodnja časovna meja Gentleman je v (5] pokazal, da je treba pri analizi vzporednih algoritmov upoštevati tudi operacije prenašanja podatkov med procesorji; analize, ki tega ne upoštevajo, dajejo nerealne rezultate. Računski model, na katerem temelje Gentlemanove ugotovitve, združuje večje število procesorjev, ki imajo lahko tudi lokalne pomnilnike. Vsak procesor lahko neposredno pošlje podatek omejenemu številu sosednjih procesorjev. Procesor lahko pošlje podatek v enem koraku le enemu sosedu. Gentlemanov računski model je dovolj splošen, da je v njem zajet tudi SIMD-MC1. Razpriilna funkcija p(k) : N >-+ N naj bo definirana kot največje število procesorjev, ki lahko po h korakih prenašanja podatkov prejmejo podatek'iz izbranega začetnega procesorja. Tu seveda predpostavljamo, da procesorji, ki so podatek že prejeli, sodelujejo pri njegovem nadaljnem širjenju v okolico. Funkcija p je seveda odvisna od povezovalne sheme procesorjev, torej od modela vzporednega računalnika. Neodvisno od povezovalne sheme pa velja sledeči Izrek |5) Na opisanem modelu računanja zahteva množenje dveh matrik reda n x n vsaj s korakov prenaianja podatkov, tako da je p(2s) > n* . Dokaz. Opazujmo poljuben element ctJ-; nahaja se v procesorju P,-,, in je enak c.j = aiikbkJ. Vsak izmed faktorjev o,-,t •n bkj, 0 < k < n - 1, ki vstopajo v ta izraz, se na začetku nahaja v lastnem procesorju in med računanjem vrednosti c,j opravi neko pot do procesorja P;,. Naj bo s(ij) dolžina najdaljše izmed poti, ki jo opravijo ti faktorji pri računanju c,j in naj bo s = maxiJ«(ij). Torej je pri računanju produkta matrik potrebnih vsaj s prenosov podatkov. Izberimo dva poljubna procesorja Pt in P„. Element matrike A, ki se nahaja v procesorju Pr, naj bo o,-j. Zanima nas zgorivja meja za število potrebnih korakov pri prenašanju tega elementa v procesor Pv. Denimo, da se v P„ na- haja element 6U|„ matrike B. Tedaj lahko pri prenašanju elementa Oij uberemo pot preko procesorja P,, v katerem pričakujemo element e,iU produkta matrik. Takšna pot namreč mora obstajati, saj v nasprotnem ne bi mogli izračunati c; „: prvi del je pot, ki jo pri računanju c,iU opravi a,j do P,, drugi del pa pot, ki jo pri tem (v obratni smeri) opravi bUiV. Iz definicije števila s sledi, da obe poti skupaj merita kvečjemu 2s. Sledi, da je za prenos podatka iz enega procesorja v drugi potrebnih kvečjemu 2s korakov. Seveda pa mora biti s zadosti velik, da lahko iz danega procesorja podatek pride do kateregakoli izmed n1 procesorjev. To pomeni, da mora biti 2s korakov dovolj za razpršitev podatka v vseh n2 procesorjev, oziroma p(2s) > n'. S tem je izrek dokazan. Opazimo, da dokazovanja nismo oprli na nobeno od medprocesorskih povezovalnih shem. □ Za model SIMD-MC2 je enostavno videti, da je moč v k korakih začetni podatek razpršiti v p(k) = 2A2 + 2k + 1 procesorjev. Od tod in iz zgornjega izreka sledi, da je za ta model s > - 4• Sledi, da je spodnja časovna meja za množenje dveh matrik reda n x n na modelu SIMD-MC2 enaka f)(n). Vsak algoritem s časovno kompleksnostjo O(n) je zato s stališča asimp-totičnih časovnih kompleksnosti optimalen na SIMD-MC?. Tak algoritem je opisan v nadaljevanju. 3.2 Algoritem Videli smo, da se na modelu SIMD-MC2 dveh matrik reda n x n ne da zmnožiti hitreje kot v linearnem času glede na n. L.E.Cannon je razvil algoritem, ki to stori v času ©(n) in je zato časovno optimalen na modelu SIMD-MC2 [4]. Na začetku velja A,j = a,j, B,j- = 6,j ter C(J- = 0, 0 < i, j < n - 1. Na koncu pa je C, ,- = dj = T,kZo 0 < t',j < n — 1, torej element produkta matrik. Algoritem se glasi: 1 begin 2 for k = 1 to n-1 do 3 forall P(j do 4 if i>k then A,j A,j®i 5 if j>k then B,j 6 endforall 7 endfor; 8 forall P, j do 9 C,j := Aij.Bij 10 endforall; 11 for k = 1 to n-1 do 12 forall P.j do 13 A, j *— A,-,®; 14 Bi,j B,®ij 15 C.j := Cij+A,j*B, 16 endforall 17 endfor 18 end. Tu pomeni znak «— prenašanje podatkov med registri različnih procesorjev, znak := pa znotraj procesorja. Algoritem sestavljajo trije deli. V prvem, ki ga sestavljajo vrstice 2.. .7, se vsebine registrov A,j in Bij premestijo: v »- ti vrstici se začetne vsebine registrov A i-krat premestijo ciklično v levo, v j-tem stolpcu pa se začetne vsebine registrov B /-krat ciklično premestijo navzgor. Po izvršitvi prvega dela velja torej za vsak P.J-: A.j = Oi,.®, in Btj = A,ejj. Vsebini registrov A.j in B,j se lahko takoj pomnožita, saj se nahajata v istem procesorju P.j, njun produkt pa je eden od členov v končnem c.j. Sočasno množenje v vseh procesorjih opisujejo stavki 8.. .10, ki tvorijo drugi del algoritma. V tretjem delu algoritma (vrstice 11.. .17) prištejemo trenutni vsebini registra C{J- še ostalih n-1 produktov, ki so členi končnega c/j. V vsakem procesorju dobimo nova faktorja, ki sestavljata takšen produkt, če vsebine vseh registrov A preslikamo enkrat ciklično v levo, vsebine vseh registrov 61 B pa enkrat ciklično navzgor. Na primer, po k izvršitvah zanke 11 velja za vsak Pjj, 0 < i, j < n - 1: A.," J — = ^iejffiij C( j = c, j = £'=o Gi.iej&pbiejepj Po k = n — 1 ponovitvah zanke 11 se v C, j nahaja rezultat e,;. Kakšna je časovna kompleksnost algoritma? Prvi del zahteva 2(n — 1) operacij sočasnega premikanja vsebin registrov. Drugi del algoritma zahteva eno sočasno množenje po vseh procesorjih. Tretji del pa zahteva 2(n — 1) operacij sočasnega premikanja vsebin registrov, ter 2(n — 1) operacij sočasnega množenja/seštevanja. Skupaj je potrebnih 4(n - 1) operacij sočasnega premikanja vsebin registrov ter 2(n —1}+1 aritmetičnih operacij. Algoritem ima časovno kompleksnost ©(n) in je zato asimptotično časovno optimalen na SIMD-MC2. 4. Množenje matrik na SIMD-CC Matriki reda nx n lahko teoretično zmnožimo v času @(log n), če se ne oziramo na model vzporednega računanja. Z izborom modela vzporednega računanja, na katerem želimo množiti matriki, pa je potrebno pri snovanju algoritma upoštevati tudi arhitekturne značilnosti modela. Prav te pa lahko zelo poslabšajo časovno kompleksnost algoritma, pa čeprav je ta optimalen na izbranem modelu. TakSen primer smo videli v prejšnji točki, kjer je imel optimalni algoritem na SIMD-MC3 časovno kompleksnost samo ©(n). V tej točki pa bomo opisali model SIMD-CC, ki dovoljuje zasnovo algoritma s časovno kompleksnostjo ©(logra). Model SIMD-CC imenujemo tudi hiptrkocka. V tej točki naj bo dimenzija matrik n = 2' , za nek q 6 N. V modelu SIMD-CC naj bo p = ns = 2^ procesorjev P0l... ,Pp_i. V vsakem procesorju Pr se nahajajo registri Ar, Bf in Cr. Vsak procesor Pr je povezan z log(p) = 3 log n = 3q procesorji, katerih indeksi so števila r(0', r'1', ..., r(s,_I>, kjer rW dobimo tako, da v r invertiramo bit rt. Če indeks r, 0 < r < p — 1, zapišemo v binarni obliki (s 3g biti) in zaporedne f-terke bitov opazujemo kot števila i, j, k, 0 < «./,*< 1, r - r3,_!... r2, rj,_j ... r, r,_j.,. r0 lahko procesor P, označimo tudi s P[i , pripadajoče registre pa z Apj-.ti, B|,ji,| in C[,j-ti|. Oba zapisa sta ekvivalentna in ju bomo uporabljali izmenično po potrebi. Prednost drugega zapisa je, da si lahko SIMD-CC predstavljamo kot tridimenzionalno polje procesorjev; števila i, j, k povedo, kje v polju se nahaja P|i./,t|. Opozoriti pa moramo, da procesorja, ki sta v tem polju sosednja, v splošnem nista povezana, saj so povezave med procesorji vspostavtjene tako, kot je bilo opisano zgoraj. Na začetku predpostavljamo, da sta matriki A in B vpisani v registre A oziroma B "na dnu" tridimenzionalnega polja, tako daje A|oj,k| = a j, k ter B[oj,i] = 6,^,0 < j, k < n - 1. Zahtevamo, da nam algoritem vrne C|0jii| = cjk = El^o o>,n,i>m,i>0 < j,k < n — 1. Opišimo postopek najprej v splošnem. Vektorja a, , in 6,,*, katerih skalami produkt je , sta na dnu polja pravokotna eden na drugega (Slika 2a.). Zato ju "dvignemo" tako, da so komponente a,,, 6, t,0 < t < n — 1 paroma v istih procesorjih (Slika 2b.). To storimo sočasno za vse pare vektorjev a}i,, 6,.n, 0 < j, k < n — 1. Istoležne komponente sočasno pomnožimo v vseh n procesorjih, ter v vsakem stolpcu seštejemo produkte tako, da se njihove vsote "sesedejo" na dno v C|o,,-,jt| - \ \ k, N \ \ \ \ \ \ b.. k 'k, \ Slika 2a Slika 2b Sedaj pa podrobneje opišimo algoritem. V prvem delu preslikamo obe matriki z dna še na vse ostale nivoje tridimenzionalnega polja, tako da na koncu dobimo A|iijk| = aj t ter B|i ) t] = bjk, za vse nivoje t, 0 < » < n —1. Na prvi pogled kaže, daje za to potrebnih 0(n) korakov, saj je vsak procesor P|oj,t| navzgor neposredno povezan le s q - 1 = log(n) — 1 procesorji P[i-,>,i], 1 < m < ? - 1, poleg tega pa lahko v enem koraku procesor pošlje podatek le enemu sosedu. Toda v SIMD-CC so procesorji med seboj tako povezani, da je možno v vsakem koraku podvojiti število tistih procesorjev v stolpcu, ki že imajo začetni podatek. Zato preslika-vanje zahteva q = 0(logn) korakov. Za n = 8 je preslikavanje v enem stolpcu ilustrirano na sliki 3. r&i-i • • • . ~ O, 111 110 101 100 011 010 001 000 ■a a 1.korak H H s=) h H 2.korak 3.korak Slika 3 V splošnem pa za to poskrbijo stavki 1... 8: 1 for m = Zq — 1 downto 2q do 2 forall P„ 0 < r < p - 1 do 3 if rm = 0 then Ar(.> «- Ar 4 endforall; 5 forall Pr, 0 < r < p - 1 do 6 if rm = 0 then Br(.) «-B, 7 endforall 8 endfor; Na koncu velja A[1Jit| = ajik ter B[,jV4| = bjk,0 < i, j, k < n - 1. Pri k = «' dobimo A[(ji,| = o,-,-; ti elementi se nahajajo na diagonali, kot kaže Slika 4a. Podobno dobimo B|i,i,t| = b, k, če vzamemo j = i (Slika 4b.). Vsebino registra A|ijit| prenesemo v vse ostale registre A[,j-,4], 0 < k < n - 1 (Slika 4a.). Vsebino registra B|l l t] pa prenesemo v vse registre B|ijit], 0 < j < n - 1 (Slika 4b.). KI r Slika 4a Slika 4b 62 Za to poskrbijo stavki 9... 12 oziroma 13 ... 16: 9 for m = q - 1 downto 0 do 10 forall Pr, 0 < r < p - 1 do 11 if rm = r2j+m then Ar,„) «^Ar 12 endforall; 13 for m = 2g - 1 downto q do 14 forall Pr, 0 < r < p - 1 do 15 if rm = r,+m then BPo) <-Bf 16 endforall; Na koncu je A|, j t| = a,-,,- ter B|ij,i] = 0 < t, i, i < n — 1, (Slika 2b). Sedaj pa lahko sočasno pomnožimo vsebine registrov Aij^,*] ter B[,jti| v vseh p procesorjih, kot to opisujejo stavki 17... 19: 17 forall Pr, 0 < r < p - 1 do 18 CP := AP*BP 19 endforall; V zanjem koraku moramo sešteti produkte, ki se nahajajo v stolpcih, tako da se njihove vsote Cj^ pojavijo na dnu tridimenzionalnega polja. Postopek seštevanja v enem stolpcu je za n = 8 ilustriran na Sliki 5, v splošnem pa je opisan s stavki 20... 24. « O O O o o—J D O C O D o * o 1.korak O o o H b h b o o o E+P+C+H£ O o o A+B+C+D ^ O o o o C o o A + ... + H 0 2.korak Slika 5 3.korak 20 for m = 2g to 3? - 1 do 21 forall P„ 0 < r < p - 1 do 22 if rm = 0 then C, <- Cp+Cr(-) 23 endforall 24 endfor; Časovno kompleksnost algoritma sestavlja 5? = 5 log(n) korakov sočasnega prenašanja podatkov med procesorji, eno sočasno množenje in log(n) sočasnih seštevanj. Opisani algoritem ima torej časovno kompleksnost reda ©(logn). 5. Množenje matrik na SIMD-PS Naj bo dimenzija matrik enaka n = 2', za nek q £N. V modelu SIMD-PS naj bo p = n! = 25' procesorjev P0l... ,Pp_[. V vsakem procesorju Pr se nahajajo registri AP, BP in Cr. Vsak procesor P, je povezan s tremi sosednjimi procesorji P,a(p), P«i(r) in Pun(p), kjer so indeksi a/i(r), ex{r) ter un(r) števila, katerih binarni zapis dobimo iz binarno zapisanega indeksa r = rj,_irj,_j ... r^rj,.! ... r,r,_i ... r^o na naslednji način: sh(r) = rs,_i... rj,r2,_i ... r,r,_i... r^r ex(r) = r^-jrj,., ... r2,r2,_, ... r,r,_, ... r,ro un(r) = r0r3,-irj,-2.. .rj,r2,_i. ..r,r,_i.. .ri Tu je tfo komplement bita r0. Funkcije sh, un in ez se imenujejo "sjhuffle", "unshuffle" ter "exchange" in izvršijo ciklično rotacijo bitqv argumenta v levo, desno oziroma komplementiranje zadnjega bita. Podobno kot pri modelu SIMD-CC bomo tudi tu uporabljali za indekse izmenično oznaki r in [x,y, zj, kjer je0,.i, 0 < i,t, s < n - 1. Dokaz: Register A[0i,->tj z vsebino a,it se nahaja v procesorju Pr, kjer je r = 00... 0 r2,_!... r, r,_i... r0. —v •• ~ - V prvi izvedbi zanke 1 se vsebina o,-,< registra Ajo.,.(| z ukazom 3 preslika v kjer sh(r) = 0... Orj,.!... r,r,_i... r00, z ukazom 5 pa iz tega registra še v register Aet(,h(r)), kjer je ex(sh{r)) = 0... 0r2,_,... r,r,_i... r0l. Predpostavimo, da so po b ponovitvah zanke 1 vrednosti Oi,t v vseh s = 2' registrih AP, kjer je r = 00... 0 r2,_!... r, r,_i... r0 r^ ... ^ ; r-"-;- in 0 < j < 26 - 1. Po naslednji ponovitvi zanke je ait zaradi 3 in 5 v vseh s = 2t+1 registrih AP, kjer je r = 00. .^0 r2,_, ...r, r,_j... r0 rj,.,... r^.,) in 0 < j < - 1. i ' : -;- Ker je n = 2', se po q ponovitvah zanke 1 a,i( nahaja v vseh n registrih A[i>(i,|, kjer 0 < s < n - 1. Ker je bil par i, t poljuben, je s tem prvi del trditve dokazan. Dokaz za registre B je podoben. a V naslednjem koraku premestimo vsebine registrov A: 9 for b = 0 to q - 1 do 10 forall Pr\ 0 < r < p - 1 do 11 A,*(r) <—AP 12 endforall 13 endfor; Trditev: Po izvriitvi vrstic 9... 13 je A[,= a.,-,0 < i,t,s < n-1. Dokaz: Pred izvršitvijo teh vrstic je A|,il (| = a, ,, 0 < s, i,t < n-1. Po q izvršitvah stavka 11 se a,,,- iz A(,,,i(| prenese v A|,,(i,|, saj velja s/i«([i,i',t]) = |«,t,a]. □ Po izvršitvi stavkov 1... 13 sta v registrih A]ii( tj in B|ii(i,| procesorja P^,,,,) vrednosti a,%i in 6,-Njun produkt a, ,6;, je eden od ti členov v končnem c(t, zato ju je smiselno pomnožiti. To seveda velja za vse procesorje PP, 0 < r < p - 1, saj lahko vsak r zapišemo v obliki r = |t,f,s], kjer 0 < i,t,s < n - 1. Sočasno 63 množenje v vseh procesorjih opisujejo stavki 14 ... 16: 14 forall Pr,0 < r < p - 1 do 15 Cr := Ar«Br 16 endforall; Rezultat stavkov 14 ... 16 je C|<,i,,] = a.,¡bi,t. Ker želimo na koncu dobiti c, t = a>,iA',i! moramo za vsak par s, t sešteti vsebine vseh registrov C[,|(|,|,0 < i < r» — 1: 17 for i = 0 to q - 1 do 18 forall Pr,0 < r < p - 1 do 19 20 C, <- Cf+ Cel(r) 21 endforall 22 endfor; Trditev: Po izvršitvi stavkov 17...22 velja C|(iJ,,| = c,tt = £i=o'i,tVi za vse t>3< •'» 0 < <,«, t < n — 1. Dokaz: Izberimo poljuben par števil t, a, 0 < t,a < n - 1 in p ¡žimo ft = a,tibi:l. Vsebina registra C(,it>,j je /¡. Naj bosta r m o binarna zapisa števil t in s, torej t,a S {0,1}'. Naj pomeni £/,...„ seštevanje po vseh j,...ji € {0,1}'. Naprimer, £3lij pomeni seštevanje, kjer indeks preteče binarna zaporedja 00, 01, 10 in 11. Tedaj opazimo, da po prvi izvršitvi zanke 17 velja za vse t,_,£{0,l}: Ci,_,...i0r<7i,_, = 53 fil<,-7--¡O' Ji Naj po i> ponovitvah zanke 17 velja za vse ... e {0,1}': Ci,.,.,...!»«!,-,...!,.,.,,.,, = 53 U\ >»,-1-1 'O' (*) Ji J« Po vnovični izvršitvi sta,vka 19 je za vse ... 6 {0,1}': ^•«-■-(t+i)-for»,-i-(l+ii•••'o • ji-j» S stavkom 20 se obe vsoti seštejeta in priredita obema registroma, zato velja za vse t',_i.6 {0,l}'+1: ^"'«-l-O+il -■