¿Qué algoritmos hash son paralelizables? Optimización del hashing de archivos de gran tamaño que se utilizan en CPU multinúcleo

Question

Estoy interesado en optimizar el hash de algunos archivos grandes (optimizar el tiempo del reloj de pared). La E/S ya se ha optimizado lo suficiente y el dispositivo de E/S (SSD local) solo recibe un 25% de la capacidad, mientras que uno de los núcleos de la CPU está completamente agotado.

Tengo más núcleos disponibles, y en el futuro es probable que tenga aún más núcleos. Hasta ahora solo he podido acceder a más núcleos si necesito varios hashes del mismo archivo, digamos un MD5 Y un SHA256 al mismo tiempo. Puedo usar el mismo flujo de E/S para alimentar dos o más algoritmos de hash, y obtengo los algoritmos más rápidos de forma gratuita (en cuanto al tiempo del reloj de pared). Según entiendo la mayoría de los algoritmos hash, cada bit nuevo cambia el resultado completo, y es inherentemente difícil/imposible de hacer en paralelo.

¿Algún algoritmo hash convencional es paralelizable?
¿Hay hash no convencionales que sean paralelizables (y que tengan al menos una implementación de muestra disponible)?

Como las futuras CPU tenderán hacia más núcleos y una nivelación en la velocidad del reloj, ¿hay alguna manera de mejorar el rendimiento del hash de archivos? (además del overclocking refrigerado por nitrógeno líquido?) o es intrínsecamente no paralelizable?

Answer 1

Actualmente hay mucha investigación en curso en esta área. El Instituto Nacional de Estándares y Tecnología de EE. UU. Está llevando a cabo una competencia para diseñar la función hash de última generación de nivel gubernamental. La mayoría de las propuestas para eso son paralelizables.

Un ejemplo: http://www.schneier.com/skein1.2.pdf

descripción del estado actual del concurso de Wikipedia: http://en.wikipedia.org/wiki/SHA-3

Answer 2

¿Qué tipo de SSD tiene? La implementación de mi C de MD5 se ejecuta a 400 MB/s en un solo núcleo Intel Core2 (2,4 GHz, no el último Intel). ¿Realmente tienes SSD que admite un ancho de banda de 1.6 GB/s? Quiero lo mismo !

El hash de árbol se puede aplicar a cualquier función hash. Hay algunas sutilezas y la especificación Skein trata de lidiar con ellas, integrando algunos metadatos en la función en sí (esto no cambia mucho las cosas para el rendimiento), pero el "modo árbol" de Skein no es "el" Skein como se envía a SHA-3. Incluso si Skein se selecciona como SHA-3, la salida de un hash en modo árbol no sería lo mismo que la salida de "plain Skein".

Afortunadamente, se definirá un estándar en algún momento para describir el hash de árbol genérico. En este momento no hay ninguno. Sin embargo, algunos protocolos se han definido con soporte para un hashing de árbol personalizado con la función hash Tiger, bajo el nombre "TTH" (Tiger Tree Hash) o "THEX" (Tree Hash Exchange Format). La especificación para TTH parece ser un poco difícil de alcanzar; Encuentro algunas referencias a borradores que se han movido o desaparecido para siempre.

Aún así, tengo un poco de dudas sobre el concepto. Es bastante ordenado, pero proporciona un aumento en el rendimiento solo si puede leer datos más rápido que lo que un solo núcleo puede procesar, y, dada la función correcta y la implementación correcta, un núcleo único puede almacenar una gran cantidad de datos por segundo. Un hash de árbol distribuido en varios núcleos requiere que los datos se envíen a los núcleos adecuados, y 1.6 GB/s no es el ancho de banda más pequeño que haya existido.

SHA-256 y SHA-512 no son muy rápidos. Entre los candidatos SHA-3, suponiendo un procesador x86 en modo de 64 bits, algunos de ellos alcanzan alta velocidad (más de 300 MB/s en mi Intel Core 2 Q6600 a 2,4 GHz, con un único núcleo, eso es lo que puedo sacar de SHA-1, también), por ejemplo BMW, SHABAL o Skein.hablar criptográficamente, estos diseños son un poco demasiado nuevo, pero MD5 y SHA-1 ya están criptográficamente "roto" (con bastante eficacia en el caso de MD5, en lugar teóricamente para SHA-1) por lo que cualquier de los de ida y 2 SHA-3 candidatos debería estar bien.

Cuando pongo mi tapa de "vidente", preveo que los procesadores seguirán siendo más rápidos que la RAM, hasta el punto de que el costo de hash quedará eclipsado por el ancho de banda de la memoria: la CPU tendrá ciclos de reloj de repuesto mientras espera para los datos de la RAM principal. En algún punto, todo el modelo de subprocesamiento (una gran RAM para muchos núcleos) tendrá que ser modificado.

Answer 3

Usted no dijo lo que necesita su hash para. Si no va a intercambiarlo con el mundo exterior, solo para uso interno, simplemente divida cada archivo en trozos, calcule y almacene todas las sumas de comprobación. Luego puede usar muchos núcleos simplemente lanzando un trozo a cada uno.

Dos soluciones que viene a la mente es dividiendo los archivos en trozos de tamaño fijo (más simple, pero usarán menos núcleos de archivos más pequeños donde se supone que no necesita toda esa potencia) o en un número fijo de trozos (usará todos los núcleos para cada archivo). Realmente depende de lo que quiere lograr y de la distribución del tamaño de su archivo.

Si, por otro lado, necesita hash para el mundo exterior, como puede leer de las otras respuestas, no es posible con hash "estándar" (por ejemplo, si desea enviar hashes SHA1 para que otros lo comprueben) con diferentes herramientas) por lo que debe buscar en otro lugar. Como calcular el hash al almacenar el archivo, para su posterior recuperación, o calcular hashes en segundo plano con los núcleos 'libres' y almacenarlos para su posterior recuperación.

La mejor solución depende de cuáles sean sus limitaciones y dónde puede invertir el espacio, el tiempo o la potencia de la CPU.