De la predicţia salturilor condiţionate la o problemă...
Transcript of De la predicţia salturilor condiţionate la o problemă...
![Page 1: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/1.jpg)
De la predicţia salturilor condiţionate la o problemă
ştiinţifică fundamentală şi…dincolo de ea
Curs festiv, Promoţia “Calculatoare”16 mai, 2008
Prof. Lucian VINŢAN
Catedra de calculatoare, Universitatea “Lucian Blaga”, Str. Emil Cioran, No. 4, 550025 Sibiu, Romania
[email protected]://webspace.ulbsibiu.ro/lucian.vintan/
![Page 2: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/2.jpg)
Scurtă recapitulare: branch prediction
� Necesitatea predicţiei dinamice adaptive� Predictoare state of the art (markoviene,
neurale, hibride)� Câteva probleme actuale:
� Salturi/apeluri indirecte registru (OOP, virtual machine systems; Intel Pentium M)
� 28% LD_miss/BRANCH (LVP, addr_correlation, SMT…)
� Branch-uri nepolarizate având comportare “aleatoare”? (1999-Milano, 2006-China, 2007-Korea)
![Page 3: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/3.jpg)
Ce sunt branch-urile nepolarizate?
� S={S1, S2, …, Sk} = set of distinct contexts that appear during all branch instances;
� k = number of distinct contexts, k≤2p, where p is the length of the binary context;
� , and obviously ;
� if then the context Si is completely biased (100%);
� if then the context Si is totally unbiased.
<≥
==5.0,
5.0,),max()(
01
0010 ff
ffffSP i
,...,,2,1)(,1)( kiSP i =∀=
,...,,2,1)(,5.0)( kiSP i =∀=
NTT
NTf
NTT
Tf
+=
+= 10 , 110 =+ ff
![Page 4: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/4.jpg)
� nt = the number of branch outcome transitions, from (0�1 or 1�0), in a certain context Si;
� = maximum number of possible transitions;
� if , then the behavior of the branch is totally shuffled;
� if , then the behavior of the branch in context Si is constant.
Ce e un… Shuffled Dynamic Branch?
>⋅
==
0,),min(2
0,0
)(t
t
t
i nTNT
n
n
SD
),min(2 TNT⋅
kiSD i ...,,2,1)(,1)( =∀→
kiSD i ...,,2,1)(,0)( =∀→
![Page 5: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/5.jpg)
O clasă de branch-uri impredictibile?
� Hard-to-Predict Dynamic Branch= [Unbiased_Branch] AND [Shuffled Branch]
� [P(Si)<0.95] AND [D(Si)>0.2] �Prediction accuracy<~75%
![Page 6: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/6.jpg)
Reducerea nr. de unbiased branches prin extensia contextului
0
5
10
15
20
25
30
16 bits 20 bits 24 bits 28 bits
Feature Set Length
Dyn
amic
Unp
olar
ized
Con
text
s [%
] LH
GH
![Page 7: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/7.jpg)
INTEL Championship Branch Prediction Competition (CBP-2), Orlando, Florida, USA, (2006), http://camino.rutgers.edu/cbp2/
Prediction accuracies obtained using state-of-the-art branch predictors
77.30%
60%
65%
70%
75%
80%
85%
bzip gzip mcf parser tw olf Average
Benchmark
Pre
dic
tio
n a
ccu
racy Local PPM
Global-Local PPM
Multiple Markov
Perceptron
Piecew ise
Frankenpredictor
O-GEHL
![Page 8: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/8.jpg)
Reduction of average percentages of unbiased branches by adding new information (PATH, PBV)
15%
20%
25%
30%
35%
40%
45%
50%
p=1 p=4 p=8 p=12 p=16 p=20 p=24
Context Length
Unb
iase
d C
onte
xt In
stan
ces
GH (p bits)
GH (p bits) + PATH (p PCs)
GH (p bits) + PBV
![Page 9: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/9.jpg)
Piecewise linear branch predictor using the previous branch’s value
PC
Selected Perceptron
Selected LHR
Local BranchHistory Table
Prediction
LH
Table of Perceptrons
GHR
GH
PBV
PBVPC
Selected Perceptron
Selected LHR
Local BranchHistory Table
Prediction
LH
Table of Perceptrons
GHRGHR
GH
PBVPBV
PBV
![Page 10: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/10.jpg)
Piecewise linear branch predictors: results
Prediction accuracy on all branches vs. unbiased branches
94.92%95.45%
77.30% 78.30%
75%
80%
85%
90%
95%
PW-J
imen
ez
PW_L
BD_8590
wPW
_LBD_12
530w
PW_L
BD_1572
0wPW
_LBD_20
573w
PW_L
BD_3071
3w
Different size perceptron-based predictors
all_branches
unbiased
![Page 11: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/11.jpg)
� Ce înseamnă aleator?� În particular, ce înseamnă un şir binar
aleator?� 01010101010101010101010...� 01101010000010011110011...
� Se poate da o definiţie matematicăintrinsecă, ontologică, a unui şir aleatorde simboluri?
� Poate genera rularea unui programdeterminist secvenţe "aleatoare"?
� Pentru şiruri de simboluri nu se poate definidecât gradul de aleatorism, diferenţa întrealeator şi non-aleator fiind deci una vagă.
Ce e o secvenţă “aleatoare”?
![Page 12: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/12.jpg)
� Pentru orice n, blocurile de n termeni dinşir au aceeaşi probabilitate P de apariţie înşir. Alfabet de m simboluri � P = 1/mn.
� Aproape toate numerele reale, scrise înreprezentare zecimală infinită, sunt aleatoare.
� Definiţia lui Borel nu este constructivă(efectivă), în sensul permiterii generării deşiruri aleatoare.
� [Problemă deschisă: constantelematematice transcendente sunt Borel-normale?]
Definiţia aleatorului după Borel
![Page 13: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/13.jpg)
� f:QxS�QxSxM� TMt(x)={q(t), s(t); q(t+1), s(t+1), m},
m M={L,R} // Instructiune� Q={q0q1q2 … qf}, s S={0,1,blank}
� Secvenţa de intrare x aparţine mulţimiituturor secvenţelor binare finite (FB –Finite Binary).
� O TM defineşte o funcţie parţială amulţimii FB pe ea însăşi �
algoritm=procesare de simboluri pe o TM.
Maşina Turing redivivus!
∈∈
![Page 14: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/14.jpg)
� Pentru orice algoritm (procedură care se termină într-un număr finit de paşi) există o maşină Turing echivalentă. � Algoritm=TM
� Noţiunea de algoritm impune ca acesta să poată fi implementat pe o maşină Turing. Cu alte cuvinte, dacă un calculator poate implementa un algoritm acesta poate fi implementat şi de o anumită maşină Turing.
Conjectura Church-Turing
![Page 15: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/15.jpg)
Mulţimea tuturor maşinilor Turing este numărabilă
• Definiţia noţiunii de numărabil; Paradoxuri ale infiniţilor actuali.• Justificare: se poate trece de la mulţimea maşinilor Turing cu k instrucţiuni (TMk) la cea a celor cu (k+1) instrucţiuni (TMk+1), =3,4,5... � TMk este numărabilă. Evident că în cadrul unei mulţimi TMk există un număr finit de maşini Turing � mulţimea tuturor TM este numărabilă, Q.E.D.
k∀
![Page 16: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/16.jpg)
� O funcţie parţială f:N�N este „Turing-calculabilă”dacă cu n=c(x) pentru care maşinase opreşte generând la final codificarea binară a lui nprin funcţia c: f(n)=c(TM(x)).
� Cum mulţimea TM este numărabilă � mulţimeafuncţiilor parţiale Turing-calculabile este şi eanumărabilă. Această mulţime aparţine mulţimiituturor funcţiilor parţiale f:N����N, care estenenumărabilă (fiind practic izomorfă cu mulţimeanumerelor reale).
� Rezultă că funcţiile calculabile sunt infinit-puţine(cardinal alef 0) � Funcţiile non-calculabile suntinfinit-majoritare!
Funcţiile Turing-calculabile sunt “infinit-puţine”!
FBxNn ∈∃∈∀ ,
![Page 17: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/17.jpg)
� Orice şir binar aleator, NU ar trebui să fie generatprintr-o funcţie parţiala Turing-calculabilă. (Existăsecvenţe necalculabile de simboluri care nu sunt, totuşi,aleatoare!)
� Asociind secvenţele aleatoare cu funcţiile parţiale carenu sunt Turing-calculabile � aceste secvenţealeatoare sunt nenumărabile (de putereacontinuului), deci infinit-majoritare pe mulţimeatuturor funcţiilor parţiale f:N�N.
� Aşadar: secvenţele deterministe sunt numărabile,cele aleatoare sunt nenumărabile!
� Deşi riguroasă, definiţia nu e efectivă � eşec practic!
Aleatorul e majoritar dar nu-l putem exprima!
![Page 18: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/18.jpg)
Bazate pe:
� Predictibilitatea Hidden Markov Models(HMM, L. Rabiner)
� Entropia discretă a secvenţei� Rata de compresie a secvenţei (Huffman,
Gzip etc.). O secventă aleatoare eincompresibilă.
� Complexitatea Kolmogorov a coduluigenerator al secvenţei de simboluri
Definiţii neriguroase, dar mai practice, ale gradulul de aleatorism
![Page 19: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/19.jpg)
� A HMM is a doubly embedded stochasticprocess with a hidden stochastic processthat can only be observed through anotherstochastic process - that generate thesequence of observable symbols.
� Our hypothesis: HMMs could compensaterelevant information miss-knowledgethrough its underlying stochastic processthat is not observable.
Predictibilitatea HMM – o limită ultimativă?
![Page 20: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/20.jpg)
Predicţia “celui mai performant HMM” (R=1, N=2)
98.43%
65.03%
40%
50%
60%
70%
80%
90%
100%
bzip
gcc
gzip
mcf
parse
r
twolf
Avera
ge
SPEC 2000 Benchmarks
Pre
dict
ion
Acc
urac
y [%
]
Biased (R=1, N=2)
Unbiased (R=1, N=2)
![Page 21: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/21.jpg)
�
�
�
� Max_RD(Binary_string)=1 (100%, complet aleator)
� 01010101010101... maximizes both D and E but…
Entropia discretă a secvenţei
∑=
≥−=k
i
XiPXiPSE1
0)(log)()(
>⋅
==
0,),min(2
0,0
)(t
t
t
i nTNT
n
n
SD
]log,0[)()()( 2 kSESDSRD ∈⋅=
![Page 22: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/22.jpg)
Gradul de aleatorism: biased vs. unbiased branches
Random Degree
9.16%
40.00%
0%
10%
20%
30%
40%
50%
60%
70%
gzip gcc mcf parser bzip2 twolf Average
SPEC 2000 Benchmarks
RD Biased
RD Unbiased
![Page 23: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/23.jpg)
Rata de compresie a secvenţei
90,37%
83,78%
19,15%
5,52%
-10%
10%
30%
50%
70%
90%
gzip gcc mcfparse
r
bzip2
twolf
Avera
ge
SPEC 2000 Benchmarks
Sp
ace
savi
ngs
Gzip_Biased
Huffman_Biased
Gzip_Unbiased
Huffman_Unbiased
![Page 24: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/24.jpg)
Permute (int n){int k;pctr = pctr+1;if(n != 1) # the first branch instruction analyzed (PC=35) BIASED (predictibil){Permute(n-1);for( k = n-1; k >= 1; k--)# the second analyzed branch (PC=58) UNBIASED!{
Swap(&permarray[n], &permarray[k]);Permute(n-1);Swap(&permarray[n], &permarray[k]);
}}
}K(Br_58) = Minimum 42 HSA instructions or 8 C instructions.K(Br_35) = 12 HSA instructions or 3 C instructions
���� K(Br_58)> K(Br_35)
“Complexitatea Kolmogorov” a codului generator
![Page 25: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/25.jpg)
Concluzii(I)
� Nu există o paradigmă eficientă pt.aleatorismul unei secvenţe (şir).
� Predicţia eficientă a branch-urilor nepolarizate:o problemă deschisă (spaţiu de gradsuperior, convenabil reprezentării problemei �predictor eficient)
� Gradele de aleatorism intrinsec - de mareajutor pentru ansamblul arhitectură-compilator(predictor improvement). Gradul de haosdeterminist.
![Page 26: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/26.jpg)
Concluzii(II)
� Creşterea complexităţii proiectelor (objectoriented programs, design patterns, complexprojects management, etc.) � creşterea nr. deunbiased branches
� Influenţa acestor branch-uri în arhitecturilemulti-thread si many-core e o problemăimportantă si deschisa.
� Arhitectura calculatoarelor nu poate fiînţeleasa profund fără ajutorul teorieialgoritmilor (calculabilităţii), teoriei informaţiei,teoriei proceselor stohastice, învăţării automateetc.
![Page 27: De la predicţia salturilor condiţionate la o problemă ...webspace.ulbsibiu.ro/lucian.vintan/html/Curs_festiv_2008.pdf · matematice transcendente sunt Borel-normale?] Definiţia](https://reader030.fdocumente.com/reader030/viewer/2022040720/5e2b174b96e8d72cf063595b/html5/thumbnails/27.jpg)
Concluzii(III)
• Acest curs a prezentat o aventurăeşuată, dpdv utilitar!
• Care este scopul ultimativ al ŞTIINŢEI şi al TEHNOLOGIEI?
• Utilitar?• Cognitiv?
• Estetic?! Etc.• Scopul ultimativ, esential, al stiintei il
constituie onoarea spiritului uman!