Libreria aritmetica parallela arbitraria di precisione

Sto provando a fare l'elevazione a più moduli di interi con un modulo molto grande mediante quadratura ripetitiva (la potenza è sempre una potenza di 2 nel mio caso, quindi credo che sia il modo più efficiente). Grazie a una buona proprietà del mio modulo, il resto dell'informatica è economico; la parte difficile è la moltiplicazione.Libreria aritmetica parallela arbitraria di precisione

Attualmente eseguo GMP su Intel Core 2 Quad. Mi piacerebbe fare un uso efficiente dei quattro core del processore, ma GMP non si adatta agli ambienti SMP, quindi sto cercando una libreria aritmetica sostitutiva arbitraria di precisione. Ho trovato alcune librerie per il calcolo parallelo su matrici , ma quello di cui ho veramente bisogno è una libreria per gli interi .

Esiste quello che sto cercando?

fonte

2011-10-26 Pteromys

Quanto sono grandi i numeri (cifre, bit)? Anche con una forking a basso costo, il tempo di commutazione del contesto per consentire alle CPU multiple di lavorare su una singola operazione aritmetica potrebbe dominare qualsiasi risparmio. Se i numeri sono abbastanza grandi, dovresti fare una divisione ricorsiva e conquistare add/sottrarre [dividere il numero in parti sinistra e destra, aggiungere in modo recusivo le parti, propagare il carry], ma mi aspetterei che la vittoria fosse nel parallelizzare più e dividere se c'è una vittoria da avere. –

I miei moduli possono avere dimensioni pari a 2^10000000 (!). – Pteromys

La risposta è sì, multi-threaded librerie precisione arbitraria esistono. Ma non sono a conoscenza di uno solo che sia effettivamente pubblico. (con velocità paragonabile a GMP)

Ad esempio, le librerie a precisione arbitraria utilizzate nei programmi Pi-computing, TachusPi e y-cruncher sono in grado di eseguire aritmetiche multi-thread su grandi numeri.

Tuttavia, entrambe le librerie sono closed source e non sono disponibili al pubblico per l'uso.

Divulgazione di affiliazione: Sono l'autore di y-cruncher. Quindi ho scritto io stesso una di queste librerie a precisione arbitraria multi-thread.

fonte

2011-10-26 13:55:35 Mysticial

Potrebbe dirmi che tipo di algoritmo usano quelle librerie? Ho sfogliato i capitoli pertinenti del TAOCP di Knuth, ma non sono riuscito a trovare algoritmi bignum esplicitamente dichiarati adatti al calcolo parallelo, tranne la cosiddetta aritmetica modulare, che nel mio caso si è rivelata inadatta. – Pteromys

Tutte le principali librerie di numeri grandi utilizzano una sorta di FFT per effettuare una moltiplicazione di grandi dimensioni. FFT e le sue varianti sono tutte molto parallelizzabili. Tuttavia, l'implementazione di uno specializzato per la moltiplicazione di numeri grandi non è un compito facile. (non puoi semplicemente dare uno schiaffo a un wrapper su FFTW e aspettarti di battere GMP e scalare con più core) – Mysticial

Grazie. (Saltai piuttosto le sezioni su FFT). Non penso, però, posso implementare io stesso una routine di moltiplicazione rapida ... – Pteromys

Avete estratto http://mpir.org? Sostengono di farlo con una variante di GMP e utilizzando GPU.

fonte

2011-10-26 13:55:06

Lo elencano come uno dei loro obiettivi. Ma sulla base della loro documentazione, non sembra che nessuno di essi sia stato implementato. Probabilmente perché MPIR è biforcato fuori da GMP e GMP stesso non è parallelizzato. – Mysticial

Questo è un peccato. Potrei parallelizzare me stesso GMP, ma quanto è difficile in realtà? – Pteromys

Una domanda interessante. Se i ragazzi MPIR dovessero fare questo e non farlo, dovresti chiedertene il motivo. Mi aspetto che la parte difficile sia ottenere il codice GMP (scritto in GCC C, a destra) per eseguire operazioni di multithreading. Il goo richiesto per fare ciò e la sincronizzazione corrispondente possono essere relativamente disordinati in C. Gli algoritmi stessi: come ho detto prima, un dividi-e-conquista per add dovrebbe essere abbastanza facile, e mi aspetterei di moltiplicare A: B per C: D deve essere calcolato in primo luogo come il calcolo dei prodotti incrociati e le somme dovrebbero parallelizzarsi in questo modo. Sarebbe una vittoria? Difficile dirlo senza farlo. –

Libreria aritmetica parallela arbitraria di precisione

risposta

Problemi correlati