8 pieces endgame database

[TAILLE]

I'm planning to buy next year a dual-processor system with a Intel Sandy Bridge or Ivy Bridge (most likely with 8-cores each). Maybe the Ivy Bridge is not available in 2012 (basically this is the tick from tick-tock, or otherwise stated the die-shrink to 22nm).
I also assume at that time as these processors have also more memory-channels, that such a motherboard could containing > 48 GByte Memory.
Assuming a clock speed around 3 - 3.4 Ghz, would the 8P DB generation (also backed up by a 500G SD) something which could be done in less then 1 month, or do you think this is still unrealistic?

Bert

Hi Bert,

To my experience the most important point in your configuration is the amount of memory. Let's take just an example :
You want to generate the 1421 (and 2114) db. What do you need for a very fast generation ?
1) the 7 pieces db in order to deal with all captures => 21Gb
2) the 0521 db to deal with a white promotion => 2,5Gb
3) the 1412 db to deal with a black promotion => 21Gb
for a total amount of about 45Gb
By preloading these db you avoid any other access disk and you have only to work on an efficient multithread alogorithm.
No doubt for me that you need far less than 1 month for the 8 db generation.

Curiously, as soon as you have a lot of memory, I think SSD disk will not give you a very big advantage during the generation process. Access disk was for me a major problem to solve because I have only 12Gb of memory but for you I think it's not a relevant point.

[TAILLE]

I'm planning to buy next year a dual-processor system with a Intel Sandy Bridge or Ivy Bridge (most likely with 8-cores each). Maybe the Ivy Bridge is not available in 2012 (basically this is the tick from tick-tock, or otherwise stated the die-shrink to 22nm).
I also assume at that time as these processors have also more memory-channels, that such a motherboard could containing > 48 GByte Memory.
Assuming a clock speed around 3 - 3.4 Ghz, would the 8P DB generation (also backed up by a 500G SD) something which could be done in less then 1 month, or do you think this is still unrealistic?

Bert

Hi Bert,

To my experience the most important point in your configuration is the amount of memory. Let's take just an example :
You want to generate the 1421 (and 2114) db. What do you need for a very fast generation ?
1) the 7 pieces db in order to deal with all captures => 21Gb
2) the 0521 db to deal with a white promotion => 2,5Gb
3) the 1412 db to deal with a black promotion => 21Gb
for a total amount of about 45Gb
By preloading these db you avoid any other access disk and you have only to work on an efficient multithread alogorithm.
No doubt for me that you need far less than 1 month for the 8 db generation.

Curiously, as soon as you have a lot of memory, I think SSD disk will not give you a very big advantage during the generation process. Access disk was for me a major problem to solve because I have only 12Gb of memory but for you I think it's not a relevant point.

Oops I forgot to add the memory needed for the 1421db itself => 12Gb.
If you can have 64Gb of memory then you will have quite no access disk during the generation process (for a given db generation you will have only a preloading of the concerned 8 pieces db).

[BertTuyt]

Gerard,

thanks.
Interesting, so basically the largest 8P DB can be calculated from memory if more the 64 GByte is available.
I guess if you would load the sub-DB's in phases so first calculate the captures, and then promotions (think when you do this in 2 passes, the program might be a little slower but not dramatic), then even less memory is required.

Lets do a quick calculation, nowadays with 3 memory channels (and 6 memory slots) my i7 has 12 GByte Memory.
Assuming with 4 channels you have 8 slots and with a dual processor you might have 16 memory slots.
If you use 4 GByte for every slot (which is not impossible in 2012) then you have 64 GByte.
So i think this is not unrealistic and also not financially impossible by then...

Bert

[TAILLE]

Gerard,

thanks.
Interesting, so basically the largest 8P DB can be calculated from memory if more the 64 GByte is available.
I guess if you would load the sub-DB's in phases so first calculate the captures, and then promotions (think when you do this in 2 passes, the program might be a little slower but not dramatic), then even less memory is required.

Lets do a quick calculation, nowadays with 3 memory channels (and 6 memory slots) my i7 has 12 GByte Memory.
Assuming with 4 channels you have 8 slots and with a dual processor you might have 16 memory slots.
If you use 4 GByte for every slot (which is not impossible in 2012) then you have 64 GByte.
So i think this is not unrealistic and also not financially impossible by then...

Bert

Yes Bert it seems you can calculate the largest 8p db with about 64Gb.
Instead of 2 passes you you can even take 3 passes :
1) calculate the captures by preloading the 7p db
2) calculate a white promotion by preloading the corresponding 8p db
3) calculate a black promotion by preloading the corresponding 8p db

For you information the biggest db for Damy are in decreasing order :
2312 : 27Gb
2132 : 24Gb
3212 : 22Gb
2123 : 19Gb
2231 : 15Gb
1223 : 15Gb
....

With 3 passes you need to store in memory only 2 db => 64Gb is largely enough to avoid any access disk during calculation.
With only 2 passes you need to store 3 db which is may be too much in certain cases, depending on your compression efficiency

[Ed Gilbert]

My experience is that you don't need all that memory. When I built the 8pc db, I used a number of instances of the build program. Each instance used only about 1.8GB of ram, and rarely was disk access a bottleneck, even with 8 instances running on one computer. I used a ram buffer for the subdivision being built, and all other dependency data was cached in 4k blocks. Often there was only a few hundred MB of ram remaining from the 1.8GB that was available for caching, but this is enough.

This was several years ago. It took 8.8 calendar months, but it would go much faster now:
- I only had the 8-core server for about 5 of those 8.8 months.
- To build now you don't need to verify. This cuts the time in half.
- Machines are now twice as fast as the ones that I used. This cuts the time in half again.
- A speed bottleneck for me was the fact that I did not store capture positions during the build, so looking up the values of dependency positions was often a slow tree search. Storing captures might speed it up another 50%.

So just doing those things today would drop the time from 8.8 months to perhaps 1.5 months, and no need for huge amounts of ram. 1.5 months is a very short time. It doesn't seem worth a lot of extra equipment to try to do it in less.

-- Ed

[TAILLE]

My experience is that you don't need all that memory. When I built the 8pc db, I used a number of instances of the build program. Each instance used only about 1.8GB of ram, and rarely was disk access a bottleneck, even with 8 instances running on one computer. I used a ram buffer for the subdivision being built, and all other dependency data was cached in 4k blocks. Often there was only a few hundred MB of ram remaining from the 1.8GB that was available for caching, but this is enough.

This was several years ago. It took 8.8 calendar months, but it would go much faster now:
- I only had the 8-core server for about 5 of those 8.8 months.
- To build now you don't need to verify. This cuts the time in half.
- Machines are now twice as fast as the ones that I used. This cuts the time in half again.
- A speed bottleneck for me was the fact that I did not store capture positions during the build, so looking up the values of dependency positions was often a slow tree search. Storing captures might speed it up another 50%.

So just doing those things today would drop the time from 8.8 months to perhaps 1.5 months, and no need for huge amounts of ram. 1.5 months is a very short time. It doesn't seem worth a lot of extra equipment to try to do it in less.

-- Ed

This confirm my point. A lot of memory cannot harm and, as I mentionned, this can allow you to ignore disk acess problem but the main point is to be able to use several threads for building the complete db. I noted that Ed chose to use several instances of its program and Michel and myself chose instead a multithread algorithm. As far as I'm concerned building such multithread algorithm was a very interesting challenge for me; this development phase was far more interesting that the calculation phase where I only have to wait passively!
Bert, I hope you will take also a lot of pleasure working at such challenge!

[Ed Gilbert]

Hi Gerard,

My point is that it is not necessary to wait a year or more for more memory to be available at a reasonable cost. The memory requirements are about the same whether you use one process with multiple threads or multiple processes. 2gb per thread or process should be sufficient. With more memory it might be a little faster, but why wait a year or two just so you can build the 8pc db in 1 month instead of 1-1/2 months?

-- Ed

[BertTuyt]

At least the 600GB SSD (which is needed for a 8P DB) is now on its way.
See below from the Internet...

The first quarter on the slide includes current, as well planned drive configurations. This quarter, Intel will launch 40GB X25-V drive for value market, and 80GB, 160GB and 300GB X25-M SSDs for mainstream market, all based on 25nm Multi-Level Cell (MLC) technology. Much larger, or huge by SSD standards, 600GB drive, manufactured using 25nm chips, will be released in the second quarter 2011. Finally, in the third quarter of this year Intel will introduce enterprise-class X25-E SSD drives, with capacities 100GB, 200GB and 400GB. These drives, codenamed Lyndonville, will utilize 25 nm Enterprise MLC memory chips.

Bert

[TAILLE]

Hi,

I have just finished the 8p db generation (4x4, 5x3 and 6x2) after more than 5 months calculations. I do not intend to generate the 7x1db because I know I will never use it.
For your information the size of the 6x2 db is 39,3Gb (as expected it is rather small comparing to 4x4 and 5x3 dbs).
I am of course ready to exchange all counters concernig this last db.

[Ed Gilbert]

I just made a change to the kingsrow egdb driver that made a big improvement in the use of cache memory. The change eliminates a data structure that consumes about 400mb of RAM when using the 8/9pc database. It means that this 400mb, which was previously overhead, can now be used instead as additional cache buffers. The idea originated from Rein Halbersma -- thanks Rein!

The eliminated data structure was an array of indicies into cache buffers. The array is indexed by a descriptor of a 4kb db block. Since the 8/9pc WLD db consumes 407gb of data, it can be divided into about 100 million 4kb blocks. The array had 100 million elements, each a 4-byte integer, which explains it 400mb size. Here is how it was used: when a position is passed to the egdb driver for lookup, its position index is calculated. The driver then does a search through a list of starting indices (another 400mb data structure) to identify which 4kb db block contains the WLD value of the position represented by that index. Once it knows which 4kb block contains the position, it needs to determine if that block is in cache or not, and if it is in cache, which cache block. That was previously the function of the array that has been eliminated. Indexing into the array gave the cache block descriptor of a 4kb cache block, or else a special value meaning that the data block is not in cache. Since the egdb cache is typically much smaller than the total 407gb size of the database, most of the values in this array were the special value meaning "not in cache". It was inefficient to have this large array so sparsely populated.

Rein's suggestion was to replace the array with a hashtable. This is a much more memory efficient way to store the information. The size of hashtable is approximately 1% of the user's egdb cache. For example, if the user's egdb cache is 2000mb, the overhead of the hashtable is only 20mb.

I have benchmarked the performance of the driver using the hashtable, and the time to do a position lookup is nearly identical to the version of the driver that used the array. The randomness requirements of the hashing function are much less stringent than the one used for the transposition table, so a fast hashing function can be used. The function I used consists of just a few XORs and shifts.

For anyone running kingsrow on a 32-bit version of Windows, this is a nice improvement. For example, if the user gives the egdb driver 1400mb of RAM to use, it would previously use 800mb of it for the 2 large arrays, leaving only 600mb for actual cache buffers. With the elimination of one of these arrays, kingsrow now gets to use 1000mb of that memory for cache buffers. OTOH, on a 64-bit computer with 16gb of RAM, the extra 400mb is not very significant.

I have not made the new version available to kingsrow users yet, but will do that when I finish testing it.

-- Ed