Dedekind@Home ?

[sviscapi]

Hi Lennart,

Regarding the acknowledgements:

The authors gratefully acknowledge the computing time provided to them on the high-performance computers [Cluster name/s] at the NHR Center PC2. These are funded by the Federal Ministry of Education and Research and the state governments participating on the basis of the resolutions of the GWK for the national highperformance computing at universities (www.nhr-verein.de/unsere-partner).

Could your code be made to run on a distributed computing platform such as BOINC ?

https://boinc.berkeley.edu/

I pitched the idea some time ago to the community: https://boinc.berkeley.edu/forum_thread.php?id=15150

Feel free to chime in :)

Regards, Samuel

[VonTum]

Oh, seeing your excerpt made me realize I forgot to actually fill in Noctua 2 for the cluster name, how embarassing!

Well, as for the original purpose of this project - Computing the 9th Dedekind Number - while it could definitely be an interesting test, and could be used as a benchmark dataset for branchy bitwise operations, the full computation's already been done. Executing this efficiently was the primary motivation behind using FPGAs. But this work is finished, and the paper is in the works.

However, a few spin-off projects have originated from this.
One which is my current PhD thesis: https://github.com/pc2/sus-compiler
And one is the fast generation of random Monotone Boolean Functions for use in statistical work. To this end Alex Fihman's been working a lot, and I've been able to produce a nice CPU implementation as well. Perhaps this could be an interesting endeavour for BOINC? Right now, my fastest implementation (when ran on a 128 core AMD Epyc Noctua 2 normal node) generates 1440MBF9/s. Memory use is only 8GB per NUMA domain, which is feasible for regular peolpe's computers.

[sviscapi]

But what about the 10th, 11th, nth Dedekind Number ? Couldn't one use your code in order to compute them ? Or is your code specific at computing the 9th Dedekind Number ? Sorry if that's a dumb question, I'm not a math person :)

[VonTum]

Well, with any algorithms we know right now it would require an impossibly huge amount of computational power to pull it off. The complexity of the best of our algorithms is on the order of O(2^(2^(n-1))). More specifically, my algorithm is on the order of O(R(n-2)*D(n-2)), which is still an insane amount considering the values involved.

As an example: With my algorithm, it takes roughly 100ms to compute D(7), about 6 minutes to compute D(8), and 50'000 FPGA hours with an insanely optimized FPGA accelerator. Not only is this compute time exponential with an enormous factor, but the factor itself also goes up exponentially. I would imagine D(10) to be on the order of billions of compute years on optimized ASICs. Even putting all the computers on earth together won't make a dent in that.

However, generating these random MBFs could be something tangible for such a project :)

[sviscapi]

Hello,

+1 for the random MBF project :) Could you please share some details regarding your CPU implementation ?

On the other hand, some distributed computing projects have been running for quite some time now. You can have a look at distributed.net for example. They have been trying to break RC5-72 for the past 22 years ;)

https://stats.distributed.net/projects.php?project_id=8

Cheers, Sam

[AlexFihman]

Hi Sam,

I think we need working quantum computer to calculate exact value of 10th Dedekind number.
But it doesn't stop us from getting approximate value of it (and 11,12) using probabilistic methods.

Mathematicians, in general, do not like probabilistic results, because resul like, D(10)≈
8.92(731)e+78, sigma 1.06e+76, means for them "it can be any value".

Currently Lennart have greately improved method of calculating D10 by pairs, I have couple more methods,
usable for D(11) and D(12) but they converge too slowly for higher dimensions, yet I believe it should be
possible to get good estimate (say up to 1%) for any dimension.

Regards,
Alex

[VonTum]

As of 8a8866e the NUMA version of generation random MBF9s performs at 1530MBF9/s on our 128 core 8-numa node AMD Epyc 7713 compute nodes. Other NUMA topologies are now also supported