Computación Paralela con Linux

por Forrest Hoffman y William Hargrove

Traddución por Jordi Cabot Sagrera

Linux ha empezado hace poco a tener un impacto importante dentro de la industria de la informática, pero ha sido una herramienta poderosa para los investigadores en informática durante muchos años. Aparte de los beneficios obvios de trabajar con un sistema operativo abierto eficiente, fiable y de libre distribución [1], la llegada de la computación clusterizada siguiendo el estilo Beowulf-- empezada por Donald Becker, Thomas Sterling, et al. [2] en el NASA's Goddard Space Flight Center-- extiende la utilidad del Linux al mundo de la computación paralela de alto rendimiento. Hoy en día, estos valiosos clusters basados en PCs están apareciendo en laboratorios de investigación federales, departamentos de I+D de empresas, universidades e incluso pequeñas facultades [3, 4]. Si un problema informático no puede solucionarse en un entorno de memoria distribuida flojamente acoplada, un cluster Beowulf -- o Pila de PCs (POP - Pile of PCs)-- puede ser la respuesta, a un precio que los fabricantes tradicionales de computadoras paralelas no pueden llegar.


 
TheStoneSouperComputer
Figura 1: El Stone SouperComputer en el Laboratorio Nacional de Oak Ridge.

Nos involucramos en la computación clusterizada hace más de dos años, después de desarrollar una propuesta para la construcción de un cluster Beowulf para soportar una gran cantidad de proyectos de investigación. La propuesta fue rechazada, pero dado que habíamos empezado el desarrollo de una nueva aplicación de alta resolución para el diseño ecológico, decidimos construir un cluster hecho a base de PCs (principalmente Intel 486s) destinados a ser renovados. Empezamos interceptando, con facilidades federales,  las máquinas sobrantes en Oak Ridge, y procesándolas en nodos útiles. En Septiembre del 1977, teníamos un sistema de computación paralela construido enteramente con hardware sin coste. Hoy en día tenemos un cluster de estilo Beowolf con 126 nodos heterogéneos en constante evolución, llamado el Stone SouperComputer (ver Figura 1), el cual se actualiza constantemente a medida que se dispone de nuevo hardware  y que es usado para el desarrollo de algoritmos y para ejecutar aplicaciones paralelas.  Para más información sobre el Stone SouperComputer, ver Hoffman y Hargrove [3] o visita nuestro World Wide Web (WWW) site en www.esd.ornl.gov/facilities/beowulf.

Construcción de un Beowulf - Un Pequeño Tutorial

Todo el mundo puede construir un computador paralelo adecuado para la enseñanza de la programación paralela y la ejecución de programas paralelos -- muchas veces usando PCs sobrantes o ya existentes. Los PCs en un laboratorio de informática pueden adaptarse para un uso dual, sistemas de encendido dual que les permiten ser rebotados en Linux o en Microsoft Windows, dependiendo de las necesidades del momento. Alternativamente, los equipos no utilizados pueden ser recogidos y fusionados en un sistema paralelo como nosotros hemos hecho.

Nunca dos clusters Beowulf son iguales. De hecho, sus configuraciones hardware y software son tan flexibles y configurables que presentan un amplio abanico de posibilidades. En este tutorial, queremos proporcionar algunas guías y consideraciones para reducir este amplio campo de opciones. Aunque cada cluster es diferente y las configuraciones están dictadas por las necesidades de la aplicación, si que se pueden especificar algunos requerimientos mínimos.

Requerimientos Mínimos

Un nodo tendría que contener, como mínimo, una CPU 486 y una placa madre Intel. Los procesadores Intel 386 funcionarían, pero su rendimiento raramente valdría la pena. Los requerimientos de memoria dependen de los requerimientos de datos de la aplicación y del paralelismo, pero un nodo tendría que contener como mínimo 16MB de memoria. La mayoría de aplicaciones necesitaran 32MB o más por nodo. Usando un espacio de disco centralizado, los nodos se pueden inicializar desde un disquete, un pequeño disco duro o un sistema de archivos en red. Entonces los nodos pueden acceder a su partición raíz desde un servidor de archivos a través de la red, normalmente usando el Network File System (NFS). esta configuración funciona mejor en un entorno con mucho ancho de banda en las conexiones y con un gran rendimiento en el servidor de archivos. Para un mejor rendimiento bajo otras condiciones, cada nodo tendría que tener suficiente espacio en el disco local para el sistema operativo, la memoria virtual y los datos. Cada nodo tendría que tener como mínimo 200 MB de espacio de disco para los componentes del sistema operativo y la memoria virtual, pero 400 MB o más permite tener espacio libre que puede ser usado para las aplicaciones en tiempo de ejecución. Como mínimo cada nodo tiene que incluir una tarjeta de red Ethernet o Fast Ethernet. Alternativamente, interconexiones de más alto rendimiento, incluyendo la Gigabit Ethernet y la Myrinet, podrían ser usadas en conjunción con CPUs más rápidas. Finalmente, cualquier tarjeta de vídeo, una lectora de disquetes, la caja y la batería, completan un nodo funcional.Los teclados y los monitores solo se necesitan para la carga y configuración inicial del sistema operativo, a no ser que las máquinas individuales sean usadas interactivamente además de servir como nodos en el sistema paralelo.

Todos los componentes hardware escogidos necesitan el soporte de drivers o módulos en Linux. Generalmente esto no es un problema si el hardware tiene algunos meses. Muchas fuentes de información acerca del hardware soportado están disponibles en la WWW (ver Recursos más adelante). Particularmente interesante es la completa lista de drivers y la excelente documentación para una amplia variedad de tarjetas de red hecha por Donald Becker's. El soporte delas tarjetas de vídeo no es importante en los nodos, ya que normalmente no ejecutan un servidor X; no obstante, el nodo master puede gestionar el cluster. Un servidor X seria útil para esta máquina. Si un componente particular presenta un problema, preguntar en los grupos de noticias puede ayudar a encontrar información acerca del hardware soportado por Linux.

Conectividad de la red

Si es posible, los nodos tendrían que estar isolados en una red privada de área local con su propio hub o switch Ethernet. Esto evitará que el tráfico de la red normal interfiera en la comunicación entre los nodos y viceversa. Para incrementar aún más el ancho de banda entre los nodos, se pueden instalar tarjetas de red adicionales en los nodos. El software de  Channel Bonding software disponible en www.beowulf.org puede usarse para operar con la red de comunicaciones paralela. El primer nodo, o master, tendría que tener una tarjeta Ethernet adicional para conectarse con la red normal, así como con la red privada. Esto es útil para los logins de usuario y las transferencias de archivos. En la red privada, es necesario usar un bloque de direcciones IP no usadas en ningún otro lugar de Internet. Lo más fácil es usar el espacio de direcciones de la Clase A 10.0.0.0 , reservado para las redes no enrutadas como esta. En este caso el archivo /etc/hosts de cada nodo seria como se muestra en la Tabla 1, y el archivo /etc/hosts.equiv de cada nodo aparecería como en la Tabla 2. Un ejemplo del archivo de configuración ifcfg-eth0 (usado por Red Hat Linux) para el nodo número 2 seria el mostrado en la Tabla 3.

Tabla 1: archivo /etc/hosts para todos los nodos

10.0.0.1 node1
10.0.0.2 node2
10.0.0.3 node3
10.0.0.4 node4
.
.
.

 

Tabla 2: archivo /etc/hosts.equiv para todos los nodos

node1
node2
node3
node4
.
.
.< /CODE>

Tabla 3: archivo /etc/sysconfig/network-scripts/ifcfg-eth0 para el nodo 2

DEVICE=eth0
IPADDR=10.0.0.2
NETMASK=255.0.0.0
NETWORK=10.0.0.0
BROADCAST=10.255.255.255
ONBOOT=yes

Además, es deseable tener un Domain Name Server (DNS) disponible, particularmente si el nombre de los nodos o sus direcciones pueden cambiar en la red privada. Los DNS se pueden ejecutar en el primer nodo para proporcionar la resolución de nombres y direcciones en la red privada .

Almacenamiento Local 

En el momento de cargar el sistema operativo, los constructores del Beowulf tienen que tomar una serie de decisiones acerca de la configuración. Estas decisiones tienen que pensarse cuidadosamente,  ya que cambiarlas requiere reinstalar todos los nodos. La mayoría de los clusters Beowulf basados en Linux usan la distribución de Red Hat Linux, pero cualquier distribución tendría que soportar una clusterización básica. Los patches opcionales para el Kernel que proporcionan un espacio de PID Global y otras ayudas fueron desarrolladas en primer lugar por Red Hat,  pero estas características no son obligatorias para la computación paralela. Cargar Red Hat es muy sencillo y puede hacerse vía CD-ROM o a través de una tarjeta de red desde Internet o desde el primer nodo en el cluster, que tendría que tener una copia de la distribución. Hemos encontrado beneficioso cargar el sistema operativo en los discos de cada nodo vía FTP desde el nodo primario en lugar de montar las particiones raíz vía NFS. Así sacrificamos un poco de facilidad de mantenimiento por un mejor rendimiento en la ejecución. Esta practica elimina trafico de red innecesario, preservado el ancho de banda para el paso de mensajes mientras las aplicaciones se ejecutan.

El entorno de ejecución de Red Hat Linux require solo unos 100 MB de espacio de disco en cada nodo; no obstante, es útil incluir compiladores y otras utilidades en todos los nodos para posibilitar la compilación paralela. Con esto, nuestra configuración requiere 175 MB de espacio en disco para el sistema operativo. Mientras algunos clusters se configuran para usar como memoria virtual un archivo del sistema de archivos normal, es más eficiente usar un partición dedicada a la memoria virtual en el disco local. Se acepta normalmente que la cantidad de espacio razonable para la memoria virtual es el doble que el tamaño de la memoria, hasta los 64 MB. Para los nodos con más de 64 MB de memoria, el espacio para la memoria virtual tendría que ser igual a la cantidad de memoria. En la practica, uno puede desear reservar 128 de espacio para la memoria virtual si el tamaño de la memoria va de 64 a 128 MB. Como resultado, si un nodo previsor con 32MB de memoria tiene dos discos de 202 MB, uno podría cargar Linux en el disco principal (como una partición única) y usar el segundo disco para espacio de memoria virtual (64MB) y espacio local para la ejecución (138 MB).

Gestión del  Cluster 

La gestión y el mantenimiento del sistema puede ser tedioso, particularmente para grandes clusters. No obstante, hay varias utilidades y scripts disponibles en la WWW para ayudar en esta tarea (ver Recursos más adelante). Por ejemplo, los nodos tienen que mantenerse en sincronía con los otros respecto al tiempo y los archivos de sistema (e.g., /etc/passwd, /etc/group, /etc/hosts, /etc/hosts.equiv, etc.). Simples shell scripts ejecutados regularmente por el cron pueden hacer la mayoría de las sincronizaciones..

Una vez todos los nodos están cargados y configurados, las aplicaciones paralelas pueden ser diseñadas y desarrollas para sacar provecho de este nuevo sistema.

Desarrollo de Aplicaciones Paralelas para la Computación Clusterizada

Hay disponibles para Linux tanto compiladores comerciales como gratuitos. Los compiladores del GNU Project's C (gcc), C++ (g++), y FORTRAN (g77) están incluidos en la mayoría de las distribuciones estándar de Linux. Los compiladores de  C y C++ son excelentes y el compilador de FORTRAN mejora constantemente. También hay disponibles compiladores comerciales de Absoft, The Portland Group (PGI), The Numerical Algorithms Group (NAG), y otros. Algunos de los compiladores comerciales de FORTRAN-90 paralelizan automáticamente algunas operaciones si se configuran adecuadamente. En general, no obstante, desarrollar código paralelo requerirá un paso explícito de mensajes entre los procesadores utilizando la PVM (Parallel Virtual Machine - Máquina virtual paralela), MPI (Message Passing Interface - Interfaz de paso de mensajes), o otras librerías de comunicaciones.  Ambas, la PVM y la PMI están disponibles gratuitamente y permiten al programador definir fácilmente los nodos usados para ejecutar el código paralelo y pasar datos entre los nodos durante la ejecución usando simples  invocaciones a la librería.

Por supuesto, no todas las tareas informáticas se pueden adecuar al paralelismo. Muchas veces, se tienen que desarrollar nuevas estrategias para resolver problemas informáticos para poder sacar partido del paralelismo. De hecho, puede ser necesario dar un paso atrás en los códigos serie existentes para concebir una aproximación paralela. Muchos problemas científicos se pueden beneficiar de una descomposición del dominio: una división del espacio o del tiempo en partes relativamente independientes que pueden ser procesados en nodos separados del cluster. Por ejemplo, las tareas de procesamiento de imágenes se pueden dividir normalmente de forma que cada nodo trabaje en una sección de una misma imagen. Esta aproximación es particularmente útil si las secciones de la imagen se procesan independientemente (i.e., el proceso de una sección no requiere información acerca de otras secciones) o el radio de influencia de cada sección es predeterminado y constante.

Una técnica subestimada para saltar al mundo de la computación paralela casi sin coste de desarrollo es usar a ""poor man's parallelism," i.e., múltiples códigos series ejecutándose simultáneamente en múltiples nodos. Esta estrategia de multiplicación, al no tener comunicación entre procesos, es perfectamente escalable, y lleva a un aumento significativo del rendimiento con un pequeño esfuerzo adicional.

Uno de los errores más peligrosos -- ya se este paralelizando código existente o desarrollando nuevo código paralelo -- es convertir un problema computacional en un problema de comunicaciones. Esto puede suceder cuando el problema está demasiado dividido, con lo que el tiempo que se necesita para comunicar los datos entre los nodos y sincronizarlos sobrepasa el tiempo de computación actual de la CPU. En este caso, usar menos nodos puede resultar en un mejor tiempo de ejecución y una utilización más eficiente de los recursos. Este equilibro entre la carga de computación local en un nodo y las comunicaciones para coordinar esfuerzos entre los nodos tiene que ser optimizado para cada aplicación paralela.

Finalmente, la heterogeneidad de los clusters juega un papel importante en el desarrollo de los algoritmos paralelos. Un factor de dos o más entre las velocidades de las CPUs de los nodos es muy significativo cuando se ejecutan aplicaciones paralelas. Si el trabajo se distribuye uniformemente entre todas las CPUs de un cluster heterogéneo, las CPUs más rápidas tendrán que esperar las más lentas para completar su parte dentro de la tarea global. Los algoritmos diseñados correctamente pueden superar esta heterogeneidad sobre dividiendo la tarea de forma que se puedan asignar nuevas subtareas a los nodos que completen las anteriores subtareas asignadas. Por supuesto, esta aproximación tiene que equilibrarse con la sobrecarga de comunicaciones..

El procesamiento paralelo se puede organizar de muchas formas diferentes, pero la organización maestro/esclavo (master/slave) es la más fácil de entender y programar. En una organización maestro/esclavo, un nodo hace de maestro mientras los otros nodos actúan como esclavos. El nodo maestro normalmente es quién decide como dividir el trabajo y generalmente dirige el tráfico mientras los nodos esclavos procesan sus subtareas asignadas y avisan cuando acaban. Variantes de esta organización incluyen una aproximación master-less donde todos los nodos hacen las mismas tareas, o una aproximación jerárquica en la que múltiples capas trabajan juntas o avisan a un súper-maestro. La mejor aproximación viene determinada por el algoritmo o por las necesidades de la aplicación.

El código fuente también se puede organizar de diferentes maneras. En una organización maestro/esclavo, uno puede desarrollar un conjunto de código fuente para el maestro y otro conjunto para los esclavos. Esto era una práctica común en los primeros sistemas paralelos, pero hoy el método Single Program Multiple Data (SPMD) es el más popular y normalmente el más fácil de mantener. Con el SPMD, un solo conjunto de código fuente es desarrollo por lo que el mismo código binario se ejecuta en todos los nodos. El programa bifurca dependiendo de la funcionalidad deseada para el nodo; los maestros realizan un conjunto de operaciones mientras los esclavos realizan otro.

Hay muchas aproximaciones posibles para la organización y la distribución de los datos usados por los programas paralelos. Una posibilidad es servir los datos a todos los nodos vía un servidor NFS central. No obstante, si varios nodos intentar acceder a los datos simultáneamente, esta estrategia llevara a una contención de la red. Una alternativa es pasar partes de datos entre los nodos usando el paso de mensajes, pero esto también implica una gran carga en la red dependiendo del tamaño de los datos y la naturaleza del problema. Otra alternativa es distribuir los datos en los discos locales de todos los nodos antes de empezar la ejecución. Esta distribución manual de los datos en todos los nodos deja la red libre para el paso de mensajes en tiempo de ejecución. De la misma forma, los nodos pueden ensamblar las respuestas y guardar los resultados de forma central, o pueden guardarse localmente par ser recogidos posteriormente a la ejecución. Hemos observado que esta aproximación de "distribuir y recoger" es particularmente útil.

Conclusiones

No hay reglas claras acerca de si construir una máquina o desarrollar código paralelo, porque depende de la aplicación. La optimización de las configuraciones del hardware y los algoritmos no se pueden determinar sin conocer detalles específicos acerca de la aplicación. En un sistema heterogéneo o compartido, optimizar el equilibro entre la carga en los nodos y la comunicación entre los nodos depende de la naturaleza del hardware. Comunicaciones más rápidas animan a una división más fina de la tarea, mientras que una división menor viene favorecida por tener nodos más rápidos.

El movimiento "Beowulf" ha llevado la computación paralela a un muy básico. Los programas paralelos desarrollados en los sistemas Beowulf usando librerías estándares para el paso de mensajes, pueden ejecutarse sin modificaciones en supercomputadores comerciales. De este modo, los clusters Beowulf representan un punto de entrada y más adelante un puente hacia incluso las más grandes supercomputadoras en el mundo. Además, la disponibilidad de baratos y valiosos clusters significa que los entornos de computación paralela pueden dedicarse a tareas específicas, cosa que no puede hacerse con las grandes supercomputadoras comerciales que son demasiado caras para ser dedicadas a una sola aplicación, y no pueden ser optimizadas. Al mismo tiempo que los entornos paralelos están más disponibles para los programadores, la experiencia colectiva ganada promoverá aplicaciones paralelas en todos los campos.

Recursos

Referencias

1
Alper, Joseph. 11 December 1998. "From Army of Hackers, an Upstart Operating System." Science, Vol. 282, No. 5396, pp. 1976-1979.
2
Becker, Donald J., Thomas Sterling, Daniel Savarese, John E. Dorband, Udaya A. Ranawak, Charles V. Packer. 1995. Beowulf: A Parallel Workstation for Scientific Computation. Proceedings, International Conference on Parallel Processing.
3
May, Mike. March 1998. "Piles of PCs." American Scientist, Vol. 26, pp. 128-129.
4
"Supercomputers: Plug and Play." 21 November 1998. The Economist.
5
Hoffman, F. M. and W. W. Hargrove. March 1999. "Cluster Computing: Linux Taken to the Extreme." Linux Magazine, Vol. 1, No. 1, pp. 56-59.
Forrest M.Hoffman
Oak Ridge National Laboratory*
Environmental Sciences Division
P.O. Box 2008
Oak Ridge TN 37831-6036
423-576-7680 voice
423-576-8543 fax
forrest@esd.ornl.gov
 Forrest M. Hoffman es un especialista informático en la División de Ciencias Ambientales en el Laboratorio Nacional de  Oak Ridge en Oak Ridge, Tennessee, donde desarrolla modelos ambientales paralelos (y serie) así como herramientas para la visualización científica, gestión de grandes cantidades de datos, administración de sistemas, y tecnologías de Internet. En su tiempo libre, construye computadoras paralelas.. 
William W. Hargrove
University of Tennessee
Energy, Environment, and Resources Center
Systems Development Institute
10521 Research Drive, Suite 100
Knoxville TN 37932
423-241-2748 voice
423-241-3870 fax
hnw@fire.esd.ornl.gov
 William W. Hargrove  es miembro de la facultad de investigación en la Universidad de Energía, Medio Ambiente y Centro de Recursos de Tenesse, sirviendo con contrato al Laboratorio Nacional de Información Geográfica y espacial de Oak Ridge, y tiene experiencia en algoritmos informáticos, sistemas de Información Geográfica, diseño ecológico y simulación.
__________

*Oak Ridge National Laboratory, managed by Lockheed Martin Energy Research Corp. for the U.S. Department of Energy under contract number DE-AC05-96OR22464.

"The submitted manuscript has been authored by a contractor of the U.S. Government under contract No. DE-AC05-96OR22464. Accordingly, the U.S. Government retains a nonexclusive, royalty-free license to publish or reproduce the published form of this contribution, or allow others to do so, for U.S. Government purposes."
Copyright 1999 Forrest Hoffman and William Hargrove
¿Quiere más artículos de Crossroads articles acerca de la Arquitectura de Computadores? Vaya al índice al siguiente o al  anterior. 

¿Quiere más artículos de Crossroads acerca de Linux? Vaya al índice, al siguiente o al anterior.

Last Modified:
Location:www.acm.org/crossroads/xrds6-1/parallel.html