6.1 KiB
6.1 KiB
P27. DeDe: декомпозиция задач распределения ресурсов
- Версия и дата проверки: 1.1, 07.09.2026.
- Статус: готово к назначению.
Статья и исходные материалы
- Основная статья: Zhiying Xu и соавт. — Decouple and Decompose: Scaling Resource Allocation with DeDe. OSDI 2025.
- Кратко о статье: Крупные задачи распределения ресурсов в облаке перерастают возможности универсальных решателей, а специализированные алгоритмы обычно привязаны к одной системе. DeDe использует общую разделимость многих постановок: разъединяет ограничения ресурсов и запросов и решает чередующиеся подзадачи независимо и параллельно. В проекте этот подход сравнивается с монолитным решением по времени, допустимости и качеству распределения.
- Почему результат актуален: опубликованный пакет предоставляет высокоуровневый интерфейс, тесты и три разные прикладные задачи. Статья свежая, поэтому статус влияния предварительный, но общий механизм не привязан к закрытому кластеру или специальному оборудованию и уже допускает независимую проверку на CPU.
- Артефакты и данные: illinois-nsai/dede под MIT, доступен как Python-пакет и содержит примеры для кластерного планирования, балансировки нагрузки и управления трафиком. Для обязательного сравнения достаточно свободного решателя CVXPY; Gurobi не требуется. Зафиксированные ревизии:
illinois-nsai/dede@11c97f786a1e(MIT). - Что уже предоставляет артефакт: DeDe предоставляет библиотеку декомпозиции и готовые примеры оптимизационных задач. Их можно использовать как основу модели; свободный решатель CVXPY остаётся допустимым baseline.
Обязательный результат
- Проверяемый вопрос или утверждение: разделение связанных ограничений на подзадачи для ресурсов и запросов ускоряет решение крупных задач распределения, сохраняя допустимость и качество результата относительно монолитного решателя.
- Технический результат: Формализовать одну задачу кластерного размещения или балансировки нагрузки и реализовать её в DeDe и как монолитную модель CVXPY. Подготовить общий генератор входов, проверку допустимости решения и единый расчёт целевой функции и невязок.
- Обязательное приращение команды: Формализовать предусмотренную задачу и подготовить её сопоставимые DeDe- и монолитную модели, общий генератор и независимую проверку допустимости и цели. Самостоятельно исследовать время, невязки и масштабирование; готовое toy-сравнение без этих результатов недостаточно.
- Эксперимент: для выбранной задачи на открытых или синтетических данных сравнить DeDe и монолитное решение CVXPY по времени, целевой функции, невязкам и масштабированию по числу ресурсов и запросов.
- Границы выводов: сравнение относится к одной формализации задачи, выбранным входам и размерам, доступным точному решателю; оно не устанавливает преимущество DeDe для других задач распределения и производственных масштабов.
- Ресурсный профиль: локально, CPU, Python, 8–16 ГБ памяти. Если высокоуровневый интерфейс нестабилен на большой задаче, использовать опубликованные низкоуровневые примеры и уменьшить размер, сохранив сравнение с точным решением на тех же входах.
Содержательные направления
- постановка и генератор задач.
- реализации DeDe и монолитного варианта.
- проверка допустимости, масштабирование и исследование нового ограничения.
Возможное продолжение
Добавить неоднородные ресурсы, онлайн-прибытие запросов, ограничение миграций, новый критерий справедливости либо собственное правило адаптации параметра декомпозиции.