Копирование дерева в память GPU

Question

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

struct Node
{
    char *NodeName;
    int NumberOfChildren;
    Node *Children;
    Node *Parent; 
}

каждый узел имеет динамическое число дочерних элементов, но имеет одного родителя.как я могу скопировать это дерево в глобальную память CUDA?я должен BFS через дерево и распределять / копировать данные в GPU?или я могу использовать одну инструкцию копирования памяти cuda?

Answer 1

Я не уверен в источнике ваших данных, но вы могли бы использовать плоское пространство памяти и использовать смещение индекса в качестве индекса для доступа к памяти.

т.е.

Узел будетбыть определенным как:

struct Node
{
    unsigned int name;
    unsigned int number_of_children;
    unsigned int parent;
    unsigned int children;
}

Вы бы поместили один большой блок памяти и построили там свое дерево.(Сохраняйте счетчик памяти последнего места, куда вы вставили элемент).

Вы также делаете это для добавления строк.

Таким образом, у вас будет один непрерывный кусок памяти, и он будетбыть простой копией памяти.Доступ к элементам, с которыми будет работать простое приведение.

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

Питер.

PS: инженер по встраиванию не программист CUDA, но столкнулся с похожими проблемами, перемещая деревья по процессорам без необходимости разбора.

Answer 2

Как правило, вы хотите использовать одну копию памяти, так как несколько маленьких копий снизят производительность. Вероятно, правильнее всего будет отслеживать общий размер, необходимый при вставке в дерево (или обходить дерево для его вычисления), распределять эту (или большую) сумму, а затем выполнять одну передачу данных. Если позднее вам потребуется скопировать дерево большего размера, чем было выделено, освободите эту память и выделите новый фрагмент.

К сожалению, все указатели в gpu будут недействительными, поэтому вы можете расширить свою структуру до чего-то вроде:

struct Node
{
    char *NodeName;
    int NumberOfChildren;
    Node *Children;    /* children on host */
    Node *Parent;      /* parent on host */
    Node *d_children;  /* children on device */
    Node *d_parent;    /* parent on device */
}

, а затем пройтись по дереву после выделения, назначив новые узлы.

С точки зрения производительности, вы определенно хотите избежать нескольких небольших передач данных.