Виконання формального аналiзу iнформацiйної незалежності операторiв, страница 2

	1	2	3	4	5	6	7	8
1	0	0	1	1	1	0	0	0
2	0	0	0	0	1	0	1	0
3	0	0	0	0	0	0	0	1
4	0	0	0	0	0	1	1	0
5	0	0	0	0	0	0	0	1
6	0	0	0	0	0	0	0	1
7	0	0	0	0	0	0	0	1
8	0	0	0	0	0	0	0	0

K	Ім’я	δ+(vi),	δ-(vi)	Вага,t	Ярус	τ1(к)	τ2т(к)
1	8	{5,3,4}	{0}	2	1	2	6
2	1	{4,7}	{0}	3	1	3	7
3	5	{2}	{8}	5	2	8	11
4	3	{6,7}	{8}	2	2	5	8
5	4	{2}	{1,8}	4	2	7	11
6	6	{2}	{3}	3	3	11	11
7	7	{2}	{3,4}	2	3	10	11
8	2	{0}	{4,5,6,7}	1	4	12	12

τ₁(1)=t₁=2

τ₁(2)=t₂=3

τ₁(3)=max{τ₁(1), τ₁(2)}+ t₃=max{2,3}+5=5+3=8

τ₁(4)=max{τ₁(1), τ₁(2)}+ t₄=max{2,3}+2=2+3=5

τ₁(5)=max{τ₁(1), τ₁(2)}+ t₅=max{2,3}+4=4+3=7

τ₁(6)=max{τ₁(3), τ₁(4), τ₁(5)}+ t₆=max{5,7,8}+3=8+3=11

τ₁(7)=max{τ₁(3), τ₁(4), τ₁(5)}+ t₇=max{5,7,8}+2=8+2=10

τ₁(8)= max{τ₁(6), τ₁(7)}+ t₈=max{10,11}+1=11+1=12=t_кр

τ₂^т(8)=t_кр=12

τ₂^т(7)= τ₂^т(8)-t₈=12-1=11

τ₂^т(6)= τ₂^т(8)-t₈=12-1=11

τ₂^т(5)= τ₂^т(8)-t₈=12-1=11

τ₂^т(4)= min{τ₂^т(7)-t₇, τ₂^т(6)-t₆}=min{11-3,11-2}=min{8,9}=8

τ₂^т(3)= τ₂^т(8)-t₈=12-1=11

τ₂^т(2)= min{τ₂^т(5)-t₄, τ₂^т(7)-t₆}=min{11-4,11-2}=min{7,9}=7

τ₂^т(1)= min{τ₂^т(3)-t₃, τ₂^т(4)-t₄, τ₂^т(5)-t₅}=min{11-5,8-2,11-4}=min{6,6,7}=6

ЗАДАЧА № 2  Отримавши діаграму розпаралелення Задачі №1, описати конфігурацію її виконання бібліотечними процедурами розширеного інтерфейсу передачі повідомлень MPI-2 (MPI-1.2), застосовуючи мову С++.

Створити логічну структуру розпаралеленої у першої частини РГЗ задачі.

          Кожен оператор представити текстами, які включають MPI- процедури, що приймають деякі умовні дані для даного оператору, процедуру затримки на заданий час виконання цього оператора і MPI- процедури передачі умовних даних іншим операторам паралельної задачі.

Рішення: Виконавши попередню задачу, ми отримали дві групи процесів, які паралельно виконуються.

Група №1                       Група №2

1 5 7 2                            8 3 4 6

0 1 2 3 - ранг                  4 5 6 7 - ранг

Якщо зобрати задачі, які виконуються паралельно до рангів, то отримаємо наступне:

  Ранг4         Ранг5           Ранг6                Ранг7

  Ранг0          Ранг1                   Ранг2             Ранг3

Процеси, які будуть описуватися в програмі, розроблені процедурами, що реалізують затримку на необхідну кількість одиниць часу, відносно до параметру, якій передається в процедуру.

          Затримка задається кількістю міжпроцесних та міжроцесорних переходів.

//Текст програми:

#include <mpi.h>

#include <stdio.h>

#include <math.h>

#include <mpio.h>

//Функція очікування

int wait(int len)

{

                    int startwtime, endwtime;

                    startwtime = (int)MPI_Wtime();

                    {

                                       endwtime = (int)MPI_Wtime();

                    }while ((endwtime-startwtime)<len*10);

return 0;

}

// Головнiй функ. передаемо параметри командн. строки

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

{

  int done=0, n, myid , numprocs, i; 

int Nproc, Size;

int TAG = 0;

MPI_Status status; // Параметри прийнятого повiдомлення

double curtime; // Часова мiтка

double startwtime, endwtime;

int namelen,v1,v2,v3,v4;

char processor_name[MPI_MAX_PROCESSOR_NAME];

//Размер массива рангов

int Kol_proc=8;

//Кол. Процессов в группах

int proc1[]={1,5,7,2};

int proc2[]={8,3,4,6};

MPI_File fh;

MPIO_Request req;

MPI_Group *group1,*group2;

MPI_Init(&argc,&argv); // Iнiцiалiзацiя паралельної частини додатка

MPI_Comm_rank(MPI_COMM_WORLD, &Nproc);