Prevedere il tempo di esecuzione del loop parallelo utilizzando la stima a priori dello sforzo per Itand (per il numero di lavoratori)

Question

Sto lavorando a un'implementazione MATLAB di una moltiplicazione adattiva per vettori di matrice per matrici scarse molto grandi provenienti da una particolare discretizzazione di una PDE (con una struttura di scarsità nota).

Dopo un sacco di pre-elaborazione, finisco con un numero di blocchi diversi (maggiore di, diciamo, 200), per i quali voglio calcolare le voci selezionate.

Uno dei passaggi di pre-elaborazione è determinare le voci (numero di) per blocco che voglio calcolare, il che mi dà una misura quasi perfetta della quantità di tempo che ogni blocco prenderà (a tutti gli effetti, lo sforzo della quadratura è il lo stesso per ogni voce).

Grazie a https://stackoverflow.com/a/9938666/2965879, Sono stato in grado di sfruttarlo ordinando i blocchi in ordine inverso, spingendo così Matlab a iniziare con i più grandi prima.

Tuttavia, il numero di voci differisce in modo così selvaggio da un blocco a blocco, che l'esecuzione diretta di PARFOR è limitato gravemente dai blocchi con il maggior numero di voci, anche se vengono alimentate nel ciclo al contrario.

La mia soluzione è quella di fare i blocchi più grandi in serie (ma parallelamente al livello delle voci!), Il che va bene fintanto che il sovraccarico per Itarand non ha importanza troppo, resp. I blocchi non diventano troppo piccoli. Il resto dei blocchi che faccio quindi con Parfor. Idealmente, lasciare che Matlab decidesse come gestirlo, ma poiché un Parfor-Loop nidificato perde il suo parallelismo, questo non funziona. Inoltre, l'imballaggio entrambi i loop in uno è (quasi) impossibile.

La mia domanda ora è su come determinare al meglio questo taglio tra il regime seriale e parallelo, tenendo conto delle informazioni che ho sul numero di voci (la forma della curva delle voci ordinate può differire per diversi problemi), come così come il numero di lavoratori che ho a disposizione.

Finora, avevo lavorato con i 12 lavoratori disponibili con una licenza PCT standard, ma da quando ora ho iniziato a lavorare su un cluster, determinando questo cut-off diventa sempre più cruciale (poiché per molti core il sovraccarico del Il ciclo seriale diventa sempre più costoso rispetto al ciclo parallelo, ma allo stesso modo, avere blocchi che reggono il resto sono ancora più costosi).

Per 12 core (resp. La configurazione del server di calcolo con cui stavo lavorando), avevo capito un parametro ragionevole di 100 voci per lavoratore come tagliato, ma questo non funziona bene quando il numero di core non è Piccolo più in relazione al numero di blocchi (ad es. 64 vs 200).

Ho provato a sgonfiare il numero di core con diversi poteri (ad esempio 1/2, 3/4), ma anche questo non funziona in modo coerente. Successivamente ho provato a raggruppare i blocchi in lotti e determinare il taglio quando le voci sono più grandi della media per lotto, resp. Il numero di lotti che sono lontani dalla fine:

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: questo codice non funziona per i vettori num_entr_asc la cui lunghezza non è un multiplo di num_core, ma ho deciso di omettere il min(...,end) costruzioni per leggibilità.)

Ho anche omesso il < max(...,...) Per combinare entrambe le condizioni (cioè insieme a voci minime per lavoratore), il che è necessario in modo che il cut-off non venga trovato troppo presto. Ho pensato un po 'anche ad usare anche la varianza, ma finora tutti i tentativi sono stati insoddisfacenti.

Sarei molto grato se qualcuno ha una buona idea su come risolverlo.

Answer 1

Ho trovato una soluzione un po 'soddisfacente, quindi nel caso in cui qualcuno fosse interessato a condividerla. Apprezzerei ancora i commenti su come migliorare/perfezionare l'approccio.

Fondamentalmente, ho deciso che l'unico modo ragionevole è quello di costruire un (molto) modello rudimentale dello scheduler per il ciclo parallelo:

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

Il parametro cost_it Per un'iterazione vuota è una miscela grezza di molti diversi effetti collaterali, che potrebbe essere separata: il costo di un'iterazione vuota in un for/parfor-loop (potrebbe anche essere diverso per blocco), nonché il tempo di avvio resp. trasmissione dei dati del parfor-loop (e probabilmente altro). Il mio motivo principale per mettere insieme tutto è che non voglio stimare/determinare i costi più granulari.

Uso la routine sopra per determinare il cut-off nel modo seguente:

% 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

In particolare, non gonfia/cambio il valore di est_cost_para che presuppone (a parte cost_it) la pianificazione più ottimistica possibile. Lo lascio come è principalmente perché non so cosa funzionerebbe meglio. Per essere conservativi (cioè evitare di nutrire blocchi troppo grandi al ciclo parallelo), si potrebbe ovviamente aggiungere una certa percentuale come tampone o persino usare una potenza> 1 per gonfiare il costo parallelo.

Nota anche quello est_cost_para viene chiamato con successive meno blocchi (anche se uso il nome variabile cost_blocks Per entrambe le routine, uno è un sottoinsieme dell'altro).

Rispetto all'approccio nella mia vercida domanda vedo due vantaggi principali:

1. La dipendenza relativamente intricata tra i dati (sia il numero di blocchi che il loro costo) e il numero di core viene catturata molto meglio con lo scheduler simulato di quanto sarebbe possibile con una singola formula.
2. Calcolando il costo per tutte le possibili combinazioni di distribuzione seriale/parallela e quindi prendendo il minimo, non si può essere "bloccati" troppo presto durante la lettura nei dati da un lato (ad es. Da un salto che è grande rispetto ai dati finora, ma piccolo rispetto al totale).

Naturalmente, la complessità asintotica è più alta chiamando est_cost_para con il suo amato tutto il tempo, ma nel mio caso (num_blocks<500) questo è assolutamente trascurabile.

Infine, se un valore decente di cost_it non si presenta prontamente, si può provare a calcolarlo misurando il tempo di esecuzione effettivo di ciascun blocco, nonché la parte puramente parallela di esso, e quindi cercando di adattarsi ai dati risultanti alla previsione dei costi e ottenere un valore aggiornato di cost_it Per la prossima chiamata della routine (usando la differenza tra costo totale e costo parallelo o inserendo un costo di zero nella formula montata). Questo dovrebbe sperare di "convergere" al valore più utile di cost_it per il problema in questione.