FlyingDutch Napisano Kwiecień 14, 2018 Udostępnij Napisano Kwiecień 14, 2018 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 Cytuj Link do komentarza Share on other sites More sharing options...
JTyburski Kwiecień 14, 2018 Udostępnij Kwiecień 14, 2018 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ą 🙂 Cytuj Link do komentarza Share on other sites More sharing options...
FlyingDutch Kwiecień 15, 2018 Autor tematu Udostępnij Kwiecień 15, 2018 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 Cytuj Link do komentarza Share on other sites More sharing options...
JTyburski Kwiecień 15, 2018 Udostępnij Kwiecień 15, 2018 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 🙂 Cytuj Link do komentarza Share on other sites More sharing options...
Polecacz 101 Zarejestruj się lub zaloguj, aby ukryć tę reklamę. Zarejestruj się lub zaloguj, aby ukryć tę reklamę. 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 Kwiecień 15, 2018 Autor tematu Udostępnij Kwiecień 15, 2018 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 Cytuj Link do komentarza Share on other sites More sharing options...
Pomocna odpowiedź
Dołącz do dyskusji, napisz odpowiedź!
Jeśli masz już konto to zaloguj się teraz, aby opublikować wiadomość jako Ty. Możesz też napisać teraz i zarejestrować się później.
Uwaga: wgrywanie zdjęć i załączników dostępne jest po zalogowaniu!