How 3.6 nearly broke PostgreSQL

Posted Oct 3, 2012 8:07 UTC (Wed) by Zenith (guest, #24899)
In reply to: How 3.6 nearly broke PostgreSQL by ajb
Parent article: How 3.6 nearly broke PostgreSQL

I am not familiar with skew caches or cuckoo hashing, so I may just be restating your solution.

Would a better solution than the one suggested by Mike not be to have 3 cores in each set, and then make the sets overlap.

So say we have a 4-core CPU (labelled A, B, C, and D), that then gets divided into two sets X = (A, B, C) and Y = (A, C, D).
That way the load can migrate from one set (X) of CPU's into another set (Y), provided that the load migration code gets lucky on selecting set Y.

to post comments

How 3.6 nearly broke PostgreSQL

Posted Oct 3, 2012 12:03 UTC (Wed) by ajb (subscriber, #9694) [Link] (1 responses)

Your example has convinced me that I was wrong to say that you could get away with only two buddies. If you have only two, the best you can do is have a ring of cpus. This is different from the case of cuckoo hashing and skew caches, where only two places are sufficient.

However, in your example, A and C have 3 buddies, but B and D have only two. It seems like the scheduling algorithm would be just as efficient if they all had three, and there would be a better chance that migrations would be beneficial.

How 3.6 nearly broke PostgreSQL

Posted Oct 3, 2012 13:31 UTC (Wed) by and (guest, #2883) [Link]

I understood that approach differently: If core A has B as its buddy, B's buddy does not necessarily need to be A. This would imply kind of a ring buffer of buddies within the package (A->B->C->D->A)...

How 3.6 nearly broke PostgreSQL

Posted Oct 4, 2012 10:46 UTC (Thu) by dunlapg (guest, #57764) [Link]

Yeah, it seems like if the problem is there are "too many" cores per socket, that instead of fixing on 2, it should be fixed on "almost but not quite too many" -- e.g., 4 for example? So if you have 4-cores per socket, it looks exactly like it does before; but if you have 8, you still only look at 4 other cores. Having the sets overlap seems like an obvious way to make sure things can find a good optimum within a few iterations.

How 3.6 nearly broke PostgreSQL

Posted Oct 6, 2012 8:13 UTC (Sat) by eternaleye (guest, #67051) [Link] (2 responses)

Another option might be to use a Kautz digraph - it seems like in terms of a migration problem like this, it might be very nearly optimal.

I've found this to be a far clearer explanation than the Wikipedia article: http://pl.atyp.us/wordpress/index.php/2007/12/the-kautz-g...

In learning about them myself, I wrote a perl script to generate a Kautz graph: http://ix.io/36j/

It takes the degree as the first argument and the dimension and the second, and outputs a list of edges as <from> <to> tuples, one per line.

I still need to write the Kautz::Graph class (stubbed in the file above) to embody a full set of the Kautz nodes with the same degree and dimension parameters, and see about modifying it to generate dot so it can make a nice graphic.

How 3.6 nearly broke PostgreSQL

Posted Oct 6, 2012 8:26 UTC (Sat) by eternaleye (guest, #67051) [Link]

...And I just realized I misread my own code. It actually prints the names of the nodes, it's just that the symbols of the name are space-separated since they can be any positive integer <= degree.

Well, one more thing to remedy.

How 3.6 nearly broke PostgreSQL

Posted Oct 6, 2012 8:45 UTC (Sat) by eternaleye (guest, #67051) [Link]

Alright, here's a version that has a Kautz::Graph class, and prints both nodes and edges when run: http://ix.io/36k/