среда, 27 мая 2009 г.

Day 2: Genetics Algorithms On GPU

или gpgpgpu.

Генетические алгоритмы на GPU

Вкратце о том, как реализовать ГА на gpu.
При реализации на CPU у нас есть M хромосом (или популяция), в каждой из которой N ген.



При реализации на GPU популяция представляется в виде множества потоков (текстур), где каждый элемент потока (rgba, в зависимости от формата текстуры) является отдельным геном(или 4, если rgba). Количество потоков равно количеству ген в хромосоме, а количество генов в одном потоке определяет размер популяции. Т.е. получаем 3д сетку вида:



Данное представление позволяет эффективно реализовать операторы скрещивания, мутации и замещения. Основными плюсами является то, что для каждого элемента потока (гена) требуется выборка только k ближайших соседей, что эффективно использует текстурный кеш видеокарты. Кроме того, можно упаковать и обработать до 4 ген(float) в одном элементе потока.
Если целевую функцию довольно просто посчитать в kernel, то удается избежать медленную передачу данных из GPU в CPU, поскольку тогда все данные (значения фитнеса) хранятся в видеопамяти. В противном случае необходимо оценить затраты на чтение/запись значений фитнеса, посчитанного на CPU и передаваемого на GPU, поскольку время записи/чтения может превысить весь суммарный эффект от распараллеливания.

Оператор скрещивания. На входе элемент потока и информация о k( на рисунке 4 соседа) соседях слева, справа, вверху, внизу. На выходе элемент потока.



С некоторой вероятностью скрещиваются две хромосомы, одна из которых является текущей, другая - с лучшим фитнесом среди k соседних. В результате скрещивания получается один потомок.

Оператор мутации. На входе/выходе элемент потока.
Любой оператор мутации реализуемый на CPU подойдет. Например, простейший для RCGA – добавление случайного числа из нормального распределения. В glsl коде это Rand текстура с этими значениями.

#extension GL_ARB_texture_rectangle : enable
uniform sampler2DRect OldPopulation;
uniform sampler2DRect Rand;
uniform vec4 Up;
uniform vec4 Down;

void main()
{
vec4 cell = texture2DRect(OldPopulation, gl_TexCoord[0].st);

vec4 rnd = texture2DRect(Rand, gl_TexCoord[1].st);

cell += rnd;

gl_FragColor = clamp(cell, Up, Down);
}
_Winnie C++ Colorizer


Оператор замещения. На входе поток с информацией о фитнессе, поток с популяцией до мутации и после. На выходе новая популяция.

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

Параллельно для M хромосом выполнить:
1. Оператор скрещивания для N потоков, где N – количество генов.
2. Оператор мутации для N потоков. На выходе N новых потоков.
3. Подсчет фитнеса
4. Замещение

В реализации без CUDA, для шага 1,2,4 понадобится N проходов(render passes) и промежуточные текстуры для хранения результатов. Для шага 3 необходим всего один проход с информацией о всех N текстурах. Кроме того, необходима текстура со случайными числами, которая либо обновляется в каждой эпохе, либо выборка в mutation kernel происходит со случайных элементов (при этом значения остаются неизменными) потока этой текстуры. Такой случайный элемент задается с помощью случайных текстурных координат.

Такая реализация имеет следующее ограничения:

Количество потоков(текстур) ограничено.
Если функция фитнесса сложная, то может не хватить команд в kernel, тогда необходимо разбивать обработку потока на несколько kernels(или N проходов).
Позже код и дополнения.

понедельник, 25 мая 2009 г.

Day 1: Intro

Буду писать о gamedev, эвристике, NP-задачах, вообщем тем, чем сейчас занимаюсь. Надеюсь это будет происходить часто и доступно.