Детерминированный графовый алгоритм

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

Система может быть представлена в виде взвешенного графа, где каждая вершина является процессом, а каждая дуга представляет собой поток сообщений между двумя процессами. Тогда математически проблема сводится к поиску способа разбиения (то есть разрезания) графа на 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).

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Детерминированный графовый алгоритм:

  1. ДЕТЕРМИНИРОВАНА ДВОЙНОЕ
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. АЛГОРИТМ
  4. АЛГОРИТМ УДАЧИ
  5. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  6. Алгоритм исцеления:
  7. Алгоритм избавления от боли
  8. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  9. Алгоритм обработки результатов.
  10. 2. Специфика и алгоритмы работы с источниками.