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

lucian.vintan@ulbsibiu.rohttp://webspace.ulbsibiu.ro/lucian.vintan/

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)

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

� 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)( =∀→

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%

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

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

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

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

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

� 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”?

� 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

� 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!

∈∈

� 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

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∀

� 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 ∈∃∈∀ ,

� 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!

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

� 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ă?

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)

�

�

�

� 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 ∈⋅=

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

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

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

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.

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.

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!