Оптимизация вложенных циклов

Question

У нас есть назначение, где нам предоставляется очень неэффективная программа, и мы должны оптимизировать код, чтобы он работал быстрее. У меня большая часть из них идет довольно быстро, за исключением этих двух, что меня так сильно задевает, потому что они ОЧЕНЬ просто функционируют. Один из них в основном устанавливает все значения в двумерном массиве на одно и то же значение, а один в основном меняет значения двух двухмерных массивов. И в этом проблема. Они занимают больше всего времени, но поскольку они такие простые, я не могу понять, как их уменьшить, не нарушая функций. И я знаю, что можно заставить их работать быстрее, потому что другие студенты в классе получают нелепые ускорения. Эти два вопроса:

fSetArray(int rows, int cols, float val) 
{ 
    int i, j; 
    F2D *out; 
    out = fMallocHandle(rows, cols); 

    for(i=0; i<rows; i++) 
    for(j=0; j<cols; j++) 
     subsref(out,i,j) = val; 

    return out; 

} 

Единственная важная часть - это две петли. В принципе, у нас есть двухмерный массив с определенной шириной (строками) и определенной высотой (cols), и мы устанавливаем ВСЕ значения в val. Но я не вижу возможности устранить одну из циклов (что было бы лучшим способом ускорить ее). Если я не пропущу что-то очевидное. Если cols и rows были одинаковыми, это было бы намного проще.

Другая функция:

fDeepCopy(F2D* in) 
{ 
    int i, j; 
    F2D* out; 
    int rows, cols; 

    rows = in->height; 
    cols = in->width; 

    out = fMallocHandle(rows, cols); 

    for(i=0; i<rows; i++) 
    for(j=0; j<cols; j++) 
     subsref(out,i,j) = subsref(in,i,j); 

    return out; 
} 

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

И прежде чем кто-либо скажет о параллелизме, из-за размера выборки и сервера, накладные расходы, необходимые для создания потоков, фактически замедляют работу программы. Я пробовал. Поскольку эти две функции слишком короткие, не стоит создавать потоки только для их уничтожения после одной параллели.

Но для справки, да, технически это проект OpenMP, и мы должны использовать распараллеливание, но для этих двух функций это фактически замедляет работу всей программы. Я приурочил его к параллельному циклу для проверки.

EDIT: Спасибо всем, кто дал мне идеи! Сейчас у меня все работает, и теперь полная скорость!

Answer 1

Один тип оптимизации - это разворот цикла. Иногда конвейер должен останавливаться, потому что есть много активности вокруг получения индекса, его обновления и сохранения его в памяти. Это, вероятно, основной причине, что ваша многопоточная реализация не преуспела, все потоки , вероятно, боролись за доступ к индексу.

Если вы хотите повторить попытку многопоточной реализации, есть каждый поток знают, что это «смещение» на основе подсчета потоков, и у каждого процесс нити другой остатка обнаруженный с помощью модуля разделения

thread 0 works on i*rows+j % (thread count) = 0 
thread 1 works on i*rows+j % (thread count) = 1 
(and so on) 

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

fDeepCopy(F2D* in) 
{ 
    int i, j; 
    F2D* out; 
    int rows, cols; 

    rows = in->height; 
    cols = in->width; 

    out = fMallocHandle(rows, cols); 

    for(i=0; i<rows; i++) { 
     // rewrite to ensure we don't walk off "4 long" pads 
     int j = 0; 
     int pads = (cols/4)*4; 
     for(; j < pads; j = j + 4) { 
     subsref(out,i,j) = subsref(in,i,j); 
     subsref(out,i,j+1) = subsref(in,i,j+1); 
     subsref(out,i,j+2) = subsref(in,i,j+2); 
     subsref(out,i,j+3) = subsref(in,i,j+3); 
     } 
     // process the remainders 
     for(; j < pads; j++) { 
     subsref(out,i,j) = subsref(in,i,j); 
     } 
    } 
    return out; 
} 

Теперь дизайнеры CPU становится лучше, так что критически, что вы на самом деле профиля вашего работает, чтобы определить, является ли процессор уже делает такую ​​оптимизацию для вашей или такой техники может на самом деле замедлить ваш код.

Наконец, вы также можете указать leverage SSE extensions, который при правильных условиях может выполнять одну и ту же операцию по нескольким значениям, хранящимся в регистре MMX. Например, вы можете использовать встроенную сборку для упаковки двух наборов из четырех 32-битных чисел с плавающей запятой с одинарной точностью в регистры MMX и выполнять добавление навалом, с четырьмя плавающими точками за раз.

Таким образом, то, что выглядит как

vec_res.x = v1.x + v2.x; 
vec_res.y = v1.y + v2.y; 
vec_res.z = v1.z + v2.z; 
vec_res.w = v1.w + v2.w; 

, которая требовала бы восемь обращений к памяти, четыре дополнения, а также четыре магазина (16 операций неоптимизированных) может быть заменен

movaps xmm0, [v1]   ;xmm0 = v1.w | v1.z | v1.y | v1.x 
addps xmm0, [v2]   ;xmm0 = v1.w+v2.w | v1.z+v2.z | v1.y+v2.y | v1.x+v2.x    
movaps [vec_res], xmm0 

, который требует только три операции, неоптимизированы.

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

Answer 2

memset должен быть полезен для первой функции.