Циклическая черепица как выбрать размер блока?

Question

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

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

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 нано сек

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

Answer 1

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

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

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

#include "stdlib.h"
#include "stdio.h"
#include <time.h>

#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-байтовые переходы предназначены для того, чтобы подчеркнуть кэши, используя каждую строку кэша один раз и не допуская, чтобы IPC и диспетчеризация команд были узким местом).

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

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

Компиляция с gcc 4.8.1 (-O3) дает мне на Xeon 5670 @ 2.9GHz -

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

более 4х:)

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

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);    
         }
    }
}

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

Tiled: 0.070000 sec