Переменное время выполнения программы C

Моя (simd) реализация занимает разное количество времени, хотя она запускается для фиксированного ввода. Время работы варьируется от, скажем, 100 миллионов тактовых циклов до 120 миллионов тактовых циклов. Программа вызывает функцию около 600 раз, и самая затратная часть функции находится в памяти, доступ к которой осуществляется ~2000 раз. Таким образом, общее использование памяти в моей программе довольно велико.

Не связано ли изменение времени работы с моделями доступа к памяти/начальным содержимым памяти?

Я использовал valgrind для анализа профиля моей программы. Это показывает, что каждый доступ к памяти занимает около 8 инструкций. Это нормально?

Ниже приведен фрагмент кода (функция), который вызывается 600 раз. Mulprev[32][20] — это массив, к которому обращаются чаще всего.

j = 15;  
u3v = _mm_set_epi64x (0xF, 0xF);
while (j + 1)  
{

    l = j << 2;  
    for (i = 0; i < 20; i++)
    {
        val1v   = _mm_load_si128 ((__m128i *) &elm1v[i]);       
        uv  = _mm_and_si128 (_mm_srli_epi64 (val1v, l), u3v);
        u1  = _mm_extract_epi16 (uv, 0);
        u2  = _mm_extract_epi16 (uv, 4) + 16;

        for (ival = i, ival1 = i + 1, k = 0; k < 20; k += 2, ival += 2, ival1 += 2)
        {
            temp11v = _mm_load_si128 ((__m128i *) &mulprev[u1][k]); 
            temp12v = _mm_load_si128 ((__m128i *) &mulprev[u2][k]);

            val1v   = _mm_load_si128 ((__m128i *) &res[ival]);
            val2v   = _mm_load_si128 ((__m128i *) &res[ival1]); 

            bv  = _mm_xor_si128 (val1v, _mm_unpacklo_epi64 (temp11v, temp12v));
            av  = _mm_xor_si128 (val2v, _mm_unpackhi_epi64 (temp11v, temp12v));

            _mm_store_si128 ((__m128i *) &res[ival], bv);                                   
            _mm_store_si128 ((__m128i *) &res[ival1], av); 
        }
    }

    if (j == 0)
        break;
    val0v = _mm_setzero_si128 ();

    for (i = 0; i < 40; i++)
    {
        testv   = _mm_load_si128 ((__m128i *)  &res[i]);
        val1v   = _mm_srli_epi64 (testv, 60);
        val2v   = _mm_xor_si128  (val0v, _mm_slli_epi64 (testv, 4));
        _mm_store_si128 (&res[i], val2v);
        val0v   = val1v;
    }
    j--;
}

Я хочу сократить время вычислений моей программы. Какие-либо предложения?


c optimization memory sse
person anup    schedule 30.01.2011    source источник
comment
Вам нужно опубликовать фактический код, если вы хотите помочь его оптимизировать.   -  person Paul R    schedule 30.01.2011
comment
Пожалуйста, смотрите отредактированный вопрос ..   -  person anup    schedule 30.01.2011

Ответы (3)


arrow_upward
3
arrow_downward

Вы почти не выполняете вычислений между загрузкой и сохранением, поэтому время выполнения, скорее всего, будет определяться стоимостью операций ввода-вывода в/из кэша/памяти. Хуже того, ваш набор данных кажется относительно небольшим. Вероятно, единственный способ оптимизировать это — улучшить шаблон доступа к памяти (сделать доступы последовательными, где это возможно, и убедиться, что строки кэша не тратятся впустую и т. д.) и/или объединить эти операции с другим кодом, который работает с тем же набором данных. до/после этой процедуры (чтобы стоимость загрузки/сохранения несколько амортизировалась).

РЕДАКТИРОВАТЬ: обратите внимание, что я дал очень похожий ответ, когда вы задали тот же вопрос для явно более ранней версии этой процедуры: Как сделать следующий код быстрее - вы, кажется, упустили тот момент, что ваша основная проблема с производительностью здесь - это доступ к памяти, а не вычисления.

person Paul R    schedule 30.01.2011

arrow_upward
1
arrow_downward

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

person Oystein    schedule 30.01.2011
comment
Я собирался предложить то же самое (нет гарантии, какие процессы запустятся в многозадачной ОС, если они имеют одинаковый приоритет), но потом прочитал это: valgrind.org/docs/manual/cl-manual.html#cl-manual.cycles По-видимому, циклы в valgrind не то же самое, что циклы процессора (?) - person esaj; 30.01.2011
comment
@esaj эта ссылка описывает циклы графа en.wikipedia.org/wiki/Cycle_(graph_theory) в графе вызовов программы. - person James Greenhalgh; 30.01.2011

arrow_upward
0
arrow_downward

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

Это может быть что угодно.

person James    schedule 30.01.2011
comment
Можете ли вы дать мне типичное время чтения кэша L1 с предполагаемым попаданием? Если данные находятся в кеше, гарантируется ли, что время выборки будет одинаковым независимо от их местоположения в кеше. Любые ссылки? - person anup; 30.01.2011
comment
8 циклов - это НЕ много времени для доступа к памяти. В случае промаха кеша весь путь до DRAM может занять 100 и более циклов на современном процессоре. - person Axel Gneiting; 31.01.2011
comment
@anup, @Axel: задержка для попадания L1 на современные процессоры обычно составляет ~ 4 цикла (более подробную информацию см. в Руководствах по оптимизации Intel или в документации по конкретному процессору). Стоит отметить, что anup на самом деле сказал, что [Valgrind] показывает, что каждый доступ к памяти занимает около 8 инструкций. Инструкции — это не циклы; современный процессор Intel потенциально может отказаться от 4 инструкций за цикл, поэтому 8 инструкций на самом деле могут означать всего пару циклов, что соответствует попаданию L1. Однако я не знаком с Valgrind, поэтому я не знаю, как он на самом деле выполняет свои измерения. - person Stephen Canon; 31.01.2011
comment
@Stephen: я говорил о DRAM, а не о кеше. - person Axel Gneiting; 03.02.2011