Clase 12: Paralelismo de tareas¶

Idea¶

Vamos a aplicar la idea de profundidad máxima, es decir, vamos a aplicar divide y vencerás hasta cierto punto. Después de esto, vamos a resolverlo de forma secuencial.

Para decidir la profundidad adecuada, se deben realizar pruebas de rendimiento (benchmarking).

Concepto teórico: La profundidad máxima (o cutoff depth) es un umbral que determina cuándo un algoritmo paralelo debe dejar de crear nuevas tareas paralelas y continuar de forma secuencial. Esto evita el overhead excesivo por creación de hilos o tareas cuando el tamaño del problema ya es pequeño. La elección óptima de este umbral depende de la arquitectura del hardware y de la naturaleza del problema.

/*  
 * This Scala source file was generated by the Gradle 'init' task. 
 * 
 * Ejemplo de benchmarking para determinar la profundidad óptima 
 * en un MergeSort paralelo con cutoff.
 */
package taller  
import org.scalameter._  

object App {  
  def main(args: Array[String]): Unit = {  

    val objMergesort = new MergeSort()  
    val randr = scala.util.Random  
    // Generamos una lista de 1 millón de enteros aleatorios
    val lst = (1 to 1000000).map(x => randr.nextInt()).toList  

    // Medición del tiempo secuencial (referencia base)
    val tseq = withWarmer(new Warmer.Default) measure{  
      objMergesort.mergeSortSec(lst)  
    }  

    // Medición del tiempo paralelo para diferentes profundidades (1 a 5)
    val ts = (1 to 5).map(  
      (ti) => {  
        val tsi = withWarmer(new Warmer.Default) measure{  
          // El tercer parámetro (0) es un parámetro adicional del método mergeSortPar
          objMergesort.mergeSortPar(ti)(0)(lst)  
        }  
        ("Profundidad "+ti, tsi)  
      }  
    )  
    println("Tiempo secuencial " + tseq)  
    println("Tiempo paralelo " + ts)  
  }  

  def greeting(): String = "Hello, world!"  
}

Al realizar la medición obtenemos:

Tiempo secuencial 503.391062 ms
Tiempo paralelo Vector((Profundidad 1,341.440403 ms), (Profundidad 2,335.967437 ms), (Profundidad 3,337.223449 ms), (Profundidad 4,371.88263 ms), (Profundidad 5,425.02556 ms))

Se observa que la mayor ganancia (speedup) se encuentra entre profundidad 2 y 3.

Análisis de resultados: - Profundidad 1: Crea pocas tareas paralelas, el speedup es modesto (~1.47x). - Profundidad 2: Mejor rendimiento (~1.50x), punto óptimo para este tamaño de datos. - Profundidad 3: Rendimiento similar a profundidad 2 (~1.49x), comienza a aumentar el overhead. - Profundidad 4 y 5: El overhead de creación de tareas supera la ganancia por paralelismo, el rendimiento empeora progresivamente.

Concepto teórico: El speedup se define como \(S = T_{secuencial} / T_{paralelo}\). En este caso, el mejor speedup es aproximadamente 503.39 / 335.97 ≈ 1.50x, lo cual es bajo para un sistema multicore típico. Esto sugiere que el algoritmo de MergeSort tiene una parte secuencial significativa (la fusión de listas) que limita el paralelismo según la Ley de Amdahl.

Tabla resumen de conceptos¶

Concepto	Descripción
Profundidad máxima (cutoff depth)	Umbral que define hasta qué nivel de recursión se crean tareas paralelas; más allá se ejecuta secuencialmente para evitar overhead
Divide y vencerás paralelo	Estrategia que divide el problema en subproblemas independientes que se resuelven en paralelo, luego se combinan los resultados
Benchmarking	Proceso de medir el rendimiento del algoritmo con diferentes configuraciones para encontrar los parámetros óptimos
Speedup	Relación entre el tiempo de ejecución secuencial y el tiempo de ejecución paralelo: \(S = T_{sec} / T_{par}\)
Overhead	Tiempo adicional invertido en gestionar la paralelización (creación de tareas, sincronización, comunicación) que no existe en la versión secuencial
Ley de Amdahl	Establece que el speedup máximo está limitado por la fracción del algoritmo que no puede paralelizarse: \(S_{max} = 1 / (1 - P)\), donde \(P\) es la fracción paralelizable

Comentarios adicionales: - El cutoff depth óptimo depende del tamaño del problema, la arquitectura del procesador (número de núcleos, jerarquía de caché) y la implementación concreta del algoritmo. - En sistemas con muchos núcleos, suele ser beneficioso usar una profundidad mayor, pero siempre existe un punto donde el overhead domina. - Para mejorar el speedup en MergeSort, se podría optimizar la fase de fusión (merge) que es inherentemente secuencial, o usar estructuras de datos más eficientes para la paralelización. - Es recomendable realizar múltiples mediciones y calcular promedios para obtener resultados estadísticamente significativos, ya que el rendimiento puede variar entre ejecuciones debido a factores del sistema operativo y del JVM.

Temas¶

Scan