Proiectul este de fapt un depozit online de software liber. Toți dezvoltatorii își pot plasa aici desenele și accesul la proiecte poate fi accesat de toți utilizatorii de oriunde din lume.
- Avem o bibliotecă în care există multe exemple de cod interesante în diferite limbi de programare.
Înlocuirea divizării prin înmulțirea cu Asamblatorul
Înlocuirea divizării prin înmulțirea cu Asamblatorul
Când se scriu algoritmi în asamblare care folosesc diviziunea printr-o operație constantă, operațiunile de divizare pot fi înlocuite de operații de multiplicare. Ce este necesar? Ideea este că procesorul efectuează operația de multiplicare de câteva ori mai rapid decât operația de divizare. De exemplu, multiplicarea 5-9 cicluri de procesor uzat (multiplicare semnat) sau 4-8 (înmulțirea unsigned), în timp ce nevoia de divizare 22-47 cicluri (diviziune semnate) sau cicluri (intre 17-41 diviziune unsigned). În algoritmi extrem de optimizate, cum ar fi criptarea, calcule matematice, arhivarea volumelor mari de date, calcularea checksum și a altor astfel de probleme, economisind pe fiecare ceas procesor poate oferi o creștere semnificativă a vitezei de ansamblu a programului.
În Ghidul de optimizare pentru Ghidul de optimizare a codului x86 pentru Procesorul AMD Athlon, întrebarea de înlocuire a împărțirii prin înmulțire este descrisă în detaliu. Sunt luate în considerare cazuri particulare de împărțire, cum ar fi împărțirea cu puterea a două, alegerea algoritmului pentru divizare semn și nesemnată este descrisă și este dat un cod pentru calcularea valorilor de corecție auxiliare. În plus, manualul descrie metodele de optimizare și alte operații matematice. Chiar dacă nu veți folosi niciodată înlocuirea multiplicării în practică, va fi foarte util să citiți despre alte modalități de optimizare.
Mai întâi considerăm optimizarea diviziunii întregi nesemnate. Aici există mai multe opțiuni, în funcție de valorile divizorului. Prima opțiune este dacă divizorul este în intervalul de la 1 la (231 - 1):
Tipul algoritmului, multiplicatorul și factorul de offset sunt calculate pe baza valorii divizorului. În manualul pentru aceasta sunt codul sursă al programului în C. Este intuitiv și ușor de înțeles.
A doua variantă a diviziunii nesemnate este atunci când divizorul este în intervalul de la 231 la (232-1). În acest caz, coeficientul poate avea doar două valori - 0 sau 1. În consecință, algoritmul optimizat va avea următoarea formă:
În cazul în care valoarea dividendului nu este importantă pentru calcule ulterioare, această opțiune poate fi optimizată în continuare prin refuzarea utilizării unui registru suplimentar:
În manual, apropo, în acest loc este permisă o tipografie. Textul spune despre eliminarea celui de-al doilea registru și arată imediat codul inactiv cu același registru (p. 117, dacă este interesant). Copiapastul nu este întotdeauna util. În același manual, se recomandă utilizarea unei variante cu un registru suplimentar, deși personal nu văd nici o diferență fundamentală în acest sens. Aceleași ouă, numai pe partea laterală.
În caz contrar, îmi amintesc cazuri speciale de diviziune intregi nesemnate. Numerele naturale zero nu pot fi împărțite, acest lucru este fără opțiuni, astfel încât nu se poate vorbi aici despre optimizare. Dacă împărțiți unul cu celălalt, coeficientul este întotdeauna egal cu divizibilul, și acesta trebuie să vă amintiți din banca școlii. Împărțirea în puterea a două în Assembler este optimizată folosind comanda de comutare bit la dreapta SHR reg, gradul doi:
Conform aceleiași reguli, în principiu, puteți desena și împărți câte unul, din moment ce 20 = 1.
Diviziunea semnului întreg este un pic mai complicată, pentru că atunci când obțineți rezultatul, trebuie să țineți cont de semnul divizibil și divizorul. Algoritmii de mai jos funcționează numai cu valori divizoare pozitive. Dacă divizorul este negativ, atunci modulul său este calculat mai întâi, care este utilizat în calcule ulterioare, iar comanda de asamblare NEG este aplicată rezultatului divizării rezultat. Aceasta rezultă din axiomul matematic n / -d = - (n / d). Divizorul întreg trebuie să fie în intervalul de la 2 la (231 - 1).
Ca și în diviziunea nesemnată, tipul algoritmului, multiplicatorul și factorul de părtinire se calculează pe baza valorii divizorului sau mai degrabă a modulului său. Codul sursă pentru C este în manual.
Cazurile particulare ale divizării semnate în întregime diferă și de cele nesemnate. Aici, de exemplu, împărțirea în două și gradul a două cu semne diferite.
După cum ați înțeles deja, toate optimizările de operațiuni de divizare de către o constanta cunoscută anterior sunt efectuate în stadiul de scriere a programului, mai degrabă decât să fie calculate dinamic în procesul de lucru. În caz contrar, despre ce optimizare putem vorbi? Din aceasta rezultă că nu este necesar să se utilizeze astfel de algoritmi pentru divizoare care se schimbă frecvent.
Articole similare
Trimiteți-le prietenilor: