Caja de herramientas de computación paralela Matlab, asignación dinámica de trabajo en parfor loops

Question

Estoy trabajando con un ciclo de parfor de larga ejecución en matlab.

parfor iter=1:1000 
    chunk_of_work(iter); 
end 

Generalmente hay alrededor de 2-3 valores atípicos de temporización por ejecución. Es decir, por cada 1000 pedazos de trabajo realizados hay 2-3 que toman aproximadamente 100 veces más que el resto. A medida que el ciclo se completa, los trabajadores que evaluaron los valores atípicos continúan ejecutándose mientras que el resto de los trabajadores no tienen carga computacional.

Esto es coherente con el trabajo de distribución de bucles parfor estáticamente. Esto está en contraste con la documentación de la caja de herramientas de computación en paralelo found here:.

"Distribución del trabajo es dinámico En lugar de ser asignado un rango fijo iteración, los trabajadores se asignan una nueva iteración sólo después que terminar de procesar su iteración actual, que da como resultado una distribución de carga de trabajo incluso ".

¿Alguna idea de lo que está pasando?

Answer 1

Creo que el documento que cita tiene una descripción bastante buena de lo que se considera una asignación de trabajo estática: a cada trabajador "se le asigna un rango de iteración fijo". Para 4 trabajadores, esto significaría que a la primera se le asignó iter 1: 250, la segunda iter 251: 500, ... o la 1: 4: 100 para la primera, 2: 4: 1000 para la segunda y así sucesivamente.

No dijo exactamente lo que observa, pero lo que describe es coherente con la distribución dinámica de carga de trabajo: Primero, los cuatro (ejemplo) trabajadores trabajan en uno iter cada uno, el primero que termina trabaja en un quinto, el siguiente que está hecho (que bien puede ser lo mismo si tres de los primeros cuatro toman algo más de tiempo) funciona en un sexto, y así sucesivamente. Ahora bien, si sus valores atípicos son los números 20, 850 y 900 en el orden en que MATLAB elige procesar las iteraciones de bucle y cada uno toma 100 veces más, esto significa que las iteraciones 21 a 320 serán resueltas por tres de los cuatro trabajadores mientras que una ocupado con el vigésimo (por 320 se hará, ahora suponiendo una distribución más o menos uniforme del tiempo de cálculo no atípico). Sin embargo, el trabajador al que se le asignó la iteración número 850 continuará ejecutándose incluso después de que otro haya resuelto el n. ° 1000 y el mismo para el n. ° 900. De hecho, si hubo aproximadamente 1100 iteraciones, la que está trabajando en la # 900 debería terminarse aproximadamente en el momento en que las demás están.

[editado como la redacción original implicaba MATLAB todavía asignar las iteraciones del bucle parfor con el fin de 1 a 1000, que no debe ser asumida]

Así larga historia corta, a menos que encuentre una manera para procesar sus outliers primero (lo que por supuesto requiere que usted sepa a priori cuáles son los valores atípicos, y para encontrar una manera de hacer que MATLAB inicie el proceso de bucle paralelo), la distribución dinámica de carga de trabajo por sí sola no puede evitar el efecto que observa.

Adición: Creo, sin embargo, que su observación de que como "el bucle llega a su fin, el trabajador * s * que evalúan los valores atípicos siguen funcionando" parece implicar al menos una de las siguientes

1. los valores extremos de alguna manera se encuentran entre las últimas iteraciones MATLAB empieza a procesar
2. Usted tiene muchos trabajadores, en el orden de magnitud del número de iteraciones
3. su estimación del número de valores atípicos (2-3) o su estimación de su penalización de tiempo de cálculo (factor 100) es demasiado baja

Answer 2

La distribución del trabajo en PARFOR es algo determinista. Puede observar con precisión lo que está sucediendo haciendo que cada trabajador inicie sesión en el disco cómo van las cosas, pero básicamente resulta que PARFOR divide su ciclo en fragmentos de una manera determinista, pero los extiende dinámicamente. Desafortunadamente, actualmente no hay forma de controlar esa fragmentación.

Sin embargo, si no puede predecir cuáles de sus 1000 casos serán atípicos, es difícil imaginar un esquema eficiente para distribuir el trabajo.

Si puede predecir sus valores atípicos, puede aprovechar el hecho de que, en términos generales, PARFOR ejecuta iteraciones de bucle en orden inverso, por lo que podría ponerlas en el "final" del bucle para que el trabajo comience ellos de inmediato.

Answer 3

El problema que enfrenta está bien descrito en la respuesta de @arne.b, no tengo nada que agregar a eso.

Pero, la caja de herramientas de cómputo paralelo contiene funciones para descomponer un job into tasks para la ejecución independiente. A partir de su pregunta, no es posible concluir que esto sea adecuado o que no sea adecuado para su aplicación. Si lo es, la estrategia general es dividir el trabajo en tareas de algún tamaño y hacer que cada procesador aborde una tarea, cuando termine vuelva a la pila de tareas sin terminar y comience con otra.

Puede descomponer su problema de modo que una tarea reemplaza una iteración de bucle (muchas tareas, mucha sobrecarga en la administración del cálculo pero mejor equilibrio de carga) o una tarea reemplaza iteraciones de N bucle (menos tareas , menos sobrecarga, peor equilibrio de carga). Los trabajos y tareas son un poco más complicados de implementar que parfor también.

Answer 4

Como alternativa a PARFOR, en R2013b y posterior, puede usar PARFEVAL y dividir el trabajo como mejor le parezca. Incluso puede cancelar los 'valores atípicos de tiempo' una vez que obtenga suficientes resultados, si es apropiado. Por supuesto, hay una sobrecarga al dividir su bucle existente en 1000 llamadas PARFEVAL remotas individuales. Tal vez eso sea un problema, tal vez no. Aquí está el tipo de cosas que me estoy imaginando:

for idx = 1:1000 
    futures(idx) = parfeval(@chunk_of_work, 1, idx); 
end 
done = false; numComplete = 0; 
timer = tic(); 
while ~done 
    [idx, result] = fetchNext(futures, 10); % wait up to 10 seconds 
    if ~isempty(idx) 
     numComplete = numComplete + 1; 
     % stash result 
    end 
    done = (numComplete == 1000) || (toc(timer) > 100); 
end 
% cancel outstanding work, has no effect on completed futures 
cancel(futures);