Geek Answers Handbook

Trace a graph in parallel

I am reviewing the exam (still) and come across a question (posted below) that puzzled me. I think that in the summary the question arises: "Think of any_old_process, which should cross the graph and do some work on the found objects, including adding more work." My question is: what data structure can be parallelized to achieve the goals set in the question?

The role of the garbage collector (GC) is to reclaim unused memory. Trace collectors must identify all living objects by crossing the plots of objects caused by aggregation relationships. In short, the GC has some worklist to accomplish. He repeatedly (a) acquires a task (for example, an object for verification), (b) performs a task (for example, marks an object if it is not already marked), and (c) creates additional tasks (for example, adds children of an unmarked task to the work list). it is advisable to parallelize this operation.

In a single-threaded environment, a worklist is usually a single LIFO stack. What would you need to make it safe for parallel GC? Will it be a reasonable design for parallel GC? A discussion of data structure designs to support parallel GC that will scale better. Explain why you would expect them to scale better.

+6
source share
2 answers

The natural data structure for a graph is a graph, i.e. a set of graph elements (nodes) that can refer to other elements. Although, for better cache reuse, elements can be placed / allocated to an array or arrays (usually vectors) to place neighboring elements as close to memory as possible. As a rule, each element or group of elements should have a mutex (spin_mutex) to protect access to it, which means that some other thread is busy working on it, so there is no need to wait. Although, if possible, the atomic operation on the flag / state fields is preferable to mark the element that was visited without blocking. For example, the simplest data structure might be as follows:

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

Given this data structure and the way GC describes how it works, it is ideal for recursive parallelism such as the division and rest pattern :

 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 } }

If the data structure in question is how the tasks are organized. I would recommend a work scheduler (for example, tbb or cilk . From articles on this topic. Simply put, each workflow has its own, but divided task task, and when the deck is empty, the thread takes tasks from other requirements.

Scalability comes from the property that each task can add some other tasks that can work in prarallel ..

+6
source

Your questions:

  • Think about any_old_process, which should cross the graph and do some work on the found objects, including adding more work.
  • ... what data structure can be parallelized to achieve the goals set in the question?

Quotes:

  • Some things about garbage collection.

Since you are particularly interested in parallelizing graph algorithms, I will give an example of one type of graph traversal that can be well parallelized.

Summary

Finding local minima ("pools") or maxima ("peaks") are useful operations in digital image processing. A concrete example is the analysis of the geological watershed. One approach to the problem is considering each pixel or a small group of pixels in the image as a node and finding non-overlapping minimum spanning trees (MSTs) with local minima as the roots of the tree.

Mountain Details

The following is a simplified example. This question from a web interview from Palantir Technologies led to Puzzle Programming and Code Golf AnkitSablok . This is simplified by two assumptions ( in bold ):

  • That a pixel / cell has only 4 neighborhoods instead of the usual eight.
  • The cell has all the neighbors in the mountains (these are local minima) or has a unique satellite. Ie, plains are not allowed.

Below is some javascript that solves this problem. It violates every reasonable coding standard against the use of side effects , but illustrates where there are some possibilities for parallelization.

If you want to delve deeper into parallelizing MSTs, see “Scalable Parallel Computation of Minimum Forest Petals”, Nobari, Cao, arras, Bressan, 2012 . The first two pages provide a clear and concise overview of the field.

Simplified example

A group of farmers has some elevation data and was about to help them understand how rainfall flows on their farmland. We well represent the earth as a two-dimensional array of heights and use the following model based on the idea that water flows downhill:

If the cells of four neighboring cells have higher heights, we call this cell a sink ; water is collected in the sinks. Otherwise, water will flow into the next cell with the lowest height. If the cell is not a receiver, you can assume that it has a unique younger neighbor and that this neighbor will be smaller than the cell.

Cells that drain into the same sink - directly or indirectly - are considered part of the same pool.

Your task is to break the map into pools. In particular, given the height map, your code should split the map into pools and display the sizes of the pools in descending order.

Suppose the height maps are square. Input begins with a line with a single integer, S, height (and width) of the map. The next S lines will contain a map line, each of which has S integers - the heights of S-cells in a line. Some farmers have small plots, such as the examples below, while some have larger plots. However, in no case does the farmer have a plot of land larger than S = 5000.

Your code should list the pool sizes in descending order. (Intermediate spaces are ignored.)

Here is an example:

 Input: 5 1 0 2 5 8 2 3 4 7 9 3 5 7 8 9 1 2 5 4 2 3 3 5 2 1 Output: 11 7 7 The basins, labeled with A's, B's, and C's, are: AAAAA AAAAA BBACC BBBCC BBCCC 



 // lm.js - find the local minima // Globalization of variables. /* The map is a 2 dimensional array. Indices for the elements map as: [0,0] ... [0,n] ... [n,0] ... [n,n] Each element of the array is a structure. The structure for each element is: Item Purpose Range Comment ---- ------- ----- ------- h Height of cell integers s Is it a sink? boolean x X of downhill cell (0..maxIndex) if s is true, x&y point to self y Y of downhill cell (0..maxIndex) b Basin name ('A'..'A'+# of basins) Use a separate array-of-arrays for each structure item. The index range is 0..maxIndex. */ var height = []; var sink = []; var downhillX = []; var downhillY = []; var basin = []; var maxIndex; // A list of sinks in the map. Each element is an array of [ x, y ], where // both x & y are in the range 0..maxIndex. var basinList = []; // An unordered list of basin sizes. var basinSize = []; // Functions. function isSink(x,y) { var myHeight = height[x][y]; var imaSink = true; var bestDownhillHeight = myHeight; var bestDownhillX = x; var bestDownhillY = y; /* Visit the neighbors. If this cell is the lowest, then it the sink. If not, find the steepest downhill direction. */ function visit(deltaX,deltaY) { var neighborX = x+deltaX; var neighborY = y+deltaY; if (myHeight > height[neighborX][neighborY]) { imaSink = false; if (bestDownhillHeight > height[neighborX][neighborY]) { bestDownhillHeight = height[neighborX][neighborY]; bestDownhillX = neighborX; bestDownhillY = neighborY; } } } if (x !== 0) { // upwards neighbor exists visit(-1,0); } if (x !== maxIndex) { // downwards neighbor exists visit(1,0); } if (y !== 0) { // left-hand neighbor exists visit(0,-1); } if (y !== maxIndex) { // right-hand neighbor exists visit(0,1); } downhillX[x][y] = bestDownhillX; downhillY[x][y] = bestDownhillY; return imaSink; } function exploreBasin(x,y,currentSize,basinName) { // This cell is in the basin. basin[x][y] = basinName; currentSize++; /* Visit all neighbors that have this cell as the best downhill path and add them to the basin. */ function visit(x,deltaX,y,deltaY) { if ((downhillX[x+deltaX][y+deltaY] === x) && (downhillY[x+deltaX][y+deltaY] === y)) { currentSize = exploreBasin(x+deltaX,y+deltaY,currentSize,basinName); } return 0; } if (x !== 0) { // upwards neighbor exists visit(x,-1,y,0); } if (x !== maxIndex) { // downwards neighbor exists visit(x,1,y,0); } if (y !== 0) { // left-hand neighbor exists visit(x,0,y,-1); } if (y !== maxIndex) { // right-hand neighbor exists visit(x,0,y,1); } return currentSize; } // Read map from file (1st argument). var lines = $EXEC('cat "' + $ARG[0] + '"').split('\n'); maxIndex = lines.shift() - 1; for (var i = 0; i<=maxIndex; i++) { height[i] = lines.shift().split(' '); // Create all other 2D arrays. sink[i] = []; downhillX[i] = []; downhillY[i] = []; basin[i] = []; } for (var i = 0; i<=maxIndex; i++) { print(height[i]); } // Everyone decides if they are a sink. Create list of sinks (ie roots). for (var x=0; x<=maxIndex; x++) { for (var y=0; y<=maxIndex; y++) a if (sink[x][y] = isSink(x,y)) { // This node is a root (AKA sink). basinList.push([x,y]); } } } //for (var i = 0; i<=maxIndex; i++) { print(sink[i]); } // Each root explores it basin. var basinName = 'A'; for (var i=basinList.length-1; i>=0; --i) { // i-- makes Closure Compiler sad var x = basinList[i][0]; var y = basinList[i][5]; basinSize.push(exploreBasin(x,y,0,basinName)); basinName = String.fromCharCode(basinName.charCodeAt() + 1); } for (var i = 0; i<=maxIndex; i++) { print(basin[i]); } // Done. print(basinSize.sort(function(a, b){return ba}).join(' '));
+3
source

More articles:


All Articles