Распараллеливать или векторизовать операцию all-to-all на большом числе матриц?

Question

У меня есть приблизительно 5000 матриц с таким же количеством строк и разным количеством столбцов (20 x 200). Каждая из этих матриц должна сравниваться друг с другом в динамическом алгоритме программирования.

В вопросе this я спросил, как быстро выполнить сравнение и получил отличный ответ, включающий двумерную свертку. Поочередно, итерационно применяя этот метод, как и

list = who('data_matrix_prefix*') 
H = cell(numel(list),numel(list)); 
for i=1:numel(list) 
    for j=1:numel(list) 
     if i ~= j 
      eval([ 'H{i,j} = compare(' char(list(i)) ',' char(list(j)) ');']); 
     end 
    end 
end 

быстро для небольших подмножеств данных (например, для 9 матриц, 9 * 9 - 9 = 72 вызовов выполняются в ~ 1 с, 870 вызовов в ~ 2.5 с).
Однако для работы на всех данных требуется почти 25 миллионов вызовов.
Я также попытался использовать сделку(), чтобы сделать массив ячеек, состоящий полностью из следующего элемента данных, так что я мог бы использовать cellfun() в одном цикле:

# who(), load() and struct2cell() calls place k data matrices in a 1D cell array called data. 
nextData = cell(k,1); 
for i=1:k 
    [nextData{:}] = deal(data{i}); 
    H{:,i} = cellfun(@compare,data,nextData,'UniformOutput',false); 
end 

К сожалению, это на самом деле не любой быстрее, потому что все время находится в compare(). Оба этих примера кода выглядят плохо подходящими для распараллеливания. Мне трудно понять, как сделать мои переменные нарезанными.
Спрятать() полностью в векторном формате; он использует только матричное умножение и conv2() (у меня создается впечатление, что все эти операции, включая cellfun(), должны быть многопоточными в MATLAB?).

Кто-нибудь видит (явно) параллелизированное решение или лучшую векторизацию проблемы?

Примечание
Я понимаю, что оба мои примеры неэффективны - первый будет в два раза быстрее, если он вычислил массив треугольной ячейки, а второй по-прежнему вычисления самостоятельно сравнений, а также. Но экономия времени для хорошей распараллеливания больше похожа на коэффициент 16 (или 72, если я устанавливаю MATLAB на все машины).

Адрес
Существует также проблема с памятью. Я использовал пару оценок, чтобы добавить каждый столбец H в файл с именами, такими как H1, H2 и т. Д., А затем очистить H _i. К сожалению, экономия происходит очень медленно ...

Answer 1

Второй пример можно легко нарезать для использования с Parallel Processing Toolbox. Этот набор инструментов распределяет итерации вашего кода между 8 различными локальными процессорами. Если вы хотите запустить код в кластере, вам также понадобится панель распределенных вычислений.

%# who(), load() and struct2cell() calls place k data matrices in a 1D cell array called data. 

parfor i=1:k-1 %# this will run the loop in parallel with the parallel processing toolbox 
    %# only make the necessary comparisons 
    H{i+1:k,i} = cellfun(@compare,data(i+1:k),repmat(data(i),k-i,1),'UniformOutput',false); 

    %# if the above doesn't work, try this 
    hSlice = cell(k,1); 
    hSlice{i+1:k} = cellfun(@compare,data(i+1:k),repmat(data(i),k-i,1),'UniformOutput',false); 
    H{:,i} = hSlice; 
end 

Answer 2

Если я правильно понял, вы должны выполнить сравнение матриц 5000^2? Вместо того, чтобы пытаться распараллелить функцию сравнения, возможно, вам стоит подумать о том, что ваша проблема состоит из 5000^2 задач? Набор инструментов Matlab Parallel Compute Toolbox поддерживает параллелизм на основе задач. К сожалению, мой опыт работы с PCT заключается в параллелизации больших проблем типа линейной алгебры, поэтому я не могу сказать вам гораздо больше. Документация, несомненно, поможет вам больше.

Answer 3

ли

compare(a,b) == compare(b,a) 

и

compare(a,a) == 1 

Если да, то изменить цикл

for i=1:numel(list) 
    for j=1:numel(list) 
    ... 
    end 
end 

в

for i=1:numel(list) 
    for j= i+1 : numel(list) 
    ... 
    end 
end 

и иметь дело с симметрией и личным случаем. Это сократит время вычисления вдвое.