Оптимальное управление вычислениями в распределенных вычислительных системах на основе графа потоков данных

  • Добавили02.12.2002
  • Размер148,22 Kб
  • Скачали1726

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

е. второй критерий оптимальности. Кроме того, если при выборе процессора для распределения очередной задачи использовать минимаксный принцип, показанный в алгоритме 6.

1, то мы приближаемся к удовлетворению и первого критерия оптимальности. Рассмотрим задачу построения остовного дерева с максимальной суммой весов дуг МОД для краткости. Вес дуги i, j в данном случае это поток fij.

Любое поддерево МОДа будет называться фрагментом. Заметим, что узел может рассматриваться как фрагмент. Дуга, имеющая один узел во фрагменте, а другой узел вне этого фрагмента, называется дугой, уходящей от фрагмента.

Утверждение. Пусть L некоторый заданный фрагмент МОДа, а u i, j дуга максимального веса, уходящая от фрагмента L, причм узел j не входит в L. Тогда, если к L добавить дугу u и узел j, то получится фрагмент МОДа.

Данное утверждение используется в качестве основы для алгоритмов построения МОД. Идея алгоритма Крускаля состоит в том, что берутся несколько произвольных вершин как начальные фрагменты, и затем эти фрагменты увеличиваются путем последовательного добавления уходящих дуг минимального веса. Настанет момент, когда какие-либо пары фрагментов соедининяются дугой, имеющей минимальный вес среди дуг, добавление которых не создат цикла.

Алгоритм заканчивает работу после .

Скачать
Диплом Математика 03.12.2002

Управление потоками данных в параллельных алгоритмах вычислительной линейной алгебры

Введение Часть 1. Система FLOWer Глава 1. Краткий обзор Глава 2. Модель вычислений 2.1. ГПД 2.2. Шаблон ГПД 2.3. Связь ГПД и шаблона ГПД Глава 3. Язык DGL Глава 4. Пример параллельной программы Часть 2. Реализация некоторых алгоритмов ВЛА в системе FLOWer

Курсовая Менеджмент 16.06.2003

Менеджер управления распределенными вычислениями в локальной сети

Дулов Е.В. 2000 1. Модель среды параллельного программирования В качестве физической архитектуры параллельного компьютера используется локальная сеть LAN Ethernet. Таким образом, параллельный компьютер состоит из некоторого количества процессоров P, соединенных между собой линией передачи данных.

Диплом Делопроизводство 12.09.2007

Разработка системы автоматизации документооборота

сформулированы задачи, решаемые в выпускной работе. Далее дано описание цели, задачи документооборота и структура организации. Вторая глава состоит в разработке бизнес процессов, которые непосредственно связаны с работой Управления Информатизации, а также

Реферат Программирование 27.03.2007

Система автоматизированной обработки статистической информации

Система автоматизированной обработки статистической информации Организация государственной статистики и характеристика форм автоматизированной обработки статистической информации Государственная статистика представляет собой одно из важнейших межотраслевых

5ballov.qip.ru рекомендует:

  • Выбор ВУЗа

    С приходом лета начался период, когда выпускники школ выбирают куда пойдут учиться дальше. Конечно, это совсем не легкий выбор, но помочь в выборе может рейтинг вузов на нашем сайте. Также в этом разделе представлена вся нужная для абитуриентов информация.

  • Как сдать ЕГЭ

    Прежде, чем идти в выбранный вуз с документами, нужно сначала получить аттестат, который выдается после сдачи экзаменов. А подготовиться к ним можно в нашем разделе ЕГЭ. Там также представлены варианты за прошлые года.

  • Подготовка к ГИА

    Для девятиклассников не менее важно окончание учебного года. Их также ждет государственная итоговая аттестация. Подготовиться к ней можно на нашем сайте в разделе ГИА. Главное помнить: самоподготовка - это путь к успешной сдаче.

Последние запросы


философия средних веков принципы основные этапы Стратегическое планирование в банке Проектирование продукции машиностроения регламентирование финансово - хозяйственной деятельности пожарной охраны успехи современной генетики в медицине и здравоохранении восточный вопрос и внешняя политика николая I 1825-1855 технические модели оценка структуры торгового ассортимента и экспертиза качества одежды наибольшый общий делитель Северная война 1700-1721 гг Понятие о медицинской профилактике этническая принадлежность и неравенство в отношении здоровья развитие личности в условиях инновационной деятельности технология продуктивного чтения бионика одно из направлений биологии и кибернетики протокол https Основы теории графов История развития права социальной защиты эссе Брежнев наблюдение и описание движения небесных тел

Облако тегов