- •Оглавление.
- •§1.2. Режим реального времени
- •Глава 2. Вычислительные системы §2.1. Классификация вс.
- •§2.2. Показатели качества вс.
- •§2.3. Классификация вс по организации структуры.
- •Глава 3. Распределение ресурсов процессора. §3.1. Принципы упорядочивания ресурсов вс методами теории расписаний.
- •§3.2. Общая постановка задачи упорядочивания.
- •§3.3. Задачи и критерии детерминированного распределения производительности вычислительных систем.
- •Глава 4. Распределение памяти в вс. §4.1. Оптимизация распределения памяти по иерархическим уровням.
- •§4.2. Управление замещением страниц в двухуровневой памяти.
- •§4.3. Класс многоуровневых алгоритмов замещения.
- •§4.4. Модели поведения программ и критерии качества.
- •Глава 5. Классические архитектуры многомашинных и многопроцессорных комплексов. §5.1. Многомашинные комплексы.
- •§5.2. Многопроцессорные комплексы.
- •§5.3. Типы структур мпвк.
- •Глава 6. Примеры многомашинных и многопроцессорных систем. §6.1. Вк на базе ес эвм (ibm).
- •§6.2. Вк на базе см эвм (dec).
- •§6.3. Комплексы на основе микро-эвм и микропроцессоров.
- •Глава 7. Особенности организации вычислительных процессов.
- •Глава 8. Системы параллельной обработки данных. §8.1. Классификация систем параллельной обработки данных.
- •§9.6. Кластерная архитектура.
- •§9.7. Проблемы выполнения сети связи процессоров в кластерной системе.
- •Глава 10. Принципы построения коммуникационных сред. §10.1. Коммутаторы для многопроцессорных вычислительных систем.
- •§10.2. Простые коммутаторы.
- •Алгоритмы арбитража. Статические приоритеты.
- •Динамические приоритеты.
- •Фиксированные временные интервалы.
- •Очередь fifo.
- •Особенности реализации шин.
- •Простые коммутаторы с пространственным разделением.
- •§10.3. Составные коммутаторы.
- •Коммутатор Клоза.
- •Распределенные составные коммутаторы.
- •Глава 11. Примеры построения коммуникационных сред. §11.1. Когерентный интерфейс sci.
- •§11.2.Коммуникационная среда myrinet.
- •Глава 12. Сосредоточенные вычислительные системы высокой производительности. §12.1. Конвейерные системы.
- •§12.2. Иерархия памяти.
- •§12.3. Управление и организация конвейеров.
- •§12.4. Статические конвейеры.
- •§12.5. Диаграмма состояний.
- •§12.6. Генерирование таблиц занятости на основе циклов.
- •§12.7. Конвейеры с динамической конфигурацией.
- •§12.8. Функции управления в конвейерных системах.
- •§12.9. Архитектура конвейерных систем.
- •§12.10. Примеры конвейерных систем.
- •§12.11. Матричные вычислительные системы.
- •Резюме.
- •Список литературы.
§3.2. Общая постановка задачи упорядочивания.
В общем случае штраф от того, что заявка на решение i-ой задачи реализуется на к- месте в очереди, т.е. после решения предыдущих к-1 задач, могут быть произвольной функцией места в очереди, длительности ожидания или иных параметров и, в частности, затрат на настройку системы. Этот штраф может характеризовать некоторое значение коэффициента ,зависящего от типа задачи и очередности ее решения. Если значения штрафоввзаимно независимы и суммарный штраф является минимальной функцией штрафов за решениеi-ой задачи на к-ом месте, то задача оптимизации последовательности заявок может рассматриваться как задача минимизации линейного функционала:
.
Здесь =1, еслиi-ая заявка реализуется на к-ом месте и нулю в противном случае. Обычно заявки должны реализоваться без пропусков после завершения предыдущих подпрограмм и каждая заявка должна быть обязательна реализована. Это приводит к ограничениям:
Подобным же образом задача составления оптимального расписания может быть сформулирована, если коэффициент характеризует величину выигрыша или дохода от реализации каждойi-ой заявки в k-ую очередь. При этом задача состоит в нахождении максимума линейной функции:
, при тех же ограничениях.
Таким образом задача составления оптимального расписания реализации заявок может быть сформулирована как типичная задача линейного программирования – задача выбора или назначений. Точные методы решения задач такого вида весьма трудоемки, и при большой размерности имеются значительные технические и принципиальные трудности для получения технических решений. Однако, и при относительно невысокой размерности, типичной для составления оптимального расписания в ВС , точное решение задачи упорядочивания может требовать значительных затрат производительности. Быстрый рост обмена необходимых вычислений при увеличении размерности расписания приводит к появлению методов упорядочивания, перебора и ряда эвристических методов, позволяющих существенно сократить трудоемкость вычислений. Эти методы не всегда имеют строгое математическое обоснование и в некоторых случаях базируются на статистических экспериментальных оценках их точности. Качественно упростить получение первого приближения в задачах теории расписаний в их наиболее общей постановке можно следующими приемами:
ранжированием заявок, что позволяет заранее произвести их частичное упорядочивание и резко сокращает количество вариантов расписания;
введение промежуточных целей, когда оптимальное расписание составляется последовательно на интервалы времени. На эти интервалы разбивается все время планирования.
введением простейших функций штрафов.
Во многих случаях приемами ранжирования, промежуточных целей и упрощением функций пользуются интуитивно, не производя оценок отклонения значения функционала от его оптимального значения без введенных допущений. При этом приходится удовлетворяться тем, что полученные расписания лучше, чем неупорядоченные случайный выбор задач на реализацию.
Оценка качества упорядочивания при неполной информации о длительности исполнения работ и штрафах за ожидания или нарушения директивных сроков встречается с большими трудностями, и результаты, полученные в этой области аналитическими методами, весьма ограничены.