Минимум функции Tk =max((Qi + Ri), где i=1, 2, …, k), ввиду её монотонности достигается при np=n, номер класса эквивалентности разбиений, а n – число вершин в разделяемом графе. Пусть, как и прежде, задан неориентированный взвешенный граф G(V,E) с числом вершин равным n. Этот граф является математической моделью решения некоторой задачи. В памяти компьютера этот граф задаётся матрицей смежности вершин A[n][n], диагональные элементы которой представляют собой временную сложность подзадач, которые могут быть решены параллельно на нескольких процессорах или последовательно на однопроцессорной платформе, а все остальные элементы этой матрицы моделируют временные сложности коммуникационных операций. При решении задачи с использованием единственного процессора коммуникационные затраты отсутствуют. И временная сложность решения всей задачи T1 определяется суммой диагональных элементов матрицы A[n][n]: mSA=A[0][0]; for(j1=1;j1<n;j1++)mSA+=A[j1][j1]; положить T1= mSA. Если теперь T1 разделить на заданный коэффициент ускорения S, то мы получим верхнюю границу для значений функции Tk, соответствующих искомым (допустимым) разбиениям. Добавим к этому ограничению условие «использовать минимальное число процессоров» и получим наиболее практически значимую постановку задачи оптимального разделения взвешенного графа: определить разбиение множества вершин графа P={V1,…,Vk}, на минимальное число подмножеств k, такое для которого выполняются условия достижения заданного ускорения (1.1).
Монотонное убывание значений функции Tk при возрастании числа подмножеств в разбиениях позволяет использовать базовый алгоритм Eq2_1 как в вычислительной схеме последовательного поиска (будем отождествлять её с алгоритмом Eq2_1), так и в алгоритме двоичного поиска минимального разбиения взвешенного графа, при котором обеспечивается выполнение условия (1.1) [3]. Ниже будем именовать вычислительную схему двоичного поиска алгоритмом Eq3_1. Сначала рассмотрим псевдокод алгоритма Eq2_1. Он состоит из следующих шагов:
1. Пусть задана матрица A[n][ n] и коэффициент ускорения kp.
2. Вычислить mSA=A[0][0]; for(j1=1;j1<n;j1++)mSA+=A[j1][j1]; mSA/=kp;
3. Установить значения вектора спецификации разбиения pPsi и характеристического вектора pChi в соответствии с разбиением множества X, состоящим из единственного класса, и: for(i=0;i<n;i++) Chi[i]=pPsi[i]=1. Положить ic=0; np= 1.
4. Для анализа первого класса эквивалентности выполнить 5-8:
if(np < 2)
{
5. Проверка, не достаточно ли одного процессора: увеличить значение счётчика и определить текущее (начальное) значение minmaxSA:
ic1++;
for(i=0;i<n;i++) pChi[i]=pPsi[i]=1;
maxSA=0; for(j1=0; j1<np; j1++)SA[j1]=0;
for(j1=0; j1<np; j1++){for(j2=0; j2<n; j2++){
if((j1+1)==pChi[j2]){SA[j1]+=A[j2][j2];
for(j3=0; j3<n; j3++)if(pChi[j3]!=(j1+1))SA[j1]+= A[j2][j3];}}
if(maxSA<SA[j1])maxSA=SA[j1];}
6. Если найдено разбиение, обеспечивающее требуемое ускорение, то перейти к обработке результата: if(mSA>=maxSA) goto m_result;
7. Выполнить minmaxSA=maxSA;
8. Увеличить текущий номер класса эквивалентности разбиений: np++;}
//************Начало основного цикла
9. Положить nf=n и выполнять 10— 30 для всех оставшихся классов эквивалентности разбиений (np=2, 3, …, n):
while(np<=nf)
{
10. Определить вектор спецификаций для нового класса эквивалентностей разбиений и построить первый характеристический вектор разбиения в этом классе: ii=np; for (i=n-1; i>0; i--)
{if(ii>1){pChi[i]=pPsi[i]=ii; ii--;}else pChi[i]=pPsi[i]=1; }
11. Увеличить значение счётчика и определить minSA:
ic1++;if(ic1>999999999){ic2++;ic1=0;}
maxSA=0; for(j1=0; j1<np; j1++)SA[j1]=0;
for(j1=0; j1<np; j1++){for(j2=0; j2<n; j2++){
if((j1+1)==pChi[j2]){SA[j1]+=A[j2][j2];
for(j3=0; j3<n; j3++)if(pChi[j3]!=(j1+1))SA[j1]+= A[j2][j3];}}
if(maxSA<SA[j1])maxSA=SA[j1];}
12. Если найдено разбиение, обеспечивающее требуемое ускорение, то перейти к обработке результата: if(mSA>=maxSA) goto m_result;
13. Выполнить: if(minmaxSA>maxSA)minmaxSA=maxSA;
// Переменная minmaxSA позволяет монотонное убывание maxSA
14. Положить:i=n-1;
15. Повторять 16 - 27 пока есть ещё не рассмотренные разбиения в текущем классе эквивалентности:разбиений: while(i>0){
//Change PS***************************
16. Изменить вектор спецификаций, выполнив действия 17-21:
for (i=n-1; i>0; i--) {
17. В текущем классе эквивалентности есть нерассмотренная спецификация?
if((pPsi[i]==pPsi[i-1])&&(pPsi[i]<np))
18. Да, тогда построить новый вектор pPsi:
{pPsi[i]++; pChi[i]=pPsi[i]; k=np;
for(ii=n-1; ii>i; ii--) {pPsi[ii] =k; if(k>pPsi[i]) k--;}
19. Для нового вектора pPsi построить первый характеристический вектор разбиения pCh:
for(ii=1; ii<n; ii++)if(pPsi[ii]==pPsi[ii-1])pChi[ii]=1;else pChi[ii]=pPsi[ii];}
20. Увеличить значение счётчика и определить minSA:
ic1++;if(ic1>999999999){ic2++;ic1=0;}
maxSA=0; for(j1=0; j1<np; j1++)SA[j1]=0;
for(j1=0; j1<np; j1++){for(j2=0; j2<n; j2++){
if((j1+1)==pChi[j2]){SA[j1]+=A[j2][j2];
for(j3=0; j3<n; j3++)if(pChi[j3]!=(j1+1))SA[j1]+= A[j2][j3];}}
if(maxSA<SA[j1])maxSA=SA[j1];}
21. Если найдено разбиение, обеспечивающее требуемое ускорение, то перейти к обработке результата: if(mSA>=maxSA) goto m_result;
2.2. Выполнить: if(minmaxSA>maxSA)minmaxSA=maxSA;
23. Прервать цикл «for i »: break;} // if(pPsi[i]==pPsi[i-1])&&pPsi[i]<np)
} //end for i
24. Если цикл «for i» был прерван (был построен новый вектор pPsi), то выполнить построение нового характеристического вектора pChi (действия 25 - 29): if(i>0) {
25. Выполнить: ii=n-1;
while(ii>0) { if(pChi[ii]<pPsi[ii]) {pChi[ii]++; k=ii; k++;
while(k<n) { if(pPsi[k]==pPsi[k-1]) {pChi[k]=1; } k++;}
ii=n-1;
26. Увеличить значение счётчика и определить minSA:
ic1++;if(ic1>999999999){ic2++;ic1=0;}
maxSA=0; for(j1=0; j1<np; j1++)SA[j1]=0;
for(j1=0; j1<np; j1++){for(j2=0; j2<n; j2++){
if((j1+1)==pChi[j2]){SA[j1]+=A[j2][j2];
for(j3=0; j3<n; j3++)if(pChi[j3]!=(j1+1))SA[j1]+= A[j2][j3];}}
if(maxSA<SA[j1])maxSA=SA[j1];}
27. Если найдено разбиение, обеспечивающее требуемое ускорение, то перейти к обработке результата: if(mSA>=maxSA) goto m_result;
28. if(minmaxSA>maxSA)minmaxSA=maxSA;
}//end if(pChi[j]<pPsi[j])
29. Выполнить: else ii--;
}// end while(ii>0)
// Конец изменений pChi
}// end if(i>0)
} //end while(i>0)
30. Выполнить:np++;
}//end while(np<=n)
//*********************Конец основного цикла
m_result: 31. Выполнить:
finish = clock();duration = (double)(finish - start) / CLOCKS_PER_SEC;
32. Вывести номер экспериментальной точки " N= jj ", число просмотренных вариантов " NN= ic2* ic1”, время поиска минимального разбиения множества вершин "duration", номер класса эквивалентности "np", в котором найдено решение, значение функции "Tk= maxSA", характеристический вектор разбиения множества вершин "pChi", который представляет собой найденное решение.
33. Стоп.//Конец описания алгоритма.
Разработка алгоритма Eq3_1 состояла в объединении имеющей общее назначение вычислительной схемы двоичного поиска и поиска экстремального разбиения множества, которая была выше и алгоритма вычисления функции F3. Ниже приводится псевдокод этого алгоритма.
1. Пусть задана матрица A[n][ n] и коэффициент ускорения kp.
2. Вычислить mSA=A[0][0]; for(j1=1;j1<n;j1++)mSA+=A[j1][j1]; mSA/=kp;
3. Выполнить: ic1=ic2=0;np=1;
4. Вывести " mSA=”, inSA;
5. Выполнить: start = clock();
6. Выполнить генерацию первого разбиения: for(i=0;i<n;i++) pChi[i]=pPsi[i]=1;
7. Обработать первое разбиение, выполнив действия 8 - 10:
if(np < 2)
{
8. Выполнить: for(i=0;i<n;i++) pChi[i]=pPsi[i]=1;
ic1++;
9. Вычислить значение функции S= maxSA для первого разбиения: maxSA=0; for(j1=0; j1<np; j1++)SA[j1]=0;
for(j1=0; j1<np; j1++){for(j2=0; j2<n; j2++){
if((j1+1)==pChi[j2]){SA[j1]+=A[j2][j2];
for(j3=0; j3<n; j3++)if(pChi[j3]!=(j1+1))SA[j1]+= A[j2][j3];}}
if(maxSA<SA[j1])maxSA=SA[j1];}
10. Если найдено разбиение, обеспечивающее требуемое ускорение, то перейти к обработке результата:
if(minSA>=maxSA){ minmaxSA=maxSA;minnp=np;
for(j1=0; j1<n; j1++) minpChi[j1]= pChi[j1];
goto m3_result;}
} // if(np < 2)
//************Начало основного цикла
11. Вычислить np: nn1=2; nn2=n; np=(nn1+nn2)/2;
12. Выполнить:
while(nn2>nn1)
{// Изменить pPsi*****************************
13. Определить вектор спецификаций для нового класса эквивалентностей разбиений и построить первый характеристический вектор разбиения в этом классе: ii=np; for (i=n-1; i>0; i--){ if(ii>1){pChi[i]=pPsi[i]=ii; ii--;}else pChi[i]=pPsi[i]=1; }
14. Увеличить значение счётчика и определить minSA:
ic1++;if(ic1>999999999){ic2++;ic1=0;}
maxSA=0; for(j1=0; j1<np; j1++)SA[j1]=0;
for(j1=0; j1<np; j1++){for(j2=0; j2<n; j2++){
if((j1+1)==pChi[j2]){SA[j1]+=A[j2][j2];
for(j3=0; j3<n; j3++)if(pChi[j3]!=(j1+1))SA[j1]+= A[j2][j3];}}
if(maxSA<SA[j1])maxSA=SA[j1];}
15. Если найдено разбиение, обеспечивающее требуемое ускорение, то перейти к обработке результата:
if(mSA>=maxSA){ minmaxSA=maxSA;minnp=np;
for(j1=0; j1<n; j1++) minpChi[j1]= pChi[j1]; goto m2_result;}
16. Положить: i=n-1;
17. Повторять 18 - 27 пока есть ещё не рассмотренные разбиения в текущем классе эквивалентности:
while(i>0)
{
//Change PS***************************
18. Изменить вектор спецификаций, выполнив действия 19-23:
for (i=n-1; i>0; i--)
{
19. В текущем классе эквивалентности есть нерассмотренная спецификация?
if((pPsi[i]==pPsi[i-1])&&(pPsi[i]<np))
20. Да, тогда. Построить новый вектор pPsi:
{pPsi[i]++; pChi[i]=pPsi[i]; k=np;
for(ii=n-1; ii>i; ii--) {pPsi[ii] =k; if(k>pPsi[i]) k--;}
21. Для нового вектора pPsi построить первый характеристический вектор разбиения pCh:
for(ii=1; ii<n; ii++){if(pPsi[ii]==pPsi[ii-1])pChi[ii]=1;else pChi[ii]=pPsi[ii];} 22. Увеличить значение счётчика и определить minSA:
ic1++;if(ic1>999999999){ic2++;ic1=0;}
maxSA=0; for(j1=0; j1<np; j1++)SA[j1]=0;
for(j1=0; j1<np; j1++){for(j2=0; j2<n; j2++){
if((j1+1)==pChi[j2]){SA[j1]+=A[j2][j2];
for(j3=0; j3<n; j3++)if(pChi[j3]!=(j1+1))SA[j1]+= A[j2][j3];}}
if(maxSA<SA[j1])maxSA=SA[j1];}
23. Если найдено разбиение, обеспечивающее требуемое ускорение, то перейти к обработке результата:
if(mSA>=maxSA){ minmaxSA=maxSA;minnp=np;
for(j1=0; j1<n; j1++) minpChi[j1]= pChi[j1];
goto m2_result;}
24. Выполнить: break; } // if(pPsi[i]==pPsi[i-1])&&pPsi[i]<np)
} //end for i
25. Если цикл «for i» был прерван (был построен новый вектор pPsi), то выполнить построение нового характеристического вектора pChi (действия 26 – 29): if(i>0)
{
26. Выполнить ii=n-1; while(ii>0)
{ if(pChi[ii]<pPsi[ii]) {pChi[ii]++; k=ii; k++;
while(k<n){if(pPsi[k]==pPsi[k-1]) {pChi[k]=1; }k++;}
ii=n-1;
27. Увеличить значение счётчика и определить minSA:
ic1++;if(ic1>999999999){ic2++;ic1=0;}
maxSA=0; for(j1=0; j1<np; j1++)SA[j1]=0;
for(j1=0; j1<np; j1++){for(j2=0; j2<n; j2++){
if((j1+1)==pChi[j2]){SA[j1]+=A[j2][j2];
for(j3=0; j3<n; j3++)if(pChi[j3]!=(j1+1))SA[j1]+= A[j2][j3];}}
if(maxSA<SA[j1])maxSA=SA[j1];}
28. Если найдено разбиение, обеспечивающее требуемое ускорение, то перейти к обработке результата:
if(mSA>=maxSA){ minmaxSA=maxSA;minnp=np;
for(j1=0; j1<n; j1++) minpChi[j1]= pChi[j1];
goto m2_result;}
}//end if(pChi[j]<pPsi[j])
29. Выполнить: else ii--;
}// end while(ii>0)
//Конец изменений pChi**************************
}// end if(i>0)
} //end while(i>0)
30. Вычислить новое значение np: m2_result:if(mSA>=maxSA)nn2=np; else nn1=np+1; np=(nn1+nn2)/2;
}//end while(nn2>nn1)
//*********************End main cycle
31. Выполнить: m3_result:finish = clock();duration = (double)(finish - start) / CLOCKS_PER_SEC;
32. Вывести номер экспериментальной точки " N= jj ", число просмотренных вариантов " NN= ic2* ic1”, время поиска минимального разбиения множества вершин "duration", номер класса эквивалентности "np", в котором найдено решение, значение функции "S= maxSA", характеристический вектор разбиения множества вершин " minpChi ", который представляет собой найденное решение.
33. Стоп.//Конец описания алгоритма
Описанные в данном разделе алгоритмы были реализованы в виде консольных программ, которые обеспечили их экспериментальное исследование. Результаты этого исследования рассматриваются в следующем разделе.
Для проведения вычислительного эксперимента с алгоритмами Eq2_1, Eq3_1, их программные реализации были объединены в специальную тест-программу. Это позволило выполнять обработку этими алгоритмами одних и тех же матриц смежности взвешенных графов, которые генерировались с использованием равномерно распредел1нных псевдослучайных чисел. Основные результаты вычислительного эксперимента с указанной тест-программой представлены в таблице 3
Таблица 3. Сравнение алгоритмов Eq2_1, Eq3_1 при n= 12, kf=10, kp=3
| N | mSA | Последовательный поиск | Двоичный поиск (Eq3_1) | ||||
| np | maxSA | Время, с | np | maxSA | Время, с | ||
| 455,691 | 451,529 | 10,469 | 451,529 | 1,828 | |||
| 524,902 | 523,995 | 5,141 | 523,995 | 5,25 | |||
| 477,854 | 471,153 | 10,187 | 471,153 | 2,11 | |||
| 518,264 | 517,727 | 4,765 | 517,727 | 4,672 | |||
| 493,197 | 492,011 | 8,266 | 492,011 | 4,984 | |||
| 501,415 | 498,243 | 8,141 | 498,243 | 8,141 | |||
| 518,372 | 517,691 | 517,691 | |||||
| 504,544 | 501,87 | 5,422 | 501,87 | 5,609 | |||
| 480,443 | 472,134 | 10,171 | 472,134 | 2,094 | |||
| 501,598 | 501,512 | 8,156 | 501,512 | 4,968 | |||
| Среднее время поиска = | 7,7718 | Среднее время поиска = | 4,6656 |
Данные приведённые в таблице 6 свидетельствуют о том, что двоичный поиск оказывается быстрее усовершенствованного последовательного поиска в 1,665766 раз в среднем.
ВЫВОДЫ
В результате вычислительного эксперимента показано, что минимальное значение временной сложности параллельных вычислений (функция Tk) монотонно убывает с увеличением номера класса эквивалентности разбиений множества вершин взвешенного графа. Эта монотонность имеет места при достаточно широком диапазоне изменений основных параметров, от которых зависит функция Tk. Монотонность функции Tk позволила использовать базовый алгоритм Eq2_1 как в вычислительной схеме последовательного поиска (будем отождествлять её с алгоритмом Eq2_1) так в алгоритме двоичного поиска минимального разбиения взвешенного графа, при котором обеспечивается коэффициент ускорения в среднем равный 1,665766. Разработанный метод оптимального разделения взвешенных графов, основанный на использовании алгоритма Eq3_1, обеспечивает эффективное решение задачи определения минимального числа процессоров, необходимых для реализации параллельных вычислений с заданным ускорением относительно последовательных вычислений.