Patrones Algoritmicos Paralelos

UNIVERSIDAD TÉCNICA DE MANABÍ
TEMA:
PATRONES ALGORITMICOS PARALELOS
OBJETOS Y ABSTRACION DE DATOS
INTEGRANTES:
ALCIVAR CANO ROBERTH STEEVEN

FERNÁNDEZ ZAMORA ERIKA
GUADALUPE
SOLORZANO MACÌAS LUIS DANILO
PROFESOR:
ING. CRISTHIAN TORRES
PARALELO:
“A”
PATRONES ALGORITMICOS PARALELOS
En las ciencias de la computación, un algoritmo paralelo, en oposición a los algoritmos clásicos

o algoritmos secuenciales, es un algoritmo que puede ser ejecutado por partes en el mismo instante
de tiempo por varias unidades de procesamiento, para finalmente unir todas las partes y obtener el
resultado correcto.
Por el contrario, a veces los problemas no son tan fácilmente paralelizables, de ahí que estos
problemas se conozcan como problemas inherentemente secuenciales. Como ejemplo de estos
métodos tendríamos los métodos numéricos iterativos como el método de Newton o el problema de
los tres cuerpos. Por otro lado, algunos problemas son difícilmente paralelizables, aunque tengan una
estructura recursiva. Como ejemplo de esto último tendríamos la búsqueda primero en
profundidad en un grafo.
Los algoritmos paralelos son importantes porque es más rápido tratar grandes tareas de computación
mediante la paralelización que mediante técnicas secuenciales. Esta es la forma en que se trabaja en
el desarrollo de los procesadores modernos, ya que es más difícil incrementar la capacidad de
procesamiento con un único procesador que aumentar su capacidad de cómputo mediante la
inclusión de unidades en paralelo, logrando así la ejecución de varios flujos de instrucciones dentro
del procesador. Pero hay que ser cauto con la excesiva paralelización de los algoritmos ya que cada
algoritmo paralelo tiene una parte secuencial y debido a esto, los algoritmos paralelos puedes llegar a
un punto de saturación
El coste o complejidad de los algoritmos secuenciales se estima en términos del espacio y tiempo
ciclos de procesador que requiera. Los algoritmos paralelos también necesitan optimizar la
comunicación entre diferentes unidades de procesamiento. Esto se consigue mediante la aplicación
de dos paradigmas de programación y diseño de procesadores distintos: memoria compartida o paso
de mensajes.
La técnica memoria compartida necesita del uso de cerrojos en los datos para impedir que se
modifique simultáneamente por dos procesadores, por lo que se produce un coste extra en ciclos de
CPU desperdiciados y ciclos de bus. También obliga a serializar alguna parte del algoritmo.
La técnica paso de mensajes usa canales y mensajes, pero esta comunicación añade un coste al bus,
memoria adicional para las colas y los mensajes y latencia en el mensaje. Los diseñadores de
procesadores paralelos usan buses especiales para que el coste de la comunicación sea pequeño, pero
siendo el algoritmo paralelo el que decide el volumen del tráfico.
El trabajo propone el diseño e implementación de un conjunto de algoritmos paralelos programados
en JAVA que proporcionan al programador una forma simple de solucionar problemas diversos que
pueden ir desde una solución de ordenación hasta la de un problema de simulación mediante el uso
de una biblioteca de clases de Objetos Paralelos. Los algoritmos paralelos implementados se
construirán como Patrones de Diseño Paralelos a través de una metodología donde cada diseño
algorítmico representa la estructura paralela de control común a una determinada técnica algorítmica
generando un programa paralelo general del cual a su vez se deriven dos o más programas modelo
que resuelvan problemas particulares. Se ha diseñado la técnica algorítmica de divide y vencerás
como un Patrón de Diseño Paralelo y se han implementado algunas aplicaciones. La implementación
se hace de forma concurrente mediante la creación de hilos, explicando los pasos a realizar en el
desarrollo de este tipo de Patrones.
Una de las más importantes utilidades de las multicomputadoras es su uso en la computación

algorítmica para obtener velocidad y eficacia. Se propone el diseño e implementación de un conjunto
de algoritmos paralelos como patrones que deriven en dos o más programas específicos, llamados
programas modelo que resuelvan problemas particulares ya que clarifica el estudio de algunas
técnicas de programación paralela aplicables a numerosos problemas prácticos; sin embargo, estas
técnicas asumen estructuras de control distintas en problemas similares, lo cual genera dificultades
prácticas al utilizarlas como pueden ser las siguientes:
 Es difícil suponer cual es la estructura algorítmica común a todos los algoritmos del mismo
patrón de diseño generado.
 Los patrones de diseño propuestos son demasiado dependientes del problema a resolver y no
proporcionan intuición práctica para derivar nuevos algoritmos utilizando la orientación a
objetos.
 Estos patrones de diseño se entienden mejor como programas particulares más que como
auténticos patrones.
TIPOS DE PATRONES
 Patrón de estructura de lenguaje

Un catálogo estructurado de patrones de diseño que soportan actividades de diseño como
“redes de patrones de diseño conectadas”
 El patrón de paralelismo de tareas
Paralelismo de tareas es un paradigma de la programación concurrente que consiste en
asignar distintas tareas a cada uno de los procesadores de un sistema de cómputo. En
consecuencia, cada procesador efectuará su propia secuencia de operaciones.
Por ello se hace necesario definir un diseño de nivel intermedio entre la descripción vaga de una
Programación de Patrones de Diseño Paralelos y un conjunto de Programas Particulares que
resuelven un problema concreto. Este nivel intermedio es un Patrón de Diseño original que describe
la estructura de control común compartida por todos los algoritmos que corresponden al mismo
patrón. Ni los tipos de datos, ni el código de procedimientos específicos dependientes de los datos
necesitan ser detallados en este nivel, ya que éstos dependen de problemas concretos. El objetivo
general de la investigación es el de obtener eficiencia en aplicaciones paralelas derivando estructuras
de control comunes a problemas distintos que lleven dentro de sí el mismo patrón de programación y
tratar con ello de minimizar las dependencias de los datos globales entre procesos paralelos. Para
hacer esto se requiere que el componente secuencial de los algoritmos paralelos tenga un mínimo de
dependencias con el código que implementa el patrón de programación; por tanto, la creación de una
estructura algorítmica general debe ser adaptada a las diferentes aplicaciones concretas cuyas formas
de solución pertenezcan al mismo patrón. Un objetivo particular es el de implementar el patrón
divide y vencerás en el lenguaje JAVA como una estructura general o plantilla, donde sus procesos
paralelos deben ser especificados mediante la creación de hilos de forma concurrente. Cada hilo
representa por tanto un proceso genérico a ejecutarse en el programa e incluye como parámetros
formales el problema secuencial a resolver o subproblemas. Cabe mencionar que la recursividad
juega un papel muy importante en ciertos patrones como lo es el mencionado, el cual es definido
como un algoritmo de partición recursiva, es decir; divide y vencerás resuelve un problema
dividiéndolo en problemas subordinados los cuales a su vez son resueltos recursivamente mediante la
división de ellos en el futuro. El resultado final se obtiene igualmente de forma recursiva
combinando las soluciones de los subproblemas. El paralelismo nace casi de forma natural en este
tipo de diseños algorítmicos donde cada problema puede ser resuelto independientemente de los
otros. Para especificar un algoritmo de partición recursiva como lo es divide y vencerás hay que
tener en cuenta componentes importantes tales como:
 Estructuras de datos para representar el problema y la solución.

 Un predicado que indique cuando un problema es indivisible o si éste puede ser dividido en el
futuro.
 Una función que regrese problemas indivisibles en soluciones.
 Una función que divida problemas en subproblemas.
 Una función que combine soluciones en una sola solución.
PREGUNTAS
1. PATRONES PARALELOS ES:

 Es un algoritmo que puede ser ejecutado por partes en el mismo instante de tiempo por
varias unidades de procesamiento.
 Dependen de problemas concretos
 Implementa el patrón divide y vence en el lenguaje JAVA
 Es una función lógica de varios argumentos.
 Clarifica el estudio de algunas técnicas de programación paralela aplicables a numerosos
problemas prácticos
2. ESCOJA LA SOLUCIÓN DE UN PROBLEMA EN UN CONTEXTO.
 Una descripción estructurada de soluciones de alta calidad a problemas recurrentes.
 Creación de una estructura algorítmica general debe ser adaptada a las diferentes aplicaciones
concretas
 Análisis de grandes conjuntos de datos para categorizar, procesar, clasificar, personalizar y facilitar
contenido
 Análisis de conjuntos de datos muy grandes para identificar patrones y recomendar cursos de acción
 Analizar conjuntos de datos de gran tamaño para reconocer, procesar y etiquetar texto, lenguaje,
voz y hacer recomendaciones basadas en el etiquetado.
3. UN PATRÓN DE LENGUAJE ES:
 Un catálogo estructurado de patrones de diseño que soportan actividades de diseño
como redes de patrones de diseño conectadas
 Asumen estructuras de control distintas en problemas similares, lo cual genera dificultades
prácticas al utilizarlas
 Son un grupo de formas de trabajo que permiten mediante la manipulación de variables, realizar
ciertos procesos específicos
 Es un conflicto que se presenta como inconveniente para alcanzar objetivos o estabilidad en
distintos ámbitos
 Se trata de una serie de instrucciones o reglas establecidas que, por medio de una sucesión de
pasos, permiten arribar a un resultado o solución.
4. COMPONENTES IMPORTANTES DE UN ALGORITMO PARALELO
 Una función que regrese problemas indivisibles en soluciones.
 Un algoritmo debe ser Impreciso y no indicar el orden de cada paso
 Un algoritmo debe ser finito. Si se sigue un algoritmo, no debe terminar es continuo
 Un conjunto de instrucciones que deben involucrar decisiones
 Describen ciertas características de problemas que dan indivisibles soluciones
5. EL PATRÓN DE PARALELISMO DE TAREAS ES:
 Consiste en asignar distintas tareas a cada uno de los procesadores de un sistema de
cómputo.
 Son bloques o símbolos que representan cada una de las etapas de un algoritmo
 Una forma de expresar los distintos pasos que va a realizar un programa, de la forma más parecida a
un lenguaje de programación.
 El que se encarga de procesar informaciones directas
 Parámetros formales el problema secuencial a resolver o subproblemas.

Patrones Algoritmicos Paralelos

Cargado por

Copyright:

Formatos disponibles

Patrones Algoritmicos Paralelos

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Patrones Algoritmicos Paralelos

Cargado por

Copyright:

Formatos disponibles

UNIVERSIDAD TÉCNICA DE MANABÍ

PATRONES ALGORITMICOS PARALELOS

OBJETOS Y ABSTRACION DE DATOS

ALCIVAR CANO ROBERTH STEEVEN

ING. CRISTHIAN TORRES

En las ciencias de la computación, un algoritmo paralelo, en oposición a los algoritmos clásicos

Una de las más importantes utilidades de las multicomputadoras es su uso en la computación

 Patrón de estructura de lenguaje

 Estructuras de datos para representar el problema y la solución.

1. PATRONES PARALELOS ES:

También podría gustarte