Parallele Berechnung von Primzahlen

1. Aufgabe

Die Suche nach Primzahlen – also Zahlen, die nur durch sich selbst und durch eins teilbar sind – war lange Zeit eine der zentralsten Bestandteile der Zahlentheorie. Primzahlenjäger können neben den zahlreichen Erkenntnissen der Zahlentheoretiker heutzutage auf eine zusätzliche Hilfestellung zurückgreifen, den Computer. Wir wollen im Folgenden ein Programm entwickeln, das mit Hilfe mehrerer Threads zu zwei fest gegebenen natürlichen Zahlen n und m die Summe aller Primzahlen p mit npm bestimmt.

Für die Identifizierung einer natürlichen Zahl als Primzahl benutzen wir das einfachste (und zugegeben auch langweiligste) Verfahren, die Zahl – nennen wir sie n – der Reihe nach solange durch alle natürlichen Zahlen 2, 3, ... zu dividieren, bis entweder eine Division den Rest 0 zurückliefert (und damit ein Primfaktor gefunden wurde) oder aber der Dividend den Wert n annimmt. In diesem Fall besitzt die Zahl keine Primfaktoren, wir haben eine Primzahl gefunden. Natürlich genügt es, n nur durch all die Zahlen zu dividieren, die kleiner oder gleich als die Hälfte von n sind.

Zur Bestimmung der Primzahleigenschaft implementieren Sie eine statische Methode IsPrime:

public static bool IsPrime (long number);

IsPrime liefert true zurück, wenn der aktuelle Parameter number prim ist, andernfalls false: Die zentrale Anliegen der Anwendung besteht in der Verteilung der Primzahlenberechnungen auf mehrere Threads (Sekundärthreads). Jeder dieser Sekundärthreads entnimmt aus einem zentralen Datenobjekt den nächsten Kandidaten, der auf seine Primzahleigenschaft hin zu untersuchen ist. Das zentrale Datenobjekt stellt sicher, dass unter keinen Umständen zwei Sekundärthreads dieselbe Zahl auf ihre Primzahleigenschaft untersuchen!

Im primären Thread der Anwendung finden nur verwaltungstechnische Tätigkeiten statt. Es werden also keine Primzahlen berechnet. Zu den Aufgaben des Primärthreads zählen:

  • Verwaltung einer unteren und oberen Grenze n bzw. m aller zu untersuchenden Zahlen mit nm.

  • Verwaltung der Anzahl der Sekundärthreads, die Primzahlen berechnen.

  • Anzeige der Anzahl der durch einen Sekundärthread gefundenen Primzahlen.

  • Anzeige der Anzahl aller gefundenen Primzahlen eines bestimmten Bereichs.

Ein Architekturbild zur Realisierung mit den zuvor skizzierten Realisierungsgedanken finden Sie in Abbildung 1 vor. Auf der rechten Seite ist das zentrale Datenobjekt dargestellt (Klasse PrimeNumberCalculator). Mittels öffentlicher Eigenschaften lassen sich die obere und untere Grenze zum Suchen nach Primzahlen setzen. Die private Instanzvariable _next kann nur intern im Objekt benutzt werden – und dies vorzugsweise nur von der öffentlichen Methode CalcPrimes.

Auf der linken Seite erkennt man eine beliebige Anzahl von n Threads T1, ... Tn, die jeder für sich mit Hilfe der CalcPrimes-Methode auf der Suche nach Primzahlen sind. In der Realisierung von CalcPrimes muss sichergestellt sein, dass zwei (quasi-)parallele Aufrufe von CalcPrimes niemals dieselbe Zahl analysieren.

Architektur einer parallelen Primzahlen-Anwendung.

Abbildung 1. Architektur einer parallelen Primzahlen-Anwendung.


Das Hauptfenster der WPF-Anwendung könnte wie in Abbildung 2 gezeigt aussehen. Im oberen Bereich der Anwendung lassen sich in zwei TextBox-Objekten die untere und obere Grenze des zu untersuchenden Zahlenbereichs einzugeben. Mit dem ComboBox-Steuerelement ist die Anzahl der Sekundärthreads einzustellen, die Primzahlen suchen. Im unteren Teil der Anwendung sind in einem StackPanel-Steuerelement eine Reihe von TextBox-Objekten vertikal angeordnet, für jeden Sekundärthread eines.

Mit der Schaltfläche „Compute ...“ werden die Sekundärthreads erzeugt und gestartet. Ist ein Sekundärthread mit der Berechnung der Primzahlen fertig, beendet er sich und zeigt die Anzahl der von ihm ermittelten Primzahlen in dem ihm zugeordneten TextBox-Objekt an. Ganz unten erkennt man noch ein TextBox-Objekt, das quasi eine Art Statuszeile darstellt. Dieses enthält nach dem Ende aller Sekundärthreads das Endergebnis, also die Summe aller gefundenen Primzahlen.

Hauptfenster der WPF-Anwendung.

Abbildung 2. Hauptfenster der WPF-Anwendung.


Überlegen Sie, wie eine Klasse PrimeNumberCalculator im Detail spezifiziert werden müsste und entwerfen Sie darauf aufbauend eine entsprechende WPF-Anwendung.

2. Lösung

Wie in der Aufgabenstellung gefordert, sollte es im Hauptfenster ein zentrales Datenobjekt geben, dessen Hauptaufgabe darin besteht, für rechenwillige Sekundärthreads den nächsten Kandidaten zur Überprüfung der Primzahleigenschaft bereitzustellen. Am einfachsten ist es, diese Variable in einer Klasse, nennen wir sie PrimeNumberCalculator, zu kapseln. Mit einer Methode CalcPrimes können wir den jeweils aktuellen Kandidaten überprüfen. Gestalten wir die Methode CalcPrimes zusätzlich thread-sicher, so lassen sich beliebig viele Threads mit der CalcPrimes-Methode als Threadprozedur starten. Eine mögliche Spezifikation der PrimeNumberCalculator-Klasse entnehmen Sie Tabelle 1:

Element

Beschreibung

Eigenschaft Minimum

public long Minimum { get; set; }

Untere Grenze, die bei der Suche nach Primzahlen zu Grunde liegt.

Eigenschaft Maximum

public long Maximum { get; set; }

Obere Grenze, die bei der Suche nach Primzahlen zu Grunde liegt.

Instanzvariable _next

private long _next;

Die Instanzvariable _next verwaltet eine natürliche Zahl im Bereich von Minimum bis Maximum. Sie beschreibt die Zahl, die als nächstes zur Analyse durch einen Sekundärthread ansteht. Alle Zahlen von Minimum, Minimum+1, Minimum+2, ..., bis _next - 1 sind bereits auf ihre Primzahleigenschaft hin untersucht worden.

Die _next-Variable ist privat definiert und kann nur durch die CalcPrimes-Methode verändert (inkrementiert) werden.

Methode CalcPrimes

public void CalcPrimes ();

Die CalcPrimes-Methode ist die zentrale Methode der Klasse PrimeNumberCalculator. Sie ist von allen Sekundärthreads als Threadprozedur zu benutzen, die sich auf die Suche nach Primzahlen machen.

Es werden prinzipiell alle Zahlen im Bereich von Minimum bis Maximum untersucht. Der Übergang von einer Zahl zur nächsten erfolgt (thread-sicher!) an Hand der privaten Instanzvariablen _next. Wird die CalcPrimes-Methode (quasi-)parallel von mehreren Threads ausgeführt, kann es also sein, dass – im Kontext eines Threads – gleich mehrere Zahlen übersprungen werden, wenn ein Wechsel zum nächsten Kandidaten ansteht. Die Zahlen dazwischen wurden in der Zwischenzeit bereits von den parallel agierenden Sekundärthreads angefordert und untersucht.

Ereignis PrimeNumbersFound

public event PrimeNumbersFoundHandler PrimeNumbersFound;

Am Ende der CalcPrimes-Methode wird die Anzahl der gefundenen Primzahlen durch das PrimeNumbersFound-Ereignis publiziert. Der dazugehörige Delegate-Typ PrimeNumbersFoundHandler sieht so aus:

public delegate void PrimeNumbersFoundHandler (int tid, long found);

Der zweite Parameter found beschreibt die Anzahl der gefundenen Primzahlen. Der erste Parameter tid enthält die ID des Threads, in dessen Kontext die Berechnungen durchgeführt wurden.

Methode IsPrime

public static bool IsPrime (long number);

Liefert true zurück, wenn der aktuelle Parameter number prim ist, andernfalls false.

Tabelle 1. Klasse PrimeNumberCalculator: Zentrales Datenobjekt.


Die Gestaltung der Oberfläche führen wir in Listing 1 nur der Vollständigkeit auf, in ihr sind keine überraschenden Stolperfallen enthalten:

01: <Window x:Class="WpfMultiThreadingPrimeNumbers.MainWindow"
02:         xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
03:         xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
04:         Title="Prime Numbers Calculator" Width="400" Height="300" >
05:     <DockPanel LastChildFill="True">
06:         <Button
07:             Margin="3" Name="ButtonUsingThreads" Click="Button_Click"
08:             DockPanel.Dock="Top" >Compute using Threads</Button>
09: 
10:         <UniformGrid Margin="3"  DockPanel.Dock="Top"  Rows="1" Columns="3">
11:             <DockPanel>
12:                 <Label Width="50" >From:</Label>
13:                 <TextBox Name="TextBoxFrom" VerticalAlignment="Center">2</TextBox>
14:             </DockPanel>
15:             <DockPanel>
16:                 <Label Width="50">To:</Label>
17:                 <TextBox Name="TextBoxTo" VerticalAlignment="Center">1000000</TextBox>
18:             </DockPanel>
19:             <DockPanel>
20:                 <Label Width="70">Threads:</Label>
21:                 <ComboBox
22:                     Name="ComboBoxNumberThreads" DockPanel.Dock="Top" Margin="3,3,0,3"
23:                     SelectionChanged="ComboBoxNumberThreads_SelectionChanged">
24:                 </ComboBox>
25:             </DockPanel>
26:         </UniformGrid>
27:         
28:         <TextBox
29:             Name="TextBoxStatus" IsEnabled="False" Margin="3"
30:             DockPanel.Dock="Bottom">Status</TextBox>
31: 
32:         <ScrollViewer DockPanel.Dock="Top" VerticalScrollBarVisibility="Auto">
33:             <StackPanel Orientation="Vertical" Name="StackPanelResults" />
34:         </ScrollViewer>
35: 
36:     </DockPanel>
37: </Window>

Beispiel 1. Beschreibung des Hauptfensters in XAML.


Damit sind auch schon bei der Code-Behind-Datei des Hauptfensters angekommen (Listing 2): Die Button_Click-Methode in Zeile 56 kann nicht auf langwierige Berechnungen für Primzahlen warten, andernfalls würde das Hauptfenster blockieren. Aus diesem tut sie nichts großartig Weiteres als einen Thread (mit der Threadprozedur ComputePrimes) starten, der sich um alle weiteren Details kümmert. Dieser Thread wird mit dem Delegate-Typ ParameterizedThreadStart näher beschrieben. Aus diesem Grund werden für ihn in einem Hilfsobjekt (Klasse CalculatorData) die drei Informationen für den Wertebereich (untere und obere Grenze) und die Anzahl der Threads, die nach Primzahlen suchen sollen, zusammengestellt und an seine Start-Methode übergeben. Gleich zu Beginn der Button_Click-Methode ist noch eine Sicherheitsabfrage vorhanden, so dass nicht mehrere Primzahlenberechnungen gleichzeitig gestartet werden können.

In der ComputePrimes-Methode ab Zeile 83 sind nun alle Tätigkeiten für das parallele Suchen nach Primzahlen zusammengefasst. Dies wäre zunächst einmal das einmalige Erzeugen eines PrimeNumberCalculator-Objekts. Es stellt die Methode CalcPrimes samt aller notwendiger Daten und Sperrmechanismen bei, um parallel nach Primzahlen suchen zu können. Kommen wir zurück zur ComputePrimes-Methode. Sie wartet auf das Ende aller erzeugten Threads (Zeile 112) und aktualisiert dann die Oberfläche des WPF-Fensters. Da alle Resultate aus den Worker-Threads im entsprechenden Thread-Kontext eintrudeln, müssen diese mittels BeginInvoke am Dispatcher-Objekt in den Primärthread der Anwendung eingeschleust werden:

001: using System;
002: ...
003: 
004: using System.Threading.Tasks;
005: using System.Collections;
006: using System.Collections.Generic;
007: 
008: namespace WpfMultiThreadingPrimeNumbers
009: {
010:     public delegate void UpdateUIHandler (int tid, long found);
011: 
012:     public delegate void UpdateUICompletedHandler (
013:         long minimum, long maximum, long total, long msecs, int numThreads);
014: 
015:     public struct CalculatorData
016:     {
017:         public CalculatorData(int min, int max, int num)
018:         {
019:             this.minimum = min;
020:             this.maximum = max;
021:             this.numberOfThreads = num;
022:         }
023: 
024:         public int minimum;
025:         public int maximum;
026:         public int numberOfThreads;
027:     }
028: 
029:     public partial class MainWindow : Window
030:     {
031:         private Thread t;
032:         private List<int> workerThreadsID;
033: 
034:         private long total;
035: 
036:         public MainWindow ()
037:         {
038:             this.InitializeComponent();
039: 
040:             for (int i = 0; i < 6; i ++)
041:                 this.ComboBoxNumberThreads.Items.Add((int) Math.Pow (2, i));
042:             this.ComboBoxNumberThreads.SelectedIndex = 0;
043: 
044:             // enable UI
045:             this.t = null;
046: 
047:             this.workerThreadsID = new List<int>();
048:         }
049: 
050:         private void ComboBoxNumberThreads_SelectionChanged
051:             (Object sender, SelectionChangedEventArgs e)
052:         {
053:             this.StackPanelResults.Children.Clear();
054:         }
055: 
056:         private void Button_Click (Object sender, RoutedEventArgs e)
057:         {
058:             // current prime numbers search active
059:             if (this.t != null)
060:                 return;
061: 
062:             // clear UI
063:             this.TextBoxStatus.Text = "";
064:             this.StackPanelResults.Children.Clear();
065: 
066:             int numberOfThreads = (int) this.ComboBoxNumberThreads.SelectedValue;
067: 
068:             String from = this.TextBoxFrom.Text;
069:             String to = this.TextBoxTo.Text;
070:             int minimum = Int32.Parse(from);
071:             int maximum = Int32.Parse(to);
072: 
073:             CalculatorData data =
074:                 new CalculatorData(minimum, maximum, numberOfThreads);
075: 
076:             ParameterizedThreadStart handler =
077:                 new ParameterizedThreadStart(this.ComputePrimes);
078: 
079:             this.t = new Thread(handler);
080:             this.t.Start(data);
081:         }
082: 
083:         private void ComputePrimes(Object o)
084:         {
085:             CalculatorData data = (CalculatorData) o;
086: 
087:             int numberOfThreads = data.numberOfThreads;
088:             Thread[] workers = new Thread [numberOfThreads];
089: 
090:             this.workerThreadsID.Clear();
091: 
092:             PrimeNumberCalculator calc = new PrimeNumberCalculator();
093:             calc.Minimum = data.minimum;
094:             calc.Maximum = data.maximum;
095:             calc.PrimeNumbersFound +=
096:                 new PrimeNumbersFoundHandler(this.Calculator_PrimeNumbersFound);
097: 
098:             Stopwatch sw = new Stopwatch();
099:             sw.Start();
100: 
101:             this.total = 0;
102:             for (int i = 0; i < numberOfThreads; i++)
103:             {
104:                 ThreadStart ts = new ThreadStart(calc.CalcPrimes);
105:                 workers[i] = new Thread(ts);
106: 
107:                 this.workerThreadsID.Add (workers[i].ManagedThreadId);
108:                 workers[i].Start();
109:             }
110: 
111:             for (int i = 0; i < numberOfThreads; i++)
112:                 workers[i].Join();
113: 
114:             sw.Stop();
115: 
116:             // update UI
117:             if (! this.Dispatcher.CheckAccess())
118:             {
119:                 UpdateUICompletedHandler handler =
120:                     new UpdateUICompletedHandler(this.UpdateUICompleted);
121: 
122:                 this.Dispatcher.BeginInvoke(
123:                     handler, data.minimum, data.maximum, this.total,
124:                     sw.ElapsedMilliseconds, numberOfThreads);
125:             }
126: 
127:             // enable UI
128:             this.t = null;
129:         }
130: 
131:         private void Calculator_PrimeNumbersFound(int tid, long found)
132:         {
133:             // update total count
134:             Monitor.Enter(this);
135:             {
136:                 this.total += found;
137:             }
138:             Monitor.Exit(this);
139: 
140:             // update UI
141:             if (! this.Dispatcher.CheckAccess())
142:             {
143:                 UpdateUIHandler handler = new UpdateUIHandler(this.UpdateUI);
144:                 this.Dispatcher.BeginInvoke (handler, tid, found);
145:             }
146:         }
147: 
148:         private void UpdateUI(int tid, long found)
149:         {
150:             TextBox tb = new TextBox();
151:             tb.Text = String.Format("[TID: {0}] Found {1}", tid, found);
152:             this.StackPanelResults.Children.Add(tb);
153:         }
154: 
155:         private void UpdateUICompleted(long minimum, long maximum,
156:             long total, long msecs, int numThreads)
157:         {
158:             this.TextBoxStatus.Text =
159:                 String.Format("[{0} - {1}]  Prime numbers found: " +
160:                 "{2}  [{3} msecs / {4} threads]",
161:                 minimum, maximum, total, msecs, numThreads);
162:         }
163:     }
164: }

Beispiel 2. Code-Behind-Anweisungen für das Hauptfenster.


Über das PrimeNumberCalculator-Objekt ist bereits alles gesagt worden. Die Spezifikation können Sie in Tabelle 1 entnehmen, eine mögliche Realisierung finden Sie Listing 3 vor:

001: using System;
002: ...
003: 
004: using System.Threading.Tasks;
005: 
006: namespace WpfMultiThreadingPrimeNumbers
007: {
008:     public delegate void PrimeNumbersFoundHandler (int tid, long found);
009: 
010:     public class PrimeNumberCalculator
011:     {
012:         private long minimum;
013:         private long maximum;
014:         private long next;
015: 
016:         public PrimeNumberCalculator()
017:         {
018:             this.minimum = 2;
019:             this.maximum = 1000;
020:             this.next = this.minimum;
021:         }
022: 
023:         public event PrimeNumbersFoundHandler PrimeNumbersFound;
024: 
025:         // properties
026:         public long Minimum
027:         {
028:             get { return this.minimum; }
029:             set { this.minimum = value; this.next = value; }
030:         }
031: 
032:         public long Maximum
033:         {
034:             get { return this.maximum; }
035:             set { this.maximum = value; }
036:         }
037: 
038:         // public interface
039:         public void CalcPrimes ()
040:         {
041:             long max;
042:             long next;
043: 
044:             int local = 0;
045: 
046:             Monitor.Enter(this);
047:             {
048:                 // retrieve upper prime number limit
049:                 max = this.maximum;
050: 
051:                 // retrieve next prime number candidate
052:                 next = this.next;
053: 
054:                 // increment current prime number candidate
055:                 // for next available client
056:                 this.next++;
057:             }
058:             Monitor.Exit(this);
059: 
060:             while (next < max)
061:             {
062:                 if (PrimeNumberCalculator.IsPrime(next))
063:                 {
064:                     // increment thread specific prime number counter
065:                     local++;
066:                 }
067: 
068:                 Monitor.Enter(this);
069:                 {
070:                     // retrieve next prime number candidate
071:                     next = this.next;
072: 
073:                     // adjust current prime number candidate
074:                     // for next available client
075:                     this.next++;
076: 
077:                     // skip even numbers
078:                     if (this.next % 2 == 0)
079:                         this.next++;
080:                 }
081:                 Monitor.Exit(this);
082:             }
083: 
084:             // calculation done, fire event with results
085:             if (this.PrimeNumbersFound != null)
086:             {
087:                 int tid = Thread.CurrentThread.ManagedThreadId;
088:                 this.PrimeNumbersFound.Invoke(tid, local);
089:             }
090:         }
091: 
092:         public static bool IsPrime(long number)
093:         {
094:             // the smallest prime number is 2
095:             if (number <= 2)
096:                 return number == 2;
097: 
098:             // even numbers other than 2 are not prime
099:             if (number % 2 == 0)
100:                 return false;
101: 
102:             // check odd divisors from 3 to the square root of the number
103:             long end = (long) Math.Sqrt(number);
104:             for (long i = 3; i <= end; i += 2)
105:                 if (number % i == 0)
106:                     return false;
107: 
108:             // found prime number
109:             return true;
110:         }
111:     }
112: }

Beispiel 3. Klasse PrimeNumberCalculator.


Das Aufteilen der Primzahlenberechnungen auf mehrere Threads können Sie auch an die TPL (Task Parallel Library) delegieren. Diese besitzt intime Kenntnisse Ihres Rechners und entscheidet an Hand eines Thread-Pools, dessen Größe genau auf die Hardware-Ausstattung des Rechners zugeschnitten ist, wieviele Threads er für die Primzahlenberechnung abstellt.

In einem zweiten Schritt haben wir deshalb das Hauptfenster der Anwendung um eine zusätzliche Schaltfläche mit der Beschriftung „Compute using TPL“ erweitert, siehe Abbildung 3:

Erweitertes Hauptfenster der WPF-Anwendung.

Abbildung 3. Erweitertes Hauptfenster der WPF-Anwendung.


Im XAML-Anteil des Fensters sieht die Schaltfläche so aus – wir führen diese Kleinigkeit nur auf Grund des Name-Attributs der Schaltfläche auf:

<Button
    Name="ButtonUsingTPL" Click="Button_Click" Margin="3"
    DockPanel.Dock="Top">Compute using TPL</Button>

Das Umsetzen einer verteilten Primzahlensuche mit Hilfe der TPL und Lambda-Ausdrücken sieht im ersten Augenblick etwas kryptisch aus. Es handelt sich um eine Optimierung des Parallel.For-Konstrukts mit thread-lokalen Variablen. Das Einbringen dieser Variante erfordert nur eine zusätzliche Methode ComputePrimesTPL, die Sie in Listing 4 vorfinden:

01: public partial class MainWindow : Window
02: {
03:     private Thread t;
04:     private List<int> workerThreadsID;
05: 
06:     private long total;
07: 
08:     private void Button_Click (Object sender, RoutedEventArgs e)
09:     {
10:         ...
11: 
12:         ParameterizedThreadStart handler =
13:             (sender == this.ButtonUsingThreads) ?
14:             new ParameterizedThreadStart(this.ComputePrimes) :
15:             new ParameterizedThreadStart(this.ComputePrimesTPL);
16: 
17:         this.t = new Thread(handler);
18:         this.t.Start(data);
19:     }
20: 
21:     public void ComputePrimesTPL (Object o)
22:     {
23:         CalculatorData data = (CalculatorData) o;
24:         int numberOfThreads = data.numberOfThreads;
25:         long minimum = data.minimum;
26:         long maximum = data.maximum;
27: 
28:         Stopwatch sw = new Stopwatch();
29:         sw.Start();
30: 
31:         this.workerThreadsID.Clear();
32: 
33:         this.total = 0;
34:         Parallel.For(
35:             minimum,  // start index (inclusive)
36:             maximum,  // end index (exclusive)
37:             //
38:             // initialization of local value
39:             () => (long) 0,
40:             //
41:             // worker function (scheduled in a single thread)
42:             (i, state, localTotal) =>
43:             {
44:                 if (PrimeNumberCalculator.IsPrime(i))
45:                 {
46:                     localTotal++;
47:                 }
48: 
49:                 return localTotal;
50:             },
51:             //
52:             // add local value to the master value (thread safe)
53:             localTotal =>
54:             {
55:                 int tid = Thread.CurrentThread.ManagedThreadId;
56: 
57:                 // counting threads being incorporated into the search
58:                 Monitor.Enter(this);
59:                 if (!this.workerThreadsID.Contains(tid))
60:                     this.workerThreadsID.Add(tid);
61:                 Monitor.Exit(this);
62: 
63:                 Interlocked.Add(ref this.total, localTotal);
64: 
65:                 // update UI
66:                 if (!this.Dispatcher.CheckAccess())
67:                 {
68:                     UpdateUIHandler handler =
69:                         new UpdateUIHandler(this.UpdateUI);
70: 
71:                     this.Dispatcher.BeginInvoke(handler, tid, localTotal);
72:                 }
73:             }
74:         );
75: 
76:         // update UI
77:         if (!this.Dispatcher.CheckAccess())
78:         {
79:             UpdateUICompletedHandler handler =
80:                 new UpdateUICompletedHandler(this.UpdateUICompleted);
81: 
82:             this.Dispatcher.BeginInvoke(
83:                 handler, data.minimum, data.maximum, this.total,
84:                 sw.ElapsedMilliseconds, this.workerThreadsID.Count);
85:         }
86: 
87:         // enable UI
88:         this.t = null;
89:     }
90:     ...
91: }

Beispiel 4. Erweiterung der Code-Behind-Anweisungen: Einbeziehung der TPL.


Das Beispiel in Abbildung 4 zeigt die parallele Bestimmung von Primzahlen mit der generischen Variante von Parallel.For. Der Typ long ist der Typ der thread-lokalen Daten, siehe Zeile 39. Das nächste Argument ist eine Funktion, die die eigentliche Arbeit verrichtet. Sie bekommt von der Parallel.For-Implementierung eine thread-lokale Variable übergeben, in der sie die jeweilige Teilsumme gefundener Primzahlen speichert und für den nächsten Teilschritt auch wieder zurückliefert. Eine Synchronisation ist nicht erforderlich, da per Definition nur ein Thread die Variable verwendet. Das letzte Argument umfasst den Aggregationsschritt, den am Schluss jeder beteiligte Thread ausführt. Erst hier wird durch Einsatz einer Sperre die Gesamtsumme gebildet. Da das aber nur einmal pro Thread und nicht einmal pro ausgeführtem Teilabschnitt passiert, ist der Aufwand für die Synchronisation vernachlässigbar.

Vergleichen Sie beide Varianten auf Ihrem Rechner. Bei welcher Variante können Sie einen zeitlichen Vorsprung beobachten?

Die vorgestellte Lösung besitzt als Schwerpunkt die Betrachtung des parallelen Ansatzes zur Berechnung von Primzahlen. Als weiniger gelungen könnte man die fehlende Strukturierung in Logik-Anteile (Primzahlenberechnung) und Visualisierung (Darstellung der Ergebnisse) beurteilen. Wir stellen nachfolgend deshalb eine zweite Lösung vor, die vor allem in Bezug auf die Strukturierung der Oberfläche erheblich verbessert wurde. Im Detail betrachtet besteht sie aus einer Logik-Klasse, zwei Steuerelementen (WPF-User Controls) und einem WPF-Hauptfenster, siehe dazu den folgenden tabellarischen Überblick:

  • Klasse PrimeNumberCalculatorEx – Logik-Klasse zur Berechnung von Primzahlen, entweder mit einer einstellbaren Anzahl von Thread-Objekten oder aber mit Hilfe der Task Parallel Library. Resultate (Zwischenergebnisse und Endresultat) werden über Ereignisse gemeldet.

  • Steuerelement PrimeNumbersToolbarControl – Mit diesem WPF-User Control lassen sich alle relevanten Parameter (unterer und oberer Grenzwert, Anzahl der Threads) für die Berechnung von Primzahlen eingeben.

    Bemerkung: Die Spezifikation der Anzahl der Threads ergibt nur dann Sinn, wenn explizit Thread-Objekte bei der Primzahlenberechnung beteiligt sind. Die Task Parallel Library trifft ihre Entscheidung selbständig, wieviele Threads sie aus dem System-Threadpool an der Suche involvieren möchte.

  • Steuerelement PrimeNumbersDisplayControl – WPF-User Control zur Anzeige des Berechnungsergebnisses wie etwa die gefundene Anzahl der Primzahlen, die Berechnungszeit als auch die Anzahl der in die Berechnung involvierten Threads.

  • Fensterklasse MainWindow – Container für das Logik-Objekt und die grafischen Steuerelemente. Im Hauptfenster findet die Verschaltung der beteiligten Objekte auf Basis von Ereignissen statt.

Bevor wir auf die einzelnen Komponenten der Anwendung im Einzelnen eingehen, beachten Sie bitte die Flexibilität des nunmehr gewählten Lösungsansatzes: Um gefundene Primzahlenergebnisse in einem PrimeNumbersDisplayControl-Steuerelement zur Anzeige zu bringen, werden diese beispielsweise diesem Steuerelement durch Aufruf einer Methode ausgehändigt (hier: Methode AddFoundPrimeNumbersResult). Internas des Steuerelements bleiben auf diese Weise vor dem Benutzer verborgen. Es ist so möglich, unterschiedliche Anzeige-Steuerelemente zu realisieren, etwa welche mit anspruchsvollerer Grafik, also erhöhtem Entwicklungsaufwand oder welche mit einfacherer Grafik und dadurch geringem Aufwand in der Realisierung. Interagieren diese Steuerelemente nur über (konzeptionell festzulegende) Methoden, Ereignisse und Eigenschaften, so können diese im Hauptfenster der Anwendung einfach via Plug and Play ausgetauscht werden.

Betrachten Sie vor diesen Überlegungen nunmehr das folgende Konglomerat an Steuerelementen (XAML- und Codebehind), Logik-Klasse und Hauptfenster. Vor den einzelnen Realisierungen geben wir noch einmal einen Überblick aller beteiligten Dateien:

  • Logik-Klasse des Primzahlenkalkulators – Datei PrimeNumberCalculatorEx.cs.

  • Steuerelement PrimeNumbersToolbarControl:

    • XAML-Direktiven – Datei PrimeNumbersToolbarControl.xaml.

    • Codebehind-Anweisungen – Datei PrimeNumbersToolbarControl.xaml.cs

  • Steuerelement PrimeNumbersDisplayControl:

    • XAML-Direktiven – Datei PrimeNumbersDisplayControl.xaml.

    • Codebehind-Anweisungen – Datei PrimeNumbersDisplayControl.xaml.cs

  • Hauptfenster MainWindow:

    • XAML-Direktiven – Datei MainWindow.xaml.

    • Codebehind-Anweisungen – Datei MainWindow.xaml.cs

Nach dieser Zusammenfassung sollte es möglich sein, einen Überblick in dem nunmehr folgenden Ansammlung von C#- und XAML-Dateien zu behalten:

001: using System;
002: using System.Collections.Generic;
003: using System.Diagnostics;
004: using System.Threading;
005: using System.Threading.Tasks;
006: 
007: namespace WpfMultiThreadingPrimeNumbers
008: {
009:     public delegate void PrimeNumbersFoundHandler (int tid, long found);
010:     public delegate void PrimeNumbersCalculationDoneHandler (long total, long msecs);
011: 
012:     public class PrimeNumberCalculatorEx
013:     {
014:         private long minimum;
015:         private long maximum;
016:         private long next;
017: 
018:         private int numberThreads;
019:         private long total;
020: 
021:         // threading utils
022:         private Task task;              // helper task to prevent UI freezing
023:         private List<Thread> workers;
024:         private List<int> workerThreadsID;
025: 
026:         // events
027:         public event PrimeNumbersFoundHandler PrimeNumbersFound;
028:         public event PrimeNumbersCalculationDoneHandler PrimeNumbersCalculationDone;
029: 
030:         public PrimeNumberCalculatorEx ()
031:         {
032:             this.minimum = 2;
033:             this.maximum = 1000;
034:             this.next = this.minimum;
035: 
036:             this.total = 0;
037: 
038:             this.workers = new List<Thread>();
039:             this.workerThreadsID = new List<int>();
040:         }
041: 
042:         // properties
043:         public long Minimum
044:         {
045:             get { return this.minimum; }
046:             set { this.minimum = value; this.next = value; }
047:         }
048: 
049:         public long Maximum
050:         {
051:             get { return this.maximum; }
052:             set { this.maximum = value; }
053:         }
054: 
055:         public int NumberThreads
056:         {
057:             get { return this.numberThreads; }
058:             set { this.numberThreads = value; }
059:         }
060: 
061:         // public interface
062:         public bool ComputePrimesAsync()
063:         {
064:             if (this.task != null)
065:                 return false;
066: 
067:             this.task = Task.Factory.StartNew (
068:             () =>
069:                 {
070:                     this.ComputePrimes();
071:                 }
072:             );
073: 
074:             return true;
075:         }
076: 
077:         public bool ComputePrimesTPLAsync()
078:         {
079:             if (this.task != null)
080:                 return false;
081: 
082:             this.task = Task.Factory.StartNew(
083:             () =>
084:                 {
085:                     this.ComputePrimesTPL();
086:                 }
087:             );
088: 
089:             return true;
090:         }
091: 
092:         // private helper methods
093:         private void ComputePrimes()
094:         {
095:             this.total = 0;
096: 
097:             this.workers.Clear();
098:             this.workerThreadsID.Clear();
099: 
100:             Stopwatch sw = new Stopwatch();
101:             sw.Start();
102: 
103:             this.total = 0;
104:             for (int i = 0; i < this.numberThreads; i++)
105:             {
106:                 Thread t = new Thread(this.CalcPrimesWorker);
107:                 this.workers.Add (t);
108:                 this.workerThreadsID.Add(t.ManagedThreadId);
109:                 t.Start();
110:             }
111: 
112:             for (int i = 0; i < this.workers.Count; i++)
113:                 workers[i].Join();
114: 
115:             sw.Stop();
116: 
117:             // calculation done, fire event with results
118:             if (this.PrimeNumbersCalculationDone != null)
119:                 this.PrimeNumbersCalculationDone.Invoke (
120:                     this.total, sw.ElapsedMilliseconds);
121: 
122:             // reset guard
123:             this.task = null;
124:         }
125: 
126:         public void ComputePrimesTPL()
127:         {
128:             Stopwatch sw = new Stopwatch();
129:             sw.Start();
130: 
131:             this.workerThreadsID.Clear();
132: 
133:             this.total = 0;
134:             Parallel.For(
135:                 this.minimum,  // start index (inclusive)
136:                 this.maximum,  // end index (exclusive)
137:                 //
138:                 // initialization of local value
139:                 () => (long) 0,
140:                 //
141:                 // worker function (scheduled in a single thread)
142:                 (i, state, localTotal) =>
143:                 {
144:                     if (PrimeNumberCalculatorEx.IsPrime(i))
145:                     {
146:                         localTotal++;
147:                     }
148: 
149:                     return localTotal;
150:                 },
151:                 //
152:                 // add local value to the master value (thread safe)
153:                 localTotal =>
154:                 {
155:                     int tid = Thread.CurrentThread.ManagedThreadId;
156: 
157:                     // counting threads being incorporated into the search
158:                     Monitor.Enter(this);
159:                     if (! this.workerThreadsID.Contains(tid))
160:                         this.workerThreadsID.Add(tid);
161:                     Monitor.Exit(this);
162: 
163:                     Interlocked.Add(ref this.total, localTotal);
164: 
165:                     // calculation done, fire event with results
166:                     if (this.PrimeNumbersFound != null)
167:                     {
168:                         this.PrimeNumbersFound.Invoke(tid, localTotal);
169:                     }
170:                 }
171:             );
172: 
173:             sw.Stop();
174: 
175:             // calculation done, fire event with results
176:             if (this.PrimeNumbersCalculationDone != null)
177:                 this.PrimeNumbersCalculationDone.Invoke (
178:                     this.total, sw.ElapsedMilliseconds);
179: 
180:             // reset guard
181:             this.task = null;
182:         }
183: 
184:         private void CalcPrimesWorker ()
185:         {
186:             long max;
187:             long next;
188: 
189:             int local = 0;
190: 
191:             Monitor.Enter(this);
192:             {
193:                 // retrieve upper prime number limit
194:                 max = this.maximum;
195: 
196:                 // retrieve next prime number candidate
197:                 next = this.next;
198: 
199:                 // increment current prime number candidate
200:                 // for next available client
201:                 this.next++;
202:             }
203:             Monitor.Exit(this);
204: 
205:             while (next < max)
206:             {
207:                 if (PrimeNumberCalculatorEx.IsPrime(next))
208:                 {
209:                     // increment thread specific prime number counter
210:                     local++;
211:                 }
212: 
213:                 Monitor.Enter(this);
214:                 {
215:                     // retrieve next prime number candidate
216:                     next = this.next;
217: 
218:                     // adjust current prime number candidate
219:                     // for next available client
220:                     this.next++;
221: 
222:                     // skip even numbers
223:                     if (this.next % 2 == 0)
224:                         this.next++;
225:                 }
226:                 Monitor.Exit(this);
227:             }
228: 
229:             // update total count
230:             Monitor.Enter(this);
231:             {
232:                 this.total += local;
233:             }
234:             Monitor.Exit(this);
235: 
236:             // calculation done, fire event with results
237:             if (this.PrimeNumbersFound != null)
238:             {
239:                 int tid = Thread.CurrentThread.ManagedThreadId;
240:                 this.PrimeNumbersFound.Invoke(tid, local);
241:             }
242:         }
243: 
244:         public static bool IsPrime(long number)
245:         {
246:             // the smallest prime number is 2
247:             if (number <= 2)
248:                 return number == 2;
249: 
250:             // even numbers other than 2 are not prime
251:             if (number % 2 == 0)
252:                 return false;
253: 
254:             // check odd divisors from 3 to the square root of the number
255:             long end = (long) Math.Sqrt(number);
256:             for (long i = 3; i <= end; i += 2)
257:                 if (number % i == 0)
258:                     return false;
259: 
260:             // found prime number
261:             return true;
262:         }
263:     }
264: }

Beispiel 5. Redesign der Logik-Klasse des Primzahlenkalkulators.


01: <UserControl
02:     x:Class="WpfMultiThreadingPrimeNumbers.PrimeNumbersToolbarControl"
03:     xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
04:     xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
05:     xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006" 
06:     xmlns:d="http://schemas.microsoft.com/expression/blend/2008" 
07:     mc:Ignorable="d" d:DesignWidth="600">
08:     <GroupBox Header="Prime Numbers Toolbar">
09:         <StackPanel Orientation="Vertical">
10:             <Button
11:                 Name="ButtonUsingThreads" x:FieldModifier="private"
12:                 Click="Button_Click" DockPanel.Dock="Top"
13:                 Content="Compute using Threads" Margin="3" />
14: 
15:             <UniformGrid Margin="3"  DockPanel.Dock="Top"  Rows="1" Columns="3">
16:                 <DockPanel>
17:                     <Label Width="50" >From:</Label>
18:                     <TextBox
19:                         Name="TextBoxFrom" x:FieldModifier="private"
20:                         VerticalAlignment="Center" Text="2"/>
21:                 </DockPanel>
22:                 <DockPanel>
23:                     <Label Width="50">To:</Label>
24:                     <TextBox
25:                         Name="TextBoxTo" x:FieldModifier="private"
26:                         VerticalAlignment="Center" Text="1000000"/>
27:                 </DockPanel>
28:                 <DockPanel>
29:                     <Label Width="70">Threads:</Label>
30:                     <ComboBox
31:                         Name="ComboBoxNumberThreads" x:FieldModifier="private"
32:                         DockPanel.Dock="Top" Margin="3,3,0,3"
33:                         SelectionChanged="ComboBoxNumberThreads_SelectionChanged">
34:                     </ComboBox>
35:                 </DockPanel>
36:             </UniformGrid>
37: 
38:             <Button
39:                 Name="ButtonUsingTPL" x:FieldModifier="private"
40:                 Click="Button_Click" Margin="3"
41:                 DockPanel.Dock="Top" Content="Compute using TPL"/>
42:         </StackPanel>
43:     </GroupBox>
44: </UserControl>

Beispiel 6. Steuerelement PrimeNumbersToolbarControl: XAML


01: using System;
02: using System.Windows;
03: using System.Windows.Controls;
04: 
05: namespace WpfMultiThreadingPrimeNumbers
06: {
07:     public enum ToolbarActions { StartUsingThreads, StartUsingTPL };
08: 
09:     public delegate void ToolbarActionsEventHandler (ToolbarActions action);
10: 
11:     public partial class PrimeNumbersToolbarControl : UserControl
12:     {
13:         private int numberThreads;
14: 
15:         // c'tor
16:         public PrimeNumbersToolbarControl()
17:         {
18:             this.InitializeComponent();
19: 
20:             for (int i = 0; i < 6; i++)
21:                 this.ComboBoxNumberThreads.Items.Add((int)Math.Pow(2, i));
22:             this.ComboBoxNumberThreads.SelectedIndex = 0;
23:         }
24: 
25:         // events
26:         public event ToolbarActionsEventHandler Action;
27: 
28:         // properties
29:         public int Minimum
30:         {
31:             get
32:             {
33:                 int number;
34:                 bool res = Int32.TryParse(this.TextBoxFrom.Text, out number);
35:                 if (!res)
36:                 {
37:                     MessageBox.Show("Wrong input: Please enter number!", "ERROR");
38:                     number = 2;
39:                 }
40: 
41:                 return number;
42:             }
43:         }
44: 
45:         public int Maximum
46:         {
47:             get
48:             {
49:                 int number;
50:                 bool res = Int32.TryParse(this.TextBoxTo.Text, out number);
51:                 if (!res)
52:                 {
53:                     MessageBox.Show("Wrong input: Please enter number!", "ERROR");
54:                     number = 100;
55:                 }
56: 
57:                 return number;
58:             }
59:         }
60: 
61:         public int NumberThreads
62:         {
63:             get
64:             {
65:                 return this.numberThreads;
66:             }
67:         }
68: 
69:         private void ComboBoxNumberThreads_SelectionChanged
70:             (Object sender, SelectionChangedEventArgs e)
71:         {
72:             this.numberThreads =
73:                 (int) this.ComboBoxNumberThreads.SelectedValue;
74:         }
75: 
76:         private void Button_Click (Object sender, RoutedEventArgs e)
77:         {
78:             if (this.Action != null)
79:             {
80:                 if (sender == this.ButtonUsingThreads)
81:                 {
82:                     this.Action.Invoke (ToolbarActions.StartUsingThreads);
83:                 }
84:                 else if (sender == this.ButtonUsingTPL)
85:                 {
86:                     this.Action.Invoke (ToolbarActions.StartUsingTPL);
87:                 }
88:             }
89:         }
90:     }
91: }

Beispiel 7. Steuerelement PrimeNumbersToolbarControl: Codebehind


01: <UserControl x:Class="WpfMultiThreadingPrimeNumbers.PrimeNumbersDisplayControl"
02:              xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
03:              xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
04:              xmlns:mc="http://schemas.openxmlformats.org/markup-compatibility/2006" 
05:              xmlns:d="http://schemas.microsoft.com/expression/blend/2008" 
06:              mc:Ignorable="d" 
07:              d:DesignHeight="300" d:DesignWidth="300">
08:     <GroupBox Header="Prime Numbers Display">
09:         <DockPanel>
10:             <ScrollViewer
11:                 DockPanel.Dock="Top"
12:                 VerticalScrollBarVisibility="Auto">
13:                 <StackPanel
14:                     Name="StackPanelResults"
15:                     x:FieldModifier="private"
16:                     Orientation="Vertical"/>
17:             </ScrollViewer>
18:         </DockPanel>
19:     </GroupBox>
20: </UserControl>

Beispiel 8. Steuerelement PrimeNumbersDisplayControl: XAML


01: using System;
02: using System.Windows.Controls;
03: 
04: namespace WpfMultiThreadingPrimeNumbers
05: {
06:     public partial class PrimeNumbersDisplayControl : UserControl
07:     {
08:         public PrimeNumbersDisplayControl()
09:         {
10:             this.InitializeComponent();
11:         }
12: 
13:         public void Clear()
14:         {
15:             this.StackPanelResults.Children.Clear();
16:         }
17: 
18:         public void AddFoundPrimeNumbersResult(int tid, long found)
19:         {
20:             // update UI - check for correct thread affinity
21:             if (this.Dispatcher.CheckAccess())
22:             {
23:                 TextBox tb = new TextBox();
24:                 tb.Text = String.Format("[TID: {0}] Found {1}", tid, found);
25:                 this.StackPanelResults.Children.Add(tb);
26:             }
27:             else
28:             {
29:                 this.Dispatcher.BeginInvoke (
30:                     (Action)(() =>
31:                     {
32:                         this.AddFoundPrimeNumbersResult (tid, found);
33:                     })
34:                 );
35:             }
36:         }
37:     }
38: }

Beispiel 9. Steuerelement PrimeNumbersDisplayControl: Codebehind


01: <Window x:Class="WpfMultiThreadingPrimeNumbers.MainWindow"
02:         xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
03:         xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
04:         xmlns:local="clr-namespace:WpfMultiThreadingPrimeNumbers"
05:         Title="Prime Numbers Calculator" Width="600" Height="300">
06:     <DockPanel LastChildFill="True">
07:         <local:PrimeNumbersToolbarControl DockPanel.Dock="Top"
08:             x:Name="PrimeNumbersToolbar" x:FieldModifier="private"/>
09:         <TextBox
10:             Name="TextBoxStatus" x:FieldModifier="private"
11:             IsEnabled="False" Margin="3"
12:             DockPanel.Dock="Bottom" Text="Status"/>
13:         <local:PrimeNumbersDisplayControl
14:             x:Name="PrimeNumbersDisplay" x:FieldModifier="private"/>
15:     </DockPanel>
16: </Window>

Beispiel 10. Hauptfenster MainWindow: XAML


01: using System;
02: using System.Windows;
03: 
04: namespace WpfMultiThreadingPrimeNumbers
05: {
06:     public partial class MainWindow : Window
07:     {
08:         private PrimeNumberCalculatorEx calculator;
09: 
10:         public MainWindow()
11:         {
12:             this.InitializeComponent();
13: 
14:             // create a prime calculator object
15:             this.calculator = new PrimeNumberCalculatorEx();
16: 
17:             // connect application (main window) with calculator
18:             this.calculator.PrimeNumbersFound +=
19:                 new PrimeNumbersFoundHandler (
20:                     this.Calculator_PrimeNumbersFound);
21:             this.calculator.PrimeNumbersCalculationDone +=
22:                 new PrimeNumbersCalculationDoneHandler (
23:                     this.Calculator_PrimeNumbersCalculationDone);
24: 
25:             // connect application (main window) with toolbar
26:             this.PrimeNumbersToolbar.Action +=
27:                 new ToolbarActionsEventHandler (
28:                     this.PrimeNumbersToolbar_Action);
29:         }
30: 
31:         private void PrimeNumbersToolbar_Action (ToolbarActions action)
32:         {
33:             this.calculator.Minimum = this.PrimeNumbersToolbar.Minimum;
34:             this.calculator.Maximum = this.PrimeNumbersToolbar.Maximum;
35:             this.calculator.NumberThreads = this.PrimeNumbersToolbar.NumberThreads;
36: 
37:             this.PrimeNumbersDisplay.Clear();
38:             this.TextBoxStatus.Text = "";
39: 
40:             if (action == ToolbarActions.StartUsingThreads)
41:             {
42:                 this.calculator.ComputePrimesAsync();
43:             }
44:             else
45:             {
46:                 this.calculator.ComputePrimesTPLAsync();
47:             }
48:         }
49: 
50:         private void Calculator_PrimeNumbersCalculationDone(long total, long msecs)
51:         {
52:             this.Dispatcher.BeginInvoke (
53:                 (Action) (() =>
54:                 {
55:                     this.TextBoxStatus.Text =
56:                         String.Format("[{0} - {1}]  Prime numbers found: " +
57:                         "{2}  [{3} msecs / {4} threads]",
58:                         this.calculator.Minimum, this.calculator.Maximum,
59:                         total, msecs, this.calculator.NumberThreads);
60:                 })
61:             );
62:         }
63: 
64:         private void Calculator_PrimeNumbersFound(int tid, long found)
65:         {
66:             this.PrimeNumbersDisplay.AddFoundPrimeNumbersResult(tid, found);
67:         }
68:     }
69: }

Beispiel 11. Hauptfenster MainWindow: Codebehind