Ешё немного про параллельные вычисления.
В stream-kernel модели параллельных вычислений различают два вида операций: отображение и свёртку.
Отображение - это вычисление значений какого-то массива, как функции от индексов элемента в массиве-результате и некоторого набора неизменяемых параметров. Неизменяемых, конечно, только на время работы операции.
Например, усреднение одного массива в другой будет выглядеть вот так (условно):
kernel float average2x2(float source[][]) {
int i,j;
i = dest_coord(0);
j = dest_coord(1);
return (source[i*2][j*2]+source[i*2+1][j*2]
+source[i*2][j*2+1]+source[i*2+1][j*2+1]
)/4;
} /* average2x2 */
...
float image[2*N][2*N];
float averaged[N][N];
averaged = average2x2(image);
Условно потому, что я давно уже не брал в руки BrookGPU. ;)
На отображениях можно делать много полезных вещей.
Например, можно сортировать данные с помощью двухцветной сортировки. Сложность получается не O(NlogN), а O(Nlog2N), зато параллелизм очень высокий и можно использовать неполноценные GPU.
Свертки используются для получения скалярной информации из большого массива.
Свертка получает на вход значение из сворачиваемого массива и результат предыдущих операций свёртки. Типы результата и массива должны совпадать, для знающих Хаскель это будет выглядеть, как reduce :: (a -> a -> a) -> [a] -> a, и про список (массив) известно, что он не пуст.
Функция свёртки должна быть ассоциативно-коммутативной: f(a,b) = f(b,a) и f(f(a,b),c) = f(a,f(b,c)). Только в этом случае результат работы свёртки над массивом не будет зависить от порядка вычислений, что необходимо для параллельной работы.
К таким функциям относятся сложение, умножение, минимум и максимум, из того, что приходит в голову сразу. Минимум и максимум интересные ещё и тем, что могут быть определены по разному - с учётом порядка индексов и без него, и чтобы понять, какой вариант более правильный, надо думать.
Вообще, когда мы изучали BrookGPU в ИТМиВТ, мы думали на тему автоматической проверки ассоциативности и коммутативности операций свёртки, но так ничего и не придумали.
А в Agda2 это, оказывается, уже есть в стандартной библиотеке.
По-моему, это замечательно. ;)
Отображение - это вычисление значений какого-то массива, как функции от индексов элемента в массиве-результате и некоторого набора неизменяемых параметров. Неизменяемых, конечно, только на время работы операции.
Например, усреднение одного массива в другой будет выглядеть вот так (условно):
kernel float average2x2(float source[][]) {
int i,j;
i = dest_coord(0);
j = dest_coord(1);
return (source[i*2][j*2]+source[i*2+1][j*2]
+source[i*2][j*2+1]+source[i*2+1][j*2+1]
)/4;
} /* average2x2 */
...
float image[2*N][2*N];
float averaged[N][N];
averaged = average2x2(image);
Условно потому, что я давно уже не брал в руки BrookGPU. ;)
На отображениях можно делать много полезных вещей.
Например, можно сортировать данные с помощью двухцветной сортировки. Сложность получается не O(NlogN), а O(Nlog2N), зато параллелизм очень высокий и можно использовать неполноценные GPU.
Свертки используются для получения скалярной информации из большого массива.
Свертка получает на вход значение из сворачиваемого массива и результат предыдущих операций свёртки. Типы результата и массива должны совпадать, для знающих Хаскель это будет выглядеть, как reduce :: (a -> a -> a) -> [a] -> a, и про список (массив) известно, что он не пуст.
Функция свёртки должна быть ассоциативно-коммутативной: f(a,b) = f(b,a) и f(f(a,b),c) = f(a,f(b,c)). Только в этом случае результат работы свёртки над массивом не будет зависить от порядка вычислений, что необходимо для параллельной работы.
К таким функциям относятся сложение, умножение, минимум и максимум, из того, что приходит в голову сразу. Минимум и максимум интересные ещё и тем, что могут быть определены по разному - с учётом порядка индексов и без него, и чтобы понять, какой вариант более правильный, надо думать.
Вообще, когда мы изучали BrookGPU в ИТМиВТ, мы думали на тему автоматической проверки ассоциативности и коммутативности операций свёртки, но так ничего и не придумали.
А в Agda2 это, оказывается, уже есть в стандартной библиотеке.
По-моему, это замечательно. ;)