Unabhängige Zufallszahlen / Random Klasse im .NET Framework

Veröffentlicht am 26. Februar 2014 von Octoate

Heute hat mir ein Kollege erzählt, dass die Random Klasse im .NET Framework keine vernünftigen Zufallszahlen erzeugen würde und dass zwei Instanzen der Random Klasse jeweils die gleichen Zufallszahlen erzeugen. Das entsprechende Beispiel hat er mir schnell anhand eines kleinen NUnit-Tests gezeigt, der in etwa so aussah:

var numbers1 = new List<int>();
var numbers2 = new List<int>();

var random1 = new Random();
for (int i = 0; i < RANDOMNUMBERS; i++)
{
	numbers1.Add(random1.Next());
}

var random2 = new Random();
for (int i = 0; i < RANDOMNUMBERS; i++)
{
	numbers2.Add(random2.Next());
}

var numbers1 = new List<int>();

var numbers2 = new List<int>();

var random1 = new Random();

for (int i = 0; i < RANDOMNUMBERS; i++)

{

numbers1.Add(random1.Next());

}

var random2 = new Random();

for (int i = 0; i < RANDOMNUMBERS; i++)

{

numbers2.Add(random2.Next());

}

Lässt man das Programm laufen und vergleicht die beiden erzeugten Listen stellt man fest, dass beide Listen die gleichen Zufallszahlen enthalten, was meinen Kollegen etwas überrascht hat. Der Grund ist dafür aber eigentlich recht einfach und auch in der Hilfe zum .NET Framework dokumentiert. Die Initialisierung des Pseudozufallszahlengenerator wird anhand der Systemzeit durchgeführt und da die Random Klasse nur einen recht einfachen Zufallszahlengenerator beinhaltet, liefern beide Klassen jetzt die gleichen Werte zurück.
Das Problem kann man auf unterschiedlichen Wegen lösen. Zum Einen kann man einfach nur ein Objekt verwenden, das die Pseudozufallszahlen zurückliefert. Benötigt man trotzdem zwei unterschiedliche Instanzen der Klasse Random könnte man mittels System.Environment.TickCount die Klassen unterschiedlich instantiieren, bspw. so:

var random1 = new Random(System.Environment.TickCount);
var random2 = new Random(System.Environment.TickCount + 1);

1 2	var random1 = new Random(System.Environment.TickCount); var random2 = new Random(System.Environment.TickCount + 1);

Eine letzte Möglichkeit ist es, einen Zufallszahlengenerator zu verwenden, der kryptographisch sichere Zufallszahlen erzeugt. So einen Zufallszahlengenerator bietet das .NET Framework unter System.Security.Cryptography.RandomNumberGenerator. Das Programm wird dadurch allerdings etwas aufwendiger, da ein solcher Zufallszahlengenerator immer in ein Byte-Array schreibt und man das Array dann erst in den benötigten Variablentyp umwandeln muss. Das Programm von oben würde unter Verwendung eines solchen Zufallszahlengenerator dann so aussehen:

var byteBuffer = new byte[4];
var numbers1 = new List<int>();
var numbers2 = new List<int>();

var random1 = RandomNumberGenerator.Create();
for (int i = 0; i < RANDOMNUMBERS; i++)
{
	random1.GetBytes(byteBuffer);
	numbers1.Add(BitConverter.ToInt32(byteBuffer, 0));
}

var random2 = RandomNumberGenerator.Create();
for (int i = 0; i < RANDOMNUMBERS; i++)
{
	random2.GetBytes(byteBuffer);
	numbers2.Add(BitConverter.ToInt32(byteBuffer, 0));
}

var byteBuffer = new byte[4];

var numbers1 = new List<int>();

var numbers2 = new List<int>();

var random1 = RandomNumberGenerator.Create();

for (int i = 0; i < RANDOMNUMBERS; i++)

{

random1.GetBytes(byteBuffer);

numbers1.Add(BitConverter.ToInt32(byteBuffer, 0));

}

var random2 = RandomNumberGenerator.Create();

for (int i = 0; i < RANDOMNUMBERS; i++)

{

random2.GetBytes(byteBuffer);

numbers2.Add(BitConverter.ToInt32(byteBuffer, 0));

}

Klingt doch eigentlich logisch, oder? Jedenfalls sollte man bei der Verwendung der Klasse Random etwas aufpassen und daran denken, dass bei Initialisierung mit gleichen Werten auch die gleichen Zufallszahlen zurückgegeben werden und sogar vorhersagbare Zufallszahlen zurückgeliefert werden (was in den meisten Fällen aber kein Problem sein sollte).

Matrix Multiplikation auf der Grafikkarte mit .NET und Cudafy

Veröffentlicht am 24. Juni 2013 von Octoate

Antworten

Die Parallelisierung von Algorithmen und Programmteilen hat mir schon immer Spaß gemacht und ich habe mir sogar zu Hause einen Rechencluster gebaut, mit dem ich experimentieren konnte. In der aktuellen dotnetpro Ausgabe (07/2013) beschreibt Bernd Marquardt, bei dem ich auf der Parallel 2012 Konferenz einen .NET TPL Workshop mitmachen durfte, in einem Artikel die Parallelisierung von Algorithmen mit AMP unter C++, die dann auf der Grafikkarte ausgeführt werden. Leider muss man hier immer noch den Umweg über C++ gehen, aber glücklicherweise gibt es für .NET mit Cudafy ein Framework, mit dem man diesen Umweg nicht gehen muss. Cudafy unterstützt, neben dem namensgebenden CUDA von Nvidia, auch OpenCL, sodass man damit plattformübergreifende Parallelisierungen vornehmen kann. Ich habe in den letzten Tage ein wenig mit Cudafy herumgespielt und möchte hier einmal ein recht simples Beispiel der Matrixmultiplikation beschreiben.

Um Cudafy zu verwenden, benötigen wir zuerst ein GPGPU Objekt, das unsere zu verwendende Hardware repräsentiert. Cudafy unterstützt dabei sowohl CUDA von Nvidia als auch OpenCL der Khronos Group. Ich habe mich in meinem Beispiel für OpenCL entschieden, denn so konnte ich sowohl die CPU als auch die beiden Grafikkarten in meinem System (Intel und Nvidia) zur Berechnung auswählen. Folgender Codeschnippsel zeigt die Instanziierung des GPGPU Objektes, ein ganz rudimentäres Exception Handling (jaja, ich weiss ;-)) und die Instanziierung meiner Matrixmultiplikationsklasse.

CudafyModes.Target = eGPUType.OpenCL;
CudafyModes.DeviceId = 2;
CudafyTranslator.Language = eLanguage.OpenCL;
try
{
	var gpu = CudafyHost.GetDevice(eGPUType.OpenCL, CudafyModes.DeviceId);
	Console.WriteLine("Running examples using {0}", gpu.GetDeviceProperties().Name);

	Console.WriteLine("Available devices {0}", CudafyHost.GetDeviceCount(eGPUType.OpenCL));

	var matrixMult = new MatrixMultiplication(gpu, 512);
	matrixMult.Execute();
	matrixMult.CpuCalculation();
}
catch (Exception ex)
{
	Console.WriteLine(ex);
}
Console.ReadKey();

CudafyModes.Target = eGPUType.OpenCL;

CudafyModes.DeviceId = 2;

CudafyTranslator.Language = eLanguage.OpenCL;

try

{

var gpu = CudafyHost.GetDevice(eGPUType.OpenCL, CudafyModes.DeviceId);

Console.WriteLine("Running examples using {0}", gpu.GetDeviceProperties().Name);

Console.WriteLine("Available devices {0}", CudafyHost.GetDeviceCount(eGPUType.OpenCL));

var matrixMult = new MatrixMultiplication(gpu, 512);

matrixMult.Execute();

matrixMult.CpuCalculation();

}

catch (Exception ex)

{

Console.WriteLine(ex);

}

Console.ReadKey();

Wichtigster Grundstein meiner Entwicklungsumgebung ist eine abstrakte Basisklasse, von denen meine implementierten Algorithmenklassen erben. Dieser Schritt ist nicht unbedingt notwendig, macht aber in meinem Fall Sinn, da ich beim „Herumspielen“ nicht nur die Matrixmultiplikation implementiert habe, sondern auch andere Algorithmen.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

using Cudafy;
using Cudafy.Host;
using Cudafy.Translator;
using System.Diagnostics;

namespace CudafyTest.Common
{
    internal abstract class GpuCalculation
    {
        protected GPGPU Gpu { get; set; }

        public GpuCalculation(GPGPU gpu)
        {
            Gpu = gpu;
        }

        public void Execute()
        {
            CudafyModule km = CudafyTranslator.Cudafy(this.GetType());
            Gpu.LoadModule(km);

            var stopWatch = new Stopwatch();
            stopWatch.Start();

            OnExecute();

            stopWatch.Stop();
            Console.WriteLine("Execution time = {0} ms", stopWatch.ElapsedMilliseconds);
        }

        protected abstract void OnExecute();
    }
}

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

using Cudafy;

using Cudafy.Host;

using Cudafy.Translator;

using System.Diagnostics;

namespace CudafyTest.Common

{

internal abstract class GpuCalculation

{

protected GPGPU Gpu { get; set; }

public GpuCalculation(GPGPU gpu)

{

Gpu = gpu;

}

public void Execute()

{

CudafyModule km = CudafyTranslator.Cudafy(this.GetType());

Gpu.LoadModule(km);

var stopWatch = new Stopwatch();

stopWatch.Start();

OnExecute();

stopWatch.Stop();

Console.WriteLine("Execution time = {0} ms", stopWatch.ElapsedMilliseconds);

}

protected abstract void OnExecute();

}

Im Konstruktor muss ein GPGPU Objekt übergeben werden, das die ausgewählte Client Hardware repräsentiert (die Instanziierung wurde bereits weiter oben beschrieben). Die Execute Methode enthält nun den Code, der benötigt wird, m einen Kernel mit Cudafy für die zu verwendende Client Hardware vorzubereiten (Aufruf von Cudafy(…) und LoadModule(..)). Außerdem wird noch eine Zeitmessung mit der allseits bekannten Stopwatch() durchgeführt. In diesem Block wird die innerhalb der Algorithmenklasse zu implementierenden Methode OnExecute() aufgerufen, sodass nach Ausführung die Dauer der Berechnung (inklusive der Übertragungszeit der Daten zur berechnenden Hardware) in der Konsole ausgegeben wird.

Die Klasse zur Matrixmultiplikation sieht dann so aus.

using Cudafy;
using Cudafy.Host;
using CudafyTest.Common;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CudafyTest.Calculations
{
    class MatrixMultiplication : GpuCalculation
    {
        private float[,] m_A;
        private float[,] m_B;
        private float[,] m_Result;
        private float[,] m_ResultCpu;
        private int m_Dimension;

        public MatrixMultiplication(GPGPU gpgpu, int number) : base(gpgpu)
        {
            m_Dimension = number;
            InitExampleArrays(number);
        }

        private void InitExampleArrays(int number)
        {
            m_A = new float[number, number];
            m_B = new float[number, number];
            m_Result = new float[number, number];

            //fill the array
            for (int i = 0; i < number; i++)
            {
                for (int j = 0; j < number; j++)
                {
                    m_A[i, j] = 1.0f + (float)i * (float)(number - j) / (float)number;
                    m_B[i, j] = 1.0f + (float)(number - i) * (float)j / (float)number;
                }
            }

            //PrintResult(m_A);
            //PrintResult(m_B);
        }

        protected override void OnExecute()
        {
            float[,] devA = Gpu.CopyToDevice(m_A);
            float[,] devB = Gpu.CopyToDevice(m_B);
            float[,] devResult = Gpu.Allocate(m_Result);

            Gpu.Launch(new dim3(m_Dimension, m_Dimension), 1).Multiply(m_Dimension, devA, devB, devResult);

            Gpu.CopyFromDevice(devResult, m_Result);

            Gpu.FreeAll();

            //PrintResult(m_Result);
        }

        [Cudafy]
        public static void Multiply(GThread gthread, int dimension, float[,] a, float[,] b, float[,] result)
        {
            int x = gthread.blockIdx.x * gthread.blockDim.x + gthread.threadIdx.x;
            int y = gthread.blockIdx.y * gthread.blockDim.y + gthread.threadIdx.y;

            if (x >= dimension || y >= dimension)
            {
                return;
            }

            float sum = 0.0f;
            for (int k = 0; k < dimension; k++)
            {
                sum += a[x, k] * b[k, y];
            }

            result[x, y] = sum;
        }

        public void CpuCalculation()
        {
            Stopwatch watch = new Stopwatch();
            watch.Start();

            m_ResultCpu = new float[m_Dimension, m_Dimension];

            for (int x = 0; x < m_Dimension; x++)
            {
                for (int y = 0; y < m_Dimension; y++)
                {
                    float sum = 0.0f;

                    for (int k = 0; k < m_Dimension; k++)
                    {
                        sum += m_A[x, k] * m_B[k, y];
                    }

                    m_ResultCpu[x, y] = sum;
                }
            }

            Console.WriteLine("CPU Calculation:");
            //PrintResult(m_Result);

            watch.Stop();

            Console.WriteLine("Time elapsed {0} ms", watch.ElapsedMilliseconds);
        }

        private void PrintResult(float[,] m_Result)
        {
            for (int y = 0; y < m_Dimension; y++)
            {
                for (int x = 0; x < m_Dimension; x++)
                {
                    Console.Write("{0:F} ", m_Result[x, y]);
                }
                Console.WriteLine();
            }

            Console.WriteLine();
        }

    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

using Cudafy;

using Cudafy.Host;

using CudafyTest.Common;

using System;

using System.Collections.Generic;

using System.Diagnostics;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace CudafyTest.Calculations

{

class MatrixMultiplication : GpuCalculation

{

private float[,] m_A;

private float[,] m_B;

private float[,] m_Result;

private float[,] m_ResultCpu;

private int m_Dimension;

public MatrixMultiplication(GPGPU gpgpu, int number) : base(gpgpu)

{

m_Dimension = number;

InitExampleArrays(number);

}

private void InitExampleArrays(int number)

{

m_A = new float[number, number];

m_B = new float[number, number];

m_Result = new float[number, number];

//fill the array

for (int i = 0; i < number; i++)

{

for (int j = 0; j < number; j++)

{

m_A[i, j] = 1.0f + (float)i * (float)(number - j) / (float)number;

m_B[i, j] = 1.0f + (float)(number - i) * (float)j / (float)number;

}

//PrintResult(m_A);

//PrintResult(m_B);

}

protected override void OnExecute()

{

float[,] devA = Gpu.CopyToDevice(m_A);

float[,] devB = Gpu.CopyToDevice(m_B);

float[,] devResult = Gpu.Allocate(m_Result);

Gpu.Launch(new dim3(m_Dimension, m_Dimension), 1).Multiply(m_Dimension, devA, devB, devResult);

Gpu.CopyFromDevice(devResult, m_Result);

Gpu.FreeAll();

//PrintResult(m_Result);

}

[Cudafy]

public static void Multiply(GThread gthread, int dimension, float[,] a, float[,] b, float[,] result)

{

int x = gthread.blockIdx.x * gthread.blockDim.x + gthread.threadIdx.x;

int y = gthread.blockIdx.y * gthread.blockDim.y + gthread.threadIdx.y;

if (x >= dimension || y >= dimension)

{

return;

}

float sum = 0.0f;

for (int k = 0; k < dimension; k++)

{

sum += a[x, k] * b[k, y];

}

result[x, y] = sum;

}

public void CpuCalculation()

{

Stopwatch watch = new Stopwatch();

watch.Start();

m_ResultCpu = new float[m_Dimension, m_Dimension];

for (int x = 0; x < m_Dimension; x++)

{

for (int y = 0; y < m_Dimension; y++)

{

float sum = 0.0f;

for (int k = 0; k < m_Dimension; k++)

{

sum += m_A[x, k] * m_B[k, y];

}

m_ResultCpu[x, y] = sum;

}

Console.WriteLine("CPU Calculation:");

//PrintResult(m_Result);

watch.Stop();

Console.WriteLine("Time elapsed {0} ms", watch.ElapsedMilliseconds);

}

private void PrintResult(float[,] m_Result)

{

for (int y = 0; y < m_Dimension; y++)

{

for (int x = 0; x < m_Dimension; x++)

{

Console.Write("{0:F} ", m_Result[x, y]);

}

Console.WriteLine();

}

Console.WriteLine();

}

Wie bereits erwähnt, ist diese Klasse während meiner Tests entstanden, sodass ich in diesem Beispiel Testdaten verwenden, die ich bei Aufruf des Konstruktors generiere. Dem Konstruktor wird in diesem Beispiel neben dem GPGPU Objekt auch noch die Dimension der Matrix mit übergeben. Die wichtigsten Teile des Codes stecken aber in der Methode OnExecute() und Multiply(…). Die Methode OnExecute() ist dafür verantwortlich, den Speicher auf der Client Hardware anzulegen und die Arrays vom Host auf den Client zu übertragen. Dies wird hier durch die Methode CopyToDevice(…) vorgenommen. Das Ergebnisarray wird nicht auf die Client Hardware kopiert, sondern nur der Speicher reserviert, da es zu Beginn sowieso leer ist und deshalb keine Daten benötigt werden. Die Launch(…) Methode startet dann die Berechnung auf der Client Hardware. Den Aufruf werde ich hier nicht weiter erläutern, mehr zur Launch(…) Methode findet man aber in der Cudafy Dokumentation. Nach dem Aufruf wird das Ergebnis von der Hardware wieder auf den Host übertragen und der belegte Speicher auf dem Client wieder freigegeben. Das war’s auch schon.

Die Client Implementierung des Algorithmus steckt in der mit dem „Cudafy“ Attribut markierten Methode Multiply(…). Die Methodenparameter sind GThread (wird standardmäßig von Cudafy hinzugefügt und enthält Statusinformationen), die Dimension der Matrix und die Matrizen für die Matrixmultiplikation. In dieser Methode wird zuerst die x und y Position innerhalb der Matrix errechnet. Die Berechnung orientiert sich hier an den Blöcken, die über die Launch Methode mit übergeben werden. Genauere Informationen dazu findet ihr in den Grundlagen zum Thema OpenCL und CUDA. Im nächsten Schritt wird vorsichtshalber noch überprüft, dass x und y auch wirklich innerhalb der Matrix liegen und anschließend die Matrixmultiplikation durchgeführt, die dann im Ergebnisarray gespeichert wird.

Die Methode CpuCalculation() habe ich implementiert, um die Geschwindigkeit einer einzelnen CPU mit der Ausführung auf einem Client zu vergleichen. Auf meinem Rechner war eine Nvidia GT650M bei einer Dimension von 256 bereits 3x so schnell wie ein Kern meiner i7 CPU. Bei einer Dimension von 512 war sie schon um den Faktor 7,5 schneller.

Abschließend kann man sagen, dass sich die Nutzung einer Grafikkarte als Client bei einem hinreichend großen Problem lohnt und man damit eine große Beschleunigung erreichen kann. Dank Cudafy funktioniert das alles auch in .NET ohne den Umweg über C++. In meinem Beispiel bleibt außerdem noch viel Platz für Optimierungen, da ich das Beispiel möglichst simpel halten wollte – und das gilt sowohl für die Berechnung der Matrixmultiplikation auf der CPU (hier wäre bspw. eine Implementierung mit der TPL sinnvoll, die dann alle Kerne nutzt) als auch auf der GPU.

C# – Byte Array als Key in einem Dictionary / HashSet

Veröffentlicht am 6. Juni 2013 von Octoate

Antworten

Heute stand ich vor dem Problem, dass ich ein Byte Array als Index in einem Dictionary in .NET verwenden wollte. Das hat natürlich nicht funktioniert, da der Hash-Code von zwei inhaltsgleichen Byte-Arrays ungleich ist und dadurch der Vergleich beim Zugriff fehl schlägt. Wenn ich also überprüfen möchte, ob ein Key bereits in der Datenstruktur vorhanden ist, wird es immer fehl schlagen, da das erzeugte Objekt mit in den Hashwert eingeht.

Das folgende kleine Beispiel zeigt das Problem:

byte[] arr1 = new byte[] { 1, 2, 3 };
byte[] arr2 = new byte[] { 1, 2, 3 };

Console.WriteLine(string.Format("Hash Array 1 = '{0}', Hash Array 2 = '{1}'", arr1.GetHashCode(), arr2.GetHashCode()));

byte[] arr1 = new byte[] { 1, 2, 3 };

byte[] arr2 = new byte[] { 1, 2, 3 };

Console.WriteLine(string.Format("Hash Array 1 = '{0}', Hash Array 2 = '{1}'", arr1.GetHashCode(), arr2.GetHashCode()));

Man erhält als Ergebnis „Hash Array 1 = ‚37121646‘, Hash Array 2 = ‚45592480‘”. Fügt man also das erste Array z.B. einem Dictionary hinzu, wird mit bei einer Abfrage mit ContainsKey(…) ein false erhalten.

Glücklicherweise gibt es seit .NET 3.5 die Möglichkeit, diesen Datentypen im Konstruktor einen IEqualityComparer<T> mitzugeben, der dann den Vergleich übernimmt. Eine Klasse, die dieses Interface implementiert, muss die Methoden Equals(…) und GetHashCode(…) zur Verfügung stellen. Für meinen Anwendungsfall reicht die folgende Implementierung:

internal class ByteArrayComparer : IEqualityComparer<byte[]>
{
	public bool Equals(byte[] x, byte[] y)
	{
		if (x == null || y == null)
		{
			return x == y;
		}
		return x.SequenceEqual(y);
	}

	public int GetHashCode(byte[] obj)
	{
		return BitConverter.ToString(obj).GetHashCode();
	}
}

internal class ByteArrayComparer : IEqualityComparer<byte[]>

{

public bool Equals(byte[] x, byte[] y)

{

if (x == null || y == null)

{

return x == y;

}

return x.SequenceEqual(y);

}

public int GetHashCode(byte[] obj)

{

return BitConverter.ToString(obj).GetHashCode();

}

Wichtig ist hier speziell die GetHashCode(…) Methode. Hier wird der Inhalt des Arrays mit dem BitConverter in einen Hex-String konvertiert und von diesem String der HashCode zurückgegeben. Der Hash wird dann also über den Inhalt gebildet und ist dann bei beiden Arrays gleich. Unsere neue Implementierung wird dem Konstruktor dann mit übergeben und dann in der entsprechenden Datenstruktur verwendet. Das folgende Beispiel zeigt die Anwendung und ein „Vorher / Nachher“ Vergleich:

byte[] arr1 = new byte[] { 1, 2, 3 };
byte[] arr2 = new byte[] { 1, 2, 3 };

//ohne IEqualityComparer
HashSet<byte[]> test = new HashSet<byte[]>() { arr1 };
Console.WriteLine(string.Format("Ohne IEqualityComparer - Contains = {0}", test.Contains(arr2)));

//mit IEqualityComparer
test = new HashSet<byte[]>(new ByteArrayComparer()) { arr1 };
Console.WriteLine(string.Format("Mit IEqualityComparer - Contains = {0}", test.Contains(arr2)));

byte[] arr1 = new byte[] { 1, 2, 3 };

byte[] arr2 = new byte[] { 1, 2, 3 };

//ohne IEqualityComparer

HashSet<byte[]> test = new HashSet<byte[]>() { arr1 };

Console.WriteLine(string.Format("Ohne IEqualityComparer - Contains = {0}", test.Contains(arr2)));

//mit IEqualityComparer

test = new HashSet<byte[]>(new ByteArrayComparer()) { arr1 };

Console.WriteLine(string.Format("Mit IEqualityComparer - Contains = {0}", test.Contains(arr2)));

Startet man das Programm, erhält man folgende Ausgabe „Ohne IEqualityComparer – Contains = False. Mit IEqualityComparer – Contains = True“. Problem gelöst :-).

Octoate.de – Sinnvolles könnt ihr woanders lesen

Konkrete Themen – Fehlanzeige, was mich gerade beschäftigt, wird aufs Korn genommen.

Archiv der Kategorie: CSharp

Unabhängige Zufallszahlen / Random Klasse im .NET Framework

Matrix Multiplikation auf der Grafikkarte mit .NET und Cudafy

C# – Byte Array als Key in einem Dictionary / HashSet