Saltar a contenido

El map es una operación que consiste en aplicar una función a cada elemento de una colección. Esta operación tiene la propiedad de que cada aplicación es independiente, lo que significa que el resultado de aplicar la función a un elemento no depende del resultado de aplicarla a otros elementos.

Como cada operación es independiente, no nos preocupamos por dependencias en la paralelización.

Paralelización usando límite y umbral

Vamos a dividir el arreglo por mitades, cumpliendo dos condiciones:

  1. Máxima profundidad dada
  2. Aplicando un límite de tamaño: para arreglos más pequeños no vamos a paralelizar
/*
 * This Scala source file was generated by the Gradle 'init' task.
 */
package taller
import common._
import org.scalameter._

object App {

  // Versión secuencial del map para un segmento del array
  def mapSegSeq[A,B](a:Array[A], f: A=>B, ini:Int, fin:Int, sal: Array[B]):Array[B] = {
      // Itera sobre el rango [ini, fin) aplicando f a cada elemento
      for (i <- ini until fin) {
        sal(i) = f(a(i))
      }
      sal
  }

  // Versión paralela recursiva del map con control de profundidad y límite
  def mapSeq[A,B](a:Array[A], f: A=>B, ini:Int, fin:Int, prof:Int, limite:Int, cntProf:Int = 0, sal:Array[B]):Array[B] = {
    // Caso base: si se alcanza la profundidad máxima o el segmento es menor al límite
    if (cntProf >= prof || (fin-ini) < limite) {
      mapSegSeq[A,B](a, f, ini, fin, sal)  // Procesamiento secuencial
    }
    else{
      // Divide en la mitad para procesamiento paralelo
      val mid = (ini + fin) / 2
      // Invoca en paralelo las dos mitades usando la función parallel
      val (left: Array[B], right: Array[B]) = parallel(
        mapSeq[A,B](a, f, ini, mid, prof, limite, cntProf + 1, sal),
        mapSeq[A,B](a, f, mid, fin, prof, limite, cntProf + 1, sal)
      )
      sal  // Retorna el array de salida modificado
    }
  }

  def main(args: Array[String]): Unit = {
    val n = 1000000
    val arr = (1 to n).toArray
    val sal = (1 to n).map(_ => 0).toArray
    val f = (x:Int) => 2*x

    // Medición del tiempo para versión secuencial
    val t0 = withWarmer(new Warmer.Default) measure {
      val result = mapSegSeq[Int,Int](arr, f, 0, arr.length, sal)
    }
    println(s"El tiempo secuencial es ${t0}")

    val limite = 1000
    val prof = 4
    // Medición del tiempo para versión paralela
    val t1 = withWarmer(new Warmer.Default) measure {
      val result = mapSeq[Int, Int](arr, f, 0, arr.length, prof, limite, 0, sal)
    }
    println(s"El tiempo con profundidad 4 es ${t1}")
    println(s"Speedup: ${t0.value/t1.value}")
  }

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

Concepto teórico adicional: La estrategia de "divide y vencerás" aplicada aquí utiliza dos criterios para decidir cuándo paralelizar: profundidad máxima y tamaño mínimo del segmento. Esto evita la sobrecarga de crear demasiadas tareas paralelas para segmentos pequeños, donde el costo de la paralelización superaría los beneficios.

Árboles

Vamos a transformar el arreglo en una estructura tipo árbol, donde los vértices vamos a paralelizarlos y las hojas las vamos a resolver de forma secuencial.

Generamos la clase árbol

package taller

// Definición de la estructura de árbol para paralelización
sealed abstract class Tree[A] {
  val size: Int  // Tamaño total del árbol (número de elementos)
}
case class Leaf[A](a: Array[A]) extends Tree[A] {
  val size: Int = a.length  // Las hojas contienen arrays de elementos
}

case class Node[A](left: Tree[A], right: Tree[A]) extends Tree[A] {
  val size: Int = left.size + right.size  // Los nodos combinan subárboles
}

La creación y llamado

// Función para aplicar map sobre la estructura de árbol de forma paralela
def mapTreeSeq[A:Manifest,B:Manifest](t: Tree[A], f: A=>B): Tree[B] = t match {
  case Leaf(a) => Leaf(a.map(f))  // Caso base: aplica f secuencialmente a las hojas
  case Node(l, r) => 
    // Caso recursivo: procesa subárboles izquierdo y derecho en paralelo
    val (left: Tree[B], right: Tree[B]) = parallel(
      mapTreeSeq[A,B](l, f),
      mapTreeSeq[A,B](r, f)
    )
    Node(left, right)  // Combina los resultados
}

// En la función main, agregamos:
// Construcción de un árbol balanceado de profundidad 3
val tree:Tree[Int] = Node(
  Node(
    Node(
      Leaf(arr.slice(0, n/8)),        // Primera octava parte
      Leaf(arr.slice(n/8, n/4))       // Segunda octava parte
    ),
    Node(
      Leaf(arr.slice(n/4, 3*n/8)),    // Tercera octava parte
      Leaf(arr.slice(3*n/8, n/2))     // Cuarta octava parte
    )
  ),
  Node (
    Node(
      Leaf(arr.slice(n/2, 5*n/8)),    // Quinta octava parte
      Leaf(arr.slice(5*n/8, 3*n/4))   // Sexta octava parte
    ),
    Node(
      Leaf(arr.slice(3*n/4, 7*n/8)),  // Séptima octava parte
      Leaf(arr.slice(7*n/8, n))       // Octava octava parte
    )
  )
)

// Medición del tiempo para la versión con árboles
val t2 = withWarmer(new Warmer.Default) measure {
  val resultTree = mapTreeSeq[Int,Int](tree, f)
}
println(s"El tiempo en el árbol es ${t2}")
println(s"Speedup con árboles es ${t0.value/t2.value}")

Comparación

Ahora vamos a comparar el secuencial, con el paralelo de forma recursiva y el paralelo con estructura tipo árbol:

El tiempo secuencial es 9.273162 ms
El tiempo con profundidad 4 es 2.814981 ms
Speedup de forma recursiva: 3.294218326873254
El tiempo en el árbol es 1.757239 ms
Speedup con árboles es 5.277120528283289

Observemos que la aceleración con árboles es 5.27 frente a la aceleración de forma recursiva con profundidad 4, que es 3.29.

Lo que sucede es que la forma recursiva agrega latencia debido a que requiere frames y carga de variables, frente al árbol que es una estructura que se va construyendo a medida que se ejecuta el algoritmo.

Concepto teórico adicional: La estructura de árbol proporciona mejor escalabilidad porque cada nodo puede procesarse independientemente sin la sobrecarga de la división recursiva continua. Esto reduce el "fork-join overhead" y aprovecha mejor el paralelismo a nivel de hardware.