Acest site este vizitat de oameni care nu vor contesta ideea că paralelismul ajută la îmbunătățirea performanțelor sistemului. Prin urmare, agitația în beneficiul paralelismului este omisă :-). De asemenea, nu există nici o controversă cu privire la ideea că tehnologia automată ne permite să implementăm în mod eficient diferiți algoritmi.
Strict vorbind, toate tehnologiile digitale reprezintă o realizare a teoriei automatelor digitale. Circuitele combinate sunt automate digitale cu o singură stare. Toate dispozitivele cu memorie sunt mașini digitale finite. Orice microcontroler și microprocesor este o mașină digitală cu un număr mare de state, tranzițiile în care sunt determinate de programul extern. La urma urmei, orice computer este, de asemenea, o mașină digitală cu un număr și mai mare de state.
Din nefericire, este imposibil să se implementeze algoritmi paralele pe microprocesoare și microcontrolere de consum și generale. În cel mai bun caz, se propune emularea paralelismului datorită sarcinilor de comutare rapide (pentru om). Dar atunci când comutarea sarcinilor se bazează pe priorități, nu este neobișnuit ca computerul să se blocheze în timpul procesării sarcinilor cu cea mai mare prioritate (XP-ul meu, de exemplu, crede că inserarea unui nou CD este cea mai importantă sarcină).
Dar trebuie să ne amintim că tehnologia digitală nu se limitează la microcontrolere și chiar mai mult la computere. Există încă diverse scheme, logică liberă și logică programabilă (FPGA). Folosind aceasta din urmă, este posibil, cu un minim de costuri, să se realizeze crearea unui dispozitiv cu orice arhitectură. Prin urmare, folosind toate FPGA-urile și CPLD-urile posibile, puteți crea sisteme paralele.
După cum sa dovedit astăzi, nu (sau, mai degrabă, nu am găsit) o teorie exactă și exhaustivă care descrie procesul de descriere a algoritmului paralel și a sintezei acestuia. Există diferite modalități de descriere a algoritmilor paraleli, dar nu există metode clare pentru sinteza lor ulterioară. Și dacă există, este, în principiu, tot felul de cazuri speciale sau metode care necesită costuri hardware mari.
Dar ce ne împiedică să folosim teoria veche și bună a automatelor digitale pentru a crea sisteme paralele? M-am gândit la asta înainte să intru în școala post-universitară. Gândire - și a decis să facă cercetări pe această temă. Astfel, în procesul cercetării mele voi, după cum urmează: 1) studiul teoriei existente a mașinilor digitale, 2) investigarea moduri de a descrie algoritmi paraleli, 3) un compus de 1 și 2 și 4) punerea în aplicare a celor de mai sus, în momentul inițial extins și pe dispozitive logice programabile .
Automat digital serial - comportament fizic
Ceea ce se numește de obicei "mașină automată digitală", voi numi în mod natural o mașină automată digitală serial. Se impune abrevierea OCA. Dar din moment ce eu sunt în viitor introduceți „mașini digitale paralele“ cu aceeași primă P, serial I abreviat ca CCA - „mașini digitale clasice“ (cu toate acestea, în cazul în care teoria mea va deveni clasice au pereoboznachat :-). ).
Deci, care este cea mai simplă "mașină digitală"? În primul rând, acesta este un dispozitiv digital. Prin urmare, se bazează pe logica binară. Dacă se bazează pe logica binară, întregul dispozitiv poate fi descris prin funcții booleene - conjuncții. Acțiunile sunt efectuate asupra unor operanzi. Prin urmare, o mașină digitală este un dispozitiv care procesează datele de intrare. Astfel, aparatul digital poate fi descris după cum urmează:
Starea a depinde de timpul t și de valoarea curentă a acțiunilor de intrare x (t).
Dobânda este reprezentată de ora curentă t. Strict vorbind, este măsurată în câteva secunde (mai exact, în nanosecunde). Folosind acest timp, putem distinge între sugerea stării:
Fig. Trecerea de stat
Așa cum se poate vedea în figura 3 (care, cu toate acestea, este clar fără o imagine), pentru o perioadă de timp t dispozitivul digital este în stare a. Cu toate acestea, atunci valoarea registrului de memorie se modifică în timp t. Acest timp depinde de timpul de propagare a semnalului din circuit și de viteza elementelor de memorie și logică. În acest moment, mașina este într-o stare aproape imprevizibilă. În mod firesc, în acest moment, valoarea rezultatelor va fi imprevizibilă.
Dar pentru fericirea noastră această perioadă de timp este foarte mică. Prin urmare, ele sunt de obicei neglijate și considerate condiționate nulă (cel puțin, ele nu o iau în considerare la modelarea circuitului).
Prin urmare, dacă ștergem intervalele de timp t per. primim un set de stări complet discrete ale dispozitivului. Este important pentru noi să cunoaștem sensul fizic al timpului? Nu, nu este. Prin urmare, un anumit timp 0, 1, 2, măsurat în arici, este luat în considerare :-). Cu toate acestea, atunci când creați un dispozitiv real, acești "arici" sunt luați în considerare.
La ce moment se schimba starea dispozitivului? De obicei, acesta este un semnal extern. Se spune că "funcționează" dispozitivul, "sincronizează" schimbarea stărilor sale (într-adevăr, schimbarea stărilor are loc în mod sincron pe tot dispozitivul). Prin urmare, acest semnal se numește "ceas cu impulsuri ceas". Pentru implementarea sa, generatorul de impulsuri rectangulare este de obicei realizat.
Astfel, rezumăm (figura 4). Dispozitivul digital procesează semnalele de intrare X în conformitate cu legea f (X) și emite rezultatul Y. Dacă există elemente de memorie, starea dispozitivului se modifică în conformitate cu legea. Schimbarea stărilor este inițiată de un semnal extern c.
Fig. 4 Comportamentul dispozitivului digital
Un automat digital serial este un model matematic
Pentru un model matematic dreptunghiurile, liniuțele și punctele nu sunt potrivite. Acolo este necesar să se vorbească limba formulelor.
Un dispozitiv digital, în cazul nostru, automatul digital este descris de un număr de seturi: setul de acțiuni de intrare X. Setul de semnale de ieșire Y și setul de stări A.
Setul de acțiuni de introducere este un set al tuturor combinațiilor posibile, numărul cărora este determinat de lățimea cuvântului de intrare. Toate cuvintele posibile de introducere formează alfabetul de intrare. Există situații (da, în practică, practic, se întâmplă), când nu este folosită întreaga alfabet de intrare.
Setul de semnale de ieșire este determinat de semnalele pe care mașina le emite. Aceste semnale sunt, de asemenea, descrise prin cuvinte care formează alfabetul de ieșire, care de asemenea nu poate fi utilizat pe deplin.
Setul de stări interne este un set al tuturor combinațiilor posibile de elemente de memorie internă. În cele mai multe cazuri reale nu se folosesc toate combinațiile posibile de valori ale elementelor de memorie. Această proprietate utilizează cu succes minimizarea ecuațiilor.
Din toate valorile posibile, este important să selectați starea în care automatul apare pentru prima dată. De regulă, punerea în funcțiune introduce mașina într-o stare imprevizibilă. Prin urmare, este introdus un semnal extern de resetare, care duce automat la o stare bine definită. Această stare este numită "inițială" și este de obicei marcată cu 0 (sau cu 1 - mai clasic).
În plus față de aceste seturi, este necesar să specificați două funcții - funcția de tranziție și funcția de ieșire.
Funcția de tranziție a fost deja analizată.
Funcția de ieșire descrie valoarea ieșirilor în funcție de starea curentă și parametrii de intrare curenți:
Cu toate acestea, funcția de ieșiri cu același succes poate depinde de starea anterioară. Aceasta depinde de punctul în care este generat semnalul de ieșire - înainte sau după tranziție. În cel de-al doilea caz, se obține o altă funcție de ieșire:
Deoarece este ușor de ghicit, timpul curent a (t) poate fi exprimat prin timpul precedent a (t - 1). În acest sens, formula (4) este aplicată în model.
Patru cazuri particulare sunt posibile din formula (4): 1) automatul depinde de stare și de intrări, 2) depinde numai de starea, 3) depinde numai de intrări și 4) nu depinde deloc de nimic. Cel de-al treilea caz este logica combinațională. Cel de-al doilea caz a fost numit automat Moore. Primul caz este o mașină Miles. Cel de-al patrulea caz este un generator constant.
Astfel, modelul matematic al unui automat digital clasic este descris de următorul sistem:
In acest set cu formula (5.1) descrie o multitudine de cuvinte de intrare, (5.2) - o pluralitate de semnale de ieșire, (5.3), - o multitudine de stări, (5.4) - starea inițială, (5.5) - funcția de tranziție, (5.6) - funcția O (5.7 ) - discretitatea muncii în timp.
Masina automată digitală paralelă
Și acum să încercăm să adăugăm paralelism la CCA. Cum se poate face acest lucru?
Mai întâi de toate, să examinăm matematica. Mai exact, în sistemul de ecuații (5). Ce se poate schimba acolo? Sau, dacă este mai științific, ce se poate schimba în sistem (5) pentru a asigura paralelismul și fără a distruge integritatea păstrând în același timp mașina ca o cutie neagră neschimbată? Să descifrăm ultimul gând :-).
Mașina digitală ca o cutie neagră nu ar trebui să se schimbe. Adică înlocuirea CCA cu echivalentul OCA și invers ar trebui să fie în afara celor imperceptibile (prin "echivalență" în acest caz înțelegem aceleași funcții) - interfața nu trebuie să se schimbe. În consecință, seturile (5.1) și (5.2) nu se modifică.
Conceptul PCA ca dispozitiv digital cu mai multe stări nu se schimbă. Prin urmare, (5.3) nici nu se schimbă.
Conceptul de schimbare a timpului discret nu se schimbă - (5.7) nu se schimbă.
Dacă să gândim, paralelismul în acest caz înseamnă prezența unui set al activului la un moment dat al unor condiții, spre deosebire de cel activ la CCA. Aceasta înseamnă că ecuațiile (5.4), (5.5) și (5.6) se modifică, în cazul în care o stare este activă:
Ce înseamnă (6.1)? Aceasta înseamnă că mai multe stări pot fi active la momentul momentului inițial. (6.2) înseamnă dependența setului de stări active simultane la un moment dat de setul de active la timpul discret timp și semnalele de intrare. (6.3) înseamnă dependența valorilor de ieșire de setul de stări active simultane și de semnale de intrare.
Sistemul (6) schimbă interfața aparatului digital? Evident, nu, deoarece interfața este limitată de seturile (5.1) și (5.2).
Schimbarea stărilor se face simultan (ecuația (6.2)).
Printr-un semnal extern de resetare, automatul trece la un set de stări inițiale (ecuația (6.1)).
Astfel, a fost obținut modelul OCA. Adăugarea sistemului (6) la sistem (5), precum și mai multe re-desemnări necesare, ne oferă modelul matematic al PCA:
Simbolul desemnează setul de stări active în prezent. Acest set nu poate coincide cu întregul set de stări, după cum se menționează în (7.4) (dacă acesta ar fi fost așa, a fost din nou cu privire la logica combinațională).
Sistemul (7) este suficient pentru a descrie OCA? Evident, da.
Cu toate acestea, este evident pentru computer, care operează cu abstracții matematice. Dacă luăm o sarcină (de exemplu, www.softcraft.ru/auto/ka/fil/), mă simt imediat un fel de neputinta - acest lucru este cât de mult este necesar pentru a umple o hârtie și să ia un octet la aceste seturi pentru a descrie funcționarea dispozitivului!
Dacă încercați să funcționați cu o diagramă de stare, atunci nu va fi ușor - diagrama va fi absolut ireproșabilă.
Evident, este necesar să se introducă simplificări și generalizări.
Ar fi frumos să introducem astfel de procese populare de programatori și fire cu filete, tampon de schimb, steaguri, semaphore.
Având în vedere acest lucru, voi numi acest model un "model matematic abstract". Doar "model" o voi numi una care este accesibilă unei persoane.
Toate acestea sunt destul de reale :-). În plus, la momentul redactării articolului, a existat deja un model care a funcționat (în mediul de modelare - mai mulți bani nu erau suficienți.).
Deci, avem o abstracție matematică, exprimată într-un fel sau altul - o diagramă de stare, o matrice, o tabelă de tranziție sau altceva. Ce să faci?
Luați în considerare procesul de sinteză pentru CCA.
Dacă vorbim despre logica liberă, atunci elementele de memorie sunt selectate, statele sunt codificate. Apoi, pe stările obținute, se creează o funcție de tranziție și o funcție de ieșire. Simplificarea este efectuată la nivelul funcțiilor booleene. Apoi, el a cumpărat o grămadă de elemente „AND“, „SAU“, „NU“ și declanșează un decodor și totul este sigilat într-un mic monștri :-).
Din fericire, există o modalitate mai convenabilă (dar nu mai ieftină) de a utiliza dispozitive logice programabile. Una dintre limbile de descriere hardware este Verilog sau VHDL (la momentul redactării, alte limbi populare nu au fost încă disponibile), descrie comportamentul dispozitivului, testează și depanează, sintetizează și este în cele din urmă implementat. Întregul proces durează mult mai puțin timp decât cel precedent.
Toate acestea se aplică la OCA. Se fac aceleași acțiuni, cu excepția formulelor și a listelor care se obțin mult mai mult. Dar codul poate fi, de asemenea, sintetizat și implementat.
Este necesar să observăm un astfel de detaliu. FPGAs moderne sunt proiectate pentru sinteza automatelor digitale - acestea au câteva linii de ceas și reset, care este mai scurt decât celelalte linii, precum și hrănite în mod direct la elementele de memorie. În legătură cu aceasta, sinteza unor astfel de dispozitive este simplificată într-o oarecare măsură. Acest lucru este, de asemenea, disponibil pentru OCA.
În această lucrare, am considerat un model matematic abstract al PCA, care poate fi sintetizat. Complexitatea procesului de sinteză nu este mai mare decât sinteza CCA.
Un automat digital este un concept familiar pentru un dezvoltator de dispozitive digitale. În consecință, utilizarea PCA este mult mai ușor de înțeles și mai simplu decât utilizarea, de exemplu, a unor plase Petri.
Sunt planificate alte articole, care vor evidenția studiile ulterioare.
Trimiteți-le prietenilor: