'

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

Понравилась презентация – покажи это...





Слайд 0

1 Пять парадигм параллельного программирования Хусаинов Ахмет Аксанович husainov51@yandex.ru http://husainov51.narod.ru


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


Слайд 5

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


Слайд 6

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


Слайд 7

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


Слайд 8

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


Слайд 9

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


Слайд 10

11 Итеративный параллелизм и семафоры Для того, чтобы исправить это, введем Определение. Семафором Дейкстры называется структура данных, состоящая из неотрицательного числа 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);


Слайд 11

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


Слайд 12

13 Итеративный параллелизм и семафоры Пример программы, в которой решается проблема сериализации. Рассмотрим задачу вычисления интеграла равного площади фигуры ограниченной кривой 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; }


Слайд 13

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


Слайд 14

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


Слайд 15

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


Слайд 16

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


Слайд 17

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


Слайд 18

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


Слайд 19

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


Слайд 20

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


Слайд 21

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


Слайд 22

23 Рекурсивный параллелизм Метод сдваивания 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); }


Слайд 23

24 Рекурсивный параллелизм Данные и структура параметров 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);


Слайд 24

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


Слайд 25

26 Конвейерные системы Рассмотрим вычислительную систему для вычисления суммы векторов. Она состоит из 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) и т.д. :


Слайд 26

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


Слайд 27

28 Производители и потребители: каналы template<class Type> 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++ } };


Слайд 28

29 Производители и потребители: каналы С помощью каналов можно реализовать конвейерные системы. Блок конвейера DWORD WINAPI name_op(void *) { Type d; while(1) { ch[in]>>d; ch[out]<<op(d); } } Класс 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


Слайд 29

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


Слайд 30

31 Асинхронные системы 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 Пунктированное множество с действием свободного частично коммутативного моноида


Слайд 31

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


Слайд 32

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


Слайд 33

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


Слайд 34

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


Слайд 35

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


Слайд 36

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


Слайд 37

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


Слайд 38

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


Слайд 39

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


Слайд 40

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


Слайд 41

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


Слайд 42

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


Слайд 43

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


Слайд 44

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


Слайд 45

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


Слайд 46

47 Числа Бетти С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-симплексов .


Слайд 47

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


Слайд 48

49 Вычисление чисел Бетти ?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.


Слайд 49

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


Слайд 50

51 Числа Бетти асинхронных систем 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} Предложение. Числа Бетти асинхронной системы вычисляются с помощью комплекса В частности


Слайд 51

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


Слайд 52

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


Слайд 53

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


Слайд 54

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


Слайд 55

56 Открытые проблемы Разработать метод построения многопоточ-ного приложения по асинхронной системе Доказать, что первая группа гомологий асинхронной системы не имеет кручения Могут ли иметь кручение группы гомологий асинхронной системы элементарной сети Петри? Найти признаки разложимости асинхронной системы переходов в параллельную композицию взаимодействующих вычислительных процессов


×

HTML:





Ссылка: