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

Question

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

Код хранит матрицу файла в двух выделенных матрицахтот же размер.Затем он выполняет операцию в каждом элементе одной матрицы, используя свое собственное значение и значения соседей (добавьте 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 столбцов, но проблема сохраняется при изменении числаtimeSteps или размер матрицы.Обратите внимание, что я измеряю только время этой конкретной части алгоритма, поэтому чтение матрицы из файла и ничего другого влияет на измерение времени.

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

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

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

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

Answer 1

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

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

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

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

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

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

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

Answer 2

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

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

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