Prevendo o tempo de execução do loop paralelo usando a estimativa A-Priori de esforço por iterrand (para determinado número de trabalhadores)

Question

Estou trabalhando em uma implementação do MATLAB de uma multiplicação adaptativa de vetor de matriz para matrizes esparsas muito grandes provenientes de uma discretização específica de um PDE (com estrutura de escassez conhecida).

Depois de muito pré-processamento, acabo com vários blocos diferentes (maiores que, digamos, 200), para os quais quero calcular entradas selecionadas.

Uma das etapas de pré-processamento é determinar o (número de) entradas por bloco que quero calcular, o que me dá uma medida quase perfeita da quantidade de tempo que cada bloco levará (para todos os efeitos e propósitos, o esforço da quadratura é o o mesmo para cada entrada).

Graças a https://stackoverflow.com/a/9938666/2965879, Pude fazer uso disso pedindo os blocos em ordem inversa, levando assim o Matlab a começar com os maiores primeiro.

No entanto, o número de entradas difere tão descontroladamente de bloco para bloco, que a execução diretamente do Parfor é limitada severamente pelos blocos com o maior número de entradas, mesmo que sejam alimentadas no loop ao contrário.

Minha solução é fazer os maiores blocos em série (mas paralelados no nível das entradas!), O que é bom, desde que a sobrecarga por iterand não importa muito, resp. Os blocos não ficam muito pequenos. O restante dos blocos que faço com o Parfor. Idealmente, eu deixaria o Matlab decidir como lidar com isso, mas como um loop parforfor-aninhado perde seu paralelismo, isso não funciona. Além disso, empacotar ambos os loops em um é (quase) impossível.

Minha pergunta agora é sobre como determinar melhor esse corte entre a série e o regime paralelo, levando em consideração as informações que tenho sobre o número de entradas (a forma da curva de entradas ordenadas pode diferir para diferentes problemas), pois bem como o número de trabalhadores que tenho disponível.

Até agora, eu trabalhava com os 12 trabalhadores disponíveis em uma licença PCT padrão, mas desde que comecei a trabalhar em um cluster, determinar esse corte se torna cada vez mais crucial (já que, para muitos núcleos, a sobrecarga do O loop em série se torna cada vez mais caro em comparação com o loop paralelo, mas da mesma forma, ter blocos que sustentam o resto são ainda mais caros).

Para 12 núcleos (resp. A configuração do servidor de computação com quem eu estava trabalhando), eu tinha descoberto um parâmetro razoável de 100 entradas por trabalhador como um corte, mas isso não funciona bem quando o número de núcleos não é pequeno mais em relação ao número de blocos (por exemplo, 64 vs 200).

Eu tentei esvaziar o número de núcleos com diferentes poderes (por exemplo, 1/2, 3/4), mas isso também não funciona de forma consistente. Em seguida, tentei agrupar os blocos em lotes e determinar o corte quando as entradas são maiores que a média por lote, resp. O número de lotes que estão longe do 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 não funciona para vetores num_entr_asc cujo comprimento não é um múltiplo de num_core, mas eu decidi omitir o min(...,end) construções para legibilidade.)

Eu também omiti o < max(...,...) Para combinar as duas condições (ou seja, junto com entradas mínimas por trabalhador), o que é necessário para que o corte não seja encontrado muito cedo. Eu pensei um pouco sobre o uso de uma variação também, mas até agora todas as tentativas foram insatisfatórias.

Eu ficaria muito grato se alguém tiver uma boa idéia de como resolver isso.

Answer 1

Cheguei a uma solução um tanto satisfatória, então, caso alguém esteja interessado, pensei em compartilhá -la. Eu ainda apreciaria comentários sobre como melhorar/ajustar a abordagem.

Basicamente, decidi que a única maneira sensata é construir um modelo (muito) rudimentar do agendador para o loop 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

O parâmetro cost_it pois uma iteração vazia é uma mistura bruta de muitos efeitos colaterais diferentes, que podem ser considerados separados: o custo de uma iteração vazia em um for/parfor-loop (também pode ser diferente por bloco), bem como o tempo de inicialização resp. transmissão de dados do parfor-loop (e provavelmente mais). Meu principal motivo para juntar tudo é que não quero estimar/determinar os custos mais granulares.

Eu uso a rotina acima para determinar o corte da seguinte maneira:

% 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

Em particular, não inflar/altero o valor de est_cost_para que assume (além de cost_it) a programação mais otimista possível. Deixo como é principalmente porque não sei o que funcionaria melhor. Para ser conservador (ou seja, evite alimentar blocos muito grandes para o loop paralelo), é claro que pode -se adicionar alguma porcentagem como buffer ou até usar uma potência> 1 para inflar o custo paralelo.

Observe também isso est_cost_para é chamado com blocos sucessivamente menos (embora eu use o nome da variável cost_blocks Para ambas as rotinas, uma é um subconjunto do outro).

Comparado à abordagem em minha pergunta prolongada, vejo duas vantagens principais:

1. A dependência relativamente complexa entre os dados (tanto o número de blocos quanto o custo) e o número de núcleos é capturado muito melhor com o agendador simulado do que seria possível com uma única fórmula.
2. Ao calcular o custo de todas as combinações possíveis de distribuição serial/paralela e depois tomar o mínimo, não se pode ficar "preso" muito cedo enquanto lê os dados de um lado (por exemplo, um salto que é grande em relação aos dados até agora, mas pequeno em comparação com o total).

Obviamente, a complexidade assintótica é maior chamando est_cost_para com seu loop enquanto o tempo todo, mas no meu caso (num_blocks<500) Isso é absolutamente insignificante.

Finalmente, se um valor decente de cost_it Não se apresenta prontamente, pode -se tentar calculá -lo medindo o tempo de execução real de cada bloco, bem como a parte puramente paralela dele, e depois tentando ajustar os dados resultantes à previsão de custos e obter um valor atualizado de cost_it Para a próxima chamada da rotina (usando a diferença entre custo total e custo paralelo ou inserindo um custo de zero na fórmula ajustada). Esperamos que isso "converja" para o valor mais útil de cost_it Para o problema em questão.