glava3 4 (Лобусов Е.С. Теоретические основы параллельных вычислений), страница 2
Описание файла
Файл "glava3+4" внутри архива находится в следующих папках: Лобусов Е.С. Теоретические основы параллельных вычислений, Теоретические основы. Документ из архива "Лобусов Е.С. Теоретические основы параллельных вычислений", который расположен в категории "". Всё это находится в предмете "параллельное программирование" из 10 семестр (2 семестр магистратуры), которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "книги и методические указания", в предмете "параллельное программирование" в общих файлах.
Онлайн просмотр документа "glava3 4"
Текст 2 страницы из документа "glava3 4"
Вычислительная загрузка является линейной функцией от распределения S.
Определим также и коммуникационную загрузку каждого процессора clj(S) в размерности времени
Коммуникационная загрузка в отличие от вычислительной уже нелинейная функция от распределения S.
Знание вычислительной и коммуникационной загрузок позволяет задать различные функционалы качества J, например,
где - некоторый скаляр.
Нетрудно видеть, что функционал качества (18) - модификация функционала качества (11).
Покажем более детально, каким образом выбрать метод решения, обеспечивающий оптимальное нахождение распределения компонент алгоритма по сети процессоров, то есть нахождение матрицы S. Оптимальность распределения трактуется в смысле минимизации выбранного функционала качества (18).
при наличии 2-х типов ограничений:
а wlj и clj даются зависимостями (16) и (17).
Эта задача нахождения минимума характеризуется нелинейным функционалом (19) и линейными ограничениями (20) и поэтому является, в общем, задачей нелинейного программирования.
Примем сначала скаляр = 0, то есть распределение зависит только от вычислительной загрузки, то есть
Такое предположение оправдано, если априорно предполагается превышение вычислительной нагрузки над коммуникационной или большая величина отношения (2).
Введем бинарные одноиндексные переменные {xk} и преобразуем постановку задачи распределения к следующему виду
где xn (j-1)+i sji ; 0 ; Re ; xn (j-1)+i = {0,1}; X = {xk}, k=1,nm .
Преобразуем все уравнения неравенства к уравнениям равенствам. Это делается стандартным приемом добавления новых переменных. Поэтому имеем
Дополнительные переменные x(n+1)m+j , x(n+2)m+1 – являются вещественными.
В такой формальной постановке задача (22) соответствует так называемой задаче смешанного булева линейного программирования, имеющей общее число переменных (n + 2)m + 1 (из них nm - булевых ) и 2m + n ограничений типа равенства.
Оказывается, что при 0 задача также сводится к смешанному булеву линейному программированию. Покажем эту процедуру сведения.
Так как в выражении для коммуникационной загрузки (17) входят парные произведения sjksil , то множество этих парных произведений образует таблицу П определенного вида размера m2n2. Всевозможные парные произведения принадлежащие какой-либо -й расширенной строке, состоящей из m строк, формируют коммуникационную загрузку -го процессора.
Таблица П
1 | { | (11,11)(11,12)(11,13)...(11,1n) (21,11)(21,12)(21,13)...(21,1n) (31,11)(31,12)(31,13)...(31,1n) - - - - - - - - - - - - - - - - (m1,11)(m1,12)(m1,13)...(m1,1n) | (12,11)(12,12)(12,13)...(12,1n) (22,11)(22,12)(22,13)...(22,1n) (32,11)(32,12)(32,13)...(32,1n) - - - - - - - - - - - - - - - - (m2,11)(m2,12)(m2,13)...(m2,1n) | - | (1n,11)(1n,12)(1n,13)...(1n,1n) (2n,11)(2n,12)(2n,13)...(2n,1n) (3n,11)(3n,12)(3n,13)...(3n,1n) - - - - - - - - - - - - - - - - (mn,11)(mn,12)(mn,13)...(mn,1n) |
2 | { | (11,21)(11,22)(11,23)...(11,2n) (21,21)(21,22)(21,23)...(21,2n) (31,21)(31,22)(31,23)...(31,2n) - - - - - - - - - - - - - - - - (m1,21)(m1,22)(m1,23)...(m1,2n) | (12,21)(12,22)(12,23)...(12,2n) (22,21)(22,22)(22,23)...(22,2n) (32,21)(32,22)(32,23)...(32,2n) - - - - - - - - - - - - - - - - (m2,21)(m2,22)(m2,23)...(m2,2n) | - | (1n,21)(1n,22)(1n,23)...(1n,2n) (2n,21)(2n,22)(2n,23)...(2n,2n) (3n,21)(3n,22)(3n,23)...(3n,2n) - - - - - - - - - - - - - - - - (mn,21)(mn,22)(mn,23)...(mn,2n) |
3 | { | (11,31)(11,32)(11,33)...(11,3n) (21,31)(21,32)(21,33)...(21,3n) (31,31)(31,32)(31,33)...(31,3n) - - - - - - - - - - - - - - - - (m1,31)(m1,32)(m1,33)...(m1,3n) | (12,31)(12,32)(12,33)...(12,3n) (22,31)(22,32)(22,33)...(22,3n) (32,31)(32,32)(32,33)...(32,3n) - - - - - - - - - - - - - - - - (m2,31)(m2,32)(m2,33)...(m2,3n) | - | (1n,31)(1n,32)(1n,33)...(1n,3n) (2n,31)(2n,32)(2n,33)...(2n,3n) (3n,31)(3n,32)(3n,33)...(3n,3n) - - - - - - - - - - - - - - - - (mn,31)(mn,32)(mn,33)...(mn,3n) |
{ | - - - - - - - - - - - - - - - - - - - - - - - - | - - - - - - - - - - - - - - - - - - - - - - - - | - | - - - - - - - - - - - - - - - - - - - - - - - - | |
m | { | (11,m1)(11,m2)(11,m3)...(11,mn) (21,m1)(21,m2)(21,m3)...(21,mn) (31,m1)(31,m2)(31,m3)...(31,mn) - - - - - - - - - - - - - - - - (m1,m1)(m1,m2)(m1,m3)...(m1,mn) | (12,m1)(12,m2)(12,m3)...(12,mn) (22,m1)(22,m2)(22,m3)...(22,mn) (32,m1)(32,m2)(32,m3)...(32,mn) - - - - - - - - - - - - - - - - (m2,m1)(m2,m2)(m2,m3)...(m2,mn) | - - | (1n,m1)(1n,m2)(1n,m3)...(1n,mn) (2n,m1)(2n,m2)(2n,m3)...(2n,mn) (3n,m1)(3n,m2)(3n,m3)...(3n,mn) - - - - - - - - - - - - - - - - (mn,m1)(mn,m2)(mn,m3)...(mn,mn) |
Определим новые бинарные переменные со сложными индексами , z, , которые соответствуют каждому элементу таблицы П, то есть
s11 s11 = z11,11 ; s11 s12 = z11,12 ; . . . ; s1n s1n = z11,nn ;
s21 s11 = z12,11 ; s21 s12 = z12,12 ; . . . ; s2n s1n = z12,nn ;
. . . . . . . . . . . . . . . . . . . . . . . . . . .
и так далее до smn smn = zmn,nn ;
интерпретация введенных индексов , показана на рис.3.2, где таблица П заштрихована.
В новых переменных выражения для загрузок (16), (17) и ограничений (20) принимает вид
(обозначения = 1, n2 и = 1, m2 означает, что индексы и , и принимают последовательно все свои значения).
Интерпретация двойных индексов
индекс | индекс | порядко-вый номер | |||||
1 | 1 . . . m | 1 . . . m | . . . . . | ||||
2 | 1 . . . m | m+1 . . . 2m | . . . . . | ||||
. . . | . . . | . . . | . . . . . | . . . . . | . . . . . | . . . . . | |
m | 1 . . . m | (m+1)m+1 . . . m2 | . . . . . | ||||
1 . . . n | (n+1). . .2 n | (n-1)n+1. . . . . . n2 | порядковый номер | ||||
1 . . . n | 1 . . . n | 1 . . . n | индекс | ||||
1 | 2 | n | индекс |
Рис.3.2
Добавляя теперь еще ограничения
и образуя критерий имеем также задачу смешанного булева программирования.
Целесообразно также включить в число ограничений и выполнение соотношения (2), то есть