4920
правок
Планирование напряжения: различия между версиями
Материал из WEGA
Планирование напряжения (посмотреть исходный код)
Версия от 04:32, 3 февраля 2026
, во вторник в 04:32→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 63: | Строка 63: | ||
'''Определение 1'''. s-расписанием для J является расписание, соответствующее принципу EDF и использующее постоянную скорость s при выполнении любого задания из J. | '''Определение 1'''. <math>s</math>-расписанием для множества <math>J</math> является расписание, соответствующее принципу EDF и использующее постоянную скорость <math>s</math> при выполнении любого задания из <math>J</math>. | ||
'''Лемма 1'''. s-расписание для J может быть вычислено за время O(n log n). | '''Лемма 1'''. <math>s</math>-расписание для <math>J</math> может быть вычислено за время <math>O(n \; log \; n)</math>. | ||
'''Определение 2'''. Для заданного множества заданий | '''Определение 2'''. Для заданного множества заданий <math>s</math> и любой скорости <math>s</math> обозначим за <math>J^{\ge s}</math> и <math>J^{< s}</math> подмножества <math>J</math>, состоящие из заданий, скорость выполнения которых в оптимальном расписании для <math>J</math> в непрерывной модели больше или равна <math>s</math> либо меньше <math>s</math>, соответственно. Разбиение <math>\langle J^{\ge s}, J^{<s} \rangle</math> называется <math>s</math>-разбиением <math>J</math>. | ||
Извлекая информацию из s-расписания, был разработан алгоритм разбиения для доказательства следующей леммы: | Извлекая информацию из <math>s</math>-расписания, был разработан алгоритм разбиения для доказательства следующей леммы: | ||
'''Лемма 2'''. s-разбиение для J может быть вычислено за время O(n log n). | '''Лемма 2'''. <math>s</math>-разбиение для <math>J</math> может быть вычислено за время <math>O(n \; log \; n)</math>. | ||
Применяя s-разбиение к J с использованием всех d скоростей в SD последовательно, можно получить d подмножеств | Применяя <math>s</math>-разбиение к <math>J</math> с использованием всех <math>d</math> скоростей в <math>SD</math> последовательно, можно получить <math>d</math> подмножеств <math>J_1, J_2, ..., J_d</math> множества <math>J</math>, где задания в одном и том же подмножестве <math>J_i</math> используют две одинаковые скорости <math>s_i</math> и <math>s_{i+1}</math> в оптимальном расписании для дискретной модели <math>(s_{d+1} = 0)</math>. | ||
'''Лемма 3'''. Оптимальное расписание для множества заданий | '''Лемма 3'''. Оптимальное расписание для множества заданий <math>J_i</math> с использованием скоростей <math>s_i</math> и <math>s_{i+1}</math> может быть вычислено за время <math>O(n \; log \; n)</math>. | ||
| Строка 87: | Строка 87: | ||
'''Теорема 4. Дискретное расписание ДМН с минимальным энергопотреблением может быть вычислено за время O( | '''Теорема 4. Дискретное расписание ДМН с минимальным энергопотреблением может быть вычислено за время <math>O(d \; n \; log \; n)</math>.''' | ||
Нижняя граница для вычисления оптимального расписания для дискретной модели в рамках алгебраической модели дерева решений также была доказана Ли и Яо. | Нижняя граница для вычисления оптимального расписания для ''дискретной модели'' в рамках алгебраической модели дерева решений также была доказана Ли и Яо. | ||
'''Теорема 5. Любой детерминированный алгоритм для вычисления дискретного расписания ДМН с минимальным энергопотреблением с d > | '''Теорема 5. Любой детерминированный алгоритм для вычисления дискретного расписания ДМН с минимальным энергопотреблением с <math>d \ge 2</math> уровнями напряжения требует времени <math>\Omega(n \; log \; n)</math> для <math>n</math> заданий.''' | ||
== Применение == | == Применение == | ||
