Вычислительных систем
 Скачать 0.78 Mb.
|
|
30 Глава 3. Организация функционирования ВС Сформировать 10 наборов задач с ?????? = 500, 1000, . . . , 5000; параметры задач генерировать как равномерно распределенные псевдослучайные чис- ла ?????? ?????? ∈ {1, 2, . . . , ??????} , ?????? ?????? ∈ {1, 2, . . . , 100} . Рассмотреть случаи для ?????? = 1024 и ?????? = 4096. 3. Провести сравнительный анализ значений целевой функции от расписаний, формируемых алгоритмами. Сформировать 10 наборов задач (?????? = 500, 1000, . . . , 5000); параметры задач генерировать как равномерно распределенные псевдослучайные чис- ла ?????? ?????? ∈ {1, 2, . . . , ??????} , ?????? ?????? ∈ {1, 2, . . . , 100} . Во всех 10 экспериментах ?????? = 1024. По результатам экспериментов построить оценки математического ожида- ния и среднеквадратического отклонения величины ?????? (см. приложение). 4. Выполнить сравнительный анализ значений целевой функции от расписаний, формируемых алгоритмами. На основе протоколов решения параллельных задач на промышлен- ных распределенных ВС сформировать наборы задач (?????? = 500, 1000, 1500) для любой из систем: LLNL uBGL, LLNL Atlas, LLNL Thunder. По ре- зультатам экспериментов построить оценки математического ожидания и среднеквадратического отклонения величины ??????. Входные данные (статистика выполнения параллельных программ на реальных системах): – Logs of Real Parallel Workloads from Production Systems // http://www.cs.huji.ac.il/labs/parallel/workload/logs.html 3.1.3. Контрольные вопросы 1. Дать определение мультипрограммного режима функционирования распределенных ВС. Назвать цели организации функционирования ВС. 2. Объяснить, в чем заключается задача построения расписания реше- ния параллельных задач на распределенной ВС. 3. Пояснить содержательный смысл целевой функции (3.1). 4. Пояснить смысл ограничений в оптимизационной задаче (3.1)–(3.4). 5. Объяснить, почему задача (3.1)–(3.4) относится к трудноразреши- мым задачам дискретной оптимизации. 6. Какова вычислительная сложность реализованных алгоритмов NFDH и FFDH? 7. Какой из алгоритмов на рассмотренных наборах задач формировал более точные расписания? 8. Проанализировать, от чего зависит эффективность того или иного алгоритма упаковки. Как значения параметров ?????? и ?????? влияют на время работы алгоритмов? 3.2. Теоретико-игровой подход к обслуживанию потока задач 31 3.2. Теоретико-игровой подход к обслуживанию потока задач 3.2.1. Игра «диспетчер-вычислительный центр» Имеется вычислительный центр (ВЦ), эксплуатирующий распределен- ную вычислительную систему из ?????? элементарных машин. ВЦ для реше- ния задач может выставлять по своему усмотрению любое число ?????? ∈ ??????, ?????? = {0, 1, . . . , ??????} ЭМ. Считается, что задача имеет ранг ?????? ∈ ??????, если для ее выполнения тре- буется ?????? машин. Предполагается, что в очереди диспетчера присутствуют задачи всех рангов. Время решения задачи ?????? равно ?????? ?????? единиц времени. Бу- дем считать, что диспетчер в дискретные моменты времени ?????? = 0, 1, 2, . . . назначает на ВС задачи различных рангов с временем решения, равным 1. Рассмотрим игру с участием двух игроков: ВЦ и диспетчера. Будем говорить, что ВЦ использует чистую стратегию с номером ?????? ∈ ??????, если он для решения задач отводит ?????? машин, и что диспетчер использует чистую стратегию ?????? ∈ ??????, если он для решения на ВС назначает задачу с рангом ?????? . Если ВЦ выбирает стратегию с номером ??????, а диспетчер – стратегию с номером ??????, то диспетчер «платит» ВЦ сумму ?????? ???????????? . Элементы ?????? ???????????? , ??????, ?????? ∈ ?????? составляют матрицу платежей C. Если ВЦ применяет смешанную стратегию ?????? = (?????? 0 , ?????? 1 , . . . , ?????? ?????? ) , а дис- петчер – смешанную стратегию П = (?????? 0 , ?????? 1 , . . . , ?????? ?????? ) , то средний платеж вычислительному центру составляет ?????? ∑︁ ??????=0 ?????? ∑︁ ??????=0 ?????? ???????????? ?????? ?????? ?????? ?????? Здесь ?????? ?????? , ?????? ?????? – вероятности выбора соответственно вычислительным цен- тром стратегии с номером ?????? и диспетчером стратегии с номером ??????. ВЦ имеет оптимальную смешанную стратегию ?????? * = (?????? * 0 , ?????? * 1 , . . . , ?????? * ?????? ) , а диспетчер – оптимальную смешанную стратегию П = (?????? * 0 , ?????? * 1 , . . . , ?????? * ?????? ) такие, что ?????? ∑︁ ??????=0 ?????? ∑︁ ??????=0 ?????? ???????????? ?????? ?????? ?????? * ?????? ≤ ?????? ≤ ?????? ∑︁ ??????=0 ?????? ∑︁ ??????=0 ?????? ???????????? ?????? * ?????? ?????? ?????? , ?????? = ?????? ∑︁ ??????=0 ?????? ∑︁ ??????=0 ?????? ???????????? ?????? * ?????? ?????? * ?????? Требуется для заданной матрицы платежей найти решение – векторы ?????? * , П * и цену ?????? игры. Подбор элементов платежной матрицы C должен осуществляться с |