Este esquema implementa una versión paralela de Sieve of Eratosthenes.
Utiliza un conjunto de números candidatos n con valor máximo m, y una matriz tamaño-m que contiene datos de primalidad, indexados por el número candidato, cuyo espacio contiene “verdadero / falso / desconocido”. Inicialmente, todas las ranuras de la matriz están configuradas en “desconocido”.
También utiliza un grupo de subprocesos, con un número de subprocesos igual a 2 veces el número de CPU.
- ¿Cuáles son algunos ejemplos de informática, matemáticas o algoritmos donde se aplica el problema de detención?
- ¿Cómo podemos demostrar que una curva de Bezier es un caso específico de una curva B-spline por la definición de B-splines?
- ¿Cómo verificamos la inexistencia de un camino hamiltoniano?
- ¿Por qué los maestros programadores insisten en usar las matemáticas para enseñar a sus estudiantes los conceptos básicos de la programación dado que no se usa tanto a diario?
- No estoy interesado en los cursos de cálculo y matemáticas, ¿CS CS es la opción correcta?
El bucle principal genera valores candidatos (n); comienza un hilo computacional con cada valor candidato. El subproceso computacional intenta factorizar su valor candidato por cualquier medio que desee (podría intentar valores divisores para ranuras de matriz i <n (mejor: i <sqrt (n)) que están marcadas como "verdaderas", haciendo un bucle en valores "desconocidos" [dándose cuenta de la versión de un pobre hombre de un valor "futuro"]). Para cada hilo computacional, el bucle principal también lanza otro hilo, dada la ID del hilo computacional para esperar un temporizador de 1 segundo.
Si el subproceso computacional determina un resultado, actualiza su ranura de matriz correspondiente, aborta el subproceso de un segundo y vuelve a colocar ambos subprocesos en el grupo. Si el subproceso del temporizador de un segundo se activa, simplemente aborta su subproceso computacional correspondiente y se coloca el hilo computacional en el grupo.
Un bit complicado es saber si el hilo computacional está abortando el segundo hilo o viceversa; no puedes hacer que ambos se aborten en el mismo instante. Para manejar esto, agregamos una variable de bloqueo paralelo para cada índice que ambos hilos intentan adquirir antes de abortar el otro hilo.
Un segundo bit complicado es asegurarse de que el almacenamiento utilizado por cada hilo no se pierda en un aborto; para un cálculo tan simple como factorizar primos, es probable que no necesite ninguna asignación de almacenamiento dinámico, y las variables locales probablemente estén en una “gran pila contigua” propiedad del subproceso y, por lo tanto, se reciclarán cuando el subproceso se recicle.
Una vez que el bucle principal ha generado todos los valores, espera a que el grupo de subprocesos se vuelva a llenar a su capacidad máxima. La matriz contiene las respuestas.
Todo esto supone actualizaciones de ranuras de matriz atómica (típicas del hardware moderno) y un sistema operativo (o su código) que proporciona operaciones para start-thread-from-pool, temporizadores basados en hilos específicos, bloqueos para hilos y un comando de aborto de hilos. La mayoría de los sistemas operativos tienen todas estas primitivas disponibles.
Los detalles de codificación para C se dejan al lector.
Dudo que esto sea eficiente para pequeños m. Es probable que el esfuerzo para lanzar un hilo desde el grupo sea bastante alto. Para grandes m, el costo de factorizar podría dominar los tiempos de lanzamiento de subprocesos, por lo que podría ser eficiente allí. Dado un valor máximo de m = 2 ^ 32, la factorización debe intentar ingenuamente los valores de sqrt (2 ^ 32) ~~ 2 ^ 16 a 10 ns por división (velocidades de hardware típicas hoy) que dan 650K ns o .0065 segundos de trabajo computacional, lo que significa los temporizadores de 1 segundo nunca se activan, por lo que es mejor que los omita. Claramente no quieres establecer m = 2 ^ 64; Su matriz será increíblemente grande.
Solo por diversión … en nuestro lenguaje paralelo, PARLANSE, sin los temporizadores de 1 segundo, esto se ve así:
(definir principal
(acción (procedimiento nulo)
(local (;; [is_prime (array (evento booleano) 1 dinámico)]
(= [máx. natural] 123456789)
[equipo de trabajadores]
) ;;
(resize is_prime 1 max) resize; tenga en cuenta que los pares de apertura y cierre pueden tener “color”
(do (= [n natural] 1) max 1; enumerar valores para intentar
(consumir (reclutar trabajadores; agregar nuevos trabajadores al equipo de trabajadores
(acción (procedimiento [candidato natural]); la acción es como lambda sin valor
(hacer [divisor natural] 1 (- m 1) 1; enumerar divisores
(ifthen (&& isprime: divisor_index
(== (módulo candidato divisor) 0)
) &&
(;; (= is_prime: candidato ~ f); señales de disponibilidad
(regreso) ; divisible -> no es primo
) ;;
) ifthen
)hacer
(= is_prime: candidato ~ t); no divisible por ninguno -> primo
)acción
norte
)consumir
)hacer
(espera (trabajadores del evento)); espera a que todos los miembros del equipo completen
)local
)acción
)definir
La sintaxis es obviamente similar a Lisp, pero no es Lisp. La matriz es una matriz de “futuros” (llamados “eventos”) en PARLANSE), todos inicialmente armados como “aún no ha llegado ningún valor”. La asignación de is_prime: candidato señala el evento; cualquier lector de un evento está obligado a esperar hasta se ha señalado. La acción “reclutar” es donde ocurre el paralelismo; se lanza un grano de cómputo que consiste en la acción interna (un procedimiento con un argumento entero positivo) en cada valor candidato. Cada grano candidato se “recluta” (agregado) Nota: el equipo actúa como un límite natural en la computación paralela; PARLANSE genera suficientes reclutas para mantener a los procesadores más que ocupados, y luego invierte en la ejecución de los reclutas existentes.
