Использование кэша, пространственная локализация и задержка

Я изучаю операции с кешем в отношении пространственной локализации. (Мои ссылки на данный момент - это " Принципы параллельного программирования " Линя и Снайдера, это руководство и, конечно, Википедия.)

Возьмите следующий пример, скомпилированный с gcc, работающий в Windows 7 Professional с использованием процессора Intel Core2 Duo (L7500).

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

int main()
{
    int *array;
    int length;
    int count;
    int range;
    int i;

    // generate an array of a million integers between 0 and 99
    length = 1000000;
    range = 100;
    array = calloc(length, sizeof(int));
    srand(time(NULL));
    for(i = 0; i < length; i++)
    {
        array[i] = rand() % range;
        // printf("%d\n", array[i]);
    }

    // count the number of occurrences of 3 in the array
    count=0;
    for(i=0; i<length; i++)
    {
        if(array[i]==3)
        {
            count++;
        }
    }
    printf("count = %6d\n", count);

    return 0;
}

Теперь во второй половине процедуры будет прочитан весь массив целых чисел, поэтому в соответствии с пространственной локализацией ЦП должен заранее загрузить их в кэш. Но сколько массива можно / нужно / должно загружать в кеш в любой момент цикла? Одна строка кэша за раз (64 байта / 4 байта на целое число = 16 целых), большие блоки или весь массив одним махом?

Кроме того, насколько я понимаю, задержка, связанная с загрузкой данных из ОЗУ в кэш (или, согласно учебнику, из нелокальной в локальную память), может быть гораздо более значительной, чем время, необходимое для фактического запуска подпрограммы. Правда?

Теперь допустим, что мы переместили этот код на многопроцессорную / многоядерную машину, и счетная часть кода была изменена для работы в 4, 8, 16 и т. Д. Параллельных потоках (с использованием pthreads), считая отдельные части массива, затем добавляя частные подсчеты вместе в конце. Может ли это вызвать множественные отдельные задержки ОЗУ к кешу, в результате чего параллельная версия будет работать медленнее, чем последовательная?

1 ответ

Решение

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

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

Например, возьмем четырехъядерный чип, подключенный к одному банку оперативной памяти. Если алгоритм требует максимальной скорости чтения из памяти и вычисления всегда быстрее, чем скорость ОЗУ, параллельная работа ничего не даст и, вероятно, замедлит работу.

Но если у вас система с двумя сокетами, каждый процессор будет иметь свою собственную оперативную память, и алгоритм будет ускоряться.

Или система может обновить с 1 банка оперативной памяти до 4 и переключиться с одноканальной конфигурации на четырехканальную оперативную память. В этот момент скорость ОЗУ может превысить скорость вычислений, и четырехъядерное ядро ​​получит выгоду от запуска большего количества потоков.

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

Другие вопросы по тегам