Переупорядочение циклов через границы функций в алгоритмах STL - PullRequest
Новая
       8

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

1 голос
/ 17 декабря 2010

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

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

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

Ответы [ 3 ]

1 голос
/ 17 декабря 2010

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

1 голос
/ 17 декабря 2010 
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));
  }
}
1 голос
/ 17 декабря 2010

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

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

...