TEK*_*TEK 6 parallel-processing concurrency multithreading traversal
我正在修改考试(仍然)并且遇到了一个让我难过的问题(如下所示).总而言之,我认为问题是"想想any_old_process必须遍历图形并对它找到的对象做一些工作,包括添加更多工作." 我的问题是,什么数据结构可以并行化以实现问题中提出的目标？
垃圾收集器(GC)的作用是回收未使用的内存.跟踪收集器必须通过遍历由聚合关系引起的对象图来识别所有活动对象.简而言之,GC有一些要执行的任务工作列表.它反复(a)获取任务(例如,要检查的对象),(b)执行任务(例如,标记对象,除非它已被标记),以及(c)生成进一步的任务(例如,添加无标记任务的子项)到工作清单).期望并行化该操作.
在单线程环境中,工作列表通常是单个LIFO堆栈.为了使并行GC安全,你需要做些什么？这对于并行GC来说是一个合理的设计吗？讨论数据结构的设计,以支持可以更好地扩展的并行GC.解释为什么你会期望它们更好地扩展.
图形的自然数据结构是图形,即可以引用其他元素的一组图形元素(节点).但是,为了更好地缓存重用,可以将元素放置/分配在一个或多个数组(通常是向量)中,以便将相邻元素尽可能地放在内存中.通常,每个元素或一组元素都应该有一个互斥锁(spin_mutex)来保护对它的访问,争用意味着其他一些线程忙于处理它,所以不需要等待.但是,如果可能的话,最好在标志/状态字段上进行原子操作,以便在没有锁定的情况下将元素标记为已访问.例如,最简单的数据结构可以是:
struct object {
vector<object*> references;
atomic<bool> is_visited; // for simplicity, or epoch counter
// if nothing resets it to false
void inspect(); // processing method
};
vector<object> objects; // also for simplicity, if it can be for real
// things like `parallel_for` would be perfect here
鉴于此数据结构和GC工作方式的描述,它非常适合递归并行,如分而治之的模式:
void object::inspect() {
if( ! is_visited.exchange(true) ) {
for( object* o : objects ) // alternatively it can be `parallel_for` in some variants
cilk_spawn o->inspect(); // for Cilk or `task_group::run` for TBB or PPL
// further processing of the object
}
}
如果问题中的数据结构是任务的组织方式.我推荐一个工作窃取调度程序(比如tbb或cilk.有很多关于这个主题的论文.简单来说,每个工作线程都有自己但共享的任务副本,当deque为空时,一个线程偷走别人的任务.
可伸缩性来自于每个任务可以添加一些其他可以在并行工作的任务的属性.
你的问题：
\n\n引用问题：
\n\n由于您对并行化图算法特别感兴趣，因此我将给出一种可以很好地并行化的图遍历的示例。
\n\n寻找局部最小值（“盆地”）或最大值（“峰值”）是数字图像处理中有用的操作。一个具体的例子是地质流域分析。解决该问题的一种方法是将图像中的每个像素或一小群像素视为一个节点，并找到以局部最小值作为树根的非重叠最小生成树 (MST)。
\n\n下面是一个简单的例子。这是Palantir Technologies 提出的网络面试问题，由AnkitSablok提供给《Programming Puzzles & Code Golf》。它通过两个假设进行了简化（下面加粗）：
\n\n下面是一些解决这个问题的 JavaScript。它违反了针对使用副作用的所有合理编码标准，但说明了存在一些并行化机会的地方。
\n\nsink[]在下面的程序中）。如果并行生成最小值/根列表，则堆栈的排队操作必须同步。有关如何对堆栈和其他队列执行此操作的讨论，请参阅“Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms”，Michael & Scott，1996。对于现代更新，请遵循 Google Scholar 上的引文树（不需要互斥:)。如果您想更深入地了解并行 MST，请参阅“可扩展并行最小生成森林计算”，Nobari，Cao，arras，Bressan，2012 年。前两页包含对该领域的清晰简明的调查。\n
\n\n一群农民有一些海拔数据，我们\xe2\x80\x99将帮助他们了解降雨如何流过他们的农田。我们\xe2\x80\x99ll 将土地表示为二维海拔数组，并基于水流向低处的思想，使用以下模型：
\n\n如果一个单元格\xe2\x80\x99的四个相邻单元格都具有较高的海拔，我们称这个单元格为汇；水聚集在水槽中。否则，水将流向海拔最低的相邻单元格。如果某个单元不是接收器，您可以假设它有一个唯一的最低邻居，并且该邻居将低于该单元。
\n\n直接或间接排入同一水槽 \xe2\x80\x93 \xe2\x80\x93 的单元称为同一盆地的一部分。
\n\n您的挑战是将地图划分为盆地。特别是，给定一张海拔图，您的代码应该将地图划分为盆地，并按降序输出盆地的大小。
\n\n假设高程图是正方形的。输入将从一行开始，其中包含一个整数 S，即地图的高度（和宽度）。接下来的 S 行将分别包含地图的一行，每行都有 S 个整数 \xe2\x80\x93，即该行中 S 个像元的高程。有些农民拥有较小的土地，如下例所示，而有些农民则拥有较大的土地。然而，在任何情况下，农民都不会拥有大于 S = 5000 的土地。
\n\n您的代码应输出以空格分隔的盆地大小列表（按降序排列）。（忽略尾随空格。）
\n\n这是一个例子：
Input:\n5\n1 0 2 5 8\n2 3 4 7 9\n3 5 7 8 9\n1 2 5 4 2\n3 3 5 2 1\n\nOutput: 11 7 7\n\nThe basins, labeled with A\xe2\x80\x99s, B\xe2\x80\x99s, and C\xe2\x80\x99s, are:\nA A A A A\nA A A A A\nB B A C C\nB B B C C\nB B C C C \n// lm.js - find the local minima\n\n\n// Globalization of variables.\n\n/*\n The map is a 2 dimensional array. Indices for the elements map as:\n\n [0,0] ... [0,n]\n ...\n [n,0] ... [n,n]\n\nEach element of the array is a structure. The structure for each element is:\n\nItem Purpose Range Comment\n---- ------- ----- -------\nh Height of cell integers\ns Is it a sink? boolean\nx X of downhill cell (0..maxIndex) if s is true, x&y point to self\ny Y of downhill cell (0..maxIndex)\nb Basin name (\'A\'..\'A\'+# of basins)\n\nUse a separate array-of-arrays for each structure item. The index range is\n0..maxIndex.\n*/\nvar height = [];\nvar sink = [];\nvar downhillX = [];\nvar downhillY = [];\nvar basin = [];\nvar maxIndex;\n\n// A list of sinks in the map. Each element is an array of [ x, y ], where\n// both x & y are in the range 0..maxIndex.\nvar basinList = [];\n\n// An unordered list of basin sizes.\nvar basinSize = [];\n\n\n// Functions.\n\nfunction isSink(x,y) {\n var myHeight = height[x][y];\n var imaSink = true;\n var bestDownhillHeight = myHeight;\n var bestDownhillX = x;\n var bestDownhillY = y;\n\n /*\n Visit the neighbors. If this cell is the lowest, then it\'s the\n sink. If not, find the steepest downhill direction.\n */\n function visit(deltaX,deltaY) {\n var neighborX = x+deltaX;\n var neighborY = y+deltaY;\n if (myHeight > height[neighborX][neighborY]) {\n imaSink = false;\n if (bestDownhillHeight > height[neighborX][neighborY]) {\n bestDownhillHeight = height[neighborX][neighborY];\n bestDownhillX = neighborX;\n bestDownhillY = neighborY;\n }\n }\n }\n if (x !== 0) {\n // upwards neighbor exists\n visit(-1,0);\n }\n if (x !== maxIndex) {\n // downwards neighbor exists\n visit(1,0);\n }\n if (y !== 0) {\n // left-hand neighbor exists\n visit(0,-1);\n }\n if (y !== maxIndex) {\n // right-hand neighbor exists\n visit(0,1);\n }\n\n downhillX[x][y] = bestDownhillX;\n downhillY[x][y] = bestDownhillY;\n return imaSink;\n}\n\nfunction exploreBasin(x,y,currentSize,basinName) {\n // This cell is in the basin.\n basin[x][y] = basinName;\n currentSize++;\n\n /*\n Visit all neighbors that have this cell as the best downhill\n path and add them to the basin.\n */\n function visit(x,deltaX,y,deltaY) {\n if ((downhillX[x+deltaX][y+deltaY] === x) && (downhillY[x+deltaX][y+deltaY] === y)) {\n currentSize = exploreBasin(x+deltaX,y+deltaY,currentSize,basinName);\n }\n return 0;\n }\n if (x !== 0) {\n // upwards neighbor exists\n visit(x,-1,y,0);\n }\n if (x !== maxIndex) {\n // downwards neighbor exists\n visit(x,1,y,0);\n }\n if (y !== 0) {\n // left-hand neighbor exists\n visit(x,0,y,-1);\n }\n if (y !== maxIndex) {\n // right-hand neighbor exists\n visit(x,0,y,1);\n }\n\n return currentSize;\n}\n\n// Read map from file (1st argument).\nvar lines = $EXEC(\'cat "\' + $ARG[0] + \'"\').split(\'\\n\');\nmaxIndex = lines.shift() - 1;\nfor (var i = 0; i<=maxIndex; i++) {\n height[i] = lines.shift().split(\' \');\n // Create all other 2D arrays.\n sink[i] = [];\n downhillX[i] = [];\n downhillY[i] = [];\n basin[i] = [];\n}\nfor (var i = 0; i<=maxIndex; i++) { print(height[i]); }\n\n// Everyone decides if they are a sink. Create list of sinks (i.e. roots).\nfor (var x=0; x<=maxIndex; x++) {\n for (var y=0; y<=maxIndex; y++) a\n if (sink[x][y] = isSink(x,y)) {\n // This node is a root (AKA sink).\n basinList.push([x,y]);\n }\n }\n}\n//for (var i = 0; i<=maxIndex; i++) { print(sink[i]); }\n\n// Each root explores it\'s basin.\nvar basinName = \'A\';\nfor (var i=basinList.length-1; i>=0; --i) { // i-- makes Closure Compiler sad\n var x = basinList[i][0];\n var y = basinList[i][5];\n basinSize.push(exploreBasin(x,y,0,basinName));\n basinName = String.fromCharCode(basinName.charCodeAt() + 1);\n}\nfor (var i = 0; i<=maxIndex; i++) { print(basin[i]); }\n\n// Done.\nprint(basinSize.sort(function(a, b){return b-a}).join(\' \'));\n| 归档时间： |
|
| 查看次数： |
1260 次 |
| 最近记录： |