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

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

На рис. 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).