LINPACK
| Tipus | biblioteca informàtica  |
|---|---|
| Característiques tècniques | |
| Escrit en | Fortran |
| Equip | |
| Desenvolupador(s) | Jack Dongarra |
| Més informació | |
| Lloc web | netlib.org… |
|
| |
LINPACK és una llibreria de programari per a realitzar operacions d'algebra lineal de manera numèrica en ordinadors digitals. Fou desenvolupada en el Argone National Laboratory per Jack Dongarra l'any 1976,[1][2] i és una de les més usades en programaris científics i d'enginyeria.
També pot esser usada com a benchmark, és a dir, com a mesura de potència de càlcul d'ordinadors. El seu ús com benchmark va ser accidental, ja que originalment va ser una extensió del programa LINPACK, el propòsit del qual era resoldre sistemes d'equacions, que atorgava el temps d'execució del programa en 23 màquines diferents. Després s'hi va anar agregant cada cop més gran quantitat de màquines (segons els seus autors més com un passatemps que una altra cosa).
Avui en dia, el programa LINPACK ha estat reemplaçat pel paquet LAPACK, el qual fa un ús molt millor de les característiques de l'arquitectura RISC (en essència, les seves tècniques algorítmiques van ser modificades perquè perdi menys temps movent dades).
El benchmark LINPACK es pot aconseguir en versió Fortran, C i com un applet de Java.
Descripció del benchmark
[modifica]La característica principal de LINPACK és que fa ús molt intensiu de les operacions de coma flotant, pel que els seus resultats són molt dependents de la capacitat de la FPU que tingui el sistema. A més, passen la major part del temps executant unes rutines anomenades BLAS (Basic Linear Algebra Subroutines o Subrutines d'Àlgebra Lineal Bàsica). Com hi ha dos tipus d'aquestes biblioteques (una codificada en assemblador i una altra en Fortran), el resultat també dependrà molt d'això. De lluny, el temps d'execució més gran es consumeix en la rutina DAXPY de la biblioteca BLAS (gairebé el 90%). DAXPY realitza el següent càlcul:
y(i) := y(i) + a * x(i).
És per això que en realitat es pot dir que el que mesura LINPACK és la velocitat del sistema per DAXPY.
D'altra banda, en realitzar essencialment càlculs amb matrius és un test fàcilment paral·lelitzable, i es pot utilitzar per mesurar l'eficiència de sistemes multiprocessador (de fet, hi ha una pàgina a Internet que informa el "Top 500" de les computadores basant-se en el LINPACK).
Els principis matemàtics
[modifica]El reporti del benchmark descriu la performance per resoldre un problema de matrius generals denses Ax = ba tres nivells de grandària i oportunitat d'optimització: problemes de 100 x 100 (optimització del bucle intern), problemes de 1.000 per 1.000 (optimització de tres bucles - el programa sencer) i un problema paral·lel escalable. Aquestes matrius són generades utilitzant un generador de nombres pseudoaleatoris, però forçant els números perquè pugui executar-se un pivoteig parcial amb Eliminació Gaussiana. Executa dues rutines bàsiques: una que descompon la matriu, i una altra que resol el sistema d'equacions basant-se en la descomposició de la primera matriu. Per a una matriu de nxn la primera rutina porta n³ operacions de coma flotant, mentre que la segona executa n² operacions de coma flotant.
Les rutines involucrades fan ús d'algorismes orientats a columnes. Això és, els programes generalment referencien als elements dels arranjaments bidimensionals seqüencialment cap avall per una columna, en comptes de fer-ho per files. Aquesta orientació era important per la forma en què el llenguatge Fortran emmagatzema els arranjaments.
Diversos benchmarks en un
[modifica]LINPACK està compost de tres benchmarks: els ja esmentats d'ordre 100 i ordre 1.000, i un tercer de Computació Altament Paral·lela (un algoritme especialment dissenyat per buscar els beneficis dels multiprocessadors).
En el primer només es permet canviar les opcions del compilador per fer-lo més eficient, però s'ha d'especificar abans de córrer una funció SECOND que retorni el temps d'execució en segons del programa.
Les regles bàsiques per al segon benchmark són una mica més relaxades. Es pot especificar qualsevol equació lineal que un desitgi, implementada en el llenguatge que un desitgi.
Optimització
[modifica]El LINPACK és un programa que executa càlculs amb matrius, i com a tal, hi ha nombroses tècniques per optimitzar-lo. Per exemple, intentant fer un ús més eficient de la càrrega de dades a la memòria cau més propera, pot portar a una aproximació de càlculs matriu-vector o matriu-matriu. Les tècniques a aplicar dependran de les grandàries dels diferents nivells de memòria cau i l'arquitectura de l'ordinador. A continuació detallem una altra tècnica:
Loop unrolling (desenvolupament del bucle)
[modifica]El loop unrolling és una tècnica d'optimització que consisteix a fer més extens un bucle simple reduint la sobrecàrrega per comparació del bucle i permetent una millor concurrència. D'aquesta manera, l'estructura repetitiva:
PER i: = 1 a n FER y(i): = y(i) + alfa * x (i) FI PER
En fer una sola instrucció per bucle, es poden assolir 4 instruccions per bucle (o les que un desitgi) de la següent manera:
m: = n - n MOD 4 PER i: = 1 a m, PAS 4 FER y(i): = y(i) + alfa*x(i) y(i+1): = y(i+1) + alfa*x(i+1) y(i+2): = y(i+2) + alfa*x(i+2) y(i+3): = y(i+3) + alfa*x(i+3) FI PER PER i: m a n FER y(i): = y(i) + alfa * x (i) FI PER
Per què això augmenta la velocitat del bucle?
- La reducció directa per la sobrecàrrega del bucle (increment, comparació i ramificació), la qual es porta el major temps d'execució per iteració, si els bucles són grans, el codi addicional requerit es veu clarament compensat.
- A l'haver-hi major quantitat d'operacions dins del bucle, es permet una major concurrència d'operacions (en aquest cas la multiplicació). La profunditat del desenvolupament dependrà del grau de segmentació del processador.
- Aquesta concurrència s'incrementa si es tenen elements de suma i multiplicació independents.
El problema d'aquesta tècnica, és que si es té compiladors que intenten detectar operacions vectorials, el desenvolupament del bucle té l'efecte exactament contrari, impedint que el compilador optimitzi segons l'estructura vectorial.
Resultats
[modifica]Els resultats s'expressen en MFLOPS (milions d'operacions de coma flotant per segon), sempre referides a operacions de suma i multiplicació de doble precisió (64 bits, encara que per alguns sistemes aquesta quantitat de bits és la precisió simple).
Referències
[modifica]- ↑ Matlis, Jan «Sidebar: The Linpack Benchmark». ComputerWorld, 30-05-2005. Arxivat 2014-08-13 a Wayback Machine.
- ↑ Markoff, John «Technology; Measuring How Fast Computers Really Are». New York Times, 22-09-1991.