ventas para marketing hashtags hashtagify diseño buscador java multithreading

para - Java multiproceso no se acelera



hashtagify (8)

A modo de comparación, intente utilizar merge sort con java 7 y el marco fork join. Hay un ejemplo de cómo hacer eso here . Esto le mostrará si es un problema con su implementación o una limitación de la máquina.

Implementé un algoritmo de ordenación de fusión paralela simple en Java. Esto corta la matriz en secciones iguales y las pasa para ser ordenadas independientemente por cada hilo. Una vez ordenados los segmentos de la matriz, se unen por un solo hilo. Como no hay recursos compartidos, no se usa la sincronización cuando se clasifican las sublistas. El último subproceso que combina la matriz de resultados, aunque espera a que se completen los otros subprocesos.

Cuando se utilizan dos hilos, la ganancia de rendimiento es casi del 66%. Cuando uso 4 hilos, el tiempo empleado no difiere de la versión de 2 hilos. Estoy en Linux 2.6.40.6-0.fc15.i686.PAE y un Intel Core i5.

Estoy comparando el tiempo con el comando de time Unix (a la matriz se le asignan enteros aleatorios uniformes). Al final de la clasificación estoy comprobando si el ordenamiento de la matriz es correcto o no (no es paralelo).

1 hilo

$ echo "100000000" | time -p java mergeSortTest Enter n: [SUCCESS] real 40.73 user 40.86 sys 0.22 2 hilos

$ echo "100000000" | time -p java mergeSortTest Enter n: [SUCCESS] real 26.90 user 49.65 sys 0.48 4 hilos

$ echo "100000000" | time -p java mergeSortTest Enter n: [SUCCESS] real 25.13 user 76.53 sys 0.43

El uso de la CPU es de alrededor del 80% al 90% cuando se utilizan 4 subprocesos, y alrededor del 50% cuando se utilizan 2 subprocesos, y alrededor del 25% cuando se utiliza un solo subproceso.

Esperaba un poco de aceleración cuando corrí en 4 hilos. Estoy equivocado en alguna parte.

ACTUALIZACIÓN 1

Aquí está el código: http://pastebin.com/9hQPhCa8

ACTUALIZACIÓN 2 Tengo un procesador Intel Core i5 de segunda generación.

Salida de cat /proc/cpuinfo | less cat /proc/cpuinfo | less (solo se muestra el núcleo 0).

processor : 0 vendor_id : GenuineIntel cpu family : 6 model : 42 model name : Intel(R) Core(TM) i5-2410M CPU @ 2.30GHz stepping : 7 cpu MHz : 800.000 cache size : 3072 KB physical id : 0 siblings : 4 core id : 0 cpu cores : 2 apicid : 0 initial apicid : 0 fdiv_bug : no hlt_bug : no f00f_bug : no coma_bug : no fpu : yes fpu_exception : yes cpuid level : 13 wp : yes flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe nx rdtscp lm constant_tsc arch_perfmon pebs bts xtopology nonstop_tsc aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 cx16 xtpr pdcm sse4_1 sse4_2 x2apic popcnt xsave avx lahf_lm ida arat epb xsaveopt pln pts dts tpr_shadow vnmi flexpriority ept vpid bogomips : 4589.60 clflush size : 64 cache_alignment : 64 address sizes : 36 bits physical, 48 bits virtual power management:

El Core i5 tiene 2 núcleos y tecnología hyperthreading por lo que parece que tiene 4 núcleos. Esos dos núcleos lógicos adicionales no ayudarán casi tanto como dos núcleos físicos, ya que su algoritmo de clasificación hace un buen trabajo para mantener la CPU ocupada.

Dado que solicitó una fuente "creíble", señalaré un artículo del sitio web de Intel que leí hace un tiempo: información sobre el performance-insights-to-intel-hyper-threading-technology . En particular, tenga en cuenta la siguiente sección sobre "limitaciones de hyperthreading":

Aplicaciones extremadamente eficientes en el cálculo. Si los recursos de ejecución del procesador ya están bien utilizados, entonces hay poco que ganar habilitando la tecnología Intel HT. Por ejemplo, el código que ya puede ejecutar cuatro instrucciones por ciclo no aumentará el rendimiento cuando se ejecuta con la tecnología Intel HT habilitada, ya que el núcleo del proceso solo puede ejecutar un máximo de cuatro instrucciones por ciclo.

También tenga en cuenta esta sección sobre la contención del subsistema de memoria:

Aplicaciones de ancho de banda de memoria extremadamente altas. La tecnología Intel HT aumenta la demanda del subsistema de memoria al ejecutar dos subprocesos. Si una aplicación es capaz de utilizar todo el ancho de banda de la memoria con la tecnología Intel HT desactivada, el rendimiento no aumentará cuando la tecnología Intel HT esté activada. En algunas circunstancias, es posible que el rendimiento se deteriore debido a las mayores demandas de memoria y / o los efectos de almacenamiento en caché de datos en estos casos. La buena noticia es que los sistemas basados ​​en el núcleo de Nehalem con controladores de memoria integrados e Intel® QuickPath Interconnects aumentan en gran medida el ancho de banda disponible en la memoria en comparación con las CPU Intel más antiguas con tecnología Intel HT. El resultado es que la cantidad de aplicaciones que experimentarán una degradación con la tecnología Intel HT en el núcleo de Nehalem debido a la falta de ancho de banda de la memoria se reduce considerablemente.

Otros puntos interesantes se pueden encontrar en la Guía de Intel para el desarrollo de aplicaciones multiproceso . Aquí hay otro fragmento de las aplicaciones de detecting-memory-bandwidth-saturation-in-threaded-applications :

A medida que un número cada vez mayor de subprocesos o procesos comparten los recursos limitados de la capacidad de caché y el ancho de banda de la memoria, la escalabilidad de una aplicación de subprocesos puede verse limitada. Las aplicaciones con muchos hilos de memoria pueden sufrir saturación de ancho de banda de memoria a medida que se introducen más subprocesos. En tales casos, la aplicación con subprocesos no se escalará como se espera, y el rendimiento se puede reducir.

Estoy obteniendo el resultado esperado en un i7 de doble núcleo con opción de JVM de servidor, 100000000 ints y 2 GB de memoria Xmx:

1 hilo: 23 segundos
2 hilos: 14 segundos
4 hilos: 10 segundos

Y también eliminé la recolección manual de elementos no utilizados y ejecuté los géneros en secuencia dentro de la misma instancia de JVM, teniendo primero una clasificación de preparación.

Como comenta el Sr. Smith, microbenchmarking (punto de acceso JVM) es algo complejo, y podría agregar que para 4+ núcleos, la clasificación de fusión podría realizarse por la mitad del número de subprocesos en un solo subproceso como ahora, por lo que su punto de referencia no es totalmente fiel al enfoque multi-threading.

Es posible que también desee verificar this pregunta.

Hace poco tuve que hacer un papper comparando el ordenamiento de burbuja, orden de fusión y ordenamiento bitónico en la arquitectura i7. Utilicé el primer código dado aquí para la combinación y tuve el mismo problema: 8 hilos no eran mejores que 4. Luego leí SMT (Intel Hyperthreading) y descubrí el problema y la solución:

Quite estas líneas en el método de combinación:

if (Runtime.getRuntime (). freeMemory () <((n1 + n2) * 4)) Runtime.getRuntime (). gc ();

Este código libera la memoria con los niveles L1 y L2 de los núcleos físicos, pero en esos kbs tenemos los buffers para dos hilos lógicos (no solo uno), por lo tanto, un hilo borra el búfer del hilo hermano en ese núcleo físico.

Después de eliminar eso si , vi la mejora 1.25 entre 4 y 8 hilos que proporciona SMT. Si alguien puede probar esto en un i5 eso sería genial.

Intenté esto en el i7 e incluso con 4 núcleos no hubo mejoría de 2 a 4 hilos. Sospecho que el problema es que sus datos no caben en la memoria caché, por lo que está probando el rendimiento del bus de memoria único.

Interesante porque tengo la misma observación al tratar de paralelizar la ordenación de fusión. Probé dos enfoques diferentes de desove del trabajo, pero no conseguí una aceleración. Mi enfoque para paralelizar el tipo de fusión es hacer que la fusión sea paralela. ¿Y las fusiones individuales en diferentes núcleos? En este caso, el corte de la recursión y la cantidad de hilos afectan la velocidad. De nuevo, la velocidad no puede sobrepasar la velocidad de serie. Esta técnica aparece en el libro Pautas y prácticas de programación estructurada paralela de Morgan Kaufman.

Un orden de fusión paralelo

La serie intel core i5-xxM tiene 2 núcleos, por lo que el uso de más de 2 subprocesos reducirá el rendimiento debido a la mayor conmutación de contexto.

Editar:

Aquí hay una expansión en mi respuesta en la que abordo la arquitectura Core i7, factores específicos que pueden afectar el rendimiento de una CPU y operaciones con gran cantidad de memoria, como una clasificación.

Tecnología turbo boost

Intel Core i7 tiene una frecuencia de procesador variable. A altas cargas, la frecuencia estará limitada por el calor, reduciendo la ganancia de rendimiento de la utilización de más núcleos.

Caché L3 compartida

La clasificación de conjuntos de datos grandes (>> 8 Mb) dará lugar a muchos fallos de página L3. El uso de demasiados hilos puede aumentar el número de fallos de página, disminuyendo la eficiencia. No estoy seguro si ese es el caso de un mergesort. (Por cierto: ¿cómo se mide la falta de memoria caché L3 en Linux?) No estoy seguro de que esto sea un factor, sin embargo.

Debo decir que me sorprende que no obtengas ningún aumento de rendimiento al usar los cuatro núcleos del i7. Trataré de hacer algunas pruebas en casa este fin de semana.