Predicción del tiempo de ejecución del bucle paralelo utilizando la estimación de un esfuerzo A-Priori por iterand (para el número de trabajadores dado)

Question

Estoy trabajando en una implementación de MATLAB de una multiplicación adaptativa de vector matriz para matrices escasas muy grandes que provienen de una discretización particular de un PDE (con estructura de escasez conocida).

Después de mucho procesamiento previo, termino con varios bloques diferentes (más grande que, por ejemplo, 200), para los cuales quiero calcular las entradas seleccionadas.

Uno de los pasos de preprocesamiento es determinar el (número de) entradas por bloque que quiero calcular, lo que me da una medida casi perfecta de la cantidad de tiempo que llevará cada bloque (para todos los efectos, el esfuerzo de la cuadratura es el esfuerzo de la cuadratura es el esfuerzo de la cuadratura es el esfuerzo de la cuadratura. lo mismo para cada entrada).

Gracias a https://stackoverflow.com/a/9938666/2965879, Pude usar esto ordenando los bloques en orden inverso, incitando a Matlab para comenzar primero con los más grandes.

Sin embargo, el número de entradas difiere tan salvajemente de bloque a bloqueo, que la carrera directa se limita severamente por los bloques con el mayor número de entradas, incluso si se alimentan al bucle en reversa.

Mi solución es hacer los bloques más grandes en serie (¡pero paralelados en el nivel de entradas!), Lo cual está bien siempre que la sobrecarga por iterand no importa demasiado, resp. Los bloques no se vuelven demasiado pequeños. El resto de los bloques que hago con Parfor. Idealmente, dejaría que Matlab decida cómo manejar esto, pero dado que un parfor-loop anidado pierde su paralelismo, esto no funciona. Además, empaquetar ambos bucles en uno es (casi) imposible.

Mi pregunta ahora es sobre cómo determinar mejor este límite entre la serie y el régimen paralelo, teniendo en cuenta la información que tengo sobre el número de entradas (la forma de la curva de las entradas ordenadas puede diferir para diferentes problemas), como así como la cantidad de trabajadores que tengo disponibles.

Hasta ahora, había estado trabajando con los 12 trabajadores disponibles bajo la licencia PCT estándar, pero como ahora comencé a trabajar en un clúster, determinar este límite se vuelve cada vez más crucial (ya que para muchos núcleos la sobrecarga de la sobrecarga de la sobrecarga El bucle en serie se vuelve cada vez más costoso en comparación con el bucle paralelo, pero de manera similar, tener bloques que sostienen el resto son aún más costosos).

Para 12 núcleos (resp. La configuración del servidor de cómputo con el que estaba trabajando), había descubierto un parámetro razonable de 100 entradas por trabajador como un corte, pero esto no funciona bien cuando el número de núcleos no es pequeño ya en relación con el número de bloques (por ejemplo, 64 vs 200).

He tratado de desinflar el número de núcleos con diferentes poderes (por ejemplo, 1/2, 3/4), pero esto tampoco funciona de manera consistente. A continuación, intenté agrupar los bloques en lotes y determinar el corte cuando las entradas son más grandes que la media por lote, resp. El número de lotes que están lejos del final:

logical_sml = true(1,num_core); i = 0;
while all(logical_sml)
    i = i+1;
    m = mean(num_entr_asc(1:min(i*num_core,end))); % "asc" ~ ascending order 
    logical_sml = num_entr_asc(i*num_core+(1:num_core)) < i^(3/4)*m;  
        % if the small blocks were parallelised perfectly, i.e. all  
        % cores take the same time, the time would be proportional to  
        % i*m. To try to discount the different sizes (and imperfect  
        % parallelisation), we only scale with a power of i less than  
        % one to not end up with a few blocks which hold up the rest  
end  
num_block_big = num_block - (i+1)*num_core + sum(~logical_sml);

(Nota: este código no funciona para vectores num_entr_asc cuya longitud no es un múltiplo de num_core, pero decidí omitir el min(...,end) Construcciones para la legibilidad).

También he omitido el < max(...,...) Para combinar ambas condiciones (es decir, con entradas mínimas por trabajador), lo cual es necesario para que el corte no se encuentre demasiado temprano. Pensé un poco sobre el uso de la varianza también, pero hasta ahora todos los intentos han sido insatisfactorios.

Estaría muy agradecido si alguien tiene una buena idea sobre cómo resolver esto.

Answer 1

Se me ocurrieron una solución algo satisfactoria, por lo que en caso de que alguien esté interesado, pensé en compartirla. Todavía agradecería los comentarios sobre cómo mejorar/ajustar el enfoque.

Básicamente, decidí que la única forma sensata es construir un modelo (muy) rudimentario del planificador para el bucle paralelo:

function c=est_cost_para(cost_blocks,cost_it,num_cores)
% Estimate cost of parallel computation

% Inputs:
%   cost_blocks: Estimate of cost per block in arbitrary units. For
%       consistency with the other code this must be in the reverse order
%       that the scheduler is fed, i.e. cost should be ascending!
%   cost_it:     Base cost of iteration (regardless of number of entries)
%       in the same units as cost_blocks.
%   num_cores:   Number of cores
%
% Output:
%   c: Estimated cost of parallel computation

num_blocks=numel(cost_blocks);
c=zeros(num_cores,1);

i=min(num_blocks,num_cores);
c(1:i)=cost_blocks(end-i+1:end)+cost_it;
while i<num_blocks
    i=i+1;
    [~,i_min]=min(c); % which core finished first; is fed with next block
    c(i_min)=c(i_min)+cost_blocks(end-i+1)+cost_it;
end

c=max(c);

end

El parámetro cost_it porque una iteración vacía es una mezcla cruda de muchos efectos secundarios diferentes, que posiblemente podrían separarse: el costo de una iteración vacía en un for/parfor-Loop (también podría ser diferente por bloque), así como el tiempo de inicio resp. transmisión de datos del parfor-loop (y probablemente más). Mi razón principal para unir todo es que no quiero tener que estimar/determinar los costos más granulares.

Utilizo la rutina anterior para determinar el corte de la siguiente manera:

% function i=cutoff_ser_para(cost_blocks,cost_it,num_cores)
% Determine cut-off between serial an parallel regime

% Inputs:
%   cost_blocks: Estimate of cost per block in arbitrary units. For
%       consistency with the other code this must be in the reverse order
%       that the scheduler is fed, i.e. cost should be ascending!
%   cost_it:     Base cost of iteration (regardless of number of entries)
%       in the same units as cost_blocks.
%   num_cores:   Number of cores
%
% Output:
%   i: Number of blocks to be calculated serially

num_blocks=numel(cost_blocks);
cost=zeros(num_blocks+1,2);

for i=0:num_blocks
    cost(i+1,1)=sum(cost_blocks(end-i+1:end))/num_cores + i*cost_it;
    cost(i+1,2)=est_cost_para(cost_blocks(1:end-i),cost_it,num_cores);
end

[~,i]=min(sum(cost,2));
i=i-1;

end

En particular, no inflé/cambio el valor de est_cost_para que asume (aparte de cost_it) La programación más optimista posible. Lo dejo como es principalmente porque no sé qué funcionaría mejor. Para ser conservador (es decir, evite alimentar bloques demasiado grandes al bucle paralelo), uno podría agregar algún porcentaje como amortiguador o incluso usar una potencia> 1 para inflar el costo paralelo.

Tenga en cuenta también que est_cost_para se llama con sucesivamente menos bloques (aunque uso el nombre de la variable cost_blocks Para ambas rutinas, una es un subconjunto del otro).

En comparación con el enfoque en mi pregunta prolongada, veo dos ventajas principales:

1. La dependencia relativamente intrincada entre los datos (tanto el número de bloques como su costo) y el número de núcleos se capturan mucho mejor con el planificador simulado de lo posible con una sola fórmula.
2. Al calcular el costo de todas las combinaciones posibles de distribución en serie/paralela y luego tomar el mínimo, uno no puede "atascarse" demasiado temprano mientras lee en los datos de un lado (por ejemplo, por un salto que es grande en relación con los datos hasta ahora, pero pequeño en comparación con el total).

Por supuesto, la complejidad asintótica es mayor llamando est_cost_para con su bandeja todo el tiempo, pero en mi caso (num_blocks<500) Esto es absolutamente insignificante.

Finalmente, si un valor decente de cost_it no se presenta fácilmente, se puede tratar de calcularlo midiendo el tiempo de ejecución real de cada bloque, así como la parte puramente paralela, y luego tratando de ajustar los datos resultantes a la predicción de costos y obtener un valor actualizado de cost_it Para la siguiente llamada de la rutina (utilizando la diferencia entre el costo total y el costo paralelo o al insertar un costo de cero en la fórmula ajustada). Con suerte, esto debería "converger" al valor más útil de cost_it para el problema en cuestión.