W jaki sposób Scala używa tutaj wszystkich moich rdzeni?

Question

object PrefixScan { 
    sealed abstract class Tree[A] 
    case class Leaf[A](a: A) extends Tree[A] 
    case class Node[A](l: Tree[A], r: Tree[A]) extends Tree[A] 

    sealed abstract class TreeRes[A] { val res : A } 
    case class LeafRes[A](override val res: A) extends TreeRes[A] 
    case class NodeRes[A](l : TreeRes[A], override val res: A, r: TreeRes[A]) extends TreeRes[A] 

    def reduceRes[A](t: Tree[A], f:(A,A)=>A): TreeRes[A] = t match { 
    case Leaf(v) => LeafRes(v) 
    case Node(l, r) => { 
     val (tL, tR) = (reduceRes(l, f), reduceRes(r, f)) 
     NodeRes(tL, f(tL.res, tR.res), tR) 
    } 
    } 
} 

Niepokoi mnie funkcja reduceRes.

Działa ... wynik obliczeń jest świetny!

Jednak zastosowałem inną wersję, reduceResPar, która używa łączenia widełek w pierwszych kilku gałęziach, aby zrównoważyć obliczenia. Ale nie przyspieszyło.

Potem wróciłem i zrozumiałem .. powyższa wersja, reduceRes, już używa wszystkich 12 rdzeni na mojej maszynie !! Jak to zrobić? Myślałem, że to tylko 1 rdzeń!

Ten kod pochodzi z kursu Parallel Programming na Coursera. Podczas ostatniego wykładu w drugim tygodniu, uczymy się o operacjach równoległego skanowania przedrostkowego.

Answer 1

Jak to zrobić? Myślałem, że to tylko 1 rdzeń!

Fakt, że używane są wszystkie używane rdzenie, nie oznacza, że ​​wykonywanie kodu jest równoległe. Z jego implementacji wynika, że ​​jest sekwencyjny, ale nie wiemy, który procesor nasz pojedynczy wątek zostanie zaplanowany przez system operacyjny w każdym cyklu.

Po uruchomieniu metody wewnątrz wątku system operacyjny decyduje o liczbie uzyskanych fragmentów czasu procesora i czasie, w którym zarządza kolejką priorytetową.

Aby zobaczyć, że twój algorytm może działać na różnych rdzeniach, możemy zapytać OS, na którym logicznym rdzeniu aktualnie wykonuje nasz wątek. Przygotowałem małą implementację dla systemu Windows, która ma natywną metodę WinAPI o nazwie GetCurrentProcessorNumber(), która zwraca numer procesora, na którym wykonujemy. Użyjemy JNA na przykład:

build.sbt:

"net.java.dev.jna" % "jna" % "4.4.0" 

Java realizacja:

import com.sun.jna.Library; 
import com.sun.jna.Native; 

public class ProcessorNumberNative { 

    public interface CLibrary extends Library { 
     CLibrary INSTANCE = (CLibrary) 
       Native.loadLibrary("Kernel32.dll", 
         CLibrary.class); 

     Integer GetCurrentProcessorNumber(); 
    } 
} 

Teraz dodajmy println na każdym z etapów swojej rekursji:

def reduceRes[A](t: Tree[A], f: (A, A) => A): TreeRes[A] = t match { 
    case Leaf(v) => 
    println(s"Logical Processor Number: ${ProcessorNumberNative.CLibrary.INSTANCE.GetCurrentProcessorNumber()}") 
    LeafRes(v) 

    case Node(l, r) => 
    println(s"Logical Processor Number: ${ProcessorNumberNative.CLibrary.INSTANCE.GetCurrentProcessorNumber()}") 
    val (tL, tR) = (reduceRes(l, f), reduceRes(r, f)) 
    NodeRes(tL, f(tL.res, tR.res), tR) 
} 

Teraz utwórzmy drzewo i wykonaj:

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

    val tree = Node(Leaf(1), 
       Node(Leaf(2), 
        Node(Node(Leaf(24), Leaf(30)), 
          Node(Leaf(3), Node(Leaf(10), Leaf(52)))))) 

    reduceRes(tree, (a: Int, b: Int) => a + b) 
} 

I dać to dwa różne przebiegi (Biegnę komputer z 4 rdzeniami logicznymi):

pierwsze:

Logical Processor Number: 1 
Logical Processor Number: 3 
Logical Processor Number: 3 
Logical Processor Number: 3 
Logical Processor Number: 0 
Logical Processor Number: 0 
Logical Processor Number: 0 
Logical Processor Number: 3 
Logical Processor Number: 0 
Logical Processor Number: 0 
Logical Processor Number: 0 
Logical Processor Number: 0 
Logical Processor Number: 0 

drugie:

Logical Processor Number: 1 
Logical Processor Number: 3 
Logical Processor Number: 1 
Logical Processor Number: 1 
Logical Processor Number: 1 
Logical Processor Number: 1 
Logical Processor Number: 1 
Logical Processor Number: 1 
Logical Processor Number: 3 
Logical Processor Number: 3 
Logical Processor Number: 3 
Logical Processor Number: 3 
Logical Processor Number: 3 

Podczas każdego wykonanie, widzisz, że wątek wykonawczy otrzymał wycinek wykonania na 3 różnych rdzeniach, 0, 1 i 3, podczas gdy wciąż pracujemy w jednym wątku vironment. To pokazuje, że chociaż obliczenie twojego algorytmu jest zdecydowanie sekwencyjne, nie oznacza to, że nie zobaczysz wszystkich swoich rdzeni w grze.