C# Monte-Carlo Algorithmus für PI Berechnung inkl. Visualisierung, Threading Problem

[Timmey92]

Moin!

Habe mich aus Mathematischem Interesse dazu entschlossen mal einen Monte-Carlo Algorithmus zu programmieren um eine Annäherung an PI zu berechnen.
Leider laste ich nur 25% meiner CPU aus derzeit (QuadCore) und möchte für eine schnellere ausführungsgeschwindigkeit Threading einführen. Habe damit aber bisher noch nicht gearbeitet (bzw. nur kleinere Sachen mal ausgelagert, kaum Erfahrung wie man das praktisch einsetzt).

Momentan nutze ich einen Thread Pool und füge da ganz viele kleine Threads zu (für jeden einzelnen Punkt ein Thread, bzw. eine Aufgabe in der ThreadPool Queue). Da friert mir bei längeren Berechnungen mit Millionen Punkten der UI-Thread ein.

Vielleicht habt ihr ja Lösungs/Verbesserungsvorschläge?

Freue mich über eure Hilfe!

Projektmappe gibts hier (VS 2010 Ultimate):
http://filebeam.com/ab953eb4740c1d7984cee5ac699d442c

Hier der Code:

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Collections;
using System.Threading;

namespace Monte_Carlo_Visualisierung
{
    public partial class Form1 : Form
    {
        List<Point> pointList = new List<Point>();
        bool running = false;

        Random Rand = new Random(); //Zufallsgenerator

        Bitmap picture = new Bitmap(500, 500);
        Graphics g;
        Pen bigPen = new Pen(Color.Black, 4); //Farbe + Stärke
        Pen smallPen = new Pen(Color.Black, 2);
        Pen pointPenIn = new Pen(Color.Red, 1);
        Pen pointPenOut = new Pen(Color.Blue, 1);
        Size small = new Size(1, 1);

        int maxPoints = 10; //Wieviele Punkte dürfen höchstens geworfen werden
        int currentPoints = 0; //Alle gezeichneten Punkte
        int hitPoints = 0; //Punkte im Kreis
        int failPoints = 0; //Punkte außerhalb des Kreises

        int sleepTime = 0;
        
        /*
        Ultraschnell (0ms)
        Wie im Fluge (1ms)
        Sehr schnell (50ms)
        Schnell (100ms)
        Normal (250ms)
        Langsam (500ms)
        Sehr Langsam (1000ms)
        Slow Motion (3 Sekunden)
         */

        public Form1()
        {
            InitializeComponent();
            g = Graphics.FromImage(picture);
            DrawBasis();
            comboBox1.SelectedItem = comboBox1.Items[0];
        }

       
        //Box und den Kreis zeichnen, einfärben
        private void DrawBasis()
        {
            picture = new Bitmap(500, 500);
            g = Graphics.FromImage(picture);

            picture.MakeTransparent();

            //Box zeichnen          

            Rectangle box = new Rectangle(0, 0, 500, 500);
            SolidBrush brushWhite = new SolidBrush(Color.Gray);
            SolidBrush brushNavy = new SolidBrush(Color.Turquoise);           

            //Box zeichnen und einfärben
            g.DrawRectangle(bigPen, box);
            g.FillRectangle(brushWhite, box);

            //Kreis zeichnen und einfärben
            g.DrawEllipse(smallPen, box);
            g.FillEllipse(brushNavy, box);

            pictureBox1.Image = picture;
            pictureBox1.Refresh();
        }

        private void tbInterval_KeyPress(object sender, KeyPressEventArgs e)
        {
            //akzeptiere nur Zahlen (Zeit ist in Millisekunden)
            if (!Char.IsDigit(e.KeyChar))
                e.Handled = true;
            
        }

        enum waitTime { ultra = 0, wif = 1, sschnell = 50, schnell = 100, normal = 250, langsam = 500, slangsam = 1000, slowmo = 3000 };

        private void btnStart_Click(object sender, EventArgs e)
        {            
            //keine aktiven Worker = Start Button            
            if (running == false)
            {
                running = true;
                //Zurücksetzen auf 0
                DrawBasis();
                maxPoints = Int32.Parse(nupPointNumber.Text);
                pointList.Clear();
                
                //Zähler auf 0
                currentPoints = 0;
                hitPoints = 0;
                failPoints = 0;

                BackgroundWorker bgw = new BackgroundWorker();
                bgw.DoWork += new DoWorkEventHandler(bgw_DoWork);     
                btnStart.Text = "Stop";     

                nupPointNumber.ReadOnly = true;

                bgw.RunWorkerAsync();
               
                
            }
            //aktive Worker = Stop Button
            else
            {                
               // DrawBasis();
                running = false;
                btnStart.Text = "Start";                
                nupPointNumber.ReadOnly = false;                
            }
        }

        void bgw_DoWork(object sender, DoWorkEventArgs e)
        {
            while (currentPoints < maxPoints)
            {
                ThreadPool.QueueUserWorkItem(new WaitCallback(calcPoint));
                currentPoints++; //Zähler der Punkte erhöhen
            }
            running = false;                 
        }



        private void calcPoint(object arguments)
        {    
            

                Thread.Sleep(sleepTime);

                Point p1 = new Point(Rand.Next(500), Rand.Next(500));

                Point m = new Point(250, 250); //mittelpunkt
                //Entfernung von p1 zu m darf nicht mehr als 250 pixel betragen, sonst außerhalb des Kreises                

                float d = (float)Math.Sqrt((p1.X - m.X) * (p1.X - m.X) + (p1.Y - m.Y) * (p1.Y - m.Y));
                if (d < 250)
                    hitPoints++; //Abstand kleienr als 250 -> innerhalb des Kreises, Zähler erhöhen
                else
                    failPoints++; //Abstand größer als 250 -> außerhalb des Kreises, Zähler erhöhen        
                try
                {
                    this.Invoke(new ImageDelegate(drawPoint), p1);
                }
                catch
                {
                    return;
                }
            
           
        }
        public delegate void ImageDelegate(object a);

        private void drawPoint(object a)
        {
            Point p = (Point)a;            
            Rectangle pointRect = new Rectangle(p, small);
            g.DrawRectangle(pointPenIn, pointRect);

            pictureBox1.Refresh();

            textBox1.Text=""+(4 * (double)hitPoints / (double)currentPoints);

            if (currentPoints >= maxPoints) //fertig
            {
                running = false;
                nupPointNumber.ReadOnly = false;
                btnStart.Text = "Start";                
                return;
            }  
        }

        private void comboBox1_SelectedIndexChanged(object sender, EventArgs e)
        {
            switch (comboBox1.SelectedIndex)
            {
                case 0:
                    sleepTime = (int)waitTime.ultra;
                    break;
                case 1:
                    sleepTime = (int)waitTime.wif;
                    break;
                case 2:
                    sleepTime = (int)waitTime.sschnell;
                    break;
                case 3:
                    sleepTime = (int)waitTime.schnell;
                    break;
                case 4:
                    sleepTime = (int)waitTime.normal;
                    break;
                case 5:
                    sleepTime = (int)waitTime.langsam;
                    break;
                case 6:
                    sleepTime = (int)waitTime.slangsam;
                    break;
                case 7:
                    sleepTime = (int)waitTime.slowmo;
                    break;
            }
        }
                  
    }
}

Ergänzung (1. April 2011)

Neuster Code mit Background Workern.
Ich glaube mein Fehler ist einfach das ich den UI Thread zu sehr fordere mit dem Neuzeichnen.

Wo und WIE kann ich noch Sachen aus dem UI Thread auslagern, damit der nicht mehr blockiert?

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Collections;
using System.Threading;

namespace Monte_Carlo_Visualisierung
{
    public partial class Form1 : Form
    {
        List<Point> pointList = new List<Point>();
        bool running = false;

        Random Rand = new Random(); //Zufallsgenerator

        Bitmap picture = new Bitmap(500, 500);
        Graphics g;
        Pen bigPen = new Pen(Color.Black, 4); //Farbe + Stärke
        Pen smallPen = new Pen(Color.Black, 2);
        Pen pointPenIn = new Pen(Color.Red, 1);
        Pen pointPenOut = new Pen(Color.Blue, 1);
        Size small = new Size(1, 1);

        int maxPoints = 10; //Wieviele Punkte dürfen höchstens geworfen werden
        int currentPoints = 0; //Alle in Auftrag gegebenen Punkte
        int drawnPoints = 0; //alle wirklich bereits gezeichneten Punkte
        int hitPoints = 0; //Punkte im Kreis
        int failPoints = 0; //Punkte außerhalb des Kreises

        int sleepTime = 0;
        
        /*
        Ultraschnell (0ms)
        Wie im Fluge (1ms)
        Sehr schnell (50ms)
        Schnell (100ms)
        Normal (250ms)
        Langsam (500ms)
        Sehr Langsam (1000ms)
        Slow Motion (3 Sekunden)
         */

        public Form1()
        {
            InitializeComponent();
            g = Graphics.FromImage(picture);
            DrawBasis();
            comboBox1.SelectedItem = comboBox1.Items[0];
        }

       
        //Box und den Kreis zeichnen, einfärben
        private void DrawBasis()
        {
            picture = new Bitmap(500, 500);
            g = Graphics.FromImage(picture);

            picture.MakeTransparent();

            //Box zeichnen          

            Rectangle box = new Rectangle(0, 0, 500, 500);
            SolidBrush brushWhite = new SolidBrush(Color.Gray);
            SolidBrush brushNavy = new SolidBrush(Color.Turquoise);           

            //Box zeichnen und einfärben
            g.DrawRectangle(bigPen, box);
            g.FillRectangle(brushWhite, box);

            //Kreis zeichnen und einfärben
            g.DrawEllipse(smallPen, box);
            g.FillEllipse(brushNavy, box);

            pictureBox1.Image = picture;
            pictureBox1.Refresh();
        }

        private void tbInterval_KeyPress(object sender, KeyPressEventArgs e)
        {
            //akzeptiere nur Zahlen (Zeit ist in Millisekunden)
            if (!Char.IsDigit(e.KeyChar))
                e.Handled = true;
            
        }

        enum waitTime { ultra = 0, wif = 1, sschnell = 50, schnell = 100, normal = 250, langsam = 500, slangsam = 1000, slowmo = 3000 };

        private void btnStart_Click(object sender, EventArgs e)
        {            
            //keine aktiven Worker = Start Button            
            if (running == false)
            {

                btnStart.Text = "Stop";
                nupPointNumber.ReadOnly = true;    

                running = true;
                //Zurücksetzen auf 0
                DrawBasis();
                maxPoints = Int32.Parse(nupPointNumber.Text);
                pointList.Clear();
                
                //Zähler auf 0
                currentPoints = 0;
                drawnPoints = 0;
                hitPoints = 0;
                failPoints = 0;

                //für jeden CPU Core einen BackgroundWorker anlegen (-1 für die UI)

                for (int i = 0; i < Environment.ProcessorCount; i++)
                {
                    BackgroundWorker bgw = new BackgroundWorker();
                    bgw.DoWork += new DoWorkEventHandler(bgw_DoWork);
                    bgw.RunWorkerAsync();
                }

               
                
            }
            //aktive Worker = Stop Button
            else
            {                
               // DrawBasis();
                running = false;
                btnStart.Text = "Start";                
                nupPointNumber.ReadOnly = false;                
            }
        }

        void bgw_DoWork(object sender, DoWorkEventArgs e)
        {
            while (drawnPoints < maxPoints)
            {
                if (running == true)
                {
                    Thread.Sleep(sleepTime);

                    Point p1 = new Point(Rand.Next(500), Rand.Next(500));

                    Point m = new Point(250, 250); //mittelpunkt
                    //Entfernung von p1 zu m darf nicht mehr als 250 pixel betragen, sonst außerhalb des Kreises                

                    float d = (float)Math.Sqrt((p1.X - m.X) * (p1.X - m.X) + (p1.Y - m.Y) * (p1.Y - m.Y));
                    if (d < 250)
                        hitPoints++; //Abstand kleienr als 250 -> innerhalb des Kreises, Zähler erhöhen
                    else
                        failPoints++; //Abstand größer als 250 -> außerhalb des Kreises, Zähler erhöhen        
                    try
                    {                                    
                        this.Invoke(new ImageDelegate(drawPoint), p1);
                    }
                    catch
                    {
                        return;
                    }
                }
                else
                {
                    break;
                }
            }
            running = false;                 
        }



        public delegate void ImageDelegate(object a);

        private void drawPoint(object a)
        {
            Point p = (Point)a;            
            Rectangle pointRect = new Rectangle(p, small);
            g.DrawRectangle(pointPenIn, pointRect);
            drawnPoints++;
            

            if (drawnPoints >= maxPoints) //fertig
            {
                running = false;
                nupPointNumber.ReadOnly = false;
                btnStart.Text = "Start";                
                return;
            }  
        }

        private void comboBox1_SelectedIndexChanged(object sender, EventArgs e)
        {
            switch (comboBox1.SelectedIndex)
            {
                case 0:
                    sleepTime = (int)waitTime.ultra;
                    break;
                case 1:
                    sleepTime = (int)waitTime.wif;
                    break;
                case 2:
                    sleepTime = (int)waitTime.sschnell;
                    break;
                case 3:
                    sleepTime = (int)waitTime.schnell;
                    break;
                case 4:
                    sleepTime = (int)waitTime.normal;
                    break;
                case 5:
                    sleepTime = (int)waitTime.langsam;
                    break;
                case 6:
                    sleepTime = (int)waitTime.slangsam;
                    break;
                case 7:
                    sleepTime = (int)waitTime.slowmo;
                    break;
            }
        }
                  
    }
}

 

[convexus]

Hallo,

was hältst du von der unabhängigen Ermittlung von PI pro Thread und Mittelwertbildung um die einzelnen Ergebnisse zusammenzuführen? Auf die Art ist die Zeit für das managen der Threads minimal.

 

[Timmey92]

http://img5.imageshack.us/i/piprogramm.png/
Und wie mache ich das mit der Darstellung?
Ich habe Simulation und Berechnung nicht voneinander getrennt.

Habe die verschiedenen Sachen nun aber sinnvoller in verschiedene Event funktionen verpackt und jetzt läuft alles so wie ich es will, also Threading unnötig
Nur bei 100000000 zu berechnenden Punkten dauert es etwas ^^

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Windows.Forms;
using System.Collections;
using System.Threading;

namespace Monte_Carlo_Visualisierung
{
    public partial class Form1 : Form
    {
        List<Point> pointList = new List<Point>();
        bool running = false;

        Random Rand = new Random(); //Zufallsgenerator

        Bitmap picture = new Bitmap(500, 500);
        Graphics g;
        Pen bigPen = new Pen(Color.Black, 5); //Farbe + Stärke
        Pen smallPen = new Pen(Color.Black, 3);
        Pen pointPenIn = new Pen(Color.Red, 1);
        Pen pointPenOut = new Pen(Color.Blue, 1);
        Size small = new Size(1, 1);

        ulong maxPoints = 10; //Wieviele Punkte dürfen höchstens geworfen werden        
        ulong drawnPoints = 0; //alle wirklich bereits gezeichneten Punkte
        ulong hitPoints = 0; //Punkte im Kreis
        ulong failPoints = 0; //Punkte außerhalb des Kreises

        int sleepTime = 0;
        
        /*
        Ultraschnell (0ms)
        Wie im Fluge (1ms)
        Sehr schnell (50ms)
        Schnell (100ms)
        Normal (250ms)
        Langsam (500ms)
        Sehr Langsam (1000ms)
        Slow Motion (3 Sekunden)
         */

        public Form1()
        {
            InitializeComponent();
            g = Graphics.FromImage(picture);
            DrawBasis();
            comboBox1.SelectedItem = comboBox1.Items[0];
        }

       
        //Box und den Kreis zeichnen, einfärben
        private void DrawBasis()
        {
            picture = new Bitmap(500, 500);
            g = Graphics.FromImage(picture);

            picture.MakeTransparent();

            //Box zeichnen          

            Rectangle box = new Rectangle(0, 0, 500, 500);
            SolidBrush brushWhite = new SolidBrush(Color.Gray);
            SolidBrush brushNavy = new SolidBrush(Color.Turquoise);           

            //Box zeichnen und einfärben
            g.DrawRectangle(bigPen, box);
            g.FillRectangle(brushWhite, box);

            //Kreis zeichnen und einfärben
            g.DrawEllipse(smallPen, box);
            g.FillEllipse(brushNavy, box);

            pictureBox1.Image = picture;
            pictureBox1.Refresh();
        }

        private void tbInterval_KeyPress(object sender, KeyPressEventArgs e)
        {
            //Back Key allowed
            if (e.KeyChar == '\b')
                return;
            
            //akzeptiere nur Zahlen (Zeit ist in Millisekunden)            
            if (!Char.IsDigit(e.KeyChar))
                e.Handled = true;
            
        }

        enum waitTime { ultra = 0, wif = 1, sschnell = 50, schnell = 100, normal = 250, langsam = 500, slangsam = 1000, slowmo = 3000 };

        private void btnStart_Click(object sender, EventArgs e)
        {            
            //keine aktiven Worker = Start Button            
            if (running == false)
            {

                btnStart.Text = "Stop";
                nupPointNumber.ReadOnly = true;    

                running = true;
                //Zurücksetzen auf 0
                DrawBasis();
                maxPoints = UInt64.Parse(nupPointNumber.Text);
                pointList.Clear();
                
                //Zähler auf 0
                drawnPoints = 0;
                hitPoints = 0;
                failPoints = 0;

                //für jeden CPU Core einen BackgroundWorker anlegen (-1 für die UI)

              //  for (int i = 0; i < Environment.ProcessorCount; i++)
                {
                    BackgroundWorker bgw = new BackgroundWorker();
                    bgw.DoWork += new DoWorkEventHandler(bgw_DoWork);
                    bgw.WorkerReportsProgress = true;
                    bgw.ProgressChanged += new ProgressChangedEventHandler(bgw_ProgressChanged);
                    bgw.RunWorkerAsync();
                }

               
                
            }
            //aktive Worker = Stop Button
            else
            {                
               // DrawBasis();
                running = false;
                btnStart.Text = "Start";                
                nupPointNumber.ReadOnly = false;                
            }
        }

        void bgw_ProgressChanged(object sender, ProgressChangedEventArgs e)
        {
            progressBar1.Value=e.ProgressPercentage;
        }

        void bgw_DoWork(object sender, DoWorkEventArgs e)
        {
            while (drawnPoints < maxPoints)
            {
                if (running == true)
                {
                    Thread.Sleep(sleepTime);

                    Point p1 = new Point(Rand.Next(500), Rand.Next(500));

                    Point m = new Point(250, 250); //mittelpunkt
                    //Entfernung von p1 zu m darf nicht mehr als 250 pixel betragen, sonst außerhalb des Kreises                

                    float d = (float)Math.Sqrt((p1.X - m.X) * (p1.X - m.X) + (p1.Y - m.Y) * (p1.Y - m.Y));
                    if (d < 250)
                        hitPoints++; //Abstand kleienr als 250 -> innerhalb des Kreises, Zähler erhöhen
                    else
                        failPoints++; //Abstand größer als 250 -> außerhalb des Kreises, Zähler erhöhen        
                    try
                    {                                    
                        this.Invoke(new ImageDelegate(drawPoint), p1,d);
                    }
                    catch
                    {
                        return;
                    }

                    ulong progress = drawnPoints * 100 / maxPoints;

                    ((BackgroundWorker)sender).ReportProgress((int)progress);
                }
                else
                {
                    break;
                }
            }
            running = false;                 
        }



        public delegate void ImageDelegate(object a, float d);

        private void drawPoint(object a, float d)
        {
            Point p = (Point)a;
            Point m = new Point(250, 250); //mittelpunkt
            Rectangle pointRect = new Rectangle(p, small);
            //float d = (float)Math.Sqrt((p.X - m.X) * (p.X - m.X) + (p.Y - m.Y) * (p.Y - m.Y));
            if(d>250)
                g.DrawRectangle(pointPenIn, pointRect);
            else
                g.DrawRectangle(pointPenOut, pointRect);
            drawnPoints++;            

            if (drawnPoints >= maxPoints) //fertig
            {
                running = false;
                nupPointNumber.ReadOnly = false;
                btnStart.Text = "Start";                
                return;
            }  
        }

        private void comboBox1_SelectedIndexChanged(object sender, EventArgs e)
        {
            switch (comboBox1.SelectedIndex)
            {
                case 0:
                    sleepTime = (int)waitTime.ultra;
                    break;
                case 1:
                    sleepTime = (int)waitTime.wif;
                    break;
                case 2:
                    sleepTime = (int)waitTime.sschnell;
                    break;
                case 3:
                    sleepTime = (int)waitTime.schnell;
                    break;
                case 4:
                    sleepTime = (int)waitTime.normal;
                    break;
                case 5:
                    sleepTime = (int)waitTime.langsam;
                    break;
                case 6:
                    sleepTime = (int)waitTime.slangsam;
                    break;
                case 7:
                    sleepTime = (int)waitTime.slowmo;
                    break;
            }
        }

        private void timer1_Tick(object sender, EventArgs e)
        {
            pictureBox1.Refresh();
            textBox1.Text = "" + (4 * (double)hitPoints / (double)drawnPoints);
        }
                  
    }
}

 

[kuddlmuddl]

Die Idee bei der Parallelisierung von Monte-Carlo Algorithmen ist NICHT jedem Partikel/Sample/Instanz/Modell einen eigenen Thread zuzuweisen!

Stattdessen nimmt man (wie du schon oben geschrieben hast) einen Threadpool mit einer für deine CPU sinnvollen Anzahl von Threads - zB 8 - und lässt jeden Thread aus deinem Thread-Pool die Partikel verarbeiten.

Ich hab mal was Monte-Carlo mäßiges programmiert mit einer konstanten Partikel-Zahl und einfach je 50 der 200 Partikel an einen der 4 Threads vergeben.
Unter der Annahme, dass die Verarbeitung eines jeden Partikels quasi gleich lange dauert ist es dann auch legitim einfach jedem Thread die selbe Anzahl an Partikel zu geben anstatt einen Pool zu verwalten, der sich bei Langeweile einen Partikel vornimmt.
Das erspart dir auch jegliche Absicherung von Gleichzeitigem Speicherzugriff da du jedem Thread einfach einen "eigenen" Breich aller Partikel zuweist die es exklusiv verarbeitet.
So vonwegen: Thread1 nimmt 0 bis 49, Thread2 nimmt 50 bis 99, Thread 3 nimmt 100 bis 149 und Thread 4 nimmt 150 bis 199

Ich hab deinen Quelltext ehrlich gesagt nicht angeguckt, aber du hast vermutlich eine steigende Zahl von Partikeln? Dann würde ich evtl das Bild in so viele Teile unterteilen wie du Threads nutzt.
Entweder zB im Bogenmaß und dann 360°/AnzahlDerThreads als Tortenstückform oder halt einfach in die 4 Quadranten I, II, III, IV unterteilen.

 

[ice-breaker]

Nur bei 100000000 zu berechnenden Punkten dauert es etwas ^^

reduzier die Anzahl der Objekte, nicht jeden Punkt einzeln berechnen lassen sondern es in "Working Sets" packen, also immer eine Reihe von Aufträgen die zusammen von einem Thread ausgeführt werden, sonst hast du zuviel Synchronisierung zwischen den Kernen, da die Auftragsliste ja geteilt wird.

Zudem schau mal wie du in C# für den Threadpool die Anzahl an Threads limitieren kannst, stell die Anzahl auf Prozessorkerne + 1 (HyperThreading-"Kerne" ignorieren)