Programara ĉenstablo

En komputado, programara ĉenstablo temas pri metodo por plibonigi iteracion, simile al ĉenstablo en procesoro. Programara ĉenstablo estas tipo de fororda plenumado, krom ke la reordiganto estas programtradukilo (aŭ por manskribita asembla programo, programisto) anstataŭ la procesoro. Kelkaj komputilo-arkitekturo klare subtenas programaran ĉenstablon, ekzemple arkitekturo IA-64 el Intel.

Ekzemplo

Konsideru la jenan iteracion

for i = 1 to N
  A(i)
  B(i)
  C(i)
end

Jen A(i), B(i), C(i) estu instrukcioj pri la datumo i, kiuj interdependas. Alivorte, A(i) finiĝu antaŭ la komenco de B(i). Ekzemple, A eble elmemorigas datumon en reĝistron. B eble faras aritman komputadon je la datumo, kaj C eble enmemorigi la rezulton. Tamen, operacioj je malsamaj i estu sendependaj. Alivorte, A(2) povas komenci antaŭ ke A(1) finiĝas.

Sen programa ĉenstablo, la programo plenumĝos sekve

A(1) B(1) C(1) A(2) B(2) C(2) A(3) B(3) C(3) ...

Konsideru ke ĉiu instrukcio finiĝas en 3 taktoperiodojn kaj (same kiel multe da modernaj sistemoj) ke unu instrukcio povas komenci po taktoperiodo, se ĝi ne dependas sur iu plenumata instrukcio. Do en la senĉenstabla versio, ĉiu iteracifojo finiĝos en 9 taktoperiodojn: 3 periodojn por A(1), 3 por B(1), kaj 3 por C(1).

Nun konsideru la sekvan programon kun ĉenstablo

A(1) A(2) A(3) B(1) B(2) B(3) C(1) C(2) C(3) ...

Estas facile pruvi ke unu instrukcio povas komenci je ĉiu taktoperiodo. Do la montrata 3 iteracifojoj kostas entute 9 taktoperiodojn, ebenige 3 taktoperiodojn po iteracifojo.

Realigado

Programara ĉenstablo ofte uziĝas kune kun iteracifo-malruligado, kaj la kunuzo donas pli bonan rezulton ol iteracio-malruligado sole. En la antaŭa ekzemplo, ni povas skribi la programon jene (se N estas 3-opa):

por i = 1 al (N - 2) paŝ 3
  A(i)
  A(i+1)
  A(i+2)
  B(i)
  B(i+1)
  B(i+2)
  C(i)
  C(i+1)
  C(i+2)
fin

Certe, estas pli ampleksa se ni ne povas certigi ke la tuta nombro da iteracifojo estas opo de la nombro da malruligitaj iteracifojoj. Vidu iteracio-malruligadon por trovi solvojn de la problemo, sed notu ke programara ĉenstablo malpermesas Dufan aparaton.

Ĝenerale, malruligado ne estas la plej bona metodo por realigi ĉenstablon. Konsideru iteracio kun instrukcioj kun longa respondtempo. Ekzemple

por i = 1 al N
  A(i) ; 3 taktoperiodoj de respondotempo
  B(i) ; 3
  C(i) ; 12(eble iu glitkoma operacio)
  D(i) ; 3
  E(i) ; 3
  F(i) ; 3
end

bezonas malruligi 12 iteracifojojn por averti eviti la ŝtopiginstrukcion C. Do la kodo de la iteracifo plilongiĝos 12-ope, tio ne nur influas memoro-uzadon, sed ankaŭ efikecon de kaŝmemoro. Pli maloportune, la antaŭparto (programero antaŭ la iteracio por tiam, kiam la N ne estas 12-opa) eble estos pli longa ol la ĉefa parto mem, kaj verŝajne malefika ĉar programara ĉenstablo ne eblas ĉi-programe (sen pli da plilongigaĉo). Ankaŭ, se N estas malgranda kompare al la nombro de malruligitaj iteracifojoj (ekzemple 10-20), la plenumado elspezus plej da tempo en la malefika antaŭparto, malefikigante programaran ĉenstablon.

Kontraste, jen estas programara ĉenstablo por nia ekzemplo (ni ekspliku pri la antaŭ- kaj postparto poste)

antaŭparto
por i = 1 al (N - 6)
  A(i+6)
  B(i+5)
  C(i+4)
  D(i+2) ; notu ke ni forigis i+3
  E(i+1)
  F(i)
fin
postparto

Unue ni pruvu ke la programo donas la saman rezulton al la origina, dum la mezo de la iteracifojoj. Aparte, ni konsideru la 7a iteracifojo en la origina iteracio. La unua iteracifojo de la ĉenita programo estu la unua iteracio, kio enhavas instrukcion el la 7a de la origina programo. La instrukcioj ordiĝas jene:

Iteracifojo 1: A(7) B(6) C(5) D(3) E(2) F(1)

Iteracifojo 2: A(8) B(7) C(6) D(4) E(3) F(2)

Iteracifojo 3: A(9) B(8) C(7) D(5) E(4) F(3)

Iteracifojo 4: A(10) B(9) C(8) D(6) E(5) F(4)

Iteracifojo 5: A(11) B(10) C(9) D(7) E(6) F(5)

Iteracifojo 6: A(12) B(11) C(10) D(8) E(7) F(6)

Iteracifojo 7: A(13) B(12) C(11) D(9) E(8) F(7)

Tamen, ne kiel la origina programo, la ĉenita versio evitas la ŝtopigon je instrukcio C. Notu ke estas jam 12 instrukcioj inter C(7) kaj la dependanta instrukcio D(7).

La antaŭ- kaj postparto pritraktas la iteracifojojn je la komenco kaj fino de iteracio. Jen estas ebla antaŭparto de nia ekzemplo

; antaŭparto (aranĝita vice por klareco)
A(1)
A(2), B(1)
A(3), B(2), C(1)
A(4), B(3), C(2)
A(5), B(4), C(3), D(1)
A(6), B(5), C(4), D(2), E(1)

Ĉiu vico montrata signifas unu iteracifojon de la meza parto, sen instrukcioj nekomencantaj. Simile, la postparto grade forigas instrukciojn finitaj

; postparto (aranĝita vice por klareco)
B(N), C(N-1), D(N-3), E(N-4), F(N-5)
C(N), D(N-2), E(N-3), F(N-4)
D(N-1), E(N-2), F(N-3)
D(N), E(N-1), F(N-2)
E(N), F(N-1)
F(N)