Multiprocesamiento de Python: entendiendo la lógica detrás de `chunksize`

¿Qué factores determinan un argumento de chunksize óptimo para métodos como multiprocessing.Pool.map() ? El método .map() parece utilizar una heurística arbitraria para su tamaño predeterminado (se explica a continuación); ¿Qué motiva esa elección y hay un enfoque más reflexivo basado en alguna situación / configuración particular?

Ejemplo – decir que soy:

  • Pasar un iterable a .map() que tiene ~ 15 millones de elementos;
  • Trabajando en una máquina con 24 núcleos y utilizando los processes = os.cpu_count() predeterminados processes = os.cpu_count() dentro de multiprocessing.Pool() .

Mi ingenua idea es darles a cada uno de los 24 trabajadores una porción del mismo tamaño, es decir, 15_000_000 / 24 o 625,000. Los trozos grandes deberían reducir la rotación / gastos generales al tiempo que utilizan a todos los trabajadores. Pero parece que a esto le faltan algunos inconvenientes potenciales de entregar lotes grandes a cada trabajador. ¿Es esta una imagen incompleta, y qué me estoy perdiendo?


Parte de mi pregunta proviene de la lógica predeterminada de si chunksize=None : tanto .map() como .starmap() llaman a .map_async() , que tiene este aspecto:

 def _map_async(self, func, iterable, mapper, chunksize=None, callback=None, error_callback=None): # ... (materialize `iterable` to list if it's an iterator) if chunksize is None: chunksize, extra = divmod(len(iterable), len(self._pool) * 4) # ???? if extra: chunksize += 1 if len(iterable) == 0: chunksize = 0 

¿Cuál es la lógica detrás de divmod(len(iterable), len(self._pool) * 4) ? Esto implica que el tamaño del trozo estará más cerca de 15_000_000 / (24 * 4) == 156_250 . ¿Cuál es la intención al multiplicar len(self._pool) por 4?

Esto hace que el tamaño resultante sea un factor 4 más pequeño que mi “lógica ingenua” desde arriba, que consiste en simplemente dividir la longitud del iterable por el número de trabajadores en pool._pool .

Por último, también hay un fragmento de los documentos de Python en .imap() que impulsa aún más mi curiosidad:

El argumento chunksize es el mismo que el utilizado por el método map() . Por mucho tiempo, los iterables que usan un gran valor para chunksize pueden hacer que el trabajo se complete mucho más rápido que usar el valor predeterminado de 1.


Respuesta relacionada que es útil pero un nivel demasiado alto: multiprocesamiento de Python: ¿por qué los bloques grandes son más lentos? .

Respuesta corta

El algoritmo de tamaño de Pool es una heurística. Proporciona una solución simple para todos los escenarios de problemas imaginables que intenta incluir en los métodos de Pool. Como consecuencia, no se puede optimizar para ningún escenario específico .

El algoritmo divide arbitrariamente lo iterable en aproximadamente cuatro veces más trozos que el enfoque ingenuo. Más trozos significan más sobrecarga, pero mayor flexibilidad de progtwigción. Como se mostrará esta respuesta, esto conduce a una mayor utilización de los trabajadores en promedio, pero sin la garantía de un tiempo de cómputo general más corto para cada caso.

“Es bueno saberlo”, podría pensar, “pero, ¿cómo me ayuda esto con mis problemas concretos de multiprocesamiento?” Bueno, no es así. La respuesta corta más honesta es: “no hay una respuesta corta”, “el multiprocesamiento es complejo” y “depende”. Un síntoma observado puede tener diferentes raíces, incluso para escenarios similares.

Esta respuesta trata de proporcionarle conceptos básicos que lo ayudan a obtener una imagen más clara de la caja negra de progtwigción de Pool. También trata de brindarle algunas herramientas básicas para reconocer y evitar posibles acantilados en la medida en que estén relacionados con el tamaño de los trozos.

Sobre esta respuesta

Esta respuesta es trabajo en progreso.

Por nombrar algunas cosas que aún faltan:

  • Una sección de resumen.
  • Medidas para mejorar la legibilidad (corta)

Si no tiene que leerlo ahora, le recomiendo que lo omita para tener una idea de lo que puede esperar, pero posponga el trabajo hasta que estas líneas hayan sido eliminadas.

Actualización reciente (21 de febrero):

  • Externalicé el capítulo 7 en una respuesta por separado, porque me sorprendí con el límite de 30000 caracteres.
  • Se agregaron dos gifs en el capítulo 7, que muestran el algoritmo de chunksize de Pool y el ingenuo en acción

Es necesario aclarar algunos términos importantes primero.


1. Definiciones

Pedazo

Una parte aquí es una parte del argumento iterable especificado en una llamada de método de grupo. El tema de esta respuesta es cómo se calcula el tamaño del trozo y qué efectos puede tener esto.

Tarea

La representación física de una tarea en un proceso de trabajo en términos de datos se puede ver en la siguiente figura.

figura0

La figura muestra un ejemplo de llamada a pool.map() , que se muestra a lo largo de una línea de código, tomada de la función multiprocessing.pool.worker , donde se desempaqueta una tarea que se lee de la inqueue . worker es la función principal subyacente en MainThread de un pool-worker-process. El argumento func especificado en el método de agrupación solo coincidirá con la variable func dentro de la función worker para métodos de llamada única como apply_async y para imap con chunksize=1 . Para el rest de los métodos de agrupación con un chunksize la función de func procesamiento será una función de mapeador (mapstar o starmapstar). Esta función mapea el parámetro de func especificado por el usuario en cada elemento de la parte transmitida del iterable (-> “tareas de mapa”). El tiempo que esto lleva, define una tarea también como una unidad de trabajo .

Taskel

Si bien el uso de la palabra “tarea” para el procesamiento completo de un fragmento coincide con el código dentro de multiprocessing.pool , no hay ninguna indicación de cómo una sola llamada a la func especificada por el usuario, con un elemento del fragmento como argumento (s) ), debe ser referido. Para evitar confusiones que surjan de conflictos de nombres (piense en maxtasksperchild en el método __init__ de __init__ ), esta respuesta se referirá a las unidades de trabajo individuales dentro de una tarea como taskel .

Un taskel (de task + elemento ) es la unidad de trabajo más pequeña dentro de una tarea . Es la ejecución única de la función especificada con la func -parámetro de un método Pool agrupación, llamada con argumentos obtenidos de un solo elemento del fragmento transmitido. Una tarea consiste en tareas de chunksize grande .

Sobrecarga de paralelización (PO)

La PO consiste en la sobrecarga interna de Python y la sobrecarga para la comunicación entre procesos (IPC). La sobrecarga por tarea dentro de Python viene con el código necesario para empaquetar y desempaquetar las tareas y sus resultados. La sobrecarga de IPC viene con la sincronización necesaria de hilos y la copia de datos entre diferentes espacios de direcciones (se necesitan dos pasos de copia: padre -> cola -> hijo). La cantidad de sobrecarga de IPC depende del tamaño del sistema operativo, hardware y datos, lo que dificulta las generalizaciones sobre el impacto.


2. Metas de paralelización

Cuando se usa el multiprocesamiento, nuestro objective general (obviamente) es minimizar el tiempo total de procesamiento para todas las tareas. Para alcanzar este objective general, nuestro objective técnico debe ser optimizar la utilización de los recursos de hardware .

Algunos objectives secundarios importantes para lograr el objective técnico son:

  • minimizar la sobrecarga de paralelización (lo más famoso, pero no solo: IPC )
  • alta utilización en todos los cpu-cores
  • Mantener el uso de memoria limitado para evitar que el sistema operativo se pagine en exceso

Al principio, las tareas deben ser lo suficientemente pesadas (intensivas) desde el punto de vista informático, para recuperar el PO que tenemos que pagar por la paralelización. La relevancia de la PO disminuye a medida que aumenta el tiempo de cálculo absoluto por tarea. O, para decirlo de otra manera, cuanto mayor sea el tiempo de cálculo absoluto por tarea para su problema, menos relevante tendrá la necesidad de reducir la PO. Si su cálculo tomará horas por tarea, la sobrecarga de IPC será insignificante en comparación. La principal preocupación aquí es evitar los procesos de trabajo inactivos después de que se hayan distribuido todas las tareas. Manteniendo todos los núcleos cargados significa que estamos paralelizando tanto como sea posible.


3. Escenarios de paralelización

¿Qué factores determinan un argumento de tamaño óptimo para métodos como multiprocessing.Pool.map ()?

El factor principal en cuestión es cuánto tiempo de cálculo puede variar entre nuestras tareas individuales. Para nombrarlo, la elección de un tamaño óptimo se determina mediante …

Coeficiente de variación ( CV ) para tiempos de cálculo por tarea.

Los dos escenarios extremos en una escala, siguiendo el scope de esta variación, son:

  1. Todas las tareas necesitan exactamente el mismo tiempo de cálculo.
  2. Un taskel podría tardar segundos o días en terminar

Para una mejor memorización, me referiré a estos escenarios como:

  1. Escenario denso
  2. Escenario amplio

Otro factor determinante es el número de procesos de trabajo utilizados (respaldados por cpu-cores). Se aclarará más tarde por qué.

Escenario denso

En un escenario denso , sería conveniente distribuir todos los grupos de tareas a la vez, para mantener al mínimo el intercambio de contexto y el IPC necesarios. Esto significa que queremos crear solo tantos fragmentos, como procesos de trabajo hay. Como ya se indicó anteriormente, el peso de la OP aumenta con los tiempos de cómputo más pequeños por tarea.

Para un rendimiento máximo, también queremos que todos los procesos de trabajo estén ocupados hasta que se procesen todas las tareas (sin trabajadores inactivos). Para este objective, los trozos distribuidos deben ser del mismo tamaño o cerca.

Escenario amplio

El ejemplo principal para un escenario amplio sería un problema de optimización, en el que los resultados convergen rápidamente o el cálculo puede demorar horas, si no días. No es predecible qué combinación de “tareas ligeras” y “tareas pesadas” contendrá una tarea en tal caso, por lo tanto, no es aconsejable distribuir demasiadas tareas en un lote de tareas a la vez. Distribuir menos tareas al mismo tiempo de lo posible, significa boost la flexibilidad de progtwigción. Esto es necesario aquí para alcanzar nuestro objective secundario de alta utilización de todos los núcleos.

Si los métodos Pool agrupación, de forma predeterminada, estuvieran totalmente optimizados para el escenario denso, crearían cada vez menos tiempos óptimos para cada problema ubicado más cerca del escenario amplio.


4. Riesgos de Chunksize> 1

Considere este ejemplo de pseudocódigo simplificado de un Escenario amplio que se puede ejecutar, que queremos pasar a un método de agrupación:

 good_luck_iterable = [60, 60, 86400, 60, 86400, 60, 60, 84600] 

En lugar de los valores reales, pretendemos ver el tiempo de cálculo necesario en segundos, para simplificar solo 1 minuto o 1 día. Suponemos que el grupo tiene cuatro procesos de trabajo (en cuatro núcleos) y que el chunksize se establece en 2 . Debido a que se mantendrá la orden, los trozos que se envíen a los trabajadores serán estos:

 [(60, 60), (86400, 60), (86400, 60), (60, 84600)] 

Ya que tenemos suficientes trabajadores y el tiempo de cálculo es lo suficientemente alto, podemos decir que, en primer lugar, cada proceso de trabajo hará que una parte funcione. (Esto no tiene que ser el caso para completar tareas rápidamente). Además, podemos decir que todo el procesamiento tomará alrededor de 86400 + 60 segundos, porque ese es el tiempo de cómputo total más alto para una parte en este escenario artificial y distribuimos partes solo una vez.

Ahora considere este iterable, que solo tiene una posición cambiada en comparación con la anterior:

 bad_luck_iterable = [60, 60, 86400, 86400, 60, 60, 60, 84600] 

… y los trozos correspondientes:

 [(60, 60), (86400, 86400), (60, 60), (60, 84600)] 

¡Solo mala suerte con la clasificación de nuestro iterable casi el doble (86400 + 86400) nuestro tiempo total de procesamiento! El trabajador que recibe la pieza viciosa (86400, 86400) está impidiendo que la segunda tarea pesada en su tarea se distribuya a uno de los trabajadores inactivos que ya terminó con sus (60, 60) piezas. Obviamente, no nos arriesgaríamos a un resultado tan desagradable si establecemos chunksize=1 .

Este es el riesgo de tamaños más grandes. Con los tamaños más altos, cambiamos la flexibilidad de progtwigción por menos gastos generales y, en casos como el anterior, es un mal negocio.

Cómo veremos en el capítulo 6. La cuantificación de la eficiencia del algoritmo , los tamaños más grandes también pueden conducir a resultados subóptimos para los escenarios densos .


5. Algoritmo de tamaño de la piscina

A continuación encontrará una versión ligeramente modificada del algoritmo dentro del código fuente. Como puede ver, corté la parte inferior y la envolví en una función para calcular el argumento de chunksize externo. También reemplacé 4 con un parámetro factor y subcontraté las llamadas len() .

 # mp_utils.py def calc_chunksize(n_workers, len_iterable, factor=4): """Calculate chunksize argument for Pool-methods. Resembles source-code within `multiprocessing.pool.Pool._map_async`. """ chunksize, extra = divmod(len_iterable, n_workers * factor) if extra: chunksize += 1 return chunksize 

Para asegurarnos de que todos estemos en la misma página, esto es lo que hace divmod :

divmod(x, y) es una función incorporada que devuelve (x//y, x%y) . x // y es la división de piso, devolviendo el cociente redondeado hacia abajo desde x / y , mientras que x % y es la operación de módulo devolviendo el rest de x / y . Por lo tanto, por ejemplo, divmod(10, 3) devuelve (3, 1) .

Ahora, cuando vea chunksize, extra = divmod(len_iterable, n_workers * 4) , notará que n_workers aquí es el divisor y en x / y y multiplicación por 4 , sin más ajustes if extra: chunksize +=1 más adelante, lleva a un tamaño de pieza inicial al menos cuatro veces más pequeño (para len_iterable >= n_workers * 4 ) de lo que sería de otra manera.

Para ver el efecto de la multiplicación por 4 en el resultado de tamaño intermedio considere esta función:

 def compare_chunksizes(len_iterable, n_workers=4): """Calculate naive chunksize, Pool's stage-1 chunksize and the chunksize for Pool's complete algorithm. Return chunksizes and the real factors by which naive chunksizes are bigger. """ cs_naive = len_iterable // n_workers or 1 # naive approach cs_pool1 = len_iterable // (n_workers * 4) or 1 # incomplete pool algo. cs_pool2 = calc_chunksize(n_workers, len_iterable) real_factor_pool1 = cs_naive / cs_pool1 real_factor_pool2 = cs_naive / cs_pool2 return cs_naive, cs_pool1, cs_pool2, real_factor_pool1, real_factor_pool2 

La función anterior calcula el tamaño de los trozos ingenuo ( cs_naive ) y el primer paso del tamaño del algoritmo de tamaño de bloque de Pool ( cs_pool1 ), así como el tamaño del bloque completo para el algoritmo de Pool completo ( cs_pool2 ). Además, calcula los factores reales rf_pool1 = cs_naive / cs_pool1 y rf_pool2 = cs_naive / cs_pool2 , que nos dicen cuántas veces los tamaños calculados ingenuamente son más grandes que las versiones internas de Pool.

A continuación se muestran dos figuras creadas con la salida de esta función. La figura de la izquierda solo muestra los tamaños de n_workers=4 hasta una longitud iterable de 500 . La figura de la derecha muestra los valores para rf_pool1 . Para la longitud iterable 16 , el factor real se convierte en >=4 (para len_iterable >= n_workers * 4 ) y su valor máximo es 7 para las longitudes iterables 28-31 . Esa es una desviación masiva del factor original 4 al que converge el algoritmo para iterables más largos. ‘Más largo’ aquí es relativo y depende del número de trabajadores especificados.

Figura 1

Recuerde que chunksize cs_pool1 aún carece del ajuste extra con el rest de divmod contenido en cs_pool2 del algoritmo completo.

El algoritmo continúa con:

 if extra: chunksize += 1 

Ahora, en los casos en los que hay un rest (un extra de la operación divmod-operation), el aumento del tamaño de trozo en 1 obviamente no puede funcionar para cada tarea. Después de todo, si lo fuera, no habría un rest para empezar.

Como puede ver en las figuras a continuación, el ” tratamiento adicional ” tiene el efecto, que el factor real para rf_pool2 ahora converge hacia 4 desde debajo de 4 y la desviación es algo más suave. Desviación estándar para n_workers=4 y len_iterable=500 caídas desde 0.5233 para rf_pool1 a 0.4115 para rf_pool2 .

Figura 2

Finalmente, boost chunksize por 1 tiene el efecto, que la última tarea transmitida solo tiene un tamaño de len_iterable % chunksize or chunksize .

Sin embargo, cuanto más interesante y cómo veremos más adelante, más como consecuencia, se puede observar el efecto del tratamiento adicional para la cantidad de trozos generados ( n_chunks ). Durante el tiempo suficiente, el algoritmo de tamaño de trozos completado de Pool ( n_pool2 en la figura a continuación) estabilizará el número de trozos en n_chunks == n_workers * 4 . Por el contrario, el algoritmo ingenuo (después de un eructo inicial) sigue alternando entre n_chunks == n_workers y n_chunks == n_workers + 1 medida que n_chunks == n_workers + 1 la longitud del iterable.

figura 3

A continuación, encontrará dos funciones de información mejoradas para Pool’s y el ingenuo chunksize-algorithm. La salida de estas funciones será necesaria en el siguiente capítulo.

 # mp_utils.py from collections import namedtuple Chunkinfo = namedtuple( 'Chunkinfo', ['n_workers', 'len_iterable', 'n_chunks', 'chunksize', 'last_chunk'] ) def calc_chunksize_info(n_workers, len_iterable, factor=4): """Calculate chunksize numbers.""" chunksize, extra = divmod(len_iterable, n_workers * factor) if extra: chunksize += 1 # `+ (len_iterable % chunksize > 0)` exploits that `True == 1` n_chunks = len_iterable // chunksize + (len_iterable % chunksize > 0) # exploit `0 == False` last_chunk = len_iterable % chunksize or chunksize return Chunkinfo( n_workers, len_iterable, n_chunks, chunksize, last_chunk ) 

No se confunda con el aspecto probablemente inesperado de calc_naive_chunksize_info . El extra de divmod no se usa para calcular el tamaño del bloque.

 def calc_naive_chunksize_info(n_workers, len_iterable): """Calculate naive chunksize numbers.""" chunksize, extra = divmod(len_iterable, n_workers) if chunksize == 0: chunksize = 1 n_chunks = extra last_chunk = chunksize else: n_chunks = len_iterable // chunksize + (len_iterable % chunksize > 0) last_chunk = len_iterable % chunksize or chunksize return Chunkinfo( n_workers, len_iterable, n_chunks, chunksize, last_chunk ) 

6. Cuantificando la eficiencia del algoritmo

Ahora, después de ver cómo la salida del algoritmo de tamaño de Pool ve diferente en comparación con la salida del algoritmo ingenuo …

  • ¿Cómo saber si el enfoque de Pool realmente mejora algo?
  • ¿Y qué podría ser exactamente algo ?

Como se muestra en el capítulo anterior, para iterables más largos (un mayor número de tareas), el algoritmo de tamaño de bloque de Pool divide aproximadamente el iterable en cuatro veces más trozos que el método ingenuo. Los trozos más pequeños significan más tareas y más tareas significan más Sobrecarga de paralelización (PO), un costo que debe sopesarse con el beneficio de una mayor flexibilidad de progtwigción (recuérdese “Riesgos de tamaño de archivo> 1” ).

Por razones bastante obvias, el algoritmo básico de tamaño de Pool no puede comparar la flexibilidad de progtwigción con el PO para usted. La sobrecarga de IPC depende del tamaño del sistema operativo, hardware y datos. El algoritmo no puede saber en qué hardware ejecutamos nuestro código, ni tiene una idea de cuánto tardará en completarse una tarea. Es una heurística que proporciona una funcionalidad básica para todos los escenarios posibles. Esto significa que no se puede optimizar para ningún escenario en particular. Como se mencionó anteriormente, la PO también se vuelve cada vez menos preocupante con el aumento de los tiempos de cálculo por tarea (correlación negativa).

Cuando recuerdas los Objetivos de paralelización del capítulo 2, un punto fue:

  • alta utilización en todos los cpu-cores

Las personas que se preguntan acerca de los núcleos no utilizados / procesos de trabajo inactivos en situaciones en las que usted esperaría que todos los procesos de trabajadores estuvieran ocupados hacen una pregunta repetida sobre SO con respecto al multiprocessing.Pool .

La inactividad de los procesos de trabajadores hacia el final de nuestro cálculo es una observación que podemos realizar incluso con Escenarios densos (tiempos de cómputo totalmente iguales por tarea) en los casos en que el número de trabajadores no es un divisor del número de fragmentos ( n_chunks % n_workers > 0 ).

Un mayor número de trozos significa una mayor probabilidad de que el número de trabajadores sea un divisor para n_chunks , por lo tanto, la probabilidad de no observar a los trabajadores en n_chunks mejora en consecuencia.

Por las razones mencionadas anteriormente, el aspecto PO se mantiene completamente fuera del scope de las consideraciones teóricas sobre la medición de la eficiencia del algoritmo, al menos en un paso inicial. Como se mencionó anteriormente, el algoritmo de tamaño de Pool puede intentar mejorar es la minimización de los procesos de trabajo inactivos, respectivamente, la utilización de cpu-cores .

El valor que cuantifica la tasa de utilización del trabajador, me referiré como:

Eficiencia de paralelización (PE)

Nuestra condición original para una formalización del problema, el estado estable, es un escenario denso con tiempos de cómputo totalmente iguales por tarea. Cualquier otro escenario sería aleatorio / caos y no adecuado para una investigación de ceteris paribus . Otros factores de caos como la política de progtwigción de subprocesos del sistema operativo tampoco se tienen en cuenta.

Es importante tener en cuenta que la EP , en el sentido en que estoy usando el término aquí, no se correlaciona automáticamente con una computación general más rápida para un problema de paralelización dado. PE no nos dice si los trabajadores están productivamente ocupados, o si la mayor parte del tiempo se pierde en el manejo de gastos generales. Solo nos dice el porcentaje de utilización del trabajador en el sentido de una ausencia de trabajadores inactivos , y lo hace solo para nuestro modelo simplificado.


6.1 Eficiencia de paralelización absoluta (APE)

Mientras pensaba en cómo podría cuantificar una posible ventaja del algoritmo de tamaño de Pool sobre el ingenuo algoritmo de tamaño de chunks, imaginé una imagen de la progtwigción de trabajadores de Pool como se ve a continuación.

Figura 4

  • El eje x se divide en unidades de tiempo iguales, donde cada unidad representa el tiempo de cálculo que requiere una tarea.
  • El eje y se divide en el número de procesos de trabajo que utiliza el grupo.
  • Aquí se muestra un panel de tareas como el rectángulo de color cian más pequeño, puesto en una línea de tiempo (un progtwig) de un proceso de trabajo anónimo.
  • Una tarea es una o varias tareas en una línea de tiempo de trabajador resaltada continuamente con el mismo tono.
  • Las unidades de tiempo de inactividad se representan a través de azulejos de color rojo.
  • El horario paralelo se divide en secciones. La última sección es la sección de cola.

Los nombres de las partes compuestas se pueden ver en la siguiente imagen.

Figura 5

La eficiencia de la paralelización se calcula dividiendo la Participación ocupada en todo el potencial:

Eficiencia de paralelización absoluta (APE) = Compartir ocupado / Progtwigción paralela

Aquí está cómo se ve en el código:

 # mp_utils.py def calc_abs_pe(n_workers, len_iterable, n_chunks, chunksize, last_chunk): """Calculate absolute parallelization efficiency. `len_iterable` is not used, but contained to keep a consistent signature with `calc_rel_pe`. """ potential = ( ((n_chunks // n_workers + (n_chunks % n_workers > 1)) * chunksize) + (n_chunks % n_workers == 1) * last_chunk ) * n_workers n_full_chunks = n_chunks - (chunksize > last_chunk) taskels_in_regular_chunks = n_full_chunks * chunksize real = taskels_in_regular_chunks + (chunksize > last_chunk) * last_chunk abs_pe = real / potential return abs_pe 

Si no hay un recurso compartido inactivo , el recurso compartido ocupado será igual al horario paralelo , por lo tanto obtenemos un APE del 100%. En nuestro modelo simplificado, este es un escenario en el que todos los procesos disponibles estarán ocupados durante todo el tiempo necesario para procesar todas las tareas. En otras palabras, todo el trabajo se paraliza efectivamente al 100 por ciento.

Pero, ¿por qué sigo refiriéndome al PE como PE absoluto aquí?

Para comprenderlo, debemos considerar un posible caso para el tamaño de chunksize (cs) que garantice la máxima flexibilidad de progtwigción (también, la cantidad de Highlanders que puede haber. ¿Coincidencia?):

___________________________________ ~ UNO ~ ___________________________________

Si, por ejemplo, tenemos cuatro procesos de trabajo y 37 tareas, habrá trabajadores chunksize=1 incluso con chunksize=1 , solo porque n_workers=4 no es un divisor de 37. El rest de dividir n_workers=4 es 1. Este único El rest de tareas tendrán que ser procesadas por un solo trabajador, mientras que las tres restantes están inactivas.

Del mismo modo, todavía habrá un trabajador inactivo con 39 tareas, cómo se puede ver en la imagen a continuación.

figura 6

Cuando compara el Horario Paralelo superior para chunksize=1 con la versión de abajo para chunksize=3 , notará que el Horario Paralelo superior es más pequeño, la línea de tiempo en el eje x más corta. Ahora debería ser obvio, cómo los tamaños más grandes inesperadamente también pueden llevar a un aumento en los tiempos de cómputo en general, incluso para escenarios densos .

Pero, ¿por qué no solo usar la longitud del eje x para cálculos de eficiencia?

Porque la sobrecarga no está contenida en este modelo. Será diferente para ambos tamaños, por lo tanto, el eje x no es realmente directamente comparable. La sobrecarga aún puede llevar a un tiempo de cómputo total más largo, como se muestra en el caso 2 de la figura a continuación.

figura7


6.2 Eficiencia relativa de paralelización (RPE)

El valor de APE no contiene la información si es posible una mejor distribución de las tareas con el tamaño de chunksize establecido en 1. Mejor aún, esto significa un menor Idling Share .

Para obtener un valor de PE ajustado para el máximo posible de PE , debemos dividir el APE considerado a través del APE que obtenemos con chunksize=1 .

Eficiencia de paralelización relativa (RPE) = APE_cs_x / APE_cs_1

Aquí está cómo se ve en el código:

 # mp_utils.py def calc_rel_pe(n_workers, len_iterable, n_chunks, chunksize, last_chunk): """Calculate relative parallelization efficiency.""" abs_pe_cs1 = calc_abs_pe( n_workers, len_iterable, n_chunks=len_iterable, chunksize=1, last_chunk=1 ) abs_pe = calc_abs_pe( n_workers, len_iterable, n_chunks, chunksize, last_chunk ) rel_pe = abs_pe / abs_pe_cs1 return rel_pe 

RPE , como se define aquí, en esencia es una historia sobre la cola de un Horario Paralelo . RPE está influenciado por el tamaño máximo efectivo contenido en la cola. (Esta cola puede ser del chunksize eje x en chunksize o last_chunk .) Esto tiene la consecuencia, que el RPE converge naturalmente al 100% (par) para todo tipo de “looks de cola” como se muestra en la siguiente figura.

figura 8

Un RPE bajo …

  • Es un fuerte indicio del potencial de optimización.
  • naturalmente, se vuelve menos probable para los iterables más largos, porque la parte relativa de la cola del Progtwig paralelo general se reduce.

Encuentra la Parte II de esta respuesta aquí abajo .

Sobre esta respuesta

Esta respuesta es trabajo en progreso. Actualmente se trata como la Parte II de la respuesta aceptada anterior , porque me sorprendió el límite de 30000 caracteres que aparentemente tiene.


7. Naive vs algoritmo de tamaño de grupo

Antes de entrar en detalles, considera los dos gifs a continuación. Para un rango de diferentes longitudes iterable , muestran cómo los dos algoritmos comparados dividen el iterable pasado (será una secuencia para ese entonces) y cómo las tareas resultantes podrían distribuirse. El orden de los trabajadores es aleatorio y el número de tareas distribuidas por trabajador en realidad puede diferir de estas imágenes para tareas ligeras o tareas en un escenario amplio. Como se mencionó anteriormente, la sobrecarga tampoco se incluye aquí. Sin embargo, para cálculos lo suficientemente pesados ​​en un escenario denso con tamaños de datos transmitidos despreciables, los cálculos reales dibujan una imagen muy similar.

cs_4_50

cs_200_250

Como se muestra en el capítulo ” 5. Algoritmo de tamaño de bloque de Pool “, con el algoritmo de tamaño de bloque de Pool, el número de trozos se estabilizará en n_chunks == n_workers * 4 para iterables lo suficientemente grandes, mientras continúa cambiando entre n_chunks == n_workers y n_chunks == n_workers + 1 con el enfoque ingenuo. Para el algoritmo ingenuo, porque n_chunks % n_workers == 1 es True para n_chunks == n_workers + 1 , tiene el efecto dramático de que se creará una nueva sección donde solo se emplee un solo trabajador.

Algoritmo de tamaño de ingenuo:

Podría pensar que creó tareas en el mismo número de trabajadores, pero esto solo será cierto en los casos en que no haya ningún rest para len_iterable / n_workers . Si hay un rest, habrá una nueva sección con una sola tarea para un solo trabajador. En ese punto su computación ya no será paralela.

Abajo puede ver una figura similar a la que se muestra en el capítulo 5, pero que muestra la cantidad de secciones en lugar de la cantidad de partes. Para el algoritmo de tamaño completo de Pool ( n_pool2 ), n_sections se estabilizará en el infame factor 4 codificado. Para el algoritmo ingenuo, n_sections alternará entre uno y dos.

figura9

Para el algoritmo de tamaño de Pool, la estabilización en n_chunks = n_workers * 4 través del tratamiento adicional antes mencionado, evita la creación de una nueva sección aquí y mantiene el Idling Share limitado a un trabajador durante el tiempo suficiente. No solo eso, sino que el algoritmo seguirá reduciendo el tamaño relativo de la acción de ralentí , lo que lleva a un valor de RPE que converge hacia el 100%.

“Lo suficientemente largo” para n_workers=4 es len_iterable=210 por ejemplo. Para que sean iguales o mayores que eso, la participación de ralentí se limitará a un trabajador.

figura 10

El ingenuo algoritmo de tamaño también converge hacia el 100%, pero lo hace más lento. El efecto convergente depende únicamente del hecho de que la parte relativa de la cola se contrae en los casos en que habrá dos secciones. Esta cola con un solo trabajador empleado está limitada a la longitud del eje x n_workers - 1 , el rest máximo posible para len_iterable / n_workers .

¿En qué se diferencian los valores reales de RPE para el ingenuo y el algoritmo de tamaño de Pool?

A continuación encontrará dos mapas de calor que muestran los valores de RPE para todas las longitudes iterables hasta 5000, para todos los números de trabajadores desde 2 hasta 100. La escala de color va de 0,5 a 1 (50% -100%). Notará áreas mucho más oscuras (valores de RPE más bajos) para el algoritmo ingenuo en el mapa de calor izquierdo. Por el contrario, el algoritmo de tamaño de Pool genera una imagen mucho más shiny.

figura 11

El gradiente diagonal de las esquinas oscuras de la parte inferior izquierda frente a las esquinas shinys de la parte superior derecha muestra nuevamente la dependencia de la cantidad de trabajadores para lo que se denomina un “iterable largo”.

¿Qué tan malo puede ser con cada algoritmo?

Con el algoritmo de tamaño de Pool, un RPE de 81.25% es el valor más bajo para el rango de trabajadores y las longitudes iterables especificadas anteriormente:

figura12

Con el ingenuo algoritmo chunksize, las cosas pueden ponerse mucho peor. El RPE calculado más bajo aquí es 50.72%. En este caso, ¡casi la mitad del tiempo de cómputo solo se está ejecutando un trabajador! Así que, cuidado, orgullosos dueños de Knights Landing . 😉

figura 13


próximo: Notas finales

I think that part of what you’re missing is that your naive estimate assumes that each unit of work takes the same amount of time in which case your strategy would be the best. But if some jobs finish sooner than others then some cores may become idle waiting for the slow jobs to finish.

Thus, by breaking the chunks up into 4 times more pieces, then if one chunk finished early that core can start the next chunk ( while the other cores keep working on their slower chunk).

I don’t know why they picked the factor 4 exactly but it would be a trade off between minimising the overhead of the map code ( which wants the largest chunks possible) and balancing chunks taking different amount of times ( which wants the smallest chunk possible).