Autor Tema: Dudas sobre algoritmo paralelo  (Leído 2821 veces)

0 Usuarios y 1 Visitante están viendo este tema.

Desconectado CompSystems

  • PIC18
  • ****
  • Mensajes: 488
    • Home Page
Dudas sobre algoritmo paralelo
« en: 04 de Agosto de 2016, 23:55:12 »
Hola, ¿han programado ustedes alguna vez algún tipo de algoritmo paralelo? si es así, pueden compartir una explicación o algún ejemplo sencillo.


La información que he encontrado es muy confusa, pero se dice que un algoritmo que se presta a paralelismo es la regla de cramer, este método sirve para solucionar sistemas lineales mediante el cálculo de determinantes, una parte del algoritmo es realizar n determinantes, por ejemplo si el sistema tiene 3 incógnitas X,Y,Z (n=3) , se debe efectuar n+1 determinantes, Dx, Dy, Dz, Dbase, siguiendo la lógica de un algoritmo secuencial, la única manera de aplicar la regla de cramer es efectuando los 4 determinantes uno por uno y almacenando cada resultado en una variable, el valor de cada incógnita se determina por x=Dx/Dbase, y=Dy/Dbase, z=Dz/Dbase
fuente
http://www.allmathwords.org/es/c/cramersrule.html

mientras que siguiendo la lógica de algoritmo paralelo, cada determinante lo podría efectuar una CPU independientemente, de esta manera se calculan los 4 determinantes paralelamente, he leído sobre hilos en JAVA tiene que ver con algoritmo paralelo?

En mi caso siempre he programado con algoritmos secuenciales, pero existen algoritmos paralelos, la siguiente definición es basada en varios links  ¿es correcta?, no duden en corregirme

Algoritmo Paralelo

En programación un algoritmo paralelo se usa para conseguir aceleraciones en la respuesta de un problema, o para hacer viable un cómputo complejo o computación científica, requiere estrictamente de varias unidades de procesamiento (CPUs) independientes o por lo menos múltiples núcleos de procesamiento en un solo chip (procesador multi-core ), el algoritmo se codifica para que cada tarea o sub-problema se ejecute en un hilo de procesamiento (threads) y el programa de control u OS se encargue en tiempo de ejecución de seleccionar cierta cantidad de ellos, cada tarea es procesada y ejecutada paralelamente o por lotes dependiendo de la ocupación de las CPUs.
Según la lógica del algoritmo cada función por ejemplo puede ir procesando y mostrando una salida o en otro caso esperar a que todas o lotes de CPUs terminen para finalmente unir todas las partes y obtener el resultado útil, se usan este tipo de algoritmos para cálculos de ingeniería avanzados, simulación de plantas nucleares, procesos químicos complejos, predicción del tiempo atmosférico, renderizado de imágenes y procesamiento de audio, descifrado de códigos, etc.)

Aunque el modelo de los hilos de la programación en paralelo se ejecutan independientemente unos con respectos a otros, todos ellos pueden acceder al mismo espacio de memoria (MEMORIA COMPARTIDA) generado problemas de y condición de carrera y de colisión sino hay una sincronización perfecta de escritura, generando retardos de procesamiento ya que cada hilo se debe tomar un turno para poder leer y almacenar datos además, requiere la necesidad de algún tipo de comunicación o la coordinación entre las sub-tareas.


Hay una clase de problemas que no pueden ser divididos en sub-problemas independientes, podemos llamarlos problemas intrínsecamente secuenciales o en serie. Para estos tipos de problemas, el cálculo en una etapa no depende de los resultados de un cálculo en una etapa anterior, y por esta razón no es tan fácil de paralelizar a través de unidades de procesamiento independientes. 

Fuente: http://gribblelab.org/CBootcamp/A2_Parallel_Programming_in_C.html
https://es.wikipedia.org/wiki/Condici%C3%B3n_de_carrera
https://es.wikipedia.org/wiki/Algoritmo_paralelo
https://es.wikipedia.org/wiki/Computaci%C3%B3n_paralela


Algoritmo Paralelo Virtualizado

Es un algoritmo que simula un paralelismo, es un caso típico de los sistemas operativos, similar a un programa gestionador ya que realiza un cambio de contexto entre las diferentes tareas, las n tareas no se ejecutan simultáneamente, simplemente se asigna un corto tiempo de ejecución a cada una de ellas, este barrido o salto entre tareas da la APARIENCIA de que todas se están ejecutándose simultáneamente, la multitarea en los actuales OS también hacen uso del verdadero procesamiento multi-core. El OS se encarga de ejecutar


1.2.2: Algoritmo seudoparalelo

Son algoritmos donde se realiza aparentemente el computo paralelo de lista argumentos, por lo general los argumentos están contendidos dentro de contenedores, en lenguaje LisP por ejemplo usan paréntesis curvos (), en lenguaje RPL usa llaves {},  en lenguaje HP-Prime usa llaves {} o paréntesis rectangulares [].

Similarmente a un Algoritmo Paralelo Virtualizado las instrucciones se efectúan en serie, para este caso se procesa uno a uno los argumentos (por pares) y al final cuando se termina de calcular la última operación o par se retorna la salida como un solo objeto. los lenguajes que soportan este paradigma de programación son LisP, RPL, HP-prime entre otros.

Ejemplo:
RPL:
{1,2,3} {4,5,6}  *  → {4,10,18}
LISP (PN):
*(1,2,3) (4,5,6) → (4,10,18)

HP-PRIME
mul1 := {1,2,3}*{4,5,6}  → mul21 := {4,10,18}
mul2 := {{1,2},3,4}*{{5,6},7,8} → mul2 := {{5,12},21,32}
mul3 := [[1,2],3,4]*[[5,6],7,8] → mul3 := [[5,12],21,32]
pot1 :=  [[1,2],[3,4],[5,6]]^3 → pot3 := [[1,8],[27,64],[125,216]]





Muchas Gracias

Actualizado según aportes de abajo
« Última modificación: 05 de Agosto de 2016, 12:07:34 por CompSystems »
Desde Colombia

Desconectado KILLERJC

  • Colaborador
  • DsPIC33
  • *****
  • Mensajes: 8242
Re:Dudas sobre algoritmo paralelo
« Respuesta #1 en: 05 de Agosto de 2016, 07:13:58 »
Citar
Hola, ¿han programado ustedes alguna vez algún tipo de algoritmo paralelo? si es así, pueden compartir una explicación o algún ejemplo sencillo.

Jamas tuve la necesidad, creo que una sola ves intente en python, pero decidi ir por el uso de un solo nucleo, ya que no era algo demasiado complejo.

Citar
En mi caso siempre he programado con algoritmos secuenciales, pero existen algoritmos paralelos, la siguiente definición es basada en varios links  ¿es correcta?, no duden en corregirme

Si, me parece correcto, la definicion aunque tengo entendido que uno no elige que nucleo exactamente va a manejar cada tarea sino que uno crea hilos (threads) y luego el OS se encarga de paralelizarlo, mas que obvio que no solamente tu codigo se esta ejecutando en cada nucleo y mas que seguro que uno tarde mas que el otro, debido a esto y que son 4 algoritmos intentando acceder a un mismo dato pueden aparecen mas problemas, como asegurarse que los datos sean correctos y que no lo cambie 1 thread en el medio de la ejecucion, tambien problemas que encontras en en el modo "Virtualizado"/RTOS, en el cual tenes que usar lock/mutex,etc

El "Virtualizado" simplemente es un secuencial con cambio de contexto o lo que nosotros vemos en los RTOS.

--------

Lo que no se si te referis a que es confuso la regla de cramer, esa es una muy simple, tenes que observar los coeficientes de cada variable, y luego te queda el coeficiente al lado del igual.
Si observas en el link el determinante de lo que llamas "Dbase", es solamente realizado con los coeficientes de las variables en cuestion, mientras que los demas Dx, Dy, Dz, se hacen reemplazando la columna con los coeficientes independientes (es decir los que estan al lado del igual) en cada columna, antes tenias que las X ocupaban la primer columna, entonces se reemplaza toda la primer columna y de ahi sale Dx.

Todo el secreto de Cramer.

Ahora si observas, para comenzar a hacer el determinante no es necesario que termine ninguna operacion antes. Es decir se introduce los coeficientes de cada incognita y luego ya se puede comenzar a hacer cualquier a de los determinantes, por eso mismo se pueden ejecutar independientemente cada uno. Finalmente si queres seguir Paralelizando y hacer la division en cada thread donde se hizo los determinantes Dx,Dy y Dz, vas a tener que esperar por el dato de Dbase, sino no vas a poder continuar. Y luego para volver de eso,  vas a tener que esperar que todos los otros threads terminen.
Sino solo paralelizas Dx,Dy y Dz, esperas que todos los threads terminen, y se pueda acceder a cada uno de los valores, y continuas dividiendo y mostrando en forma "virtualizada".

Algo que se puede ver un poco mas en codigo :
http://gribblelab.org/CBootcamp/A2_Parallel_Programming_in_C.html
« Última modificación: 05 de Agosto de 2016, 07:27:02 por KILLERJC »

Desconectado Picuino

  • Moderadores
  • DsPIC33
  • *****
  • Mensajes: 5878
    • Picuino
Re:Dudas sobre algoritmo paralelo
« Respuesta #2 en: 05 de Agosto de 2016, 08:40:40 »
Es muy común que un sólo procesador tenga que hacer varias tareas a la vez. Eso es en paralelo. Ejemplo: rutinas de interrupciones.

Otro tipo de paralelismo es el de varios procesadores realizando diferentes tareas que tienen que sincronizarse entre sí (por ejemplo sincronización entre máquinas o robots)

Otro menos común es el de un problema matemático complejo que se divide entre varios procesadores (cálculo del tiempo atmosférico, renderizado de imágenes, simulaciones científicas, descifrado de códigos, etc) Es típico de los grandes centros de cálculo con muchos procesadores.

Hay mucho que aprender sobre paralelismo y en ciertos casos es bastante complejo.

¿Para qué lo quieres exactamente? ¿Es sólo por curiosidad?

Desconectado Picuino

  • Moderadores
  • DsPIC33
  • *****
  • Mensajes: 5878
    • Picuino
Re:Dudas sobre algoritmo paralelo
« Respuesta #3 en: 05 de Agosto de 2016, 08:49:22 »
El paralelismo más sencillo para un sólo procesador es el que hacen los PLCs:

Repetir siempre {
   Leer entradas();

   Ejecutar programa();

   Escribir salidas();
   Enviar y recibir mensajes();
}


Ejecutar programa () {

   Si (condición 1)  Hacer tarea 1;
   Si (condición 2)  Hacer tarea 2;
   Si (condición 3)  Hacer tarea 3;
   Si (condición 4)  Hacer tarea 4;
   Si (condición 5)  Hacer tarea 5;
   Si (condición 6)  Hacer tarea 6;

   Si (condicion 1)  Activar condición 2; Desactivar condición 1   // Tarea dividida en dos pasos
}

Cada tarea debe llevar un tiempo pequeño. Si la tarea es muy larga, hay que dividirla en tareas más simples y ejecutarla por pasos.
Por ejemplo, al terminar la tarea 1 se puede activar la condición para que se ejecute la tarea 2 en el siguiente paso.

Todo el ciclo se repite cada pocos milisegundos, dando la sensación de que todo se ejecuta a la vez.

Saludos.

Desconectado CompSystems

  • PIC18
  • ****
  • Mensajes: 488
    • Home Page
Re:Dudas sobre algoritmo paralelo
« Respuesta #4 en: 05 de Agosto de 2016, 10:25:24 »
Muchas gracias, analizando sus respuestas, deseo redactar un artículo dirigido a personas que desean entrar en el tema de la programación computacional, voy a intentar transmitir algunos conceptos básicos y de fácil entendimiento ya que hay artículos o material técnico difícil de comprender en los libros y en la web.

mas aportes de la comunidad este foro sobre algoritmos paralelos son bienvenidos



Ahora expongo mi definición de Algoritmo

1: Algoritmo

Nos dicen en los cursos de programación que un algoritmo es un conjunto de pasos para de resolver un problema dado, pero esta es una definición sesgada, en los siguientes apartados se muestra una definición más exacta. Una clasificación de algoritmos son Algoritmos Secuenciales, Algoritmos Paralelos


1.1: Algoritmo Secuencial

En general, no existe ningún consenso definitivo en cuanto a la definición formal de algoritmo secuencial o en serie, pero una buena definición es una lista de instrucciones (PASOS FINITOS EN LA MAYORÍA DE LOS CASOS) para TRATAR de resolver un problema dado.

Un problema que se resuelve en pasos finitos es por ejemplo el algoritmo secuencial de cálculo de las raíces de una ecuación cuadrática, si el algoritmo está completamente diseñado, la salida siempre será una lista de raíces reales, con o sin multiplicidad, y/o raíces complejas.

Otro caso es un algoritmo que permanece en un ciclo infinito de pasos, como sabemos PI tiene infinitos números decimales, una muestra de ellos son los siguientes PI=3.1415926535 8979323846 2643383279 5028841971 6939937510 5820974944 5923078164 0628620899 8628034825 3421170679 …,  para este caso se diseña un algoritmo que permanece en un ciclo infinito de pasos, guardando la salida por ejemplo en un archivo, pero hay una limitante, necesitaríamos infinitos sistemas de almacenamiento, una alternativa es mostrar pantallazos o por grupos los decimales del numero PI, borrando periódicamente lotes de decimales una especie de desplazamiento o scroll, aun así el algoritmo continua un bucle infinito, se ha llegado por ejemplo a almacenar en un fichero, 24 billones de dígitos del numero PI en 58 TB TeraBytes por supuesto en varios discos duros, se podría seguir calculando más dígitos, pero las restricciones de hardware actuales lo limitan por ahora, pero en un futuro posiblemente se podrá romper esta barrera.
Fuente sobre el cálculo de numero PI: http://www.solosequenosenada.com/2010/05/14/numero-pi-con-un-millon-decimales-y-programa-para-calcularlo

Otro tipo de algoritmos secuenciales son los que se ejecutan en pasos finitos pero que no siempre resuelven un problema dado como es el caso de ciertos algoritmos de métodos numéricos donde el problema a resolver puede o no converger es decir obtener una solución.
« Última modificación: 05 de Agosto de 2016, 10:29:43 por CompSystems »
Desde Colombia

Desconectado Picuino

  • Moderadores
  • DsPIC33
  • *****
  • Mensajes: 5878
    • Picuino
Re:Dudas sobre algoritmo paralelo
« Respuesta #5 en: 05 de Agosto de 2016, 12:57:55 »
Un tema importante que tienes que conocer a la hora de tratar con el paralelismo es la sincronización.

En informática también se llama computación concurrente: https://es.wikipedia.org/wiki/Computaci%C3%B3n_concurrente

Hay conceptos importantes como:
  concurrencia: concurrencia (informática)
  semáforos: semáforo (informática)
  cierres de exclusión mútua: https://es.wikipedia.org/wiki/Cierre_de_exclusi%C3%B3n_mutua
  mensajes: https://es.wikipedia.org/wiki/Paso_de_mensajes
  bloqueo mutuo: https://es.wikipedia.org/wiki/Bloqueo_mutuo
  Monitor: Monitor (concurrencia)
  Hilo de ejecución: https://es.wikipedia.org/wiki/Hilo_de_ejecuci%C3%B3n
  RTOS: https://es.wikipedia.org/wiki/Sistema_operativo_de_tiempo_real
  modelo de grafos: https://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos#Aplicaciones
  redes de petri: https://es.wikipedia.org/wiki/Red_de_Petri
  condiciones de carrera: https://es.wikipedia.org/wiki/Condici%C3%B3n_de_carrera
  Problema productor-consumidor: https://es.wikipedia.org/wiki/Problema_productor-consumidor

Y otros más que podrás sacar a partir de estos que te he dejado.

Un saludo.
« Última modificación: 05 de Agosto de 2016, 13:00:56 por Picuino »

Desconectado Picuino

  • Moderadores
  • DsPIC33
  • *****
  • Mensajes: 5878
    • Picuino
Re:Dudas sobre algoritmo paralelo
« Respuesta #6 en: 05 de Agosto de 2016, 16:54:10 »
El tema de los algoritmos te llevaría a tratar:

https://es.wikipedia.org/wiki/M%C3%A1quina_de_Turing
https://es.wikipedia.org/wiki/Teor%C3%ADa_de_la_complejidad_computacional
https://es.wikipedia.org/wiki/An%C3%A1lisis_de_algoritmos
https://es.wikipedia.org/wiki/Teor%C3%ADa_de_la_computabilidad
https://es.wikipedia.org/wiki/N%C3%BAmero_computable
https://es.wikipedia.org/wiki/Recursi%C3%B3n

Son temas casi matemáticos y creo que un poco alejados (por ser muy teóricos) de lo que finalmente es la programación.
Creo que estos temas es mejor tratarles después de saber programar y no al revés.

Saludos.

Desconectado KILLERJC

  • Colaborador
  • DsPIC33
  • *****
  • Mensajes: 8242
Re:Dudas sobre algoritmo paralelo
« Respuesta #7 en: 05 de Agosto de 2016, 17:01:04 »
Citar
Creo que estos temas es mejor tratarles después de saber programar y no al revés.

Eso pense yo cuando lei esto:

Citar
Muchas gracias, analizando sus respuestas, deseo redactar un artículo dirigido a personas que desean entrar en el tema de la programación computacional, voy a intentar transmitir algunos conceptos básicos y de fácil entendimiento ya que hay artículos o material técnico difícil de comprender en los libros y en la web.

Pensaba que para lograr adecuadamente ese objetivo es necesario conocer del tema. Por eso mismo yo no me extendi demasiado, tengo poco conocimiento del mismo, se de los problemas, se de lo puso Picuino por que a veces lo toque, pero no poseo demasiada experiencia como para desarrollar un gran texto

Desconectado Picuino

  • Moderadores
  • DsPIC33
  • *****
  • Mensajes: 5878
    • Picuino
Re:Dudas sobre algoritmo paralelo
« Respuesta #8 en: 06 de Agosto de 2016, 03:08:15 »
Yo empezaría con algo parecido a estos cursos:
https://studio.code.org/

https://studio.code.org/s/course3
Funciones, variables, condiciones, bucles, depuración, etc.