Детерминированный графовый алгоритм
Система может быть представлена в виде взвешенного графа, где каждая вершина является процессом, а каждая дуга представляет собой поток сообщений между двумя процессами. Тогда математически проблема сводится к поиску способа разбиения (то есть разрезания) графа на k непересекающихся подграфов, отвечающих определенным ограничениям (например, суммарные требования к центральному процессору и памя-
![]() | |||
![]() | |||
ти для каждого подграфа не должны превышать определенный предел). Для каждого решения, удовлетворяющего ограничениям, дуги, целиком находящиеся внутри отдельного подграфа, представляют собой внутримашинную передачу данных и могут быть проигнорированы. Дуги, переходящие из одного подграфа в другой, представляют собой сетевой трафик. Цель заключается в том, чтобы найти такой вариант разбиения, который сводил бы к минимуму сетевой трафик и при этом отвечал всем ограничениям. Для примера на рис. 8.24 показана система из девяти процессов от А до I, где каждая дуга подписана значением нагрузки по передаче данных между двумя процессами (например, в мегабитах в секунду).
На рис. 8.24, а граф разбит таким образом, что процессы A, E и G отнесены к узлу 1, процессы B, Fи H — к узлу 2, а процессы C, D и I — к узлу 3. Суммарный сетевой трафик получается путем сложения трафика всех дуг, разрезанных при разбиении (прерывистыми прямыми), и равен 30. На рис. 8.24, б показан другой вариант разбиения, при котором сетевой трафик равен 28. Если предположить, что этот вариант отвечает всем ограничениям по ресурсам центрального процессора и памяти, он является более предпочтительным, поскольку требует меньшего объема передачи данных.
Интуитивно мы занимаемся поиском кластеров, тесно связанных друг с другом (у которых широкие потоки внутрикластерного обмена данными), но слабо взаимодействующих с другими кластерами (имеющих узкие потоки межкластерного обмена данными). Самые первые статьи с обсуждениями этой проблемы были написаны Чоу и Абрахамом, Ло, а также Стоуном и Бокхари (Chow and Abraham, 1982; Lo, 1984; Stone and Bokhari, 1978).
Еще по теме Детерминированный графовый алгоритм:
- ДЕТЕРМИНИРОВАНА ДВОЙНОЕ
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- АЛГОРИТМ
- АЛГОРИТМ УДАЧИ
- Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
- Алгоритм исцеления:
- Алгоритм избавления от боли
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- Алгоритм обработки результатов.
- 2. Специфика и алгоритмы работы с источниками.