Facultatea de Automatica si Calculatoare , UPB



Implementare

BLAS (Basic Linear Algebra Subprograms)

folosind FINMATH

Dinu Mirela 342 C2

Facultatea de Automatică şi Calculatoare

Universitatea Politehnica Bucuresti

Cuprins

1. Abstract ……………………………………………..3

2. Introducere …………………………………………3

3. Noţiuni introductive ……………………………..4

4. Rezultate……………………………………………..6

5. Concluzii şi recomandări ……………………….11

6. Bibliografie ………………………………………….12

7. Anexe………………………………………………….13

1. Abstract

Lucrarea de faţă vine cu o nouă implementare a legendarului BLAS, folosind de data aceasta FINMATH, bibliotecă dezvoltată de cei de la Fintronic ().

Se urmăreşte prin această lucrare posibilitatea de a implementa operaţii aparent complexe (matrice-vector) la nivel de cod sintetizabil, cu alte cuvinte direct in hardware ! Într-o primă fază a proiectului, au fost « «traduse » rutinele BLAS folosind Verilog-ul « altoit » al celor de la Fintronic, urmând ca pe viitor, proiectul să ia amploare, ajungând în ipostaza de a implementa hardware transformata Z, de a genera seturi de test pentru modulele astfel realizate,etc.

Cuvinte cheie : BLAS, FinMath, FinSim, verilog, VP, precizie mare

2. Introducere

Lucrurile nu stau niciodată pe loc, din totdeauna se doreşte avansarea, îmbunătăţirea la orice nivel , iar domeniul tehnic bate recordul la viteza cu care înaintează în stabilirea unor noi performanţe.

Scrise iniţial in 1978 , codurile sursă BLAS (Basic Linear Algebra Subprograms) au drept scop îmbunătăţirea calculelor la nivelul algebrei lineare. Rutinele implementate de BLAS lucreză cu blocuri – module standard care realizează operatii de bază la nivel de matrice – vector .

FinMath, pe de altă parte urmăreşte acelaşi lucru : realizarea operaţiilor de bază sau/şi mai complexe la nivel matrice-vector astfel încât să poată fi implementate direct in cod sintetizabil .

FinSimMath permite efectuarea unui număr foarte mare de task-uri de sistem matematice, şi asigură acces la informaţii referitoarea la depaşirea numărului de biţi (overflow, underflow), numărul de biţi necesari.

Prin acest proiect, am încercat s-a încercat combinarea BLAS cu FinSimMath în scopul de a obţine ceva cu o finalitate bine definită, performant, dar mai ales util !

3. Noţiuni introductive

Rutinele BLAS se împart în 3 nivele :

- rutine BLAS de nivelul 1 : asigură blocuri standard pentru efectuarea de operatii la nivel de bază între vectori si matrice. BLAS la nivelul 1 efectuează operaţii între scalari, vectori şi vector-vector

- rutine BLAS de nivelul 2 : efectuează operaţii la nivel de matrice-vector

- rutine BLAS de nivelul 3 : efectuează operaţii între matrice

Deoarece rutinele BLAS sunt eficiente, portabile şi disponibile oricui, acestea sunt folosite în mod comun în dezvoltarea unor aplicaţii software de mare performanţă în algebra lineară, cum ar fi LAPACK de exemplu. Sursele BLAS sunt gratuite, sunt disponibile pe site-ul :

Una din caracteristicile ce fac sursele BLAS cât mai accesibile şi uşor de prelucrat este faptul că orice modificare şi îmbunătăţire este comentată detaliat, împreună cu data şi numele autorului. Astfel este imposibil să te pierzi printre sursele lor. O variantă mai nouă, scrisă în C este disponibilă pe acelaşi site.

Pe de altă parte, conceperea FinSimMath a avut o motivaţie extrem de puternică în spate : nevoia de a dispune de o modelare matematică în cadrul limbajului Verilog. Conform celor de la fintronic, limbajul FinSimMath a fost creat pentru a îndeplini următoarele scopuri :

1) Nici o funcţie de conversie explicită nu mai este necesară

2) Sunt permise schimbari ale formatelor numerelor , incluzând chiar a numărului de biţi ale câmpurilor

3) Informaţia stocată în matrice este foarte uşor de accesat la nivel global

FinSimMath este o extensie a limbajului Verilog IEEE std 1364 care suportă de altfel şi tipuri de variabile precum VpDescriptor, VpReg, VpComplex, VpPolar, VpFComplex, VpFPolar. Operatori logici, aritmetici şi de atribuire sunt definiţi pentru a efectua operaţii pe toate combinaţiile posibile între aceste tipuri, incluzând vectori şi matrice.

FinSimMath aduce nou obiectele, operatorii VP (Variable Precision) şi permite combinarea Verilogului pur, ca limbaj principal de programare cu obiectele şi funcţiile VP (Variable Precision). Astfel, este permisă orice combinaţie între următorii operatori :

|VP |Precizie arbitrară în virgulă mobilă / fixă |

|Verilog |Regiştrii |

| |Variabile Reale /întregi |

| |Constante admise |

Avantajele FinSimMath sunt evidente :

➢ Integrarea în Verilog/ System Verilog a posibilităţii de a alege precizia variabilei în virgulă fixă / mobilă

➢ Conversie implicită şi directă între obiecte care folosesc formate diferite

➢ Overhead redus în comparaţie cu alte limbaje

➢ Sintaxa intuitivă, derivată din limbajul Verilog reduce drastic timpul de învăţare

➢ Ideal pentru estimarea valorii de vârf a DSP (Digital Signal Processor)

➢ Oferă optimizare realistă a lungimii cuvintelor

Pe scurt, FinSimMath implementează operaţii la nivel artimetic, trigonometric, hiperbolic, logaritmic şi puteri, exponenţial direct în Verilog. Prin urmare, FinSimMath reprezintă o unealtă puternică putând fi folosită în domenii precum : DSP, procesoare, sisteme Embedded, aplicaţii militare , design IC .

Obiectele de precizie variabilă precum tipurile VpReg, VpComplex, and VpPolar pot avea propriile formate (fixe sau mobile) precum şi dimensiuni ale formatului modificabile în timpul rulării.

Acest lucru permite existenţa unei bucle restrânse în găsirea formatele optime şi a dimensiunilor acestor, luând în calcul costuri variabile care au drept cauză acurateţea calculului, evitarea overflow-ului, zgomotul de cuantizare, consumul de putere (în timpul comutării mai ales) sau alte constrângeri de resurse.

Scrierea globală într-o matrice, precum şi citirea dintr-un vector multidimensional sunt permise de FinSimMath folosind taskuri de poziţie pentru fiecare element al matricei prin instrucţiunile $InitM şi $PrintM.

O formă generală de atribuirea unui alias, folosind poziţionarea taskurilor la nivel de element în matrice, se poate face şi la nivel de dimensiune în cadrul unui vector multi-dimensional. Pentru aceasta este folosit constructorul View, care are drept scop separarea informaţiilor de zona de memorie ocupată (locaţie).

Este de asemenea, disponibil un bogat repertoriu mathematic la nivel de funcţii de sistem şi taskuri, acesta incluzând : $VpSin, $VpCos, $VpTan, $VpCtan, $VpAsin, $VpAcos, $VpAtan, $VpActan, VpSinh, $VpCosh, $VpTanh, $VpCtanh, $VpAsinh, $VpAcosh, $VpAtanh, $VpActanh,$VpPow, $VpPow2, $VpLog, $VpLn, $VpAbs, $VpFloor, $VpHypot, $Fft, $Ifft, $Dct, $Idct, etc.

4. Rezultate

Proiectul este la încă în faza incipientă, fază deseori numită “copilăria” unui proiect, în care “joaca” este definitorie. Astfel, rând pe rând m-am jucat cu rutinele implementate de BLAS, testându-le şi înţelegând codul.

BLAS vine cu o implementare puternică în Fortran, şi ulterior în C , fiind disponibil pentru o varietate de sisteme de operare precum : ALPHA, HPPA, LINUX, SGI64, SUN4, SUN4SOL2 sau versiune proprie (caz în care fişierele de makefile trebuiesc adaptate).

Pe de altă parte, FinSimMath vine cu un tutorial propriu, schiţat în linii mari, care are rolul nu atât, de a epuiza conceptul de programare VP Verilog , cât cu scopul declarat, de a ghida utilizatorul în a păşi singur şi cu încredere pe drumul codării la nivel hardware.

Tutorialul este disponibil de pe site-ul companiei, la adresa : . Limbajul VP Verilog este destul de intuitiv pentru a asigura o stăpânire rapidă a conceptelor şi a sintaxei folosite. Prin urmare, am luat sursele scrise în Fortran , le-am » tradus » în FinMath , şi utilizând FinSim – tool disponibil tot de la cei de la Fintronic, le-am testat.

Mai jos, este prezentat un exemplu din rutinele BLAS (de nivel 1, deocamdată) implementat în FinMath. Prima rutină din BLAS , nivel 1, se numeşte CAXPY, şi are drept rezultat adunarea unui vector cu un alt vector înmulţit cu o constantă. Mai exact, prin apelul subrutinei CAXPY(N,CA,CX,INCX,CY,INCY), se obţine CY + CX * CA .

Se observă cu uşurinţă că, dacă varianta BLAS a funcţiei CAXPY lucrează la nivel de vectori unidimensionali, varianta implementată cu FinMath poate performa aceleaşi operaţii atât la nivel de vector, cât şi de matrice.

Pe de altă parte, subrutina CAXPY scrisă în Fortran, este de dimensiuni destul de mari, ocupând la nivel de cod aproximativ 25 linii, pe când în FinMath lucrurile stau extrem de simplu. Modulul de mai jos este de fapt implementat cu scopul de a testa funcţionalitatea rutinei, care în FinMath ocupă efectiv un singur rând, şi anume :

$InitM(RX, CY[$I1][$I2] + (ct * CX[$I1][$I2]));

Pentru o comparaţie mai bună am pus cele două coduri în paralel, urmând a discuta linie cu linie , modulul VPCaxpz.v implementat in FinMath.

Declararea modulului este specifică limbajului Verilog, folosind cuvintele cheie « module« , respectiv « endmodule«  

module VPCaxpy;

Parametrii specifici procedurii CAXPY sunt numărul de linii, numărul de coloane şi constanta cu care se înmulţeste prima matrice. Pentru a lucra cu vectori unidimensionali numărul de linii, respective numărul de coloane este 1. De asemenea, pentru a putea face adunarea celor 2 matrice,dimensiunile acestora trebuie să fie identice.

Acest lucru nu trebuie neapărat verificat , deoarece în caz nefavorabil (dimensiuni ale matricelor diferite), FinSim dă eroare la rulare, specificând clar şi cauza care o determină. Parametrii se declară fix ca în Verilog, folosind cuvântul cheie « parameter« , numele variabilei , precum şi valoarea acesteia.  

parameter NLIN = 3;

parameter NCOL = 2;

Constanta cu care se înmulţeşte prima matrice, poate fi de tip real sau întreg, FinMath supotând operaţii între numere reale/întregi şi matrice /vectori.

real ct ;

Argumentele de tip tablou ale rutinei CAXPY sunt cele două matrice/vectori. Sunt declarate folosind parametrizat numărul de linii şi de coloane.

Astfel, pentru a schimba dimensiunile matricelor/ vectorilor este suficient a se umbla la parametrii iniţiali ai modulului.

real CX[NLIN-1:0][NCOL-1:0];

real CY[NLIN-1:0][NCOL-1:0];

real RX[NLIN-1:0][NCOL-1:0];

În faza iniţială, bloc care se execută la începutul rulării (momentul de timp 0), sunt iniţializate variabilele. Pentru testare, am ales valoarea constantei 2, iar cele 2 matrice au fost iniţializate după modelul lui Pascal.

Mai concret, pe laturile exterioare din stânga au valoarea 1, iar celelalte elemente sunt date de suma elementelor care le incadrează la dreapta (un fel de sumă pe diagonală).

Funcţia pusă la dispoziţie de FinMath, $InitM primeşte ca parametru matricea de iniţializat, precum si valorile cu care se iniţializează.

Este de fapt o instrucţiune ciclică (exemplu : FOR) dublă, în care se parcurg toate elementele unei matrice, atribuindu-le valoarea corespunzatoare. Indicii sunt daţi de $I1 şi $I2 , un element dintr-o matrice putând fi asociat cu uşurinţă modelului matematic A[$I1][ $I2].

initial begin

ct = 2 ;

$InitM(CX, (($I1 == 0) ? 1 :(($I2 == 0) ? 1 : (CX[$I1-1][$I2] +CX[$I1][$I2-1]))));

$InitM(CY, (($I1 == 0) ? 1 :(($I2 == 0) ? 1 : (CY[$I1-1][$I2] +CY[$I1][$I2-1]))));

Pentru a testa dacă rezultatul este cel dorit în urma iniţializării matricelor, am afişat la terminal valorile acestora, folosind extrem de simplu , dar folositor, instrucţiunea oferită de FinMath $PrintM, care are drept scop citirea valorilor elementelor unei matrice, vectorul multidimensional fiind văzut ca o variabilă de tip "%e”.

Se observă păstrarea tiparului Verilog prin introducerea acestui nou tip de variabilă "%e”.

Afişarea matricelor iniţiale are drept scop şi compararea acestora cu rezultatul obţinut în vederea verificării funcţionalităţii corecte a procedurii.

$PrintM(CX, "%e");

$PrintM(CY, "%e");

Rezultatul este calculat simplu, într-un singur rând, care iniţializează matricea rezultat R cu valoarea obţinută prin înmulţirea primei matrice cu valoarea constantă, şi ulterior adunarea rezultatului parţial la cea de a doua matrice.

$InitM(RX, CY[$I1][$I2] + (ct * CX[$I1][$I2]));

Pentru a putea spune cu siguranţă ca rezultatul este cel dorit, am afişat matricea R.

$PrintM(RX,"%e");

end

endmodule

Celălalte subrutine BLAS implementate în FinSimMath sunt ataşate în anexe, curprinzând codul sursă precum şi comentariile aferente.

5. Concluzii şi recomandări

Pentru a testa şi rula rutinele BLAS implementată în C (vezi arhiva cblas.tgz de pe site-ul oficial : ), se recomandă a se utiliza sistemul de operare Linux (rulat direct de pe calculator, sau din maşină virtuală). Este necesară instalarea în prealabil a unui compilator de Fortran (g77). Există distribuţii de Linux uşor de folosit şi de utilizatorii neexperimentaţi în operarea pe aceasta platformă (ex : Debian, Ubuntu – instalarea se face simplu, prin rualrea comenzii  : apt-get install numeProgram ).Pentru a rula exemplele din CBLAS trebuie downloadat şi fişierul ce conţine rutinele BLAS (blas.tgz). După dezarhivarea ambelor arhive, in Makefile-ul din folderul CBLAS trebuie trecută calea către rutinele BLAS (CBLAS-ul nu este decât o adaptare a BLAS-ului implementat in Fortran). De asemenea este necesar un compilator de C (GCC) . Restul paşilor sunt menţionaţi în fişierul Readme din arhivă.

Simularea cu FinSim necesită existenţa următoarelor fişiere :

- run.bat : conţine calea către vsvars32.bat, fişier care vine o dată cu instalarea unui compilator de C sub Windows (Visual Studio 6.00)

- runsim.bat : structura este mai complicată, are rolul de a simula şi de a rula modulul implementat . Fişierul runsim.bat este ataşat proiectului în anexe.

- top.cf : conţine modulele VPVerilog care vor fi testate, modulele trebuie sa fie incluse în acelaşi folder, top.cf este folosit de runsim.bat în simulare şi rulare

- modulele VPVerilog ce vor fi compilate şi rulate

FinSim nu este compatibil cu WindowsVista.

În concluzie, FinSimMath este o unealtă puternică care poate fi folosită în mod corespunzător pentru a realiza cod sintetizabil. Proiectul nu se opreşte aici, urmând ca pe viitor să testăm “pe viu” (adică pe FPGA) codurile implementate cu VPVerilog şi simulat cu FinSim. Astfel, urmează perspective noi, care , sperăm , vor contribui puternic la dezvoltarea industriei hardware.

6. Bibliografie

Tutorial on FinSimMath(TM) (an extension of Verilog(R) for Mathematical Descriptions) by Alec Stănculescu Fintronic USA, Inc.

DSP Designers determine the size of operands in one Verilog simulation

Support for complex numbers in Cartesian and Polar coordinates.

Example Code for Fast Autocorrelation using FFT/IFFT, within a Verilog module.

Example Code for inverting in seconds a 2000x2000 sparse matrix with elements of type real, within a Verilog module.

Example Code for computing in seconds the inverse of a 500x500 matrix with elements of type complex with cartesian coordinates, within a Verilog module.

Example Code for computing the pseudo inverse, within a Verilog module.

7. Anexe

Runsim.bat : compilează şi rulează modulele VPVerilog

[pic]

VPCcopy.v : copiează o matrices au un vector într-o altă matrice / vector (copie)

VPCdotC.v :returnează produsul scalar a 2 vectori c[i][j]=a[i][j]*b[i][j]

VPCswap.v : interschimbarea a 2 vectori /matrice

-----------------------

@echo off

title Fintronic USA Verilog Simulator

if not exist %FINTRONIC% (echo ***ERROR*** The FinSim environment is not set. Please check that the & echo installation program has inserted FinSim environment & echo variables in your AUTOEXEC.BAT and restart your computer. & goto end)

rem set the options for finvc

set FINVCOPT=-cf top.cf -a -ol 9

rem set the options for finbuild

set FINBUILDOPT=-driver

rem set the options for TOP.sim

set FINSIMOPT=-verbose

rem get all the compiler options from the command line

:begin

shift

if "%0" == "" goto compile

set FINVCOPT=%FINVCOPT% %0

goto begin

rem run the compiler finvc

:compile

finvc %FINVCOPT%

if errorlevel 1 (echo. & echo ***ERROR*** The compiler finvc terminated abnormally & echo Please check the log file finvc.log & goto end)

rem run the simulation builder finbuild

finbuild %FINBUILDOPT%

if errorlevel 1 (echo. & echo ***ERROR*** The simulation builder finbuild terminated abnormally & echo Please check the log files finbuild.log and compile.log & goto end)

rem run the simulator TOP.exe

TOP.exe %FINSIMOPT%

if errorlevel 1 (echo. & echo ***ERROR*** The simulation terminated abnormally & echo Please check the log file finsim.log & goto end)

echo.

echo The simulation has completed successfully

:end

/* Purpose

* =======

* CCOPY copies a vector/matrix x to a vector/matrix y.

*

* Further Details

* ===============

* Rewrites blas sources using FinMath ()

* mirela dinu, 2008/05/17

* vs 1.0

*/

module VPCcopy;

/* .. Scalar arguments .. */

parameter NLIN = 3;

parameter NCOL = 2;

real CX[NLIN-1:0][NCOL-1:0];

real RX[NLIN-1:0][NCOL-1:0];

initial begin

/* populate CX into a Pascal Matrix */

$InitM(CX, (($I1 == 0) ? 1 :(($I2 == 0) ? 1 : (CX[$I1-1][$I2] +CX[$I1][$I2-1]))));

/* print the initial matrixes */

$PrintM(CX, "%e");

/* calculate the result */

RX = CX;

/* print the result*/

$PrintM(RX,"%e");

end

endmodule

SUBROUTINE CAXPY(N,CA,CX,INCX,CY,INCY)

* .. Scalar Arguments ..

COMPLEX CA

INTEGER INCX,INCY,N

* .. Array Arguments ..

COMPLEX CX(*),CY(*)

* Purpose

* =======

* CAXPY constant times a vector plus a vector.

*

* Further Details

* ===============

*

* jack dongarra, linpack, 3/11/78.

* modified 12/3/93, array(1) declarations changed to array(*)

* .. Local Scalars ..

INTEGER I,IX,IY

* .. External Functions ..

REAL SCABS1

EXTERNAL SCABS1

IF (N.LE.0) RETURN

IF (SCABS1(CA).EQ.0.0E+0) RETURN

IF (INCX.EQ.1 .AND. INCY.EQ.1) GO TO 20

* code for unequal increments or equal increments

* not equal to 1

IX = 1

IY = 1

IF (INCX.LT.0) IX = (-N+1)*INCX + 1

IF (INCY.LT.0) IY = (-N+1)*INCY + 1

DO 10 I = 1,N

CY(IY) = CY(IY) + CA*CX(IX)

IX = IX + INCX

IY = IY + INCY

10 CONTINUE

RETURN

* code for both increments equal to 1

20 DO 30 I = 1,N

CY(I) = CY(I) + CA*CX(I)

30 CONTINUE

RETURN

END

module VPCaxpy;

/* Purpose : CAXPY constant times *a matrix/vector plus a matrix/vector.

* Rewrites blas sources using FinMath ()

* mirela dinu, 2008/05/17 */

/* .. Parameters .. number of collons and lines is 1 for vectors */

parameter NLIN = 3;

parameter NCOL = 2;

real ct ; // constant that times the matrix/vector

/*... Array arguments ... */

real CX[NLIN-1:0][NCOL-1:0];

real CY[NLIN-1:0][NCOL-1:0];

/* result matrix/vector */

real RX[NLIN-1:0][NCOL-1:0];

initial begin

ct = 2 ;

/* populate CX into a Pascal Matrix */

$InitM(CX, (($I1 == 0) ? 1 :

(($I2 == 0) ? 1 : (CX[$I1-1][$I2] +

CX[$I1][$I2-1]))));

/* populate CY into a Pascal Matrix */

$InitM(CY, (($I1 == 0) ? 1 :

(($I2 == 0) ? 1 : (CY[$I1-1][$I2] +

CY[$I1][$I2-1]))));

/* print the initial matrixes */

$PrintM(CX, "%e");

$PrintM(CY, "%e");

/* calculate the result */

$InitM(RX, CY[$I1][$I2] +

(ct * CX[$I1][$I2]));

/* print the result*/

$PrintM(RX,"%e");

end

endmodule

/* Purpose

* forms the dot (scalar) product of two vectors/matrixs c[i][j]=a[i][j]*b[i][j]

* Rewrites blas sources using FinMath ()

* mirela dinu, 2008/05/17

*/

module VPCdotC;

/* .. Scalar arguments .. */

parameter NLIN = 1; // vector size = 1

parameter NCOL = 5;

real ct ;

real CX[NLIN-1:0][NCOL-1:0];

real CY[NLIN-1:0][NCOL-1:0];

real RX[NLIN-1:0][NCOL-1:0];

initial begin

ct = 2 ;

/* populate CX into a Pascal Matrix */

$InitM(CX, (($I1 == 0) ? 2 :(($I2 == 0) ? 1 : (CX[$I1-1][$I2] +CX[$I1][$I2-1]))));

/* populate CY into a Pascal Matrix */

$InitM(CY, (($I1 == 0) ? 3 :(($I2 == 0) ? 1 : (CY[$I1-1][$I2] +

CY[$I1][$I2-1]))));

/* print the initial matrixes */

$PrintM(CX, "%e");

$PrintM(CY, "%e");

/* calculate the result */

$InitM(RX, CY[$I1][$I2] * CX[$I1][$I2]);

/* print the result*/

$PrintM(RX,"%e");

end endmodule

/* Purpose

* interchanges two vectors/matrixs

* Rewrites blas sources using FinMath ()

* mirela dinu, 2008/05/17*/

module VPCswap;

/* .. Scalar arguments .. */

parameter NLIN = 1; // vector size = 1

parameter NCOL = 5;

real ct ;

real CX[NLIN-1:0][NCOL-1:0];

real CY[NLIN-1:0][NCOL-1:0];

real AUX[NLIN-1:0][NCOL-1:0];

initial begin

$display("CSWAP \n");

ct = 2 ;

$InitM(CX, (($I1 == 0) ? 2 :(($I2 == 0) ? 1 : (CX[$I1-1][$I2] +

CX[$I1][$I2-1]))));

$InitM(CY, (($I1 == 0) ? 3 :(($I2 == 0) ? 1 : (CY[$I1-1][$I2] +

CY[$I1][$I2-1]))));

/* print the initial matrixes */

$display("Initial values \n");

$PrintM(CX, "%e");

$PrintM(CY, "%e");

/* calculate the result */

$InitM(AUX, CX[$I1][$I2]);

CX = CY;

CY = AUX ;

/* print the result*/

$display("After swapping \n");

$PrintM(CX,"%e");

$PrintM(CY,"%e");

end

endmodule

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download