Вычислительных систем
 Скачать 0.78 Mb.
|
|
3.3. Стохастически оптимальное функционирование ВС 39 Найдя Λ 1 (??????) , переходим к вычислению Λ 2 (??????) и ̂︀ ?????? 2 (??????) Λ 2 (??????) = min ?????? 2 (?????? 2 (?????? 2 ) + Λ 1 (?????? − ?????? 2 ?????? 2 )), ?????? 2 = 0, 1, . . . , [??????/?????? 2 ]. ̂︀ ?????? 2 (??????) = argmin ?????? 2 (?????? 2 (?????? 2 ) + Λ 1 (?????? − ?????? 2 ?????? 2 )), ?????? 2 = 0, 1, . . . , [??????/?????? 2 ]. Значение Λ 1 (?????? − ?????? 2 ?????? 2 ) повторно вычислять не следует, его можно взять из таблицы 3.1. Вычисления продолжатся вплоть до нахождения Λ ?????? (??????) и ̂︀ ?????? ?????? (??????) . Опти- мальное значение целевой функции берется из таблицы ?????? * = Λ ?????? (??????). На обратном ходе отыскиваются компоненты вектора (?????? * 1 , ?????? * 2 , . . . , ?????? * ?????? ) оптимального решения. Значение ?????? * ?????? берется из таблицы ?????? * ?????? = ̂︀ ?????? ?????? (??????). Значения остальных неизвестных вычисляются с учетом ограничений за- дачи и берутся из таблицы ?????? * ??????−?????? = ̂︀ ?????? ??????−?????? (︃ ?????? − ??????−1 ∑︁ ??????=0 ?????? ??????−?????? ?????? * ??????−?????? )︃ , ?????? = 1, 2, . . . , ?????? − 1. Таблица 3.1 ?????? Λ 1 (??????) ̂︀ ?????? 1 (??????) Λ 2 (??????) ̂︀ ?????? 2 (??????) Λ ?????? (??????) ̂︀ ?????? ?????? (??????) 0 Λ 1 (0) ̂︀ ?????? 1 (0) Λ 2 (0) ̂︀ ?????? 2 (0) Λ ?????? (0) ̂︀ ?????? ?????? (0) 1 Λ 1 (1) ̂︀ ?????? 1 (1) Λ 2 (1) ̂︀ ?????? 2 (1) Λ ?????? (1) ̂︀ ?????? ?????? (1) ?????? Λ 1 (??????) ̂︀ ?????? 1 (??????) Λ 2 (??????) ̂︀ ?????? 2 (??????) Λ ?????? (??????) ̂︀ ?????? ?????? (??????) 3.3.3. Задание 1. Написать программу, реализующую метод динамического про- граммирования для решения рассмотренной задачи. В качестве входных параметров программа получает количество ?????? ма- шин в системе, значения ?????? 1 , ?????? 2 , . . . , ?????? ?????? , ?????? 1 , ?????? 2 , . . . , ?????? ?????? , ?????? 1 , ?????? 2 , . . . , ?????? ?????? . Считать, что спрос на подсистему ранга ?????? имеет пуассоновское распределение с па- раметром ?????? ?????? 40 Глава 3. Организация функционирования ВС 2. Исследовать зависимость значения целевой функции ?????? от значений параметров ?????? ?????? и ?????? ?????? 3.3.4. Контрольные вопросы 1. Объяснить суть подхода к организации функционирования распре- деленных ВС с использованием аппарата стохастического программирова- ния. В чем преимущество данного подхода? 2. Привести примеры постановок задач стохастического программиро- вания. 3. Когда следует осуществлять новое разбиение системы на подсисте- мы элементарных машин? 4. Объяснить основные этапы в выводе целевой функции ??????. 5. Пояснить основные шаги метода динамического программирования. 3.4. Вложение параллельных программ в ВС 41 3.4. Вложение параллельных программ в ВС 3.4.1. Модель ВС с иерархической организацией коммуникационной среды Пусть имеется распределенная ВС, представленная в виде дерева, со- держащего ?????? коммуникационных уровней (рис. 3.2). Рассмотрим вложе- ние параллельной программы в подсистему из ?????? элементарных машин. Очевидно, что подсистема также имеет иерархическую структуру. Обозначим через ?????? ?????? количество элементов на уровне ?????? ∈ {1, 2, . . . , ??????} (вычислительные узлы, процессоры и пр.); ?????? ???????????? – число прямых дочерних узлов элемента ?????? ∈ {1, 2, . . . , ?????? ?????? } , находящегося на уровне ??????; ?????? ???????????? – количе- ство ЭМ, принадлежащих потомкам данного элемента. Рис. 3.2. Пример подсистемы ЭМ, выделенной для решения параллельной задачи ранга ?????? = 16. Параллельная программа представлена графом ?????? = (??????, ??????) информаци- онных обменов, где ?????? = {1, 2, . . . , ??????} – множество ветвей параллельной программы, а ?????? ⊆ ?????? × ?????? – множество информационно-логических связей между ветвями. Обозначим через ?????? ???????????? вес ребра (??????, ??????) ∈ ??????, отражающий интенсивность обменов данными между ветвями ?????? и ?????? при выполнении программы. Вложение параллельной программы в ВС задается значениями пере- менных ?????? ???????????? ∈ {0, 1} : ?????? ???????????? = 1 , если ветвь ?????? ∈ ?????? назначена на ЭМ, в против- ном случае ?????? ???????????? = 0 Для оценки эффективности вложения используется время ?????? (??????) вы- полнения информационных обменов. Оно определяется максимальным из времен выполнения обменов ветвями программы. Пусть ??????(??????, ??????, ??????, ??????) – сум- марное время взаимодействий между ветвями ??????, ?????? ∈ ?????? , назначенными на процессорные ядра ?????? и ?????? соответственно. |