1

Создание метасистемы переходов от последовательных вычислений к распределенным и облачным вычислениям 2

1. Анализ методов построения и оптимизации реляционных схем и параллельных алгоритмов для распределенных вычислений и методов организации вычислений в облачных кластерах, инструментальных средств, предназначенных для формализованного представления алгоритмов. 2. Разработка метода оценки минимального количества необходимых процессоров для решения вычислительной задачи и определение совокупности метаданных, необходимых при принятии решения о модификации параллельного алгоритма с целью улучшения его эффективности. 3

3. Разработка методов оптимизации параллельного алгоритма по времени выполнения и числу процессоров по отдельности и в совокупности. 4. Разработка программного обеспечения для апробации полученных алгоритмов и методики их применения в зависимости от количественных характеристик параллельного алгоритма и параметров очередного шага оптимизации. 4

5. Построение онтологической модели облачного кластера и на ее основе разработка методов распределения параллельных программ между ролями-сотрудниками при организации облачных вычислений. 6. Разработка матричного представления операций реляционной алгебры с помощью аппарата теории графов и численных методов создания эффективных реляционных схем, обладающих необходимым внутренним параллелизмом. 5

высокопроизводительная вычислительная техника высокопроизводительная вычислительная техника программирование векторно-конвейерные компьютеры параллельные компьютеры с общей памятью параллельные компьютеры с распределенной памятью ЭВМ с кластерной архитектурой модель параллелизма данных модель параллелизма данных модель параллелизма задач задач 6

7 Орграфы в качестве объектов вместе с функторами в качестве морфизмов образуют категорию, обозначаемую через OGR. Переход от информационного графа к матрице или списку: и где: OGR – категория орграфов, М – прямоугольных разреженных матриц : pushout G1G1 L0L0 G0G0 L1L1 где: G 0,G 1 OGR, L 0,L 1 L.

8 1. Разбиение совокупности всех операций алгоритма на группы (построение параллельной формы) 2. Перемещение вершин между группами, оптимизация по числу процессоров где: G 0,G 1,G 2 OGR, L 0,L 1,L 2 L. G1G1 L1L1 G0G0 L0L0 L2L2 G2G2 H

Оценка минимальной ширины графа с учетом числа групп: d i - ширина i-й группы, m – число групп, S – высота графа, k – номер группы n вх – число входных вершин, N вых – число выходных вершин Разность между шириной графа и числом входных/выходных вершин Приращение плотности групп в зависимости от вх и вых d=n/s d=d+ d

Список смежности – совокупность пар смежных вершин (v i,v j ), где вершина v i является начальной вершиной, а вершина v j – конечной для ребра (v i,v j ) информационного графа G. V=V 1 -V 2 ={1,3,8} M 1 ={1,3,8} V=V 1 -V 2 ={2,4,6,9} M 2 ={2,4,6,9} V=V 1 -V 2 (V1,V2) (V1,V2) M 5 ={14}, V 21 (M 4 )={14}, V=M 5 V 21 (M 4 )={14} 2.2. V 23 (M 4 )={16}, V 22 (M 4 )={0} V=M 5 V 22 (M 4 )= V=M 5 V 23 (M 4 )= Если V=M i V 2j (M i-1 )=, то M i-1,j M i 10 M 1 ={1,3,8} M 2 ={2,4,6,9} M 3 ={15,5,10,12} M 4 ={7,11,13} M 5 ={14} M 6 ={16} M 1 ={1,3,8} M 2 ={2,4,6,9} M 3 ={5,10,12,15} M 4 ={7,11,13} M 5 ={14} M 6 ={16} 1.1.

Матрица смежностиСписки смежностиСписки следования M 1 ={1,3,8} M 2 ={4,6,9} M 3 ={10,12,2} M 4 ={7,5,15} M 5 ={14,11,13} M 6 ={16} M 1 ={1,3,8} M 2 ={4,6,9} M 3 ={10,12,2} M 4 ={7,5,15} M 5 ={14,11,13} M 6 ={16} M 1 ={1,3,8} M 2 ={4,6,9} M 3 ={10,12,2} M 4 ={7,5,15} M 5 ={14,11,13} M 6 ={16} M 1 ={1,3,8} M 2 ={4,6,9} M 3 ={10,12,2} M 4 ={7,5,15} M 5 ={14,11,13} M 6 ={16} M 1 ={1,3,8} M 2 ={9,4,6} M 3 ={2,10,12} M 4 ={7,13,15} M 5 ={14,5,11} M 6 ={16} M 1 ={1,3,8} M 2 ={9,4,6} M 3 ={2,10,12} M 4 ={7,13,15} M 5 ={14,5,11} M 6 ={16} Группы вершин Число проходов Трудоемкость О(n 2 ) 11

Насколько непрерывно работают все три задействованные в вычислительном процессе системе? Сколько времени простаивает каждый процессор в процессе работы алгоритма? Можно ли сократить общее время работы алгоритмы путем уменьшения времени простоев процессоров? Можно ли сократить ширину алгоритму путем уменьшения времени простоев процессоров за счет объединения мелких (по времени работы) операций в более крупные? D 1 1 B E G H F C A 1-й процессор 2-й процессор 3-й процессор 1 t n

D 1 1 B E G H F C A 1-й процессор 2-й процессор 3-й процессор 1 t n t n D E G H F C AВ 1-й процессор 2-й процессор 3-й процессор 1 t n D E G H F C AВ 1 1-й процессор 2-й процессор 13

1.t 0 =0 2.max(t 1j ) j=1..3 =3 t 0 = t 0 +3 t n j=2: t 12 =3, t=max-t 12 =3-3=0 j=3: t 13 =1, t=max-t 13 =3-1=2 2=t 21 t 13 = (t 21, t 13 ), t 21 =0 7 8 t n j=1: t 11 =2, t=max-t 11 =3-2=1 1=t 22 t 11 = (t 11, t 22 ), t 22 =0 3.max(t 2j ) j=1..3 =3 t 0 =t 0 +3=6 j=1: t 21 =0, t=max-t 21 =3-0=3 3>t 3i (i=1..3) t 21 = (t 21, t 31 ), t 31 =0 j=2: t 22 =0, t=max-t 22 =3-0=3 3>t 3i (i=1..3) t 22 = (t 22, t 32 ), t 32 =0 j=3: t 23 =3, t=max-t 23 =3-3=0 14

15 Диспетчер очереди Веб-роли Веб-сотрудники Хранилище Очередь запросов Диспетчер программ БД подпрограмм -распараллеливание отдельных программ; -определение числа ролей-сотрудников и времени, которое они будут заняты; -проектирование структуры базы данных и очереди запросов. ЗАДАЧИ

n t n t Схема решения задач по мере их поступления в очередь Схема решения задач с учетом их условий n t Схема решения задач при наличии Диспетчера программ 1 2 3

Модель организации без учета времени 3 {0,4,4,5,7} {2,4,5} 1 7 {6,3} {6,3,4} 4 {7,5} {6,3} 2 {7,5} (9) (6,7) (4,4,5,7) (9,10) (9) (12) Модель организации с учетом времени Параметр «Процесс» решения j-й задачи на n процессорах Параметр «Сроки» решения j-й задачи на n процессорах

Если запуск j-й задачи невозможен, то на графе для добавления i-й задачи следует вычеркнуть из множества R первые чисел и провести ребра к узлу с номером i от тех узлов, во множестве S которых есть вычеркнутые числа. Подписываем над ребрами соответствующие расписания. Время начала решения задачи будет вычисляться по правилу: 3. Если в очереди нет задач, то шаг 2. Иначе решается локальная задача: Пусть – время поступления i-й и j-й задач в очередь (i

Пусть: - облачный кластер содержит N процессоров; -массив «Очередь» содержит информацию о номерах задач, где М – размер очереди; -массив «Процесс» содержит информацию о номерах вычисляемых в настоящее время на облачном кластере задач; Значение S вычисляется по правилу:, где, t – время начала решения задачи. - величина К – число занятых в текущий момент процессоров. 19 Первая задача Пятая задача Время Число проц. Расписание

20

21 Запрос Описание Результат 1. Database_Programm and hasDispatcherProcess value Dicpatcher1 Какая программа выполняется в соответствии с расписанием Dicpatcher1 Programm Database_Programm and hasDispatcherProcess some (Dispatcher_Process and Number_Process value 1) Какая программа выполняется в соответствии с процессом 1 Programm1 3. Dispatcher_Process and hasDispatcherProcess some (hasProgramm some (Number_Task value 1)) По какому расписанию должна выполняться задача 1 Task1 4. Dispatcher_line and not (Wait_Task) Вывести список выполняемых задач Task3 5. Wait_Task and Enter_Time value " T15:00:00"^^dateTime Время поступления в очередь какой задачи равно " T15:00:00" Task1 6.Processors and solveTask some (Select_Task and Start_Time value " T16:00:00"^^dateTime) Какие процессоры начали работу в " T16:00:00" Processor1 Processor2 Processor3

22 Методы построения реляционных схем Методы построения параллельных алгоритмов Онтологическая модель процесса построения реляционных схем Параллельная реализация методов построения реляционных схем Онтологическая модель процесса организации облачных вычислений Методы организации облачных вычислений Теория графовАлгебра матриц Теория множеств

23 Правило 1. Если из узла А в узел В существует несколько путей: и, то следует удалить из орграфа дугу: Правило 2. Если из узла А в узел В существует несколько равных путей, В 1 и В 2 – предпоследние узлы в данных путях, то следует удалить из орграфа дугу: Правило 3. Если между узлами А и В существует контур: АВ, BА, то следует удалить из орграфа дугу:

Стягивание дерева – процесс преобразования фрагмента дерева в поддерево путем соединения нескольких последовательно идущих ребер в одной начальной вершине, для которой выполняется правило:. v2v2 v3v3 v4v4 v1v1 v1v1 v2v2 v3v3 v4v4 24 v1v1 v2v2 v3v3 v4v4 v5v5 v6v6 v1v1 v1v1 v2v2 v2v2 v3v3 v3v3 v4v4 v4v4 v5v5 v5v5 v6v6 v6v6 v7v7 v7v7 v8v8 v8v П р и м е р:

Заказы (заказа, заказчика, имя заказчика, улица, город, штат, индекс, фильма, название фильма, количество, срок) FD1: заказа заказчика, срок; FD2: заказчика имя; FD3: заказчика улица, индекс; FD4: индекс штат, город; FD5: улица город, штат, индекс; FD6: фильма название фильма; FD7: название фильма количество, срок; FD8: название фильма фильма; заказазаказчика срок имя улицаиндекс городштат название фильма количество S1 (заказа, фильма, название фильма, количество); S2 (заказа, заказчика, срок); S3 (заказчика, имя, улица, индекс). S4 (индекс, город, штат); S1 (заказа, фильма, название фильма, количество); S2 (заказа, заказчика, срок); S3 (заказчика, имя, улица, индекс). S4 (индекс, город, штат); заказазаказчика срок имя индекс городштат название фильма количество улица 25

Точка декомпозиции графа – узел, соответствующий атрибуту, который является граничным при делении отношения R=R1 R2, т.е. входит в качестве первичного ключа в отношение R1 и внешнего ключа в отношение R2. Точка сочленения является точкой декомпозиции, если она удовлетворяет следующим условиям: Точка сочленения орграфа – узел, удаление которого приведет к делению орграфа минимум на два связных орграфа. заказа заказчика срок имя улица индекс город штат название фильма фильма количество 2., т.е.является вершиной дерева орграфа функциональных зависимостей. 1., т.е. является хотя бы для одной дуги конечным узлом; 3. Поддерево с вершиной в точке декомпозиции является концевым поддеревом орграфа и не содержит в себе других поддеревьев. 26

зз-каимяулицагородштатиндексфНаз.фКол-восрок з з-ка индекс улица ф Наз. ф заказазаказчика срок имя улица город штат название фильма фильма количество индекс Строка декомпозиции матрицы смежности А – i-я строка, для которой выполняется условие: R i S j = для всех j: A ij 0, где R – множество атрибутов, входящих в название i-й строки, S – множество атрибутов, входящих в названия столбцов, на пересечении которых с i-й строкой стоят единицы. {индекс} {город, штат}= S1 (индекс, город, штат); S2 (индекс, фильма, название фильма, заказа, заказчика, срок, имя, количество, улица); 27

зз-каИмяулицаиндексфНаз.фКол-восрок з з-ка улица ф Наз. ф S1 (индекс, город, штат); S2(индекс, фильма, название фильма, заказа, заказчика, срок, имя, количество, улица); заказазаказчика срок имя улица название фильма фильма количество индекс

зз-каИмяулицаиндексфКол-восрок з з-ка Наз. ф S1 (индекс, город, штат); S2 (заказчика, имя, улица, индекс); S3(фильма, название фильма, заказа, заказчика, срок, количество). S1 (индекс, город, штат); S2(индекс, фильма, название фильма, заказа, заказчика, срок, имя, количество, улица); заказазаказчика срок имя улица название фильма фильма количество индекс заказазаказчика срок имя улица название фильма фильма количество индекс {з, з-ка, Наз.ф} {Имя, улица, индекс}=

30

31

32 Исследуемые технологические параметры IUGHQOэOэTf IуIу UуUу GуGу К.О.К.О. CaF 2 MgF 2 h ФРП N D e tокр Ef I U G H Q T f

33 x 1 =1*x 1 ; x 33 =1*x 33 ; x 65 =W 23 *x 39 ; x 2 =1*x 2 ; x 34 =1*x 34 ; x 66 =W 24 *x 40 ; x 3 =1*x 3 ; x 35 =1*x 35 ; x 67 =W 25 *x 41 ; x 4 =1*x 4 ; x 36 =1*x 36 ; x 68 =W 26 *x 42 ; x 5 =1*x 5 ; x 37 =1*x 37 ; x 69 =W 27 *x 9 ; x 6 =1*x 6 ; x 38 =1*x 38 ; x 70 =W 28 *x 10 ; x 7 =1*x 7 ; x 39 =1*x 39 ; x 71 =W 29 *x 11 ; x 8 =1*x 8 ; x 40 =1*x 40 ; x 72 =W 30 *x 12 ; x 9 =1*x 9 ; x 41 =1*x 41 ; x 73 =W 31 *x 13 ; x 10 =1*x 10 ; x 42 =1*x 42 ; x 74 =1*x 74 ; x 11 =1*x 11 ; x 43 =W 1 *x 17 ; x 75 =1*x 75 ; x 12 =1*x 12 ; x 44 =W 2 *x 18 ; x 76 =1*x 76 ; x 13 =1*x 13 ; x 45 =W 3 *x 19 ; x 77 =1*x 77 ; x 14 =1*x 14 ; x 46 =W 4 *x 20 ; x 78 =1*x 78 ; x 15 =1*x 15 ; x 47 =W 5 *x 21 ; x 79 =1*x 79 ; x 16 =1*x 16 ; x 48 =W 6 *x 22 ; x 80 =1*x 80 ; x 17 =1*x 17 ; x 49 =W 7 *x 23 ; x 81 =1*x 81 ; x 18 =1*x 18 ; x 50 =W 8 *x 24 ; x 82 =1*x 82 ; x 19 =1*x 19 ; x 51 =W 9 *x 25 ; x 83 =1*x 83 ; x 20 =1*x 20 ; x 52 =W 10 *x 26 ; x 84 =1*x 84 ; x 21 =1*x 21 ; x 53 =W 11 *x 27 ; x 85 =1*x 85 ; x 22 =1*x 22 ; x 54 =W 12 *x 28 ; x 86 =W 32 *x 78 ; x 23 =1*x 23 ; x 55 =W 13 *x 29 ; x 87 =W 33 *x 79 ; x 24 =1*x 24 ; x 56 =W 14 *x 30 ; x 88 =W 34 *x 80 ; x 25 =1*x 25 ; x 57 =W 15 *x 31 ; x 89 =W 35 *x 82 ; x 26 =1*x 26 ; x 58 =W 16 *x 32 ; x 90 =W 36 *x 83 ; x 27 =1*x 27 ; x 59 =W 17 *x 33 ; x 91 =W 37 *x 84 ; x 28 =1*x 28 ; x 60 =W 18 *x 34 ; x 92 =W 38 *x 85 ; x 29 =1*x 29 ; x 61 =W 19 *x 35 ; x 93 =1*x 93 ; x 30 =1*x 30 ; x 62 =W 20 *x 36 ; x 94 =1*x 94 ; x 31 =1*x 31 ; x 63 =W 21 *x 37 ; x 95 =W 38 *x 94 ; x 32 =1*x 32 ; x 64 =W 22 *x 38 ;

34

35 (1) (2)

36

37 Т=78ед.

38 Т=78ед. Т=168ед. Рис.1 Рис.2

1.Предложено представление функциональных зависимостей реляционных схем в матричном виде, и получены матричные аналоги свойств функциональных зависимостей. 2. Разработан метод построения реляционной схемы на основе атрибутов предметной области и декларированных функциональных зависимостей. Все получаемые схемы удовлетворяют нормальной форме Бойса-Кодда. 3. Разработан метод нахождения первичного ключа отношения на основе функциональных зависимостей. 5. Разработан метод приведения разреженной матрицы к треугольному виду с сохранением первоначальных значений элементов. 6. Разработан метод оптимизации информационного графа параллельного алгоритма по ширине, т.е. по числу процессоров, задействованных в решении поставленной прикладной задачи. Метод состоит из двух частей, которые могут применяться независимо друг от друга. 39

7. Получены оценки теоретической и практической минимальной ширины информационного графа, по которым можно принимать решение о дальнейшем его преобразовании. 8. Разработан метод оптимизации параллельного алгоритма по времени выполнения, позволяющий осуществить равномерную загрузку процессоров, сократить время решения поставленной задачи и уменьшить ширину информационного графа. 9. Разработан метод оптимизации информационного графа параллельного алгоритма по ширине, основанный на списках смежности. Метод состоит из двух частей, которые могут применяться независимо друг от друга. 10. Разработан метод оптимизации информационного графа параллельного алгоритма по ширине, основанный на списках следования. Метод обеспечивает равномерное заполнение групп и построен таким образом, что ширина каждого яруса будет приближена к теоретической минимальной ширине, никогда не превосходя ее. 11. Разработано программное обеспечение для апробации полученных методов и проведения дальнейших исследований в данной области. 40

12.Разработана онтологическая модель процесса построения реляционных схем на распределенных вычислительных системах, оптимального по нескольким параметрам. 13.Разработан метод построения детализированного взвешенного ориентированного графа распределения задач по ролям-сотрудникам при организации параллельных вычислений в облачном кластере. 14.Разработан формализованный алгоритм распределения задач по ролям- сотрудникам при облачных вычислениях, обладающий следующими характеристиками: возможность легкого переноса на любой императивный язык программирования и большой запас внутреннего параллелизма. 15.С помощью программы Protege 4.0 построена онтологическая модель облачного кластера, отражающая взаимосвязи между его составляющими и позволяющая с помощью dl-запросов получить информацию, необходимую для дальнейшего принятия решения о распределении очередной задачи из очереди. 41