¿Por qué estas rutinas no escalan su rendimiento de más ejecuciones concurrentes?

Fondo

Actualmente estoy trabajando en mi tesis de licenciatura y básicamente mi tarea es optimizar un código dado en Go, es decir, hacer que funcione lo más rápido posible. Primero, optimicé la función serial y luego traté de introducir el paralelismo a través de goroutines. Después de investigar en Internet ahora entiendo la diferencia entre simultaneidad y paralelismo gracias a las siguientes diapositivas de talks.golang . Visité algunos cursos de progtwigción paralelos donde paralelizamos el código ac / c ++ con la ayuda de pthread / openmp, así que traté de aplicar estos paradigmas en Go. Dicho esto, en este caso particular estoy optimizando una función que calcula la media móvil de una porción con longitud len:=n+(window_size-1) (es igual a 9393 o 10175), por lo tanto, tenemos n ventanas de las cuales calculamos el el promedio aritmético correspondiente y guardarlo correctamente en el segmento de salida.

Tenga en cuenta que esta tarea es inherentemente vergonzosa paralela.

Mis bashs de optimización y resultados

En moving_avg_concurrent2 la porción en piezas más pequeñas de num_goroutines y ejecuté cada una con un solo goroutine. Esta función se realiza con una rutina, por alguna razón (no se pudo averiguar por qué todavía, pero estamos obteniendo tangente aquí), mejor que moving_avg_serial4 pero con más de una rutina, comenzó a funcionar peor que moving_avg_serial4 .
En moving_avg_concurrent3 adopté el paradigma maestro / trabajador. El rendimiento fue peor que moving_avg_serial4 cuando se usa una rutina. Aquí, al menos, obtuve un mejor rendimiento al boost num_goroutines pero aún así no es mejor que moving_avg_serial4 . Para comparar las actuaciones de moving_avg_serial4 , moving_avg_concurrent2 y moving_avg_concurrent3 escribí un punto de referencia y tabulé los resultados:

 fct & num_goroutines | timing in ns/op | percentage --------------------------------------------------------------------- serial4 | 4357893 | 100.00% concur2_1 | 5174818 | 118.75% concur2_4 | 9986386 | 229.16% concur2_8 | 18973443 | 435.38% concur2_32 | 75602438 | 1734.84% concur3_1 | 32423150 | 744.01% concur3_4 | 21083897 | 483.81% concur3_8 | 16427430 | 376.96% concur3_32 | 15157314 | 347.81% 

Pregunta

Como como se mencionó anteriormente este problema es vergonzosamente paralelo, esperaba ver un tremendo aumento en el rendimiento, pero ese no fue el caso.

¿Por qué moving_avg_concurrent2 no escala en absoluto?
¿Y por qué moving_avg_concurrent3 es mucho más lento que moving_avg_serial4 ?
Sé que los goroutines son baratos, pero todavía no son gratuitos, pero ¿es posible que esto genere tanta sobrecarga, de modo que somos incluso más lentos que moving_avg_serial4 ?

Código

Funciones:

 // returns a slice containing the moving average of the input (given, ie not optimised) func moving_avg_serial(input []float64, window_size int) []float64 { first_time := true var output = make([]float64, len(input)) if len(input) > 0 { var buffer = make([]float64, window_size) // initialise buffer with NaN for i := range buffer { buffer[i] = math.NaN() } for i, val := range input { old_val := buffer[int((math.Mod(float64(i), float64(window_size))))] buffer[int((math.Mod(float64(i), float64(window_size))))] = val if !NaN_in_slice(buffer) && first_time { sum := 0.0 for _, entry := range buffer { sum += entry } output[i] = sum / float64(window_size) first_time = false } else if i > 0 && !math.IsNaN(output[i-1]) && !NaN_in_slice(buffer) { output[i] = output[i-1] + (val-old_val)/float64(window_size) // solution without loop } else { output[i] = math.NaN() } } } else { // empty input fmt.Println("moving_avg is panicking!") panic(fmt.Sprintf("%v", input)) } return output } // returns a slice containing the moving average of the input // reordering the control structures to exploid the short-circuit evaluation func moving_avg_serial4(input []float64, window_size int) []float64 { first_time := true var output = make([]float64, len(input)) if len(input) > 0 { var buffer = make([]float64, window_size) // initialise buffer with NaN for i := range buffer { buffer[i] = math.NaN() } for i := range input { // fmt.Printf("in mvg_avg4: i=%v\n", i) old_val := buffer[int((math.Mod(float64(i), float64(window_size))))] buffer[int((math.Mod(float64(i), float64(window_size))))] = input[i] if first_time && !NaN_in_slice(buffer) { sum := 0.0 for j := range buffer { sum += buffer[j] } output[i] = sum / float64(window_size) first_time = false } else if i > 0 && !math.IsNaN(output[i-1]) /* && !NaN_in_slice(buffer)*/ { output[i] = output[i-1] + (input[i]-old_val)/float64(window_size) // solution without loop } else { output[i] = math.NaN() } } } else { // empty input fmt.Println("moving_avg is panicking!") panic(fmt.Sprintf("%v", input)) } return output } // returns a slice containing the moving average of the input // splitting up slice into smaller pieces for the goroutines but without using the serial version, ie we only have NaN's in the beginning, thus hope to reduce some overhead // still does not scale (decreasing performance with increasing size and num_goroutines) func moving_avg_concurrent2(input []float64, window_size, num_goroutines int) []float64 { var output = make([]float64, window_size-1, len(input)) for i := 0; i  0 { num_items := len(input) - (window_size - 1) var barrier_wg sync.WaitGroup n := num_items / num_goroutines go_avg := make([][]float64, num_goroutines) for i := 0; i < num_goroutines; i++ { go_avg[i] = make([]float64, 0, num_goroutines) } for i := 0; i < num_goroutines; i++ { barrier_wg.Add(1) go func(go_id int) { defer barrier_wg.Done() // computing boundaries var start, stop int start = go_id*int(n) + (window_size - 1) // starting index // ending index if go_id != (num_goroutines - 1) { stop = start + n // Ending index } else { stop = num_items + (window_size - 1) // Ending index } loc_avg := moving_avg_serial4(input[start-(window_size-1):stop], window_size) loc_avg = make([]float64, stop-start) current_sum := 0.0 for i := start - (window_size - 1); i < start+1; i++ { current_sum += input[i] } loc_avg[0] = current_sum / float64(window_size) idx := 1 for i := start + 1; i < stop; i++ { loc_avg[idx] = loc_avg[idx-1] + (input[i]-input[i-(window_size)])/float64(window_size) idx++ } go_avg[go_id] = append(go_avg[go_id], loc_avg...) }(i) } barrier_wg.Wait() for i := 0; i < num_goroutines; i++ { output = append(output, go_avg[i]...) } } else { // empty input fmt.Println("moving_avg is panicking!") panic(fmt.Sprintf("%v", input)) } return output } // returns a slice containing the moving average of the input // change of paradigm, we opt for a master worker pattern and spawn all windows which each will be computed by a goroutine func compute_window_avg(input, output []float64, start, end int) { sum := 0.0 size := end - start for _, val := range input[start:end] { sum += val } output[end-1] = sum / float64(size) } func moving_avg_concurrent3(input []float64, window_size, num_goroutines int) []float64 { var output = make([]float64, window_size-1, len(input)) for i := 0; i  0 { num_windows := len(input) - (window_size - 1) var output = make([]float64, len(input)) for i := 0; i < window_size-1; i++ { output[i] = math.NaN() } pending := make(chan *Work) done := make(chan *Work) // creating work go func() { for i := 0; i < num_windows; i++ { pending <- NewWork(compute_window_avg, input, output, i, i+window_size) } }() // start goroutines which work through pending till there is nothing left for i := 0; i < num_goroutines; i++ { go func() { Worker(pending, done) }() } // wait till every work is done for i := 0; i < num_windows; i++ { <-done } return output } else { // empty input fmt.Println("moving_avg is panicking!") panic(fmt.Sprintf("%v", input)) } return output } 

Puntos de referencia:

 //############### BENCHMARKS ############### var import_data_res11 []float64 func benchmarkMoving_avg_serial(b *testing.B, window int) { var r []float64 for n := 0; n < bN; n++ { r = moving_avg_serial(BackTest_res.F["Trading DrawDowns"], window) } import_data_res11 = r } var import_data_res14 []float64 func benchmarkMoving_avg_serial4(b *testing.B, window int) { var r []float64 for n := 0; n < bN; n++ { r = moving_avg_serial4(BackTest_res.F["Trading DrawDowns"], window) } import_data_res14 = r } var import_data_res16 []float64 func benchmarkMoving_avg_concurrent2(b *testing.B, window, num_goroutines int) { var r []float64 for n := 0; n < bN; n++ { r = moving_avg_concurrent2(BackTest_res.F["Trading DrawDowns"], window, num_goroutines) } import_data_res16 = r } var import_data_res17 []float64 func benchmarkMoving_avg_concurrent3(b *testing.B, window, num_goroutines int) { var r []float64 for n := 0; n < bN; n++ { r = moving_avg_concurrent3(BackTest_res.F["Trading DrawDowns"], window, num_goroutines) } import_data_res17 = r } func BenchmarkMoving_avg_serial_261x10(b *testing.B) { benchmarkMoving_avg_serial(b, 261*10) } func BenchmarkMoving_avg_serial4_261x10(b *testing.B) { benchmarkMoving_avg_serial4(b, 261*10) } func BenchmarkMoving_avg_concurrent2_261x10_1(b *testing.B) { benchmarkMoving_avg_concurrent2(b, 261*10, 1) } func BenchmarkMoving_avg_concurrent2_261x10_8(b *testing.B) { benchmarkMoving_avg_concurrent2(b, 261*10, 8) } func BenchmarkMoving_avg_concurrent3_261x10_1(b *testing.B) { benchmarkMoving_avg_concurrent3(b, 261*10, 1) } func BenchmarkMoving_avg_concurrent3_261x10_8(b *testing.B) { benchmarkMoving_avg_concurrent3(b, 261*10, 8) } //############### BENCHMARKS end ############### 

Observaciones:
Esta es mi primera publicación, todavía estoy aprendiendo, por lo que cualquier crítica constructiva también es bienvenida.

Hecho # 0: los esfuerzos de optimización pre-maduros a menudo tienen rendimientos negativos
mostrando que son solo una pérdida de tiempo y esfuerzo


¿Por qué?
Un solo SLOC “incorrecto” puede devastar el rendimiento en más de aproximadamente + 37%
o puede mejorar el rendimiento para gastar menos del -57% del tiempo de procesamiento de referencia

 51.151µs on MA(200) [10000]float64 ~ 22.017µs on MA(200) [10000]int 70.325µs on MA(200) [10000]float64 

¿Por qué []int -s?
Lo ves por ti mismo arriba: este es el pan de cada día para las estrategias de procesamiento HPC / fintech eficientes sub- [us] (y aún hablamos en términos de solo la progtwigción del proceso [SERIAL] ).

Éste puede probar en cualquier escala, pero primero prueba (aquí) tus propias implementaciones, en la misma escala – MA(200) [10000]float64 configuración MA(200) [10000]float64 – y publica las duraciones de tu línea de base en [us] para ver el proceso inicial rendimiento y para comparar manzanas con manzanas , teniendo el umbral publicado de 51.2 [us] para comparar.

Luego viene la parte más difícil:


Hecho # 1: Esta tarea NO es vergonzosamente paralela

Sí, uno puede ir e implementar un cálculo de Promedio Móvil, de modo que de hecho proceda a través de montones de datos usando un enfoque de procesamiento “justo” – [CONCURRENT] intencionalmente adoctrinedo (independientemente de si se debe a algún tipo de error, algún “consejo” de autoridad ) “ , ceguera profesional o simplemente de una doble ignorancia de Sócrates-justa) que obviamente no significa que la naturaleza del procesamiento de flujo convolucional, presente dentro de la formulación matemática Moving Average, haya olvidado ser un proceso puro [SERIAL] , solo debido a un bash de aplicarlo, calcule dentro de cierto grado de procesamiento “justo” – [CONCURRENT] .

(Por cierto, los informáticos duros y los nerds de doble dominio también objetarán aquí, que Go-language es, por diseño, que utiliza las mejores habilidades de Rob Pike para tener un marco de corrutinas concurrentes, no una planificación de procesos verdaderos [PARALLEL] , incluso aunque las herramientas CSP de Hoare, disponibles en el concepto de lenguaje, pueden agregar sal y pimienta e introducir un tipo de bloque de herramientas de comunicación entre procesos, que bloquearán secciones de código “justo” – [CONCURRENT] en algunos CSP-p2p cableados -sincronización)


Hecho # 2: ir distribuido (para cualquier tipo de aceleración) solamente AL FINAL

Tener un bajo nivel de rendimiento en [SERIAL] no establece ningún criterio. Tener una cantidad razonable de ajuste de rendimiento en single-thread, solo entonces uno puede beneficiarse distribuyéndose (aún teniendo que pagar costos de serie adicionales, lo que hace que Amdahl Law (más bien Overhead-strict -Amdahl Law ) entre al juego).

Si uno puede introducir un nivel tan bajo de configuración adicional-overheads y aun así lograr cualquier paralelismo notable, escalado en la parte no [SEQ] del procesamiento , allí y solo existe la posibilidad de boost el rendimiento efectivo del proceso.

No es difícil perder mucho más que ganar en esto, así que siempre compare la pureza [SEQ] frente a las compensaciones potenciales entre una non-[SEQ] / N[PAR]_processes teórica e ingenua que non-[SEQ] / N[PAR]_processes , para la cual pagará un costo de una sum de todas las add-on- [SEQ] -overheads, por lo tanto, si y solo si:

 ( pure-[SEQ]_processing [ns] + add-on-[SEQ]-setup-overheads [ns] + ( non-[SEQ]_processing [ns] / N[PAR]_processes ) ) << ( pure-[SEQ]_processing [ns] + ( non-[SEQ]_processing [ns] / 1 ) ) 

Al no tener esta ventaja para los aviones a reacción, tanto de la altura excedente como de Sun, nunca intentes entrar en ningún tipo de bashs de HPC / paralelismo: nunca pagarán por sí mismos al no ser notablemente mejores que un proceso inteligente [SEQ] .


enter image description here

Epílogo: sobre la IU de experimento interactivo de la Ley Amdahl estricta y estricta

Una animación vale más que millones de palabras.

Una animación interactiva aún mejor:

Asi que,
se supone un proceso bajo prueba, que tiene una parte [SERIAL] y una [PARALLEL] del cronogtwig del proceso.

Deje p ser la fracción [PARALLEL] de la duración del proceso ~ ( 0.0 .. 1.0 ) lo que la parte [SERIAL] no dura más que ( 1 - p ) , ¿verdad?

Entonces, comencemos la experimentación interactiva de tal caso de prueba, donde p == 1.0 , lo que significa que toda la duración del proceso se gasta en solo una parte [PARALLEL] , y tanto la serie inicial como las partes finales del flujo de proceso ( que principalmente son siempre [SERIAL] ) tienen duraciones cero ( ( 1 - p ) == 0. )

Supongamos que el sistema no hace magia en particular y, por lo tanto, necesita pasar algunos pasos reales en la inicialización de cada parte de [PARALLEL] , para poder ejecutarlo en un procesador diferente ( (1), 2, .., N ) , entonces vamos a agregue algunos gastos generales, si se le pide que reorganice el flujo del proceso y marque + distribuya + elimine todas las instrucciones y datos necesarios, de modo que el proceso previsto ahora pueda iniciarse y ejecutarse en N procesadores en paralelo.

Estos costos se denominan o (aquí se supone inicialmente que la simplicidad es constante e invariante para N , lo que no siempre es el caso real, en silicio / en NUMA / en infraestructuras distribuidas).

Al hacer clic en el título de Epílogo anterior, se abre un entorno interactivo y es libre para la propia experimentación.

Con p == 1. && o == 0. && N > 1 el rendimiento está creciendo abruptamente a los límites actuales de O / S de hardware [PARALLEL] alcanzables para una ejecución de código O / S todavía monolítica (donde aún no hay costos de distribución adicionales) para MPI- y distribuciones similares de depeche-mode de unidades de trabajo (donde uno tendría que agregar inmediatamente una gran cantidad de [ms] , mientras que nuestra mejor implementación [SERIAL] obviamente hizo todo el trabajo en menos que solo ~ 22.1 [nosotros] )).

Pero a excepción de este caso artificialmente optimista, el trabajo no parece tan barato para ser paralelizado eficientemente.

  • Intente no tener un cero, pero aproximadamente ~ 0.01% los costos generales de configuración de o , y la línea comienza a mostrar una naturaleza muy diferente de la escala de overhead para incluso el caso extremo [PARALLEL] (teniendo aún p == 1.0 ), y teniendo la aceleración potencial en algún lugar cerca de la mitad del caso de aceleración lineal inicialmente súper idealista.

  • Ahora, pon el p a algo más cercano a la realidad, en algún lugar menos artificialmente establecido que el caso super-idealista inicial de == 1.00 --> { 0.99, 0.98, 0.95 } y ... bingo, esta es la realidad, donde el proceso- la progtwigción debe ser probada y validada previamente.

Qué significa eso?

Como ejemplo, si una sobrecarga (de lanzamiento + unión final a un grupo de corrutinas) tomaría más de ~ 0.1% de la duración real de la sección de procesamiento [PARALLEL] , no habría una aceleración mayor de 4x (aproximadamente un 1/4 de la duración original en el tiempo) para 5 corutinas (teniendo p ~ 0.95), no más de 10x (una duración 10 veces más rápida) para 20 corutinas (todas suponiendo que un sistema tiene 5 núcleos de CPU, respectivamente 20 CPU) núcleos libres, disponibles y listos (lo mejor es con procesos / subprocesos mapeados de núcleo de CPU de nivel O / S) para servir ininterrumpidamente a todas las coroutines durante toda su vida útil, para lograr cualquier aceleración esperada.

Al no tener dicha cantidad de recursos de hardware libres y listas para todas esas unidades de tareas, destinadas a implementar la parte [PARALLEL] del cronogtwig de proceso, los estados de locking / espera introducirán estados de espera absolutos adicionales y el rendimiento resultante agrega estas nuevas secciones [SERIAL] locking / espera a la duración total del proceso y las aceleraciones inicialmente deseadas dejan de existir repentinamente y el factor de rendimiento cae muy por debajo de << 1.00 (lo que significa que el tiempo de ejecución efectivo se debió) a los estados de locking mucho más lentos, que el flujo de trabajo just-paralleled solo- [SERIAL] ).

Esto puede sonar complicado para los nuevos experimentadores entusiastas, sin embargo podemos ponerlo en una perspectiva inversa. Dado el conjunto del proceso de distribución, el grupo de tareas previsto [PARALLEL] no es más corto que, digamos, alrededor de 10 [us] , muestran los gráficos estrictos generales, debe haber al menos aproximadamente 1000 x 10 [us] de procesamiento intensivo de cómputo sin locking dentro de la sección [PARALLEL] para no devastar la eficiencia del parallel processing.

Si no hay un pedazo de procesamiento "gordo", los costos indirectos (que van notablemente por encima del umbral mencionado anteriormente de ~ 0.1% ) luego devastan brutalmente la eficiencia neta del procesamiento paralelizado exitoso (pero habiendo realizado en tal costes relativos injustificadamente elevados de la configuración frente a los efectos netos limitados de cualquier procesador N , como se demostró en los gráficos en vivo disponibles).

No es de sorprender que los nerds de computación distribuida, que la sobrecarga o viene con también dependencias adicionales, en N (cuantos más procesos, más esfuerzos se deben gastar para distribuir paquetes de trabajo), en los datos marshalados, los tamaños de los BLOB (el cuanto mayor sean los BLOB, más tiempo permanecerán bloqueados los dispositivos MEM / IO, antes de servir el siguiente proceso para recibir un BLOB distribuido a través de dicho dispositivo / recurso para cada uno de los objectives 2..N -ésimo proceso de recepción), en evitados / CSP -coordinación entre procesos mediada por un canal, designada (llamada locking adicional por incidente, reduciendo la p más y más por debajo del ideal de 1. ).

Entonces, la realidad del mundo real está bastante lejos de lo inicialmente idealizado, agradable y prometedor p == 1.0 , ( 1 - p ) == 0.0 y o == 0.0

Como es obvio desde el principio, intente vencer el umbral de 22.1 [us] [SERIAL] , que tratar de superar esto, mientras empeora cada vez más, si va [PARALLEL] donde los gastos indirectos y escalado son realistas, usando enfoques que ya están bajo rendimiento , no ayuda un solo bit.

    Intereting Posts