La cola de prioridad escalable minimiza los conflictos - Calendae | Informática, Electrónica, CMS, Ciberseguridad

La cola de prioridad escalable minimiza los conflictos

Hola y mil gracias por leerme. Soy Simón Sánchez y en esta ocasión vamos a hablar sobre La cola de prioridad escalable minimiza los conflictos

La era multinúcleo ha estado en pleno apogeo durante una década, pero aprovechar toda esa bondad paralela sigue siendo un gran desafío. Idealmente, la eficiencia del procesamiento se escalaría linealmente con un aumento en los núcleos, pero no siempre es así. Dado que los recuentos de núcleos están destinados a proliferar solo en todo el espectro de procesamiento, este es un tema que merece una atención seria.

Los investigadores del Laboratorio de Ciencias de la Computación e Inteligencia Artificial del MIT están explorando formas de mejorar la escalabilidad de las colas de prioridad, que son esenciales para aplicaciones como la planificación de tareas y la simulación de eventos discretos. Las colas de prioridad concurrentes escalan a aproximadamente ocho núcleos, pero por encima de los dígitos de un solo dígito, la eficiencia disminuye a medida que varios subprocesos intentan acceder a los elementos en la parte superior de la cola. Al ajustar las colas de prioridad para que se dirijan a cierta distancia de la cabeza, el equipo del MIT demostró una mayor eficiencia de hasta 80 núcleos.

Con las versiones tradicionales de una cola de prioridad, los cuellos de botella se producen cuando varios subprocesos intentan acceder simultáneamente al frente de la cola de prioridad. El algoritmo SprayList creado por el equipo del MIT resuelve este problema asignando tareas al azar. El algoritmo basado en listas de salto permite que los procesadores con muchos núcleos funcionen al unísono.

«Aproximadamente, en cada nivel de SkipList, un hilo lanza una moneda al azar para decidir cuántos nodos avanzar en ese nivel», escriben en su papel. “Básicamente, utilizamos la aleatoriedad local y la estructura aleatoria SkipList para equilibrar los resultados en la parte superior de la lista. Las longitudes de los saltos en cada nivel se eligen de tal manera que las probabilidades de golpear los nodos entre el primer O (p log3 p) sean casi uniformes. «

La Figura 1 muestra la información detrás de los aerosoles.

Justin Kopinsky, un estudiante graduado del MIT en ingeniería eléctrica e informática y uno de los

Los investigadores probaron el algoritmo SprayList utilizando un servidor Fujitsu RX600 S6 con cuatro procesadores Intel Xeon E7-4870 (Westmere EX) de 10 núcleos, que admiten un total de 80 subprocesos de hardware (aproximadamente una configuración de 80 núcleos). Al ejecutar varios puntos de referencia, detallados en su artículo, se dijo que el algoritmo lograba una reducción drástica en la contención. Los investigadores explican que, si bien un enfoque aleatorio tarda más en evitar la cola que las colas de prioridad convencionales, la ganancia en escalabilidad ha superado el trabajo adicional para cargas de trabajo razonablemente paralelas. Además, afirman que los parámetros de relajación de su algoritmo se pueden ajustar para aumentar aún más el rendimiento según la carga de trabajo específica y los recuentos de núcleos.

Los investigadores presentarán sus hallazgos este mes en el Simposio de la Association for Computing Machinery sobre los principios y la práctica de la programación paralela.

Deberías compartir en en tu Twitter y Facebook para que tus amigos lo sepan

??? ? ? ???

Comparte