programacion - huella hash
¿Qué algoritmos hash son paralelizables? Optimización de hash de archivos de gran tamaño que utilizan CPU multinúcleo (3)
Estoy interesado en optimizar el hashing de algunos archivos grandes (optimizando 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 probablemente tendrá incluso 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.
¿Se puede paralelizar alguno de los algoritmos hash convencionales?
¿Hay hashes 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 forma de mejorar el rendimiento del hash de archivos? (además del overclocking refrigerado por nitrógeno líquido?) o es intrínsecamente no paralelizable?
¿Qué tipo de SSD tienes? 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".
Con suerte, 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í, estoy un poco dudoso 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. Criptográficamente hablando, estos diseños son demasiado nuevos, pero MD5 y SHA-1 ya están criptográficamente "rotos" (bastante eficaz en el caso de MD5, más bien teóricamente para SHA-1), por lo que cualquiera de los candidatos SHA-3 de ronda 2 debería estar bien.
Cuando pongo mi límite 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 que los datos la RAM principal. En algún punto, todo el modelo de subprocesamiento (una gran RAM para muchos núcleos) tendrá que ser modificado.
De hecho, hay mucha investigación 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 de Wikipedia del estado actual del concurso: http://en.wikipedia.org/wiki/SHA-3
No dijiste para qué necesitas tu hash. 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 se me ocurren es dividir archivos en fragmentos de tamaño fijo (más simple, pero usará menos núcleos para archivos más pequeños en los que no se supone que necesites toda esa potencia) o en un número fijo de fragmentos (usará todo el 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, necesitas hashes para el mundo exterior, como puedes leer de las otras respuestas, no es posible con hashes "estándar" (por ejemplo, si quieres enviar hash SHA1 para que otros lo consulten con diferentes herramientas) así que debes buscar en otro lado. 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 son sus limitaciones y dónde puede invertir el espacio, el tiempo o la potencia de la CPU.