StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POImproving random memory access when random access is needed
text
Body
copied!<h2>The basic concept of what I am doing</h2> <p>Complete coalition structure formation problem/Combinatorial auctions. </p> <p>Given a set of N agents, which disjoint subsets of the set of agents yields the best outcome.</p> <p>E.g. <code>Agents = {a,b}</code> and their values</p> <ul> <li><code>{a} = 2</code></li> <li><code>{b} = 3</code></li> <li><code>{a,b} = 4</code></li> </ul> <p>In this instance the coalition of <code>{{a},{b}} = 5</code> would give the best outcome, where it is the pairwise disjoint subset of <code>{a,b}</code>.</p> <p>So in short the problem is about splitting a set and check if any of the splittings sum is greater than the original set. (This part is as good as it goes in terms of generating splittings and how I represent my data.)</p> <p>How I represent the data is basicly an array of values, where the index is the set configuration (a set is represented as an integer).</p> <p>For the example above:</p> <p><code>int val[4] = {0,2,3,4}</code> where set </p> <ul> <li><code>{a} = 01 = index 1</code></li> <li><code>{b} = 10 = index 2</code></li> <li><code>{a,b} = 11 = index 3</code></li> </ul> <p>So the set acts as an index in the value array.</p> <p>The problem is that this gives random memory access, given a large number of agents for which there are <code>2^n</code> values to consider. </p> <h2>SKIP HERE FOR THE MEMORY ACCESS PROBLEM</h2> <p>E.g. in the environment of 20 agents, given the set of two elements <code>10000000000000000001</code> the value for element <code>10000000000000000000</code> is 1048575 indexes away from <code>00000000000000000001</code> which is 4194300 bytes away in memory, which represent 32767 cachlines of 128 bytes of distance. Hence, horrible access pattern.</p> <p>The solutions I have tried looking for involve ordering the indexes in terms of cardinality/Hamming weight: </p> <p><a href="https://stackoverflow.com/questions/13542794/hamming-weight-based-indexing">Hamming weight based indexing</a> </p> <p><a href="https://stackoverflow.com/questions/13554747/determin-the-lexicographic-distance-between-two-integers">Determin the lexicographic distance between two integers</a></p> <p>suffer from arithmetic overhead that to my calulations will overshadow the penalty from random access. Especially <a href="https://stackoverflow.com/questions/13542794/hamming-weight-based-indexing">Hamming weight based indexing</a> as it uses many dependant calculations which gets serilized and blocks the thread.</p> <p>As a last resort I ask here again, is there any method(I know about coalescing, which is hard to do for this problem) to improve the access times when your solution is depandant on random access, or is it a helpless state?</p> <p>Currently I am around 45% instruction replay overhead becouse of that, and changing the blocksize gives no notable result. And yes I try hide the latency by calculating several coalitions per thread, which work somewhat.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload