这将是一个漫长的故事,但也许你们中的一些人想研究这个案例。
我正在开发并行图算法。我选择了一个名为STINGER的尖端 HPC 并行图数据结构。STINGER 的使命宣言如下:
“STINGER 应该提供一个通用的抽象数据结构,以便大型图社区可以快速利用彼此的研究进展。[...] 为 STINGER 编写的算法可以很容易地在多种语言和框架之间进行翻译/移植 [...]认识到没有一种数据结构对每个图算法都是最优的。STINGER 的目标是配置一个可以很好地运行大多数算法的合理数据结构。与跨领域的另一种通用数据结构相比,使用 STINGER 应该不会显着降低性能一套广泛的典型图算法。”
STINGER 可能相当高效并且适用于共享内存并行。另一方面,它不是很抽象、通用或简洁。STINGER 提供的接口对我来说并不令人满意,原因有几个: 它太冗长(函数需要对我来说并不重要的参数);它只模拟一个有向图,而我需要一个无向图;和其他原因。
但是,我不敢自己实现一个新的并行图数据结构。
所以我已经开始用我自己的Graph
类封装一个 STINGER 实例。例如,要检查是否存在无向边,我现在可以调用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, {...})
where{...}
只是一个函数,一个闭包或一个“代码块”,然后将被适当地执行。但是,我缺乏实现这一点的 C++ 经验。我想知道你能在这个问题上给我什么建议。也许还有“你应该使用宏,因为......”。