Говорят "Любая программа содержит хотя бы одну ошибку". Применительно к параллельному программированию этот тезис можно переформулировать так "Параллельное программирование начинается с параллельных ошибок". Действительно, процесс создания параллельной программы, либо с нуля на основе
В настоящей лабораторной работе рассматривается один из инструментов отладки, основанный на сборе и автоматическом анализе информации по результатам выполнения программ и предназначенный для многопоточных и
В качестве полигона для демонстрации ошибок и возможностей инструментов по их поиску и анализу используются: классическая задача
Целью данной лабораторной работы является приобретение практических навыков отладки параллельных программ для систем с распределенной памятью, использующих для организации параллелизма либо механизм потоков, либо технологию
Данная цель предполагает решение следующих задач:
Данный документ состоит из введения, двух разделов, списка дополнительных заданий и списка литературы. Во введении обосновывается актуальность инструментальной поддержки в процессе отладки параллельных программ. В первом разделе приводятся методические рекомендации к лабораторной работе: формулируются цели и задачи, системные требования, рекомендации по проведению занятий. Во втором разделе изучается отладка параллельных программ с демонстрацией характерных ошибок и изучением методов их обнаружения и устранения. Изучение проводится на специально подобранных примерах. Для обнаружения ошибок используется инструмент отладки Intel Thread
В документации к
Минимальные требования
При практическом использовании ITС рекомендуются повышенные требования к минимально-необходимым аппаратным ресурсам (для достижения приемлемых показателей оперативности работы):
Для изучения всех аспектов "реальных" параллельных вычислений желательно использование многоядерных процессоров компании Intel.
Для анализа
При выполнении данной лабораторной работы рекомендуется придерживаться следующей последовательности изучения материала:
Задача
Итак, пусть имеются вектора $$a$$ и $$b$$ размерности $$n$$ (состоящие из $$n$$ элементов).
(рис 11.1) Скалярное произведение двух векторовТак, например, при умножении вектора $$a= (1,2,3)$$ на вектор $$b= (3,2,1)$$ получится, как нетрудно посчитать 10:
$$(1\ 2\ 3) \times \begin{pmatrix} 3\\2\\1 \end{pmatrix} = 1 * 3 + 2 * 2 + 3 * 1 = 10$$Алгоритм вычисления скалярного произведения полностью описывается его формулой, поэтому приведем сразу его код:
sum_all = 0;
for (i = 0; i < Size; i++)
{
sum_all += x[i] * y[i];
}
Необходимые объявления переменных, а также ввод данных здесь рассматривать не будем (см. проект
Алгоритм
Итак, мы имеем цикл с регулярной структурой и одинаковой вычислительной сложностью итераций. Распараллеливание его средствами
sum_all = 0;
#pragma omp parallel for
for (i = 0; i < N; i++)
{
sum_all += up[i] * vp[i];
}
Некоторый произвол возможен в том, как разделить вычисления между потоками. Первая схема - каждый поток обрабатывает непрерывный фрагмент умножаемых векторов. Вторая - вектора делятся между потоками поэлементно (или поблочно). Каждая схема может быть реализована с использованием параметра schedule. Провести соответствующие эксперименты предоставляем читателю самостоятельно.
В представленном выше коде мы сознательно допустили достаточно очевидную ошибку. Посмотрим, как с ней справится
Откройте проект
C:\ITCLabs\Scalar ,Scalar .slnПосле открытия проекта в окне Solution Explorer дважды щелкните на файле исходного кода Scalar.сpp. После этих действий программный код, с которым предстоит работать, будет открыт в
Далее выполните действия, описанные в пункте 7.3 документа "
И, наконец, запустите C:\ITCLabs\.
Нажмите кнопку Finish. После этого запустится
(рис 11.3) Результат анализа параллельной реализации 1 скалярного умноженияКак и следовало ожидать источник неприятностей - переменная sum_all, на что недвусмысленно указывает
Для исправления представленного выше кода требуется лишь одна модификация - переменная, в которую накапливается сумма, должна быть сделана локальной для каждого потока. В противном случае во избежание parallel for.
Вносим исправления:
sum_all = 0;
#pragma omp parallel for reduction(+:sum_all)
for (i = 0; i < N; i++)
{
sum_all += up[i] * vp[i];
}
Повторно запускаем активность в
(рис 11.4) Результат анализа параллельной реализации 1 после исправленияОтметим, что параметр
В дополнение рассмотрим еще один несколько искусственный вариант
Итак, пусть параллельная схема вычисления скалярного произведения выглядит следующим образом.
#pragma omp parallel private(rank, sum)
{
rank = omp_get_thread_num();
if (rank == 0)
{
NumThreads = omp_get_num_threads();
x = CreateVector(N);
y = CreateVector(N);
}
sum[rank] = 0;
#pragma omp for
for (i = 0; i < N; i++)
{
sum[rank] += x[i] * y[i];
}
}
sum_all = 0;
for (i = 0; i < NumThreads; i++)
{
sum_all += sum[i];
}
DeleteVector(x);
DeleteVector(y);
Нулевой поток "занимается" выделением памяти под данные и их инициализацией, после чего начинается собственно расчет. Представленная схема хоть и выглядит для задачи sum.
Попробуйте самостоятельно найти в представленном
Откройте проект Scalar2. Соберите программу в конфигурации debug. Прежде всего, посмотрим на результаты работы последовательной и параллельной версии. Зададим размер векторов равный 100 и запустим программу.
(рис 11.5) Результат запуска параллельной реализации 2Итак, результаты запуска однозначно указывают на некорректность параллельной версии. Приступаем к поиску ошибок.
Снова выполните действия, описанные в пункте 7.3 документа "C:\ITCLabs\Scalar2\Debug\Scalar2.exe.
Нажмите кнопку Finish. После этого запустится
(рис 11.6) Результат анализа параллельной реализации 2 скалярного умноженияПервое, что можно отметить - появились новые
"Открываем" ее двойным щелчком:
(рис 11.7) Просмотр диагностики "Use of unsupported API"Представленная диагностика вызвана тем, что omp_get_num_threads(). Отсюда, кстати, и большая часть остальных ошибок, которые вызваны тем, что значение переменной
Выходов из подобных ситуаций два: отказаться от использования run-time функций
Но прежде вернемся к ошибке под номером 9.
(рис 11.8) Неверная локализация переменной sumНесмотря на не слишком вразумительное сообщение, тем не менее, можно понять, что выше по коду нами допущена ошибка - переменная sum сделана private, что, конечно же, неверно. Этот массив специально был создан для подсчета потоками локальных сумм и естественно должен быть общим, чтобы по окончании параллельной секции из него в переменную sum_all можно было собрать итоговую сумму.
Исправляем ситуацию:
#pragma omp parallel private(rank/*, sum*/)
{
...
}
sum_all = 0;
for (i = 0; i < NumThreads; i++)
{
sum_all += sum[i];
}
DeleteVector(x);
DeleteVector(y);
Убираем ключ /Qtcheck из проекта и снова запускаем анализ в
(рис 11.9) Результат анализа параллельной реализации 2 после первого исправленияТеперь мы, к сожалению, потеряли информацию об именах переменных. Число сообщений также сократилось. Однако
Анализируя первое же сообщение, мы находим одну из типичных ошибок в многопоточных программах - использование потоками неинициализированных данных.
(рис 11.10) Ошибка - использование потоками неинициализированных данных Глядя на выделенные строки, нетрудно понять, что поток с номером, отличным от 0, будет пытаться использовать переменные x и y до того, как нулевой поток выделит под них память, что в лучшем случае приведет к падению, а в худшем к неверному результату расчетов. Решение в данной ситуации также является типичным и состоит в установке барьера после участка инициализации.
#pragma omp parallel private(rank)
{
rank = omp_get_thread_num();
if (rank == 0)
{
NumThreads = omp_get_num_threads();
x = CreateVector(N);
y = CreateVector(N);
}
sum[rank] = 0;
#pragma omp barrier
#pragma omp for
for (i = 0; i < N; i++)
{
sum[rank] += x[i] * y[i];
}
}
...
После внесения последних исправлений, результаты запуска полученной параллельной версии, наконец-то, совпадут с последовательным вариантом. Убедитесь в этом, а также в том, что
В качестве второго примера рассмотрим задачу из области численного
и принимающую на границе $$D^0$$ области $$D$$ значения $$g(x,y)$$.
Используя распространенный метод конечных разностей (он же метод сеток) перепишем уравнение Пуассона в конечно-разностной форме [11.9],
$$\cfrac{u_{i-1,j}+ u_{i+1,j} +u_{i,j+1}-4 u_{i,j}}{h^2}=f_{i,j}$$Разрешив его относительно $$u_{ij}$$, получим
$$u_{ij} = 0.25 (u_{i-1,j}+ u_{i+1,j} +u_{i,j+1}-h^2 f_{ij})$$Мы получили основу для построения итерационной схемы решения
Последовательная реализация данной итерационной схемы может выглядеть следующим образом:
do
{
dmax = 0;
for (i = 1; i < N - 1; i++)
{
for(j = 1; j < N - 1; j++)
{
temp = u[N * i + j];
u[N * i + j] = 0.25 * (u[N * i + j + 1] + u[N * i + j - 1] +
u[N * (i + 1) + j] + u[N * (i - 1) + j]);
dm = fabs(u[N * i + j] - temp);
if (dmax < dm)
dmax = dm;
}
}
}
while (dmax > EPS);
Здесь dmax есть максимальная разность между "старым", с предыдущей итерации, и "новым", посчитанным на текущей, значениями и используется для принятия решения об окончании расчетов.
"Сеточные" задачи, в которых решение получается выполнением набора из одних и тех же действий в каждом "узле" сетки обладают очень простой схемой распараллеливания. Достаточно сетку "порезать" на части: вертикально на столбцы, горизонтально на полосы, или и так и так, то есть на блоки, и распараллеливание выполнено. Если при этом объем вычислений, выполняемых в каждом узле, примерно одинаков, то и эффективность полученной параллельной реализации может быть довольно высока.
Таким образом, в данной работе мы рассмотрим две схемы распараллеливания решения
В данной лабораторной работе нашей целью не является производительность получаемых параллельных реализаций, поэтому в качестве первого варианта, как было сказано выше, мы используем вариант с максимальным параллелизмом, который в
do
{
dmax = 0;
#pragma omp parallel for
for (i = 1; i < N - 1; i++)
{
#pragma omp parallel for
for(j = 1; j < N - 1; j++)
{
temp = u[N * i + j];
u[N * i + j] = 0.25 * (u[N * i + j + 1] + u[N * i + j - 1] +
u[N * (i + 1) + j] + u[N * (i - 1) + j]);
dm = fabs(u[N * i + j] - temp);
if (dmax < dm)
dmax = dm;
}
}
}
while (dmax > EPS);
Конечно же, в представленном виде код является некорректным. В чем именно, нам предстоит выяснить, использую Intel Thread
Исследуем представленный выше код на наличие ошибок.
Для проверки правильности работы параллельной программы можно применить, казалось бы, естественный подход - сравнить результаты выполнения последовательной и параллельной версий. Например, в задаче
Рассматриваемый пример прекрасно демонстрирует описанные выше ситуации - вычислительная схема
Проанализируем код с помощью Intel Thread
(рис 11.11) Задача Дирихле - результат анализа параллельной реализации 1Как видим, налицо существенное количество ошибок, которые
"Разворачивая" любую из них, мы получим информацию вида:
(рис 11.12) Задача Дирихле - ошибка типа "гонка данных"Как видим, диагностика temp, когда два потока могут пытаться одновременно записать в нее значения.
Решение выявленных проблем зависит от того, как используется та или иная переменная и может состоять в ее "локализации", то есть создании внутренней для каждого потока копии, как для переменной temp, или в синхронизации доступа к ней, если переменная нужна всем потокам, как в случае с dmax.
Заметим, что две из найденных N. Какие именно, предлагаем читателям найти самостоятельно.
Корректируем код:
omp_lock_t dmax_lock;
omp_init_lock(dmax_lock);
do
{
dmax = 0;
#pragma omp parallel for
for (i = 1; i < N - 1; i++)
{
#pragma omp parallel for private(temp, dm)
for(j = 1; j < N - 1; j++)
{
temp = v[N * i + j];
v[N * i + j] = 0.25 * (v[N * i + j + 1] + v[N * i + j - 1] +
v[N * (i + 1) + j] + v[N * (i - 1) + j]);
dm = fabs(v[N * i + j] - temp);
omp_set_lock(dmax_lock);
if (dmax < dm)
dmax = dm;
omp_unset_lock(dmax_lock);
}
}
}
while (dmax > EPS);
omp_destroy_lock(dmax_lock);
По результатам запуска убеждаемся, что параллельная версия работает корректно. Снова запускаем Thread Checker и видим.
(рис 11.13) Задача Дирихле - результат анализа параллельной реализации 1 после исправленияПрав или нет
Второй вариант распараллеливания, который мы будем использовать в данной работе, состоит в уменьшении степени параллелизма реализации, что, тем не менее, ведет к увеличению эффективности. Вариант заключается в распараллеливании только внешнего цикла и дополнительно предполагает некоторые изменения в схеме подсчета значения dmax:
do
{
dmax = 0;
#pragma omp parallel for
for (i = 1; i < N - 1; i++)
{
dm = 0;
for(j = 1; j < N - 1; j++)
{
temp = u[N * i + j];
u[N * i + j] = 0.25 * (u[N * i + j + 1] + u[N * i + j - 1] +
u[N * (i + 1) + j] + u[N * (i - 1) + j]);
d = fabs(u[N * i + j] - temp);
if (dm < d)
dm = d;
}
if (dmax < dm)
dmax = dm;
}
}
while (dmax > EPS);
Как и в первом случае представленный код содержит ошибки, которые необходимо найти с помощью Intel Thread
Прежде всего, отметим, что в связи с изменившейся схемой работы и рассмотренная выше параллельная версия и данная могут не давать идентичные результаты по сравнению с последовательным кодом, что, конечно, является дополнительным усложняющим моментом для "ручной" отладки.
Проанализируем код с помощью Intel Thread
(рис 11.14) Задача Дирихле - результат анализа параллельной реализации 2Количество ошибок в этой версии еще больше в связи с увеличившимся количеством переменных, кроме того, в список попала переменная j, заботу о которой раньше "брал не себя" компилятор - как известно переменную цикла в директиве # не обязательно объявлять как private.
Также как и для варианта 1 исправление найденных ошибок заключается в локализации необходимых переменных и использовании синхронизации при работе с переменной dmax.
omp_lock_t dmax_lock;
omp_init_lock(dmax_lock);
do
{
dmax = 0;
#pragma omp parallel for private(j, temp, d, dm)
for (i = 1; i < N - 1; i++)
{
dm = 0;
for(j = 1; j < N - 1; j++)
{
temp = v[N * i + j];
v[N * i + j] = 0.25 * (v[N * i + j + 1] + v[N * i + j - 1] +
v[N * (i + 1) + j] + v[N * (i - 1) + j]);
d = fabs(u[N * i + j] - temp);
if (dm < d)
dm = d;
}
omp_set_lock(dmax_lock);
if (dmax < dm)
dmax = dm;
omp_unset_lock(dmax_lock);
}
}
while (dmax > EPS);
omp_destroy_lock(dmax_lock);
Снова запускаем
(рис 11.15) Задача Дирихле - результат анализа параллельной реализации 2 после исправленияКак и выше for при использовании директивы # без дополнительных параметров.
На примере данной классической задачи мы продемонстрируем еще одну типичную ошибку - тупик ( deadlock ), ее диагностику при помощи
Приведем вольную формулировку задачи Дейкстры: за круглым столом заседают 5 философов. Напротив каждого из них стоит блюдо со спагетти. Между каждыми двумя соседями расположена одна вилка. Философ может находиться в одном из двух состояний: ест, размышляет. При еде философу нужны 2 вилки (левая и правая).
Реализуем требуемый
Идея реализации состоит в следующем: главный поток создает дополнительные потоки в соответствии с количеством философов, запускает их и переходит в бесконечный цикл. Каждый из дополнительных потоков реализует поведение философа. При этом вилки предлагается моделировать при помощи
Сделаем следующие объявления:
// Количество философов
const unsigned int n = 5;
// Структура - описание философа
typedef struct
{
int iID; // Номер философа
HANDLE hMyObjects[2]; // Мьютексы (вилки)
} THREADCONTROLBLOCK, *PTHREADCONTROLBLOCK;
Приведем функцию потока. Используем функцию WaitForSingleObject для ожидания
long WINAPI ThreadRoutine(long lParam)
{
PTHREADCONTROLBLOCK pcb=(PTHREADCONTROLBLOCK)lParam;
while (TRUE)
{
WaitForSingleObject(pcb->hMyObjects[0],INFINITE);
WaitForSingleObject(pcb->hMyObjects[1],INFINITE);
printf("Eating: Philosopher %d \n",pcb->iID);
ReleaseMutex(pcb->hMyObjects[1]);
ReleaseMutex(pcb->hMyObjects[0]);
};
return (0);
}
Тогда функция main будет выглядеть так:
int main()
{
HANDLE hMutexes[n];
THREADCONTROLBLOCK tcb[n];
int iThreadID;
for (int i = 0; i < n; i++)
hMutexes[i] = CreateMutex(NULL, FALSE, NULL);
for (int i = 0; i < n; i++)
{
tcb[i].iID = i+1;
tcb[i].hMyObjects[0] = hMutexes[i % n];
tcb[i].hMyObjects[1] = hMutexes[(i+1) % n];
CloseHandle(CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)ThreadRoutine,
(void *)tcb[i],0,LPDWORD(iThreadID)));
}
while(TRUE);
return(0);
}
Запустим программу на выполнение несколько раз.
(рис 11.16) Задача об обедающих философах - результаты запуска параллельной реализации 1Результаты будут варьироваться от запуска к запуску. Единственное, что их объединяет, - неизменное зависание в некоторый момент. Попробуем разобраться, в чем дело. Прибегнем к помощи Intel Thread
(рис 11.17) Диагностика ITC в задаче об обедающих философах (параллельная реализация 1)
Подумаем над тем, как исключить тупики, наличие которых обуславливает не столько некорректная реализация, сколько сама постановка задачи. Действительно, возможна ситуация, в которой каждый из философов взял ровно одну вилку и ждет, когда освободится вторая, которая занята соседом. Сосед в свою очередь ждет свою вторую вилку и т.д.
Одним из возможных способов решения проблемы является изменение модели поведения философа. К примеру, можно наделить его обязанностью брать вилки одновременно, лишь тогда, когда обе они свободны. Изменения в программной реализации будут минимальны - достаточно заменить 2 вызова функции WaitForSingleObject на 1 вызов функции WaitForMultipleObjects для одновременного
#include <stdio.h>
#include <windows.h>
// Количество философов
const unsigned int n = 5;
typedef struct {
int iID;
HANDLE hMyObjects[2];
} THREADCONTROLBLOCK, *PTHREADCONTROLBLOCK;
long WINAPI ThreadRoutine(long lParam) {
PTHREADCONTROLBLOCK pcb=(PTHREADCONTROLBLOCK)lParam;
while (TRUE) {
WaitForMultipleObjects(2, pcb->hMyObjects, TRUE, INFINITE);
printf("Eating: Philosopher %d \n",pcb->iID);
ReleaseMutex(pcb->hMyObjects[1]);
ReleaseMutex(pcb->hMyObjects[0]);
};
return (0);
}
int main() {
HANDLE hMutexes[n];
THREADCONTROLBLOCK tcb[n];
int iThreadID;
for (int i = 0; i < n; i++)
hMutexes[i] = CreateMutex(NULL,FALSE,NULL);
for (int i = 0; i < n; i++) {
tcb[i].iID = i+1;
tcb[i].hMyObjects[0] = hMutexes[i % n];
tcb[i].hMyObjects[1] = hMutexes[(i+1) % n];
CloseHandle(CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)ThreadRoutine,
(void *)tcb[i],0,LPDWORD(iThreadID)));
}
while(TRUE);
return(0);
}
Тестовые запуски подтверждают наши ожидания - программа перестала зависать.
Для постановки задачи рассмотрим некоторую "гипотетическую" лабораторию искусственного интеллекта, в которой выполняются работы по созданию роботов.
Для испытаний лабораторных образцов построен полигон, устроенный следующим образом: в начале полигона находится единственная дверь. Пройдя через нее, робот оказывается перед $$B$$ дверьми. Выбрав одну из дверей, робот вновь оказывается перед $$B$$ дверьми, и т.д. Пройдя через дверь, робот получает премию в размере $$x$$, где $$x$$ - количество монет, лежащее за данной дверью (для разных дверей количество монет может быть разным).
Считая известным:
следует определить среднюю премию, получаемую роботом при проходе через данный полигон.
Считать, что выполняются следующие условия: $$B\le20\le10$$
Объектом исследования в данной задаче является полигон с иерархической структурой, по которому по
Прежде всего, введем необходимые обозначения.
$$B$$, $$L$$, $$P_{L,L+1}^{ij}$$ и $$x_{L}^{i}$$ являются исходными данными для данной задачи. Из условия задачи вытекают следующие ограничения на исходные данные:
Теперь перейдем непосредственно к выбору модели. Вследствие иерархической структуры полигона выглядит разумным его представление в виде дерева степени $$B$$ и глубины $$L$$. При этом узлы дерева содержат значения $$x_{L}^{i}$$, а дугам приписаны
(рис 11.18) Модель полигона в задаче о роботе
Перейдем к описанию метода нахождения результата. Пусть $$E_d^i$$ - средняя премия, которая может быть получена, если робот начинает путь в узле $$i$$ уровня $$d$$.
Тогда
$$E_d^i= x_d^i + \sum_{i=0}^{B-1}{ P_{d,d+1}^{i,j} \times E_{d+1}^{i}, \text{где } d = \overline{0;l-2} ; i = \overline{0;B-1}} \\ E_{L-1}^i= x_{L-1}^i, \text{где } i = \overline{0;B-1}}$$Очевидный метод вычисления результата $$E_0^0$$ состоит в вычислении значений $$E$$ на последнем уровне дерева (второе соотношение) с последующим пересчетом из конца в начало (первое рекуррентное соотношение).
Перейдем к реализации последовательной версии изложенного выше метода решения.
Проектирование структур данных
Предусмотрим для
const int b = 10; // Степень дерева - B в постановке задачи
const int l = 7; // Количество уровней дерева
const int MAX_VALUE = 20; // Максимальное значение в вершине дерева
int NodesCount; // Количество узлов дерева = (1-b^l) / (1-b)
int BranchesCount; // Количество ветвей дерева = NodesCount - 1;
typedef struct // Узел дерева
{
int value; // Значение в узле
// Вероятность попадания в узел из узла предыдущего уровня
double probability;
// Компонент для подсчета среднего
double expectation;
} TreePart;
Учитывая регулярную структуру дерева, будем хранить его в виде массива узлов, располагая в нем узлы последовательно по уровням, от корня к листьям. Учитывая возможный большой размер массива, будем создавать его динамически в куче. В результате получим:
TreePart *RobotTree; // Массив для хранения дерева. // Схема хранения: // (V00) // (V10 V11 ... V1b) // (V21 V22... V2b^2) // ... // (Vl-1,1 Vl-1,2...Vl-1,b^(l-1)), // где скобки стоят для наглядности. // Дерево упаковывается в одномерный массив по уровням.
Для удобства индексации и снижения накладных расходов предусмотрим однократное вычисление значения b в степени от 0 до l-1, а также номеров первых узлов каждого уровня дерева в массиве RobotTree.
// Вспомогательный массив для хранения значений b в степени 0...l-1 __int64 power[l]; // Вспомогательный массив для хранения номера первого узла каждого уровня // в массиве RobotTree __int64 index[l];
Проектирование модульной структуры
Предусмотрим наличие в проекте файла
// Ввод дерева void InputTree(void); // Освобождение памяти, выделенной для хранения дерева void ReleaseTree(void); // Функция вычисления максимума __inline double max(double v1, double v2); // Функция вычисления премии по значению в узле __inline double func(double value); // Вычисление средней премии - основная расчетная функция double GetExpectation(void); // Головная функция int main(void);
Прокомментируем основные функции.
Функция InputTree предназначена для ввода исходных данных в соответствии с условием задачи. В этой функции вычисляется количество узлов и ветвей, выделяется память для хранения дерева, заполняются вспомогательные массивы power и index, инициализируется датчик случайных чисел и происходит
Функция func предназначена для обобщения задачи на случай, когда размер премии при открывании двери является некоторой функцией от x. В рассматриваемой сейчас постановке она просто возвращает значение x.
Функция GetExpectation рассчитывает средний размер премии по дереву при помощи описанного выше метода. Приведем ее реализацию:
// Вычисление среднего
// Алгоритм базируется на следующих соотношениях:
// E_l,i = СУММА по j=0__b-1 (Probability_l+1,j * E_l+1,j + value_l,i),
// где l - уровень, i - номер узла в уровне, l+1,j - узлы потомки узла l,i.
// Учитывая, что на последнем уровне E_l-1,i = Value_l-1,i
// Вычиляем рекуррентное соотношения из конца в начало.
// В итоге имеем сумму для нулевого узла - корня дерева
double GetExpectation(void)
{
// Последний уровень
int i, j, level;
double sum;
TreePart rp;
for (j = 0; j < power[l-1]; j++)
RobotTree[j + index[l-1]].expectation =
func(RobotTree[j + index[l-1]].value);
// Пересчет из конца в начало
// Цикл по уровням
for (level = l - 2; level >= 0; level--)
{
// Цикл по узлам уровня
for (j = 0; j < power[level]; j++)
{
// Для узла level, j подсчитываем expectation
// Цикл по потомкам
sum = func(RobotTree[ index[level] + j ].value);
for (i = 0; i < b; i++)
{
rp = RobotTree[ index[level+1] + b * j + i ];
sum = sum + rp.expectation * rp.probability;
}
RobotTree[ index[level] + j ].expectation = sum;
}
}
return RobotTree[0].expectation;
}
Рассмотрим возможный вариант распараллеливания предложенной выше последовательной реализации. Акцент сделаем на корректности реализации, а не на ее производительности, которая не является целью данной лабораторной работы. Приведем лишь одно соображение по поводу производительности. Поскольку метод решения задачи предполагает, что последний уровень дерева обсчитывается отдельно от остальных, начнем наше распараллеливание именно с него. Если подумать, можно обнаружить первый "подводный камень" этой задачи, связанный не с корректностью, но с производительностью разрабатываемой реализации. Легко допустить неточность, посчитав, что распараллеливание на последнем уровне можно опустить. Казалось бы, в чем смысл отдельной работы ради одного уровня? На самом деле смысл есть, поскольку последний уровень содержит наибольшее число узлов, и пренебрегать им при распараллеливании не стоит. Применим для распараллеливания обсчета #.
Соответствующий фрагмент кода будет выглядеть так:
#pragma omp parallel for
for (j = 0; j < power[l-1]; j++)
RobotTree[j + index[l-1]].expectation =
func(RobotTree[j + index[l-1]].value);
Заметим, что переменная j станет локализованной автоматически (согласно стандарту
Перейдем к распараллеливанию основного блока кода, производящего обсчет дерева.
Естественный вариант состоит в разделении всех узлов каждого уровня между потоками. Этого можно добиться по крайней мере двумя способами. Первый состоит в размещении директивы # перед циклом по узлам очередного уровня. В итоге получим:
// Пересчет из конца в начало
// Цикл по уровням
for (level = l - 2; level >= 0;level--)
{
// Цикл по узлам уровня
#pragma omp parallel for private(sum, i, rp)
for (j = 0; j < power[level]; j++)
{
// Для узла level,j подсчитываем expectation
sum = func(RobotTree[ index[level] + j ].value);
// Цикл по потомкам
for (i = 0; i < b; i++)
{
rp = RobotTree[ index[level+1] + b * j + i ];
sum = sum + rp.expectation * rp.probability;
}
RobotTree[ index[level] + j ].expectation = sum;
}
Проблема этого варианта состоит в том, что на каждой итерации внешнего цикла происходит "пробуждение" потоков в начале и "засыпание" в конце, что может плохо отразиться на производительности. Поэтому более правильным является вариант, в котором создание параллельной секции происходит один раз перед внешним циклом.
double GetExpectation(void)
{
int i, j, level;
double sum;
TreePart rp;
// Последний уровень
#pragma omp parallel for
for (j = 0; j < power[l-1]; j++)
RobotTree[j + index[l-1]].expectation =
func(RobotTree[j + index[l-1]].value);
#pragma omp parallel
{
// Пересчет из конца в начало
// Цикл по уровням
for (level = l - 2; level >= 0; level--)
{
// Цикл по узлам уровня
#pragma omp for private(sum, i, rp)
for (j = 0; j < power[level]; j++)
{
// Для узла level,j подсчитываем expectation
sum = func(RobotTree[ index[level] + j ].value);
// Цикл по потомкам
for (i = 0; i < b; i++)
{
rp = RobotTree[ index[level+1] + b * j + i ];
sum = sum + rp.expectation * rp.probability;
}
RobotTree[ index[level] + j ].expectation = sum;
}
}
}
return RobotTree[0].expectation;
}
Собрав проект в соответствии с рекомендациями, изложенными в Описании
(рис 11.19) Диагностика ITC в задаче о роботеРазвернув сообщения об ошибках, мы видим источник проблемы - гонки данных для переменной level. Действительно, предусмотрев локализацию при распараллеливании цикла, мы забыли об этом в директиве #. Исправим ошибку и приведем в заключение корректную реализацию.
double GetExpectation(void)
{
int i, j, level;
double sum;
TreePart rp;
// Последний уровень
#pragma omp parallel for
for (j = 0; j < power[l-1]; j++)
RobotTree[j + index[l-1]].expectation =
func(RobotTree[j + index[l-1]].value);
#pragma omp parallel private(level)
{
// Пересчет из конца в начало
// Цикл по уровням
for (level = l - 2; level >= 0; level--)
{
// Цикл по узлам уровня
#pragma omp for private(sum, i, rp)
for (j = 0; j < power[level]; j++)
{
// Для узла level,j подсчитываем expectation
sum = func(RobotTree[ index[level] + j ].value);
// Цикл по потомкам
for (i = 0; i < b; i++)
{
rp = RobotTree[ index[level+1] + b * j + i ];
sum = sum + rp.expectation * rp.probability;
}
RobotTree[ index[level] + j ].expectation = sum;
}
}
}
return RobotTree[0].expectation;
}
Code\MM ). Выполните отладку прилагаемых программ, добейтесь их работоспособности.Говорят "Любая программа содержит хотя бы одну ошибку". Применительно к параллельному программированию этот тезис можно переформулировать так "Параллельное программирование начинается с параллельных ошибок". Действительно, процесс создания параллельной программы, либо с нуля на основе
В настоящей лабораторной работе рассматривается один из инструментов отладки, основанный на сборе и автоматическом анализе информации по результатам выполнения программ и предназначенный для многопоточных и
В качестве полигона для демонстрации ошибок и возможностей инструментов по их поиску и анализу используются: классическая задача
Целью данной лабораторной работы является приобретение практических навыков отладки параллельных программ для систем с распределенной памятью, использующих для организации параллелизма либо механизм потоков, либо технологию
Данная цель предполагает решение следующих задач:
Данный документ состоит из введения, двух разделов, списка дополнительных заданий и списка литературы. Во введении обосновывается актуальность инструментальной поддержки в процессе отладки параллельных программ. В первом разделе приводятся методические рекомендации к лабораторной работе: формулируются цели и задачи, системные требования, рекомендации по проведению занятий. Во втором разделе изучается отладка параллельных программ с демонстрацией характерных ошибок и изучением методов их обнаружения и устранения. Изучение проводится на специально подобранных примерах. Для обнаружения ошибок используется инструмент отладки Intel Thread
В документации к
Минимальные требования
При практическом использовании ITС рекомендуются повышенные требования к минимально-необходимым аппаратным ресурсам (для достижения приемлемых показателей оперативности работы):
Для изучения всех аспектов "реальных" параллельных вычислений желательно использование многоядерных процессоров компании Intel.
Для анализа
При выполнении данной лабораторной работы рекомендуется придерживаться следующей последовательности изучения материала:
Задача
Итак, пусть имеются вектора $$a$$ и $$b$$ размерности $$n$$ (состоящие из $$n$$ элементов).
(рис 11.1) Скалярное произведение двух векторовТак, например, при умножении вектора $$a= (1,2,3)$$ на вектор $$b= (3,2,1)$$ получится, как нетрудно посчитать 10:
$$(1\ 2\ 3) \times \begin{pmatrix} 3\\2\\1 \end{pmatrix} = 1 * 3 + 2 * 2 + 3 * 1 = 10$$Алгоритм вычисления скалярного произведения полностью описывается его формулой, поэтому приведем сразу его код:
sum_all = 0;
for (i = 0; i < Size; i++)
{
sum_all += x[i] * y[i];
}
Необходимые объявления переменных, а также ввод данных здесь рассматривать не будем (см. проект
Алгоритм
Итак, мы имеем цикл с регулярной структурой и одинаковой вычислительной сложностью итераций. Распараллеливание его средствами
sum_all = 0;
#pragma omp parallel for
for (i = 0; i < N; i++)
{
sum_all += up[i] * vp[i];
}
Некоторый произвол возможен в том, как разделить вычисления между потоками. Первая схема - каждый поток обрабатывает непрерывный фрагмент умножаемых векторов. Вторая - вектора делятся между потоками поэлементно (или поблочно). Каждая схема может быть реализована с использованием параметра schedule. Провести соответствующие эксперименты предоставляем читателю самостоятельно.
В представленном выше коде мы сознательно допустили достаточно очевидную ошибку. Посмотрим, как с ней справится
Откройте проект
C:\ITCLabs\Scalar ,Scalar .slnПосле открытия проекта в окне Solution Explorer дважды щелкните на файле исходного кода Scalar.сpp. После этих действий программный код, с которым предстоит работать, будет открыт в
Далее выполните действия, описанные в пункте 7.3 документа "
И, наконец, запустите C:\ITCLabs\.
Нажмите кнопку Finish. После этого запустится
(рис 11.3) Результат анализа параллельной реализации 1 скалярного умноженияКак и следовало ожидать источник неприятностей - переменная sum_all, на что недвусмысленно указывает
Для исправления представленного выше кода требуется лишь одна модификация - переменная, в которую накапливается сумма, должна быть сделана локальной для каждого потока. В противном случае во избежание parallel for.
Вносим исправления:
sum_all = 0;
#pragma omp parallel for reduction(+:sum_all)
for (i = 0; i < N; i++)
{
sum_all += up[i] * vp[i];
}
Повторно запускаем активность в
(рис 11.4) Результат анализа параллельной реализации 1 после исправленияОтметим, что параметр
В дополнение рассмотрим еще один несколько искусственный вариант
Итак, пусть параллельная схема вычисления скалярного произведения выглядит следующим образом.
#pragma omp parallel private(rank, sum)
{
rank = omp_get_thread_num();
if (rank == 0)
{
NumThreads = omp_get_num_threads();
x = CreateVector(N);
y = CreateVector(N);
}
sum[rank] = 0;
#pragma omp for
for (i = 0; i < N; i++)
{
sum[rank] += x[i] * y[i];
}
}
sum_all = 0;
for (i = 0; i < NumThreads; i++)
{
sum_all += sum[i];
}
DeleteVector(x);
DeleteVector(y);
Нулевой поток "занимается" выделением памяти под данные и их инициализацией, после чего начинается собственно расчет. Представленная схема хоть и выглядит для задачи sum.
Попробуйте самостоятельно найти в представленном
Откройте проект Scalar2. Соберите программу в конфигурации debug. Прежде всего, посмотрим на результаты работы последовательной и параллельной версии. Зададим размер векторов равный 100 и запустим программу.
(рис 11.5) Результат запуска параллельной реализации 2Итак, результаты запуска однозначно указывают на некорректность параллельной версии. Приступаем к поиску ошибок.
Снова выполните действия, описанные в пункте 7.3 документа "C:\ITCLabs\Scalar2\Debug\Scalar2.exe.
Нажмите кнопку Finish. После этого запустится
(рис 11.6) Результат анализа параллельной реализации 2 скалярного умноженияПервое, что можно отметить - появились новые
"Открываем" ее двойным щелчком:
(рис 11.7) Просмотр диагностики "Use of unsupported API"Представленная диагностика вызвана тем, что omp_get_num_threads(). Отсюда, кстати, и большая часть остальных ошибок, которые вызваны тем, что значение переменной
Выходов из подобных ситуаций два: отказаться от использования run-time функций
Но прежде вернемся к ошибке под номером 9.
(рис 11.8) Неверная локализация переменной sumНесмотря на не слишком вразумительное сообщение, тем не менее, можно понять, что выше по коду нами допущена ошибка - переменная sum сделана private, что, конечно же, неверно. Этот массив специально был создан для подсчета потоками локальных сумм и естественно должен быть общим, чтобы по окончании параллельной секции из него в переменную sum_all можно было собрать итоговую сумму.
Исправляем ситуацию:
#pragma omp parallel private(rank/*, sum*/)
{
...
}
sum_all = 0;
for (i = 0; i < NumThreads; i++)
{
sum_all += sum[i];
}
DeleteVector(x);
DeleteVector(y);
Убираем ключ /Qtcheck из проекта и снова запускаем анализ в
(рис 11.9) Результат анализа параллельной реализации 2 после первого исправленияТеперь мы, к сожалению, потеряли информацию об именах переменных. Число сообщений также сократилось. Однако
Анализируя первое же сообщение, мы находим одну из типичных ошибок в многопоточных программах - использование потоками неинициализированных данных.
(рис 11.10) Ошибка - использование потоками неинициализированных данных Глядя на выделенные строки, нетрудно понять, что поток с номером, отличным от 0, будет пытаться использовать переменные x и y до того, как нулевой поток выделит под них память, что в лучшем случае приведет к падению, а в худшем к неверному результату расчетов. Решение в данной ситуации также является типичным и состоит в установке барьера после участка инициализации.
#pragma omp parallel private(rank)
{
rank = omp_get_thread_num();
if (rank == 0)
{
NumThreads = omp_get_num_threads();
x = CreateVector(N);
y = CreateVector(N);
}
sum[rank] = 0;
#pragma omp barrier
#pragma omp for
for (i = 0; i < N; i++)
{
sum[rank] += x[i] * y[i];
}
}
...
После внесения последних исправлений, результаты запуска полученной параллельной версии, наконец-то, совпадут с последовательным вариантом. Убедитесь в этом, а также в том, что
В качестве второго примера рассмотрим задачу из области численного
и принимающую на границе $$D^0$$ области $$D$$ значения $$g(x,y)$$.
Используя распространенный метод конечных разностей (он же метод сеток) перепишем уравнение Пуассона в конечно-разностной форме [11.9],
$$\cfrac{u_{i-1,j}+ u_{i+1,j} +u_{i,j+1}-4 u_{i,j}}{h^2}=f_{i,j}$$Разрешив его относительно $$u_{ij}$$, получим
$$u_{ij} = 0.25 (u_{i-1,j}+ u_{i+1,j} +u_{i,j+1}-h^2 f_{ij})$$Мы получили основу для построения итерационной схемы решения
Последовательная реализация данной итерационной схемы может выглядеть следующим образом:
do
{
dmax = 0;
for (i = 1; i < N - 1; i++)
{
for(j = 1; j < N - 1; j++)
{
temp = u[N * i + j];
u[N * i + j] = 0.25 * (u[N * i + j + 1] + u[N * i + j - 1] +
u[N * (i + 1) + j] + u[N * (i - 1) + j]);
dm = fabs(u[N * i + j] - temp);
if (dmax < dm)
dmax = dm;
}
}
}
while (dmax > EPS);
Здесь dmax есть максимальная разность между "старым", с предыдущей итерации, и "новым", посчитанным на текущей, значениями и используется для принятия решения об окончании расчетов.
"Сеточные" задачи, в которых решение получается выполнением набора из одних и тех же действий в каждом "узле" сетки обладают очень простой схемой распараллеливания. Достаточно сетку "порезать" на части: вертикально на столбцы, горизонтально на полосы, или и так и так, то есть на блоки, и распараллеливание выполнено. Если при этом объем вычислений, выполняемых в каждом узле, примерно одинаков, то и эффективность полученной параллельной реализации может быть довольно высока.
Таким образом, в данной работе мы рассмотрим две схемы распараллеливания решения
В данной лабораторной работе нашей целью не является производительность получаемых параллельных реализаций, поэтому в качестве первого варианта, как было сказано выше, мы используем вариант с максимальным параллелизмом, который в
do
{
dmax = 0;
#pragma omp parallel for
for (i = 1; i < N - 1; i++)
{
#pragma omp parallel for
for(j = 1; j < N - 1; j++)
{
temp = u[N * i + j];
u[N * i + j] = 0.25 * (u[N * i + j + 1] + u[N * i + j - 1] +
u[N * (i + 1) + j] + u[N * (i - 1) + j]);
dm = fabs(u[N * i + j] - temp);
if (dmax < dm)
dmax = dm;
}
}
}
while (dmax > EPS);
Конечно же, в представленном виде код является некорректным. В чем именно, нам предстоит выяснить, использую Intel Thread
Исследуем представленный выше код на наличие ошибок.
Для проверки правильности работы параллельной программы можно применить, казалось бы, естественный подход - сравнить результаты выполнения последовательной и параллельной версий. Например, в задаче
Рассматриваемый пример прекрасно демонстрирует описанные выше ситуации - вычислительная схема
Проанализируем код с помощью Intel Thread
(рис 11.11) Задача Дирихле - результат анализа параллельной реализации 1Как видим, налицо существенное количество ошибок, которые
"Разворачивая" любую из них, мы получим информацию вида:
(рис 11.12) Задача Дирихле - ошибка типа "гонка данных"Как видим, диагностика temp, когда два потока могут пытаться одновременно записать в нее значения.
Решение выявленных проблем зависит от того, как используется та или иная переменная и может состоять в ее "локализации", то есть создании внутренней для каждого потока копии, как для переменной temp, или в синхронизации доступа к ней, если переменная нужна всем потокам, как в случае с dmax.
Заметим, что две из найденных N. Какие именно, предлагаем читателям найти самостоятельно.
Корректируем код:
omp_lock_t dmax_lock;
omp_init_lock(dmax_lock);
do
{
dmax = 0;
#pragma omp parallel for
for (i = 1; i < N - 1; i++)
{
#pragma omp parallel for private(temp, dm)
for(j = 1; j < N - 1; j++)
{
temp = v[N * i + j];
v[N * i + j] = 0.25 * (v[N * i + j + 1] + v[N * i + j - 1] +
v[N * (i + 1) + j] + v[N * (i - 1) + j]);
dm = fabs(v[N * i + j] - temp);
omp_set_lock(dmax_lock);
if (dmax < dm)
dmax = dm;
omp_unset_lock(dmax_lock);
}
}
}
while (dmax > EPS);
omp_destroy_lock(dmax_lock);
По результатам запуска убеждаемся, что параллельная версия работает корректно. Снова запускаем Thread Checker и видим.
(рис 11.13) Задача Дирихле - результат анализа параллельной реализации 1 после исправленияПрав или нет
Второй вариант распараллеливания, который мы будем использовать в данной работе, состоит в уменьшении степени параллелизма реализации, что, тем не менее, ведет к увеличению эффективности. Вариант заключается в распараллеливании только внешнего цикла и дополнительно предполагает некоторые изменения в схеме подсчета значения dmax:
do
{
dmax = 0;
#pragma omp parallel for
for (i = 1; i < N - 1; i++)
{
dm = 0;
for(j = 1; j < N - 1; j++)
{
temp = u[N * i + j];
u[N * i + j] = 0.25 * (u[N * i + j + 1] + u[N * i + j - 1] +
u[N * (i + 1) + j] + u[N * (i - 1) + j]);
d = fabs(u[N * i + j] - temp);
if (dm < d)
dm = d;
}
if (dmax < dm)
dmax = dm;
}
}
while (dmax > EPS);
Как и в первом случае представленный код содержит ошибки, которые необходимо найти с помощью Intel Thread
Прежде всего, отметим, что в связи с изменившейся схемой работы и рассмотренная выше параллельная версия и данная могут не давать идентичные результаты по сравнению с последовательным кодом, что, конечно, является дополнительным усложняющим моментом для "ручной" отладки.
Проанализируем код с помощью Intel Thread
(рис 11.14) Задача Дирихле - результат анализа параллельной реализации 2Количество ошибок в этой версии еще больше в связи с увеличившимся количеством переменных, кроме того, в список попала переменная j, заботу о которой раньше "брал не себя" компилятор - как известно переменную цикла в директиве # не обязательно объявлять как private.
Также как и для варианта 1 исправление найденных ошибок заключается в локализации необходимых переменных и использовании синхронизации при работе с переменной dmax.
omp_lock_t dmax_lock;
omp_init_lock(dmax_lock);
do
{
dmax = 0;
#pragma omp parallel for private(j, temp, d, dm)
for (i = 1; i < N - 1; i++)
{
dm = 0;
for(j = 1; j < N - 1; j++)
{
temp = v[N * i + j];
v[N * i + j] = 0.25 * (v[N * i + j + 1] + v[N * i + j - 1] +
v[N * (i + 1) + j] + v[N * (i - 1) + j]);
d = fabs(u[N * i + j] - temp);
if (dm < d)
dm = d;
}
omp_set_lock(dmax_lock);
if (dmax < dm)
dmax = dm;
omp_unset_lock(dmax_lock);
}
}
while (dmax > EPS);
omp_destroy_lock(dmax_lock);
Снова запускаем
(рис 11.15) Задача Дирихле - результат анализа параллельной реализации 2 после исправленияКак и выше for при использовании директивы # без дополнительных параметров.
На примере данной классической задачи мы продемонстрируем еще одну типичную ошибку - тупик ( deadlock ), ее диагностику при помощи
Приведем вольную формулировку задачи Дейкстры: за круглым столом заседают 5 философов. Напротив каждого из них стоит блюдо со спагетти. Между каждыми двумя соседями расположена одна вилка. Философ может находиться в одном из двух состояний: ест, размышляет. При еде философу нужны 2 вилки (левая и правая).
Реализуем требуемый
Идея реализации состоит в следующем: главный поток создает дополнительные потоки в соответствии с количеством философов, запускает их и переходит в бесконечный цикл. Каждый из дополнительных потоков реализует поведение философа. При этом вилки предлагается моделировать при помощи
Сделаем следующие объявления:
// Количество философов
const unsigned int n = 5;
// Структура - описание философа
typedef struct
{
int iID; // Номер философа
HANDLE hMyObjects[2]; // Мьютексы (вилки)
} THREADCONTROLBLOCK, *PTHREADCONTROLBLOCK;
Приведем функцию потока. Используем функцию WaitForSingleObject для ожидания
long WINAPI ThreadRoutine(long lParam)
{
PTHREADCONTROLBLOCK pcb=(PTHREADCONTROLBLOCK)lParam;
while (TRUE)
{
WaitForSingleObject(pcb->hMyObjects[0],INFINITE);
WaitForSingleObject(pcb->hMyObjects[1],INFINITE);
printf("Eating: Philosopher %d \n",pcb->iID);
ReleaseMutex(pcb->hMyObjects[1]);
ReleaseMutex(pcb->hMyObjects[0]);
};
return (0);
}
Тогда функция main будет выглядеть так:
int main()
{
HANDLE hMutexes[n];
THREADCONTROLBLOCK tcb[n];
int iThreadID;
for (int i = 0; i < n; i++)
hMutexes[i] = CreateMutex(NULL, FALSE, NULL);
for (int i = 0; i < n; i++)
{
tcb[i].iID = i+1;
tcb[i].hMyObjects[0] = hMutexes[i % n];
tcb[i].hMyObjects[1] = hMutexes[(i+1) % n];
CloseHandle(CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)ThreadRoutine,
(void *)tcb[i],0,LPDWORD(iThreadID)));
}
while(TRUE);
return(0);
}
Запустим программу на выполнение несколько раз.
(рис 11.16) Задача об обедающих философах - результаты запуска параллельной реализации 1Результаты будут варьироваться от запуска к запуску. Единственное, что их объединяет, - неизменное зависание в некоторый момент. Попробуем разобраться, в чем дело. Прибегнем к помощи Intel Thread
(рис 11.17) Диагностика ITC в задаче об обедающих философах (параллельная реализация 1)
Подумаем над тем, как исключить тупики, наличие которых обуславливает не столько некорректная реализация, сколько сама постановка задачи. Действительно, возможна ситуация, в которой каждый из философов взял ровно одну вилку и ждет, когда освободится вторая, которая занята соседом. Сосед в свою очередь ждет свою вторую вилку и т.д.
Одним из возможных способов решения проблемы является изменение модели поведения философа. К примеру, можно наделить его обязанностью брать вилки одновременно, лишь тогда, когда обе они свободны. Изменения в программной реализации будут минимальны - достаточно заменить 2 вызова функции WaitForSingleObject на 1 вызов функции WaitForMultipleObjects для одновременного
#include <stdio.h>
#include <windows.h>
// Количество философов
const unsigned int n = 5;
typedef struct {
int iID;
HANDLE hMyObjects[2];
} THREADCONTROLBLOCK, *PTHREADCONTROLBLOCK;
long WINAPI ThreadRoutine(long lParam) {
PTHREADCONTROLBLOCK pcb=(PTHREADCONTROLBLOCK)lParam;
while (TRUE) {
WaitForMultipleObjects(2, pcb->hMyObjects, TRUE, INFINITE);
printf("Eating: Philosopher %d \n",pcb->iID);
ReleaseMutex(pcb->hMyObjects[1]);
ReleaseMutex(pcb->hMyObjects[0]);
};
return (0);
}
int main() {
HANDLE hMutexes[n];
THREADCONTROLBLOCK tcb[n];
int iThreadID;
for (int i = 0; i < n; i++)
hMutexes[i] = CreateMutex(NULL,FALSE,NULL);
for (int i = 0; i < n; i++) {
tcb[i].iID = i+1;
tcb[i].hMyObjects[0] = hMutexes[i % n];
tcb[i].hMyObjects[1] = hMutexes[(i+1) % n];
CloseHandle(CreateThread(NULL,0,(LPTHREAD_START_ROUTINE)ThreadRoutine,
(void *)tcb[i],0,LPDWORD(iThreadID)));
}
while(TRUE);
return(0);
}
Тестовые запуски подтверждают наши ожидания - программа перестала зависать.
Для постановки задачи рассмотрим некоторую "гипотетическую" лабораторию искусственного интеллекта, в которой выполняются работы по созданию роботов.
Для испытаний лабораторных образцов построен полигон, устроенный следующим образом: в начале полигона находится единственная дверь. Пройдя через нее, робот оказывается перед $$B$$ дверьми. Выбрав одну из дверей, робот вновь оказывается перед $$B$$ дверьми, и т.д. Пройдя через дверь, робот получает премию в размере $$x$$, где $$x$$ - количество монет, лежащее за данной дверью (для разных дверей количество монет может быть разным).
Считая известным:
следует определить среднюю премию, получаемую роботом при проходе через данный полигон.
Считать, что выполняются следующие условия: $$B\le20\le10$$
Объектом исследования в данной задаче является полигон с иерархической структурой, по которому по
Прежде всего, введем необходимые обозначения.
$$B$$, $$L$$, $$P_{L,L+1}^{ij}$$ и $$x_{L}^{i}$$ являются исходными данными для данной задачи. Из условия задачи вытекают следующие ограничения на исходные данные:
Теперь перейдем непосредственно к выбору модели. Вследствие иерархической структуры полигона выглядит разумным его представление в виде дерева степени $$B$$ и глубины $$L$$. При этом узлы дерева содержат значения $$x_{L}^{i}$$, а дугам приписаны
(рис 11.18) Модель полигона в задаче о роботе
Перейдем к описанию метода нахождения результата. Пусть $$E_d^i$$ - средняя премия, которая может быть получена, если робот начинает путь в узле $$i$$ уровня $$d$$.
Тогда
$$E_d^i= x_d^i + \sum_{i=0}^{B-1}{ P_{d,d+1}^{i,j} \times E_{d+1}^{i}, \text{где } d = \overline{0;l-2} ; i = \overline{0;B-1}} \\ E_{L-1}^i= x_{L-1}^i, \text{где } i = \overline{0;B-1}}$$Очевидный метод вычисления результата $$E_0^0$$ состоит в вычислении значений $$E$$ на последнем уровне дерева (второе соотношение) с последующим пересчетом из конца в начало (первое рекуррентное соотношение).
Перейдем к реализации последовательной версии изложенного выше метода решения.
Проектирование структур данных
Предусмотрим для
const int b = 10; // Степень дерева - B в постановке задачи
const int l = 7; // Количество уровней дерева
const int MAX_VALUE = 20; // Максимальное значение в вершине дерева
int NodesCount; // Количество узлов дерева = (1-b^l) / (1-b)
int BranchesCount; // Количество ветвей дерева = NodesCount - 1;
typedef struct // Узел дерева
{
int value; // Значение в узле
// Вероятность попадания в узел из узла предыдущего уровня
double probability;
// Компонент для подсчета среднего
double expectation;
} TreePart;
Учитывая регулярную структуру дерева, будем хранить его в виде массива узлов, располагая в нем узлы последовательно по уровням, от корня к листьям. Учитывая возможный большой размер массива, будем создавать его динамически в куче. В результате получим:
TreePart *RobotTree; // Массив для хранения дерева. // Схема хранения: // (V00) // (V10 V11 ... V1b) // (V21 V22... V2b^2) // ... // (Vl-1,1 Vl-1,2...Vl-1,b^(l-1)), // где скобки стоят для наглядности. // Дерево упаковывается в одномерный массив по уровням.
Для удобства индексации и снижения накладных расходов предусмотрим однократное вычисление значения b в степени от 0 до l-1, а также номеров первых узлов каждого уровня дерева в массиве RobotTree.
// Вспомогательный массив для хранения значений b в степени 0...l-1 __int64 power[l]; // Вспомогательный массив для хранения номера первого узла каждого уровня // в массиве RobotTree __int64 index[l];
Проектирование модульной структуры
Предусмотрим наличие в проекте файла
// Ввод дерева void InputTree(void); // Освобождение памяти, выделенной для хранения дерева void ReleaseTree(void); // Функция вычисления максимума __inline double max(double v1, double v2); // Функция вычисления премии по значению в узле __inline double func(double value); // Вычисление средней премии - основная расчетная функция double GetExpectation(void); // Головная функция int main(void);
Прокомментируем основные функции.
Функция InputTree предназначена для ввода исходных данных в соответствии с условием задачи. В этой функции вычисляется количество узлов и ветвей, выделяется память для хранения дерева, заполняются вспомогательные массивы power и index, инициализируется датчик случайных чисел и происходит
Функция func предназначена для обобщения задачи на случай, когда размер премии при открывании двери является некоторой функцией от x. В рассматриваемой сейчас постановке она просто возвращает значение x.
Функция GetExpectation рассчитывает средний размер премии по дереву при помощи описанного выше метода. Приведем ее реализацию:
// Вычисление среднего
// Алгоритм базируется на следующих соотношениях:
// E_l,i = СУММА по j=0__b-1 (Probability_l+1,j * E_l+1,j + value_l,i),
// где l - уровень, i - номер узла в уровне, l+1,j - узлы потомки узла l,i.
// Учитывая, что на последнем уровне E_l-1,i = Value_l-1,i
// Вычиляем рекуррентное соотношения из конца в начало.
// В итоге имеем сумму для нулевого узла - корня дерева
double GetExpectation(void)
{
// Последний уровень
int i, j, level;
double sum;
TreePart rp;
for (j = 0; j < power[l-1]; j++)
RobotTree[j + index[l-1]].expectation =
func(RobotTree[j + index[l-1]].value);
// Пересчет из конца в начало
// Цикл по уровням
for (level = l - 2; level >= 0; level--)
{
// Цикл по узлам уровня
for (j = 0; j < power[level]; j++)
{
// Для узла level, j подсчитываем expectation
// Цикл по потомкам
sum = func(RobotTree[ index[level] + j ].value);
for (i = 0; i < b; i++)
{
rp = RobotTree[ index[level+1] + b * j + i ];
sum = sum + rp.expectation * rp.probability;
}
RobotTree[ index[level] + j ].expectation = sum;
}
}
return RobotTree[0].expectation;
}
Рассмотрим возможный вариант распараллеливания предложенной выше последовательной реализации. Акцент сделаем на корректности реализации, а не на ее производительности, которая не является целью данной лабораторной работы. Приведем лишь одно соображение по поводу производительности. Поскольку метод решения задачи предполагает, что последний уровень дерева обсчитывается отдельно от остальных, начнем наше распараллеливание именно с него. Если подумать, можно обнаружить первый "подводный камень" этой задачи, связанный не с корректностью, но с производительностью разрабатываемой реализации. Легко допустить неточность, посчитав, что распараллеливание на последнем уровне можно опустить. Казалось бы, в чем смысл отдельной работы ради одного уровня? На самом деле смысл есть, поскольку последний уровень содержит наибольшее число узлов, и пренебрегать им при распараллеливании не стоит. Применим для распараллеливания обсчета #.
Соответствующий фрагмент кода будет выглядеть так:
#pragma omp parallel for
for (j = 0; j < power[l-1]; j++)
RobotTree[j + index[l-1]].expectation =
func(RobotTree[j + index[l-1]].value);
Заметим, что переменная j станет локализованной автоматически (согласно стандарту
Перейдем к распараллеливанию основного блока кода, производящего обсчет дерева.
Естественный вариант состоит в разделении всех узлов каждого уровня между потоками. Этого можно добиться по крайней мере двумя способами. Первый состоит в размещении директивы # перед циклом по узлам очередного уровня. В итоге получим:
// Пересчет из конца в начало
// Цикл по уровням
for (level = l - 2; level >= 0;level--)
{
// Цикл по узлам уровня
#pragma omp parallel for private(sum, i, rp)
for (j = 0; j < power[level]; j++)
{
// Для узла level,j подсчитываем expectation
sum = func(RobotTree[ index[level] + j ].value);
// Цикл по потомкам
for (i = 0; i < b; i++)
{
rp = RobotTree[ index[level+1] + b * j + i ];
sum = sum + rp.expectation * rp.probability;
}
RobotTree[ index[level] + j ].expectation = sum;
}
Проблема этого варианта состоит в том, что на каждой итерации внешнего цикла происходит "пробуждение" потоков в начале и "засыпание" в конце, что может плохо отразиться на производительности. Поэтому более правильным является вариант, в котором создание параллельной секции происходит один раз перед внешним циклом.
double GetExpectation(void)
{
int i, j, level;
double sum;
TreePart rp;
// Последний уровень
#pragma omp parallel for
for (j = 0; j < power[l-1]; j++)
RobotTree[j + index[l-1]].expectation =
func(RobotTree[j + index[l-1]].value);
#pragma omp parallel
{
// Пересчет из конца в начало
// Цикл по уровням
for (level = l - 2; level >= 0; level--)
{
// Цикл по узлам уровня
#pragma omp for private(sum, i, rp)
for (j = 0; j < power[level]; j++)
{
// Для узла level,j подсчитываем expectation
sum = func(RobotTree[ index[level] + j ].value);
// Цикл по потомкам
for (i = 0; i < b; i++)
{
rp = RobotTree[ index[level+1] + b * j + i ];
sum = sum + rp.expectation * rp.probability;
}
RobotTree[ index[level] + j ].expectation = sum;
}
}
}
return RobotTree[0].expectation;
}
Собрав проект в соответствии с рекомендациями, изложенными в Описании
(рис 11.19) Диагностика ITC в задаче о роботеРазвернув сообщения об ошибках, мы видим источник проблемы - гонки данных для переменной level. Действительно, предусмотрев локализацию при распараллеливании цикла, мы забыли об этом в директиве #. Исправим ошибку и приведем в заключение корректную реализацию.
double GetExpectation(void)
{
int i, j, level;
double sum;
TreePart rp;
// Последний уровень
#pragma omp parallel for
for (j = 0; j < power[l-1]; j++)
RobotTree[j + index[l-1]].expectation =
func(RobotTree[j + index[l-1]].value);
#pragma omp parallel private(level)
{
// Пересчет из конца в начало
// Цикл по уровням
for (level = l - 2; level >= 0; level--)
{
// Цикл по узлам уровня
#pragma omp for private(sum, i, rp)
for (j = 0; j < power[level]; j++)
{
// Для узла level,j подсчитываем expectation
sum = func(RobotTree[ index[level] + j ].value);
// Цикл по потомкам
for (i = 0; i < b; i++)
{
rp = RobotTree[ index[level+1] + b * j + i ];
sum = sum + rp.expectation * rp.probability;
}
RobotTree[ index[level] + j ].expectation = sum;
}
}
}
return RobotTree[0].expectation;
}
Code\MM ). Выполните отладку прилагаемых программ, добейтесь их работоспособности.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.