Удобное копирование массива с перенастройкой по известному индексу, сбор, разброс

Ответ 1

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

Для сортировки с использованием кеша O (N) используйте сортировку radix с достаточно маленьким radix (не более половины числа строк кэша в кэше процессора).

Вот реализация C алгоритма, подобранного по методу radix:

void reorder2(const unsigned size)
{
    const unsigned min_bucket = size / kRadix;
    const unsigned large_buckets = size % kRadix;
    g_counters[0] = 0;

    for (unsigned i = 1; i <= large_buckets; ++i)
        g_counters[i] = g_counters[i - 1] + min_bucket + 1;

    for (unsigned i = large_buckets + 1; i < kRadix; ++i)
        g_counters[i] = g_counters[i - 1] + min_bucket;

    for (unsigned i = 0; i < size; ++i)
    {
        const unsigned dst = g_counters[g_index[i] % kRadix]++;
        g_sort[dst].index = g_index[i] / kRadix;
        g_sort[dst].value = g_input[i];
        __builtin_prefetch(&g_sort[dst + 1].value, 1);
    }

    g_counters[0] = 0;

    for (unsigned i = 1; i < (size + kRadix - 1) / kRadix; ++i)
        g_counters[i] = g_counters[i - 1] + kRadix;

    for (unsigned i = 0; i < size; ++i)
    {
        const unsigned dst = g_counters[g_sort[i].index]++;
        g_output[dst] = g_sort[i].value;
        __builtin_prefetch(&g_output[dst + 1], 1);
    }
}

Он отличается от сортировки по основанию в двух аспектах: (1) он не выполняет подсчеты, потому что все счетчики известны заранее; (2) он избегает использования значений power-of-2 для radix.

Этот код С++ использовался для бенчмаркинга (если вы хотите запустить его на 32-битной системе, слегка уменьшите константу kMaxSize).

Здесь приведены результаты тестов (на процессоре Haswell с кешем 6 Мб):

Нетрудно видеть, что малые массивы (менее ~ 2000 000 элементов) являются кэширующими даже для наивного алгоритма. Также вы можете заметить, что метод сортировки начинает оставаться неактивным в кэше в последней точке диаграммы (с size/radix около 0,75 строк кэша в кеше L3). Между этими ограничениями подход сортировки более эффективен, чем наивный алгоритм.

В теории (если мы сравниваем только пропускную способность памяти, необходимую для этих алгоритмов с 64-байтными строками кэша и 4-байтовыми значениями), алгоритм сортировки должен быть в 3 раза быстрее. На практике мы имеем гораздо меньшую разницу, около 20%. Это может быть улучшено, если мы используем меньшие 16-разрядные значения для массива data (в этом случае алгоритм сортировки примерно в 1,5 раза быстрее).

Еще одна проблема с подходом к сортировке - это худшее поведение, когда size/radix близок к некоторой мощности-2. Это может быть либо проигнорировано (потому что не так много "плохих" размеров) или исправлено, сделав этот алгоритм несколько более сложным.

Если мы увеличим количество проходов до 3, все 3 прохода используют в основном кеш L1, но пропускная способность памяти увеличивается на 60%. Я использовал этот код для получения экспериментальных результатов: TL; DR. После определения (экспериментально) наилучшего значения radix, я получил несколько лучшие результаты для размеров более 4 000 000 (где 2-х тактный алгоритм использует кеш-память L3 за один проход), но несколько худшие результаты для меньших массивов (где 2-проходной алгоритм использует L2 кеш для обоих проходов). Как и следовало ожидать, производительность для 16-разрядных данных лучше.

Заключение: разница в производительности намного меньше, чем разница в сложности алгоритмов, поэтому наивный подход почти всегда лучше; если производительность очень важна, и используются только значения 2 или 4 байта, предпочтительный подход к сортировке.

Ответ 2

data = [1, 2, 3, 4, 5, 7]

index = [5, 1, 4, 0, 2, 3]

Мы хотим создать новый массив из элементов данных в позиции из индекс. Результат должен быть

result -> [4, 2, 5, 7, 3, 1]

Один поток, один проход

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

Оба data и index получают доступ (чтение) последовательно, что уже является оптимальным для кэша ЦП. Это оставляет случайную запись, но запись в память не похожа на кеш, так как чтение от нее в любом случае.

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

Использование нескольких блоков для result - несколько потоков

Мы могли бы выделять или использовать блоки размера кэша для результата (блоки являются областями в result array) и циклически повторяться через index и data несколько раз (пока они остаются в кеше).

В каждом цикле мы тогда записываем только элементы в result, которые вписываются в текущий результат-блок. Это также будет "кэшировать" для записей тоже, но требует нескольких циклов (количество циклов может даже стать довольно высоким - т.е. size of data / size of result-block).

Вышеприведенное может быть вариантом при использовании нескольких потоков: data и index, являющихся доступными только для чтения, будут разделяться всеми ядрами на некотором уровне в кеше (в зависимости от кэш-архитектуры). Блоки result в каждом потоке были бы полностью независимыми (одному ядру никогда не приходилось ждать результата другого ядра или записи в том же регионе). Например: 10 миллионов элементов - каждый поток может работать над независимым блоком результата, например 500 000 элементов (число должно быть 2).

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

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

Ответ 3

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

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

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

Ответ 4

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

def populate(index,data,newArray,cache)
    blockSize = 1000
    for i = 0; i < size(index); i++
        //We cached this value earlier
        if i in cache
            newArray[i] = cache[i]
            remove(cache,i)
        else
            newIndex = index[i]
            newValue = data[i]
            //Check if this index is in our block
            if i%blockSize != newIndex%blockSize
                //This index is not in our current block, cache it
                cache[newIndex] = newValue
            else
                //This value is in our current block
                newArray[newIndex] = newValue

cache = {}
newArray = []
populate(index,data,newArray,cache)
populate(index,data,newArray,cache)

Анализ

Наивное решение обращается к массиву индекса и данных по порядку, но к новому массиву обращаются в случайном порядке. Поскольку новый массив случайным образом доступен, вы по существу заканчиваете O (N ^ 2), где N - количество блоков в массиве.

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

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

Позволяет себе представить, что вся информация внутри кеша существует на одном блоке и помещается в память. И пусть кеш имеет y элементов. Наивный подход был бы случайным образом доступным, по крайней мере, в раз. Основанный на блоке подход получит их во втором проходе.

Ответ 5

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

Если бы вы отсортировали индекс, но также применили те же операции к массиву индексов к массиву данных, массив данных стал бы результатом, который вы после.

Существует множество алгоритмов сортировки для выбора, все они удовлетворяют вашим критериям, не зависящим от кэша. Но их сложность меняется. Я бы рассмотрел либо quicksort, либо mergesort.

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

Ответ 6

Я обеспокоен тем, что это не может быть выигрышный шаблон.

У нас был фрагмент кода, который хорошо работал, и мы оптимизировали его, удалив копию.

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

Ответ 7

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

Я написал следующую программу, чтобы на самом деле проверить, помогает ли простое разделение цели в N блоках, и мои результаты были следующими:

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

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

Следствием этого является: Да, он более "кэширует", чем не подразделяет, но для одного потока (и только одного переупорядочения) это не поможет вам немного.

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


void main(char **ARGS,int ARGC) {
int N=1<<26;

double* source = malloc(N*sizeof(double)); 
double* target = malloc(N*sizeof(double)); 
int* idx = malloc(N*sizeof(double)); 
int i;
for(i=0;i<N;i++) {
source[i]=i;
target[i]=0;
idx[i] = rand() % N ;
};

struct timeval now,then;
gettimeofday(&now,NULL);
for(i=0;i<N;i++) {
target[idx[i]]=source[i];
};
gettimeofday(&then,NULL);
printf("%f\n",(0.0+then.tv_sec*1e6+then.tv_usec-now.tv_sec*1e6-now.tv_usec)/N);


gettimeofday(&now,NULL);
int j;
int targetblocks;
int M = 24;
int targetblocksize = 1<<M;
targetblocks = (N/targetblocksize);
for(i=0;i<N;i++) {
for(j=0;j<targetblocks;j++) {
int k = idx[i];
if ((k>>M) == j) { 
target[k]=source[i];
};
};
};
gettimeofday(&then,NULL);
printf("%d,%f\n",targetblocks,(0.0+then.tv_sec*1e6+then.tv_usec-now.tv_sec*1e6-now.tv_usec)/N);


};