Dienstag, 15. Dezember 2015

Akka.NET Adventskalender – Tür 15

Teile und Herrsche

Gestern sind wir auf ein Problem gestoßen. Eine lang laufende CPU-intensive Berechnung schrie förmlich nach Verbesserung. Der Gedanke zur Lösung war, die Aufgabe in kleinere voneinander unabhängige Teile zu zerlegen, die wir dann jeweils einzelnen Akoten zur Bearbeitung geben konnten.

Damit wir besser mit verschiedenen Partitionierungs-Strategien experimentieren können, erzeugen wir uns zunächst einen Generator, der den Bereich von dem wir ausgehen, in eine vorgegebene Anzahl jeweils gleich großer Bereiche aufteilt.

Dafür definieren wir eine Klasse Range, die jeweils den Bereich (inklusive der Grenzen) definiert:

public class Range
{
    public int StartAt { get; set; }
    public int EndAt { get; set; }

    public Range (int startAt, int endAt)
    {
        StartAt = startAt;
        EndAt = endAt;
    }

    public override string ToString()
    {
        return string.Format("[Range: StartAt={0}, EndAt={1}]", 
            StartAt, EndAt);
    }
}

Die Überladung von ToString() brauchen wir später um einige Diagnose-Ausgaben einfacher erzeugen zu können. Und eine Generator-Methode könnte so aussehen:

public static IEnumerable<Range> Distribute(int rangeMax, int nrParts)
{
    int rangeStartAt = 0;
    int nrPartsRemaining = nrParts;

    while (nrPartsRemaining > 0)
    {
        int rangeEndAt = rangeStartAt + 
            (rangeMax - rangeStartAt) / nrPartsRemaining;
        
        yield return new Range(rangeStartAt, rangeEndAt);
        
        rangeStartAt = rangeEndAt + 1;
        nrPartsRemaining--;
    }
}

Zur Verdeutlichung ein paar Beispiele:

20 - 3 parts: 
    [Range: 0...6], 
    [Range: 7...13], 
    [Range: 14...20]

1000 - 6 parts: 
    [Range: 0...166], 
    [Range: 167...333], 
    [Range: 334...500], 
    [Range: 501...667], 
    [Range: 668...834], 
    [Range: 835...1000]

Bewaffnet mit dieser Verteilungs-Logik können wir nun einen Aktor erzeugen, der die Berechnung der Summe für einen bestimmten Bereich vornimmt. Erst mal belassen wir es bei einem rechnenden Aktor bis wir wissen ob alles funktioniert, danach teilen wir auf.

Tatsächlich allerdings brauchen wir zwei Aktoren, einen Master, der die Arbeit an seine Worker verteilt, die Ergebnisse sammelt und die tatsächliche Summe bildet und die Worker, die die Berechnungen ausführen.

Die zentralen Teile des Master könnten so aussehen:

public class Master : ReceiveActor
{
    public class CalculatePi {}

    IActorRef worker;
    double sum;

    public Master()
    {
        worker = Context.ActorOf(Props.Create<Worker>());

        Receive<CalculatePi>(c => DoCalculation(c));
        Receive<double>(s => AddToSum(s));
    }

    private void DoCalculation(CalculatePi _)
    {
        sum = 0;

        foreach (var range in Distribute(RangeTo, NrParts))
            worker.Tell(new Worker.CalculateRange(range));
    }

    private void AddToSum(double d)
    {
        sum += d;
    }
}

und unser Worker könnte zum Beispiel so implementiert werden:

public class Worker : ReceiveActor
{
    public class CalculateRange : Range
    {
        public CalculateRange(Range range) 
            : base(range) {}

        public CalculateRange(int startAt, int endAt) 
            : base(startAt, endAt) {}
    }
 
    public Worker()
    {
        Receive<CalculateRange>(CalculateRangeHandler);
    }
 
    private void CalculateRangeHandler(CalculateRange range)
    {
        // calculate
        double sum = 0;
        for (int n = range.StartAt; n <= range.EndAt; n++)
            sum += Math.Pow(-1, n) / (2 * n + 1);

        // send back result. If we multiply by 4 here, the sender will
        // automatically contain pi.
        Sender.Tell(sum * 4);
    }
}

Damit Du das ganze nicht mühsam abtippen musst, habe ich ein kleines github Repository vorbereitet, in dem die gesamte Applikation steckt.

Damit haben wir die Arbeit in gleiche Teile aufgeteilt und diese jeweils an unsere Worker Aktoren weitergegeben. Allerdings haben wir derzeit nur eine Instanz des Worker Aktors, der die eigentliche Arbeit erledigt. Sicher errätst Du was das bedeutet – die Gesamtzeit für die Lösung der Aufgabe hat sich leider noch nicht verbessert. Die Ursache liegt auf der Hand: wir haben nur einen Aktor, der alle Nachrichten empfängt und es ist ja ein wesentliches Merkmal eines Aktors immer nur eine Nachricht zu verarbeiten.

Damit bleibt noch etwas Raum für Verbesserungen, die wir morgen in Angriff nehmen werden.

Keine Kommentare:

Kommentar veröffentlichen