Строковое расширение в openCL

Question

У меня есть простая задача расширения строки FX в соответствии со следующими правилами:

X -> X+YF+
Y-> -FX-Y

В OpenCL манипуляции со строками не поддерживаются, но используется массив символов.Как будет выглядеть программа ядра, которая параллельно расширяет эту строку в openCL?

Подробнее: Рассмотрим расширение 'FX' в приведенном ниже коде Python.

axiom = "FX"
def expand(s):
    switch = {
        "X": "X+YF+",
        "Y": "-FX-Y",
    }
    return switch.get(s, s)


def expand_once(string):
    return [expand(c) for c in string]


def expand_n(s, n):
    for i in range(n):
        s = ''.join(expand_once(s))
    return s


expanded = expand_n(axiom, 200)

Результат expanded будет результатом расширения аксиомы 'FX' в 200 раз.Это довольно медленный процесс, поэтому нужно делать это на openCL для распараллеливания.Результатом этого процесса является массив строк, которые я затем буду использовать для рисования кривой дракона.

ниже приведен пример того, как я мог бы придумать такую ​​кривую дракона: эта часть не имеет большого значения.Расширение OpenCL является важной частью.

 import turtles
    from PIL import Image
turtles.setposition(5000, 5000)
turtles.left(90)  # Go up to start.


for c in expanded:
    if c == "F":
        turtles.forward(10)
    elif c == "-":
        turtles.left(90)
    elif c == "+":
        turtles.right(90)

# Write out the image.
im = Image.fromarray(turtles.canvas)
im.save("dragon_curve.jpg")

Answer 1

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

Если вам действительно нужно делать это итеративно, задача для каждогорабочий элемент, чтобы знать, где в выходной строке разместить его результат.Один из способов сделать это - назначить рабочим группам определенную подстроку ввода и на каждой итерации вести подсчет общего числа X и Y в каждой подстроке размера рабочей группы.Из этого вы можете вычислить, насколько эта подстрока будет расширяться за одну итерацию, и если вы накапливаете эти значения, вы будете знать смещение выходных данных каждого расширения подстроки.Эффективно ли это - другой вопрос.: -)

Тем не менее, ваш алгоритм на самом деле довольно предсказуем: вы можете точно рассчитать, насколько большой будет конечная строка с заданной исходной строкой и числом итераций.Лучший способ сгенерировать эту строку с помощью OpenCL - это создать нерекурсивную функцию, которая аналитически вычисляет символ в позиции N с учетом M итераций, а затем вызывать эту функцию один раз для каждого рабочего элемента с (известным!) Финаломдлина строки как размер работы.Я не знаю, возможно ли придумать такую ​​функцию, но кажется, что это может быть, и если это возможно, это, вероятно, самый эффективный способ сделать это на GPU.

Кажется, что это возможно: насколько я могу судить, результат будет очень периодическим:

FX
FX+YF+
FX+YF++-FX-YF+
FX+YF++-FX-YF++-FX+YF+--FX-YF+
FX+YF++-FX-YF++-FX+YF+--FX-YF++-FX+YF++-FX-YF+--FX+YF+--FX-YF+
^^^^^^ ^^^^^^^ ^^^^^^^ ^^^^^^^ ^^^^^^^ ^^^^^^^ ^^^^^^^ ^^^^^^^
  A*      B       A       B       A       B       A       B

Насколько я вижу, все блоки A идентичны, как и B,(кроме первого A, который фактически находится в позиции -1). Таким образом, вы можете определить символы в 14 позициях из каждых 16 полностью детерминистически.Я сильно подозреваю, что возможно определить схему + s и - s, которая также их соединяет.Если вы поймете это, решение станет довольно простым.

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