Параллельные вычисления. Баканов В.М. - 72 стр.

UptoLike

ВУЗ: 

МИРЭА | Москва

Составители: 

Рубрика: 

- 72 -
Пункт Действие Примечание
а) Задать список вершин, зависящих
только
от входных данных
; занести его в список
list_1
Начальные данные для работы
алгоритма задаются вручную
б)
Найти вершины, зав
и
симые по дугам от
вершин, входящих
только
в список
list_1
и предыдущие списки (если они есть);
занести их в список
list_2
Наиболее трудоемкий пункт, тре-
бующий просмотра матрицы
смежности для каждого элемента
списка
в) Если список
list_2
не пуст, скопировать
его в
list_1
и идти к пункту б); иначе за-
кончить работу
Цикл по ярусам, пока
о
ные могут
быть выявлены
Вариант (с целью достижения наибольшей прозрачности оптимизации не
производилось) реализации алгоритма на языке С приведен ниже (исходные
данные - квадратная булева матрица смежности
MS[ ][ ]
размерности
N_MS
,
одномерные целочисленные массивы
LIST_1[ ]
и
LIST_2[ ]
длиной
N_L1
и
N_L2
соответственно):
001
do { // по ярусам сколько их будет выявлено
002
N_L2=0;
003
for (ii=0; ii<N_L1; ii++) { // цикл по вершинам в списке LIST_1
004
i_ii=LIST_1[ii]; // i_ii – номер вершины из списка LIST_1
005
for (j=0; j<N_MS; j++) // цикл по столбцам MS (j – номер вершины,
// к которой направлено дуга)
006
if (MS[i_ii][j]) { // нашли какую-то дугу i_ii
→
j
007
j1 = j; // запомнили вершину, к которой идет дуга от i_ii
008
for (i1=0; i1<N_MS; i1++) // по строками MS = исходящим вершинам
009
if (MS[i1][j1]) { // нашли какую-то дугу i1
→
j1
010
flag=false;
011
for (k=0; k<N_L1; k++) // цикл по списку LIST_1
012
if (LIST_1[k] == i1) // если вершина j1 входит в LIST_1…
013
flag=true; // при flag=true вершина i1 входит в список LIST_1
014
}
// конец блока if (MS[i1][j1])
015
if (flag) // …если i1 входит в список LIST_1
016
LIST_2[N_L2++] = j1; // добавить вершину j1 в список LIST_2
017
}
// конец блока if (MS[i_ii][j])
018
}
// конец блока for (ii=0; ii<N_L1; ii++)
019
for(i=0; i<N_L2; i++) // копируем LIST_2 в LIST_1
020
LIST_1[i] = LIST_2[i];
021
N_L1 = N_L2;
022
} while (N_L2); // …пока список LIST_2 не пуст
Время t
j
выполнения операций каждого яруса определяется временем ис-
полнения наиболее длительной операции из расположенных на данном ярусе
(
)
ji
max(
j
t
t
=
, где j – номер яруса, i – номер оператора в данном ярусе). При
планирования выполнения параллельной программы необходимо учитывать
ограниченность по числу процессоров (
P
max
P
≤
), поэтому может быть вы-
годно объединение двух и более быстровыполняемых операторов для после-
довательного исполнения в рамках одного яруса. Как показано ниже в теку-
щем разделе, подобная задача по трудоемкости относится к NP-полным зада-
                                                        - 72 -


 Пункт                     Действие                                            Примечание
   а)     Задать список вершин, зависящих только                    Начальные данные для работы
          от входных данных; занести его в список                   алгоритма задаются вручную
          list_1
   б)     Найти вершины, зависимые по дугам от                      Наиболее трудоемкий пункт, тре-
          вершин, входящих только в список list_1                   бующий     просмотра   матрицы
          и предыдущие списки (если они есть);                      смежности для каждого элемента
          занести их в список list_2                                списка
   в)     Если список list_2 не пуст, скопировать                   Цикл по ярусам, пока оные могут
          его в list_1 и идти к пункту б); иначе за-                быть выявлены
          кончить работу

  Вариант (с целью достижения наибольшей прозрачности оптимизации не
производилось) реализации алгоритма на языке С приведен ниже (исходные
данные - квадратная булева матрица смежности MS[ ][ ] размерности N_MS,
одномерные целочисленные массивы LIST_1[ ] и LIST_2[ ] длиной N_L1 и N_L2
соответственно):
   001   do {                                           // по ярусам сколько их будет выявлено
   002   N_L2=0;
   003   for (ii=0; ii

Страницы