Równoległa arytmetyczna biblioteka arytmetyczna dokładności

Próbuję wykonywać modułową potęgowanie liczb całkowitych o bardzo dużym module przez powtarzalne dzielenie kwadratu (moc zawsze wynosi 2 w moim przypadku, więc uważam, że jest to najbardziej efektywny sposób). Dzięki miłej właściwości mojego modułu, pozostała część obliczeniowa jest tania; najtrudniejszą częścią jest mnożenie.Równoległa arytmetyczna biblioteka arytmetyczna dokładności

Obecnie uruchamiam GMP na Intel Core 2 Quad. Chciałbym sprawnie korzystać z czterech rdzeni procesora, ale GMP nie skaluje się w środowiskach SMP, dlatego szukam zastępczej arytmetycznej biblioteki arytmetycznej. Znalazłem kilka bibliotek do obliczeń równoległych na macierzach, ale potrzebuję biblioteki dla liczb całkowitych.

Czy to, czego szukam, istnieje?

Źródło

2011-10-26 Pteromys

Jak duże są twoje liczby (cyfry, bity)? Nawet przy taniej rozwidlaniu czas przełączania kontekstu, aby umożliwić wielordzeniowym procesorom pracę z pojedynczą operacją arytmetyczną, może zdominować wszelkie oszczędności. Jeśli liczby są wystarczająco duże, powinieneś zrobić rekursywny podział i podbijać przy dodawaniu/odejmowaniu [dzielenie liczby na lewą i prawą część, werbalnie dodawaj części, propaguj przenoszenie], ale oczekiwałbym wygranej zrównoleglenie wielokrotności i dzielenie, jeśli istnieje wygrana. –

Moje moduły mogą mieć wielkość 2^10000000 (!). – Pteromys

odpowiedź brzmi tak, wielowątkowy biblioteki arbitralny precyzji istnieją. Ale nie znam jednego, który jest rzeczywiście publiczny. (Z szybkością porównywalną do GMP)

Na przykład, biblioteki dowolnej precyzji, które są stosowane w programach komputerowych Pi, TachusPi i y-cruncher mogą wielowątkowych arytmetycznych w dużych ilościach.

Obie biblioteki są jednak źródłami zamkniętymi i nie są dostępne publicznie do użytku.

Ujawnienie afiliacji: Jestem autorem y-cruncher. Napisałem więc jedną z takich wielowątkowych bibliotek arbitralnej precyzji.

Źródło

2011-10-26 13:55:35 Mysticial

Czy możesz mi powiedzieć, jakiego rodzaju algorytmu używają te biblioteki? Przejrzałem odpowiednie rozdziały TAOCP Knutha, ale nie mogłem znaleźć algorytmów bignum, które są wyraźnie określone jako odpowiednie do obliczeń równoległych, z wyjątkiem tak zwanej modularnej arytmetyki, która okazała się nieodpowiednia w moim przypadku. – Pteromys

Wszystkie główne biblioteki dużych liczb używają jakiegoś rodzaju FFT do dużego mnożenia. FFT i jego warianty są bardzo możliwe do zrównoleglenia. Jednak wdrożenie jednego specjalizowanego do multiplikacji dużej liczby nie jest łatwym zadaniem. (nie można po prostu uderzyć wrappera na FFTW i oczekiwać, że pokona GMP i skaluje się z wieloma rdzeniami) – Mysticial

Dzięki. (Raczej pominąłem sekcje na FFT). Nie sądzę jednak, że sam mogę wdrożyć szybką procedurę mnożenia ... – Pteromys

Czy wymeldowałeś się http://mpir.org? Twierdzą, że robią to z wariantem GMP i używają GPU.

Źródło

2011-10-26 13:55:06

Wymieniają je jako jeden z ich celów. Ale w oparciu o ich dokumentację nie wygląda na to, że zostało zaimplementowane. Prawdopodobnie dlatego, że MPIR jest rozwidleniem GMP, a sama GMP nie jest zrównoleglona. – Mysticial

Szkoda. Mógłbym zrównoleglić GMP sam, ale jak trudne jest to w rzeczywistości? – Pteromys

Interesujące pytanie. Jeśli faceci z MPIR mają to robić i nie mają, powinieneś się zastanawiać dlaczego. Spodziewałbym się, że trudniej będzie uzyskać kod GMP (napisany w GCC C, po prawej), aby wykonywać operacje wielowątkowości. Musiał to zrobić, a odpowiednia synchronizacja może być dość niechlujna w C. Algorytmy same w sobie: jak powiedziałem wcześniej, dzielenie i przejęcie dla dodania powinno być łatwe i oczekiwałbym pomnożenia A: B przez C: D, obliczane przede wszystkim jako obliczeniowe produkty krzyżowe, a sumy powinny również równoważyć w ten sposób. Czy to byłaby wygrana? Trudno powiedzieć bez robienia tego. –

Równoległa arytmetyczna biblioteka arytmetyczna dokładności

Odpowiedz

Powiązane problemy