Распараллелить или векторизовать операцию «все против всех» на большом количестве матриц? - PullRequest
Новая
       23

Распараллелить или векторизовать операцию «все против всех» на большом количестве матриц?

1 голос
/ 20 мая 2010

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

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

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 миллионов вызовов.
Я также попытался с помощью метода deal () создать массив ячеек, состоящий полностью из следующего элемента данных, чтобы я мог использовать 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

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

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

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

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

Ответы [ 3 ]

3 голосов
/ 20 мая 2010

ли 

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

и иметь дело с симметрией и тождеством. Это сократит ваше время расчета вдвое.

1 голос
/ 20 мая 2010

Второй пример можно легко нарезать для использования с 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
0 голосов
/ 20 мая 2010

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

...