3 ms·
> The problem: The calculation of these terms on normal processors is slow and also the use of GPUs as currently the fastest hardware accelerator technology for
by vlovich123 3y ago
> The problem: The calculation of these terms on normal processors is slow and also the use of GPUs as currently the fastest hardware accelerator technology for many AI applications is not efficient for this algorithm.
> https://arxiv.org/pdf/2304.03039.pdf https://arxiv.org/pdf/2304.03039.pdf At
this rate, a single FPGA processes about 5.2 α values per second, taking 47’000
FPGA hours to compute D(9)
and
> https://arxiv.org/pdf/2304.00895.pdf https://arxiv.org/pdf/2304.00895.pdf The only thing left to say is that we run the algorithm on Nvidia A100 GPUs. 5311 GPU hours and
4257682565 matrix multiplications later, we got the following value for the ninth Dedekind number
Does this mean that Christian Jäkel developed a new technique? Or was this extending the existing P-coefficient formula work and making it work on GPUs?
- HappyPanacea 3y agoIt does seems so, both seems to compute the Dedekind number by using sums over equivalence classes of lower number of variables functions. Before [0][1] It was only possible to compute D(n+2) from Rn and Jäkel gave way to compute D(n+3) and D(n+4) from Rn and that seems to be major speed improvement. The D(n+3) computed D(8) in 17.56s, he couldn't use the same method for presumably because R(7) is 30,000 times R(6) and he is using matrix multiplication so it will take stupid long. Edit: I didn't read carefully enough, it is not new at all see [2] or [3] for examples. [0]: Yusun, T.J.: Dedekind numbers and related sequences (2008) page 19 [1]: Lennart Van Hirtum. A path to compute the 9th dedekind number using fpga supercomputing. https://hirtum.com/thesis.pdf https://hirtum.com/thesis.pdf, 2021. KU Leu- ven, Masters Thesis page 51 "While it would be nice to pick k = 3 and just compute D(9) from the structure of 6, at this time no efficient methods exist for computing P(n,k,α,β) for k ≥ 3. So we have to use k = 2" [2]: F. a Campo, Relations between powers of Dedekind numbers and exponential sums related to them, J. Integer Seq. 21 (2018), article 18.4.4, https://cs.uwaterloo.ca/ https://cs.uwaterloo.ca/ journals/JIS/VOL21/Campo/campo3.pdf and https://cs.uwaterloo.ca/journals/ https://cs.uwaterloo.ca/journals/ JIS/VOL21/Campo/campo3-corrigendum.pdf. [3]: Pieter-Jan Hoedt, Parallelizing with MPI in Java to Find the ninth Dedekind Number, preprint, 2015 https://web.archive.org/web/20150911060239/http://people.cs.kuleuven.be/~bart.demoen/WVKULAK/firstdraftofPaper_Hoedt.pdf https://web.archive.org/web/20150911060239/http://people.cs....
- ChristianJaekel 3y agoHi, I'm Christian, the one-man team. I want to clarify that the symmetries I used are not based on Rn. I developed methods to utilize equivalent lattice intervals. That’s a generalization, since the Rn values can be seen as a special kind of interval. This new approach, based in intervals, made the reformulation in terms of matrix multiplication possible.
- VonTum 3y agoLennart here, Both fundamental techniques were known beforehand, and in both cases the major innovation was adapting the algorithm for the specific compute platform. For us it was exploiting FPGAs to compute these P-Coëfficients, for Jäkel, his major contribution was restructuring the summation as large matrix multiplications, which could then be executed very efficiently on GPU.