matlab - ¿Ahorrando tiempo y memoria usando parfor?

optimization parallel-processing

Question

Considere prova.mat en MATLAB obtenido de la siguiente manera

for w=1:100
    for p=1:9    
        A{p}=randn(100,1); 
    end
    baseA_.A=A;

    eval([''baseA.A'' num2str(w) ''= baseA_;''])

end

save(sprintf(''prova.mat''),''-v7.3'', ''baseA'')

Para tener una idea de las dimensiones reales en mis datos, la 1x9 cell en A1 está compuesta por las siguientes 9 matrices: 904x5, 913x5, 1722x5, 4136x5, 9180x5, 3174x5, 5970x5, 4455x5, 340068x5 . Los otros Aj tienen una composición similar.

Considere el siguiente código

clear all
load prova
tic
parfor w=1:100
       indA=sprintf(''A%d'', w);
       Aarr=baseA.(indA).A;
       Boot=[];
       for p=1:9
           C=randn(100,1).*Aarr{p};
           Boot=[Boot; C];  
       end
       D{w}=Boot;
end
toc

Si ejecuto el bucle parfor con 4 trabajadores locales en mi Macbook Pro, me llevará 1,2 segundos. Reemplazar parfor con for toma 0.01 seg.

Con mis datos reales, la diferencia de tiempo es de 31 segundos frente a 7 segundos [la creación de la matriz C también es más complicada].

Si lo he entendido correctamente, el problema es que la computadora tiene que enviar la baseA a cada trabajador local y esto requiere tiempo y memoria.

¿Podría sugerir una solución que pueda hacer que parfor más conveniente que for ? Pensé que guardar todas las celdas en la baseA era una forma de ahorrar tiempo al cargar una vez al principio, pero tal vez me equivoque.

Answer 1

Corte los datos transmitidos en una matriz de celdas

El siguiente enfoque funciona para los datos que se agrupan en bucle . No importa cuál sea la variable de agrupación, siempre que se determine antes del ciclo. La ventaja de la velocidad es enorme.

Un ejemplo simplificado de tales data es el siguiente, con la primera columna que contiene una variable de agrupación:

ngroups = 1000;
nrows   = 1e6;
data    = [randi(ngroups,[nrows,1]), randn(nrows,1)];
data(1:5,:)
ans =
          620     -0.10696
          586      -1.1771
          625       2.2021
          858      0.86064
           78       1.7456

Ahora, suponga por simplicidad que estoy interesado en la sum() por grupo de los valores en la segunda columna. Puedo recorrer en grupo, indexar los elementos de interés y resumirlos. Realizaré esta tarea con un bucle for , un parfor simple y un parfor con datos parfor , y compararé los tiempos.

Tenga en cuenta que este es un ejemplo de juguete y no estoy interesado en soluciones alternativas como bsxfun() , este no es el punto del análisis.

Resultados

Tomando prestado el mismo tipo de trama de , primero confirmo los mismos hallazgos sobre parfor simple vs for . En segundo lugar, el método parfor supera por completo a ambos métodos en datos parfor , lo que lleva un poco más de 2 segundos en completarse en un conjunto de datos con 10 millones de filas (la operación de división se incluye en el tiempo). El parfor simple tarda 24s en completarse y casi el doble de esa cantidad de tiempo (estoy en Win7 64, R2016a e i5-3570 con 4 núcleos).

El punto principal de cortar los datos antes de comenzar el parfor es evitar:

• la sobrecarga de toda la información que se transmite a los trabajadores,
• operaciones de indexación en conjuntos de datos cada vez mayores.

El código

ngroups = 1000;
nrows   = 1e7;
data    = [randi(ngroups,[nrows,1]), randn(nrows,1)];

% Simple for
[out,t] = deal(NaN(ngroups,1));
overall = tic;
for ii = 1:ngroups
    tic
    idx     = data(:,1) == ii;
    out(ii) = sum(data(idx,2));
    t(ii)   = toc;
end
s.OverallFor = toc(overall);
s.TimeFor    = t;
s.OutFor     = out;

% Parfor
try parpool(4); catch, end
[out,t] = deal(NaN(ngroups,1));
overall = tic;
parfor ii = 1:ngroups
    tic
    idx     = data(:,1) == ii;
    out(ii) = sum(data(idx,2));
    t(ii)   = toc;
end
s.OverallParfor = toc(overall);
s.TimeParfor    = t;
s.OutParfor     = out;

% Sliced parfor
[out,t] = deal(NaN(ngroups,1));
overall = tic;
c       = cache2cell(data,data(:,1));
s.TimeDataSlicing = toc(overall);
parfor ii = 1:ngroups
    tic
    out(ii) = sum(c{ii}(:,2));
    t(ii)   = toc;
end
s.OverallParforSliced = toc(overall);
s.TimeParforSliced    = t;
s.OutParforSliced     = out;

x = 1:ngroups;
h = plot(x, s.TimeFor,''xb'',x,s.TimeParfor,''+r'',x,s.TimeParforSliced,''.g'');
set(h,''MarkerSize'',1)
title ''Time per iteration''
ylabel ''Time [s]''
xlabel ''Iteration number[-]'';
legend({sprintf(''for          : %5.2fs'',s.OverallFor),...
        sprintf(''parfor       : %5.2fs'',s.OverallParfor),...
        sprintf(''parfor_sliced: %5.2fs'',s.OverallParforSliced)},...
        ''interpreter'', ''none'',''fontname'',''courier'')

Puede encontrar cache2cell() en mi repositorio de github .

Simple para datos en rodajas

¿Se preguntará qué sucede si ejecutamos el simple for los datos cortados? Para este simple ejemplo de juguete, si eliminamos la operación de indexación cortando los datos, eliminamos el único cuello de botella del código, y el for realidad será un poco más rápido que el parfor .

Sin embargo, este es un ejemplo de juguete donde la operación de indexación toma completamente el costo del bucle interno. Por lo tanto, para que el parfor valga la pena, el bucle interno debe ser más complejo y / o extendido.

Ahorro de memoria con parfor en rodajas

Ahora, suponiendo que su ciclo interno sea más complejo y que el ciclo simple sea más lento, veamos cuánta memoria ahorramos evitando los datos transmitidos en parfor con 4 trabajadores y un conjunto de datos con 50 millones de filas (para aproximadamente 760 MB en RAM )

Como puede ver, se envían casi 3 GB de memoria adicional a los trabajadores. La operación de división necesita algo de memoria para completarse, pero aún mucho menos que la operación de transmisión y, en principio, puede sobrescribir el conjunto de datos inicial, por lo tanto, tiene un costo de RAM insignificante una vez completado. Finalmente, el parfor en los datos parfor solo usará una pequeña fracción de memoria, es decir, la cantidad que corresponde a los segmentos que se están utilizando.

Cortado en una celda

Los datos sin procesar se dividen en grupos y cada sección se almacena en una celda. Dado que una matriz de celdas es una matriz de referencias, básicamente dividimos los data contiguos en la memoria en bloques independientes.

Mientras que nuestros data muestra data veían así

data(1:5,:)
ans =
          620     -0.10696
          586      -1.1771
          625       2.2021
          858      0.86064
           78       1.7456

c rodajas parece

c(1:5)
ans = 
    [ 969x2 double]
    [ 970x2 double]
    [ 949x2 double]
    [ 986x2 double]
    [1013x2 double]

donde c{1} es

c{1}(1:5,:)
ans =
            1      0.58205
            1      0.80183
            1     -0.73783
            1      0.79723
            1       1.0414

Answer 2

Información general

Muchas funciones tienen múltiples subprocesos implícitos integrados , lo que hace que un bucle parfor no sea más eficiente, cuando se usan estas funciones, que un bucle for serie, ya que todos los núcleos ya se están utilizando. parfor realidad será un detrimento en este caso, ya que tiene la sobrecarga de asignación, mientras que es tan paralela como la función que está tratando de usar.

Cuando no se utiliza una de las funciones implícitamente multiproceso, parfor se recomienda básicamente en dos casos: muchas iteraciones en su ciclo (es decir, como 1e10 ), o si cada iteración lleva mucho tiempo (por ejemplo, eig(magic(1e4)) ) . En el segundo caso, es posible que desee considerar el uso de spmd (más lento que parfor en mi experiencia). La razón por la que parfor es más lento que un bucle for para rangos cortos o iteraciones rápidas es la sobrecarga necesaria para administrar a todos los trabajadores correctamente, en lugar de simplemente hacer el cálculo.

Consulte esta pregunta para obtener información sobre la división de datos entre trabajadores separados.

Benchmarking

Código

Considere el siguiente ejemplo para ver el comportamiento de for en oposición al de parfor . Primero abra el grupo paralelo si aún no lo ha hecho:

gcp; % Opens a parallel pool using your current settings

Luego ejecute un par de bucles grandes:

n = 1000; % Iteration number
EigenValues = cell(n,1); % Prepare to store the data
Time = zeros(n,1);
for ii = 1:n
tic
    EigenValues{ii,1} = eig(magic(1e3)); % Might want to lower the magic if it takes too long
Time(ii,1) = toc; % Collect time after each iteration
end

figure; % Create a plot of results
plot(1:n,t)
title ''Time per iteration''
ylabel ''Time [s]''
xlabel ''Iteration number[-]'';

Luego haga lo mismo con parfor lugar de for . Notará que el tiempo promedio por iteración sube (0.27s a 0.39s para mi caso). Sin embargo, parfor cuenta que el parfor utilizó a todos los trabajadores disponibles, por lo tanto, el tiempo total ( sum(Time) ) debe dividirse por el número de núcleos en su computadora. Entonces, para mi caso, el tiempo total bajó de alrededor de 270 segundos a 49 segundos, ya que tengo un procesador octacore.

Entonces, aunque el tiempo para hacer cada iteración por separado aumenta usando parfor con respecto al uso de for , el tiempo total disminuye considerablemente.

Resultados

Esta imagen muestra los resultados de la prueba tal como la ejecuté en la PC de mi casa. eig(500) n=1000 y eig(500) ; mi computadora tiene un procesador I5-750 de 2.66 GHz con cuatro núcleos y ejecuta MATLAB R2012a. Como puede ver, el promedio de la prueba paralela oscila alrededor de 0.29s con mucha dispersión, mientras que el código de serie es bastante estable alrededor de 0.24s. El tiempo total, sin embargo, bajó de 234s a 72s, que es una velocidad de 3.25 veces. La razón por la que esto no es exactamente 4 es la sobrecarga de memoria, como se expresa en el tiempo extra que toma cada iteración. La sobrecarga de memoria se debe a que MATLAB tiene que verificar lo que está haciendo cada núcleo y asegurarse de que cada iteración de bucle se realice solo una vez y que los datos se coloquen en la ubicación de almacenamiento correcta.