Переупорядочение петли по границам функций в алгоритмах STL

Для простоты предположим, что у меня есть вектор из N матриц, каждый из M строк. Я использую STL std::accumulate для вычисления суммы всех матриц. Я передаю двоичный функтор, который принимает две матрицы (по ссылке) и возвращает их сумму (по ссылке). Полное раскрытие: я использую параллельный режим libstdC++. Внутри функтора я перебираю строки по отдельности, чтобы вычислить сумму.Переупорядочение петли по границам функций в алгоритмах STL

Хотя каждая матрица слишком велика, чтобы вписаться в кеш, строка подходит очень хорошо. Поэтому было бы целесообразно повторно упорядочить петли так, чтобы внешний контур индексировал по строкам M, а внутренний - по матрицам N. В дополнение к определению функтора inline, есть ли что-то еще, что я могу сделать, чтобы поощрить такой переупорядочивание перекрестной функции-границы. Я могу, конечно, реструктурировать код, но в идеале я хотел бы сохранить простую структуру, доступную для использования алгоритмов STL. Если есть что-то конкретное gcc, я бы тоже не возражал.

Я на самом деле не имею дело с матрицами, это был всего лишь пример, но применяется одна и та же структура проблем. Основная проблема - производительность. Объяснение фактического сценария было бы слишком громоздким, но основная проблема заключается в следующем: накопление STL влечет за собой упорядочение среди вложенных циклов, которые не очень удобны для кеша, поскольку он пытается завершить добавление двух объектов, прежде чем перейти к следующему объекту. Один объект слишком велик для хранения в кеше, но его части могут быть. Таким образом, выполнение может ускоряться, если каждый раз вычислять «дополнения» по одной «части» (по всем объектам). Ручное переупорядочение петель приводит к существенному улучшению FLOPS. Но я бы идеально хотел, чтобы компилятор выполнял переупорядочение, чтобы я мог кодировать на уровне STL (насколько это возможно). Поэтому я ищу трюки, чтобы сделать это.

источник

2010-12-17 srean

Непонятный вопрос. У вас проблемы с производительностью? Можете ли вы показать нам, что у вас есть? – wilhelmtell 2010-12-17 02:16:32

@wilhelmtell Я добавил еще несколько деталей. Надеюсь, теперь это немного яснее. – srean 2010-12-17 03:05:33

Я поддерживаю все три предложения, которые я получил до сих пор. Я все еще ищу способ побудить компилятор сделать правильные вещи. Потому что правильная вещь зависит от размеров кеша. Может быть, решение заключается в использовании препроцессора для условной компиляции. – srean 2010-12-17 05:11:45

class Matrix; 
class Row; 
struct SumNRow { 
    int _rowidx; 
// Row _tempRow; //For return by reference left out for simplicity 
    SumNRow(int iRowIdx): _rowIdx(iRowIdx) {} 
    Row operator(const Matrix & iMarix1, const Matrix iMatrix2) { 
    return iMarix1[_rowIdx] + iMatrix2[_rowIdx]; 
    } 
}; 

template<class MatrixIterator> 
void sum(const MatrixIterator & iMarixStart, const MatrixIterator & iMatrixEnd, Matrix & oMarix) { 
    for (int i = 0; i < iMarixStart->rowCount(); ++i) { 
    oMarix[i]=std::accumulate(iMarixStart, iMatrixEnd, SumNRow(i)); 
    } 
}

источник

2010-12-17 04:52:33 Basilevs

Я не могу представить, чтобы компилятор понял это, если все не было вложенным, а M и N были постоянными. Даже тогда это было бы растяжкой.

Чтобы сохранить алгоритмический стиль STL, используйте foreach M над накоплением и попросите функцию просто суммировать строку.

источник

2010-12-17 02:53:59

Напишите новый алгоритм или оберните вещи в цикле или вызове std::for_each(). Это будет намного проще, чем найти способы адаптации std::accumulate(). Я думаю, что единственной альтернативой здесь является введение в библиотеку нового уровня абстракции, который выходит за рамки итераторов. Легче просто написать новый алгоритм или ввести дополнительный цикл.

источник

2010-12-17 03:32:33 wilhelmtell

Переупорядочение петли по границам функций в алгоритмах STL

ответ

Смежные вопросы