Пять парадигм параллельного программирования

Основные разделы
Что такое параллельная программа?
Пять стилей параллельного программирования
Ноутбук как симметричная мультипроцессорная система (SMP)
Как писать параллельные программы?
Итеративный параллелизм и семафоры
Математическое моделирование параллельных вычислительных систем
Моноиды трасс и вычислительные процессы
Полукубические множества
Моноиды трасс и полукубические множества
Рекурсивный параллелизм
Конвейерные системы
Производители и потребители: каналы
Клиент-сервер: задача о читателях и писателях
Асинхронные системы
Асинхронные системы и кубические множества
Взаимодействующие каналы
Сети Петри и асинхронные системы
Топология – «резиновая» геометрия
Числа Бетти
Вычисление чисел Бетти
Числа Бетти полукубических множеств
Числа Бетти асинхронных систем
Числа Бетти сетей Петри
Открытые проблемы

Что такое параллельная программа?
Время вычисления суммы s=((a+b)+c)+d равно 3 такта
Для двух параллельно работающих процессоров существует программа, вычисляющая за 2 такта

Пять стилей параллельного программирования
Итеративный параллелизм
Рекурсивный параллелизм
Производители и потребители
Клиенты и серверы
Взаимодействующие каналы (или взаимодействующие равные)
Эндрюс Г.Р. Основы многопоточного, параллельного и распределенного программировния. – М.: Изд. дом «Вильямс», 2003

Ноутбук как симметричная мультипроцессорная система (SMP)
Архитектура SMP:

Как писать параллельные программы?
1. Разрабатываются подпрограммы, которые могут выполняться независимо. Например, для метода трассировки лучей пишется подпрограмма
DWORD WINAPI Part(void *a) {…}
выводящая точки в заданную прямоугольную область окна. Она вызывает для каждой точки прямоугольника функцию, зависящую от координат точки и от положения наблюдателя и вычисляющую цвет точки
Метод трассировки лучей описан в учебном пособии
Хусаинов А.А., Михайлова Н.Н. Программирование графики в Borland C++. – КнАГТУ, 2009.

Как писать параллельные программы?
Эта подпрограмма всегда имеет один аргумент типа (void *).
Если подпрограмма имеет несколько параметров, то они передаются через структуру. В частности для метода трассировки аргумент указывает на структуру, содержащую номер окна. При числе окон=10, номер = 0, …, 9:

Как писать параллельные программы?
Например:
struct arg
{
int ithr ; …
};
DWORD WINAPI Part(void *a)
{ int it=((arg *)a)->ithr; …
}
Эти подпрограммы вызываются главной программой, или подпрограммами, с помощью функции CreateThread(). Например, для метода трассировки лучей
for (i=0;i
{
a[i].ithr = i; H[i]=CreateThread(NULL,0,Part,(void *)(&a[i]),0,0);
}
for (i=0;i
Хусаинов А.А., Михайлова Н.Н. Архитектура вычислительных систем, 2007

Итеративный параллелизм и семафоры
Метод трассировки лучей реализуется с помощью цикла, в котором на каждом шаге вызывается некоторая подпрограмма, причем подпрограммы работают независимо.
Это позволяет нам запускать эти подпрограммы одновременно как потоки.
Поскольку число процессов намного меньше числа точек, то мы объединили части цикла в подпрограммы. И запускаем потоки параллельно.
К сожалению, экран не позволяет различным потокам выводить точки на экран одновременно
В частности, при числе потоков равном 4, мы получаем следующую картину:

Итеративный параллелизм и семафоры

Итеративный параллелизм и семафоры
Для того, чтобы исправить это, введем
Определение. Семафором Дейкстры называется структура данных, состоящая из неотрицательного числа s (счетчика семафора) и двух унарных операций P(s) и V(s).
Операция V(s) увеличивает s на 1.
Операция P(s) сначала зависает на то время, пока s = 0 . Когда будет выполнено условие s>0, P(s) отнимет от s единицу и продолжит выполнение.
Если имеется некоторый разделяемый ресурс, в данном случае экран, то, для того, чтобы в каждый момент времени им мог воспользоваться 1 поток, перед использованием нужно выполнить операцию P(s), а после использования – V(s). В начале работы главной программы s=1.
Вывод точки осуществляется с помощью операторов
WaitForSingleObject(sema,INFINITE); // операция P(s)
SetPixel(dc,x,y,color); // вывод на устройство dc
ReleaseSemaphore(sema, 1, NULL); // операция V(s)
Предварительно семафор создается с помощью вызова
Handle sema=CreateSemaphore(NULL,1,1,NULL);

Итеративный параллелизм и семафоры

Итеративный параллелизм и семафоры
Пример программы, в которой решается проблема сериализации. Рассмотрим задачу вычисления интеграла
равного площади фигуры ограниченной кривой y=1/(1+x2) и прямыми x=0; y=0; x=1.
Определим данные
volatile int j=0;
HANDLE mut;
double s=0;
Напишем подпрограмму добавления площади прямоугольника к сумме.
DWORD WINAPI sum(void* ps) // функция потоков
{
int *k = (int *)ps;
double w = (double)(1./(1.+(0. +(*k)) /n* (0. +(*k)) /n));
WaitForSingleObject(mut, INFINITE); // ждем освобождения s
s = s + w; j++; // прибавляем значение
ReleaseSemaphore(mut,1,NULL); // освобождаем s
return 1;
}

Итеративный параллелизм и семафоры
Напишем главную программу
main()
{
int i; int p[n];
for(i=0; i // для передачи номера потока
mut = CreateSemaphore(NULL,1,1,NULL); // создание мьютекса
for(i=0; i
{
CreateThread(NULL,0,sum, (void *) (&p[i]),0,0);
// параметр – номер из {0, …, n-1}
}
while (j
cout << “\nValue obtained by threads = ” << s; // результат
}
Результат выполнения программы будет близок к π/4.

Математическое моделирование параллельных вычислительных систем
При синхронизации работы потоков с помощью семафоров возникают проблемы, связанные с обнаружением тупиков и описанием пространства состояний вычислительного процесса. Рассмотрим, например, два потока, с двумя семафорами s1 и s2.
Первый из них, поток A, вызывает операции
P(s1); P(s2); V(s2); V(s1)
Второй, поток B, -
P(s2); P(s1); V(s1); V(s2)

Математическое моделирование параллельных вычислительных систем
Рассмотрим математическую модель
состоящую из множества состояний, заданных парами точек плоскости (t1,t2), где ti – доля выполнения i-го потока. Область F будет состоять из тупиков, область G – из недоступных точек. В общем случае возникают
Направленные топологические пространства
Автоматы высших размерностей.

Математическое моделирование параллельных вычислительных систем
Категория состоит из объектов A,B,C, …
и морфизмов , , , …
Для любых морфизмов и задана композиция такая, что имеет место
γ(βα) = (γβ)α
Для каждого объекта задан тождественный морфизм 1A: A→A такой, что α 1A =α, 1Bα=α
Функтор между категориями сопоставляет объектам - объекты, морфизмам – морфизмы, он переводит тождественные морфизмы в тождественные, композицию – в композицию.

Математическое моделирование параллельных вычислительных систем
Пусть U: A →B - функтор. Объект A называется универсальным для B ∈B, если задан морфизм η: B → U(A) такой, что для любого η’: B → U(A’) ∃! α: A→A’, для которого U(α)η= η’.
Примеры: Пополнение метрического пространства является универсальным объектом. Пополнением пространства рациональных чисел будет пространство вещественных чисел. Универсальным объектом для любого множества E по отношению к забывающему функтору Vect → Set будет линейное пространство с базисом E.
Как связаны между собой категории моделей вычислительных систем?

Полукубические множества

Полукубические множества

Моноиды трасс и вычислительные процессы
Что такое вычислительный процесс?
Рассмотрим вычислительную систему, состоящую из операций
Определение. Пусть E – мн-во, I ⊆ExE – наз отношением независимости, если I антирефлексивно и симметрично
M(E,I)=〈E | ∀(a,b) ∈I (ab=ba)〉 - свободный частично-коммутативный моноид или моноид трасс
Граф независимости: вершины E, ребра {{a,b}:(a,b) ∈I}
Операции вычислительной системы порождают свободный частично коммутативный моноид. Вычислительный процесс – композиция этих операций. Язык Мазуркевича состоит из независающих вычислительных процессов.

Моноиды трасс и полукубические множества
Теорема 1. Каждому полукубическому множеству с выделенной вершиной соответствует универсальный моноид трасс
Соответствующий моноид будет порожден ребрами - 1-кубиками. Перестановочны соседние ребра из 2-кубиков. Отождествляются противоположные.
Эта теорема позволяет определить сохраняющие независимость морфизмы полукубических множеств.

Рекурсивный параллелизм
Метод сдваивания
int sum(int l, int r) // x[l] + … + x[r]
{
if(l == r) return x[l];
else return sum(l, (l + r + 1)/2 - 1) + sum((l + r + 1)/2, r);
}

Рекурсивный параллелизм
Данные и структура параметров
int x[100]; struct arg {int l, r, res};
Вызываемый поток
DWORD WINAPI sum(void* s)
{
int i, l=((arg *)s)->l, r=((arg *)s)->r;
if (l==r) ((arg *)s)->rez = x[l]; // результат
else
{// в противном случае вызываем два потока с разными аргументами
arg *r1 = new arg, *r2 = new arg;
HANDLE H[2];
r1->l=l; r1->r= (l+r+1)/2-1; r2->l=(l+r+1)/2; r2->r = r; H[0]= CreateThread(0,0,sum, (void *)r1,0,0);
H[1]= CreateThread(0,0,sum, (void *)r2,0,0);
WaitForMultipleObjects(2, H, 1, INFINITE);
((arg *)s)->rez = (r1->rez)+(r2->rez);
delete r1; delete r2;
} return 1;
}
Вызов из главной программы
arg t; t.l = 0; t.r = 99; sum(&t);

Рекурсивный параллелизм
Рекурсивный параллелизм применяется для распараллеливания алгоритма перебора с возвратом
И.А. Трещев установил в программе счетчик, для определения, нужно ли загружать поток, если существуют свободные процессоры, или вызывать этот модуль как рекурсивную подпрограмму. Оказалось, что наибольшее ускорение достигается при числе потоков, большем, чем число процессоров.

Конвейерные системы
Рассмотрим вычислительную систему для вычисления суммы векторов. Она состоит из 5 микроопераций
Comp(a,b) – сравнение порядков
Shift(a,b) – сдвиг мантиссы большего числа
Add(a,b) – сложение мантисс
Norm(a,b) – нормализация
Round(a,b) – округление результата
Для сложения двух векторов (a1, …,an) и (b1, …,bn) в 1-й такт выполняется Comp(a1,b1), во 2-й Comp(a2,b2) Shift(a1,b1) и т.д. :

Конвейерные системы
Ускорение S5=T1/T5=5nh/((n+4)h) ≈ 5

Производители и потребители: каналы
template
class channel
{
Type *buf; // буфер для очереди
int size; HANDLE s, // семафор доступа к очереди
empty, full; // число свободных и заполненных мест в очереди
int countr, countw; // счетчики чтения и записи
public:
channel (int n): size(n) // constructor
{
buf = new Type [n];
countr=0; countw=0;
s=CreateSemaphore(NULL,1,1,NULL); //
empty=CreateSemaphore(NULL,n,n,NULL); // n свободных мест
full=CreateSemaphore(NULL,0,n,NULL); // no full places
}
void operator << (Type d) // запись в канал
{
WaitForSingleObject(empty, INFINITE); // ждем своб мест
WaitForSingleObject(s, INFINITE); // захват буфера
buf[countw++]=d; // запись в очередь
if (countw==size) countw=0;
ReleaseSemaphore(s,1,NULL);
ReleaseSemaphore(full,1,NULL); // full++
}
void operator >> (Type& d) // чтение из канала
{
WaitForSingleObject(full, INFINITE); // ждем поступления данных
WaitForSingleObject(s, INFINITE); // захват буфера
d = buf[countr]; countr++; // чтение из очереди
if (countw==size) countw=0;
ReleaseSemaphore(s,1,NULL);
ReleaseSemaphore(empty,1,NULL); // empty++
}
};

Производители и потребители: каналы
С помощью каналов можно реализовать конвейерные системы.
Блок конвейера
DWORD WINAPI name_op(void *)
{
Type d;
while(1)
{
ch[in]>>d; ch[out]<
}
}
Класс channel был разработан в препринте
Husainov A.A. The study of distributed computing algorithms by multithread applications // Preprint, Cornell Univ. 2004. 17 pp. http://arxiv.org/abs/cs.DC/0404015

Клиент-сервер: задача о читателях и писателях
Процессы читают и редактируют файл
Имеющие право на чтение – читатели
На чтение-запись – писатели
Писатель может работать только один
Читателей может быть несколько
Писатели имеют приоритет перед читателями – если писатель поступил, то читатели не могут работать
Поступивший писатель становится в очередь
Элементы параллельного программирования / под ред. В.Е. Котова – М.: Радио и связь, 1983

Асинхронные системы
T=(S,s0,E,I,Tran)
S – множество состояний,
s0∈ S – начальное состояние,
E – множество событий,
Tran ⊆ S×E×S – множество переходов
I⊂E×E – антирефлексивное симметричное
отношение независимости
(∀ a∈E ∃ s, s’ ∈ S) (s,a,s’) ∈ Tran
(s,a,s’ ) ∈ Tran & (s,a,s’’ )∈ Tran ⇒ s’ = s’’
(a,b) ∈ I & (s,a,t) ∈ Tran & (t,b,u) ∈ Tran ⇒
(∃ v ∈ S) (s,b,v) ∈ Tran & (v,a,u) ∈ Tran
Пунктированное множество с действием свободного частично коммутативного моноида

Асинхронные системы
a – читатель поступил доступ
b – читатель закончил работу с файлом
c – поступил новый писатель
d – писатель закончил работу с файлом

Асинхронные системы и кубические множества
Теорема 2. Каждой асинхронной системе соответствует некоторое кубическое множество. И наоборот, каждому пунктированному кубическому множеству соответствует универсальная асинхронная система.

Асинхронные системы и кубические множества
Асинхронным системам соответствуют также полиэдры – топологические пространства, склеенные из точек, отрезков, треугольников и т.д.
Топологическим свойствам асинхронных систем посвящена статья
Хусаинов А.А., Лопаткин В.Е., Трещев И.А. Исследование математической модели параллельных вычислительных систем методами алгебраической топологии // Сиб.ЖИМ №1, с. 141-151 (2008)

Взаимодействующие каналы
Сеть Петри волновой системы: xn=un+sin(vn*vn), yn=exp(sin(un-vn))

Взаимодействующие каналы
Сеть Петри волновой системы: xn=un+sin(vn*vn), yn=exp(sin(un-vn))

Взаимодействующие каналы
Сеть Петри волновой системы: xn=un+sin(vn*vn), yn=exp(sin(un-vn))

Взаимодействующие каналы
Сеть Петри волновой системы: xn=un+sin(vn*vn), yn=exp(sin(un-vn))

Взаимодействующие каналы
Сеть Петри волновой системы: xn=un+sin(vn*vn), yn=exp(sin(un-vn))

Взаимодействующие каналы
Сеть Петри волновой системы: xn=un+sin(vn*vn), yn=exp(sin(un-vn))

Взаимодействующие каналы
Сеть Петри волновой системы: xn=un+sin(vn*vn), yn=exp(sin(un-vn))

Взаимодействующие каналы
Каналы, соответствующие местам
channel *pc[11];
Подпрограмма потока
DWORD WINAPI mult(LPVOID) // поток для умножения
{
int j;
double d1, d2;
for (j=0; j
{
*pc[0]>>d1; *pc[1]>>d2; // прием данных из каналов 0 и 1
*pc[4]<<(d1*d2); // умножение и отправление в канал 4
}
return 1;
}

Взаимодействующие каналы
Полученные «асинхронные систолические системы» называются волновыми системами
Более точная математическая модель волновой системы, чем сеть Петри, была разработана и применена для оценки ускорения в диссертации
И.А. Трещев «МАТЕМАТИЧЕСКИЕ МОДЕЛИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ И ИХ ПРИМЕНЕНИЕ ДЛЯ ПОСТРОЕНИЯ МНОГОПОТОЧНЫХ ПРИЛОЖЕНИЙ НА СИСТЕМАХ С SMP-АРХИТЕКТУРОЙ »

Сети Петри и асинхронные системы
Пример
a
b
c
a
b
c
p0
p1
M(E,I)= 〈a,b,c| ac=ca〉

Топология – «резиновая» геометрия (изучает инварианты гомеоморфизмов)
Каждой дырке соответствует цикл, не являющийся границей подобласти. В данном случае существует 1-мерный цикл
не ограничивающий подобласть
Кольцо
{(x,y): r2 ≤ x2+y2 ≤ R2 }
цикл≠0
цикл=0
Числа Бетти

Числа Бетти.
Резиновый мяч. Любой 1-мерный цикл является границей поверхности, содержащейся в области {(x,y,z): r2 ≤ x2+y2 +z2 ≤ R2 } .
В данном случае существует 2-мерный цикл, окружающий дырку, и поэтому не являющийся границей.
β1 = 0, β2 = 1

Числа Бетти
Сn= L{(x0,x1, …, xn) – симплекс: x0 < x1<…< xn }
Zn=dn-1(0), Bn=dn+1Cn+1
Hn=Zn/Bn
βn=dim Cn- r(dn)-r(dn+1)
Разбиваем фигуру на треугольники, тетраэдры, …, n-симплексы (x0, …, xn)
Цепи – суммы n-симплексов
.

Числа Бетти
.
β0=3-0-r(d1)=3-2=1, β1=3-r(d1)-0=1
2-цепей нет ⇒ цикл 01+12-02 ≠ 0

Вычисление чисел Бетти
βn= dim Cn – r( dn )– r (dn+1)
С0 = L{0,1,2,3} ≈ Q4 ,
С1 = L{01,02, 03,12,13, 23} ≈ Q6 ,
С2 = L{012,013, 023, 123} ≈ Q4
rank d1=3, rank d2=3 ⇒ β0=1, β1= 0, β2=1.

Числа Бетти полукубических множеств
d1=
d2=

Числа Бетти асинхронных систем
S0=S∪{*}, S1={(s,e1): s∈S0,e1 ∈E}, … ,
Sn= {(s, e1 , …, en): s∈S0,e1 <…< en ∈E, (ei, ej ) ∈I, при 1≤ i< j ≤ n}
Предложение. Числа Бетти асинхронной системы вычисляются с помощью комплекса
В частности

Числа Бетти асинхронных систем
rk d1 = 3
β0=4-3=1 , β 1=8-3-3=2 , β 2=4-3=1
rk d2 = 3

Числа Бетти асинхронных систем
28 октября (четверг), в 12.00, в 201/3 состоится защита диссертации В.Е. Лопаткина «Исследование математических моделей параллельных вычислительных систем методами алгебраической топологии», в ней развиваются
Приложения чисел Бетти для нахождения признаков распараллеливаемости
Другие инварианты: группы гомологий асинхронных систем, кольца когомологий автоматов высших размерностей и их свойства

Числа Бетти сетей Петри
2 подхода к определению чисел Бетти сетей Петри:
Сети Петри сопоставляется асинхронная система и вычисляются ее числа Бетти (Husainov A.A. Homology of small categories and asynchronous transition systems // Homology, Homotopy and Applications 2004). В качестве примера, вычислены числа Бетти конвейера из трех переходов
Для сети Петри и отношения независимости между переходами строятся 2 частично-упорядоченных множества и вычисляются числа Бетти этих множеств (А.Д. Гринблат, Е.А. Хусаинова)

Числа Бетти сетей Петри