Intereting Posts
Дерево вызовов для встроенного программного обеспечения Любые хорошие примеры программирования с помощью libssl? Формат PE – вопросы IAT Почему мы инициализируем верхнюю часть стека как -1? Может ли шейдер OpenGL ES изменить значение глубины fragmentа? Как получить позицию курсора в программе на C с помощью termcap, не записывая символ? возникла ошибка компиляции при использовании clock_gettime в c99 Проверьте, заблокирован или разблокирован мьютекс pthread (после того, как stream заблокирован) Шифрование текстового файла в C Как выводить одновременно на консоль и текстовый файл так, чтобы они были идентичны Intel Galileo голый металл UART Неожиданное расширение знака указателя int32 или 32bit при преобразовании в uint64 Соответствует ли стандарт C99 двоичному представлению unsigned int? В то время как помощь цикла Как использовать таймеры в драйверах устройств ядра Linux?

петля. как выбрать размер блока?

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

а. С блокировкой

int max = 1000000; int B = 100; for (i = 0; i < max; i += B) { for (j = i; j < (i + B); j++) { array[j] = 0; } } 

б. Без блокировки

 for (i = 0; i < max; i++) { array[i] = 0; } 

время: с блокировкой: прошедшее время – 6997000 Nano Secs

Без блокировки прошедшего времени – 6097000 Nano Secs

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

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

    Рассмотрим следующий пример:

     #include "stdlib.h" #include "stdio.h" #include  #define MAX (1024*1024*32) #define REP 100 #define B (16*1024) int main() { int i,j,r; char array[MAX]; for (i = 0; i < MAX; i++) { // warmup to make things equal if array happens to fit in your L3 array[i] = 0; } clock_t t1 = clock(); // Tiled loop for (i = 0; i < MAX; i += B) { for (r = 0; r < REP; r++) { for (j = i; j < (i + B); j+=64) { array[j] = r; } } } clock_t t2 = clock(); // un-tiled loop for (r = 0; r < REP; r++) { for (i = 0; i < MAX; i+=64) { array[i] = r; } } clock_t t3 = clock(); printf ("Tiled: %f sec\n", (double)(t2 - t1) / CLOCKS_PER_SEC); printf ("Untiled: %f sec\n", (double)(t3 - t2) / CLOCKS_PER_SEC); printf ("array[0] = %d\n", array[0]); // to prevent optimizing out all the writes } 

    Обе петли выполняют одинаковый доступ (переходы в 64 байта - это усиление кэшей с использованием каждой строки кэша один раз и предотrotation узкого места IPC и диспетчеризации команд).

    Версия с черепицей переупорядочивает эти обращения в блоках, так что повторение одного блока может несколько раз ударять по кешу. Поскольку размер блока установлен в 16k, он, вероятно, поместится в большинстве кэшей L1 и получит действительно хорошую задержку. Для каждой итерации внешнего цикла у вас будет 1 итерация, когда вы пропустите все кеши и перейдете в память (если ваш L3 больше 32M, просто установите MAX еще выше, чтобы убедиться) и повторения REP-1 которые вылетают из L1.

    Версия Untiled также будет повторять время REP в целом, но каждое повторение будет разбивать все данные из кэшей, делая все обращения доступными в память, накапливаясь до гораздо более высокой общей задержки.

    Компиляция с gcc 4.8.1 (-O3) дает мне на Xeon 5670 @ 2,9 ГГц -

     Tiled: 0.110000 sec Untiled: 0.450000 sec array[0] = 99 

    более 4x 🙂

    Обратите внимание, что версия с поддержкой до сих пор имеет одно преимущество - есть один упорядоченный stream, поэтому предварительный выбор HW может ускорить выбор данных для вас, что несколько смягчает эффект латентности памяти. Тем не менее, вы можете помочь CPU сделать что-то подобное в банковской версии, если вы добавите следующее:

     for (i = 0; i < MAX; i += B) { for (r = 0; r < REP; r++) { for (j = i; j < (i + B); j+=64) { array[j] = r; if (r == REP - 2) // SW prefetching __builtin_prefetch(&array[j+B], 0); } } } 

    Говорить CPU о том, чтобы довести следующий блок немного до завершения текущего. Для цены условной ветви (с несколькими неверными предсказаниями на блок) вы сокращаете время выполнения первой итерации на следующем блоке - я получаю дальнейшее сокращение от этого:

     Tiled: 0.070000 sec