Лабораторная работа №1 по дисциплине "Параллельное программирование"

Практически в каждой MPI-функции  одним из параметров является коммуникатор (идентификатор группы процессов); в момент инициализации библиотеки MPI создается коммуникатор MPI_COMM_WORLD и в его пределах процессы нумеруются линейно от 0 до size. Однако с помощью коммуникатора для процессов можно определить и другие системы нумерации (пользовательские топологии).

 

4. В чем  механизм блокирующей посылки  сообщения? Какие MPI-функции осуществляют блокирующие посылки?

 

Функция MPI_Send осуществляет блокирующую посылку сообщения с идентификатором msgtag процессу с номером dest; причем сообщение состоит из count элементов типа datatype (все элементы сообщения расположены подряд в буфере buf, значение count может быть и нулем). Тип передаваемых элементов datatype должен указываться с помощью предопределенных констант типа, разрешается передавать сообщение самому себе. При пересылке сообщений можно использовать специальное значение MPI_PROC_NULL для несуществующего процесса; операции с таким процессом немедленно успешно завершаются (код завершения MPI_SUCCESS).

 

5. Что такое передача сообщений с буферизацией? Какие MPI-функции осуществляют буфферизованные посылки?

Передача сообщения с буферизацией - если прием посылаемого сообщения еще не был инициализирован процессом-получателем, то сообщение будет записано в специальный буфер, и произойдет немедленный возврат из процедуры. Выполнение этой процедуры никоим образом не зависит от соответствующего вызова процедуры приема сообщения. Тем не менее процедура может вернуть код ошибки, если места под буфер недостаточно (о выделении массива для буферизации должен озаботиться пользователь).

MPI_Вsend - передача сообщения  с буферизацией. Если прием посылаемого сообщения еще не был инициализирован процессом-получателем, то сообщение будет записано в специальный буфер, и произойдет немедленный возврат из процедуры. Выполнение этой процедуры никоим образом не зависит от соответствующего вызова процедуры приема сообщения. Тем не менее процедура может вернуть код ошибки, если места под буфер недостаточно (о выделении массива для буферизации должен озаботиться пользователь).

 

6. В чем  заключается механизм 'джокеров' и  каковы его преимущества? Какие проблемы могут возникнуть при использовании 'джокеров'?

Удобно сортировать сообщения  с помощью механизма ‘джокеров’; в этом случае вместо явного указания номера задачи-отправителя используется ‘джокер’ MPI_ANY_SOURCE (‘принимай от кого угодно’) и MPI_ANY_TAG вместо идентификатора получаемого сообщения (‘принимай что угодно’). Достоинство ‘джокеров’ в том, что приходящие сообщения извлекаются по мере поступления, а не по мере вызова MPI_Recv с нужными идентификаторами задач и/или сообщений (что экономит память и увеличивает скорость работы).

Пользоваться ‘джокерами’ рекомендуется  с осторожностью, т.к. возможна ошибка в приеме сообщения ‘не того’  или ‘не от того’.

 

7. Что такое взаимная  блокировка (тупиковая ситуация, 'deadlock', 'клинч')? В каких условиях это  явление возникает?

При обмене данными в некоторых  случаях возможны вызванные взаимной блокировкой т.н. тупиковые ситуации (используются также термины ‘deadlock’, ‘клинч’); в этом случае функции посылки и приема данных мешают друг другу и обмен не может состояться. Ниже рассмотрена deadlock-ситуация при использовании для пересылок разделяемой памяти.

Вариант 1. Ветвь 1 : Recv ( из ветви 2 ) Send ( в ветвь 2 )

Ветвь 2 : Recv ( из ветви 1 ) Send ( в ветвь 1 )

 

Вариант 1 приведет к deadlock’у при любом  используемом инструментарии, т.к. функция  приема не вернет управления до тех  пор, пока не получит данные; из-за этого  функция передачи не может приступить к отправке данных, поэтому функция приема не вернет управление... и т.д. до бесконечности.

Вариант 2. Ветвь 1 : Send ( в ветвь 2 ) Recv ( из ветви 2 )

Ветвь 2 : Send ( в ветвь 1 ) Recv ( из ветви 1 )

Федеральное агентство  по образованию

Московский государственный открытый университет

Чебоксарский политехнический  институт

 

 

Кафедра

Информационных технологий и программирования

 

 

 

                                специальность         230105    ___

 (шифр специальности)

 

 

 

 

 

 

 

 

 

Лабораторная работа №4

по дисциплине: параллельное программирование

 

 

 

Дата проверки      Выполнили студенты                 

                                                                                   Дьяконов В.Н.

Сорокин Д.В.                        

Результат проверки     Учебный шифр

609264

609244

Курс 4

 

Проверил       Малов А.А.

 

Замечания

 

 

 

Чебоксары, 2012 г.

 

 

 

 

 

 

 

 

Лабораторная работа №4

 

Цель работы: приобретение практических знаний и навыков в  разработке несложных MPI-программ, анализе точности вычисляемых значений.

 

Выполнение  работы:

 

Листинг программы 1 части:

 

// source code PI_01.C program

#include “mpi.h” 

#include <stdio.h>

#include <math.h>

#include <sys/timeb.h> // for ftime

double f_time(void); /* define real time by ftime function  */

#include “f_time.c” 

 

double compute_interval (int myrank, int ntasks, long intervals);

 

int main(int argc, char ** argv) 

{

 long intervals=100; // number of integration’s parts

 int i, myrank,ranksize;

 double pi, di, send[2], recv[2],

        t1,t2, t3,t4, t5,t6,t7, // time’s moments

             pi_prec=4.0*(atanl(1.0)-atan(0.0)); // pi precision

 MPI_Status status;

t1=f_time();    

 MPI_Init (&argc, &argv);  /* initialize MPI-system */

 t2=f_time();

 MPI_Comm_rank (MPI_COMM_WORLD, &myrank); /* my place in MPI system */

 MPI_Comm_size (MPI_COMM_WORLD, &ranksize);  /* size of MPI system */

 

 if (myrank == 0)  /* I am the MASTER */

 {

 intervals = atoi( argv[1] ); /* get interval’s count from command line */

 printf (“Calculation of PI by numerical integration with %ld intervals\n”, intervals);

 }

 

 MPI_Barrier(MPI_COMM_WORLD); /* make sure all MPI tasks are running */

 

 if (myrank == 0) /* I am the MASTER */

 {  /* distribute parameter */

 printf (“Master: Sending # of intervals to MPI-Processes \n”);

 t3 = MPI_Wtime();

 for (i=1; i<ranksize; i++)  

  MPI_Send (&intervals, 1, MPI_LONG, i, 98, MPI_COMM_WORLD);

 } /* end work MASTER */

 else  /* I am a SLAVE */

 { /* receive parameters */

 MPI_Recv (&intervals, 1, MPI_LONG, 0, 98, MPI_COMM_WORLD, &status);

 } // end work SLAVE

 

 /* compute my portion of interval */

 t4 = MPI_Wtime();

 pi = compute_interval (myrank, ranksize, intervals); /*=======================*/

 t5 = MPI_Wtime();

 MPI_Barrier (MPI_COMM_WORLD); /* make sure all MPI tasks are running */

 t6 = MPI_Wtime();

 

 if (myrank == 0) /* I am the MASTER */

{  /* collect results add up & printing results */

 for (i=1; i<ranksize; i++)

 {

  MPI_Recv (&di, 1, MPI_DOUBLE, i, 99, MPI_COMM_WORLD, &status);

  pi += di;

 } /* end of collect results */

 t7 = MPI_Wtime();

 printf (“Master: Has collected sum from MPI-Processes \n”);

 printf (“\nPi estimation: %.12lf (rel.error= %.5f %%)\n”, 

           pi, 1.0e2*(pi_prec-pi)/pi_prec);

 printf (“%ld tasks used,  execution time: %.3lf sec\n”,ranksize, t7 –t3);

 printf(“\nStatistics:\n”);

 printf(“Master: startup: %.0lf msec\n”,t2-t1);

 printf(“Master: time to send # of intervals:%.3lf sec\n”,t4-t3);

 printf(“Master: waiting time for sincro after calculation:%.2lf sec\n”,t6-t5);

 printf(“Master: time to collect: %.3lf sec\n”,t7-t6);

 printf(“Master: calculation time:%.3lf sec\n”,t5-t4);

MPI_Barrier (MPI_COMM_WORLD); /* make sure all MPI tasks are running */

  for (i=1; i<ranksize; i++)

 {  /* collect there calculation time */

 MPI_Recv(recv, 2, MPI_DOUBLE, i, 100, MPI_COMM_WORLD, &status);

 printf(“process %d: calculation time: %.3lf sec,\twaiting time for sincro.: %.3lf sec\n”,        

           i,recv[0],recv[1]);

 } // end of collection

} // end work MASTER

 

 else /* I am a SLAVE */

{ /* send my result back to master */

 MPI_Send (&pi, 1, MPI_DOUBLE, 0, 99, MPI_COMM_WORLD);

 MPI_Barrier (MPI_COMM_WORLD); /* make sure all MPI tasks are running */

 send[0]=t5-t4;

 send[1]=t6-t5;

 MPI_Send (send, 2, MPI_DOUBLE, 0, 100, MPI_COMM_WORLD);

} // end work SLAVE

 

 MPI_Finalize ();

} // end MAIN function

 

/* ============================================================== */

double compute_interval (int myrank, int ntasks, long intervals) 

{ /* calculate integral’s localsum */

 double x, width, localsum=0.0;

 long j;

 width = 1.0 / intervals; /* width of single stripe */

 for (j=myrank; j<intervals; j+= ntasks)

 {

  x = (j + 0.5) * width;

  localsum += 4 / (1 + x*x);

 }

 return (localsum * width); /* area of stripe */

} // end of COMPUTE_INTERVAL function

// end of PI_01.C program

 

 

f_time содержится в файле  F_TIME.C (подключается посредством 

Функция

#include “f_time.c”):

 

double f_time() /* return time since 01 jan 1970 as double ‘sec, msec’ */

{

 struct timeb tp;

 ftime(&tp);

 return ((double)(tp.time)+1.0e-3*(double)(tp.millitm));

} // end f_time function

 

 

 

 

Результат программы:

 

/ source code PI_SER.C program

#include <stdio.h>

#include <math.h>

 #include <sys/timeb.h> // for ftime

double f_time(void); /* define real time by ftime function  */

 void srandom (unsigned seed);  

long random(void);

double dboard (int darts);

#include “dboard.c” // including dboard.c file

#include “f_time.c”  // including f_time.c file

 #define DARTS    10000  /* number of throws at dartboard */

#define ROUNDS 100     /* number of times “darts” is iterated */

 int main(int argc, char *argv[])

{

double pi,         /* average of pi after ‘darts’ is thrown */

            avepi,   /* average pi value for all iterations */

            t1, t2, // time’s moments

            pi_prec=4.0*(atanl(1.0)-atan(0.0)); // pi precision

int i, n;

 

t1=f_time(); // fix start time calculated

 

srandom (5); // init of random generator

avepi = 0;

for (i=0; i<ROUNDS; i++) // rounds times call dboard function

{

 pi = dboard(DARTS);

 avepi = ((avepi * i) + pi)/(i + 1); 

 t2=f_time(); // fix end time calculated

 printf(“%7d throws aver.value of PI= %.12lf (rel.error= %.5lf %%, time= %.3lf sec)\n”,  

         (DARTS * (i+1)), avepi, 1.0e2*(pi_prec-avepi)/pi_prec, t2-t1);

} // end for (i=0; i<ROUNDS; i++)  

} // end of MAIN function

// end of PI_SER.C program

 

Текст функции DBOARD (подключается посредством #include “dboard.c”):

 

double dboard(int darts)

{

double x_coord,    /* x coordinate, between –1 and 1  */

            y_coord,    /* y coordinate, between –1 and 1  */

            pi,              /* pi  */

            r;                /* random number between 0 and 1  */

int score,   /* number of darts that hit circle */

           n;

unsigned long cconst; 

 

cconst = 2 << (31 – 1); /* used to convert integer random number                                         

                               between 0 and 2^31 to double random number between 0 and 1 */

score = 0; // start as

 

for (n=1; n<=darts; n++)  // cicles at random 2D-points

{

 r = (double)random() / cconst;

 x_coord = (2.0 * r) – 1.0; // x-coord of 2D-point

 r = (double)random() / cconst;

 y_coord = (2.0 * r) – 1.0; // y-coord of 2D-point

 if (((x_coord*x_coord) + (y_coord*y_coord)) <= 1.0) // 2D-point in circle?

   Score++;

} // end for (n=1; n<=darts; n++)

 pi = 4.0 * (double)score / (double)darts;

 return(pi);

} // end of dboard function

 

Листинг программы 2 части:

 

// source code PI_SER.C program

#include <stdio.h>

#include <math.h>

 #include <sys/timeb.h> // for ftime

double f_time(void); /* define real time by ftime function  */

 void srandom (unsigned seed);  

long random(void);

double dboard (int darts);

#include “dboard.c” // including dboard.c file

#include “f_time.c”  // including f_time.c file

 #define DARTS    10000  /* number of throws at dartboard */

#define ROUNDS 100     /* number of times “darts” is iterated */

 int main(int argc, char *argv[])

{

double pi,         /* average of pi after ‘darts’ is thrown */

            avepi,   /* average pi value for all iterations */

            t1, t2, // time’s moments

            pi_prec=4.0*(atanl(1.0)-atan(0.0)); // pi precision

int i, n;

 

t1=f_time(); // fix start time calculated

 

srandom (5); // init of random generator

avepi = 0;

for (i=0; i<ROUNDS; i++) // rounds times call dboard function

{

 pi = dboard(DARTS);

 avepi = ((avepi * i) + pi)/(i + 1); 

 t2=f_time(); // fix end time calculated

 printf(“%7d throws aver.value of PI= %.12lf (rel.error= %.5lf %%, time= %.3lf sec)\n”,  

         (DARTS * (i+1)), avepi, 1.0e2*(pi_prec-avepi)/pi_prec, t2-t1);

} // end for (i=0; i<ROUNDS; i++)  

} // end of MAIN function

// end of PI_SER.C program

Текст функции DBOARD (подключается посредством #include “dboard.c”):

 

double dboard(int darts)

{

double x_coord,    /* x coordinate, between –1 and 1  */

            y_coord,    /* y coordinate, between –1 and 1  */

            pi,              /* pi  */

            r;                /* random number between 0 and 1  */

int score,   /* number of darts that hit circle */

           n;

unsigned long cconst; 

 

cconst = 2 << (31 – 1); /* used to convert integer random number                                         

                               between 0 and 2^31 to double random number between 0 and 1 */

score = 0; // start as

 

for (n=1; n<=darts; n++)  // cicles at random 2D-points

{

 r = (double)random() / cconst;

 x_coord = (2.0 * r) – 1.0; // x-coord of 2D-point

 r = (double)random() / cconst;

 y_coord = (2.0 * r) – 1.0; // y-coord of 2D-point

 if (((x_coord*x_coord) + (y_coord*y_coord)) <= 1.0) // 2D-point in circle?

  Score++;

} // end for (n=1; n<=darts; n++)

 pi = 4.0 * (double)score / (double)darts;

 return(pi);

} // end of dboard function

 

// source code PI_02.C program

#include “mpi.h” 

#include <stdlib.h>

#include <stdio.h>

#include <math.h>

 

#define DARTS    10000  /* number of throws at dartboard */

#define ROUNDS 100     /* number of times ‘darts’ is iterated */

#define MASTER   0       /* task ID of master task */

 

void srandom (unsigned seed);  

double dboard (int darts);

#include “dboard.c” // including dboard.c file

 

int main(int argc, char *argv[])

{

double homepi,   /* value of pi calculated by current task */

  pi,             /* average of pi after ‘darts’ is thrown */

  avepi,       /* average pi value for all iterations */

  pirecv,      /* pi received from worker */

  pisum,      /* sum of workers PI values */

           t1, t2, // time’s moments

           pi_prec=4.0*(atanl(1.0)-atan(0.0)); // pi precision

int  taskid,       /* task ID – also used as seed number */

  numtasks, /* number of tasks */

  source,      /* source of incoming message */ 

  rc,             /* MPI’s return code */

 i, n;

MPI_Status status;

 rc = MPI_Init(&argc,&argv);

rc = MPI_Comm_size(MPI_COMM_WORLD,&numtasks);

rc = MPI_Comm_rank(MPI_COMM_WORLD,&taskid);

  t1=MPI_Wtime(); // store start time calculated

 srandom (taskid); // initialization random number generator by taskid value

 avepi = 0;

for (i=0; i<ROUNDS; i++)

{

 homepi = dboard(DARTS); // all tasks calculate pi by dartboard algorithm 

 

if (taskid != MASTER) // It’s NOT MASTER!

{

 rc = MPI_Send(&homepi, 1, MPI_DOUBLE, MASTER, i, MPI_COMM_WORLD);

 if (rc != MPI_SUCCESS) // if error MPI_Send function

  printf(“%d: Send failure on round %d\n”, taskid, i);

} 

else // I am MASTER

{

 pisum = 0;

 for (n=1; n<numtasks; n++)

 {

  rc = MPI_Recv(&pirecv, 1, MPI_DOUBLE, MPI_ANY_SOURCE, i, 

                           MPI_COMM_WORLD, &status);

  if (rc != MPI_SUCCESS) // if error MPI_Recv function

    printf(“%d: Receive failure on round %d\n”, taskid, i);

  pisum = pisum + pirecv;

 }

/* Master calculates the average value of pi for this iteration */

 pi = (pisum + homepi)/numtasks;

/* Master calculates the average value of pi over all iterations */

 avepi = ((avepi * i) + pi) / (i + 1); 

 t2=MPI_Wtime(); // fix end time calculated

 printf(“%9d throws aver.value of PI= %.12lf (rel.error= %.5lf %%, time= %.3lf sec)\n”,  

         (DARTS * (i+1)), avepi, 1.0e2*(pi_prec-avepi)/pi_prec, t2-t1);

  }    

} // end for (i=0; i<ROUNDS; i++)

 MPI_Finalize();

 return 0;