Пупков К.А., Коньков В.Г. Интеллектуальные системы (1-е изд., 2001) (1245264), страница 31

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 31)

При этом предполагается, что исходные процессы уже могутисполняться в параллельном режиме. Но сама процедура выделенияпараллельно исполняемых процессов зависит от класса математическогоописания и здесь не рассматривается. После ввода осуществляется оценкавычислительной сложности процессов; причем для этого могутвыполняться и эксперименты на реальных процессорах. Введенноеописание взаимодействующих процессов приводится к представлению, накотором проводится последующее решение. Ввод описания сети, то есть ее структуры и типов процессоров.

Причемпри отсутствии априорных сведений о характеристиках процессоров103проводятся эксперименты, уточняющие их производительность и скоростьпередачи данных. Введенное пользователем описание трансформируется кпредставлению, которое также используется в последующем решении. Ввод начального распределения процессов по процессорам сети ивыбор показателя (критерия) эффективности функционирования сети, чтоделается пользователем. Запуск алгоритма конфигурирования. Анализ получаемого решения. Переход к следующему этапу реализации.Функционирование средств конфигурирования осуществляется пользователемчерез соответствующий интерфейс.Один из факторов, на который обращается внимание, - быстродействиеалгоритма (пере)распределения.Руководствуясь этим, выполним модификацию одного статического методараспределения.Сделаем предположение, что все n компонент алгоритма обработкивыполняются параллельно (то есть не учитывается параллельно-яруснаяструктура алгоритма обработки) и распределяются на сеть из m процессоров.Тогда нетрудно получить следующую математическую формулировку.min   min max ( wl j   cl j ) XXjm x n ( j 1)  i  1, i  1 : nj 1n x n ( j  1)  i  n , j  1 : mi 1wl j   cl j   , j  1 : mmin Xm x n ( j 1 )  i  1, i  1 : n (*)j 1n  x n ( j  1)  i  x nm  j  n , ji 1wl j   cl j  x ( n  1 ) m  j    0; x k  0 ,  x k  1 : ( n  (162) 1 : m (**) 0 , j  1 : m (* * *) 2 ) m , x k  0 ,1Где {xk }k  1 : mn - бинарные переменные, определяющие распределениепроцессов по процессорам; n - количество процессов, m - количествопроцессоров, wlj(x1,...,xk) - вычислительная загрузка j-го процессора, clj(x1,...,xk) коммуникационная загрузка j-го процессора.Общее число переменных (n+2)m+1, из них nm бинарных, общее числоограничений типа равенство (n+2m).Примем параметр =0.

Тогда вся задача (пере)распределения сводится к задачесмешанного булевого линейного программирования.Предварительный анализ нахождения решения, используя симплекс-метод,позволяет предложить процедуру поиска решения варьированием толькобинарных переменных из (*) и (**), так как все остальные оставшиесяпеременные xnm+j, x(n+1)m+j за исключением одной необходимо включаются вчисло базовых.Работа процедуры нахождения решения происходит последовательно по шагам,что принципиально позволяет выполнять постепенное перераспределение. Даемкраткое описание процедуры.На каждом шаге происходит поиск из группы уравнений (162) одного, длякоторого дополнительная переменная при некотором j=k становится равнойнулю x(n+1)m+k=0. Все остальные дополнительные переменные x(n+1)m+j, jkявляются неотрицательными.Система уравнений (162) принимает вид:  wlk ; x( n 1) m  k  0 .(163)x( n 1) m  j  wlk  wl j    wl j ; j  k Из уравнения для  посредством перебора находится та вычислительнаязагрузка (и связанная с ней бинарная переменная), которая при добавлении куравнению, содержащему максимальное значение дополнительной переменнойx(n+1)m+n (то есть к уравнению, имеющему минимальную вычислительнуюзагрузку), обеспечивает максимальное уменьшение показателя .После переноса в k-ое уравнение найденной вычислительной загрузкипроисходит приведение полученной системы уравнений к виду (163).

Далееопять повторяется процесс поиска перемещаемой вычислительной загрузки итак далее до нахождения min  . Останов алгоритма происходит по некоторомуXусловию, связанному с анализом значений дополнительных переменных.Учет коммуникационной загрузки увеличивает существенно сложностьрасчетов.Если характеризовать процессор, выделенный под некоторую подзадачу:производительностью р (Мфлопс) и скоростью передачи данных по линку s(бит/с), - а саму подзадачу: вычислительной сложностью с (количествоопераций) и объемом передаваемых данных v (бит), - то тогда можно ввестисложное отношение104ccR2 vp wlpvR1clssгде R2 - определяет свойства процессора с линком, R1 - определяет свойстваподзадачи, wl - вычислительная загрузка процессора (сек), cl коммуникационная загрузка процессора (сек).Данное отношение в формеwlh(164)clбудем рассматривать как коэффициент согласования процессора с подзадачейили как условие согласования вычислительной и коммуникационной загрузоквыбранного процессора.

Величины wl и cl оцениваются по результатампростейших экспериментов.Представляет интерес использовать условие согласования (164) для построенияалгоритма распределения. В этом случае совокупность уравнений ограничения:m xn( j 1)  i  1, i  1 : n j 1n xn ( j 1)  i  n, j  1 : m  ,i 1wl j  cl j  0, j  1 : m последняя группа m неравенств определяет условие согласования загрузок.Как видно, изложенный подход балансировки загрузки транспьютерной сети наоснове симплекс-метода обладает рядом особенностей: непосредственно вкритерии учитывается согласование 2-х видовзагрузок для каждоготранспьютера сети; адаптация критерия на условия реального применениявыбором коэффициентов согласования  j ; ускорением общего временинахождения решения, благодарябинарных базовых переменных.формированиюопределенногонабораВ связи с тем, что основная математическая платформа MATLAB-SIMULINKпредставляет собой приложение WINDOWS, то для обеспечения работы вединой системной среде и для быстрого перехода от Программно-АппаратногоКомплекса в среду разработки (SIMULINK) интерфейс данной СТР выполнен ввиде стандартного приложения WINDOWS.Данные средства обеспечивают интерактивный диалог СТР с разработчиком(пользователем).

С помощью них разработчик обрабатывает существующиеописания, а также может вводить новые описания с последующей ихпараллельной обработкой.Через интерфейс пользователя осуществляется манипуляция основнымифункциями СТР. В зависимости от вида реализации: одно-транспьютерная илимультитранспьютерная, который задается пользователем, запускаютсяразличные схемы преобразования внутреннего представления.

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

Предоставляется возможность следить заинтересующим параметром состояния работающей модели, а также изменятьлюбой параметр системы в процессе функционирования.В процессе работы с СТР пользователю, как понятно из рис.53, необходимоиметь файлы внутреннего представления, а дальнейший ход функционированиязадается в зависимости от требуемой реализации.На стадии одно-транспьютерной реализации необходимым для получениярезультата является D-файл. Его использует программа преобразования блокови подстановки, генерирующая текст параллельной программы на языкеOCCAM.

Далее, с использованием технологических средств параллельногопрограммирования, эта программа компилируется в исполняемый код, готовыйк погружению на транспьютер. После проверки правильности и корректностифункционирования схемы, на одном транспьютере можно приступать кмультитранспьютерной реализации.При создании сетевого варианта (мультипроцессорной реализации) порядокработы несколько отличен. Важным компонентом функционирования СТР наэтой стадии является База данных времен блоков, сформированнаяпредварительно на стадии создания Библиотеки параллельных алгоритмов. Скаждым блоком проводится серия экспериментов по заранее спроектированнойсхеме с целью получения времени его работы на различных вычислительныхсредствах. Результаты экспериментирования обрабатываются, обобщаются изаносятся в таблицу.

Характеристики

Список файлов книги