Эффективная компоновка и сокращение виртуальных двухдисковых данных (аннотация)

Ответ 1

Во-первых, я был озадачен на мгновение, почему (N**2 - N)/2 дал 27 для N = 7... но для индексов 0-7, N = 8 и 28 элементов в P. Не пытайтесь ответить на вопросы как это так поздно в тот же день.: -)

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

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

#include <cstdlib>
#include <cstdio>

const int N = 7;
const float input_values[N] = { 3.0F, 5.0F, 7.0F, 11.0F, 13.0F, 17.0F, 23.0F };
float P[N][N];      // Yes, I'm wasting half the array.  This way I don't have to fuss with mapping the indices.
float result1[N] = { 0.0F, 0.0F, 0.0F, 0.0F, 0.0F, 0.0F, 0.0F };
float result2[N] = { 0.0F, 0.0F, 0.0F, 0.0F, 0.0F, 0.0F, 0.0F };

float f(float arg1, float arg2)
{
    // Arbitrary computation
    return (arg1 * arg2);
}

float compute_result(int index)
{
    float row_sum = 0.0F;
    float col_sum = 0.0F;
    int row;
    int col;

    // Compute the row sum
    for (col = (index + 1); col < N; col++)
    {
        row_sum += P[index][col];
    }

    // Compute the column sum
    for (row = 0; row < index; row++)
    {
        col_sum += P[row][index];
    }

    return (row_sum - col_sum);
}

void direct_approach()
{
    int row;
    int col;

    for (row = 0; row < N; row++)
    {
        for (col = (row + 1); col < N; col++)
        {
            P[row][col] = f(input_values[row], input_values[col]);
        }
    }

    int index;

    for (index = 0; index < N; index++)
    {
        result1[index] = compute_result(index);
    }
}

void refined_approach()
{
    float row_sums[N];
    float col_sums[N];
    int index;

    // Initialize intermediate arrays
    for (index = 0; index < N; index++)
    {
        row_sums[index] = 0.0F;
        col_sums[index] = 0.0F;
    }

    // Compute the row and column sums
    // This can be parallelized by computing row and column sums
    //  independently, instead of in nested loops.
    int row;
    int col;

    for (row = 0; row < N; row++)
    {
        for (col = (row + 1); col < N; col++)
        {
            float computed = f(input_values[row], input_values[col]);
            row_sums[row] += computed;
            col_sums[col] += computed;
        }
    }

    // Compute the result
    for (index = 0; index < N; index++)
    {
        result2[index] = row_sums[index] - col_sums[index];
    }
}

void print_result(int n, float * result)
{
    int index;

    for (index = 0; index < n; index++)
    {
        printf("  [%d]=%f\n", index, result[index]);
    }
}

int main(int argc, char * * argv)
{
    printf("Data reduction test\n");

    direct_approach();

    printf("Result 1:\n");
    print_result(N, result1);

    refined_approach();

    printf("Result 2:\n");
    print_result(N, result2);

    return (0);
}

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

Чтобы справиться с проблемой пропуска: если это просто вопрос "не использовать входные значения x, y и z", вы можете хранить x, y и z в массиве do_not_use и проверять эти значения, когда чтобы вычислить суммы. Если значения, которые нужно пропустить, являются некоторой функцией строки и столбца, вы можете сохранить их как пары и проверить пары.

Надеюсь, это даст вам идеи для вашего решения!

Обновить, теперь, когда я проснулся: Работа с "пропуском" зависит от того, какие данные нужно пропустить. Другая возможность для первого случая - "не использовать входные значения x, y и z" - гораздо более быстрое решение для больших наборов данных заключалось бы в том, чтобы добавить уровень косвенности: создать еще один массив, этот целочисленный индекс, и хранить только индексы хороших входных данных. F'r, если неверные данные находятся во вставках 2 и 5, допустимым массивом будет:

int valid_indices[] = { 0, 1, 3, 4, 6 };

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

Назад к распараллеливанию - независимо от того, что вы будете иметь дело с (N ** 2 - N)/2 вычислениями of f(). Одна из возможностей заключается в том, чтобы просто принять, что будет спор за сумму массивов, что не будет большой проблемой, если вычисление f() займет значительно больше времени два дополнения. Когда вы попадаете на очень большое количество параллельных путей, снова будет проблемой, но должно быть "сладкое пятно", уравновешивающее количество параллельных пути против времени, необходимого для вычисления f().

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

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

Ответ 2

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

Итак... здесь мы идем!

Основная проблема

Мне кажется, что вы можете определить свою функцию результата несколько иначе, и она поднимет хотя бы некоторое противоречие с вашими промежуточными значениями. Предположим, что ваша матрица P имеет нижнюю треугольную форму. Если вы (фактически) заполняете верхний треугольник отрицательным нижним значением (и главной диагональю со всеми нулями), вы можете переопределить каждый элемент вашего результата в виде суммы одной строки: (здесь показано для N = 4, а где -i означает отрицательный результат в ячейке, отмеченной как i)

 P     0    1    2    3 
   |--------------------
  0|   x   -0   -1   -3
   |
  1|   0    x   -2   -4
   |
  2|   1    2    x   -5
   |
  3|   3    4    5    x

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

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

Значения пропуска

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

Чтобы работать со схемой, предложенной выше, я считаю, что вы должны сохранить пропущенные элементы как пары (row, col), и вам также нужно добавить транспонированную каждую пару координат (так что у вас будет вдвое больше пропущенные значения.) Таким образом, ваш примерный список пропусков P[6], P[14] and P[18] становится P(4,0), P(5,4), P(6,3), который затем становится P(4,0), P(5,4), P(6,3), P(0,4), P(4,5), P(3,6).

Затем вы сортируете этот список, сначала на основе строки, а затем столбца. Это делает наш список P(0,4), P(3,6), P(4,0), P(4,5), P(5,4), P(6,3).

Если каждая строка вашей виртуальной матрицы P обрабатывается одним потоком (или одним экземпляром вашего ядра или что-то еще), вы можете передать ему значения, которые ему нужно пропустить. Лично я бы сохранил все это в большом массиве 1D и просто передал в первом и последнем индексе, в которые должен был бы быть рассмотрен каждый поток (я бы также не сохранил индексы строк в последнем массиве, в который я прошел, поскольку он может неявно выведено, но я думаю, что это очевидно.) В приведенном выше примере для N = 8 пары начала и конца, переданные каждому потоку, будут: (обратите внимание, что конец один за конечным значением, необходимым для обработки, просто как STL, поэтому пустой список обозначается begin == end)

Thread 0: 0..1
Thread 1: 1..1 (or 0..0 or whatever)
Thread 2: 1..1
Thread 3: 1..2
Thread 4: 2..4
Thread 5: 4..5
Thread 6: 5..6
Thread 7: 6..6

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

Псевдо-реализация

Я не знаю CUDA, но у меня есть некоторый опыт работы с OpenCL, и я думаю, что интерфейсы схожи (поскольку аппаратное обеспечение, на которое они нацелены, одинаковое.) Здесь реализована реализация ядра, выполняющего обработку для строка (т.е. вычисляет одну запись result) в псевдо-С++:

double calc_one_result (
    unsigned my_id, unsigned N, double const init_values [],
    unsigned skip_indices [], unsigned skip_begin, unsigned skip_end
)
{
    double res = 0;
    for (unsigned col = 0; col < my_id; ++col)
        // "f" seems to take init_values[column] as its first arg
        res += f (init_values[col], init_values[my_id]);
    for (unsigned row = my_id + 1; row < N; ++row)
        res -= f (init_values[my_id], init_values[row]);
    // At this point, "res" is holding "result[my_id]",
    // including the values that should have been skipped

    unsigned i = skip_begin;
    // The second condition is to check whether we have reached the
    // middle of the virtual matrix or not
    for (; i < skip_end && skip_indices[i] < my_id; ++i)
    {
        unsigned col = skip_indices[i];
        res -= f (init_values[col], init_values[my_id]);
    }
    for (; i < skip_end; ++i)
    {
        unsigned row = skip_indices[i];
        res += f (init_values[my_id], init_values[row]);
    }

    return res;
}

Обратите внимание на следующее:

• Семантика init_values и функция f соответствуют описанному вопросом.
• Эта функция вычисляет одну запись в массиве result; в частности, он вычисляет result[my_id], поэтому вы должны запустить экземпляры N этого.
• Единственная общая переменная, которую она записывает, - это result[my_id]. Ну, вышеприведенная функция ничего не пишет, но если вы переведете ее в CUDA, я думаю, вам придется писать об этом в конце. Однако никто не пишет этому конкретному элементу result, поэтому эта запись не вызовет каких-либо утверждений о расходе данных.
• Два входных массива init_values и skipped_indices разделяются между всеми запущенными экземплярами этой функции.
• Все обращения к данным являются линейными и последовательными, за исключением пропущенных значений, которые, я считаю, неизбежны.

• skipped_indices содержат список индексов, которые должны быть пропущены в каждой строке. Это содержимое и структура, как описано выше, с одной небольшой оптимизацией. Поскольку не было необходимости, я удалил номера строк и оставил только столбцы. Номер строки будет передан в функцию как my_id в любом случае, а срез массива skipped_indices, который должен использоваться каждым вызовом, определяется с помощью skip_begin и skip_end.

  В приведенном выше примере массив, который передается во все вызовы calc_one_result, будет выглядеть так: [4, 6, 0, 5, 4, 3].

• Как вы можете видеть, отдельно от циклов единственная условная ветвь в этом коде skip_indices[i] < my_id в третьем for-loop. Хотя я считаю, что это безобидно и полностью предсказуемо, даже эту ветку можно легко избежать в коде. Нам просто нужно передать другой параметр skip_middle, который сообщает нам, где пропущенные элементы пересекают главную диагональ (т.е. Для строки # my_id, индекс в skipped_indices[skip_middle] является первым, который больше, чем my_id).

В заключение

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

Стоимость реализации:

• Вызов f в два раза больше времени (и отслеживание, когда он вызывается для row < col, чтобы вы могли умножить результат на -1.)
• Сохранение в списке пропущенных значений вдвое больше элементов. Поскольку размер этого списка находится в тысячах (а не на миллиардах!), Это не должно быть большой проблемой.
• Сортировка списка пропущенных значений; который снова из-за его размера, не должен быть проблемой.

( ОБНОВЛЕНИЕ: добавлен раздел "Псевдо-реализация".)