Die Verwendung von mehrdimensionalen Arrays ist oftmals ein wesentlicher Bestandteil in Programmen. Je nach Problemstellung und Größe der Arrays kann der Zugriff auf solche die Laufzeit eines Programms negativ beeinflussen.

In C# gibt es grundsätzlich neben den eindimensionalen Arrays 2 Arten von mehrdimensionalen Arrays. Diese unterscheiden sich nur in ihrer Notation:

• [,] – Multidimensionale Arrays
• [][] – Jagged-Arrays

Bei multidimensionalen Arrays werden die Dimensionen durch ein Komma getrennt, bei Jagged-Arrays durch die erneute Klammerung. Multidimensionale Arrays haben eine feste Größe. Bei einem Jagged-Array kann die Größe variieren, da es ein Array von Arrays ist. Das ist im Grunde genommen eigentlich schon alles was man darüber wissen sollte. – Wie aber steht es jetzt mit den Geschwindigkeits-Unterschieden? Gibt es vielleicht noch andere Möglichkeiten?

Ja! Die gibt es definitiv. Bei einem Disput mit einem Kommilitonen über genau dieses Thema hat dieser prompt einen Eintrag in seinem Blog dazu und dazugehörige Messergebnisse veröffentlicht:

 Manolo's HPC Blog

Er verwendet dort eine weitere, eher aus der Welt der C Programmierer bekannte Technik, um mehrdimensionale Arrays zu realisieren. Es wird einfach ein eindimensionales Array verwendet, das alle Elemente linear beinhaltet.

Der Zugriff erfolgt über die Formel:

position = Y * breite + X

Als ich das Ergebnis das erste mal sah, konnte ich kaum glauben, dass dieses schneller als ein Jagged-Array ist. Aber bei einer genaueren Untersuchung erklärt sich auch warum. Darf man dem manik.net – Blog trauen:

MSIL kann eindimensionale Arrays besser optimieren wie mehrdimensionale.
Auf MSIL ebene sieht man den unterschied:

int [,] secondarr = new int[1, 2];
secondarr[0, 0] = 40;

MSIL:
IL_0029: ldc.i4.s 40
IL_002b: call instance void int32[0...,0...]::Set(int32, int32,in32)

Mit einem Jaggedarray sieht das ganze dann auf MSIL so aus:
IL_001c: ldc.i4.s 40
IL_001e: stelem.i4
stelem = „store an element“

Bei mehrdimensionalen Arrays wird der ganze „Generic Type“-Kram also betrieben was einiges an Overhead erzeugt.

Daher ist es ratsam wann immer möglich ein lineares Array anstelle von einem Mehrdimensionalen Array zu verwenden.

Ich habe mir die ganze Sache aber in eigener Regie noch einmal angesehen. Als Ergebnis habe ich es geschafft, eine noch schnellere Variante zu programmieren. Diese setzt allerdings ein \unsafe bei den Compiler-Einstellungen voraus.

Anstelle auf die einzelnen Elemente des Arrays zuzugreifen, wird direkt auf einen Pointer zugegriffen. – Eigentlich nichts besonderes, kann aber bei manch einer Berechnung den ein oder anderen Performancegewinn bringen.

Die Ergebnisse sehen dabei wie folgt aus:

Result = 249500250000000
1000times: Matrix A with [1000, 1000]  (matrix array): 11637ms
Result = 249500250000000
1000times: Matrix B with [1000][1000]  (jagged array): 6361ms
Result = 249500250000000
1000times: Matrix C with [1000* 1000]  (linear array): 5486ms
Result = 249500250000000
1000times: Matrix D with [1000* 1000]  (unsafe array): 5175ms!!!

Gegenüber dem [,] Array sind die beiden letzten Varianten ungefähr doppelt so schnell.

Also für die Zukunft merken:

• Keine [,]-Arrays verwenden!

• [][]-Arrays können durch lineare Arrays ersetzt werden!

Den Quellcode zum verifizieren und selber Testen gibt es hier:

          using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Diagnostics; namespace SpeedTest
{ class Program { staticvoid Main(string[]
args) { int n = 1000; Stopwatch swatch = new Stopwatch(); double[,]
A = newdouble[n, n]; swatch.Start();
CalcMatrix(A,n); swatch.Stop(); Console.WriteLine("{0}times:
Matrix A with [{0}, {0}] (matrix array): {1}ms", n, swatch.ElapsedMilliseconds);
swatch.Reset(); double[][] B = newdouble[n][]; //
init jagged arraysfor (int i
= 0; i < n; i++) { B[i] = newdouble[n];
} swatch.Start(); CalcJagged(B, n); swatch.Stop(); Console.WriteLine("{0}times:
Matrix B with [{0}][{0}] (jagged array): {1}ms", n, swatch.ElapsedMilliseconds);
swatch.Reset(); double[] C = newdouble[n*
n]; swatch.Start(); CalcLinear(C, n); swatch.Stop(); Console.WriteLine("{0}times:
Matrix C with [{0}* {0}] (linear array): {1}ms", n, swatch.ElapsedMilliseconds);
swatch.Reset(); unsafe { double[]
D = newdouble[n * n]; swatch.Start(); fixed(double*
pD = D) CalcUnsafe(pD,n); swatch.Stop(); } Console.WriteLine("{0}times:
Matrix D with [{0}* {0}] (unsafe array): {1}ms", n, swatch.ElapsedMilliseconds);
swatch.Reset(); Console.ReadKey(); } privatestaticvoid CalcJagged(double[][]
B, int n) { double result = 0; for (int x
= 0; x < n; x++) { for (int i
= 0; i < n; i++) { for (int j
= 0; j < n; j++) { B[i][j] = i * j; result += B[i][j]; } } } Console.WriteLine("Result
= " + result); } privatestaticvoid CalcMatrix( double[,]
A, int n) { double result = 0; for (int x
= 0; x < n; x++) { for (int i
= 0; i < n; i++) { for (int j
= 0; j < n; j++) { A[i, j] = i * j; result += A[i, j]; } } } Console.WriteLine("Result
= " + result); } privatestaticvoid CalcLinear(double[]
C, int n) { double result = 0; for (int x
= 0; x < n; x++) { for (int i
= 0; i < n; i++) { for (int j
= 0; j < n; j++) { C[i * n + j] = i * j; result += C[i * n + j]; } } } Console.WriteLine("Result
= " + result); } unsafeprivatestaticvoid CalcUnsafe(double*
pD, int n) { double result = 0; for (int x
= 0; x < n; x++) { for (int i
= 0; i < n; i++) { for (int j
= 0; j < n; j++) { *(pD + i * n + j) = i * j; result += *(pD + i * n + j); } }
} Console.WriteLine("Result = " + result); } }
}

Ich hatte gestern bereits mit einem kleinen Problem zu kämpfen, welches sich aber recht leicht beheben lässt.

Nachdem man eine neue Compute-Node hinzugefügt hat, und einen Framework-Test ausgeführt hat, kam es zu folgenden Fehler:

Exception thrown while executing RunDiagnostic: Could not load file or assembly 'file:///C:\Program Files\Microsoft HPC Pack 2008 R2\Bin\CCPPSH.dll' or one of its dependencies. The system cannot find the file specified.

System.IO.FileNotFoundException

Ein einfaches Nach-Kopieren der Dateien genügt leider nicht. Um sich Abhilfe zu schaffen empfehle ich folgende Methode:

Als erstes sollte man die betroffene Node offline nehmen, im Cluster Manager also “Take Offline” mit einem Rechtsklick auf die Node auswählen.

Danach kopiert (z.B. per Remote Desktop und Kopieren/Einfügen)  ihr das HPC Pack 2008 R2 auf die betroffene Node. Dafür habe ich mir einen Ordner “C:\Install” angelegt.

Dann startet ihr im Unterordner “C:\Install\HPC Pack 2008 R2 CTP\HPCPack\setup” die MSI-Installation “ cpp_x64.msi mit [Rechsklick –> Install]. Den Installations-Dialogen folgend wird darauf das HPC Pack wieder deinstalliert.

Dieser Schritt ist nötig, um eine Neuinstallation zu beginnen. Dies tun wir mit der setup.exe im übergeordneten Ordner.

Bei der Installation wählt ihr “Join an existing HPC cluster by creating a new compute node”.

Danach gebt ihr noch den hostname eurer Head-Node ein. In meinem Fall ist dies “MSHPC”.

Die Client Tools habe ich ebenfalls mit installiert.

Je nach gewählter Topologie kann man sich entscheiden, Microsoft Update zu nutzen. In meinem Fall hab ich es deaktiviert, weil das Cluster-Netzwerk von der Außenwelt getrennt ist.

Nun kann die Node wieder online geschaltet werden, und siehe da, alle Tests sollten erfolgreich verlaufen.

Gestern habe ich mich mal an den neuen Windows HPC Server 2008 R2 als CTP Version herangewagt.

Dafür hergehalten hat ein kleiner Test-Cluster, den ich von meiner Uni dafür bereitgestellt bekommen habe.

Es handelt sich dabei um 3 Supermicro Nodes, mit jeweils 2x2 Cores (Amd Opteron) Prozessoren.

Die Headnode verfügt über 32GB Ram, die Compute-Nodes jeweils 8.

Zur Zeit habe ich also nur 2 Compute-Nodes, es können aber ohne Probleme weitere nachgezogen werden.

Im Rahmen meiner Seminararbeit werde ich einen Block-orientierten Gauss-Algorithmus mit MPI/MPI.NET entwickeln, einmal in C und einmal in C#, und die Performance-Unterschiede auf Linux, Windows, Managed und Unmanaged miteinander vergleichen.

Auf was für Hürden ich eventuell mit der CTP des Windows HPC Server 2008 R2 treffe, werde ich euch in der nächsten Zeit hier in meinem Blog mal berichten.