LINPACK

El benchmark Linpack fue desarrollado en el Argone National Laboratory por Jack Dongarra en 1976, y es uno de los mas usados en sistemas cientificos y de ingenieria.

Su uso como benchmark fue accidental, ya que originalmente fue una extension del programa Linpack -cuyo proposito era resolver sistemas de ecuaciones- que otorgaba el tiempo de ejecucion del programa en 23 maquinas distintas. Luego fueron agregandose cada vez mayor cantidad de maquinas (segun sus mismos autores mas como un pasatiempo que otra cosa).

Hoy en dia, el programa Linpack ha sido reemplazado por el paquete Lapack, el cual hace un uso mucho mejor de las caracteristicas de la arquitectura RISC (en esencia, sus tecnicas algoritmicas fueron modificadas para que pase menor tiempo moviendo datos).

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

La caracteristica 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. Ademas pasan la mayor parte del tiempo ejecutando unas rutinas llamadas BLAS (Basic Linear Algebra Subroutines o Subrutinas de Algebra Lineal Basica). Como hay dos tipos de estas bibliotecas (una codificada en ensamblador y otra en Fortran), el resultado tambien dependera mucho de esto. De lejos, el mayor tiempo de ejecucion se consume en la rutina DAXPY de la biblioteca BLAS (casi el 90%). DAXPY realiza el siguiente calculo

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 calculos con matrices es un test facilmente paralelizable, y se puede utilizar para medir la eficiencia de sistemas multiprocesador (de hecho, existe una pagina en Internet que informa el "Top 500" de las computadoras basandose en el Linpack: https://www.top500.org/).

El reporte del benchmark describe la performance para resolver un problema de matrices generales densas Ax = b a tres niveles de tamano y oportunidad de optimizacion: problemas de 100 x 100 (optimizacion del bucle interno), problemas de 1.000 por 1.000 (optimizacion de tres bucles - el programa entero) y un problema paralelo escalable. Estas matrices son generadas usando un generador de numeros pseudoaleatorios, pero forzando los numeros para que pueda ejecutarse un pivoteo parcial con Eliminacion Gaussiana. Ejecuta dos rutinas basicas: una que descompone la matriz, y otra que resuelve el sistema de ecuaciones basandose en la descomposicion de la primera matriz. Para una matriz de n x n la primera rutina lleva n3 operaciones de coma flotante, mientras que la segunda ejecuta n2 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 orientacion era importante por la forma en que el lenguaje Fortran almacena los arreglos.

Linpack esta compuesto de tres benchmarks: los ya mencionados de orden 100 y orden 1.000, y un tercero de Computacion Altamente Paralela (un algoritmo especialmente disenado para buscar los beneficios de los multiprocesadores).

En el primero solo se permite cambiar las opciones del compilador para hacerlo mas eficiente; sin embargo debe especificarse antes de correrlo una funcion SECOND que devuelva el tiempo de ejecucion en segundos del programa.

Las reglas basicas para el segundo benchmark son un poco mas relajadas. Se puede especificar cualquier ecuacion lineal que uno desee, implementada en el lenguaje que uno desee.

El Linpack es un programa que ejecuta calculos con matrices, y como tal, existe numerosas tecnicas para optimizarlo. Por ejemplo, intentando hacer un uso mas eficiente de la carga de datos en la cache mas proxima, puede llevar a una aproximacion de calculos matriz-vector o matriz-matriz. Las tecnicas a aplicar dependeran de los tamanos de los distintos niveles de cache y la arquitectura de la computadora. A continuacion detallamos otra tecnica:

El loop unrolling es una tecnica de optimizacion que consiste en hacer mas extenso un bucle simple reduciendo la sobrecarga por comparacion del bucle y permitiendo una mejor concurrencia. De esta manera, la siguiente estructura repetitiva:

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

?Por que esto aumenta la velocidad del bucle?

• la reduccion directa por la sobrecarga del bucle (incremento, comparacion y ramificacion), la cual se lleva el mayor tiempo de ejecucion por iteracion; si los bucles son grandes, el codigo 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 multiplicacion). La profundidad del desarrollo dependera del grado de segmentacion del procesador.

• esta concurrencia se incrementa si se tienen elementos de suma y multiplicacion independientes.

El problema de esta tecnica, es que si tenemos compiladores que intentan detectar operaciones vectoriales, el desarrollo del bucle tiene el efecto exactamente contrario, impidiendo que el compilador optimice segun la estructura vectorial.

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

• Software de analisis numerico
• Benchmarks

• Wikipedia:Articulos que necesitan referencias
• Wikipedia:Referenciar informatica