› › › Paralel Programlama V (Parallel Programming V)

Paralel Programlama V (Parallel Programming V)

watch_later 4/10/2016
comment Add Comment
Ölümcül Kilitlenme (Deadlock)
İki  ya da daha fazla süreç bloke edildiğinde kilitlenme oluşur ve her makine ilerleme sağlamak için birbirini bekler. Aşağıdaki kod bloğunda, 0 ve 1 makineleri deadlock nedeniyle işlemler tamamlanmayacak ve çalıştırma başarısız olacaktır.

 

#include "mpi.h"
#include 
#include 

using namespace std;


int main(int argc, char* argv[])
{
    int myRank,
        size;

    double a[100],
           b[100];

    MPI_Status status;

    /* Initialize MPI */
    MPI_Init(&argc, &argv);

    /* Determine the size of the group */
    MPI_Comm_size(MPI_COMM_WORLD,&size);

    /* Determine the rank of the calling process */
    MPI_Comm_rank(MPI_COMM_WORLD,&myRank);

    if(size != 2)
    {
        printf("Number of CPUs must be 2 !\n");
        MPI_Abort(MPI_COMM_WORLD, 99);
    }

    if(myRank == 0)
    {
        /* Receive a message then send one */
        MPI_Recv(b, 100, MPI_DOUBLE, 1, 10, MPI_COMM_WORLD, &status);
        printf("Rank %d received the message.\n",myRank);

        MPI_Send(a, 100, MPI_DOUBLE, 1, 0, MPI_COMM_WORLD);
        printf("Rank %d sent the message.\n",myRank);
    }
    else
    {
        /* Receive a message then send one */
        MPI_Recv(b, 100, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD, &status);
        printf("Rank %d received the message.\n",myRank);

        MPI_Send(a, 100, MPI_DOUBLE, 0, 10, MPI_COMM_WORLD );
        printf("Rank %d sent the message.\n",myRank);
    }

    /* Terminate MPI */
    MPI_Finalize();

    return 0;
}
Ölümcül Kilitlenmeden Kaçınma (Avoiding Deadlock) 
İletişim daha iyi organize hale getirilirse programda deadlock oluşmaz. Master mesajı send ile gönderir, slave mesajı masterdan recv ile alır. Aynı şekilde slave mesajı send ile gönderir, master mesajı recv ile alır. 
#include "mpi.h"
#include 
#include 
using namespace std;


int main(int argc, char* argv[])
{
    int myRank,
        size;

    double a[100],
           b[100];

    MPI_Status status;

    /* Initialize MPI */
    MPI_Init(&argc, &argv);

    /* Determine the size of the group */
    MPI_Comm_size(MPI_COMM_WORLD,&size);

    /* Determine the rank of the calling process */
    MPI_Comm_rank(MPI_COMM_WORLD,&myRank);

    if(size != 2)
    {
        printf("Number of CPUs must be 2 !\n");
        MPI_Abort(MPI_COMM_WORLD, 99);
    }

    if(myRank == 0)
    {
        MPI_Send(a, 100, MPI_DOUBLE, 1, 0, MPI_COMM_WORLD);
        printf("Rank %d sent the message.\n",myRank);

        /* Receive a message then send one */
        MPI_Recv(b, 100, MPI_DOUBLE, 1, 10, MPI_COMM_WORLD, &status);
        printf("Rank %d received the message.\n",myRank);
    }
    else
    {
        MPI_Recv(a, 100, MPI_DOUBLE, 0, 0, MPI_COMM_WORLD, &status);
        printf("Rank %d received the message.\n",myRank);

        /* Send a message then receive one */
        MPI_Send(b, 100, MPI_DOUBLE, 0, 10, MPI_COMM_WORLD );
        printf("Rank %d sent the message.\n",myRank);
    }

    /* Terminate MPI */
    MPI_Finalize();

    return 0;
}

Veri Dağıtımı (Data Distribution)
MPI ile veri paylaştırma  işlemi yük dengeleme için önemlidir. Yük dengeleme işlemi içinde paralel çalıştırılacak programların makinelere belirli dağıtım kriterlerine göre dağıtım yapılması sağlanır. Bu dağıtım yöntemleri:

Bileşenlerin sayısı n ve süreçlerin sayısı comm_sz olarak varsayalım. local_n = n / comm_sz işlemi ile local_n değeri bulunur ve blok dağıtım (block distribution) ile her makine için local_n ardışık bileşenlerin blokları atanabilir. Halkalı dağıtım (cyclic distribution) ise Round Robin ile makinelere süreç dağıtma işlemine dayanır. Diğer bir dağıtım yöntemi ise blok - halkalı dağıtım (block - cyclic distribution) 'dır. Bu yöntem elemanların sıklık dağılımı ile belirli bir blok sayısına göre Round Robin ile makinelere atama yapılır. 
 
 
 
Egzersiz
Paralel olarak çalıştırmak istenen işlem sayısı n = 14 olmak üzere p = 4 işlemcide blok dağıtım işlemi nasıl yapılır?  
n = 4 işlemci, lenght(array) = 14 
14 = 3 x 4 + 2
r = 2, q = 3
r = 2        işlemciye      ceil(n/p) 4 eleman
p – r = 2      işlemciye      floor(n/p)  3 eleman 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
0
0
0
0
1
1
1
1
2
2
2
3
3
3


Egzersiz
Paralel olarak sıralanacak dizinin boyutu n = 14 olmak üzere p = 4 işlemcide halkalı dağıtım ile nasıl sıralanır? 
n = 4 işlemci, lenght(array) = 14

1
2
3
4
5
6
7
8
9
10
11
12
13
14
0
1
2
3
0
1
2
3
0
1
2
3
0
1


Egzersiz
Paralel olarak sıralanacak dizinin boyutu n = 14 olmak üzere p = 4 işlemcide blok boyutu = 2 iken blok ve halkalı (hibrit) dağıtım ile nasıl sıralanır? 
n = 4 işlemci, lenght(array) = 14

1
2
3
4
5
6
7
8
9
10
11
12
13
14
0
0
1
1
2
2
3
3
0
0
1
1
0
1


Dizi elemanlarını veri dağıtım yöntemleriyle toplayıp ve toplamı master makinede ekrana yazdıralım.

Blok Dağıtım (Block Distribution): 
#include 
#include 
using namespace std;
int main(intargc, char** argv)
{
    int i;int n = 1000;
    int a[n];
    int sum, ssum, id, size, start, end;
    
    MPI_Init(&argc,&argv);
    MPI_Comm_rank(MPI_COMM_WORLD,&id);
    MPI_Comm_size(MPI_COMM_WORLD,&size);
    para_range(1,n,size,id,start,end);
    
    for ( i = start; i <= end; i++ )
    {
      a[i-1] = i;
    }
    
    sum = 0;
    for ( i = start; i <= end; i++ )
    {
      sum = sum + a[i-1];
    }

    MPI_Reduce(&sum,&ssum,1,MPI_INTEGER,MPI_SUM,0,MPI_COMM_WORLD);
   
    sum = ssum;
    if ( id == 0 )
    {
       printf("Sum: %d\n",sum);
    }

    MPI_Finalize();
    return 0;
}
Halkalı Dağıtım (Cyclic Distribution):
#include 
#include 
using namespace std;
int main(int argc, char** argv)
{
    int n = 1000;int a[n];
    int i, sum, ssum, id, size, start, end;

    MPI_Init(&argc,&argv);
    MPI_Comm_rank(MPI_COMM_WORLD,&id);
    MPI_Comm_size(MPI_COMM_WORLD,&size);
    
    for ( i = 1 + id; i <= n; i = i + size)
    {
       a[i-1] = i;
    }
    
    sum = 0;
    for ( i = 1 + id; i <= n; i = i + size)
    {
       sum = sum+ a[i-1];
    }

    MPI_Reduce(&sum,&ssum,1,MPI_INTEGER,MPI_SUM,0,MPI_COMM_WORLD);
    
    sum = ssum;
    if ( id == 0 )
    {
      printf("Sum: %d\n",sum);
    }

    MPI_Finalize();
    
 return 0;
}
Blok ve Halkalı Dağıtım Simülasyonu









Bir sonraki yazımda görüşmek üzere...
Burak Tahtacıoğlu

comment 0 yorum:

more_vert



sentiment_satisfied Emoticon