Я пытаюсь разбить небольшой гранично-взвешенный граф на разбиения максимального размера.(Вариант использования, который может или не может быть релевантным, состоит в разбиении графа связи параллельной программы для минимизации более дорогих затрат на связь.) Например, у меня может быть граф из 21 узла, и мне может потребоваться максимальный размер раздела 4узлов на раздел (всего 7 разделов);gpmetis создает разделение, где один раздел имеет 5 узлов (а другой - 3).Я обнаружил, что схема разбиения rb (рекурсивное деление пополам) имеет тенденцию работать лучше для небольших графов, но это не всегда работает.
В настоящее время я использую METIS (инструмент gpmetis) для этого ина маленьких графиках это иногда создает разделы, которые больше, чем я хочу.Обратите внимание, что аргументом gpmetis является количество разделов, а не максимальное количество узлов на раздел.
Вопросы:
Почему это происходит?Производит ли METIS такой результат, потому что фактически обеспечивает лучшее разделение несмотря на дисбаланс в размере раздела?
Есть ли способ достичь моей цели максимального размера раздела (в идеале с METIS, но яЯ открыт для использования других инструментов).