Wydajny algorytm obliczania liczb pierwszych dla FPGA (sito Erastotenesa)

[FlyingDutch]

Cześć,

mam następujące pytanie:

Czy zna ktoś z Was wydajną implementację jakiegoś algorytmu do obliczania liczb pierwszych korzystającego z zalet FPGA (sprzętowe zrównoleglanie)?

Jednym z takich algorytmów jest np. "sito Eratostenesa". Tutaj podaję linki do opisu tego algorytmu:

http://www.algorytm.edu.pl/algorytmy-maturalne/sito-eratostenesa.html

http://strefakodera.pl/algorytmy/algorytmy-wyszukiwania/wyznaczanie-liczb-pierwszych-sito-eratostenesa

Na razie badam temat i szukam informacji w sieci. To co udało mi się znaleźć do tej pory:

https://people.ece.cornell.edu/land/courses/ece5760/FinalProjects/f2011/clt67_yl478/clt67_yl478/index.html

https://www.fpgarelated.com/showthread/comp.arch.fpga/120236-1.php

https://pdfs.semanticscholar.org/9037/3f58c4607d48409b44efdb4b0167e4daaa2d.pdf

https://community.reconfigure.io/t/cryptography-on-fpgas/213

Zastanawiam, się na jakiej konfiguracji zestawu uruchomieniowego FPGA dało by się efektywnie zaimplementować ten algorytm? Z pewnością zestaw musi dysponować sporą pamięcią RAM (np. dodatkowa pamięć DDR).

Jeśli macie jakieś przemyślenia na ten temat, to proszę podzielcie się nimi (może jakieś gotowe implementacje algorytmów)?

Pozdrawiam

[JTyburski]

Jak udowodnisz, że hipoteza Riemanna jest prawdziwa (czego nikt od ponad 100 lat jeszcze nie zrobił, a nawet byli tacy co psychicznie zwariowali od tego jak np John Nash w USA) to wtedy będziesz miał najwydajniejszy algorytm świata, bo sobie opiszesz liczby pierwsze marną funkcją dzeta 🙂 Oczywiście w ten sposób już dużo liczb zostało znalezionych, ale nie ma pewności czy da się tak wszystkie znaleźć 🙂 W każdym razie możesz próbować tą funkcją 🙂

[FlyingDutch]

Jak udowodnisz, że hipoteza Riemanna jest prawdziwa (czego nikt od ponad 100 lat jeszcze nie zrobił, a nawet byli tacy co psychicznie zwariowali od tego jak np John Nash w USA) to wtedy będziesz miał najwydajniejszy algorytm świata, bo sobie opiszesz liczby pierwsze marną funkcją dzeta 🙂 Oczywiście w ten sposób już dużo liczb zostało znalezionych, ale nie ma pewności czy da się tak wszystkie znaleźć 🙂 W każdym razie możesz próbować tą funkcją 🙂

Cześć Jakub,

zdaje sobie sprawę, że jest to problem bardzo trudny do implementacji. Po pierwsze jest to raczej problem dla zestawu SoC+FPGA lub akceleratora PCI opartego na FPGA dla komputera PC. Wszystkie wydajne algorytmy zakładają przechowywanie coraz większych (już obliczonych) liczb pierwszych. Moduł musiałby dysponować bardzo dużą pamięcią RAM i interfejsem np. SATA aby przechowywać wyniki na dysku. Poza tym trzeba by dysponować biblioteką do operowania na bardzo dużych liczbach dla FPGA.

Nie będę się porywał "z motyką na Słońce", raczej interesowało mnie, czy były w tym zakresie podejmowane jakieś próby i jak się skończyły (podejrzewam, że dużo łatwiej byłoby tu użyć "CUDA" czy "OpenCL" dla GPU). Ale umieścić post na forum zawsze można, aby zaspokoić swoją ciekawość 😉

BTW: największe znane liczby pierwsze to chyba liczby pierwsze Mersenne'a (jeśli się pomyliłem to proszę sprostujcie mnie):

https://www.mersenne.org/primes/

Dla tych, którzy chcieliby wypróbować implementacje dla algorytmu "Sito Erastotenesa" (implementacja w C/C++) podaję dwa linki:

https://primesieve.org/

https://en.wikipedia.org/wiki/Sieve_of_Atkin

Pozdrawiam

[JTyburski]

Ano wszystko się opiera o pamięć - taka już zależność, że wszystko robimy szybko, ale przechowujemy za to dane, albo nie przechowujemy danych, ale za to wszystko robimy wolno 🙂

[Polecacz 101]

Produkcja i montaż PCB - wybierz sprawdzone PCBWay!
   • Darmowe płytki dla studentów i projektów non-profit
   • Tylko 5$ za 10 prototypów PCB w 24 godziny
   • Usługa projektowania PCB na zlecenie
   • Montaż PCB od 30$ + bezpłatna dostawa i szablony
   • Darmowe narzędzie do podglądu plików Gerber
Zobacz również » Film z fabryki PCBWay

[FlyingDutch]

Ano wszystko się opiera o pamięć - taka już zależność, że wszystko robimy szybko, ale przechowujemy za to dane, albo nie przechowujemy danych, ale za to wszystko robimy wolno 🙂

Cześć,
to od dawna znana zależność, niestety 😉 Z tego powodu chyba muszę się 'przymierzyć' do jakiegoś tańszego akceleratora FPGA z PCI-express do peceta, bo wszystkie interesujące mnie tematy wymagają dużych ilości pamięci RAM i masowych .Myślałem najpierw o jakimś SoC+FPGA opartym o ARM np:

https://kamami.pl/zestawy-uruchomieniowe/558403-terasic-de0-nano-soc-kit-p0286-zestaw-startowy-z-ukladem-altera-cyclone-v-soc.html

ale dochodzę do wniosku, że to półśrodki - muszę pomyśleć o akceleratorze FPGA z PCI do peceta.

Jakub, może mógłbyś polecić jakieś tańsze układy z tej grupy?

A co byś powiedział na taki akcelerator z Cyclone IV i PCI-express 4x (1GB RAM DDR2):

https://pl.aliexpress.com/item/PCIe-development-board-PCIe-X4-fpga-board-Cyclone-IV-EP4CGX75CF23I7-fpga-board-fpga-development-board-pcie/32839983232.html?spm=a2g17.10010108.1000016.1.5854fc63CnmsOa&isOrigTitle=true

? Cena po przeliczeniu z US $ na PLN to około 514 PLN (po dzisiejszym kursie dolara);

Wycofuję pytanie - ten układ FPGA ma za mało zasobów.

Pozdrawiam