Herramientas de procesamiento de datos en paralelo. Sistemas paralelos. Sistemas de cluster de clase BEOWULF

Mensajes

• Procesamiento paralelo y en canalización

  El procesamiento de datos en paralelo encarna la idea de realizar varias acciones simultáneamente, como cinta transportadora Y paralelismo.

  Procesamiento paralelo

  Cuando un dispositivo realiza una operación por unidad de tiempo, podemos decir que el dispositivo realizará mil operaciones en mil unidades. Si asumimos que hay cinco dispositivos independientes funcionando simultáneamente, entonces dicho sistema de dispositivos puede realizar las mismas mil operaciones en doscientas unidades de tiempo. Por analogía, un sistema de N dispositivos realizará el mismo trabajo en 1000/N unidades de tiempo. A vida real esto también se aplica, por ejemplo:

  un soldado puede cavar un huerto en 10 horas, y una compañía de soldados de 50 personas con las mismas habilidades con trabajo simultáneo Lo desenterrarán en 12 minutos: el principio de paralelismo en acción.

  Samarsky A.A., que realizó cálculos para simular explosiones nucleares a principios de los años 50, fue un pionero en el procesamiento paralelo de flujos de datos. Samarsky calculó la evolución de la onda expansiva de una manera interesante: sentó en las mesas a varias docenas de personas con máquinas de sumar, obligándolas a transferir datos entre sí simplemente con palabras y anotar los números necesarios en las máquinas de sumar. Se podría decir que esto es
  y existió el primer sistema paralelo. Aunque los cálculos de la bomba de hidrógeno se realizaron con maestría, su precisión fue bastante baja porque la red utilizada tenía pocos nodos y el tiempo de cálculo era demasiado largo.

  Procesamiento del transportador

  Para sumar dos números reales representados en forma de punto flotante, es necesario realizar muchas operaciones pequeñas: comparar órdenes, alinear órdenes, sumar mantisas, normalizar, etc. Los procesadores de las primeras computadoras realizaban todas estas “microoperaciones” para cada par de argumentos de forma secuencial, uno tras otro, hasta llegar al resultado final, y sólo entonces era procesado siguiente par
  términos.

  La esencia del procesamiento de tuberías es aislar las etapas individuales de ejecución. operación general. Cada etapa, una vez completado su trabajo, transmitiría el resultado a la siguiente y al mismo tiempo recibiría una nueva porción de datos. La combinación de operaciones previamente separadas definitivamente tiene un efecto positivo en la velocidad de procesamiento. Por ejemplo, una operación puede tener cinco microoperaciones, cada una de las cuales se realiza en una unidad de tiempo.
  Si hay un dispositivo serie indivisible, procesa 100 pares de argumentos en 500 unidades. Si cada microoperación se divide en una etapa (o etapa) separada de un dispositivo transportador, entonces en la quinta unidad de tiempo, los primeros cinco pares de argumentos estarán en diferentes etapas de procesamiento de dicho dispositivo, y el conjunto completo de cien pares se procesarán en 104 (5+99) unidades de tiempo: la aceleración en comparación con un dispositivo en serie es casi cinco veces (según el número de etapas de la tubería).

  Parecería que el procesamiento de tuberías se puede reemplazar con éxito por el paralelismo convencional; basta con duplicar el dispositivo principal tantas veces como se supone que se asignan las etapas de la tubería. De hecho, 5 dispositivos procesan 100 pares de argumentos en 100 unidades de tiempo, lo que es más rápido que el tiempo de funcionamiento de un dispositivo transportador. Si aumenta cinco veces el número de dispositivos, el volumen de equipos y su costo aumentarán significativamente. Por ejemplo, consideremos una situación en la que se está retirando una cinta transportadora en una planta de automóviles, mientras que es necesario mantener el ritmo de producción de automóviles, se necesitarán mil equipos, cada uno de los cuales puede ensamblar un automóvil de principio a fin; realizando cientos de operaciones diferentes, y en un tiempo bastante corto.

  El coste del coche será colosal. Por eso surgió el procesamiento de tuberías.

  Sistemas paralelos modernos

  Actualmente, existen cuatro direcciones en el desarrollo de alto rendimiento. tecnología informática.

  Computadoras transportadoras vectoriales

  Las características de tales máquinas son un conjunto de comandos vectoriales y dispositivos funcionales de transportador. A diferencia del enfoque tradicional, los comandos vectoriales pueden operar con conjuntos completos de datos independientes, lo que significa que es posible cargar de manera eficiente las tuberías disponibles, es decir, un comando como A=B+C puede significar no sumar dos números, sino dos matrices. Representante característico esta dirección— familia de computadoras de canalización vectorial CRAY.

  Computadoras masivamente paralelas con memoria distribuida.

  La construcción de computadoras de esta clase se distingue por una idea simple: cada microprocesador en serie está equipado con su propia memoria local y luego se conecta a través de algún medio de comunicación. Esta arquitectura tiene muchas ventajas: para aumentar el rendimiento, basta con aumentar el número de procesadores; la configuración óptima se selecciona fácilmente si se conoce la potencia informática necesaria;

  Sin embargo, existe una desventaja significativa que supera muchas de las ventajas. En estas computadoras, la comunicación entre procesadores es mucho más lenta que el procesamiento de datos locales por parte de los propios procesadores. En este sentido, es muy difícil escribir programa efectivo para este tipo de computadoras, para algunos algoritmos esto a veces es simplemente imposible. Ejemplos de este tipo de ordenadores: Intel Paragon, IBM SP1, Parsytec, en cierta medida IBM SP2 y CRAY T3D/T3E, aunque la influencia de esta desventaja en estos ordenadores es mucho menor. Redes de ordenadores, que cada vez se consideran más suficientes alternativa barata Los ordenadores extremadamente caros también pueden clasificarse en la misma clase.

  Computadoras paralelas con memoria compartida

  Toda la RAM de estos ordenadores es compartida por varios procesadores idénticos. Los problemas de la clase anterior se resolvieron, pero se agregaron otros nuevos: por razones técnicas, es imposible aumentar la cantidad de procesadores que tendrían acceso a la memoria compartida. Ejemplos de esta dirección son muchos ordenadores SMP multiprocesador o, por ejemplo, nodos individuales de ordenadores HP Exemplar y Sun StarFire.

  Sistemas combinados

  La última dirección no es independiente, sino simplemente una combinación de las tres anteriores. Formemos un nodo informático a partir de varios procesadores (tradicionales o de canalización vectorial) y una memoria común para ellos. Si falta potencia informática, se pueden combinar varios nodos con canales de alta velocidad. Este tipo de arquitectura se llama arquitectura de clúster. Sun StarFire, NEC SX-5, CRAY SV1, HP ejemplar, últimos modelos IBM SP2 y otros.

  Esta dirección está en momento presente el más prometedor para diseñar computadoras con indicadores de rendimiento récord.

  Niveles de paralelismo

  Dependiendo del nivel en el que se debe garantizar el paralelismo, se utilizan determinados métodos y medios de implementación. Se distinguen los siguientes niveles de paralelismo.

  nivel micro. La ejecución de un comando se divide en fases y las fases de varios comandos vecinos se pueden superponer mediante canalización. Alcanzar este nivel posible en aviones con un procesador.

  Nivel de hilo. Las tareas se dividen en partes que se pueden ejecutar en paralelo (hilos). Este nivel se alcanza en aviones paralelos.

  Nivel de mando. Se ejecutan varias instrucciones en paralelo; el procesador alberga varios canales a la vez. Típico de procesadores superescalares.

  Nivel de trabajo. Las tareas independientes se ejecutan simultáneamente en diferentes procesadores; prácticamente no hay interacción entre sí. El nivel es típico de computadoras con múltiples procesadores y múltiples máquinas.

  El concepto de nivel de paralelismo está estrechamente relacionado con el concepto de granularidad. La granularidad es una medida de la relación entre la cantidad de cálculo realizado en tarea paralela, al volumen de comunicaciones (para mensajería). El grado de granularidad varía desde grano fino hasta grano grueso. La ley de Amdahl se centra en los de grano grueso.
  paralelismo.

  El paralelismo de grano grueso significa que cada cálculo paralelo es suficientemente independiente de los demás, y los cálculos individuales requieren un intercambio de información relativamente poco frecuente entre ellos. Las unidades de paralelización son grandes y programas independientes, incluidos miles de comandos. El sistema operativo proporciona este nivel de paralelismo.

  Para una ejecución paralela eficiente, es necesario equilibrar el grado de granularidad del programa y la cantidad de retraso de comunicación que se produce entre los diferentes gránulos. Para una latencia de comunicación mínima, lo mejor es la partición detallada del programa. En este caso, opera el paralelismo de datos. Si el retraso en la comunicación es grande, entonces es mejor utilizar la partición del programa de grano grueso.

  Literatura

  1. Badenko V.L. Computación de alto rendimiento. Tutorial. - San Petersburgo: Editorial Politécnica. Universidad, 2010. - 180 p.
  2. Barski A.B. Tecnologías de la información paralelas: Libro de texto/A.B. Barsky.-M.: Universidad de Internet tecnologías de la información; BINOMIO. Laboratorio de conocimiento, 2007.-503 p.: ill., tab.-(serie “Fundamentos de las tecnologías de la información”) - p.20-28, p.56-58.
  3. Korneev V.V. Sistemas informáticos.-M.: Helios APB, 2004.-512 p., ill.- p. 34-46
  4. Latsis A.O. Procesamiento de datos en paralelo. M.: Academia, 2010. - 336 p.
  5. Tsilker B.Ya., Orlov S.A. Organización de ordenadores y sistemas. Libro de texto para universidades. - San Petersburgo: Peter, 2004. - 668 p.

Mensajes

Ministerio de Educación y Ciencia de la Federación de Rusia

Agencia Federal para la Educación

Universidad Técnica Estatal del Sur de Rusia

(Instituto Politécnico de Novocherkassk)

Instituto Shakhty (sucursal) SRSTU (NPI)

CONFERENCIAS SOBRE DISCIPLINA

"COMPUTACIÓN PARALELA"

Minas - 2010

Introducción

Conceptos básicos

1. Preguntas generales resolviendo "grandes problemas"

1.1 Desafíos modernos ciencia y tecnología que requiere supercomputadoras para resolver

1.2.2 Modelos abstractos de computación paralela

1.2.3 Métodos procesamiento paralelo datos, error de cálculo

1.3 El concepto de proceso paralelo y gránulos de paralelización.

1.4 Interacción de procesos paralelos, sincronización de procesos.

1.5 Posible aceleración en computación paralela(ley de Amdahl)

2. Principios de la construcción de sistemas informáticos multiprocesador.

2.1 Arquitectura de sistemas informáticos multiprocesador

2.2 Distribución de cálculos y datos en multiprocesadores sistemas computacionales con memoria distribuida

2.3 Clasificación de sistemas informáticos paralelos.

2.4 Sistemas informáticos multiprocesador con memoria distribuida

2.4.1 Supercomputadoras masivamente paralelas de la serie Cry T3

2.4.2 Sistemas de clúster de clase BEOWULF

Conclusión

Referencias

Introducción

Todavía al amanecer era de la computadora A mediados del siglo pasado, los diseñadores de computadoras electrónicas comenzaron a pensar en la posibilidad de utilizar la computación paralela en las computadoras. Después de todo, aumentar la velocidad solo mejorando los componentes electrónicos de una computadora es un método bastante costoso que, además, enfrenta limitaciones impuestas por las leyes físicas. Así, el procesamiento paralelo de datos y el paralelismo de comandos se introdujeron en el diseño de las computadoras, y ahora cualquier usuario de una computadora personal, quizás sin saberlo, está trabajando en una computadora paralela.

Una de las tendencias notables en el desarrollo de la humanidad es el deseo de modelar los procesos de la realidad circundante de la manera más estricta posible para mejorar las condiciones de vida en el presente y predecir el futuro con la mayor precisión posible. Los métodos matemáticos y las técnicas de modelado digital permiten en muchos casos resolver problemas similares Sin embargo, con el tiempo, surge una grave complicación cualitativa y cuantitativa de la tecnología para resolver problemas. En muchos casos, la limitación es la falta de potencia informática de las computadoras electrónicas modernas, pero la importancia de los problemas que se resuelven ha atraído enormes recursos financieros al campo de la creación de computadoras electrónicas de alta complejidad.

Desde hace algún tiempo, aumentar la velocidad de las computadoras de arquitectura tradicional (llamada "von Neumann") se ha vuelto prohibitivamente costoso debido a las limitaciones tecnológicas en la producción de procesadores, por lo que los desarrolladores han centrado su atención en otra forma de aumentar la productividad: combinar computadoras electrónicas. en sistemas informáticos multiprocesador. En este caso, los fragmentos individuales del programa se ejecutan en paralelo (y simultáneamente) en diferentes procesadores, intercambiando información a través de una red informática interna.

La idea de combinar ordenadores electrónicos para aumentar tanto la productividad como la fiabilidad se conoce desde finales de los años cincuenta.

Los requerimientos de obtener el máximo rendimiento al mínimo costo llevaron al desarrollo de sistemas informáticos multiprocesadores; Se conocen sistemas de este tipo que combinan la potencia informática de miles de procesadores individuales. La siguiente etapa son los intentos de unir millones de computadoras heterogéneas en el planeta en un único complejo informático con un rendimiento enorme a través de Internet. Hoy en día, el uso de sistemas informáticos paralelos es una dirección estratégica en el desarrollo de la tecnología informática. El desarrollo de hardware está necesariamente respaldado por la mejora de los componentes algorítmicos y de software: tecnologías de programación paralela.

El método de paralelización de cálculos existe desde hace mucho tiempo; organizar el funcionamiento conjunto de muchos procesadores independientes requiere una investigación teórica y práctica seria, sin la cual una instalación multiprocesador compleja y relativamente costosa a menudo no solo no supera, sino que es inferior en rendimiento a una. computadora tradicional.

El potencial de paralelización no es el mismo para tareas informáticas varios tipos– es importante para programas científicos que contienen muchos ciclos y cálculos largos y mucho menos para problemas de ingeniería, que se caracterizan por cálculos que utilizan fórmulas empíricas.

Consideremos dos preguntas principales:

1. Sistemas informáticos multiprocesador - (supercomputadoras masivamente paralelas) Cray T3D(E) ​​​​con un número de procesadores de 40 a 2176. Se trata de supercomputadoras con memoria distribuida en procesadores RISC del tipo Alpha21164A, con una topología red de comunicacion– un toro tridimensional, un sistema operativo UNIX con un microkernel y traductores para los lenguajes FORTRAN, HPF, C/C++. Modelos de programación soportados: MPI, PVM, HPF.

2. Grupos de estaciones de trabajo de Beowulf. Los clústeres de estaciones de trabajo son una colección de estaciones de trabajo conectadas a una red local. Cluster es un sistema informático con memoria distribuida y control distribuido. Un sistema de clúster puede tener un rendimiento comparable al de las supercomputadoras. Los clústeres de estaciones de trabajo generalmente se denominan clústeres Beowulf (clúster Beowulf, por el proyecto del mismo nombre), conectados por local red ethernet y utilizar el sistema operativo Linux.

Conceptos básicos

La tecnología de programación más común para sistemas de clúster y computadoras paralelas con memoria distribuida es actualmente tecnología MPI. La principal forma en que interactúan los procesos paralelos en dichos sistemas es pasándose mensajes entre sí. Esto se refleja en el nombre de esta tecnología: Message Passing Interface. El estándar MPI define una interfaz que debe ser respetada tanto por el sistema de programación de cada plataforma informática, y por el usuario al crear sus programas. MPI soporta los lenguajes Fortran y C. Versión completa La interfaz contiene descripciones de más de 125 procedimientos y funciones.

La interfaz MPI admite la creación de programas paralelos en el estilo MIMD (Multiple Institution Multiple Data), que implica combinar procesos con diferentes códigos fuente. Sin embargo, escribir y depurar dichos programas es muy difícil, por lo que en la práctica los programadores utilizan con mucha más frecuencia el modelo de programación paralela SPMD (Single Program Multiple Data), dentro del cual se utiliza el mismo código para todos los procesos paralelos. Hoy en día, cada vez más implementaciones MPI admiten el trabajo con los llamados "hilos".

Dado que MPI es una biblioteca, al compilar el programa es necesario vincular los módulos de biblioteca correspondientes.

Después de recibir el archivo ejecutable, debe ejecutarlo en la cantidad requerida de procesadores. Después del lanzamiento, todos los procesos en ejecución ejecutarán el mismo programa; el resultado de la ejecución, según el sistema, se enviará al terminal o se escribirá en un archivo.

Un programa MPI es un conjunto de procesos interactivos paralelos. Todos los procesos se generan una vez, formando una parte paralela del programa. Durante la ejecución de un programa MPI, la generación procesos adicionales o no se permite la destrucción de los existentes (esta posibilidad apareció en versiones posteriores de MPI). Cada proceso opera en su propio espacio de direcciones; no hay variables ni datos compartidos en MPI. La principal forma de interacción entre procesos es mediante el envío de mensajes de forma explícita.

Para localizar la interacción de procesos de programas paralelos, puede crear grupos de procesos, proporcionándoles un entorno de comunicación separado: un comunicador. La composición de los grupos formados es arbitraria. Los grupos pueden coincidir completamente, ser parte unos de otros, no cruzarse o cruzarse parcialmente. Los procesos sólo pueden interactuar dentro de un determinado comunicador; los mensajes enviados en diferentes comunicadores no se cruzan ni interfieren entre sí. Los comunicadores están en idioma Fortran. tipo entero(en lenguaje C – tipo predefinido MPI Comm).

Cuando se inicia un programa, siempre se supone que todos los procesos generados operan dentro del marco de un comunicador integral. Este comunicador siempre existe y sirve para la interacción entre todos los procesos en ejecución del programa MPI. Todas las interacciones entre procesos tienen lugar dentro de un comunicador específico; los mensajes transmitidos en diferentes comunicadores no interfieren entre sí.

Procesadores de conjunto de instrucciones reducido (RISC). La arquitectura RISC (Computadora con conjunto de instrucciones reducido) del procesador se basa en la idea de aumentar la velocidad de su funcionamiento simplificando el conjunto de instrucciones.

Las investigaciones han demostrado que el 33% de las instrucciones de un programa típico son transferencias de datos, el 20% son bifurcaciones condicionales y otro 16% son operaciones aritméticas y lógicas. En la gran mayoría de instrucciones, el cálculo de la dirección se puede realizar rápidamente, en un ciclo. Más modos difíciles El direccionamiento se utiliza en aproximadamente el 18% de los casos. Alrededor del 75% de los operandos son escalares, es decir, variables de número entero, real, de carácter, etc., y el resto son arrays y estructuras. El 80% de las variables escalares son locales y el 90% de las variables estructurales son globales. Por tanto, la mayoría de los operandos son operandos locales de tipos escalares. Se pueden almacenar en registros.

Según las estadísticas, la mayor parte del tiempo se dedica a procesar las declaraciones de "llamada de subrutina" y "retorno de subrutina". Cuando se compilan, estas declaraciones producen largas secuencias de instrucciones de máquina con una gran cantidad de accesos a la memoria, por lo que incluso si la proporción de estas declaraciones es sólo del 15%, consumen la mayor parte del tiempo del procesador. Sólo alrededor del 1% de las rutinas tienen más de seis parámetros y alrededor del 7% de las rutinas contienen más de seis variables locales.

Como resultado del estudio de estas estadísticas, se concluyó que en programa tipico dominar operaciones simples: transferencias aritméticas, lógicas y de datos. Dominar y modos simples direccionamiento. La mayoría de los operandos son variables locales escalares. uno de recursos críticos mejorar el rendimiento es la optimización de estos operadores.

La arquitectura RISC se basa en los siguientes principios e ideas. El conjunto de instrucciones debe ser limitado e incluir solo instrucciones simples, cuyo tiempo de ejecución después del muestreo y decodificación sea de un ciclo de reloj o un poco más. Se utiliza el procesamiento de tuberías. Las instrucciones RISC simples se pueden implementar de manera eficiente en hardware, mientras que las instrucciones complejas solo se pueden implementar en microprogramación. El diseño del dispositivo de control en el caso de la arquitectura RISC se simplifica, lo que permite que el procesador funcione a gran escala. velocidades de reloj. Uso comandos simples le permite implementar de manera efectiva tanto el procesamiento de datos de canalización como la ejecución de comandos.

Las instrucciones complejas tardan más en ejecutarse en un procesador RISC, pero su número es relativamente pequeño. En procesadores RISC pequeño número Las instrucciones se dirigen a la memoria. Recuperar datos de la RAM requiere más de un ciclo de reloj. La mayoría de las instrucciones funcionan con operandos ubicados en registros. Todos los comandos tienen un formato unificado y una longitud fija. Esto hace que cargar y decodificar instrucciones sea más fácil y rápido ya que, por ejemplo, el campo de código de operación y dirección siempre están en la misma posición. Las variables y los resultados intermedios de los cálculos se pueden almacenar en registros. Teniendo en cuenta las estadísticas del uso de variables, la mayoría de Las variables locales y los parámetros de procedimiento se pueden colocar en registros. al llamar nuevo procedimiento El contenido de los registros generalmente se mueve a la RAM, pero si el número de registros es lo suficientemente grande, es posible evitar una parte significativa de las operaciones de intercambio de memoria que consumen mucho tiempo reemplazándolas con operaciones de registro. Gracias a la arquitectura simplificada del procesador RISC, hay espacio en el chip para acomodar conjunto adicional registros

Actualmente, los sistemas informáticos con arquitectura RISC ocupan posiciones de liderazgo en el mercado informático mundial para estaciones de trabajo y servidores. El desarrollo de la arquitectura RISC está asociado con el desarrollo de compiladores, que deben aprovechar de manera efectiva el gran archivo de registro, canalización, etc.

1. Cuestiones generales para la resolución de "grandes problemas"

El término “grandes problemas” suele referirse a problemas cuya solución requiere no sólo la construcción de complejos modelos matemáticos, pero también realizando una gran cantidad de cálculos, muchos órdenes de magnitud mayores que los típicos de las computadoras electrónicas programables. Aquí se utilizan ordenadores electrónicos con los recursos adecuados: el tamaño de las instalaciones operativas y memoria externa, velocidad de las líneas de transmisión de información, etc.

El límite superior en el número de cálculos para "problemas grandes" está determinado únicamente por el rendimiento de los sistemas informáticos actualmente existentes. Al “ejecutar” tareas computacionales en condiciones reales La cuestión no es “resolver el problema en absoluto”, sino “resolverlo en un tiempo aceptable” (horas/decenas de horas).

1.1. Tareas modernas de la ciencia y la tecnología que requieren

para resolver supercomputadoras

Muy a menudo uno tiene que enfrentarse a problemas que, si bien representan un valor considerable para la sociedad, no pueden resolverse con la ayuda de medios relativamente computadoras lentas oficina o clase en casa. La única esperanza en este caso reside en los ordenadores de alta velocidad, comúnmente llamados superordenadores. Sólo las máquinas de esta clase pueden hacer frente al procesamiento. grandes volúmenes información. Estos podrían ser, por ejemplo, datos estadísticos o los resultados de observaciones meteorológicas, información financiera. A veces la velocidad de procesamiento es crítica. Los ejemplos incluyen el pronóstico del tiempo y la modelización del cambio climático. Cuanto antes se predijo desastre natural, aquellos más posibilidades prepárate para ello. Una tarea importante Se trata del modelado de medicamentos, el desciframiento del genoma humano, la tomografía, incluida la médica, la exploración de yacimientos de petróleo y gas. Hay muchos ejemplos que se pueden dar.

Modelar los procesos de la realidad circundante para mejorar las condiciones de vida en el presente y predecir de manera confiable el futuro es una de las tendencias en el desarrollo de la humanidad. Los métodos matemáticos y las técnicas de modelado digital en muchos casos permiten resolver este tipo de problemas; sin embargo, con el tiempo, la tecnología de solución se vuelve más compleja. tareas similares. En muchos casos, la limitación es la falta de potencia informática de los ordenadores electrónicos modernos.

Los requerimientos de obtener el máximo rendimiento al mínimo costo llevaron al desarrollo de sistemas informáticos multiprocesadores; Se conocen sistemas de este tipo que combinan la potencia informática de miles de procesadores individuales.

A continuación se enumeran algunas áreas de la actividad humana que requieren potencia de supercomputadora utilizando computación paralela para su solución:

Predicciones del tiempo, el clima y los cambios atmosféricos globales.

Ciencias de los materiales

Construcción de dispositivos semiconductores.

Superconductividad

Desarrollo farmacéutico

genética humana

Astronomía

Problemas de transporte de gran dimensión.

Dinámica hidráulica y gaseosa.

Fusión termonuclear controlada

Exploración de petróleo y gas

Problemas computacionales en las ciencias oceánicas.

Reconocimiento y síntesis de voz, reconocimiento de imágenes.

Uno de los mayores desafíos es el modelado. sistema climático y pronóstico del tiempo. En este caso, las ecuaciones de dinámica del continuo y las ecuaciones de termodinámica de equilibrio se resuelven numéricamente de forma conjunta. Para simular el desarrollo de procesos atmosféricos durante 100 años y el número de elementos de discretización 2,6 × 106 (una cuadrícula con un paso de 10 en latitud y longitud sobre toda la superficie del Planeta con 20 capas de altura, el estado de cada elemento es descrito por 10 componentes) en cualquier momento el estado de la atmósfera terrestre se describe por 2,6×107 números. Con un paso de muestreo de tiempo de 10 minutos, es necesario determinar 5 × 104 conjuntos durante el período de tiempo simulado (es decir, 1014 valores numéricos requeridos de cálculos intermedios). Al estimar el número de operaciones computacionales necesarias para obtener cada resultado intermedio en 102÷103, el número total de cálculos de punto flotante necesarios para realizar un experimento numérico con un modelo atmosférico global alcanza 1016÷1017.

Una supercomputadora con un rendimiento de 1012 op/s en el caso ideal (carga completa y algoritmización eficiente) realizará dicho experimento en varias horas; Para llevar a cabo el proceso de modelado completo, es necesario ejecutar el programa varias veces (decenas/cientos de veces).

El problema de la supercomputación es tan importante que muchos estados supervisan el trabajo en el campo de las tecnologías de supercomputación.

El apoyo estatal está directamente relacionado con el hecho de que la independencia en la producción y el uso de tecnología informática redunda en interés de la seguridad nacional, y el potencial científico del país está directamente relacionado y está determinado en gran medida por el nivel de desarrollo de la tecnología informática y el software.

A efectos de objetividad a la hora de comparar, el rendimiento de los ordenadores superelectrónicos se calcula basándose en la ejecución de una tarea de prueba previamente conocida (“benchmark”, del banco de pruebas inglés). El rendimiento máximo está determinado por el número máximo de operaciones que se pueden realizar en una unidad de tiempo en ausencia de conexiones entre dispositivos funcionales, caracteriza las capacidades potenciales del equipo y no depende del programa que se esté ejecutando.

La desventaja del método de evaluar el rendimiento máximo como el número de instrucciones ejecutadas por una computadora por unidad de tiempo (MIPS, Millones de instrucciones por segundo) es que sólo proporciona la mayor cantidad de instrucciones posibles. idea general sobre el rendimiento, ya que no tiene en cuenta las características específicas de programas específicos (es difícil predecir en qué fecha y qué instrucciones específicas del procesador se mostrará el programa de usuario).

Cabe señalar que existen argumentos en contra de la generalización. aplicación práctica computación paralela:

Los sistemas informáticos paralelos son prohibitivamente caros. Según la ley de Grosch, confirmada por la práctica, el rendimiento de una computadora crece en proporción al cuadrado de su costo; como resultado, es mucho más rentable obtener el requerido poder de computación comprando uno potente procesador que utilizar varios procesadores más lentos.

Contraargumento. El aumento de velocidad de las computadoras electrónicas secuenciales no puede continuar indefinidamente; las computadoras están sujetas a una rápida obsolescencia y se requieren frecuentes costos financieros para la compra de nuevos modelos. La práctica de crear sistemas informáticos paralelos de la clase Beowulf ha demostrado claramente la rentabilidad de este camino en particular.

Al organizar el paralelismo, las pérdidas de rendimiento aumentan innecesariamente rápidamente. Según la hipótesis de Marvin Minsky, la aceleración computacional lograda cuando se utiliza un sistema paralelo es proporcional al logaritmo binario del número de procesadores (con 1000 procesadores, la aceleración posible es solo 10).

Contraargumento. La estimación de aceleración dada es correcta para paralelizar ciertos algoritmos. Sin embargo, hay una gran cantidad de tareas que, cuando se resuelven en paralelo, se logra una utilización cercana al 100% de todos los procesadores disponibles de un sistema informático paralelo.

Las computadoras en serie mejoran constantemente. Según la conocida Ley de Moore, la complejidad de los microprocesadores secuenciales se duplica cada 18 meses, por lo que el rendimiento requerido se puede lograr en computadoras secuenciales "normales".

Contraargumento. Un desarrollo similar es característico de los sistemas paralelos.

Sin embargo, el uso del paralelismo permite obtener la aceleración de cálculo necesaria sin esperar el desarrollo de procesadores nuevos y más rápidos. La eficiencia del paralelismo depende en gran medida de las propiedades características de los sistemas paralelos. Todas las computadoras electrónicas en serie modernas funcionan de acuerdo con el circuito clásico de von Neumann; Los sistemas paralelos se distinguen por una variedad significativa de arquitectura y el efecto máximo del uso del paralelismo se puede obtener aprovechando al máximo todas las funciones del hardware (la consecuencia es la transferencia algoritmos paralelos y programas entre diferentes tipos de sistemas es difícil y a veces imposible).

Contraargumento. Dada la variedad real de arquitecturas de sistemas paralelos, también existen ciertas formas "establecidas" de garantizar el paralelismo. La invariancia del software creado se garantiza mediante el uso de estándares. software soporte de computación paralela ( bibliotecas de software PVM, MPI, DVM, etc.). PVM y MPI se utilizan en las supercomputadoras Cray-T3.

A lo largo de décadas de funcionamiento de computadoras electrónicas en serie, se ha acumulado una gran cantidad de software enfocado a computadoras electrónicas en serie; procesarlo para computadoras paralelas es prácticamente imposible.

Contraargumento. Si estos programas proporcionan una solución a las tareas asignadas, entonces su procesamiento no es necesario en absoluto. Sin embargo, si los programas secuenciales no permiten obtener soluciones a los problemas en un tiempo aceptable, o existe la necesidad de resolver nuevos problemas, entonces se debe desarrollar un nuevo software que pueda implementarse inicialmente en ejecución paralela.

Existe una limitación en la aceleración de los cálculos con la implementación paralela del algoritmo en comparación con la implementación secuencial.

Contraargumento. De hecho, no existe ningún algoritmo sin una (cierta) parte de cálculos secuenciales. Sin embargo, ésta es la esencia de una propiedad del algoritmo y no tiene nada que ver con la posibilidad de solución paralela del problema en general. Es necesario aprender a aplicar nuevos algoritmos que sean más adecuados para la resolución de problemas en sistemas paralelos.

Así, por cada consideración crítica contra el uso de tecnologías de computación paralela, hay un contraargumento más o menos significativo.

1.2 Procesamiento de datos en paralelo

1.2.1 Posibilidad fundamental del procesamiento paralelo

Casi todos los algoritmos desarrollados hasta la fecha son secuenciales. Por ejemplo, al evaluar la expresión a + b × c, primero debes realizar la multiplicación y solo luego realizar la suma. Si las computadoras electrónicas contienen nodos de suma y multiplicación que pueden operar simultáneamente, entonces en este caso El nodo de suma estará inactivo esperando a que el nodo de multiplicación complete su trabajo. Es posible probar la afirmación de que es posible construir una máquina que procese un algoritmo determinado en paralelo.

Es posible construir m procesadores que, cuando funcionan simultáneamente, producen el resultado deseado en un solo ciclo de reloj de la computadora.

En teoría, estas máquinas "multiprocesador" podrían construirse para cada algoritmo específico y aparentemente "evitar" la naturaleza secuencial de los algoritmos. Sin embargo, no todo es tan simple: hay infinitos algoritmos específicos, por lo que el razonamiento abstracto desarrollado anteriormente no está tan directamente relacionado con el significado práctico. Su desarrollo nos convenció de la posibilidad misma de la paralelización, se convirtió en la base del concepto de paralelismo ilimitado y permitió considerar desde una perspectiva general la implementación de los llamados entornos informáticos: sistemas multiprocesador, ajustado dinámicamente a un algoritmo específico.

1.2.2. Modelos abstractos de computación paralela

El modelo de computación paralela proporciona un enfoque de alto nivel para la caracterización y comparación del tiempo de ejecución. varios programas, mientras se abstrae de hardware y detalles de ejecución. Primero modelo importante La computación paralela fue introducida por una máquina de acceso aleatorio paralela (PRAM - Parallel Random Access Machine), que proporciona una abstracción de una máquina de memoria compartida (PRAM es una extensión del modelo RAM - Random Access Machine de una máquina de acceso aleatorio en serie). El modelo BSP (Bulk Synchronous Parallel) combina abstracciones de memoria compartida y distribuida. Se supone que todos los procesadores ejecutan instrucciones de forma sincrónica; en el caso de ejecutar la misma instrucción, PRAM es una máquina SIMD abstracta (SIMD - flujo de instrucción única / flujo de datos múltiple - un flujo de instrucción único junto con un flujo de datos múltiple), sin embargo, los procesadores pueden ejecutar instrucciones diferentes. Los comandos principales son leer de la memoria, escribir en la memoria y operaciones lógicas y aritméticas ordinarias.

El modelo PRAM está idealizado en el sentido de que cada procesador puede acceder a cualquier celda de memoria en cualquier momento (las operaciones de escritura realizadas por un procesador son visibles para todos los demás procesadores en el orden en que se realizaron, pero las escrituras realizadas por diferentes procesadores, puede ser visible en cualquier orden). Por ejemplo, cada procesador en PRAM puede leer datos de una celda de memoria o escribir datos en la misma celda. Esto, por supuesto, no sucede en máquinas paralelas reales, ya que los módulos de memoria en el nivel físico organizan el acceso a la misma celda de memoria. Además, el tiempo de acceso a la memoria en máquinas reales no es el mismo debido a la presencia de cachés y posibles organización jerárquica módulos de memoria.

El modelo PRAM básico admite lecturas y escrituras simultáneas (en este contexto, paralelas). Se conocen submodelos PRAM que tienen en cuenta reglas que permiten evitar situaciones de conflicto cuando varios procesadores acceden simultáneamente a la memoria compartida.

El teorema de Brent nos permite modelar circuitos de elementos funcionales utilizando máquinas de acceso aleatorio paralelas (PRAM). Los elementos funcionales pueden ser 4 básicos (realizar operaciones lógicas NOT, AND, OR, XOR - negación, AND lógico, OR lógico y OR exclusivo, respectivamente), NAND y NOR más complejos (AND-NOT y OR-NOT), y cualquier complejidad.

A continuación, se supone que el retraso (es decir, el tiempo de respuesta, el tiempo después del cual aparecen los valores de señal previstos en la salida del elemento después de que se han establecido los valores en las entradas) es el mismo para todos los elementos funcionales.

Consideramos un circuito de elementos funcionales conectados sin formar ciclos (asumimos que elementos funcionales tener cualquier número de entradas, pero exactamente una salida: un elemento con varias salidas puede ser reemplazado por varios elementos con la única salida). El número de entradas determina la potencia de entrada del elemento, y el número de entradas a las que está conectada la salida del elemento determina su potencia de salida. Generalmente se supone que las potencias de entrada de todos los elementos utilizados están acotadas arriba, mientras que las potencias de salida pueden ser cualquiera. El tamaño de un circuito se refiere al número de elementos que contiene, mayor número elementos en los caminos desde las entradas del circuito hasta la salida del elemento se llama profundidad de este elemento (la profundidad del circuito es igual a la mayor de las profundidades de sus elementos constituyentes).

Figura 1. Simulación de un circuito de tamaño 15 y profundidad 5 con dos procesadores utilizando una máquina de acceso aleatorio paralela (máquina PRAM)

La Figura 1 muestra el resultado de modelar un circuito de tamaño (número total de procesadores) n=15 con una profundidad de circuito (número máximo de elementos en cada nivel de profundidad) d=5 con el número de procesadores p=2 (los elementos simulados simultáneamente son combinados en grupos por áreas rectangulares, y para cada grupo se indica el paso en el que se modelan sus elementos, el modelado se produce secuencialmente de arriba a abajo en orden de profundidad creciente, en cada profundidad p piezas a la vez). Según el teorema de Brent, modelar un circuito de este tipo no requerirá más de ceil(15/2+1)=9 pasos.

1.2.3. Métodos de procesamiento de datos paralelos, error de cálculo.

Son posibles los siguientes modos de ejecución de partes independientes del programa:

Ejecución paralela: se ejecutan varios comandos de procesamiento de datos al mismo tiempo; Este modo de computación se puede lograr no solo mediante la presencia de varios procesadores, sino también mediante el uso de dispositivos de procesamiento de vectores y tuberías.

Computación distribuida: este término se utiliza generalmente para designar un método de procesamiento de datos en paralelo, que utiliza varios dispositivos de procesamiento suficientemente alejados entre sí y en el que la transmisión de datos a través de líneas de comunicación provoca importantes retrasos.

Con este método de organización de cálculos, el procesamiento de datos es efectivo solo para algoritmos paralelos con baja intensidad de flujos de transferencia de datos entre procesadores; Así funcionan, por ejemplo, los sistemas informáticos multimáquina, formados mediante la combinación de varios ordenadores electrónicos individuales utilizando canales de comunicación de redes de información locales o globales.

Formalmente, esta lista también puede incluir el modo multitarea (modo de tiempo compartido), en el que se utiliza un solo procesador para ejecutar procesos; Este modo es conveniente para depurar aplicaciones paralelas.

Hay dos formas de procesar datos en paralelo: paralelismo y canalización.

El paralelismo presupone la presencia de p dispositivos idénticos para procesar datos y un algoritmo que permite a cada uno realizar una parte independiente de los cálculos; al final del procesamiento, los datos parciales se recopilan juntos para obtener el resultado final; En este caso, aceleraremos el proceso p veces. No todos los algoritmos pueden paralelizarse exitosamente de esta manera (una condición natural para la paralelización es el cálculo de partes independientes de los datos de salida utilizando los mismos procedimientos, o similares; la iteración o la recursividad causan mayores problemas al paralelizar).

La idea del procesamiento de canalizaciones es aislar las etapas individuales de la realización de una operación general, y cada etapa, después de completar su trabajo, pasa el resultado a la siguiente, al mismo tiempo que acepta una nueva porción de datos de entrada. Cada etapa de procesamiento es realizada por su propia parte del dispositivo de procesamiento de datos (etapa transportadora), cada etapa realiza una acción específica (microoperación); procesamiento general datos requiere la operación de estas partes de forma secuencial.

Al ejecutar comandos, el sistema transportador imita el funcionamiento de un transportador de una planta de ensamblaje, en el que un producto pasa secuencialmente por varias estaciones de trabajo; y en cada uno de ellos el producto es nueva operación. El efecto de aceleración se consigue mediante el procesamiento simultáneo de varios productos en diferentes lugares de trabajo.

La aceleración de los cálculos se logra utilizando todas las etapas de la canalización para el procesamiento de datos en tiempo real (los datos se transmiten a la entrada de la canalización y se procesan secuencialmente en todas las etapas). Las canalizaciones pueden ser dispositivos escalares o vectoriales (la única diferencia es que en el último caso se pueden utilizar vectores de instrucciones). En el caso de un transportador de longitud l, el tiempo de procesamiento de n operaciones independientes será l+n−1 (cada etapa opera por unidad de tiempo). Cuando se utiliza un dispositivo de este tipo, procesar una sola porción de datos de entrada requerirá l×n tiempo, y solo para muchas porciones obtendremos una aceleración computacional cercana a l.

En la Figura 2 se puede ver que el rendimiento E de un dispositivo transportador crece asintóticamente al aumentar la longitud n del conjunto de datos en su entrada, tendiendo a un rendimiento máximo teórico de 1/τ

Figura 2. Rendimiento del dispositivo transportador en función de la longitud del conjunto de datos de entrada

1.3. El concepto de proceso paralelo y gránulos de paralelización.

El esquema más general para realizar cálculos secuenciales y paralelos se muestra en la Figura 3 (los tiempos S y E son el comienzo y el final de la tarea, respectivamente).

Figura 3. Diagramas de ejecución de procesos para cálculo secuencial - a), con paralelización cercana al ideal - b) y en el caso general de paralelización - c)

Un proceso es un nombre que se le da a ciertas secuencias de comandos que, al igual que otros procesos, afirman utilizar el procesador para su ejecución; Los comandos (instrucciones) dentro del proceso se ejecutan secuencialmente, no se tiene en cuenta el paralelismo interno.

En la Figura 3, las líneas finas muestran las acciones de creación de procesos e intercambio de datos entre ellos, las líneas gruesas muestran la ejecución real de los procesos (el eje x es el tiempo). En el caso de cálculos secuenciales, se crea un único proceso (Figura 3a) que realiza acciones necesarias; en ejecución paralela El algoritmo requiere varios procesos (ramas paralelas de la tarea). En el caso ideal, todos los procesos se crean simultáneamente y finalizan al mismo tiempo (Figura 3b); en el caso general, el diagrama del proceso es mucho más complicado y representa una especie de gráfico (Figura 3c).

La longitud característica de un grupo de instrucciones ejecutadas secuencialmente en cada uno de los procesos paralelos se denomina tamaño del gránulo (grano). En cualquier caso, es aconsejable optar por el “grano grueso” (ideal – diagrama 3b). Normalmente, el tamaño de un grano (gránulo) es de decenas a cientos de miles de operaciones de máquina (que es un orden de magnitud mayor que el tamaño típico de un operador de Fortran o C/C++). Dependiendo del tamaño de los gránulos, se habla de paralelismo de grano fino y de grano grueso.

El tamaño del gránulo también está influenciado por la conveniencia de la programación: un determinado fragmento lógicamente completo del programa a menudo se diseña en forma de gránulo. Es aconsejable esforzarse por lograr una carga uniforme de los procesadores.

El desarrollo paralelo del programa es no es una tarea fácil debido a la dificultad de identificar el paralelismo (generalmente oculto) en un programa (es decir, identificar partes del algoritmo que se pueden ejecutar de forma independiente entre sí).

Automatizar la detección de paralelismo en algoritmos no es fácil y es poco probable que se resuelva por completo en un futuro próximo. Al mismo tiempo, durante décadas de funcionamiento de la tecnología informática, se ha desarrollado tal cantidad de algoritmos secuenciales que no se puede hablar de paralelización manual.

Incluso modelo más simple La computación paralela nos permite identificar una circunstancia importante: el tiempo de intercambio de datos debe ser lo más corto posible con respecto al tiempo de ejecución de la secuencia de comandos que forman el gránulo.

Para problemas reales (tradicionalmente) tamaño característico Los granos de paralelización son varios órdenes de magnitud mayores que el tamaño característico de un operador de lenguaje de programación tradicional (C/C++ o Fortran).

1.4. Interacción de procesos paralelos, sincronización de procesos.

La ejecución de comandos de programas forma un proceso computacional; en el caso de la ejecución de varios programas en una memoria común o compartida y el intercambio de mensajes entre estos programas, se acostumbra hablar de un sistema de procesos interactivos concurrentes.

Creación y destrucción de procesos tipo UNIX. sistemas operativos ejecutado por operadores (llamadas al sistema).

El paralelismo a menudo se describe en términos de declaraciones macro. En lenguajes paralelos, las ramas paralelas se inician utilizando el operador JOIN.

Para los sistemas informáticos multiprocesador, garantizar la sincronización de los procesos es de particular importancia. Por ejemplo, el momento en el que comienza el intercambio de datos entre procesadores no está acordado a priori de ninguna manera y no puede determinarse con precisión, ya que depende de muchos parámetros difíciles de estimar del funcionamiento de los sistemas informáticos multiprocesador, mientras que la sincronización es simplemente necesaria para asegurar una reunión para el intercambio de información. En los sistemas informáticos multiprocesador débilmente acoplados no se puede esperar en absoluto una sincronización absoluta de los relojes de las máquinas de los procesadores individuales; sólo se puede hablar de medir intervalos de tiempo en el sistema de tiempo de cada procesador.

La sincronización es una forma eficaz de prevenir situaciones de "punto muerto", una situación en la que cada uno de los procesos que interactúan ha recibido a su disposición parte de los recursos que necesita, pero ni él ni los demás procesos tienen recursos suficientes para completar el procesamiento y posteriormente liberar recursos.

Los sistemas de programación paralela utilizan técnicas de sincronización de alto nivel. La tecnología de programación paralela MPI utiliza un esquema de sincronización para el intercambio de información entre procesos.

La sincronización también puede ser compatible con hardware (por ejemplo, sincronización de barrera en la supercomputadora Cray T3, con la ayuda de la cual todos los procesos esperan hasta un cierto punto en el programa, después de alcanzar el cual es posible seguir trabajando).

1.5. Posible aceleración en la computación paralela (ley de Amdahl)

Es de interés estimar la magnitud del posible aumento de la productividad, teniendo en cuenta las características cualitativas del propio programa inicialmente secuencial.

Figura 4. Esquema para derivar la ley de Amdahl

La Ley de Amdahl (1967) relaciona la aceleración potencial de la paralelización con la fracción de operaciones que se realizan a priori de forma secuencial. Sea f(0

Al transferir el algoritmo a una máquina paralela, el tiempo de cálculo se distribuirá de la siguiente manera:

f×ts – tiempo de ejecución de una parte del algoritmo que no se puede paralelizar,

· (1-f)×ts/n – tiempo empleado en ejecutar la parte paralelizada del algoritmo.

El tiempo t p requerido para el cálculo en una máquina paralela con n procesadores es

t p =f×ts+(1-f)×ts/n .

Aceleración del tiempo de cálculo con una pequeña proporción de operaciones secuenciales (f<<1) возможно достичь (не более чем в n раз) ускорения вычислений.

En el caso de f=0,5, ¡es imposible lograr S>2 con cualquier número de procesadores! Tenga en cuenta que estas restricciones son de naturaleza fundamental (no se pueden eludir para un algoritmo determinado), pero una estimación práctica de la fracción f de operaciones secuenciales suele ser imposible a priori.

Por tanto, las características cualitativas del propio algoritmo imponen restricciones a la posible aceleración durante la paralelización. Por ejemplo, los algoritmos de cálculo que utilizan fórmulas secuenciales, característicos de los cálculos de ingeniería, están mal paralelizados (la parte f es significativa), mientras que, al mismo tiempo, los algoritmos que pueden reducirse a problemas de programación lineal están paralelizados satisfactoriamente.

No es fácil estimar a priori la fracción de operaciones secuenciales f. Sin embargo, se puede intentar utilizar formalmente la ley de Amdahl para resolver el problema inverso de determinar f a partir de datos de rendimiento experimentales; esto permite juzgar cuantitativamente la eficiencia de paralelización lograda.

Figura 6. Rendimiento de un sistema de cluster de computación usando el procedimiento de multiplicación de matrices (experimento y cálculo usando la fórmula de Amdahl)

La Figura 6 muestra los resultados de un experimento en el grupo SCI-MAIN del Centro de Investigación en Computación de la Universidad Estatal de Moscú sobre el problema de la multiplicación de matrices usando un esquema de tiras (dimensión 103 × 103 números reales de doble precisión), los datos experimentales se ajustan mejor (se utilizó el método de mínimos cuadrados) corresponden a la fórmula de Amdahl con f = 0,051.

La ley de Amdahl es conveniente para el análisis cualitativo del problema de paralelización.

2. Principios de la construcción de sistemas informáticos multiprocesador.

2.1. Arquitectura de sistemas informáticos multiprocesador.

La arquitectura de las computadoras paralelas se ha desarrollado casi desde el comienzo de su creación y uso, y en una variedad de direcciones. Las disposiciones más generales conducen a dos clases: computadoras con memoria compartida y computadoras con memoria distribuida. Las computadoras con memoria compartida constan de múltiples procesadores que tienen igual prioridad de acceso a la memoria compartida con un único espacio de direcciones (Figura 7a).

Figura 7. Computadoras paralelas:

a) con memoria compartida b) con memoria distribuida

Un ejemplo típico de dicha arquitectura son las computadoras de clase SMP (Symmetric Multi Processors), que incluyen varios procesadores, pero una memoria, un conjunto de dispositivos de entrada/salida y un sistema operativo. La ventaja de las computadoras con memoria compartida es la relativa facilidad de programar tareas paralelas; la desventaja es la escalabilidad insuficiente. Los sistemas SMP reales no suelen contener más de 32 procesadores; se utiliza la tecnología NUMA para aumentar aún más la potencia informática de dichos sistemas.

En las computadoras con memoria distribuida (sistemas multicomputadoras), cada nodo informático es una computadora completa e incluye un procesador, memoria, dispositivos de entrada/salida, sistema operativo, etc. (Figura 7b). Un ejemplo típico de dicha arquitectura son los sistemas informáticos de clase MPP (procesamiento masivo en paralelo), en los que se combinan nodos informáticos homogéneos mediante algún medio de comunicación. La ventaja de las computadoras con memoria distribuida es la escalabilidad (casi ilimitada) la desventaja es la necesidad de utilizar software especializado (bibliotecas de mensajería) para realizar intercambios de información entre nodos informáticos. Para sistemas informáticos multiprocesador con memoria compartida y distribuida, se utilizan los términos máquinas estrechamente y débilmente acopladas, respectivamente.

Como se ha demostrado, el rendimiento de los canales de comunicación afecta en gran medida la capacidad de paralelizar de manera efectiva, y esto es importante para ambas arquitecturas consideradas. El sistema de comunicación más simple es un bus común (Figura 8a), que conecta todos los procesadores y la memoria; sin embargo, incluso si el número de dispositivos en el bus es más de varias docenas, el rendimiento del bus cae catastróficamente debido a la influencia mutua y la competencia de dispositivos para la propiedad monopólica del autobús durante el intercambio de datos.

Figura 8. Sistemas multiprocesador

a) - con un bus común, b) - con un interruptor matricial

c) - con interruptores en cascada (red Omega)

Se utilizan enfoques más sofisticados para construir sistemas más potentes. Un esquema de conmutación matricial eficaz es (Figura 8b), en el que los dispositivos se conectan entre sí mediante interruptores bidireccionales que permiten o prohíben la transferencia de información entre los módulos correspondientes. Una alternativa es conectar los interruptores en cascada; por ejemplo, según el esquema de la red Omega (Figura 8c). Además, cada conmutador puede conectar cualquiera de sus dos entradas a cualquiera de las dos salidas; en este caso, para conectar n procesadores con n bloques de memoria, se requieren n×log2n/2 conmutadores. La desventaja de los esquemas con interruptores en cascada es el retraso en el funcionamiento del interruptor.

Para sistemas con memoria distribuida, se utilizan casi todas las opciones de conexión imaginables (Figura 9), mientras que el parámetro de calidad en términos de velocidad de transmisión de mensajes es la longitud promedio de la ruta que conecta procesadores arbitrarios; En este caso nos referimos al camino físico, ya que implementar la topología lógica (mediante software) no presenta ninguna dificultad.

Figura 9. Opciones para topologías de comunicación de procesadores en sistemas informáticos multiprocesador

La topología lineal más simple (Figura 9a) corresponde satisfactoriamente a muchos algoritmos, que se caracterizan por la conexión entre sí únicamente de procesos vecinos (problemas unidimensionales de física matemática y multidimensionales, reducidos a unidimensionales); La desventaja es la incapacidad de transmitir mensajes si hay una interrupción en algún lugar. Al reducir a la mitad la longitud promedio de la ruta y aumentar la confiabilidad de la comunicación (si se interrumpe la comunicación, los mensajes se pueden transmitir en la dirección opuesta, aunque a una velocidad más baja), se logra la conexión del primer nodo al último: se crea una topología en "anillo". obtenido (Figura 9b).

La topología “estrella” (Figura 9c) corresponde mejor a la distribución de carga entre procesos, característica de los sistemas “cliente/servidor” (el nodo maestro “distribuye” tareas y “recopila” los resultados de los cálculos, mientras que los nodos esclavos interactúan con entre sí mínimamente).

La topología reticular (Figura 9d) se utilizó a principios de los años noventa al construir la supercomputadora Intel Paragon basada en procesadores i860; encontrar la ruta mínima de transferencia de datos entre los procesadores A y B para la topología de “red tridimensional” se ilustra en la Figura 10. La topología de “toro bidimensional” (Figura 9d) expande la “red bidimensional” con conexiones adicionales que reduce la longitud del camino promedio (por supuesto, un "toro tridimensional") y es característico de la tecnología de red SCI. Se utiliza una topología de "camarilla" tridimensional (Figura 9e), caracterizada por la presencia de cada procesador comunicándose con cada uno. La Figura 9h muestra una vista general de la topología de comunicación completa de todos los procesadores entre sí; Esta topología se caracteriza por la longitud de ruta promedio más corta entre procesadores, pero es prácticamente imposible de implementar en hardware con una cantidad significativa de procesadores debido al aumento catastrófico en la cantidad de conexiones.

La topología de "hipercubo" (Figura 9i) se caracteriza por una longitud de ruta promedio reducida y proximidad a las estructuras de muchos algoritmos de cálculo numérico, lo que garantiza un alto rendimiento. Un hipercubo de N dimensiones contiene 2N procesadores. Un hipercubo bidimensional es un cuadrado, un hipercubo tridimensional forma un cubo regular y un hipercubo de cuatro dimensiones es un cubo dentro de un cubo. Para la familia de supercomputadoras nCube, un hipercubo de dimensión máxima 13 contiene 8192 procesadores; en el sistema nCube 3, el número de procesadores puede llegar a 65536 (hipercubo de 16 dimensiones).

Los siguientes indicadores se utilizan a menudo como características principales de la topología de la red de datos:

Figura 10. Encontrar la ruta mínima para transmitir mensajes entre procesadores en una topología de celosía tridimensional

El diámetro se define como la distancia máxima (normalmente el camino más corto entre procesadores) entre dos procesadores en la red. Este valor caracteriza el tiempo máximo requerido para la transferencia de datos entre procesadores (el tiempo de transferencia es, en una primera aproximación, directamente proporcional al camino; longitud).

La conectividad es un indicador que caracteriza la presencia de diferentes rutas de transferencia de datos entre procesadores de red; un tipo específico de indicador se puede definir, por ejemplo, como el número mínimo de arcos que deben eliminarse para dividir la red de datos en dos áreas desconectadas.

El ancho de división binaria es un indicador definido como el número mínimo de arcos que se deben eliminar para dividir una red de datos en dos áreas desconectadas del mismo tamaño.

El costo se define, por ejemplo, como el número total de líneas de datos en un sistema informático multiprocesador.

Parece natural combinar las ventajas de los sistemas con memoria compartida (relativa facilidad para crear programas paralelos) y distribuida (alta escalabilidad); La solución a este problema fue la creación de computadoras con arquitectura NUMA (Acceso No Uniforme a Memoria).

En este sentido, los ordenadores SMP clásicos cuentan con una arquitectura UMA (Uniform Memory Access). Esto utiliza un mecanismo (generalmente a nivel de hardware, el que sea más rápido) que permite a los programas de usuario tratar toda la memoria (físicamente) distribuida entre los procesadores como un único espacio de direcciones. Ejemplos de computadoras NUMA son el sistema Cm, construido en los años setenta y que contiene un conjunto de clusters unidos por un bus entre clusters, y el complejo BBN Butterfly que combina 256 procesadores (1981, BBN Advanced Computers).

2.2. Distribución de cálculos y datos en multiprocesadores.
sistemas informáticos de memoria distribuida

Si un sistema informático multiprocesador contiene nodos informáticos con RAM local, además de distribuir partes del cálculo entre nodos informáticos individuales, es importante distribuir racionalmente los datos (por ejemplo, bloques de matrices procesadas de dimensión significativa) entre los nodos informáticos disponibles. El hecho es que el tiempo dedicado al intercambio de datos entre los nodos informáticos que procesan estos datos y los nodos informáticos que los almacenan en su RAM local puede ralentizar el proceso de cálculo en órdenes de magnitud.

Está claro que la ubicación de un gran conjunto de datos en un nodo informático no es aconsejable debido a la inevitable pérdida significativa de tiempo para organizar la transferencia de bloques individuales de estos datos al nodo informático de procesamiento. Por otro lado, una división puramente formal de los datos en un número de bloques igual al número del nodo informático conlleva el mismo problema.

La distribución racional de datos a través de la RAM local de un nodo informático debe llevarse a cabo teniendo en cuenta la frecuencia de acceso de cada nodo informático a cada bloque de datos ubicado en los nodos informáticos correspondientes, esforzándose por minimizar el número de intercambios, lo que requiere determinar la fina estructura de información del algoritmo.

Parecería que, en el caso general, es posible construir una determinada función de la complejidad (por ejemplo, en términos de tiempo) de los cálculos, teniendo en cuenta tanto los costos de recursos de los propios cálculos como la complejidad de los intercambios para un determinado distribución de datos entre nodos informáticos y mayor minimización de esta función de acuerdo con el parámetro (parámetros) de distribución de datos; Además, la propia distribución puede ser modificable. En realidad, la construcción de dicha función es difícil debido a la necesidad de cuantificar los parámetros de tiempo de las operaciones e identificar parámetros de optimización importantes. Un candidato para el papel de dicha función podría ser, por ejemplo, la ley de redes de Amdahl descrita anteriormente.

Los paquetes estándar para resolver problemas de álgebra lineal utilizan métodos para distribuir datos entre nodos informáticos, basados ​​en análisis teóricos y prácticas a largo plazo.

2.3. Clasificación de sistemas informáticos paralelos.

La clasificación de las arquitecturas de sistemas informáticos tiene como objetivo identificar tanto los principales factores que caracterizan cada arquitectura como las interrelaciones de las estructuras informáticas paralelas.

SISD (flujo de instrucción único/flujo de datos único): flujo de comando único y flujo de datos único; La clase SISD incluye máquinas secuenciales clásicas (tipo von Neumann). En tales máquinas hay sólo un flujo de instrucciones (procesadas secuencialmente), cada una de las cuales inicia una operación escalar. A esta clase también pertenecen las máquinas con tecnología de procesamiento mediante cinta transportadora.

SIMD (flujo de instrucción única/flujo de datos múltiple): un flujo de comando único junto con un flujo de datos múltiple. En este caso, se conserva un flujo de comandos, pero incluye comandos vectoriales que realizan una operación aritmética con muchos datos a la vez. Las operaciones vectoriales se pueden realizar mediante una matriz de procesadores (como en la máquina ILLIAC IV) o mediante un método de canalización (Cray-1). De hecho, los microprocesadores Pentium VI y Xeon con el conjunto de instrucciones MMX, SSE, SSE2 son sistemas SIMD de un solo chip.

En los países de la CEI, los sistemas SIMD deberían llamarse PS-2000 (1972 - 1975), un sistema informático altamente paralelo para procesar información con una productividad de hasta 200 millones de operaciones por segundo.

MISD (flujo de instrucciones múltiples/flujo de datos único): flujo de comandos múltiples y flujo de datos único. La arquitectura implica la presencia de muchos procesadores que procesan el mismo flujo de datos; Se cree que tales máquinas no existen.

MIMD (flujo de instrucciones múltiples/flujo de datos múltiples): múltiples flujos de comandos y datos. La clase MIMD incluye dos tipos de máquinas: controladas por flujo de comandos y controladas por flujo de datos; Si las computadoras del primer tipo utilizan la ejecución tradicional de comandos secuencialmente en su ubicación en el programa, entonces el segundo tipo implica activar los operadores tal como están actualmente listos.

La clase asume la presencia de varios procesadores combinados en un solo complejo, cada uno de los cuales trabaja con su propio flujo de comandos y datos.

Un ejemplo clásico es el sistema Denelcor HEP (Procesador de elementos heterogéneos); contiene hasta 16 módulos de procesador, conectados a través de un conmutador de varias etapas a 128 módulos de memoria de datos, y todos los módulos de procesador pueden funcionar de forma independiente entre sí con sus propios flujos de comandos, y cada módulo de procesador puede admitir hasta 50 flujos de comandos de usuario.

2.4. Sistemas informáticos multiprocesador con memoria distribuida.

Desde la última década del siglo XX, los sistemas de memoria distribuida han tendido a monopolizar las arquitecturas de supercomputadoras, y los dispositivos disponibles en el mercado se utilizan cada vez más como procesadores en nodos informáticos. Las principales ventajas de estos sistemas son la enorme escalabilidad (según la clase de tareas a resolver y el presupuesto, el usuario puede solicitar un sistema con un número de nodos desde varias decenas hasta miles); lo que llevó a la aparición de un nuevo nombre para los sistemas considerados: computadoras masivamente paralelas (sistemas informáticos de arquitectura MPP - procesamiento masivo en paralelo).

El primer superordenador con procesamiento paralelo masivo, el Connection Machine (CM-1), estaba equipado con 64.000 procesadores, cada uno con su propia memoria. SM-1 escaneó 16 mil artículos con noticias de última hora en 1/20 de segundo. y desarrolló un circuito integrado procesador con 4 mil transistores en tres minutos. Los representantes convexos de los sistemas MPP son las supercomputadoras de la serie Cry T3.

Cry T3E (1350) es un sistema informático multiprocesador fabricado en 2000, con memoria distribuida construida a partir de procesadores RISC. La topología de la red de comunicación es un toro tridimensional. Sistema operativo UNICOS/mk (sistema operativo UNIX con microkernel). Traductores para lenguajes FORTRAN, HPF, C/C++. Frecuencia de reloj 675 MHz. El número de procesadores es de 40 a 2176. La cantidad máxima de RAM para cada nodo es 512 MB y la velocidad máxima es 2938 Gflop/s. A diferencia de su predecesor, el Cry T3D, este sistema no requiere una computadora frontal.

El sistema utiliza un procesador Alpha21164A, sin embargo, si es necesario, se puede reemplazar fácilmente por otro, por ejemplo, un procesador más rápido. Cada elemento de procesamiento contiene una unidad central de procesamiento, un módulo de memoria y una unidad de comunicaciones para comunicarse con otros procesadores. La capacidad del canal de comunicación entre procesadores es de 325 MB/s.

Se admiten los modelos de programación MPI, PVM, HPF y la propia biblioteca de mensajería shmem de Cray. El rendimiento obtenido resolviendo sistemas de ecuaciones algebraicas lineales alcanza los 1,12 Tflop/s.

MPP: el sistema consta de nodos informáticos homogéneos, que incluyen:

Uno y, a veces, varios procesadores centrales (generalmente la arquitectura RISC - Computación de conjunto de instrucciones reducidas, que se caracteriza por una palabra de comando larga para especificar operaciones, un conjunto reducido de instrucciones y la ejecución de la mayoría de las operaciones en un ciclo de procesador),

Memoria local (no es posible el acceso directo a la memoria de otros nodos),

Procesador de comunicación (o adaptador de red),

Discos duros (opcionales) y/u otros dispositivos de entrada/salida.

Se agregan al sistema nodos de E/S especiales y nodos de control. Los nodos informáticos están conectados por algún medio de comunicación (red de alta velocidad, conmutadores, etc.).

El mantenimiento de sistemas multiprocesador no es una tarea fácil: con cientos o miles de nodos informáticos, el fallo diario de varios de ellos es inevitable; Se requiere un sistema de gestión de recursos 5k (complejo de software y hardware) de una computadora masivamente paralela para manejar tales situaciones, evitando un reinicio general catastrófico con pérdida del contexto de las tareas que se están ejecutando actualmente.

2.4.1. Supercomputadoras masivamente paralelas de la serie CRY T3

Fundada en 1972, Cry Research Inc. (ahora Cry Inc.), famosa por el desarrollo de la supercomputadora vectorial Cry 1, lanzó en 1993-1995 los modelos Cry T3D/T3E, que implementan completamente el principio de sistemas masivamente paralelos (sistemas de arquitectura MPP). En la configuración máxima, estas computadoras combinan procesadores 32 - 2048 DEC Alpha 21064/150 MHz, 21164/600 MHz, 21164A/675 MHz (según el modelo), se realiza todo el preprocesamiento y preparación del programa (por ejemplo, compilación). en la máquina de control (computadora principal).

Los desarrolladores de la serie Cry T3D/T3E tomaron el camino de la creación de memoria virtual compartida. Cada procesador puede acceder directamente sólo a su memoria local, pero todos los nodos comparten un único espacio de direcciones. Cuando se intenta acceder a una dirección que pertenece a la memoria local de otro procesador, se genera una interrupción de hardware especializada y el sistema operativo realiza una transferencia de página de un nodo a otro, y debido a la velocidad extremadamente alta del sistema de comunicación ( la velocidad máxima de transferencia de datos entre dos nodos alcanza los 480 MB/s), este enfoque está generalmente justificado. Sin embargo, se ha observado un efecto "ping-pong" que reduce drásticamente el rendimiento: si las variables modificadas por varios procesadores caen en una página, esta página migra continuamente entre nodos. Los nodos informáticos ejecutan programas de usuario en modo exclusivo (modo de tarea única).

El diseño específico de las computadoras de la serie Cry T3 se caracteriza por una tripleta de números, por ejemplo, 24/16/576 (nodos de control/nodos del sistema operativo/nodos de computación); Con la topología de “toro tridimensional” utilizada, cada nodo (independientemente de su ubicación) tiene seis vecinos inmediatos. Al elegir una ruta entre dos nodos A y B (cuyas coordenadas 3D se muestran en la Figura 11), los enrutadores de red, iniciando el proceso desde el vértice inicial A, primero realizan un desplazamiento a lo largo de la coordenada X hasta las coordenadas de la siguiente comunicación. el nodo y el nodo B se vuelven iguales; luego se realizan acciones similares a lo largo de la coordenada Y y luego a lo largo de Z (el enrutamiento físicamente similar ocurre simultáneamente a lo largo de las tres coordenadas). Los desplazamientos también pueden ser negativos; si fallan una o más conexiones, se pueden evitar.

Otra característica interesante de la arquitectura Cry T3 es la compatibilidad con la sincronización de barrera: la organización de hardware de todos los procesos que esperan un cierto punto en el programa, al alcanzar el cual es posible seguir trabajando. Las computadoras de la serie T3E demostraron un rendimiento de 1,8 a 2,5 Tflops (en microprocesadores 2048 Alpha/600 MHz).

Un desarrollo adicional de la línea Cry T3 de computadoras masivamente paralelas es la supercomputadora Cry XT3. Cada nodo de computación Cry XT3 incluye un procesador AMD Opteron, memoria local (1 - 8 GB) y un canal Hyper Transport que proporciona comunicación a través de la unidad de comunicación Cry SeaStar, que tiene un rendimiento máximo (para AMD Opteron 2,4 GHz) de 2,6 teraflops (548 procesadores), RAM 4,3 TB, topología 6x12x8) hasta 147 teraflops. Cray XT3 se ejecuta bajo el sistema operativo UNICOS/lc, que le permite combinar hasta 30.000 nodos informáticos, utiliza compiladores Fortran 77/90/95 y C/C++, bibliotecas de comunicación MPI (interfaz de paso de mensajes compatible con el estándar MPI 2.0) y ShMem (biblioteca desarrollada por Cray Research Inc. para trabajar con memoria compartida), bibliotecas estándar para cálculos numéricos.

A pesar de lograr resultados tan altos en el campo de los sistemas MPP, Cry Inc. produce computadoras de canalización vectorial, y estos modelos se pueden combinar en un sistema MPP. El rendimiento de cada procesador de la computadora Cry SV1 alcanza los 4 Gflops (rendimiento máximo total del sistema de 32 Gflops), el número total de procesadores puede llegar a 1000.

Figura 11. Red de comunicación "toro tridimensional" de la computadora Cray T3E

2.4.2. Sistemas de cluster de clase BEOWULF

El coste prohibitivo de los ordenadores industriales masivamente paralelos perseguía a los especialistas que querían utilizar sistemas informáticos de potencia comparable en sus investigaciones, pero no podían comprar superordenadores industriales. Las búsquedas en esta dirección llevaron al desarrollo de clusters informáticos (que no deben confundirse con clusters de bases de datos y servidores WEB); La base tecnológica para el desarrollo de la agrupación fueron los microprocesadores y las tecnologías de comunicación (redes) ampliamente disponibles y relativamente económicos que aparecieron en el mercado público en los años noventa.

Un clúster informático es una colección de nodos informáticos (de decenas a decenas de miles), unidos por una red de alta velocidad con el fin de resolver un único problema informático. Cada nodo de un clúster informático es en realidad una computadora electrónica programable (a menudo un servidor SMP de dos o cuatro procesadores/núcleos) que ejecuta su propio sistema operativo (en la gran mayoría Linux (*)); La red unificadora se selecciona en función de la clase requerida de tareas a resolver y las capacidades financieras casi siempre se implementa la posibilidad de acceso remoto al clúster a través de Internet.

Los nodos informáticos y la computadora de control generalmente combinan (al menos) dos redes (independientes): una red de control (sirve para administrar los nodos informáticos) y una red de comunicación (a menudo más productiva) (intercambio directo de datos entre procesos que se ejecutan en los nodos). ); además, el nodo de control tiene una salida a Internet para acceder a los recursos de un grupo de usuarios remotos, el servidor de archivos realiza las funciones de almacenar programas de usuario (Figura 12). La administración del clúster se realiza desde la computadora de control (o mediante acceso remoto); los usuarios tienen derecho a acceder (de acuerdo con los derechos asignados por el administrador) a los recursos del clúster exclusivamente a través de la computadora de control.

Los clústeres de Windows de gran potencia siguen siendo exóticos por razones bien conocidas (a pesar del Windows Compute Cluster Server, una solución de clase WCCS promovida activamente por MS).

Uno de los primeros proyectos del cluster fue el proyecto BEOWULF. El proyecto BEOWULF se fundó en el centro de investigación CESDIS (Centro de Excelencia en Ciencias de la Información y Datos Espaciales), creado sobre la base de la organización de la NASA GSFC (Centro de Vuelo Espacial Goddard) en 1994 y comenzó con el montaje en GSFC de un sistema de 16 nodos. cluster (en procesadores 486DX4/100 MHz, 16 Mb de memoria, 3 adaptadores de red en cada nodo y 3 cables Ethernet paralelos de 10 Mbit); El sistema informático estaba destinado a realizar trabajos en el ESS (Proyecto de Ciencias de la Tierra y el Espacio).

Posteriormente, los departamentos de la NASA ensamblaron otros modelos de clusters tipo BEOWULF: por ejemplo, el HIVE (Highly-parallel Integrated Virtual Environment) de 64 nodos de doble procesador (Pentium Pro/200 MHz, 4 Gb de memoria y 5 switch Fast Ethernet en cada uno). . Fue en el marco del proyecto Beowulf que se desarrollaron controladores para implementar el modo Channel Bonding.

Figura 12. Diagrama ampliado de un clúster informático

"Beowulf" es un ejemplo típico de un sistema MIMD (Instrucción múltiple - Datos múltiples) multiprocesador, con varias ramas de programa ejecutándose simultáneamente, intercambiando datos en ciertos intervalos. Muchos desarrollos posteriores en todo el mundo son en realidad clanes Beowulf.

En 1998, en el Laboratorio Nacional de Los Álamos, el astrofísico Michael Warren y miembros del grupo de astrofísica teórica construyeron el sistema informático Avalon, que era un clúster Linux con procesadores DEC Alpha/533 MHz. Inicialmente Avalon constaba de 68 procesadores, luego se amplió a 140, cada nodo tenía 256 MB de RAM, un disco duro EIDE de 3,2 Gb y un adaptador de red Kingston.

Los nodos se conectan mediante cuatro conmutadores Fast Ethernet y un conmutador central Gigabit Ethernet de doce puertos de 3Com.

Un ejemplo típico de un sistema informático de clúster masivamente paralelo es el MVS-1000M (red de comunicación: Myrinet 2000, velocidad de intercambio de información de 120 a 170 MB/s, auxiliar: Fast y Gigabit Ethernet) y el MVS-15000BC.

El requisito de máxima eficiencia en el uso de los recursos de potencia informática (tanto el procesador como la RAM y la memoria de disco) de los procesadores individuales en un clúster conduce inevitablemente a una reducción de la "inteligencia" del sistema operativo de los nodos informáticos al nivel de los monitores; por otro lado, se ofrecen sistemas operativos de clúster distribuidos, por ejemplo, Amoeba, Chorus, Mach, etc.

Los servidores blade (*) se producen específicamente para completar el hardware de los grupos informáticos: placas verticales estrechas que incluyen un procesador, RAM (generalmente 256 - 512 MB con una caché L2 de 128 - 256 KB), memoria de disco y chips de soporte de red; Estas placas se instalan en “cestas” de formato estándar 3U con un ancho de 19² y una altura de 5,25², hasta 24 piezas cada una (240 nodos informáticos por rack con una altura de 180 cm). Para reducir el consumo total de energía, se pueden utilizar procesadores de la serie Transmeta Crusoe TM 5x00 con tecnología VLIW, que consumen sólo unos pocos vatios (frente a los 75 W del P4 o los 130 W de los cristales de arquitectura IA-64); Al mismo tiempo, el consumo total de energía con 240 nodos informáticos no supera 1 kW.

Conclusión

La programación paralela es un área completa de temas relacionados, incluido el soporte de hardware, el análisis de la estructura de los algoritmos para identificar el paralelismo y los lenguajes algorítmicos para programar tareas paralelas.

Actualmente, las tecnologías informáticas paralelas se están desarrollando rápidamente en relación con las necesidades de la ciencia y la tecnología mundiales.

Muy a menudo uno tiene que afrontar tareas que, aunque tienen un valor considerable para la sociedad, no pueden resolverse utilizando ordenadores de oficina o domésticos relativamente lentos. La única esperanza en este caso reside en los ordenadores de alta velocidad, comúnmente llamados superordenadores. Sólo las máquinas de esta clase pueden procesar grandes cantidades de información. Estos podrían ser, por ejemplo, datos estadísticos o los resultados de observaciones meteorológicas, información financiera. A veces la velocidad de procesamiento es crítica. Esto incluye la previsión meteorológica y la modelización del cambio climático. Cuanto antes se pronostique un desastre natural, mayor será la oportunidad de prepararse para él. Una tarea importante es la modelización de medicamentos, el desciframiento del genoma humano, la exploración de yacimientos de petróleo y gas y otras tareas de gran escala, cuya solución es posible con la ayuda de supercomputadoras y sistemas de cluster.

El problema actual es una clara falta de hardware para la computación paralela en instituciones educativas y científicas, que no permite el desarrollo integral de tecnologías relevantes; El estudio puramente teórico de un tema, que a menudo se practica, tiene consecuencias más negativas que positivas. Recién ahora están surgiendo tecnologías que permiten introducir la práctica de la computación paralela en la mayoría de los laboratorios educativos e industriales. La creación de programas paralelos eficaces requiere un análisis mucho más serio y profundo de la estructura de los algoritmos que la programación secuencial tradicional, y algunos enfoques no pueden implementarse sin un cambio serio en la forma de pensar de los programadores. Junto con el análisis teórico, se requiere una práctica constante en la creación de programas paralelos para obtener resultados prácticamente significativos.

Referencias

1. Voevodin V.V., Voevodin Vl.V. Computación paralela. -SPb.: BHV-Petersburgo, 2004. -608 p.

2. Harvey M. Deitel. Introducción a los sistemas operativos (traducido del inglés por L.A. Teplitsky, A.B. Khodulev, Vs.S. Shtarkman, editado por Vs.S. Shtarkman). -M.: Mir, 1987 (versión electrónica, 2004)

3. Gergel V.P., Strongin R.G. Fundamentos de la computación paralela para sistemas informáticos multiprocesador (libro de texto, ed. 2, actualizado). -N.Novgorod: ed. La Universidad Estatal de Nizhny Novgorod lleva el nombre N.I. Lobachevsky, -2003 (versión electrónica http://pilger.mgapi.edu/metods/1441/basic_pr.zip).

4. Korneev V.V. Sistemas informáticos. -M.: Helios ARV, -2004, -512 p.

5. Latsis A.O. Cómo construir y utilizar una supercomputadora. -M.: Mejor vendido, 2003.

6. Shpakovsky G.I. Organización de ordenadores paralelos y procesadores superescalares. // libro de texto prestación. -Minsk: Universidad Estatal de Bielorrusia, 1996. -296 p. (versión electrónica http://pilger.mgapi.edu/metods/1441/spakovsk.zip)

7. Shpakovsky G.I., Serikova N.V. Programación para sistemas multiprocesador en el estándar MPI. -Minsk: BSU, 2002. -325 p. (versión electrónica http://www.cluster.bsu.by/download/book_PDF.pdf, http://pilger.mgapi.edu/metods/1441/pos_mpi.pdf)

Por disciplina "Paralelocálculos en Óptica y Optoinformática” en el 10mo semestre Formas...

Conferencias sobre la disciplina “Fundamentos teóricos del control automatizado”

Tarea

... ____________________________ “____”__________________200_ conferenciasPordisciplina"Fundamentos teóricos... cálculos: 1) sistema completamente centralizado - algoritmo secuencial clásico 2) sistema completamente descentralizado - paralelo ...

NOTAS DE CONFERENCIA sobre la disciplina “TECNOLOGÍAS DE RED” (versión agregada) para estudiantes de la especialidad 7

Abstracto

Departamento de "Sistemas de información en la gestión" CONSPECT CONFERENCIASPordisciplina"TECNOLOGÍAS DE RED" (versión extendida) para... una ventaja muy importante es la capacidad de realizar paralelocálculos. Cuando en un sistema informático, la tarea...

Apuntes de conferencias sobre la disciplina "sistemas neuroinformáticos" Shebakpol

Abstracto

Abstracto conferenciasPordisciplina“Sistemas neuroinformáticos” Shebakpolsky M.F. Contenidos... sobre entrenamiento, simplicidad del modelo. paralelocálculos. No hay razón para creer... que las computadoras tienen una característica inherente. paralelo naturaleza cálculos se pierde; cada operación...

bajo el término procesamiento paralelo entenderemos la ejecución simultánea de tareas, pasos de tareas (elementos), programas, subrutinas, bucles, operadores y comandos. El procesamiento de información en paralelo se puede utilizar para dos propósitos principales:

1. Incrementar la productividad de las computadoras y los aviones no mejorando la base de elementos, sino mediante la organización efectiva de los procesos informáticos.

2. Asegurar una alta confiabilidad de las aeronaves mediante la duplicación de equipos informáticos.

Arroz. 5.1. Niveles de paralelismo

Aumentar el rendimiento de las computadoras y los ordenadores es el principal objetivo del uso del procesamiento paralelo, por esta razón, los ordenadores como los servidores multiprocesador, mainframes y supercomputadores tienen una arquitectura paralela;

El procesamiento de información paralelo se puede realizar en varios niveles (Fig. 5.1).

Evidentemente, cuanto más bajo es el nivel, más fina es la fragmentación de los procesos de software, más fina, como suele decirse, “ grano de paralelismo" En general, es posible implementar el paralelismo tanto en un solo nivel como en varios simultáneamente. El procesamiento independiente de un solo procesador implementa el paralelismo en el nivel 1. El procesamiento vectorial consiste en la ejecución paralela de bucles en el nivel 2 y se puede realizar en uno o varios procesadores. Los niveles 3 y 4 corresponden a computadoras multiprocesador. El paralelismo de nivel 5 es típico de los sistemas informáticos de varias máquinas.

Hay dos formas principales de organizar el procesamiento paralelo:

· combinación temporal de etapas de resolución de diferentes problemas;

· solución simultánea de varias tareas o partes de una tarea;

primera manera- combinar en el tiempo las etapas de resolución de diferentes problemas es procesamiento multiprograma información. El procesamiento multiprograma se ha utilizado ampliamente durante mucho tiempo para mejorar el rendimiento de las computadoras y las computadoras. Una discusión detallada del procesamiento multiprograma se relaciona con el tema "Sistemas operativos" y está más allá del alcance de este libro de texto.

Segunda manera- la solución simultánea de varias tareas o partes de una tarea - sólo es posible si hay varios dispositivos de procesamiento. En este caso se utilizan ciertas características de las tareas o flujos de tareas, lo que permite la paralelización.

Se pueden distinguir los siguientes tipos de paralelismo, que permiten la implementación de características algorítmicas de tareas individuales y sus subprocesos.

1. Paralelismo natural de tareas independientes.

2. Paralelismo de objetos o datos.

3. Paralelismo de ramas de tareas o programas.

Veamos estos tipos de paralelismo.

1. Paralelismo natural de tareas independientes. radica en el hecho de que en la entrada del sistema informático se recibe un flujo continuo de tareas no relacionadas, es decir la solución a cualquier problema no depende de los resultados de resolver otros problemas. En este caso, el uso de varios dispositivos de procesamiento con cualquier método de integración (integración en un sistema) aumenta el rendimiento del sistema.

Un ejemplo típico de paralelismo natural es la llegada de solicitudes de usuarios a un sitio web de información. Cada solicitud genera un procedimiento independiente para su ejecución, que no depende de otros procedimientos similares.

2. Paralelismo de objetos o datos Ocurre cuando el mismo (o casi el mismo) programa debe procesar un determinado conjunto de datos que ingresan al sistema simultáneamente.

Podría tratarse, por ejemplo, de tareas de procesamiento de señales de una estación de radar: todas las señales se procesan con el mismo programa. Otro ejemplo es el procesamiento de información de sensores que miden simultáneamente el mismo parámetro y están instalados en varios objetos similares.

Los programas de este tipo pueden ser de diferente tamaño y complejidad, desde programas muy simples que contienen varias operaciones hasta programas grandes que contienen cientos y miles de operaciones. En este caso, la ejecución paralela de operaciones se logra aumentando el número de dispositivos de procesamiento, cada uno de los cuales es capaz de ejecutar de forma autónoma una secuencia de comandos en un conjunto de datos separado. A menudo, la característica principal de tales programas (en particular, programas para procesar vectores y matrices) es que el mismo comando debe ejecutarse en una gran colección de datos elementales interconectados de alguna manera, y la operación correspondiente se puede realizar en todos los datos simultáneamente. En este caso, el tiempo necesario para resolver el problema se reduce en proporción al número de dispositivos de procesamiento.

3. Paralelismo de ramas de tareas o programas.- uno de los tipos más comunes de paralelismo en el procesamiento de información. Consiste en el hecho de que al resolver un problema, sus partes individuales se pueden separar: ramas que, en presencia de varios dispositivos de procesamiento, se pueden ejecutar en paralelo. En este caso, sólo sucursales independientes tareas, es decir aquellas partes del mismo para las cuales se cumplan las siguientes condiciones:

· ninguno de los valores de salida de estas ramas del problema es un valor de entrada para otra rama similar (falta de conexiones funcionales);

· las condiciones para la ejecución de una rama no dependen de los resultados o características obtenidas durante la ejecución de otras ramas (independencia de control).

Una buena idea del paralelismo de ramas la da la forma paralela de niveles (LPF) del programa, cuyo ejemplo se muestra en la Fig. 5.2.

El programa se presenta como un conjunto de sucursales ubicadas en varios niveles: niveles. Los círculos con números dentro indican ramas. La longitud de una rama está representada por un número al lado de un círculo e indica cuántas unidades de tiempo se ejecuta esta rama. Las flechas muestran los datos de entrada y los resultados del procesamiento. Los datos de entrada se indican con el símbolo X, los datos de salida con el símbolo Y. Los símbolos X tienen índices digitales inferiores que indican los números de las cantidades de entrada; Los símbolos Y tienen índices digitales tanto en la parte inferior como en la superior; el número en la parte superior corresponde al número de la rama durante la cual se obtuvo el resultado dado, y el número en la parte inferior significa el número de serie del resultado obtenido durante la implementación de esta rama del programa. Las ramas de tareas independientes que no están relacionadas entre sí se colocan en un nivel, es decir Los resultados de resolver cualquier rama de un nivel determinado no son datos de entrada para otra rama del mismo nivel.

Arroz. 5.2. Un ejemplo de un formulario de programa paralelo por niveles

Mostrado en la Fig. 5.2 el programa contiene 9 sucursales ubicadas en 3 niveles. Usando como ejemplo este programa generalmente bastante simple, se pueden identificar las ventajas de un sistema informático que incluye varios dispositivos de procesamiento y los problemas que surgen.

Supongamos que la longitud i la décima rama está representada por el número de unidades de tiempo yo que son necesarios para su ejecución. Entonces es fácil calcular que llevará tiempo ejecutar todo el programa en 1 procesador. T 1:

T 1=S(10+20+15+30+55+10+15+25+15)=195

Si imaginamos que el programa es ejecutado por dos dispositivos de procesamiento (procesadores) que funcionan independientemente uno del otro, entonces se reducirá el tiempo necesario para resolver el problema. Sin embargo, este tiempo, como es fácil ver, variará dependiendo de la secuencia de ejecución de las ramas independientes.

Consideremos, por ejemplo, esta versión del programa que se muestra en la Fig. 5.2. Deje que el procesador 1 ejecute las ramas 1-3-4-6-7-9 y el procesador 2 ejecute las ramas 2-5-8. En la figura. La Figura 5.3 muestra diagramas de tiempo de ejecución del procesador de ramas del programa.

Arroz. 5.3. Descomposición de ramas de programa en 2 procesadores.

Es fácil calcular que el procesador 1 gasta 105 y el procesador 2, 100 unidades de tiempo. En este caso, hay dos períodos de tiempo en los que uno de los procesadores se ve obligado a estar inactivo: P1 con una duración de 10 unidades y P2 con una duración de 5 unidades de tiempo. El intervalo P1, durante el cual solo funciona el procesador 2, se formó debido al hecho de que la rama 7 depende de la rama 5 (cuando se completa la rama 6, los datos Y 5 1 aún no están listos). El intervalo P1, durante el cual solo funciona el procesador 1, se formó debido al final del conteo del procesador 2.

Así, en un sistema de dos procesadores, nuestro programa se ejecutará íntegramente en nada menos que 105 unidades de tiempo. El valor que caracteriza la reducción del tiempo necesario para resolver un problema en varios procesadores en comparación con el uso de un solo procesador se denomina aceleración del conteo S y calcular como

El coeficiente de paralelización varía de 0 a 1 (de 0 a 100%) y refleja la eficiencia en el uso de los recursos informáticos. En nuestro ejemplo es fácil calcular que la aceleración S= 195/105 = 1,86, y el factor de paralelización kp= 0,93. Como podemos ver, debido al tiempo de inactividad de uno de los procesadores, la aceleración de cálculo es significativamente menor que 2, es decir número de procesadores utilizados. Tenga en cuenta que en nuestro ejemplo, no se tuvieron en cuenta los retrasos asociados con el cambio de contexto del programa (cambio de ramas) y la transferencia de datos de una rama a otra. Sin embargo, debido a las características algorítmicas del programa, parte de los cálculos en los intervalos P1 y P2 los realiza un solo procesador, es decir realmente secuencial.

Consideremos el caso generalizado de un programa en el que, algorítmicamente, la proporción de cálculos secuenciales (la relación entre el tiempo de cálculos secuenciales y el tiempo total de cálculo del programa) es un valor determinado. F. En este caso, el tiempo de ejecución del programa en el sistema es de pag procesadores no pueden ser inferiores a

Esta relación se llama ley de amdahl. Usando el ejemplo del programa en la Fig. 5.2 podemos ver que la proporción de cálculos secuenciales es F= 15/195. Sustituyendo este valor en la fórmula de la ley de Amdahl, obtenemos para un sistema de dos procesadores una aceleración máxima de 1,86 veces, que corresponde al valor calculado previamente.

Para ilustrar el funcionamiento de la ley de Amdahl, damos el siguiente ejemplo. Dejemos que la proporción de cálculos secuenciales en algún programa sea del 10%. Entonces, la aceleración de cálculo máxima en 100 procesadores no excederá 9,2. El coeficiente de paralelización será sólo del 9,2%. En 10 procesadores, la aceleración será 5,3 y el coeficiente de paralelización será del 53%. Es fácil ver que incluso una fracción tan pequeña de cálculos secuenciales, ya a nivel teórico, sin tener en cuenta los retrasos inevitables en una computadora real, limita seriamente la capacidad de escalar el programa.

Determinemos cuál debería ser la participación máxima. F Cálculos secuenciales en el programa para que sea posible obtener una aceleración de cálculo predeterminada. S con coeficiente de paralelización máximo kp. Para ello, expresamos la proporción de cálculos secuenciales de la ley de Amdahl:

La relación (5.6) determina una muy importante consecuencia de la ley de Amdahl. Para acelerar el programa enq veces, es necesario acelerar no menos deq veces no menos que () ª parte del programa. Por ejemplo, para obtener una aceleración de 100x, es necesario paralelizar el 99,99% de todo el programa.

Además de la paralelización algorítmica, para resolver un problema con ramas paralelas utilizando varios dispositivos de procesamiento, es necesaria una organización adecuada del proceso, que determine las formas de resolver el problema y genere la información necesaria sobre la preparación de cada rama. Sin embargo, todo esto es relativamente fácil de implementar cuando se conoce con bastante precisión la duración de la ejecución de cada rama. En la práctica, esto ocurre muy raramente: en el mejor de los casos, existe una u otra estimación temporal. Por tanto, organizar un horario de trabajo óptimo o cercano al óptimo es una tarea bastante difícil.

También cabe señalar que existen ciertas dificultades asociadas con el aislamiento de sucursales independientes al desarrollar programas. Al mismo tiempo, al resolver muchos problemas complejos, sólo la programación con la selección de ramas independientes puede reducir significativamente el tiempo de solución. En particular, los problemas de álgebra matricial, programación lineal, procesamiento de señales espectrales, transformadas de Fourier directa e inversa, etc. se prestan bien al procesamiento paralelo de este tipo.

“El paralelismo como método de procesamiento de datos en paralelo”

Kotovsk2010

Introducción

El rápido desarrollo de la ciencia y la penetración del pensamiento humano en áreas siempre nuevas, junto con la solución de problemas previamente planteados, genera constantemente una corriente de preguntas y plantea nuevas tareas, generalmente más complejas. En el momento de las primeras computadoras, parecía que aumentar su velocidad 100 veces resolvería la mayoría de los problemas, pero el rendimiento de gigaflop de las supercomputadoras modernas hoy en día es claramente insuficiente para muchos científicos. Eléctrica e hidrodinámica, exploración sísmica y predicción meteorológica, modelado de compuestos químicos, investigación en realidad virtual: esta no es una lista completa de áreas de la ciencia cuyos investigadores aprovechan todas las oportunidades para acelerar la ejecución de sus programas.

La dirección más prometedora y dinámica para aumentar la velocidad de resolución de problemas aplicados es la introducción generalizada de ideas de paralelismo en el funcionamiento de los sistemas informáticos. Hasta la fecha, se han diseñado y probado cientos de computadoras diferentes, utilizando uno u otro tipo de procesamiento de datos paralelo en su arquitectura. En la literatura científica y la documentación técnica se pueden encontrar más de una docena de nombres diferentes que caracterizan solo los principios generales del funcionamiento de las máquinas paralelas: tuberías vectoriales, paralelas masivas, computadoras con una palabra de comando amplia, matrices sistólicas, hipercubos, procesadores especiales. y multiprocesadores, computadoras jerárquicas y de clúster, flujo de datos, computadoras matriciales y muchos otros. Si, para completar la descripción, agregamos datos sobre parámetros tan importantes como, por ejemplo, la organización de la memoria, la topología de la comunicación entre procesadores, la sincronización del funcionamiento de dispositivos individuales o el método para realizar operaciones aritméticas, entonces el cantidad de arquitecturas diferentes se volverá completamente incomprensible.

Los intentos de sistematizar todo el conjunto de arquitecturas comenzaron después de que M. Flynn publicara la primera versión de la clasificación de sistemas informáticos a finales de los años 60 y continúan de forma continua hasta el día de hoy. La clasificación es muy importante para una mejor comprensión del área temática en estudio, pero encontrar una clasificación exitosa puede tener una serie de consecuencias importantes.

La cuestión principal de la clasificación, qué debe constituir su base, se puede resolver de diferentes maneras, dependiendo de para quién se crea esta clasificación y qué problema pretende resolver. Por lo tanto, la división de computadoras, de uso frecuente, en computadoras personales, estaciones de trabajo, minicomputadoras, computadoras centrales, minisupercomputadoras y supercomputadoras permite, quizás, estimar aproximadamente el costo de una computadora. Sin embargo, esto no acerca al usuario a comprender lo que se requiere de él para escribir un programa que opere al límite del rendimiento de una computadora paralela, es decir, para qué decidió usarlo.

La clasificación debería ayudar a comprender qué es cada arquitectura, cómo están interconectadas, qué se debe tener en cuenta para escribir programas verdaderamente efectivos o a qué clase de arquitecturas se debe apuntar para resolver la clase de problemas requerida. Al mismo tiempo, una clasificación exitosa podría sugerir posibles formas de mejorar las computadoras y, en este sentido, debería ser bastante significativa. Es difícil esperar encontrar “puntos ciegos” no triviales, por ejemplo, en la clasificación por costo, pero pensar en una posible taxonomía desde el punto de vista de la simplicidad y la capacidad de fabricación de la programación puede ser extremadamente útil para determinar las direcciones para el Búsqueda de nuevas arquitecturas.

1. Sistemas informáticos paralelos

Los sistemas informáticos paralelos son sistemas informáticos y de software físicos que implementan el procesamiento de datos paralelo de una forma u otra en muchos nodos informáticos.

La idea de la computación paralela se basa en la idea de que la mayoría de los problemas se pueden dividir en un conjunto de problemas más pequeños que se pueden resolver simultáneamente. Normalmente, la computación paralela requiere coordinación. La computación paralela se presenta en varias formas: paralelismo a nivel de bits, paralelismo a nivel de instrucciones, paralelismo de datos y paralelismo de tareas. La computación paralela se ha utilizado durante muchos años principalmente en la computación de alto rendimiento, pero recientemente ha habido un mayor interés en ella debido a la existencia de restricciones físicas en el crecimiento de las velocidades de reloj del procesador. La computación paralela se ha convertido en un paradigma dominante en la arquitectura informática, principalmente en forma de procesadores multinúcleo.

Escribir programas para sistemas paralelos es más difícil que para sistemas secuenciales, ya que la competencia por los recursos introduce una nueva clase de errores potenciales de software (bugs), entre los cuales las condiciones de carrera son las más comunes. La comunicación y sincronización entre procesos plantean una barrera importante para lograr un alto rendimiento en sistemas paralelos. En los últimos años también se ha comenzado a considerar la cuestión del consumo de energía de las computadoras paralelas. La naturaleza del aumento en la velocidad del programa como resultado de la paralelización se explica mediante la ley de Amdahl.

Si el cálculo no implica acciones cíclicas (repetitivas), entonces N módulos informáticos nunca realizarán un trabajo N veces más rápido que un solo módulo informático.

Por ejemplo, para ordenar rápidamente una matriz en una máquina con dos procesadores, puede dividir la matriz por la mitad y ordenar cada mitad en un procesador independiente. Ordenar cada mitad puede llevar un tiempo diferente, por lo que la sincronización es necesaria.

2. Tipos de paralelismo

2.1 Paralelismo a nivel de bits

Esta forma de paralelismo se basa en aumentar el tamaño de la palabra de máquina. Aumentar el tamaño de la palabra de la máquina reduce la cantidad de operaciones requeridas por el procesador para realizar operaciones en variables cuyo tamaño excede el tamaño de la palabra de la máquina. Por ejemplo: en un procesador de 8 bits es necesario sumar dos números enteros de 16 bits. Para hacer esto, primero debe sumar los 8 bits inferiores de los números, luego sumar los 8 bits superiores y agregar el valor de la bandera de acarreo al resultado de su suma. Total de 3 instrucciones. Con un procesador de 16 bits, puedes realizar esta operación con una sola instrucción.

Históricamente, los microprocesadores de 4 bits fueron reemplazados por microprocesadores de 8 bits, seguidos por microprocesadores de 16 y 32 bits. Los procesadores de 32 bits han sido durante mucho tiempo el estándar en la informática cotidiana. Con la llegada de la tecnología x86–64, se empezaron a utilizar procesadores de 64 bits para estos fines.

2.2 Paralelismo a nivel de instrucción

Un programa de computadora es esencialmente un flujo de instrucciones ejecutadas por un procesador. Pero puedes cambiar el orden de estas instrucciones, distribuirlas en grupos que se ejecutarán en paralelo, sin cambiar el resultado de todo el programa. Esta técnica se conoce como paralelismo a nivel de instrucción. Los avances en el desarrollo del paralelismo a nivel de instrucción en la arquitectura de computadoras se produjeron desde mediados de los años 80 hasta mediados de los 90.

Los procesadores modernos tienen un proceso de instrucción de varias etapas. Cada etapa de la canalización corresponde a una acción específica realizada por el procesador en esta instrucción en esta etapa. Un procesador con N etapas de canalización puede tener simultáneamente hasta N instrucciones diferentes en diferentes niveles de completitud. Un ejemplo clásico de procesador canalizado es un procesador RISC con 5 etapas: recuperación de instrucciones de la memoria (IF), decodificación de instrucciones (ID), ejecución de instrucciones (EX), acceso a la memoria (MEM), escritura del resultado en registros (WB). El procesador Pentium 4 tiene una tubería de 35 etapas.

Algunos procesadores, además de utilizar pipelines, tienen la capacidad de ejecutar múltiples instrucciones simultáneamente, lo que proporciona un paralelismo adicional a nivel de instrucción. Es posible implementar este método utilizando superescalaridad, donde las instrucciones se pueden agrupar para su ejecución en paralelo (si no tienen dependencias de datos). También son posibles implementaciones que utilizan paralelismo explícito a nivel de instrucción: VLIW y EPIC.

2.3 Paralelismo de datos

La idea principal del enfoque basado en el paralelismo de datos es que se realiza una operación en todos los elementos de la matriz de datos a la vez. Se procesan varios fragmentos de dicha matriz en un procesador vectorial o en diferentes procesadores de una máquina paralela. El programa distribuye datos entre procesadores. En este caso, la vectorización o paralelización se realiza con mayor frecuencia en la etapa de compilación: traducir el texto fuente del programa a instrucciones de máquina. El papel del programador en este caso generalmente se reduce a especificar configuraciones de optimización vectorial o paralela para el compilador, directivas de compilación paralela y el uso de lenguajes especializados para la computación paralela.

2.4 Paralelismo de tareas (multithreading)

Un estilo de programación basado en el paralelismo de tareas implica que una tarea informática se divide en varias subtareas relativamente independientes y cada procesador se carga con su propia subtarea.

2.5 Sistemas operativos distribuidos

Un sistema operativo distribuido, al distribuir dinámica y automáticamente el trabajo entre las distintas máquinas del sistema para su procesamiento, hace que un conjunto de máquinas en red actúen como un monoprocesador virtual. El usuario de un sistema operativo distribuido, en general, no tiene información sobre en qué máquina realiza su trabajo.

Un sistema operativo distribuido existe como un único sistema operativo en un sistema informático. Cada computadora en una red que ejecuta un sistema operativo distribuido realiza parte de las funciones de este sistema operativo global. Un sistema operativo distribuido une todas las computadoras de la red en el sentido de que trabajan en estrecha cooperación entre sí para utilizar de manera eficiente todos los recursos de la red informática.

A lo largo de la historia del desarrollo de la tecnología informática, se ha intentado encontrar algún tipo de clasificación general bajo la cual se incluirían todas las direcciones posibles del desarrollo de las arquitecturas informáticas. Ninguna de estas clasificaciones pudo cubrir toda la variedad de soluciones arquitectónicas que se estaban desarrollando y no resistió el paso del tiempo. Sin embargo, han entrado en circulación científica y se utilizan ampliamente una serie de términos que es útil conocer no solo para los desarrolladores, sino también para los usuarios de computadoras.

Cualquier sistema informático (ya sea un superordenador o un ordenador personal) consigue su máximo rendimiento mediante el uso de elementos de alta velocidad y la ejecución paralela de un gran número de operaciones. Es la posibilidad de funcionamiento paralelo de varios dispositivos del sistema (trabajando superpuestos) la base para acelerar las operaciones básicas.

Las computadoras paralelas a menudo se dividen según la clasificación de Flynn en máquinas SIMD (Instrucción única, datos múltiples) y MIMD (Instrucción múltiple, datos múltiples). Como cualquier otra, la clasificación anterior es imperfecta: hay coches que no entran directamente en ella, también hay características importantes que no se tienen en cuenta en esta clasificación. En particular, los procesadores vectoriales a menudo se clasifican como máquinas SIMD, aunque su alto rendimiento depende de otra forma de paralelismo: la organización de la tubería de la máquina. Los sistemas vectoriales multiprocesador, como Cray Y-MP, constan de varios procesadores vectoriales y, por tanto, pueden denominarse MSIMD (Multiple SIMD).

La clasificación de Flynn no distingue entre otras características importantes para los modelos informáticos, como el nivel de grano en cálculos paralelos y métodos de sincronización.

Hay cuatro tipos principales de arquitectura para sistemas de procesamiento paralelo:

1) Procesamiento de tuberías y vectores.

La base del procesamiento de tuberías es la ejecución separada de alguna operación en varias etapas (en varias etapas) con la transferencia de datos de una etapa a la siguiente. La productividad aumenta debido al hecho de que se realizan varias operaciones simultáneamente en diferentes etapas del transportador. La canalización solo es efectiva cuando la tubería está cerca de su capacidad total y la velocidad a la que se suministran nuevos operandos coincide con la capacidad máxima de la tubería. Si se produce latencia, se ejecutarán menos operaciones en paralelo y el rendimiento general disminuirá. Las operaciones vectoriales brindan una oportunidad ideal para cargar completamente el proceso computacional.

Cuando se ejecuta un comando de vector, se aplica la misma operación a todos los elementos del vector (o más a menudo a los elementos correspondientes de un par de vectores). Puede llevar algún tiempo configurar una canalización para realizar una operación particular, pero los operandos pueden luego fluir hacia la canalización a la velocidad máxima permitida por las capacidades de la memoria. En este caso, no hay pausas ni en relación con la selección de un nuevo comando ni en relación con la definición de una rama de cálculos durante una transición condicional. Por tanto, el principio fundamental de la computación en una máquina vectorial es realizar alguna operación elemental o una combinación de varias operaciones elementales, que deben aplicarse repetidamente a algún bloque de datos. Estas operaciones en el programa original corresponden a pequeños bucles compactos.

2) Máquinas tipo SIMD. Las máquinas SIMD constan de una gran cantidad de elementos de procesamiento idénticos que tienen su propia memoria. Todos los elementos de procesamiento en dicha máquina ejecutan el mismo programa. Obviamente, una máquina de este tipo, compuesta por un gran número de procesadores, puede proporcionar un rendimiento muy alto sólo en aquellas tareas en las que todos los procesadores pueden hacer el mismo trabajo. El modelo de cálculo para una máquina SIMD es muy similar al modelo de cálculo para un procesador vectorial: se realiza una sola operación en un gran bloque de datos.

A diferencia del funcionamiento limitado de un procesador vectorial, un procesador matricial (sinónimo de la mayoría de las máquinas SIMD) puede ser significativamente más flexible. Los elementos de procesamiento de dichos procesadores son computadoras programables universales, por lo que un problema resuelto en paralelo puede ser bastante complejo y contener ramas. La manifestación típica de este modelo computacional en un programa fuente es aproximadamente la misma que en el caso de las operaciones vectoriales: bucles en elementos de una matriz en los que los valores producidos en una iteración del bucle no se utilizan en otra iteración del bucle.

Los modelos de computación en computadoras vectoriales y matriciales son tan similares que a menudo se considera que estas computadoras son equivalentes.

3) Máquinas tipo MIMD. El término "multiprocesador" cubre la mayoría de las máquinas MIMD y (al igual que el término "procesador matricial" se aplica a las máquinas SIMD) se utiliza a menudo como sinónimo de máquinas MIMD. En un sistema multiprocesador, cada elemento de procesamiento (PE) ejecuta su programa de forma bastante independiente de otros elementos de procesamiento. Los elementos de procesamiento, por supuesto, deben comunicarse de alguna manera entre sí, lo que requiere una clasificación más detallada de las máquinas de tipo MIMD. Los multiprocesadores con memoria compartida (multiprocesadores estrechamente acoplados) tienen memoria de datos e instrucciones disponible para todos los PE. Los PE se comunican con la memoria compartida mediante un bus común o una red de intercambio. Por el contrario, en los sistemas multiprocesador débilmente acoplados (máquinas con memoria local), toda la memoria se comparte entre los elementos de procesamiento y cada bloque de memoria es accesible sólo para el procesador asociado a él. La red de intercambio conecta los elementos de procesamiento entre sí.

El modelo básico de computación en un multiprocesador MIMD es un conjunto de procesos independientes que acceden periódicamente a datos compartidos. Existe una gran cantidad de variantes de este modelo. En un extremo del espectro está el modelo de computación distribuida, en el que un programa se divide en un número bastante grande de tareas paralelas que constan de muchas subrutinas. En el otro extremo del espectro está el modelo de computación de flujo, en el que cada operación de un programa puede tratarse como un proceso separado. Una operación de este tipo espera sus datos de entrada (operandos), que otros procesos deben pasarle. Una vez recibidos se realiza la operación y el valor resultante se pasa a aquellos procesos que lo necesiten. En los modelos informáticos de transmisión de granularidad alta y media, los procesos contienen una gran cantidad de operaciones y se ejecutan en forma de transmisión.

4) Máquinas multiprocesador con procesadores SIMD.

Muchas supercomputadoras modernas son sistemas multiprocesador que utilizan procesadores vectoriales o procesadores SIMD como procesadores. Estas máquinas pertenecen a la clase MSIMD.

Los lenguajes de programación y los compiladores correspondientes para máquinas MSIMD suelen proporcionar construcciones de lenguaje que permiten al programador describir el paralelismo "grueso". Dentro de cada tarea, el compilador vectoriza automáticamente los bucles adecuados. Las máquinas MSIMD, como se puede imaginar, permiten utilizar lo mejor de estos dos principios de descomposición: operaciones vectoriales (paralelismo "de grano fino") para aquellas partes del programa que son adecuadas para ello, y las capacidades flexibles del MIMD. arquitectura para otras partes del programa.

A lo largo de los años de desarrollo de la tecnología informática, los sistemas multiprocesador han pasado por varias etapas de desarrollo. Históricamente, la tecnología SIMD fue la primera en dominarse. Sin embargo, actualmente existe un interés constante en las arquitecturas MIMD. Este interés está determinado principalmente por dos factores:

1. La arquitectura MIMD permite una gran flexibilidad: con soporte de hardware y software adecuado, MIMD puede funcionar como un sistema de usuario único que proporciona procesamiento de datos de alto rendimiento para una sola tarea de aplicación, como una máquina multiprograma que ejecuta múltiples tareas en paralelo, o como alguna combinación de estas capacidades.
2. La arquitectura MIMD puede aprovechar al máximo la tecnología de microprocesador moderna basándose en estrictas consideraciones de costo/rendimiento. De hecho, prácticamente todos los sistemas multiprocesador modernos se basan en los mismos microprocesadores que se encuentran en las computadoras personales, estaciones de trabajo y pequeños servidores de un solo procesador.

Una de las características distintivas de un sistema informático multiprocesador es la red de comunicación a través de la cual los procesadores se conectan entre sí o con la memoria. El modelo de comunicación es tan importante para un sistema multiprocesador que muchas características de rendimiento y otras estimaciones se expresan como la relación entre el tiempo de procesamiento y el tiempo de comunicación correspondiente a las tareas que se resuelven. Hay dos modelos principales de comunicación entre procesadores: uno se basa en el paso de mensajes y el otro se basa en el uso de memoria compartida. En un sistema multiprocesador de memoria compartida, un procesador escribe en una ubicación de memoria específica y otro procesador lee desde esa ubicación de memoria. Para garantizar la coherencia de los datos y la sincronización de los procesos, el intercambio a menudo se implementa utilizando el principio de acceso mutuamente excluyente a la memoria compartida mediante el método del "buzón".

En las arquitecturas de memoria local, no es posible compartir memoria directamente. En cambio, los procesadores acceden a datos compartidos pasando mensajes a través de una red de intercambio. La efectividad del esquema de comunicación depende de los protocolos de comunicación, las redes de comunicación subyacentes y el ancho de banda de la memoria y los canales de comunicación.

A menudo, y sin razón, en las máquinas de memoria compartida y de vectores los costes de comunicación no se tienen en cuenta, ya que los problemas de comunicación están en gran medida ocultos al programador. Sin embargo, la sobrecarga de comunicación en estas máquinas existe y está determinada por conflictos de buses, memoria y procesadores. A medida que se agregan más procesadores a un sistema, más procesos compiten por los mismos datos y bus, lo que genera una condición de saturación. El modelo de sistema de memoria compartida es muy conveniente para la programación y, a veces, se considera un medio de alto nivel para evaluar el impacto de la comunicación en el funcionamiento del sistema, incluso si el sistema subyacente se implementa realmente utilizando memoria local y principios de transmisión de mensajes.

En las redes de conmutación de circuitos y de conmutación de paquetes, a medida que aumentan las demandas de tráfico, se debe considerar la posibilidad de congestión de la red. Aquí, la comunicación entre procesadores conecta los recursos de la red: canales, procesadores, buffers de mensajes. El volumen de información transmitida se puede reducir mediante una cuidadosa descomposición funcional de la tarea y una cuidadosa distribución de las funciones realizadas.

Así, las máquinas MIMD existentes se dividen en dos clases principales dependiendo del número de procesadores que se combinen, lo que determina tanto el método de organización de la memoria como el método de sus interconexiones.

El primer grupo incluye máquinas con memoria principal común (compartida), que combinan hasta varias docenas (generalmente menos de 32) procesadores. La cantidad relativamente pequeña de procesadores en tales máquinas hace posible tener una memoria compartida centralizada y combinar procesadores y memoria usando un solo bus. Si los procesadores tienen suficiente memoria caché, el bus de alto rendimiento y la memoria compartida pueden acomodar accesos a la memoria desde múltiples procesadores. Debido a que existe una única memoria con el mismo tiempo de acceso, estas máquinas a veces se denominan UMA (Acceso Uniforme a Memoria). Este método de organización con una memoria compartida relativamente pequeña es actualmente el más popular. La estructura de dicho sistema se muestra en la Fig. 10.1.

Arroz. 10.1. Arquitectura típica de un sistema multiprocesador con memoria compartida.

El segundo grupo de máquinas consta de sistemas de memoria distribuida a gran escala. Para admitir una gran cantidad de procesadores, la memoria principal debe distribuirse entre ellos; de lo contrario, es posible que el ancho de banda de la memoria simplemente no sea suficiente para satisfacer las solicitudes provenientes de una gran cantidad de procesadores. Naturalmente, este enfoque también requiere la implementación de comunicación entre procesadores. En la figura. La figura 10.2 muestra la estructura de dicho sistema.

A medida que crece el número de procesadores, simplemente no hay forma de evitar la necesidad de implementar un modelo de memoria distribuida con una red de alta velocidad para comunicarse entre procesadores. Con el rápido crecimiento en el rendimiento del procesador y las crecientes demandas asociadas de mayor ancho de banda de memoria, la escala de los sistemas (es decir, la cantidad de procesadores en un sistema) que requieren memoria distribuida está disminuyendo, así como la cantidad de procesadores que pueden ser admitidos. en un bus compartido y memoria compartida.

La distribución de memoria entre nodos individuales del sistema tiene dos ventajas principales. Primero, es una forma rentable de aumentar el ancho de banda de la memoria porque la mayoría de los accesos se pueden realizar en paralelo a la memoria local en cada nodo. En segundo lugar, reduce la latencia de acceso (tiempo de acceso) a la memoria local. Estas dos ventajas reducen aún más la cantidad de procesadores para los cuales tiene sentido una arquitectura de memoria distribuida.

Normalmente, los dispositivos de E/S, así como la memoria, se distribuyen entre nodos y, en realidad, los nodos pueden consistir en una pequeña cantidad (2-8) de procesadores interconectados de alguna otra manera. Si bien esta agrupación de múltiples procesadores con memoria e interfaz de red puede ser bastante útil en términos de rentabilidad, no es muy importante para comprender cómo funciona una máquina de este tipo, por lo que por ahora nos limitaremos a sistemas con un procesador por nodo. La principal diferencia arquitectónica a tener en cuenta en las máquinas de memoria distribuida es cómo se maneja la comunicación y cuál es el modelo de memoria lógica.

Arroz. 10.2. Arquitectura típica de máquina de memoria distribuida.