Плавающее умножение выполняется медленнее в зависимости от операндов в C

Я выполняю вычисление трафаретов на матрице, которую я ранее читал из файла. Я использую два разных типа матриц (тип NonZero и нулевой тип). Оба типа разделяют значение границ (обычно 1000), в то время как остальные элементы равны 0 для типа "нуль" и 1 для типа NonZero.

Код хранит матрицу файла в двух распределенных матрицах одинакового размера. Затем он выполняет операцию в каждом элементе одной матрицы, используя ее собственное значение и значения соседей (добавить x 4 и mul x 1) и сохраняет результат во второй матрице. Как только вычисление завершено, указатели на матрицы меняются местами, и одна и та же операция выполняется в течение конечного количества раз. Здесь у вас есть код ядра:

#define GET(I,J) rMat[(I)*cols + (J)]
#define PUT(I,J) wMat[(I)*cols + (J)]

for (cur_time=0; cur_time<timeSteps; cur_time++) {
    for (i=1; i<rows-1; i++) {
        for (j=1; j<cols-1; j++) {
            PUT(i,j) = 0.2f*(GET(i-1,j) + GET(i,j-1) + GET(i,j) + GET(i,j+1) + GET(i+1,j));
        }
    }
    // Change pointers for next iteration
    auxP = wMat;
    wMat = rMat;
    rMat = auxP;
}

В случае, когда я подвергаюсь воздействию, используется фиксированное количество 500 временных шагов (внешние итерации) и размер матрицы 8192 строк и 8192 столбца, но проблема сохраняется при изменении количества временных шагов или размера матрицы. Обратите внимание, что я только измеряю время этой конкретной части алгоритма, поэтому чтение матрицы из файла или ничего другого влияет на временную меру.

Что происходит, это то, что я получаю разные времена в зависимости от того, какой тип матрицы я использую, получая намного худшую производительность при использовании типа Zero (каждая другая матрица выполняет то же самое, что и тип NonZero, поскольку я уже пытался создать матрицу полный случайных значений).

Я уверен, что это операция умножения, как будто я удаляю ее и оставляю только добавление, они выполняют то же самое. Обратите внимание, что при нулевом матричном типе большая часть результата будет равна 0, поэтому операция будет "0.2 * 0".

Такое поведение, безусловно, странно для меня, поскольку я думал, что операции с плавающей запятой независимы от значений операндов, что здесь не похоже. Я также попытался захватить и показать исключения SIGFPE в случае, если это была проблема, но я не получил никаких результатов.

В случае, если это помогает, я использую процессор Intel Nehalem и gcc 4.4.3.

Ответы

Ответ 1

Проблема уже в основном диагностирована, но я точно напишу, что здесь происходит.

По сути, вопросник представляет собой моделирование диффузии; начальная величина на границе диффундирует во всю большую сетку. На каждом шаге времени t значение на переднем фронте диффузии будет равно 0,2 ^ t (игнорируя эффекты в углах).

Наименьшее нормированное значение одной точности составляет 2 ^ -126; при cur_time = 55 значение на границе диффузии составляет 0,2 ^ 55, что немного меньше 2 ^ -127. С этого момента шаг вперед, некоторые ячейки в сетке будут содержать денормальные значения. В вопросе Nehalem операции с денормальными данными примерно в 100 раз медленнее, чем та же операция по нормализованным данным с плавающей запятой, объясняя замедление.

Когда сетка изначально заполняется постоянными данными 1.0, данные никогда не становятся слишком маленькими, поэтому избегается денормальная стойка.

Обратите внимание, что изменение типа данных на double задерживает, но не устраняет проблему. Если для вычисления используется двойная точность, денормальные значения (теперь меньше 2 ^ -1022) будут впервые возникать на 441-й итерации.

За счет точности на переднем крае диффузии вы можете зафиксировать замедление, включив "Flush to Zero", что заставляет процессор генерировать нуль вместо денормальных результатов в арифметических операциях. Это делается путем переключения бит в FPSCR или MXSCR, предпочтительно с помощью функций, определенных в заголовке <fenv.h> в библиотеке C.

Другое ( "хакерское, менее хорошее" ) "исправить" было бы сначала заполнить матрицу очень маленькими ненулевыми значениями (0x1.0p-126f, наименьшее нормальное число). Это также предотвратило бы появление денормалов при вычислении.

Ответ 2

Возможно, ваш ZeroMatrix использует типичную схему хранения для Sparse Matrices: сохраняйте каждое ненулевое значение в связанном списке. Если это так, вполне понятно, почему он работает хуже, чем типичная схема хранения на основе массива: потому что он должен запускаться через связанный список один раз для каждой операции, которую вы выполняете. В этом случае вы можете ускорить процесс, используя алгоритм с матричным умножением, который учитывает наличие разреженной матрицы. Если это не так, напишите минимальный, но полный код, чтобы мы могли играть с ним.

здесь есть одна из возможностей эффективного умножения разреженных матриц:

http://www.cs.cmu.edu/~scandal/cacm/node9.html