• Author / Uploaded
• Joel Cesar Fernandez Segura

• Categories
• Computación distribuída
• Unidad Central de procesamiento
• Computación paralela
• Computación concurrente
• Redes sociales y digitales

Citation preview

COMPUTACION PARALELA Y DISTRIBUIDA, ESTADO DEL ATRE, VOL. 1, NO. 1, MAYO 2016

1

Computacion Paralela y Distribuida Joel Fernandez, Informatica, UNT, Jordy Reyes, Informatica, UNT, Resumen—La computacion Paralela y Distribuida es un area de la ACM, esta relacionada al procesamiento paralelo, las arquitecturas paralelas y los sistemas distribuidos,estudiaremos las distintas sub areas que hay, hablaremos sobre los fundamentos del paralelismo, la descomposicion paralela, la comunicacion y coordinacion, los algoritmos paralelos, la arquitectura paralela, el rendimiento, la computacion distribuida, el cloud computing y los modelos formales y ˜ de esa area. semanticos.Daremos tambien una perspectiva del avance de los ultimos 20 anos Index Terms—Paralelismo, Rendimiento,concurrencia, atomicidad, exclusion mutua, multicast, computacion distribuida,cloud computing.

F

1.

I NTRODUCCION

E

˜ N los anos 50, empezo´ a surgir el procesamiento paralelo . El objetivo en esa e´ poca era construir una m´aquina con capacidad computacional 100 veces mayor de la de cualquier otra m´aquina disponible. En esos ˜ anos empezaron producir los dos primeros productos: los supercomputadores conocidos como STRETCH y LARC. En paralelo a estas iniciativas, muchas otras producen computadores con las arquitecturas m´as variadas y con diferentes tipos de software. Las princi´ de m´aquipales razones para la construccion nas paralelas son: disminuir el tiempo total ´ de una aplicacion, ´ conseguir rede ejecucion solver problemas m´as complejos, de grandes dimensiones, y proporcionar concurrencia, o ´ simult´anea de tareas, sea, permitir la ejecucion ´ red distribuida( en otras ventajas utilizacion WAN o la propia internet) esto nos permite disminuir costos, en vez de pagar para utilizar un supercomputador, podr´ıamos utilizar recursos baratos disponibles remotamente, para problemas de grandes dimensiones, usar memorias de varios computadores permite resolver el ´ de memoria presente problema de la limitacion • J. Fernandez es estudiante de Informatica, Escuela de Informatica, Universidad Nacional de Trujillo, La Libertad, Peru. E-mail: [email protected] • J. Reyes es estudiante de Informatica, Escuela de Informatica, Universidad Nacional de Trujillo, La Libertad, Peru. Articulo recivido el 31 de Mayo, 2016; revisado 31 Mayo, 2016.

´ en una unica m´aquina. Adem´as de esto, po´ ˜ demos decir que durante los ultimos 10 anos, ´ apuntan a la las tendencias en computacion ´ paralela, presencia continua de la computacion ´ continuan ´ dado que las redes de interconexion avanzando significativamente en t´erminos de ´ y ancho de banda. velocidad de comunicacion Mayo 31, 2016

2. ¿Q UE ESTUDIA LA C OMPUTACION PARALELA Y D ISTRIBUIDA ? ´ Debido a la terminolog´ıa de la computacion paralela y distribuida var´ıa entre las comuni´ dades, ofrecemos aqu´ı una breve descripcion de los sentidos previstos de algunos t´erminos. Esta lista no es exhaustiva ni definitiva, pero se proporciona en aras de la claridad. -Paralelismo: El uso de los recursos computacionales adicionales simult´aneamente, por lo general para acelerar. ´ eficaz y regular el -Concurrencia: la gestion acceso simult´aneo a los recursos. -Actividad: Un c´alculo que pueden realizar de forma concurrente con otros; por ejemplo, un programa, proceso, hilo, o un componente de hardware paralelo activo. -Atomicidad: Reglas y propiedades de le´ es observacionalmente galidad de una accion indivisible; por ejemplo, el establecimiento de ´ de todos los bits en una palabra, la transmision ´ ´ un unico paquete, o completar una transaccion.

COMPUTACION PARALELA Y DISTRIBUIDA, ESTADO DEL ATRE, VOL. 1, NO. 1, MAYO 2016

-Consenso: Acuerdo entre dos o m´as actividades alrededor de un predicado dado; Por ˜ de ejemplo, el valor de un contador, el dueno ´ de un hilo. una cerradura, o la terminacion -Consistencia: Las reglas y propiedades que rigen acuerdo acerca de los valores de las variables escritos o mensajes producidos, por parte de algunas actividades y usada por otros (por lo tanto, posiblemente, exhibiendo una carrera de datos); por ejemplo, la consistencia secuencial, que indica que los valores de todas las variables de un programa paralelo de memoria compartida son equivalentes a la de ´ ´ de algun ´ un unico programa de la realizacion entrelazado de accesos a la memoria de estas actividades. -Multicast: Un mensaje enviado a varios des´ tinatarios, posiblemente, en general, sin ningun tipo de restricciones acerca de si algunos de los destinatarios reciban el mensaje antes que otros. Un evento es un mensaje de multidi´ enviado a un conjunto designado de fusion oyentes o suscriptores. 2.1. Fundamentos del Paralelismo En esta a´ rea se estudia todos los fundamentos del paralelismo como por ejemplo: c´alculos ´ simult´aneos multiples; los objetivos del para´ y coordinacion ´ como lelismo; la comunicacion ´ Los por ejemplo la necesidad de sincronizacion; ´ que no se encuentran errores de programacion ´ secuencial o carreras de en la programacion datos.

2

dependencia de tiempo, es decir, un procesador ´ de la tarea T1 P1 debe culminar la ejecucion antes que otro procesador P2 pueda comenzar ´ de la tarea T2. Normalmente, ellas la ejecucion ´ para cumplir deben comunicarse informacion sus trabajos, ya sea: - Compartiendo recursos: datos en la memoria compartida, etc. ´ de la informacion: ´ env´ıo - Por la transmision de mensajes, etc. 2.3.1. Paso de Mensajes Los datos son intercambiados entre los procesadores por medio de mensajes. El mensaje es originado en un sitio (el procesador que env´ıa), transmitido a trav´es de la red de intercone´ y recibido en otro lugar (el procesador xion, receptor). Cualquier computador puede actuar como receptor o puede enviar mensajes en un momento dado. Para el sistema de pase de mensajes la red es un servidor, y de acuerdo ´ del que env´ıa y del que recibe la a la ubicacion ´ de comunicacion ´ puede hacerse m´as operacion r´apida o no. 2.3.2. Exclusion Mutua En las m´aquinas a memoria compartida, la forma de comunicarse dos procesadores es a trav´es de la memoria compartida entre ellos. Esto implica que se debe controlar el acceso a la memoria para que dos o m´as procesos no accesen al mismo tiempo la misma direc´ de memoria y se creen as´ı situaciones de cion inconsistencia (por ejemplo, datos modificados simult´aneamente por dos procesos distintos).

´ paralela 2.2. Descomposicion ´ basada en ta- 2.3.3. Redes de Interconexion Se estudia la descomposicion ´ o como hilos, reas, estrategias de aplicacion Las m´aquinas paralelas pueden clasificarse ´ Data-paralelo, estrategias tales descomposicion ´ si es directa tomando en cuenta la conexion: como SIMD y MapReduce. entre los procesadores (normalmente la red de ´ es est´atica) o a trav´es de bancos interconexion ´ y Coordinacion ´ 2.3. Comunicacion de memorias compartidos (en este caso, la red ´ es generalmente din´amica) Las m´aquinas paralelas se caracterizan por de interconexion replicar algunos de sus componentes: unidades - Memoria compartida: Los procesos tienen de procesamiento, unidades de control, etc. acceso a la misma memoria f´ısica. Los procesos ´ Adem´as, es muy raro que la descomposicion pueden correr en un solo procesador( tiem´ en tareas, po compartido) o los procesos pueden correr que uno haga de una aplicacion conlleve a que estas sean completamente inde- en procesadores distintos dentro del mismo pendientes entre ellas. En este caso se habla de computador.

COMPUTACION PARALELA Y DISTRIBUIDA, ESTADO DEL ATRE, VOL. 1, NO. 1, MAYO 2016

- Memoria Distribuida: Otra forma es conectar a los procesadores directamente entre ellos (la memoria est´a distribuida entre los procesadores), teni´endose as´ı una m´aquina a memoria distribuida sin espacio de direcciones globales.

3

realizar. De esta manera, parte de los datos pueden ser procesados en la fase 1 mientras otros son procesados en la 2, otros en la tres, y as´ı sucesivamente. -MIMD(Multiple Instruction, Multiple Data): ´ Las ideas b´asicas son que multiples tareas heterog´eneas puedan ser ejecutadas al mismo tiempo, y que cada procesador opere indepen2.4. Algoritmos Paralelos, Analisis y Prodientemente con ocasionales sincronizaciones gramacion con otros. Est´a compuesto por un conjunto Aqu´ı podemos estudiar un algoritmo, anali- de elementos de procesamiento donde cada zarlo, ver su eficiencia y rendimiento. Vemos uno realiza una tarea, independiente o no, con ´ y la respecto a los otros procesadores. caminos cr´ıticos, el trabajo y la duracion ´ con la ley de Amdahl. Asi como la relacion velocidad y escalabilidad. 2.6. Rendimiento paralelo Un aspecto importante a considerar es que En los Sistemas Distribuidos/Paralelos, uno todo programa paralelo tiene una parte secuen´ de sus principales problemas es la degradacion ´ cial que eventualmente limita la aceleracion que se puede alcanzar en una plataforma pa- de sus rendimientos. En un ambiente ideal, el rendimiento crece linealmente al crecer el ralela. ´ ´ de procesadores. Si se duplica el nume´ es la re- numero La Ley de Amdahl: la aceleracion ro de procesadores en un sistema, el rendi´ entre el tiempo de ejecucion ´ sobre un lacion miento deber´ıa igualmente duplicarse. Esto no ´ procesador secuencial y el tiempo de ejecucion ´ en multiples procesadores. Esto es conocido sucede en la realidad, ya que a partir de un ´ cierto numero de procesadores los excesivos como la ”ley de Amdahl”. intercambios de mensajes de control y de transferencia de datos entre los procesadores, pro2.5. Arquitectura Paralela ´ en el sistema, lo vocan un efecto de saturacion ´ ´ la que genera autom´aticamente una degradacion Aqu´ı estudiamos las arquitecturas segun del rendimiento. Parece entonces evidente la taxonom´ıa de Flynn, a los procesadores multi ´ entre la optimizacion ´ del rendimiento ´ nucleo, el procesamiento vectorial, el procesa- relacion ´ y la minimizaci on de los intercambios entre los miento sim´etrico(SMP), y los accesos de memoprocesadores. Existen otros aspectos que juegan rias UMA y NUMA. un papel importante para optimizar el rendimiento en un sistema Distribuido/Paralelo, 2.5.1. Taxonomia de Flynn como es el equilibrio de la carga de trabajo, y -SISD(Single Instruction, Single Data): un ´ del numero ´ la minimizacion de operaciones de ´ unico programa es ejecutado usando solamenentradas/salidas, entre otros. te un conjunto de datos espec´ıficos a e´ l. SIMD(Single Instruction, Multiple Data): un simple controlador env´ıa las instrucciones, una 2.7. Sistemas Distribuidos Un sistema distribuido se define como una a una, a un arreglo de procesadores que ope´ de computadoras separadas f´ısicaran en el esquema maestro-esclavo. Es de- coleccion cir, las instrucciones son difundidas desde la mente y conectadas entre s´ı por una red de memoria a un conjunto de procesadores. As´ı, comunicaciones; cada m´aquina posee sus comcada procesador es simplemente una unidad ponentes de hardware y software que el pro´ aritm´etica-logica y se tiene una sola unidad gramador percibe como un solo sistema (no nede control. -MISD(Multiple Instruction, Single cesita saber qu´e cosas est´an en qu´e m´aquinas). Data): La idea es descomponer las unidades El programador accede a los componentes de de procesamiento en fases, en donde cada una software (objetos) remotos, de la misma mase encarga de una parte de las operaciones a nera en que acceder´ıa a componentes locales,

COMPUTACION PARALELA Y DISTRIBUIDA, ESTADO DEL ATRE, VOL. 1, NO. 1, MAYO 2016

en un grupo de computadoras que usan un middleware entre los que destacan (RPC) y SOAP para conseguir un objetivo. Los sistemas distribuidos deben ser muy confiables, ya que si un componente del sistema se descompone otro componente debe ser capaz de reemplazarlo. Esto se denomina tolerancia a fallos. El ˜ de un sistema distribuido puede ser tamano muy variado, ya sean decenas de hosts (red de a´ rea local), centenas de hosts (red de a´ rea metropolitana), o miles, o millones de hosts (Internet); esto se denomina escalabilidad. 2.8. Cloud Computing ´ se Es un paradigma en el que la informacion almacena de manera permanente en servidores en Internet y se env´ıa a memorias temporales del cliente, lo que incluye computadores port´atiles, equipos de escritorio, centros de ocio, tel´efonos celulares, etc. Como consecuen´ cia se ha creado un nuevo modelo de prestacion de servicios de negocio y tecnolog´ıa, basados en la web. Este modelo permite al usuario acceder a un cat´alogo de servicios estandarizados y responder a las necesidades de su negocio. ´ El usuario, a cambio, paga unicamente por el consumo efectuado. Los tipos de servicios que se pueden proveer a trav´es de la nube son muy variados: almacenamiento de documentos y datos, los usuarios pueden obtener un CPU sin comprar equipo, utilizar un software para ´ de los recursos empresariales la planificacion (ERP)sin necesidad de comprarlo, etc. 2.9. Modelos Formales y Semanticas Estudia - Los modelos formales de los procesos y de paso de mensajes, incluyendo las ´ secuencial a´ lgebra tales como la comunicacion - Procesos (CSP) y pi-c´alculo - Los modelos for´ en paralelo, incluyendo males de computacion el paralelo de acceso aleatorio de la m´aquina (PRAM) y - alternativas como paralelo s´ıncrona a granel (BSP) - Los modelos formales de dependencias computacionales - Modelos de consistencia de memoria compartida (relaja´ con las especificaciones del do) y su relacion ´ - requisitos de relenguaje de programacion ´ gularidad algor´ıtmicos incluyendo instruccion ´ ´ logar´ıtmica, atomica - Modelos de progresion

4

incluyendo no bloqueantes garant´ıas y equidad - Las t´ecnicas para especificar y comprobar las ´ como la atomicidad propiedades de correccion y la ausencia de datos.

3. P ROSPECTIVA DE LA C OMPUTACION ˜ PARALELA Y D ISTRIBUIDA EN 20 A NOS ´ paralela y distribuida en los La computacion ´ ˜ ha ido creciendo exponencialmenultimos anos ´ de los sistemas de te. Debido a la evolucion ´ computo paralelo, el desarrollo de aplicaciones que explotan paralelismo ha ido cambiando paulatinamente su foco. Desde las cl´asicas aplicaciones num´ericas en supercomputadores de alto rendimiento, hacia las aplicaciones de ´ de streaming multimedia, y la computacion ´ proposito general en cualquier a´ mbito. Hoy por hoy interesa explotar el paralelismo tanto de algoritmos b´asicos como de complejos programas modulares. Las nuevas aplicaciones paralelas muestran diferentes niveles de paralelis´ mo, con diferentes estrategias de paralizacion. Muchas aplicaciones muestran comportamientos din´amicos, dependientes de datos, donde las pol´ıticas de balanceo autom´atico de carga son claves. A su vez, las aplicaciones deber´ıan ser flexibles, para poder ejecutarse en entornos ´ cada vez m´as diversos, mezclando cluster de memoria distribuida con multicores y dispositivos aceleradores como GPUs. La enorme diversidad y heterogeneidad de las plataformas, y las diferentes formas de componer dichos elementos presentan problemas para el desarrollo de aplicaciones portables que sean capaces de adaptarse de forma eficiente al entorno de ´ Hasta ahora han aparecido diversos ejecucion. ´ que han sido adopmodelos de programacion tados con e´ xito por la comunidad cient´ıfica y de desarrolladores. En sistemas distribuidos las implementaciones eficientes del paradigma de paso de mensajes (las implementaciones de MPI). Para sistemas de memoria compartida las herramientas de control de threads de alto nivel (OpenMP). Para los dispositivos aceleradores, o sistemas h´ıbridos que contengan aceleradores, modelos espec´ıficos (CUDA u OpenCL). En un intento de unir diferentes tendencias y paradigmas los modelos PGAS (Partitioned Global Adress Space) (UPC, Chapel, X10). Sin embargo

COMPUTACION PARALELA Y DISTRIBUIDA, ESTADO DEL ATRE, VOL. 1, NO. 1, MAYO 2016

cada d´ıa se crean nuevas arquitecturas con cada ´ vez m´as potencia y nucleos que explotar, en ˜ unos 20 anos veremos como las arquitecturas de computadoras van a cambiar, veremos que una computadora ya no se compondr´a de 2 ,3 ´ ´ o 4 nucleos, sino de 30 o 40 nucleos, es mas ya no usaremos una placa madre, sino tal vez dos o tres a la vez; estos avances se ver´an forzados a llevar el software a otro nivel, y con estos avances deben surgir nuevas tecnolog´ıas de software. Para poder aprovechar estas ar´ ser´an lenguaquitecturas la principal aparicion ´ y compiladores paralelos jes de programacion nativos, dejaremos de lado a los compilado´ res que ejecutan codigo de manera secuencial y las librer´ıas que ayudan al paralelismo de lenguajes secuenciales tambi´en desaparecer´an. Los algoritmos deber´an ser implementados de manera paralela y aqu´ı el an´alisis de algoritmos ser´a clave, as´ı como tambi´en su rendimiento y complejidad. Otra de las a´ reas que se van a beneficiar ser´a el procesamiento gr´afico, pues ´ paralela y las nuevas arcon la computacion quitecturas ser´a m´as sencillo poder representar gr´aficos cada vez m´as n´ıtidos sin mucho esfuer´ en la nube, los sistemas zo. La computacion distribuidos y las supercomputadoras tambi´en se ver´an beneficiadas con este avance, ya que la ´ prioridad de estas es el uso eficiente y optimo de los recursos.

4.

5

[2] Association From Computing Machinery and IEEE. (2013). Computer Science Curricula 2013. United States of America. [3] Jimenes, D., Boratto, M., Coelho, L. (s.f.). Uni˜ versidad de Murcia- Espana. Obtenido de Univer˜ sidad de Murcia- Espana: http://dis.um.es/ domingo/09/ERBASE/minicursoespanol.pdf [4] Liu, M. (2004). Computacion Distribuida, Fundamentos y Aplicaciones. United States Of America: Pearson Edication. [5] Ortiz, A. (2012). Programacion Multinucleo. Monterrey, Mexico. [6] Solano, J. (2011). Computacion en la Nube. Investiga TEC, 4-5. [7] Vargas, J., Alpizar, I. (s.f.). Universidad de Costa Rica. Recuperado el 22 de 05 de 2016, de Universidad de Costa Rica: http://citic.ucr.ac.cr/sites/default/files/recursos/17

Joel Fernandez Segura Estudiante de la carrera profesional de Informatica, en la Universidad Nacional de Trujillo. PLACE PHOTO HERE

C ONCLUSION

Como pudimos observar el area de la ACM Computacion Paralela y Distribuida abarca un tema muy interesante, amplio y aun por investiar mucho mas , tambien el avance de las tecnologias en la arquitectura nos ayuda a poder lograr la programacion paralela. El estudio de los algoritmos paralelos y su rendimiento nos da una perspectiva de los avances en terminos ˜ de los medibles del rendimiento. Y el diseno sistemas distribuidos han contribuido bastante para la tecnologia de hoy en dia, tal como la computacion en la Nube, los clusters.

R EFERENCIAS [1] Aguilar, J., Leiss, E. (2004). Introduccion a la Computacion Paralela. Merida, Venezuela: Graficas Quinteto.

Jordy Reyes Julca Estudiante de la carrera profesional de Informatica, en la Universidad Nacional de Trujillo. PLACE PHOTO HERE