February 15th, 2009

with Cat The Cat

Снова разное.

Один из моих любимых афоризмов:
"If you want to know what God thinks of money, just look at the people he gave it to."
  --  Dorothy Parker
Оказывается, ей же принадлежит и афоризм "The two most beautiful words in the English language are 'check enclosed.'"

Был удивлён, обнаружив.

Третий раз постирал флешку. Она работает!

Был удивлён, обнаружив.

Collapse )
with Cat The Cat

Ешё немного про параллельные вычисления.

В 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 это, оказывается, уже есть в стандартной библиотеке.

По-моему, это замечательно. ;)