Paikallinen stabilointi

Aila Koponen HY/TKTL HAJALG seminaari Paikallinen stabilointi 16.11.2007

Paikallinen stabilointi

Seminaari Hajautetut algoritmit:

Itsestabiloivat algoritmit

Aila Koponen 9.10.07

Paikallinen stabilointi Paikallinen stabilointi

Joitain ongelmia itsestabiloinnissa Joitain ongelmia itsestabiloinnissa

! ! Superstabilointi Superstabilointi

! ! Virheit Virheit ä ä erist erist ä ä v v ä ä t itsestabiloivat algoritmit t itsestabiloivat algoritmit

! ! Virheenhakukoodit ja korjaus Virheenhakukoodit ja korjaus

Aila Koponen HY/TKTL HAJALG seminaari Paikallinen stabilointi 16.11.2007

Ongelmia itsestabiloinnissa Ongelmia itsestabiloinnissa

Tilanne

Tilanne: Itsestabiloivat algoritmit eiv: Itsestabiloivat algoritmit eiväät takaa t takaa

kkääyttyttääytymistytymistääään jn jäärjestelmrjestelmään stabiloitumisen aikana.n stabiloitumisen aikana.

Virheen l

Virheen lööytyminen voi alkujaan kestääytyminen voi alkujaan kestää --

virhetilanteeseen sotkeutunut alue voi kasvaa virhetilanteeseen sotkeutunut alue voi kasvaa

suureksikin suureksikin

Stabiloinnin aiheuttama muutosalue voi kattaa Stabiloinnin aiheuttama muutosalue voi kattaa

pahimmassa tapauksessa koko j

pahimmassa tapauksessa koko jäärjestelmrjestelmäänn Stabiloitumiseen kuluva aika on ep

Stabiloitumiseen kuluva aika on epäämmääräärääineninen

Superstabilointi Superstabilointi

Superstabiloiva algoritmi on m

Superstabiloiva algoritmi on määritelmääritelmäänsänsä mukaan aina mukaan aina itsestabiloiva ja lis

itsestabiloiva ja lisääksi:ksi:

Virhemallina konfiguraatiomuutos (+

Virhemallina konfiguraatiomuutos (+--linkki)linkki)

JJärjestelmärjestelmää saavuttaa mistäsaavuttaa mistä tahansa tilasta turvallisen tahansa tilasta turvallisen konfiguraation hallitusti s

konfiguraation hallitusti sääilyttäilyttäen porttiehdon en porttiehdon

stabiloitumisen aikana. Porttiehto on vahvin ehto joka stabiloitumisen aikana. Porttiehto on vahvin ehto joka pitääpitää topologiamuutoksen aikana.topologiamuutoksen aikana.

Stabiloitumisvauhti oltava ripe

Stabiloitumisvauhti oltava ripeää, esimerkiss, esimerkissää

superstabiloinnin aikavaativuus on yksi asynkroninen superstabiloinnin aikavaativuus on yksi asynkroninen

sykli sykli

Aila Koponen HY/TKTL HAJALG seminaari Paikallinen stabilointi 16.11.2007

Superstabilointi 2/4 Superstabilointi 2/4

Esimerkkin

Esimerkkinää superstabiloivaksi muuntamisesta ksuperstabiloivaksi muuntamisesta käytetäytetään itsestabiloivaa ään itsestabiloivaa väväritysalgoritmia prosessori ritysalgoritmia prosessori PP_{i i} :lle::lle:

Turvallinen konf: naapuriprosessorit eri v

Turvallinen konf: naapuriprosessorit eri väriset, naapureita max äriset, naapureita max ∆, ∆, vväärejrejää ∆+1∆+1 Jossain vaiheessa suurimman id:n omaava prosessori kiinnitt

Jossain vaiheessa suurimman id:n omaava prosessori kiinnittääää vvärinsärinsää jolloin jolloin pysyv

pysyvää vävärjrjääytyminen ytyminen ’’suuremastasuuremasta’’ ’pienimp’pienimpäääänn’’ alkaa -alkaa - turvallinen konfiguraatio turvallinen konfiguraatio saavutetaan ennen pitk

saavutetaan ennen pitkääää. .

od

10

write r_i.color := color

09

color_i := choose(\\ GColors)

08

if color_i ∈ GColors then

07

od

06

If ID(m) > I then GColors := GColors ∪ lr_m.color

05

lr_m := read (r_m)

04

for m := 1 to δ do

03

GColors := Ø //’suurempien’ naapureiden värit 02

do forever

01

Superstabilointi 3/4 Superstabilointi 3/4

Prosessorit ketjussa suuremmasta ID:st

Prosessorit ketjussa suuremmasta ID:stää pienemppienempääään. Turvallisessa n. Turvallisessa konfiguraatiossa

konfiguraatiossa ””naapureiden maksimimnaapureiden maksimimäääärärä ∆=∆=22”” ja ”ja ”vväärien rien mmääräärää ∆+1∆+1”. Stabiloituminen tapahtuu, mutta:”. Stabiloituminen tapahtuu, mutta:

Topologiamuutos s

Topologiamuutos säilytti naapureiden maksimimäilytti naapureiden maksimimäääärrääehdon mutta ei ehdon mutta ei eriveriväärisyysehtoarisyysehtoa

Pysyv

Pysyvää vävärjrjääytyminen ’ytyminen ’suuremastasuuremasta’’ ’pienimp’pienimpäääänn’’ alkaa ennen pitkalkaa ennen pitkääää Identiteettien j

Identiteettien jäärjestyksen vuoksi alkaa vrjestyksen vuoksi alkaa värjärjääytymisaaltoytymisaalto ja tuurilla ja tuurilla kaikki vaihtavat v

kaikki vaihtavat vääriäriä......

Aila Koponen HY/TKTL HAJALG seminaari Paikallinen stabilointi 16.11.2007

Superstabilointi 4/4 Superstabilointi 4/4

write r_i.color := ⊥

16

color_i := ⊥

15

if recover_ij and j>i then //topologiamuutos 14

interrupt section

13

od

12

write r_i.color := color

11

color_i := choose(\\ AColors)

10

if color_i = ⊥ or color_i ∈ GColors then

09

od

08

if ID(m) > I then GColors := GColors ∪ lr_m.color

07

AColors := AColors ∪ lr_m.color

06

lr_m := read (r_m)

05

for m := 1 to δ do

04

GColors := Ø //’suurempien’ naapureiden värit 03

AColors := Ø //kaikkien naapureiden värit 02

do forever

01

Superstabiloiva v

Superstabiloiva vääritysalgoritmi prosessori ritysalgoritmi prosessori PP_{i i} :lle::lle:

VäVärejrejää nyt yksi ylimnyt yksi ylimääräärääinen, inen, ⊥⊥ . Perusv. Perusvääripaletti kuten edellripaletti kuten edellää. . Toipuvan linkin p

Toipuvan linkin päissäissää olevat prosessorit saavat signaalin olevat prosessorit saavat signaalin recoverrecover_ijij

Virheit

Virheit ä ä erist erist ä ä v v ä ä t itsestabiloivat t itsestabiloivat algoritmit

algoritmit

Virhemalli olettaa ett

Virhemalli olettaa ettää vain vvain vääliaikaisia vikoja (liaikaisia vikoja (transient transient faults

faults) tapahtuu pitk) tapahtuu pitkääkestoisissa suorituksissa (kestoisissa suorituksissa (long-long-lived lived tasks

tasks))

MistMistää tahansa tilasta (ei vain alkutilasta) lätahansa tilasta (ei vain alkutilasta) lähtien htien voidaan saavuttaa turvallinen konfiguraatio

voidaan saavuttaa turvallinen konfiguraatio Stabiloitumiseen kuluva aika on rajoitettu

Stabiloitumiseen kuluva aika on rajoitettu O(f) O(f) sykliin sykliin kun kun f:f:n prosessorin tilat ovat korruptoituneetn prosessorin tilat ovat korruptoituneet

Esimerkkin

Esimerkkinää käkäytetytetään kiinteään kiinteään tuloksen antavaa n tuloksen antavaa itsestabiloivaa synkronista algoritmia, joka on

itsestabiloivaa synkronista algoritmia, joka on muodostettu p

muodostettu pääivitysalgoritmista (ivitysalgoritmista (2.11. Esa Elovaara2.11. Esa Elovaara) ) lisäälisäämmäällllää ””settiin”settiin” ko.prosessorin kiinteko.prosessorin kiinteää syösyötete

Aila Koponen HY/TKTL HAJALG seminaari Paikallinen stabilointi 16.11.2007

Virheit

Virheit ä ä erist erist ä ä v v ä ä t... 2/4 t... 2/4

Esimerkkin

Esimerkkinää virheitvirheitääeristäeristävvääksi muuntamisesta kksi muuntamisesta kääytetytetään kiinteään kiinteään tuloksen n tuloksen tuottavaa synkronista algoritmi

tuottavaa synkronista algoritmiää prosessori prosessori PP_{i i} :lle.:lle.

EntäEntä jos tilojen muuttumisen lisäjos tilojen muuttumisen lisäksi syksi syöötteet muuttuvat? ...paljon kukkua tteet muuttuvat? ...paljon kukkua tulostemuuttujissa ennenkuin tilanne stabiloituu...

tulostemuuttujissa ennenkuin tilanne stabiloituu...

write O_i := ComputeOutput_i(Inputs(Processors_i))

11

write Processors_i := ConPrefix(ReadSet_i)

10

ReadSet_i:= ReadSet_i \\NotMinDist(P_j ,ReadSet_i)

09

forall P_j ∈ processors(ReadSet_i) do

08

ReadSet_i:= ReadSet_i ∪ {<i,0,I_i>}

07

ReadSet_i:= ReadSet_i ++ <*,1,*>

06

ReadSet_i:= ReadSet_i \\ <i,*,*>

05

ReadSet_i:= ReadSet_i ∪ read(Processors_j)

04

forall P_j ∈ N(i) do

03

ReadSet_i := Ø

02

upon a pulse

01

MajorityInputs(Processors_i))

21

write O_i := ComputeOutput_i(RepairCounter_i,

20

RepairCounter_i := min(RepairCounter_i+ 1, d + 1)

19

else

18

RepairCounter_i := 0

17

((exists)<*,*,*,A> ∈ Processors_i| A ≠ Inputs(Processors_i)) then

16

if (O_i ≠ ComputeOutput_i(Inputs(Processors_i))) or

15

if RepairCounter_i = d + 1 then

14

write Processors_i:= ConPrefix(ReadSet_i)

13

ReadSet_i:= ReadSet_i\\ NotMinDist(P_j ,ReadSet_i)

12

forall P_j∈ processors(ReadSet_i) do

11

ReadSet_i:= ReadSet_i∪ {<i,0,I_i,A_i>}

10

ReadSet_i:= ReadSet_i ++ <*,1,*,*>

09

ReadSet_i:= ReadSet_i \\ <i,*,*,*>

08

od

07

RepairCounter_i := min(RepairCounter_i, read(RepairCounter_j))

06

If RepairCounter_i ≠ d + 1 then

05

ReadSet_i:= ReadSet_i ∪ read(Processors_j)

04

forall P_j∈ N(i) do

03

ReadSet_i := Ø

02

upon a pulse

01

Virheit Virheit ä ä erist erist ä ä v v ä ä t... 3/4 t... 3/4

Aila Koponen HY/TKTL HAJALG seminaari Paikallinen stabilointi 16.11.2007

Virheenhakukoodit ja korjaus Virheenhakukoodit ja korjaus

Virhemallina k

Virhemallina kääytetytetääään n huonoimman tilaphuonoimman tilapääisen vian isen vian malli

mallin (n (malicious transient fault modelmalicious transient fault model) sijaan ) sijaan tavanomaisen tavanomaisen vvääliaikaisen vian mallialiaikaisen vian mallia ((non-non-malicious transient fault modelmalicious transient fault model) ) pitkpitkääkestoisille suorituksille vkestoisille suorituksille väähenthentäämmääään n

keskim

keskimäääärrääististää vakiinnuttamisaikaavakiinnuttamisaikaa Virheenhakukoodeilla

Virheenhakukoodeilla ((error-error-detection codes) detection codes) virheiden virheiden llööytytääminen tehostuuminen tehostuu

Jos virheenhakukoodit eiv

Jos virheenhakukoodit eiväät havaitse kaikkia t havaitse kaikkia virhemallin sallimia vikoja, voidaan k

virhemallin sallimia vikoja, voidaan kääyttyttääää tilaptilapääisen isen vian nuuskijoita

vian nuuskijoita ((transient fault detectorstransient fault detectors) ja ) ja vahtikoiralaskureita

vahtikoiralaskureita ((watchdog counterswatchdog counters) ) Esitelty

Esitelty korjausskeemakorjausskeema kkäyttäyttääää virheenhakuvirheenhaku-koodeja ja -koodeja ja pyramiditilatietorakenteita

pyramiditilatietorakenteita [Dol00, luku 5.3] [Dol00, luku 5.3]

Virheenhakukoodit ja korjaus (2/4) Virheenhakukoodit ja korjaus (2/4)

Virheenhakukoodit

Virheenhakukoodit lasketaan yksittlasketaan yksittääisen prosessorin isen prosessorin nykytilasta

nykytilasta

Talletetaan prosessorikohtaisesti Talletetaan prosessorikohtaisesti

Askeleen suorituksen alussa tarkistetaan sopiko Askeleen suorituksen alussa tarkistetaan sopiko

edellinen koodi tilaan; jos sopi

edellinen koodi tilaan; jos sopi –– jatketaan suoritustajatketaan suoritusta Tilap

Tilapääisen vian nuuskijanisen vian nuuskijan lölöydettyydettyää

sattumanvaraisen tilan prosessori laittaa sattumanvaraisen tilan prosessori laittaa

vahtikoiralaskurin

vahtikoiralaskurin ppäääällelle

Korjausskeema saa hoitaa viat pois Korjausskeema saa hoitaa viat pois

Jos viat eiv

Jos viat eiväät poistuneet skorjausskeeman t poistuneet skorjausskeeman tarvitsemassa ajassa (

tarvitsemassa ajassa (O(n)O(n)) vahtikoiralaskurin ) vahtikoiralaskurin ylyläärajalla kun nuuskinta uusittiin, nollataan taas rajalla kun nuuskinta uusittiin, nollataan taas

Aila Koponen HY/TKTL HAJALG seminaari Paikallinen stabilointi 16.11.2007

Virheenhakukoodit ja korjaus (3/4) Virheenhakukoodit ja korjaus (3/4)

¿¿Pyramiditilatietorakenne Pyramiditilatietorakenne prosessorille Pprosessorille _i ?

[Dol00, sivut 123

[Dol00, sivut 123--133]133]

∆i∆i= = V_i[0], [0], V_i[1], [1], V_i[2], ... , [2], ... , V_i[d[d] koostuu tilannekuva-] koostuu tilannekuva- eli ”eli ”snapshotsnapshot””-- nnäkymistäkymistää V_i[l[l] (] (viime viikolla: Stabiloijatviime viikolla: Stabiloijat))

ll -s-sääteinen nteinen näkymäkymää kuvaa konfiguraation topologian määkuvaa konfiguraation topologian määrittelemrittelemäälläällään n alueella eli k.o. prosessorista l

alueella eli k.o. prosessorista läähtien htien ll :n prosessorin pää:n prosessorin päähhään. n.

NäNäkymkymän muodostava algoritmi kerän muodostava algoritmi kerääää, h, häiritsemäiritsemäättttää muuta toimintaa, muuta toimintaa, prosessoreiden tilat ja viestipuskureiden sis

prosessoreiden tilat ja viestipuskureiden sisäällllöt. öt.

Erityisesti pyramidi

Erityisesti pyramidi ∆∆_i sisäsisältltääää P_i ––keskiset näkeskiset näkymäkymät t V_i[l[l] joissa nä] joissa näkymkymään ään kuuluvan prosessorin et

kuuluvan prosessorin etäisyys keskustasta on korkeintaan äisyys keskustasta on korkeintaan ll ja myja myös ös tilannekuva on otettu

tilannekuva on otettu l l aikayksikköäaikayksikköä sitten. sitten.

Pyramidin pohjalla on n

Pyramidin pohjalla on nääkymkymää koko jkoko järjestelmärjestelmääststää, jonka sä, jonka säde on siis de on siis dd..

Virheenhakukoodit ja korjaus (4/4) Virheenhakukoodit ja korjaus (4/4)

Korjausskeemassa

Korjausskeemassa oletetaan ettäoletetaan että kaikki virheet lökaikki virheet löydetydetääään n virheenhakukoodeilla

virheenhakukoodeilla Prosessoreiden k

Prosessoreiden kääyttyttöötilat: tilat:

viallinen, rajatapaus, toiminnassa viallinen, rajatapaus, toiminnassa Vian havainneet prosessorit (

Vian havainneet prosessorit (→→ viallinenviallinen) alustavat tilapyramidinsa ) alustavat tilapyramidinsa tyhjiksi ja alkavat ker

tyhjiksi ja alkavat keräämäämääään vikaantumattomilta naapureiltaan tilatietoja n vikaantumattomilta naapureiltaan tilatietoja niiden pyramideista

niiden pyramideista Naapuri on

Naapuri on viallinen, viallinen, itse ei todennut vikaaitse ei todennut vikaa →→ rajatapaus rajatapaus Rajatapaukset

Rajatapaukset odottavat kunnes odottavat kunnes viallisetvialliset ovat saaneet koostettua ovat saaneet koostettua pyramidinsa ja sitten vasta kokoavat omanssa uudestaan

pyramidinsa ja sitten vasta kokoavat omanssa uudestaan Lopuksi voidaan koostaa luotettavasti n

Lopuksi voidaan koostaa luotettavasti nääististää tiedoista ja vikaantuneen tiedoista ja vikaantuneen prosessorin omista tilasiirtym

prosessorin omista tilasiirtymääfunktioista k.o. prosessorin tiedot ennen funktioista k.o. prosessorin tiedot ennen vikaantumista

vikaantumista

Topologiatiedoista ja kierroslaskureista voidaan p

Topologiatiedoista ja kierroslaskureista voidaan päätelläätellää milloin pämilloin päivitykset ivitykset ovat ohi. Kaikki vaihtavat samaan aikaan

ovat ohi. Kaikki vaihtavat samaan aikaan toiminnassatoiminnassa -tilaan. -tilaan.

Aila Koponen HY/TKTL HAJALG seminaari Paikallinen stabilointi 16.11.2007

Viitteet Viitteet

Dol00

Dol00 Shlomi Dolev. SelfShlomi Dolev. Self--Stabilization. MIT Press, Stabilization. MIT Press, 2000.

2000.