0. Introducción

Una bien conocida caracterización de Física Computacional (FC) fue dada por K. Wilson en 1986. Según él un problema típico de Física Computacional: i) tiene una formulación matemática precisa, ii) es intratable por métodos analíticos, iii) tiene objetivos relevantes en ciencia y iv) requiere un conocimiento profundo del problema.

En general, la forma de hacer ciencia usando ordenadores es inherentemente multidisciplinar. Asi, por ejemplo, un físico computacional necesita tener (a parte de unos excelentes fundamentos en física teórica) una base firme en matemáticas aplicadas, técnicas de uso de ordenadores y conocimientos de arquitectura de los mismos. Dicho esto, la actual extensión del uso de los ordenadores y su potencia creciente puede hacer pensar a más de uno que, en el fondo, con tener unas pequeñas nociones de como compilar un programa y unos mínimos algoritmos de resolución de ecuaciones diferenciales, ya puede estar en codiciones de hacer FC. Esta última conclusión es equivalente a pensar que el realizar experimentos en casa sobre el movimiento de una masa deslizándose por un plano inclinado nos faculta automáticamente para realizar experimentos de medición de las diferencias entre masa inercial y pesante (huelga decir que éstos últimos son extremadamente complicados y que para su diseño uno necesita, por ejemplo, de una excelente preparación en la Teoria de la Relatividad). En general, los problemas complejos que no pueden ser abordados por métodos tradicionales son de tal complejidad que se han de desarrollar algoritmos numéricos específicos para su accesibilidad por medio de técnicas de ordenador. Ya en 1952 Hartree había reconocido la importancia de los desarrollos algorítmicos:

With the development of new kinds of equipment of greater capacity, and particularly of greater speed, it is almost certain that new methods will have to be developed in order to make the fullest use of this new equipment. It is necessary not only to design machines for the mathematics, but also to develop a new mathematics for the machines

En esta linea, el algoritmo para la realización de la transformada de Fourier de una forma eficaz (FFT) fue un hito en el cálculo numérico y, parece ser, que el articulo donde se publicó originalmente es uno de los más citados de la literatura científica. Por último, permitaseme insistir en que las propiedades de un algoritmo dado, es muchas veces, objeto de estudio per se. Asi por ejemplo, en la discretización de ecuaciones diferenciales para su resolución numérica uno puede estar incluyendo soluciones espúreas que solo aparecen en la versión discreta de las ecuaciones diferenciales originales, el comprender y controlar estas soluciones espúreas es actualmente un importante campo de investigación en las teorías matemáticas sobre diferencias finitas.

En cualquier caso, la sinergia entre mejores algoritmos y mejores ordenadores nos ha llevado en los últimos años a tener acceso a problemas más y más relevantes. Asi, por ejemplo, cuando el Cray 1S apareció, los programas de predicción meteorológica daban datos precisos hasta un límite de 12 horas. El Cray XMP elevó el límite a 24 horas y ya se empezó a poder modelar el plasma. Con el Cray 2 se podía predecir el tiempo hasta 48 horas, se pudo iniciar el modelado de la dinámica de los compuestos químicos y se hicieron las primeras estimaciones de la masa de los bosones de Higgs. El Cray YMP permitió 72 horas de predicciones meteorológicas y el estudio de hidrodinámica en 2D. Por último, el C90 permite el diseño de drogas farmaceuticas y de aviones.

Hemos de insistir que a diferencia de un experto informático, el objetivo intelectual último de un físico computacional no es la comprensión de su funcionamiento sino su uso para resolver y comprender problemas concretos de la Física. Algunos problemas típicos de FC : la comprensión de la estructura electrónica de materiales, el comportamiento de un fluido en un régimen turbulento, el modelaje del clima, la obtención de las claves genéticas del genoma humano,...

1  Pequeña historia de la tecnología de los ordenadores

Una historia completa de los ordenadores debería incluir las máquinas analógicas como los ábacos Chinos, las máquinas analíticas de J. Loom (1805) y C. Babbage (1834), y la calculadora de Marchant (1965). Sin embargo nos vamos a restringir principalmente al área de los ordenadores digitales.

La evolución de los ordenadores digitales se divide en generaciones. Cada generación se caracteriza por una mejora substancial sobre la generación precedente in tecnología usada para su construcción, su organización interna (arquitectura) y sus lenguajes de programación.

1.1  La era mecánica (1623-1945)

La idea de utilizar máquinas para resolver problemas matemáticos se remonta a principios del siglo XVII. Algunos matemáticos como W. Schickhard, G. Leibnitz and B. Pascal (la contribución de Pascal al cálculo por ordenador fue reconocida por N. Wirth, quien en 1972 bautizó su nuevo lenguaje de ordenador como Pascal) diseñaron e implementaron calculadoras que eran capaces de sumar, restar, multiplicar y dividir.

El primer aparato programable fue probablemente la máquina de diferencias de C. Babbage, la cual se comenzó a construir en 1823 pero nunca se finalizó. Otra máquina mucho más ambiciosa fue la máquina analítica, que fue diseñada en 1842 pero solo fue parcialmente completada por Babbage. Los historiadores piensan que Babbage no puedo completar sus máquinas debido a que la tecnología de la época no era lo suficientemente fiable. Aun cuando no completó ninguna de sus máquinas, Babbage y sus colegas, sobre todo Ada, condesa de Lovelace, reconocieron importantes tecnicas de programación como los ciclos iterativos, los índices en las variables o las ramas condicionales.

Una máquina inspirada por el diseño de Babbage fue la primera en ser usada para el cálculo científico. G. Scheutz supo de la máquina de diferencias en 1833, y junto con su hijo, E. Scheutz, comenzó a construir una versión más pequeña. Por 1853, habían construido una máquina que podía procesar números de 15 dígitos y calcular diferencias de cuarto orden. Su máquina ganó una medalla de oro en la exibición de Paris de 1855, y posteriormente vendieron su máquina al observatorio de Dudley, Albany (New York), donde se utilizó para calcular la orbita de Marte. Uno de los primeros usos comerciales de los ordenadores mecánicos lo realizó la oficina del censo de los Estados Unidos que utilizó un equipo diseñado por H. Hollerith para tabular el censo de 1890. En 1911 la compañia Hollerith se fusionó con un competidor para fundar la corporación que en 1924 sería IBM.

1.2  La primera generación de ordenadores electrónicos (1937-1953)

Los primeros ordenadores electrónicos se caracterizaron por utilizar interruptores electrónicos, en forma de tubos de vacio, en lugar de relés electro-mecánicos. Los tubos de vacio se caracterizaban en que no tenían partes móviles y podían abrirse y cerrarse unas 1000 veces más rápidos que los interruptores mecánicos. Aun asi, en aquellos tiempos la fiabilidad de los tubos de vacio era comparable con la de los relés debido a lo novedoso de su tecnología.

El primer intento para construir un ordenador electrónico fue realizado por J.V. Atanasoff, un profesor de Física y Matemáticas en Iowa State Univ. en 1937. Atanasoff quería construir una máquina que ayudase a sus estudiantes a resolver sistemas de equaciones diferenciales. En 1941 él y su estudiante C. Berry consiguieron construir una máquina que podía resolver 29 equaciones simultáneas con 29 incógnitas. Sin embargo la máquina no era programable y se parecía más a una calculadora electrónica.

Otra máquina construida en aquellos tiempos fue Colossus, diseñada por Alan Turing para los militares británicos en 1943. Esa máquina contribuyó decisivamente a la ruptura de los códigos secretos del ejército alemán durante la segunda guerra mundial. La existencia de Colossus fue mantenida en secreto incluso después de la finalización de la II guerra mundial.

El primer ordenador electrónico programable para cualquier tipo de problema fue el ENIAC (Electronic Numerical Integrator And Computer), construido por J.P. Eckert and J.V. Mauchly en la Universidad de Pensilvania. Su trabajo comenzó en 1943 financiado por el ejército norteamericano que necesitaba un forma rápida de realizar cálculos balísticos durante la guerra. La máquina no estuvo completa hasta 1945 y luego se utilizó extensivamente para el diseño de la bomba de hidrógeno. En 1955 ENIAC se jubiló después de haber hecho importantes contribuciones en el diseño de túneles de viento, números aleatorios y predicciones meteorológicas. Eckert, Mauchly and J. von Newmann habían comenzado ya a diseñar una nueva máquina: EDVAC en la que introdujeron el concepto de programa almacenado. ENIAC era controlado por un conjunto de interruptores externos de tal forma que, para cambiar el programa uno tenía que alterar su configuración. EDVAC usaba una memoria que era capaz de almacenar las instrucciones y los datos lo que la hacía incrementar en ordenes de magnitud su velocidad con respecto a ENIAC. Asi pues el gran avance de EDVAC fue el reconocer que las instrucciones de programación del ordenador podían ser codificadas como números. Sin embargo, los primeros programas fueron escritos en código máquina (assembler). Eckert y Mauchly desarrollaron posteriormente el primer ordenador con éxito comercial: UNIVAC.

1.3  Segunda Generación (1954-1962)

La segunda generación de ordenadores introdujo importantes desarrollos en la arquitectura de los mismos, la tecnología para construir sus circuitos básicos y los lenguajes para programarlos. En esta época los interruptores electrónicos estaban basados en la tecnología de los transistores cuyo tiempo de encendido/apagado era de 0.3 microsegundos. Los primeros ordenadores construidos utilizando esta tecnología fueron TRADIC en los laboratorios Bell (1954) y TX-0 en el laboratorio Lincoln del MIT. La tecnología de las memorias se basaba en núcleos magnéticos que podían ser accedidos en orden aleatorio.

Durante esta segunda generación se introdujeron importantes lenguajes de alto nivel: FORTRAN (1956), ALGOL (1958) y COBOL (1959). Ordenadores comerciales relevantes fueron los IBM 704, 709 y 7094.

1.4  Tercera generación (1963-1972)

La tercera generación trajo un increible incremento en la potencia de cálculo. Las mayores innovaciones de esta etapa fueron el uso de circuitos integrados, memorias de semiconductor, formas de programación en paralelo y la introducción de los sistemas operativos y del tiempo compartido.

Los primeros circuitos integrados tenían unos 10 aparatos por circuito (chip) y llegaron a tener 100. En 1964 S. Cray desarrolló el CDC 6600 que fué la primera arquitectura en usar el paralelismo. Usando 10 unidades funcionales que podían trabajar simultáneamente, y 32 bancos de memoria independientes, el CDC 6600 era capaz de llegar a 1 millón de operaciones de coma flotante por segundo (1 Mflops). En 1969, Cray desarrolló el CDC 7600 que llegó a los 10 Mflops. En esa misma época el IBM 360-195 tambié llegó a los 10 Mflops pero utilizando la técnica de la caché de memoria.

En 1963 se desarrolló el lenguaje CPL (Combined Programming Language) que intentaba simplificar el ALGOL. Aun asi, CPL era demasido complicado y fue simplificado aun más por M. Richards en (1967), creando el BPCL (Basic CPL). In 1970 K. Thompson de los laboratorios Bell lo simplificó aún más y los llamó B.

1.5  Cuarta generación (1972-1984)

En esta generación se introdujeron los circuitos integrados con muchos componentes y se pasó de 1000 a 100000 componentes por chip. En esta escala, los procesadores, enteros caben en un chip, y algunos sistemas sencillos (procesador, memoria y controladores I/O) cabían también en un chip. Las memorias semiconductoras reemplazaron totalmente a las memorias magnéticas. Los ordenadores más emblemáticos fueron los CRAY 1, CRAY X-MP y CYBER 205. Se desarrollaron lenguajes de nivel muy alto como el FP (Functional Programming) y Prolog (Programming in logic). Esos lenguajes tendían a usar programación declarativa en lugar de la programación imperativa del Pascal, C, FORTRAN... En un lenguaje declarativo, el programador da la especificación matemática de lo que se debe calcular, dejando el como se calcula al compilador.

Dos sucesos importantes aparecieron durante este periodo: el desarrollo del lenguaje C y del sistema operativo UNIX ambos realizados en los laboratorios Bell. En 1972, D. Ritchie, buscando obtener los comportamientos del CPL y la sencillez del B de Thompson, desarrolló el C. Thompson y Ritchie utilizaron entonces el C para escribir una versión de UNIX para del DEC PDP-11. Este UNIX basado en C fue incluido rápidamente en otros ordenadores de forma que el usuarion ya no tenía que aprender un nuevo sistema operativo cada vez que se cambiaba el ordenador.

1.6  Quinta generación (1984-1990)

Esta generación se caracterizó por el uso extendido del proceso en paralelo y la fabricación de chips con millones de componentes. Ordenadores estrella de esta época son: Sequent Balance 8000 (20 procesadores-1 módulo de memoria), iPSC-1 de Intel (128 procesadores-cada uno con su memoria), Connection Machine de Thinking Machines (miles de procesadores muy sencillos trabajando bajo la dirección de una unidad de control).

1.7  La actualidad

Para saber como estamos actualmente lo mejor es consultar la lista de ``benchmarks'' que hay en http://www.specbech.org.

 

2  Como trabajan los ordenadores

2.1  Representando Números

Los ordenadores pueden ser potentes pero, en cualquier caso son finitos. Un consecuencia obvia de esto es que un número se almacena en un espacio finito y, por lo tanto, la representación de un número en la memoria de un ordenador es una aproximación. Los dígitos 0 y 1 son las unidades microscópicas de memoria. De esta forma, no es una gran sorpresa que todos los números sean representados en forma binaria. Por consiguiente, si un entero es representado con los N bits, n1, n2, ¼nN, de forma que ni = 0,1, podemos representar sólo 2N enteros. Puesto que el signo del entero utiliza un bit (0 representa +), nos deja solo N-1 bits para representar enteros entre 0 y 2N-1.

En la descripción de cualquier ordenador se nos dice el número de bits que se usa para almacenar un número (longitud de la palabra). De acuerdo con su diseño, cada procesador maneja de manera óptima una longitud de palabra (386-16 bits, Pentium-32 bits, Merced-64 bits). Muchas veces en lugar de tomar como unidad los bits, se utilizan los bytes donde 1 byte = 8 bits. Notar que 1K (un kilobyte) = 210 bytes = 1024 bytes. Normalmente 1 byte es la cantidad de memoria que se necesita para almacenar un símbolo. De esta forma, una página ocupa entre 2K y 5K.

Los números reales se representan de dos formas en el ordenador: notación de coma fija y notación de coma flotante. En la notación de coma fija, el número x se representa como

xfija = signo×(an 2n+an-12n-1 +¼+a0 20+¼+a-m2-m)

esto es, un bit se utiliza para almacenar el signo y los restantes N-1 se utilizan para almacenar las a's (n+m = N-2). Los valores particulares de N, m y n dependen de la máquina que se utiliza. La ventaja de esta respresentación es que sabemos en todo momento el error absoluto que cometemos en todos los números: 2-m-1. La mayor desventaja de esta notación es que los números pequeños tienen un mayor error relativo. En el cálculo científico lo que nos interesa sobre todo es tener errores relativos pequeños, de esta forma utilizamos el método de la coma flotante. Para una máquina de 32 bits, los enteros de 4 bytes están en el rango: -2147483648:2147483647. En la representación de coma flotante un número x es representado como:

xflot = (-1)s×mantisa×2expfld-bias

Aqui mantisa contiene los dígitos significantes del número y s el el bit que lleva el signo. Asi la mantisa es siempre positiva. Una palabra de 32 bits utilizará típicamente un esponente de 8 bits cuyo entero correspondiente podrá tomar valores entre 0 y 255. Los números que tengan exponentes negativos podrán ser representados en este esquema si elegimos bias = 127. En este caso el exponente tomará valores entre -127 y 128. Si 8 bits se utilizan para el exponente y 1 bit para el signo, la mantisa podrá utilizar 23 bits, asi, la precisión de la mantisa será de 1 parte en 223 lo que es equivalente a 10-7. Asi pues, la mantisa se almacena el la memoria como:

m = m1×2-1+m2×2-2+¼+m23×2-23

Por ejemplo, el número 0.5 se almacena como:

0-0111 1111-1000 0000 0000 0000 0000 000

donde el primer 0 es el signo, el segundo grupo de bits nos da el exponente: 0111 11112 = 12710 y los 23 bits restantes indican la mantisa. El número más grande que se puede almacenar en una máquina que trabaje a 32 bits es 2128 = 3.4×1038 y el más pequeño es 2-128 = 2.9×10-39. Si escribimos un programa en precisión doble (8 bytes por palabra lo cual no es eficaz en un procesador de 32 bites), en el método de coma flotantes se usarán 11 bits para el exponente y 52 para la mantisa. Los números que podremos representar van desde 2.225074×10-308 a 1.799693×10308.

La forma de almacenar los números en el método de coma flotante afecta fuertemente a la precisión de los cálculos. Como ejemplo veamos como se suman dos números de 32 bits: 7+1.0×10-7. El ordenador almacena estos números de la siguiente forma:

7 = 0 10000010 1110 0000 0000 0000 0000 000
10-7 = 0 01100000 1101 0110 1011 1111 1001 010

Puesto que los exponentes son diferentes, sería incorrecto sumar directamente las mantisas. Asi pues, el ordenador toma el número más pequeño e incrementa su exponente para igualarlo al del número más grande, esto lo hace pagando el precio de ir moviendo los dígitos de la mantisa hacia la derecha e ir añadiendo ceros por la izquierda. Asi, 10-7 acaba siendo expresado antes de sumarlo al 7, como 0 10000010 0000 0000 0000 0000 0000 000 obviamente, si ahora sumamos el 7 nos da 7. Esto es, cuando usamos el método de la coma flotante (lo cual es lo estandar), hemos de tener cuidad al operar con números de precisiones muy diferentes, pues el error que se comete puede ser enorme.