Biblioteca aritmética de precisión arbitraria paralela

Estoy tratando de hacer una exponenciación modular de enteros con un módulo muy grande por cuadratura repetitiva (la potencia es siempre una potencia de 2 en mi caso, así que creo que esta es la forma más eficiente). Gracias a una buena propiedad de mi módulo, el resto de la informática es barato; la parte difícil es la multiplicación.Biblioteca aritmética de precisión arbitraria paralela

Actualmente ejecuto GMP en Intel Core 2 Quad. Me gustaría hacer un uso eficiente de los cuatro núcleos del procesador, pero GMP no escala en entornos SMP, por lo que estoy buscando una biblioteca aritmética de precisión arbitraria de sustitución. He encontrado algunas bibliotecas para el cálculo paralelo en matrices, pero lo que realmente necesito es una biblioteca para enteros.

¿Existe lo que estoy buscando?

Fuente

2011-10-26 Pteromys

¿Qué tan grandes son sus números (dígitos, bits)? Incluso con horquillas baratas, el tiempo de conmutación de contexto para permitir que múltiples CPU trabajen en una sola operación aritmética podría dominar cualquier ahorro. Si los números son lo suficientemente grandes, deberías hacer una división recursiva y conquistar al sumar/restar [dividir el número en partes izquierda y derecha, agregar recusivamente las partes, propagar el acarreo], pero esperaría que la victoria sea en paralelizar múltiples y dividir si hay una victoria que se tenía. –

Mis módulos pueden ser tan grandes como 2^10000000 (!). – Pteromys

La respuesta es sí, con hilos múltiples bibliotecas de precisión arbitraria existen. Pero no conozco ninguno que sea realmente público. (con velocidad comparable a GMP)

Por ejemplo, las bibliotecas de precisión arbitraria que se utilizan en los programas de Pi-computing, TachusPi y y-cruncher son capaces de aritmética de subprocesos múltiples en números grandes.

Sin embargo, ambas bibliotecas son de código cerrado y no están disponibles para el público.

Divulgación de afiliación: Soy el autor de y-cruncher. Así que escribí una de esas librerías de precisión arbitraria de subprocesos múltiples.

Fuente

2011-10-26 13:55:35 Mysticial

¿Podría decirme qué tipo de algoritmo utilizan esas bibliotecas? Revisé los capítulos relevantes del TAOCP de Knuth, pero no pude encontrar los algoritmos de bignum que explícitamente son adecuados para la computación paralela, excepto la llamada aritmética modular, que resultó ser inadecuada en mi caso. – Pteromys

Todas las principales bibliotecas de gran número usan algún tipo de FFT para multiplicar grandes. FFT y sus variantes son todas muy paralelizables. Sin embargo, implementar uno especializado para la multiplicación de números grandes no es una tarea fácil. (No se puede simplemente golpear un wrapper encima de FFTW y esperar que supere el GMP y escalar con múltiples núcleos) – Mysticial

Gracias. (Prefiero omitir secciones en FFT). No creo, sin embargo, puedo implementar la rutina de multiplicación rápida yo mismo ... – Pteromys

¿Has echado un vistazo http://mpir.org? Afirman estar haciendo esto con una variante de GMP y usando GPU.

Fuente

2011-10-26 13:55:06

Lo enumeran como uno de sus objetivos. Pero según su documentación, no parece que se haya implementado. Probablemente porque MPIR se bifurca de GMP y GMP en sí mismo no está paralelizado. – Mysticial

Eso es una pena. Podría paralelizar GMP, pero ¿qué tan difícil es en realidad? – Pteromys

Una pregunta interesante. Si se supone que los chicos de MPIR están haciendo esto y no lo han hecho, deberían preguntarse por qué. Esperaría que la parte más difícil sea obtener el código GMP (escrito en GCC C, derecha) para hacer operaciones de subprocesamiento múltiple. La sustancia requerida para hacer esto y la sincronización correspondiente pueden ser relativamente desordenadas en C. Los algoritmos mismos: como dije antes, una división y conquista para agregar debería ser bastante fácil, y esperaría multiplicar A: B por C: D que se computa principalmente como calcular productos cruzados y sumas también deben paralelizarse de esa manera. ¿Sería una victoria? Difícil de decir sin hacerlo. –

Biblioteca aritmética de precisión arbitraria paralela

Respuesta

Cuestiones relacionadas