# P27. DeDe: декомпозиция задач распределения ресурсов

- **Версия и дата проверки:** 1.1, 07.09.2026.
- **Статус:** готово к назначению.

## Статья и исходные материалы

- **Основная статья:** Zhiying Xu и соавт. — [Decouple and Decompose: Scaling Resource Allocation with DeDe](https://www.usenix.org/conference/osdi25/presentation/xu). OSDI 2025.
- **Кратко о статье:** Крупные задачи распределения ресурсов в облаке перерастают возможности универсальных решателей, а специализированные алгоритмы обычно привязаны к одной системе. DeDe использует общую разделимость многих постановок: разъединяет ограничения ресурсов и запросов и решает чередующиеся подзадачи независимо и параллельно. В проекте этот подход сравнивается с монолитным решением по времени, допустимости и качеству распределения.
- **Почему результат актуален:** опубликованный пакет предоставляет высокоуровневый интерфейс, тесты и три разные прикладные задачи. Статья свежая, поэтому статус влияния предварительный, но общий механизм не привязан к закрытому кластеру или специальному оборудованию и уже допускает независимую проверку на CPU.
- **Артефакты и данные:** [illinois-nsai/dede](https://github.com/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 и монолитного варианта.
- проверка допустимости, масштабирование и исследование нового ограничения.

## Возможное продолжение

Добавить неоднородные ресурсы, онлайн-прибытие запросов, ограничение миграций, новый критерий справедливости либо собственное правило адаптации параметра декомпозиции.