Распараллеливание случайного чтения, кажется, работает хорошо - почему?

18

Рассмотрим следующую очень простую компьютерную программу:

for i = 1 to n:
    y[i] = x[p[i]]

Здесь и y - это n- элементные массивы байтов, а p - это n- элементный массив слов. Здесь n большое, например, n = 2 31 (так что только незначительная часть данных помещается в любой тип кэш-памяти).ИксYNпNNNзнак равно231

Предположим, что состоит из случайных чисел , равномерно распределенных между 1 и n .п1N

С точки зрения современного оборудования это должно означать следующее:

  • чтение дешево (последовательное чтение)п[я]
  • чтение очень дорого (случайное чтение; почти все чтения являются ошибками кэша; нам придется извлекать каждый отдельный байт из основной памяти)Икс[п[я]]
  • запись дешево (последовательная запись).Y[я]

И это действительно то, что я наблюдаю. Программа очень медленная по сравнению с программой, которая выполняет только последовательное чтение и запись. Отлично.

Теперь возникает вопрос: насколько хорошо эта программа распараллеливается на современных многоядерных платформах?


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

Однако это было не то, что я заметил, когда начал экспериментировать с некоторыми алгоритмами, в которых узким местом была такая операция!

Я просто заменил простой цикл for параллельным циклом forMP в OpenMP (по сути, он просто разделит диапазон на более мелкие части и запустит эти части на разных ядрах процессора параллельно).[1,N]

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

  • 2 x 4-ядерных Xeon (всего 8 ядер): ускорение в 5-8 раз по сравнению с однопоточной версией.

  • 2 x 6-ядерных Xeon (всего 12 ядер): ускорение в 8-14 раз по сравнению с однопоточной версией.

Теперь это было совершенно неожиданно. Вопросов:

  1. Почему именно такого рода программы распараллеливают так хорошо ? Что происходит в оборудовании? (Мое текущее предположение примерно такое: случайные чтения из разных потоков «конвейерны», и средняя скорость получения ответов на них намного выше, чем в случае одного потока.)

  2. Является ли это необходимо использовать несколько потоков и нескольких ядер , чтобы получить какие - либо ускорений? Если в интерфейсе между основной памятью и процессором действительно происходит какая-то конвейерная обработка, то однопоточное приложение не может сообщить основной памяти, что ему скоро понадобятся , x [ p [ i + 1 ] ] , ... а компьютер может начать извлекать соответствующие строки кэша из основной памяти? Если это возможно в принципе, как мне добиться этого на практике?Икс[п[я]]Икс[п[я+1]]

  3. Что является правильным теоретическую модель мы могли бы использовать для анализа программ такого типа (и для правильного прогнозирования производительности)?


Изменить: теперь есть некоторые исходные коды и результаты тестов доступны здесь: https://github.com/suomela/parallel-random-read

Nзнак равно232

  • ок. 42 нс за итерацию (случайное чтение) с одним потоком
  • ок. 5 нс на итерацию (случайное чтение) с 12 ядрами.
Юкка Суомела
источник

Ответы:

9

пNпNпп

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

NN/пп процессоре параллельной системы процессором , в то время как эффекты кэша и виртуальной памяти могут вместо этого снизить эффективную скорость вычислений последовательного процессора.

Nзнак равно231 байт нам нужно 2048 Мбайт памяти. Но при использовании 12 ядер, как в вашем последнем примере, каждое ядро ​​должно обрабатывать только 2048/12 МБ данных, что составляет около 170 МБ. Высокопроизводительные процессоры Xeon оснащены кэш-памятью 3-го уровня, размер которой варьируется от 15 до 30 Мбайт. Очевидно, что при таком огромном размере кэша коэффициент попадания в кэш высокий, и это объясняет наблюдаемое хорошее или даже суперлинейное ускорение.

N

Наконец, кроме QSM (Queuing Shared Memory) , я не знаю ни одной другой теоретической параллельной модели, учитывающей на том же уровне конкуренцию за доступ к разделяемой памяти (в вашем случае, при использовании OpenMP основная память распределяется между ядрами и кеш всегда распределяется между ядрами). В любом случае, хотя модель интересная, она не получила большого успеха.

Массимо Кафаро
источник
1
Это может также помочь рассмотреть это как каждое ядро, обеспечивающее более или менее фиксированный уровень параллелизма на уровне памяти, например, 10 x [] загружаются в процесс в данный момент времени. С вероятностью 0,5% попадания в общий L3, у одного потока будет 0,995 ** 10 (95 +%) шансов потребовать от всех этих загрузок ожидания ответа основной памяти. С 6 ядрами, обеспечивающими в общей сложности 60 x [] ожидающих считываний, есть почти 26% шанс, что по крайней мере одно чтение попадет в L3. Кроме того, чем больше MLP, тем больше контроллер памяти может планировать доступ для увеличения фактической пропускной способности.
Пол А. Клейтон
5

Я решил попробовать __builtin_prefetch () самостоятельно. Я публикую это здесь как ответ на случай, если другие захотят проверить это на своих машинах. Результаты близки к тому, что описывает Юкка: сокращение времени выполнения примерно на 20% при предварительной выборке на 20 элементов вперед по сравнению с предварительной выборкой на 0 элементов вперед.

Результаты:

prefetch =   0, time = 1.58000
prefetch =   1, time = 1.47000
prefetch =   2, time = 1.39000
prefetch =   3, time = 1.34000
prefetch =   4, time = 1.31000
prefetch =   5, time = 1.30000
prefetch =   6, time = 1.27000
prefetch =   7, time = 1.28000
prefetch =   8, time = 1.26000
prefetch =   9, time = 1.27000
prefetch =  10, time = 1.27000
prefetch =  11, time = 1.27000
prefetch =  12, time = 1.30000
prefetch =  13, time = 1.29000
prefetch =  14, time = 1.30000
prefetch =  15, time = 1.28000
prefetch =  16, time = 1.24000
prefetch =  17, time = 1.28000
prefetch =  18, time = 1.29000
prefetch =  19, time = 1.25000
prefetch =  20, time = 1.24000
prefetch =  19, time = 1.26000
prefetch =  18, time = 1.27000
prefetch =  17, time = 1.26000
prefetch =  16, time = 1.27000
prefetch =  15, time = 1.28000
prefetch =  14, time = 1.29000
prefetch =  13, time = 1.26000
prefetch =  12, time = 1.28000
prefetch =  11, time = 1.30000
prefetch =  10, time = 1.31000
prefetch =   9, time = 1.27000
prefetch =   8, time = 1.32000
prefetch =   7, time = 1.31000
prefetch =   6, time = 1.30000
prefetch =   5, time = 1.27000
prefetch =   4, time = 1.33000
prefetch =   3, time = 1.38000
prefetch =   2, time = 1.41000
prefetch =   1, time = 1.41000
prefetch =   0, time = 1.59000

Код:

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

void cracker(int *y, int *x, int *p, int n, int pf) {
    int i;
    int saved = pf;  /* let compiler optimize address computations */

    for (i = 0; i < n; i++) {
        __builtin_prefetch(&x[p[i+saved]]);
        y[i] += x[p[i]];
    }
}

int main(void) {
    int n = 50000000;
    int *x, *y, *p, i, pf, k;
    clock_t start, stop;
    double elapsed;

    /* set up arrays */
    x = malloc(sizeof(int)*n);
    y = malloc(sizeof(int)*n);
    p = malloc(sizeof(int)*n);
    for (i = 0; i < n; i++)
        p[i] = rand()%n;

    /* warm-up exercise */
    cracker(y, x, p, n, pf);

    k = 20;
    for (pf = 0; pf < k; pf++) {
        start = clock();
        cracker(y, x, p, n, pf);
        stop = clock();
        elapsed = ((double)(stop-start))/CLOCKS_PER_SEC;
        printf("prefetch = %3d, time = %.5lf\n", pf, elapsed);
    }
    for (pf = k; pf >= 0; pf--) {
        start = clock();
        cracker(y, x, p, n, pf);
        stop = clock();
        elapsed = ((double)(stop-start))/CLOCKS_PER_SEC;
        printf("prefetch = %3d, time = %.5lf\n", pf, elapsed);
    }

    return 0;
}
Пэт Морин
источник
4
  1. Доступ к DDR3 действительно конвейерный. На http://www.eng.utah.edu/~cs7810/pres/dram-cs7810-protocolx2.pdf слайдах 20 и 24 показано, что происходит в шине памяти во время конвейерных операций чтения.

  2. (частично неправильно, см. ниже) Несколько потоков не нужны, если архитектура процессора поддерживает предварительную выборку из кэша. Современные x86 и ARM, а также многие другие архитектуры имеют явную инструкцию предварительной выборки. Многие дополнительно пытаются обнаружить шаблоны в обращениях к памяти и выполняют предварительную выборку автоматически. Поддержка программного обеспечения зависит от компилятора, например, GCC и Clang имеют встроенную функцию __builtin_prefech () для явной предварительной выборки.

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

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

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

Юхани Симола
источник
__builtin_prefech звучит очень многообещающе. К сожалению, в моих быстрых экспериментах это, похоже, не сильно помогло с однопоточностью (<10%). Насколько большие улучшения скорости следует ожидать в такого рода приложениях?
Юкка Суомела
Я ожидал большего. Поскольку я знаю, что предварительная выборка оказывает существенное влияние на DSP и игры, мне пришлось самому экспериментировать. Оказалось, кроличья нора идет глубже ...
Юхани Симола
Моей первой попыткой было создание фиксированного случайного порядка, хранящегося в массиве, с последующей итерацией в этом порядке с предварительной выборкой и без нее ( gist.github.com/osimola/7917602 ). Это принесло разницу около 2% на Core i5. Похоже, либо предварительная выборка вообще не работает, либо аппаратный предиктор понимает косвенность.
Юхани Симола
1
Итак, проверяя это, вторая попытка ( gist.github.com/osimola/7917568 ) обращается к памяти в последовательности, сгенерированной фиксированным случайным начальным числом . На этот раз версия с предварительной загрузкой была примерно в 2 раза быстрее, чем без предварительной, и в 3 раза быстрее, чем предварительная выборка на 1 шаг вперед. Обратите внимание, что версия с предварительной загрузкой выполняет больше вычислений на доступ к памяти, чем версия без предварительной выборки.
Юхани Симола
Кажется, это зависит от машины. Я попробовал код Пата Морина ниже (не могу комментировать этот пост, так как у меня нет репутации), и мой результат в пределах 1,3% для разных значений предварительной выборки.
Юхани Симола