Linpack

Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar al autor principal del artículo en su página de discusión pegando: {{subst:Aviso referencias|Linpack}} ~~~~

El benchmark Linpack fue desarrollado en el Argone National Laboratory por Jack Dongarra en 1976, y es uno de los más usados en sistemas científicos y de ingeniería.

Su uso como benchmark fue accidental, ya que originalmente fue una extensión del programa Linpack -cuyo propósito era resolver sistemas de ecuaciones- que otorgaba el tiempo de ejecución del programa en 23 máquinas distintas. Luego fueron agregándose cada vez mayor cantidad de máquinas (según sus mismos autores más como un pasatiempo que otra cosa).

Hoy en día, el programa Linpack ha sido reemplazado por el paquete Lapack, el cual hace un uso mucho mejor de las características de la arquitectura RISC (en esencia, sus técnicas algorítmicas fueron modificadas para que pase menor tiempo moviendo datos).

El benchmark Linpack puede conseguirse en versión Fortran, C y como un applet de Java.

Descripción del benchmark

La característica principal de Linpack es que hace un uso muy intensivo de las operaciones de coma flotante, por lo que sus resultados son muy dependientes de la capacidad de la FPU que tenga el sistema. Además pasan la mayor parte del tiempo ejecutando unas rutinas llamadas BLAS (Basic Linear Algebra Subroutines o Subrutinas de Álgebra Lineal Básica). Como hay dos tipos de estas bibliotecas (una codificada en ensamblador y otra en Fortran), el resultado también dependerá mucho de esto. De lejos, el mayor tiempo de ejecución se consume en la rutina DAXPY de la biblioteca BLAS (casi el 90%). DAXPY realiza el siguiente cálculo

y(i) := y(i) + a * x(i).

Es por esto que en realidad se puede decir que lo que mide Linpack es la velocidad del sistema para DAXPY.

Por otra parte, al realizar esencialmente cálculos con matrices es un test fácilmente paralelizable, y se puede utilizar para medir la eficiencia de sistemas multiprocesador (de hecho, existe una página en Internet que informa el "Top 500" de las computadoras basándose en el Linpack).

Los principios matemáticos

El reporte del benchmark describe la performance para resolver un problema de matrices generales densas Ax = b a tres niveles de tamaño y oportunidad de optimización: problemas de 100 x 100 (optimización del bucle interno), problemas de 1.000 por 1.000 (optimización de tres bucles - el programa entero) y un problema paralelo escalable. Estas matrices son generadas usando un generador de números pseudoaleatorios, pero forzando los números para que pueda ejecutarse un pivoteo parcial con Eliminación Gaussiana. Ejecuta dos rutinas básicas: una que descompone la matriz, y otra que resuelve el sistema de ecuaciones basándose en la descomposición de la primera matriz. Para una matriz de n x n la primera rutina lleva n³ operaciones de coma flotante, mientras que la segunda ejecuta n² operaciones de coma flotante.

Las rutinas involucradas hacen uso de algoritmos orientados a columnas. Esto es, los programas generalmente referencian a los elementos de los arreglos bidimensionales secuencialmente hacia abajo por una columna, en lugar de hacerlo por filas. Esta orientación era importante por la forma en que el lenguaje Fortran almacena los arreglos.

Varios benchmarks en uno

Linpack está compuesto de tres benchmarks: los ya mencionados de orden 100 y orden 1.000, y un tercero de Computación Altamente Paralela (un algoritmo especialmente diseñado para buscar los beneficios de los multiprocesadores).

En el primero sólo se permite cambiar las opciones del compilador para hacerlo más eficiente; sin embargo debe especificarse antes de correrlo una función SECOND que devuelva el tiempo de ejecución en segundos del programa.

Las reglas básicas para el segundo benchmark son un poco más relajadas. Se puede especificar cualquier ecuación lineal que uno dese, implementada en el lenguaje que uno desee.

Optimización

El Linpack es un programa que ejecuta cálculos con matrices, y como tal, existe numerosas técnicas para optimizarlo. Por ejemplo, intentando hacer un uso más eficiente de la carga de datos en la caché más próxima, puede llevar a una aproximación de cálculos matriz-vector o matriz-matriz. Las técnicas a aplicar dependerán de los tamaños de los distintos niveles de caché y la arquitectura de la computadora. A continuación detallamos otra técnica:

Loop unrolling (desarrollo del bucle)

El loop unrolling es una técnica de optimización que consiste en hacer más extenso un bucle simple reduciendo la sobrecarga por comparación del bucle y permitiendo una mejor concurrencia. De esta manera, la siguiente estructura repetitiva:

PARA i:= 1 a n HACER
        y(i) := y(i) + alfa * x(i)
FIN PARA

En lugar de hacer una sola instrucción por bucle, se pueden lograr 4 instrucciones por bucle (o las que uno desee) de la siguiente forma:

m := n - n MOD 4
PARA i:= 1 a m, PASO 4 HACER
        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)
FIN PARA
PARA i: m a n HACER
        y(i) := y(i) + alfa * x(i)
FIN PARA

¿Por qué esto aumenta la velocidad del bucle?

• la reducción directa por la sobrecarga del bucle (incremento, comparación y ramificación), la cual se lleva el mayor tiempo de ejecución por iteración; si los bucles son grandes, el código adicional requerido se ve claramente compensado.

• al haber mayor cantidad de operaciones dentro del bucle, se permite una mayor concurrencia de operaciones (en este caso la multiplicación). La profundidad del desarrollo dependerá del grado de segmentación del procesador.

• esta concurrencia se incrementa si se tienen elementos de suma y multiplicación independientes.

El problema de esta técnica, es que si tenemos compiladores que intentan detectar operaciones vectoriales, el desarrollo del bucle tiene el efecto exactamente contrario, impidiendo que el compilador optimice según la estructura vectorial.

Resultados

Los resultados se expresan en MFlops (millones de operaciones de coma flotante por segundo), siempre referidas a operaciones de suma y multiplicación de doble precisión (64 bits, aunque para algunos sistemas esta cantidad de bits es la precisión simple).