Arhitectura sistemelor de calcul

CAP. I Introducere

Maşina Turing

Primul model abstract de P.C. a fost introdus în 1986 de către matematicianul englez Allan Turing. Acest model a fost cunoscut sub numele de MAŞINĂ TURING (MT). Turing a pornit de la definiţia de calcul care în general reprezintă o evaluare a unei funcţii f(x) unde x reprezintă datele de intrare obţinându-se la ieşire rezultatul: z = f(x) , unde z reprezintă datele de ieşire; x şi z pot avea diverse semnificaţii putând fi numere, cuvinte, fişiere de date, etc.

A evalua o funcţie f(x) folosind un calculator înseamnă a putea exprima f ca o succesiune de funcţii f1,…,fn cu ajutorul setului de instrucţiuni al calculatorului, fiecare funcţie intermediară fi conţinând o întreagă secvenţă de instrucţiuni (setul de instrucţiuni al unui calculator reprezintă setul de funcţii elementare pe care le poate realiza un calculator).

- funcţiile f1,…fn pot fi văzute ca un program de evaluare a lui f(x);

- secvenţa de operaţii elementare y1 = f1(x); y2 = f2(y1); … yn-1 = fn-1(yn-2); yn = fn(yn-1) = z reprezintă definiţia formală a operaţiilor de calcul a lui f(x).

Maşina Turing are două componente principale: procesorul şi memoria maşinii Turing. Procesorul M.T. este un sistem digital, secvenţial, cu număr finit de stări . Memoria M.T. este o bandă de lungime infinită împărţită în locaţii de memorie, locaţii care pot fi goale sau care pot conţine un set continuu de simboluri. M.T. are un cap de citire/scriere cu ajutorul căruia procesorul poate citi simbolurile din locaţia de memorie aflată în dreptul capului sau poate rescrie locaţia respectivă din dreptul capului sau poate muta memoria o locaţie la stânga sau la dreapta faţă de poziţia curentă.

M.T. are un set finit de instrucţiuni (datorită numărului de finit de stări ale procesorului) instrucţiuni care au următorul format: sh, ti, oj, sk. Dacă procesorul P se găseşte în starea sh şi în dreptul capului de citire/scriere se află simbolul ti atunci procesorul P execută operaţia oj şi va trece în starea sk. Operaţia oj poate fi una din următoare patru operaţii:

1) Scriere: oj = tj → procesorul va scrie în locaţia curentă simbolul tj.

2) R (right) → procesorul va muta capul de citire/scriere la dreapta o poziţie ceea ce poate însemna mutarea benzii de memorie la stânga o poziţie.

3) L (left) → procesorul va muta capul de citire/scriere la stânga o poziţie ceea ce poate însemna mutarea benzii de memorie la dreapta o poziţie.

4) H (halt) → M.T. se opreşte.

În aceste condiţii, operaţia de calcul z=f(x) va fi executată de M.T. în mai mulţi paşi succesivi astfel:

1. Datele de intrare X sunt aduse în dreptul capului de citire/scriere .

2. M.T. generează secvenţa de funcţii f(i), i={1,…,n} fiecare dintre acestea conţinând câte o secvenţă de instrucţiuni din setul de instrucţiuni.

3. Se înregistrează în locaţia din dreptul capului de citire/scriere rezultatul z.

Limite ale maşinii Turing(TM) şi ale calculatoarelor reale

1. Există probleme care nu se pot rezolva cu maşina Turing şi implicit nici cu calculatorul real.

Def: O funcţie este efectiv calculabilă cu MT dacă f(x) poate fi evaluată într-un număr finit de paşi de către o MT oricare ar fi datele de intrare.

Def: O MT, M cu datele de intrare X, notată (M,X) se spune că „se opreşte” dacă MT se opreşte după un număr finit de paşi. Se va arăta că există funcţii raţionale ce nu pot fi calculate cu o maşină Turing.

Fie funcţia fH(M,X) care are următoarele valori:

Se poate arăta că fH nu se poate calcula, ceea ce înseamnă că nu se poate determina o metodă generală prin care să se cunoască aprioric dacă MT se opreşte sau nu oricare ar fi M şi X.

Ex: o eroare în programare poate genera bucle infinite şi deoarece problema opririi MT nu are soluţie rezultă că nu poate fi creat un program universal care să poată depista aceste erori de programare.

2. Există probleme care se pot rezolva cu MT şi nu pot fi rezolvabile cu calculatoarele reale. Chiar dacă procesorul MT are un număr finit de stări şi implicit MT are un set finit de instrucţiuni, banda de memorie a MT are un număr infinit de locaţii de memorie şi deci MT este o maşină cu stări infinite. Calculatoarele reale au un număr finit de locaţii de memorie (sunt maşini cu stări finite) şi nu pot lucra cu numere oricât de mari, de aceea toate problemele care lucrează cu numere mari pot fi rezolvate doar cu MT. Ex: MT poate înmulţi 2 numere oricât de mari.

3. Există probleme care sunt rezolvabile cu calculatoarele rele într-un număr finit de paşi dar care practic nu se pot rezolva deoarece necesită fie o cantitate prea mare de spaţii de memorie, fie un timp de calcul prea lung.

Fie o problemă ce se poate rezolva cu un algoritm A, care trebuie rezolvată de calculator. Referitor la dificultatea algoritmului A apar două întrebări:

a) ce spaţiu de memorie este necesar pentru rezolvarea algoritmului

b) cât timp este necesar pentru rezolvarea algoritmului

Cele două mărimi depind de mărimea datelor de intrare. Cel mai restrictiv este timpul de execuţie şi de aceea se va introduce complexitatea de timp a unui algoritm ca o măsură a numărului de paşi necesari pentru rezolvarea algoritmului.

Def: Un algoritm are complexitatea de timp a(f(n)), dacă numărul de paşi necesari pentru rezolvarea algoritmului este p = c•f(n), unde

c = o constantă, f = o funcţie de dimensiunea datelor de intrare, n.

Dimensiunea datelor de intrare, n, reprezintă numărul parametrilor de intrare independenţi.

Ex: Fie un algoritm a(n2)

Def: O problemă este tratabilă cu un anumit calculator dacă ea poate fi rezolvată exact (într-un număr finit de paşi) într-o cantitate de timp rezonabilă, oricare ar fi n.

Teoremă: O problemă este tratabilă dacă şi numai dacă există un algoritm de tratare a ei, care are complexitatea de timp a(p(n)), unde p = funcţie polinomială; reciproc: o problemă nu este tratabilă dacă toţi algoritmii de rezolvare a ei au complexitatea de timp a(kn) ceea ce înseamnă că necesită un timp de execuţie care creşte exponenţial cu dimensiunea datelor de intrare.

Ex: Fie datele de intrare reprezentând un fişier de date de dimensiune n şi algoritmul de rezolvare a unei probleme execută asupra fiecărei date din fişier toate operaţiile realizate înaintea ei plus încă două operaţii suplimentare pentru data respectivă. Prima dată necesită două operaţii.

Complexitatea de algoritm este a(2n) şi problema este netratabilă.

Dacă o problemă nu este tratabilă, atunci ea va putea fi rezolvată exact într-un timp rezonabil doar dacă dimensiunea datelor de intrare este ≤ cu o valoare maximă, „m”. Valoarea lui m depinde de viteza de lucru a calculatorului care rezolvă problema, viteză notata s [operaţii/secundă]. Cu cât viteza calculatorului este mai mare cu atât m va fi mai mare, dar creşterea este direct proporţională cu toţi algoritmii.

Limitări ale vitezei de calcul

Creşterea vitezei de calcul s-a făcut prin perfecţionarea tehnologiilor de fabricaţie a unităţilor de memorie şi a circuitelor de comutaţie. Perfecţionarea tehnologiilor a condus la o creştere medie a vitezei de calcul de 100 ori pentru fiecare decadă în ultimii 50 ani. În realitate rata de creştere, s, nu este constantă (rata de creştere a tehnologiei) ci este în scădere; deci viteza de calcul va trebui să crească în continuare nu numai pe baza tehnologiei ci şi prin îmbunătăţirea algoritmilor de calcul sau a procedurilor euristice. Pentru rezolvarea unor probleme netratabile au fost dezvoltate metode inexacte şi metode nonalgoritmice.

Metoda inexactă presupune înlocuirea problemei Q netratabilă care trebuie rezolvată cu Q’ tratabilă, a cărei soluţie aproximează soluţia lui Q.

Metoda nealgoritmică analizează un set mic de soluţii posibile ale lui Q folosind anumite metode şi criterii intuitive de selecţie şi soluţia cea mai bună din cele analizate este considerată soluţia lui Q.

Metoda prin care se obţine o soluţie acceptabilă dacă nu optimală într-un timp de calcul se numeşte procedură euristică.

Limita fizică posibilă a vitezei de calcul

Folosind metode bazate pe mecanica cuantică, H.I. Bremermann a determinat că nici un sistem de calcul (virus sau artificial) nu poate procesa mai mult de 2•1047 biţi/gram din masa sa/sec.

Ex: în aceste condiţii un calculator de dimensiunea pământului (6•1027g) operând continuu o perioadă egală cu vârsta pământului (1020 ani) ar putea procesa mai puţin de 1093 biţi.

Def: Calculatorul este un sistem electronic digital programat intern care are asociat un software de bază necesar operării, întreţinerii şi folosirii eficiente de către utilizator.

Orice calculator are două componente majore:

- „hardware” = toate subsistemele componente ale unui calculator şi modul de interconectare al acestora;