Hashero: Jacksum Optimizado para Multicore


Hashero v.0.1

Hashero v.0.1

Jacksum es una herramienta de línea de comandos que permite calcular y verificar 58 hashes o sumas de verificación diferentes a partir de archivos o texto.

Una de las cosas que permite hacer es calcular varios hashes juntos, pero no los calculaba en forma concurrente sino uno tras otro.

En esta nueva era de computadoras multi núcleo es necesario aprovechar todos los procesadores que estén disponibles si queremos que nuestros programas funcionen más rápido. Ya se sabe que en los próximos años los procesadores no serán más rápidos sino más paralelos.

Jacksum está escrito en Java que es un lenguaje con gran soporte para hacer programas concurrentes. Básicamente el plan era calcular en forma paralela los distintos hashes solicitados por el usuario y el resultado es Hashero, que no es más que una interfaz gráfica básica para una versión paralela de Jacksum 1.7.0.

Para el cálculo de más de un hash, Jacksum usa una especie de patrón composite. La clase CombinedChecksum puede contener varios Checksums (MD5, MD4, SHA256, CRC32, etc.) y los calcula todos juntos en forma secuencial.

La solución fue crear un thread por cada procesador o núcleo disponible. A cada thread se le asigna un conjunto de hashes a calcular. Así es que si el usuario pide calcular MD5 y SHA1 y hay dos procesadores, un thread calculará el MD5 y el otro el SHA1. Además hay otro thread que es el encargado de leer el archivo. De esa forma se lo lee una única vez.

Para la comunicación entre el thread que lee y los que calculan se usan colas. En particular, cada thread que calcula hashes tiene su propia cola y el thread que lee los datos encola cada bloque de bytes leído en cada cola.

Un factor importante para lograr máxima velocidad es que todos los threads tengan una cantidad de trabajo similar. Por ejemplo, si hay 2 procesadores y se desean calcular 3 hashes, evidentemente uno de los dos procesadores calculará 2 y el otro 1 y el tiempo total de cálculo será el tiempo que tarde el thread que más trabajo tenga que hacer. Como no todos los algoritmos de hash tardan lo mismo y para nivelar la carga de trabajo entre procesadores se midió el tiempo que insume el cálculo de cada algoritmo de hash. Ese tiempo se considera como el  peso del algoritmo y a la hora de repartir hashes entre threads se intenta que el peso total de todos sea parejo usando el algoritmo conocido como LPT-Algorithm (Longest Processing Time).

En el caso de Jacksum 1.7.0, el algoritmo más lento es GOST que con un peso de 12, supera ampliamente al segundo que es MD2 con un peso de 3. Es por eso que cuando se calculan los 60 hashes que soporta Hashero en un procesador con cuatro núcleos, un núcleo es dedicado exclusivamente a calcular GOST (su thread tiene peso total 12) y los otros 3 núcleos se reparten los demás hashes sin llegar ninguno a superar un peso total de 8.

El tiempo de cálculo en ese caso está determinado por el tiempo que se tarda en calcular GOST, ya que es el último en terminar. Se se calculan todos los hashes menos GOST, el tiempo baja enormemente.

Sin el conocimiento previo del peso de cada algoritmo y asignando los hashes en forma arbitraria (sin usar el algoritmo LPT), podría pasar que un thread tuviera asignado GOST y 10 algoritmos más, con lo cual el tiempo total de cálculo sería mayor y mientras un núcleo estaría aún procesando los demás ya estarían ociosos.

En este gráfico se observa el tiempo total de cálculo a medida que se van agregando algoritmos al cálculo. GOST fue el último que se agregó a la secuencia de Jacksum y se ve cómo casi duplica los tiempos. Es decir que calcular un GOST equivale en tiempo a calcular los otros 57 hashes. En la línea correspondiente a Hashero se observa el impacto que tiene GOST, también duplicando el tiempo total, pero por reordenamiento de los hashes entre threads, el salto absoluto es menor (10 segundos contra 30 en el caso secuencial).

En las pruebas realizadas comparando una ejecución secuencial y una paralela de los 60 hashes  con 4 núcleos reales (no HyperThreading), se midió un speedup de alrededor de 3,12.

Hashero y la versión modificada de Jacksum en la que está basado también tiene algunas mejoras de rendimiento para algunos algoritmos puntuales.

Se la puede usar desde la línea de comandos de igual manera, Hashero es sólo una interfaz gráfica para realizar pruebas.

Hashero, que incluye la versión modificada de Jacksum, se puede bajar desde esta página.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s