¿Cómo puedo paralelizar un algoritmo en una máquina con múltiples procesadores?

Question

• Intel Core2Duo, por ejemplo, se supone que tiene un solo troquel pero dos núcleos.

• Por lo tanto, debería ser posible controlar qué se procesa en qué núcleo, lo que significa que es posible indicar a mi algoritmo que use los dos núcleos en paralelo.

La pregunta es ¿cómo?

¿Necesito bajar al nivel del núcleo para hacer esto, o hay una manera más simple? Para ser más concretos, ¿qué se necesita para implementar un dual-core-merge-sort?

Answer 1

A juzgar por sus preguntas anteriores, diría que está buscando implementar en C/C++, pero creo que la respuesta es más o menos la misma, independientemente del idioma.

Si desea paralelizar cualquier operación, hágalo multiproceso. Puede tener tantos hilos paralelos y concurrentes como núcleos.

Aquí hay una pregunta relacionada: How to implement divide and conquer algorithms in C# using multithreading?

Según tengo entendido, la unión de un hilo en particular a un núcleo o procesador se llama processor affinity. En general, no es una buena idea, porque el propósito del sistema operativo es hacer malabares con los hilos entre los procesadores. Es poco probable que haga un mejor trabajo de esto que el sistema operativo.

Answer 2

Espero que esté buscando la asignación de hilos a cada uno de los núcleos .. Esta es una descripción detallada de lo que se puede hacer y cómo hacerlo.

Processor affinity

Espero que esto ayude.

Answer 3

A Specimen of Parallel Programming: Parallel Merge Sort Implementation. Y aquí hay uno en Erlang. Para respuestas más precisas, tienes que hacer una pregunta más precisa.

Answer 4

Para implementar un algoritmo que aprovecha múltiples núcleos, considere OpenMP.

Por supuesto, los algoritmos que tienen fuertes dependencias de datos pueden no paralelizarse bien.

Answer 5

Depende del lenguaje de programación que desee lograr. Por ejemplo para:

• Python - utilizar multiprocessing o parallel python lib.

• C# /. NET - use parallel framework para multi-core aplicaciones.

• nuevoLISP - simplemente use spawn()/other stuff para el mismo objetivo.

• C - se puede utilizar POSIX threads y tal

• etc., etc., etc ....

Simplemente elija el idioma y busque capacidades de procesamiento paralelo en ese idioma.

¡Buena suerte!

Answer 6

Si bien los hilos POSIX (pthreads) son probablemente una buena idea para comenzar, esto no es exclusivo.

El subprocesamiento múltiple en C no es realmente trivial, por lo tanto, aconsejaría fork().

inicie una horquilla de trabajador para cada CPU con una subsección de su algoritmo mergesort, y luego vuelva a montarlos en la bifurcación del administrador.

Al trabajar para una solución en paralelo, considero las horquillas antes de las roscas, ya que son más fáciles de implementar y se obtiene un resultado preliminar rápido. Una vez que funcione, es posible que desee tomarse un tiempo y trabajar con pthreads.