CUDA — Генерация последовательности Халтона параллельно
Я хочу написать ядро в CUDA, которое будет генерировать последовательность Хэлтона параллельно, с 1 значением, сгенерированным и сохраненным каждым потоком.
Глядя на последовательность, кажется, что создание каждого последующего значения в последовательности включает в себя работу, проделанную при создании предыдущего значения. Генерация каждого значения с нуля потребует избыточной работы и приведет к большому разрыву между временами выполнения потоков.
Есть ли способ сделать это с параллельным ядром, которое улучшает последовательный алгоритм? Я действительно новичок в параллельном программировании, так что извините за вопрос, если ответ — это какой-то известный шаблон.
Примечание: я нашел эта ссылка в учебнике (который использует его без описания того, как он работает), но ссылка на файл там мертвая.
Решение
Последовательность Халтона генерируется:
- получить представление i в системе счисления base-p
- обратный порядок бит
Например, последовательность Halton с основанием 2:
index binary reversed result
1 1 1 1 / 10 = 1 / 2
2 10 01 01 / 100 = 1 / 4
3 11 11 11 / 100 = 3 / 4
4 100 001 001 / 1000 = 1 / 8
5 101 101 101 / 1000 = 5 / 8
6 110 011 011 / 1000 = 3 / 8
7 111 111 111 / 1000 = 7 / 8
Так что действительно много повторяется в побитовом обратном направлении. Первое, что мы можем сделать, это повторно использовать предыдущие результаты.
При вычислении элемента с индексом i в последовательности Халтона base-p мы сначала определяем ведущий бит и оставшуюся часть представления i-го base-p (это можно сделать путем планирования потоков в виде base-p). Тогда у нас есть
out[i] = out[remaining_part] + leading_bit / p^(length_of_i_in_base_p_representation - 1)
//"^" is used for convenience
Чтобы избежать ненужного чтения глобальной памяти, каждый поток должен обрабатывать все элементы с одинаковой «оставшейся частью», но с разным «начальным битом».
Если мы генерируем последовательность Халтона между p ^ n и p ^ (n + 1), концептуально должно быть p ^ n параллельных задач. Однако это не вызывает проблем, если мы назначаем поток с группой задач.
Дальнейшая оптимизация может быть сделана путем смешивания повторных вычислений и загрузки из памяти.
Пример кода:
Общее количество нитей должно быть p ^ m.
const int m = 3 //any value
__device__ void halton(float* out, int p, int N)
{
const int tid = ... //globally unique and continuous thread id
const int step = p^m; //you know what I mean
int w = step; //w is the weight of the leading bit
for(int n = m; n <= N; ++n) //n is the position of the leading bit
{
for(int r = tid; r < w; r += step) //r is the remaining part
for(int l = 1; l < p; ++l) //l is the leading bit
out[l*w + r] = out[r] + l/w;
w *= p;
}
}
примечание: этот пример не вычисляет первые элементы p ^ m в последовательности Halton, но эти значения все еще необходимы.
Другие решения