Альтернатива макросам для параллельной итерации?

Это будет длинная история, но, возможно, некоторые из вас хотели бы изучить этот случай.

Я работаю над разработкой алгоритма параллельного графа. Я выбрал передовую структуру данных параллельного графа HPC с именем ЖАЛО. Миссия STINGER гласит:

«STINGER должен предоставить общую абстрактную структуру данных, чтобы
большое графическое сообщество может быстро использовать исследования друг друга
разработки. […] Алгоритмы, написанные для STINGER, могут быть легко
переведено / портировано между несколькими языками и фреймворками […] Это
признается, что ни одна структура данных не является оптимальной для каждого графика
алгоритм. Цель STINGER — настроить разумные данные
структура, которая может хорошо работать большинство алгоритмов. Там не должно быть
значительное снижение производительности при использовании STINGER по сравнению с
другая общая структура данных в широком наборе типичных графиков
Алгоритмы «.

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

Тем не менее, я уклоняюсь от реализации новой структуры данных параллельного графа самостоятельно.

Так что я уже начал инкапсулировать экземпляр STINGER своим собственным Graph учебный класс. Например, чтобы проверить, существует ли неориентированное ребро, я могу теперь вызвать Graph::hasEdge(node u, node v) вместо записи в мои алгоритмы:

int to = stinger_has_typed_successor(stinger, etype, u, v);
int back = stinger_has_typed_successor(stinger, etype, v, u);
bool answer = to && back;

Пока что это сработало хорошо. Теперь к теме итерации.

STINGER реализует обход (итерация по узлам, ребрам, падающим ребрам узла и т. Д.) С помощью макросов. Например, вы пишете

STINGER_PARALLEL_FORALL_EDGES_BEGIN(G.asSTINGER(), etype) {
node u = STINGER_EDGE_SOURCE;
node v = STINGER_EDGE_DEST;
std::printf("found edge (%d, %d)", u, v);
} STINGER_PARALLEL_FORALL_EDGES_END();

Вот STINGER_PARALLEL_FORALL_EDGES_BEGIN расширяется до

do {                                    \
\
\
for(uint64_t p__ = 0; p__ < (G.asSTINGER())->ETA[(etype)].high; p__++) {    \
struct stinger_eb *  current_eb__ = ebpool + (G.asSTINGER())->ETA[(etype)].blocks[p__]; \
int64_t source__ = current_eb__->vertexID;            \
int64_t type__ = current_eb__->etype;             \
for(uint64_t i__ = 0; i__ < stinger_eb_high(current_eb__); i__++) { \
if(!stinger_eb_is_blank(current_eb__, i__)) {                   \
struct stinger_edge * current_edge__ = current_eb__->edges + i__;

Макрос скрывает кишки структуры данных, которые, по-видимому, должны быть полностью открыты для эффективной (параллельной) итерации. Есть макросы для различных комбинаций, в том числе STINGER_FORALL_EDGES_BEGIN, STINGER_READ_ONLY_FORALL_EDGES_BEGIN, STINGER_READ_ONLY_PARALLEL_FORALL_EDGES_BEGIN

Да, я мог бы использовать эти макросы, но мне интересно, есть ли более элегантный способ реализации итерации. Если бы я мог пожелать интерфейс, это выглядело бы как

G.forallEdges(readonly=true, parallel=true, {..})

GraphIterTools.forallEdges(G, readonly=true, parallel=true, {...})

где {...} это просто функция, замыкание или «блок кода», который затем будет выполнен соответствующим образом. Тем не менее, мне не хватает опыта C ++ для реализации этого. Интересно, что вы можете дать мне по этому вопросу? Может быть, также «Вы должны пойти с макросами, потому что …».

4

Решение

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

template<typename Callback>
void forallEdges(int etype, Callback callback)
{
STINGER_PARALLEL_FORALL_EDGES_BEGIN(this->asSTINGER(), etype) {
node u = STINGER_EDGE_SOURCE;
node v = STINGER_EDGE_DEST;

// call the supplied callback
callback(u, v);

} STINGER_PARALLEL_FORALL_EDGES_END();
}

Затем определите функцию обратного вызова и передайте ее новому методу:

void my_callback(node u, node v) { ... }
...
G.forallEdges(etype, my_callback);

Или в C ++ 11 вы можете использовать лямбда-функцию:

G.forallEdges(etype, [](node u, node v) { ... });
2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]