Partitioners in ParallelFX


As you already know the parallel processing on multicore processors will be supported on the next version of .NET Framework. The .NET Framework 4.0 and Visual Studio 2010 will be release in spring of this year. In this post I am going to talk about Partitiones in ParallelFX.
Partition of data source play important role in parallel data processing. PLINQ and TLP have built-in partition concept which in certain situation and advanced scenarios, does not produce efficient results.
Two main kinds of partitioning existing in ParallelFX.

Range partitioning: When we talk about collections of data such as lists or arrays with known length, range partitioning is a commonly used and the simplest way of partitioning. Each thread receives a certain amount of data from the initial to the final index and there is no possibility that two or more threads access the same information in the list. The only overhead involved in range partitioning is the initial work of creating the ranges; no additional synchronization is required after that. This partitioning method is very efficient when we have constant workload by all data in the list. Drawback of this partitioning is the situation when one thread is finish early, and cannot help other to finish their work.

Chunk partitioning: When we have collections with an unknown number of elements, such as LinkedList etc., the possibility of partitioning comes down to it that every thread takes a number of elements from the list – “chunk size” and processes them. When it completes, it  returns and take another  chunk. This implementation of partitioning is done in a way that no one thread can take  the same element in collection.  Chunk size is arbitrary and can be from 1 to several elements, all depends on the nature of the operation. The Chunk partitioner does incur the synchronization overhead each time the thread needs to get another chunk. The amount of synchronization incurred in these cases is inversely proportional to the size of the chunks.
The TPL partitioners support dynamic number of partitions, they are created on the fly when the parallel loop spawns a new task.

Partitioner Class
Partitioners Class provides common partitioning strategies for arrays, lists, and enumerables. It contains only one methods, and several overloaded versions, which are presented in below text.

public static class Partitioner
{
public static OrderablePartitioner Create(IEnumerable source);
public static OrderablePartitioner Create(IList list, bool loadBalance);
public static OrderablePartitioner> Create(int fromInclusive, int toExclusive);
public static OrderablePartitioner> Create(long fromInclusive, long toExclusive);
public static OrderablePartitioner Create(TSource[] array, bool loadBalance);
public static OrderablePartitioner> Create(int fromInclusive, int toExclusive, int rangeSize);
public static OrderablePartitioner> Create(long fromInclusive, long toExclusive, long rangeSize);
}

Demo

In this demo we will  show some of custom partitions implementations.Let’s assume that we have to count prime numbers below a 500 000. In this example we have a method for prime number check which is implemented below.


public bool IsPrime(long n)

{
    for (long i = 2; i * i < n; i++)
    {
        if (n % i == 0)
            return false;
        else
            return true;
    }
}

The method return true if n is prime, otherwise returns false. The interval for prime number checking is  [1,500 000],  so the code implementation is:


var src = Enumerable.Range(1, 500000).ToArray();

I Implementation is pure sequential, and it contains simple LINQ query as the following:

var count = (from p in src
where IsPrime(p)
select p).Count();

As we know this code will be executed on one core of multicore processors.

II Implementation is implementation of the standard PLINQ query similar as above:


var count = (from p in src.AsParallel()
                 where IsPrime(p)
                 select p).Count();

The differences of mentioned implementation is in AsParallel(), word in second implementation. III Implementation is implementation of custom partitioner with Partitioners class. We create partitioner with Create method, and ParallelFX does the rest.

var count2 = Partitioner.Create(src, true).AsParallel().
            Where(p => IsPrime(p)).
            Select(p => p).Count();

The test is created on Quad Core Intel processors, and the result is presented on the following picture. image

Summary

The new Partitioner class allows to define custom partitioner which can be in some situations more efficient than default partitioner in PLINQ. Use custom partitioner in PLINQ query when you try to process no constant operations for every element on data source.
Reference:
1. http://msdn.microsoft.com/en-us/library/dd460693(VS.100).aspx
2. http://blogs.msdn.com/pfxteam/

The New version of GPdotNET is coming soon


The new stable release of the GPdotNET will be built on .NET 4.0, so the .NET 3.5 will not be supported at all. The reason for that is the compatibility with ParallelFX. From .NET 4.0 ParallelFX is integral part of the .NET 4.0 System namespace.

Some of the new feature:

1. Localization –The application will be localized on English and Bosnian language.

2. Improvements of the selection engine. Current 4 selections (Elite, Rank, Roulette-Wheel and Tournament) are optimized and rewritten.

a. There are 3 new selections:

i. Stochastic Uniform selection SUS
ii. Fitness Uniform Selection Scheme FUSS
iii. Skrgic Selection Scheme SSS

3. Parallel processing is also optimized but it is still not complete.

4. Fitness measure is expanded to over 15 types (similar to GeneExproTools 4.0):

  1. Absolute Error with Selection Range
  2. Absolute/Hits
  3. MSE (mean squared error)
  4. RMSE (root mean squared error)
  5. MAE (mean absolute error)
  6. RSE (relative squared error)
  7. RRSE (root relative squared error)
  8. RAE (relative absolute error)
  9. Relative Error with Selection Range
  10. Relative/Hits
  11. rMSE (relative MSE)
  12. rRMSE (relative RMSE)
  13. rMAE (relative MAE)
  14. rRSE (relative RSE)
  15. rRRSE (relative RRSE)
  16. rRAE (relative RAE)
  17. R-square
  18. Correlation Coefficient

5. Export results to Excel for further analysis

Screenshots:

clip_image002

Figure 1 Dialog for creating a model 1. Data model, 2. Time series model

clip_image004

Figure 2 Excel definition of the function, for Excel result export

clip_image006

Figure 3: 7 Selection methods

clip_image008

Figure 4: Over 15 Fitness type of measures

clip_image010

Figure 5: Export Options

Visual Studio 2010 i C# 4.0 IV DIO: Parallelfx i rješavanje sistema linearnih jednačina


Najznačajnija novina u VS 2010 po mom mišljenju je ParallelFx biblioteka za paralelno programiranje koja iskorištava višejezgrene procesore. O ovoj novini pisao sam na nekoliko postova:
  1. ParallelFx nova generacija konkurentnog programiranja
  2. ParallelFx II dio-PLINQ
  3. Izračunavanje broja PI i implementacija prekoParallelFx
U ovom dijelu biće prezentirana primjena ParallelFx na rješavanje sistema linearnih jednačina. Više detalja oko same biblioteke možete pronaći na gornjim linkovima.
Uvod

Jako puno inženjerskih problema pri procesu rješavanja svodimo na rješavanje sistema linearnih jednačina, koje onda rješavamo jednom od standardnih matematičkih metoda. Rješavanje sistema linearnih jednačina zahtjeva znatno procesorsko vrijeme kao i znatnu količinu memorije za pohranjivanje. Kada rješavamo sisteme sa većim brojem nepoznatih 100, 1000, 10000 i više, vrijeme izvršavanja klasičnim metodama i algoritmima se smanjivalo se kako su se procesori razvijal. Obzirom da se takt procesora više ne može povećavati, a daljnje proširenje svodi se na višejezgrene procesore, naši algoritmi za rješavanje ostali su na istom nivou. Naime, svi ti algoritmi bazirani su na sekvencijalno načinu izvršavanja koda pa višejezgreni procesori nemaju efekta u rješavanju. Pojavom više jezgrenih procesora šire su se počeli razvijati algoritmi za paralelno procesuiranje, a tako i paralelni algoritmi za rješavanje sistema jednačina kao i drugih algoritama koji zahtjevaju značajno procesorsko vrijeme. Paralelni algoritmi za rješavanje određenih inženjerskih procesa pojavili su se početkom 90-tih godina i s njima su se koristile samo velike kompanije poput NASA-e i sličnih, a koji su imali znatne materijalne i financijske resurse. U tu svrhu povezivali su se hiljade procesora koji su onda paralelno izvršavali dijelove koda, a na kraju su se sublimirali i davali rješenja. Tada još nisu bili poznati višejezgreni procesori poput današnjih pa su se procesori povezivali klasično gdje su zauzimali znatno prostora.

servers

Slika 1. 1000-Pentium Beowulf-Style Cluster Computer (www.genetic-programming.org/)

Npr. John Koza tvorac genetskog programiranja, povezao je 1000 procesora gdje je vršio svoja ispitivanja i proračune sa paralelnim algoritmom genetskog programiranja (O genetskom programiranju već sam pisao ). Pojavom višejezgrenih procesora paralelno programiranje postalo je dostupno i običnim „smrtnicima“ a samim tim i šira upotreba paralelnog načina programiranja.

Gaussova metoda eliminacije

Jedna od najpopularnijih metoda rješavanja sistema linearnih jednačina je Gaussova metoda koja koristi princip eliminacije kojom se u konačnom broju iteracija na kraju dobija jedno rješenje, od kojeg se u povratnom smjeru dolazi do drugih rješenja. Linearni sistema od clip_image006 jednačina sa clip_image006[1] nepoznatih clip_image008 je skup jednačina clip_image010 slijedeće matrične forme:

clip_image012

clip_image014

clip_image016

Gdje su clip_image018i clip_image020 realni brojevi članovi matrice. Sistem zovemo homogenim ako su svi članovi matrice kolone slobodnih članova clip_image020[1] jednaki nuli; inače sistema zovemo nehomogeni. Korištenjem matrica i njihovih operacija, jednačine clip_image010[1] možemo posmatrati kao matrični jednačinu:

clip_image022

Gdje je matrica clip_image024 clip_image026 matrica

clip_image028,

dok su matrice kolona nepoznatih označavamo sa clip_image030 , a matricu kolona slobodnih članova označavamo sa clip_image032. Formalni zapisi ovih matrica dati su sljedećim izrazima respektivno:

clip_image034 ,

clip_image036.

Proširena matrica sistema clip_image038 je matrica reda clip_image040 koju definišemo kao:

clip_image042

Rješenje sistema linearnih jednačina je skup brojeva clip_image044 koji zadovoljavaju svih clip_image006[2] jednačina, a vektor rješenja sistema linearnih jednačina clip_image046 je vektor koji zadovoljava matričnu jednačinu. Način na koji se rješavaju sistemi linearnih jednačina Gaussovim sistemom eliminacije možete pogledati iz referenci koje su stavljene na kraju ovog članka. Da bi implementirali algoritma za rješavanje sistema linearnih jednačina potrebno je poznavati ovu metodu, te imati na umu procesorsko vrijeme i memoriju koju će algoritam zauzimati.

Algoritam Gausove metode eliminacije

Način na koji rješavamo sisteme jednačina „pješice“ najbolji je način kako da započnemo implementaciju algoritma. Za informaciju, na internetu postoje hiljade stranica na kojima se mogu naći algoritmi za rješavanje sistema linearnih jednačina u raznim programskim jezicima. S toga ova implementacija koja je data nije ništa revolucionarno.

Algoritam Gauss clip_image048 – proširena matrica sistema

ULAZ : Proširena matrica sistema koja definiše clip_image050 članova clip_image052, gdje je clip_image054, a clip_image056– predstavlja broj nepoznati. 1.

Nakon učitavanja matrice sistema potrebno je izvršiti triangulaciju matrice, gdje je po definiciji zadnjih član takve matrice rješenje clip_image058. 2. Obrnutim postupkom uz poznavanje rješenja clip_image058[1] dolazimo do rješenje clip_image060, i tako do rješenja clip_image062

IZLAZ : Vektor rješenja  clip_image064.gif. Izvorni kod ovog algoritma dat je u nastavku:

//Gaussova metoda eliminacije
for (int k = 0; k <= brKol - 2; k++)
 {
  // Prvo potrazimo najveci koeficijent u kolonama kao Pivot, zbog preciznosti rezultata
  double pivot = matSistema[k][k];
  for (int i = k + 1; i <= brVrsta - 1; i++)
   {
    if (pivot < Math.Abs(matSistema[i][k]))
    {
      double[] temp = matSistema[k];
      matSistema[k] = matSistema[i];
      matSistema[i] = temp;
    }
  }
 // Triangulacija
 for (int j = k + 1; j <= brVrsta - 1; j++)
  {
    m[j][k] = matSistema[j][k] / matSistema[k][k];
    for (int p = k; p <= brKol - 1; p++)
    {
      matSistema[j][p] = matSistema[j][p] - m[j][k] * matSistema[k][p];
    }
  }
 }
//
double[] rjesenje = new double[brKol - 1];
rjesenje[brKol - 2] = matSistema[brVrsta - 1][brKol - 1] / matSistema[brVrsta - 1][brKol - 2];
 for (int i = brVrsta - 2; i >= 0; i--)
 {
   double sum = 0.0;
   for (int j = brKol - 2; j >= i + 1; j--)
    {
      sum = sum + matSistema[i][j] * rjesenje[j];
    }
   rjesenje[i] = (1 / matSistema[i][i]) * (matSistema[i][brKol - 1] - sum);
 }
return rjesenje;

Kada smo implementirali algoritam za rješavanje sistema linearnih jednačina potrebno je sada analizirati kod i vidjeti gdje bi se mogla izvršiti paralelizacija da bi naš algoritam bio brzi od konvencionalnog odnosno da bi mogao iskorištavati današnja višejezgrene procesore. Prije nego se upustimo u analizu koda potrebno je pretpostaviti da će naš algoritam rješavati više od 500 jednačina odnosno tražiti više od 500 nepoznati. Ako bi algoritam rješavao manje jednačina paralelizacija ne bi imala smisla jer se vrijeme izvršavanja sekvencijalnog koda bilo brže od paralelnog. Ako pogledamo gornju implementaciju mjesta gdje bi paralelizirali kod je samo na dijelovima pri triangulaciji matrice i izračunavanju rješenja. Na ova dva mjesta imamo ugnježdene petlje, a one u algoritmu troše najviše procesorskog vremena.

Kako algoritam počinje…

On uzima prvu kolonu i provjerava da li u danoj koloni prvi član po apsolutnoj vrijednosti je najveći član od svih desnih kolona. Ako to slučaj nije tada se traži kolona u kojoj je prvi član najveći i te dvije kolone zamjenjuju mjesta. To možemo slobodno uraditi zbog osobina matrica. Kada se normalizira kolona tada se vrši triangulacija odnosno za svaku vrstu ispod posmatrane elementi kolone moraju biti nule (Gaussov postupak eliminacije). U ovom koraku se koriste dvije ugnježdene petlje (crveno obojen kod) kojim se ovo ostvaruje. Ovaj dio kod je najpogodniji za paralelnu implementaciju. Razlog zašto se ne ide na paralelnu implementacije prve petlje je taj što se mora ispoštovati poredak kolona, a u paralelnoj implementaciji to ne možemo postići jednostavno. Drugi dio koda pri kojem se na osnovu triangulacije matrice izračunavaju rješenja također koristi dvije ugnježdene petlje, a samim tim i dio koda koji bi mogao biti kandidat za paralelnu implementaciju. Ovaj dio koda također se mora izvršavati u striktno definisanom redu tj. prvo se izračunava zadnja vrsta, pa predzadnja i td. do prve vrste. Kada bi ovaj dio koda bio implementiran paralelno narušili bi poredak, a tako i rješenja ne bi bila izračunata tačno. Na osnovu analize paralelna implementacija kod izgleda na sljedeći način:

//Gaussova metoda eliminacije
for (int k = 0; k <= brKol - 2; k++)
{
  // Prvo potrazimo najveci koeficijent u kolonama kao Pivot, zbog preciznosti rezultata
  double pivot = matSistema[k][k];
  for (int i = k + 1; i <= brVrsta - 1; i++)
  {
    if (pivot < Math.Abs(matSistema[i][k]))
     {   double[] temp = matSistema[k];
       matSistema[k] = matSistema[i];
       matSistema[i] = temp;
     }
  }
 // Triangulacija
 Parallel.For(k + 1, brVrsta, j =>
 {
   m[j][k] = matSistema[j][k] / matSistema[k][k];
   for (int p = k; p <= brKol - 1; p++)
   {
     matSistema[j][p] = matSistema[j][p] - m[j][k] * matSistema[k][p];
   }
 }
             );
}
//
double[] rjesenje = new double[brKol - 1];
rjesenje[brKol - 2] = matSistema[brVrsta - 1][brKol - 1] / matSistema[brVrsta - 1][brKol - 2];
for (int i = brVrsta - 2; i >= 0; i--)
 {
   double sum = 0.0;
   for (int j = brKol - 2; j >= i + 1; j--)
    {
      sum = sum + matSistema[i][j] * rjesenje[j];
    }
   rjesenje[i] = (1 / matSistema[i][i]) * (matSistema[i][brKol - 1] - sum);
 }
 return rjesenje;

Vidimo da paralelna verzija algoritma se nije puno promijenila a što Parallelfx čini vrlo efikasnom bibliotekom.

Testiranje sekvencijalnog i paralelnog algoritma

Sada kada smo implementirali algoritam potrebno ga je i testirati na višejezgrenim PC mašinama da bi smo se uvjerili da naš paralelni algoritam brže radi od sekvencijalog. U tu svrhu generirano je 5 csv datoteka u kojim stoje proširene matrice sistema od 10, 50, 100, 500 i 1000 nepoznatih, kojim ćemo izvršiti testiranje algoritma. Sistemi su jednostavni čija su rješenja sve jedinice. Test aplikacija je koncipirana tako da učitava sisteme jednačina iz csv datoteka rješava sisteme koristeći sekvencijalni i paralelni algoritam te na konzolu izbacuje vremena koja su potrošena pri rješavanju. Test koji je prezentiran ovdje rađen je na Intel Core 2 Quad CPU Q6600 2,4 GZ:

CoreQuad

Rezultat testa je sljedeći:

restest

Iz testa možemo primijetiti da sistemi preko 100 nepoznati daju bolje rezultate kod paralelne implementacije i možemo smatrati okvirno da je to neka granica preko koje bi trebali koristiti paralelnu implementaciju algoritma. Kako broj nepoznatih raste tako raste razlika između paralelne i sekvencijalne implementacije algoritma. Kompletan izvorni kod algoritma i testa može se skinuti sa ovog linka. Projekt je rađen u Visual Studiu 2010 beta 1koji se može skinuti sa ovog linka.

Reference

  1. http://blogs.msdn.com/pfxteam/
  2. Ćamila Ljubović, Matematika, IPSvjetlost Sarajevo 1997
  3. http://geeks.netindonesia.net/blogs/norman