При сообщении алгоритмической сложности алгоритма предполагается, что базовые вычисления выполняются на некоторой абстрактной машине (например, ОЗУ), которая приближается к современному ЦП. Такие модели позволяют нам сообщать о временной и пространственной сложности алгоритмов. Теперь, с распространением GPGPU , возникает вопрос, существуют ли хорошо известные модели, в которых можно учитывать и энергопотребление.
Общеизвестно, что графические процессоры потребляют значительное количество энергии, и некоторые команды подразделяются на различные категории энергопотребления в зависимости от их сложности и расположения на сложном чипе. Следовательно, с точки зрения энергии, инструкции не имеют удельной (или даже фиксированной) стоимости. Тривиальным расширением может быть присвоение весов стоимости операции, но я ищу мощную модель, в которой операция / инструкция может стоить непостоянных единиц энергии, например, полиномиального количества (или даже более сложной, например: функция времени, прошедшего с момента запуска алгоритма или с учетом вероятности отказа системы охлаждения, которая разогреет микросхемы и замедлит тактовую частоту и т. д.)
Существуют ли в таких моделях нетривиальные затраты и неисправности?
Ответы:
Пока не существует устоявшейся модели, но сейчас это область активных исследований. Один из экспертов в области алгоритмов - Кирк Прухс. Его документы имеют больше информации, и вы также можете просмотреть эту презентацию .
источник
Модели для потребления энергии
Скорость масштабирования является одной из наиболее часто используемых моделей (в последнее время) при рассмотрении энергопотребления. Он заключается в изменении напряжения питания. Понижая напряжение питания или тактовую частоту процессора, можно добиться значительного снижения энергопотребления; Более высокие скорости обеспечивают более быстрое выполнение, но они также приводят к гораздо более высокому (сверхлинейному) энергопотреблению.
Однако масштабирование скорости - не единственная рассматриваемая энергия. Это то, что называется динамической энергией. Статическая энергия есть сила , которая связана с процессором бытия «на». Можно избавиться от этой статической мощности путем отключения процессора во время простоя. Однако это имеет цену. По этой теме было проделано много работы, которая очень близка к проблеме аренды лыж .
Обычно потребление энергии представляет собой сумму статического и динамического потребления энергии, умноженного на время выполнения. Тем не менее, большинство статей посвящено одной из этих проблем.
Ввод неисправностей в этой модели
Я думаю, что это самая удивительная часть модели масштабирования скорости. Обычно можно подумать, что чем быстрее вы выполняете задачу, тем больше вероятность провала выполнения. Напротив, было показано, что уменьшение скорости процессора увеличивает число переходных отказов системы; вероятность отказов возрастает экспоненциально, и этой вероятностью нельзя пренебрегать в крупномасштабных вычислениях.
Это самостоятельная справка, поэтому я не знаю, ценится ли она здесь, однако, если вам интересно, вы можете найти больше информации в этой статье о динамической части потребления энергии.
источник
Были попытки проанализировать энергопотребление алгоритмов в теории (конечно, используя реальные затраты на операцию); см. например [1]. Хотя результаты достаточно удивительны - самый быстрый алгоритм не всегда тот, который использует наименьшее количество энергии - некоторые препятствия остаются.
В частности, современные платформы отключают определенные функции, так что стоимость рабочей энергии резко возрастает при их повторном включении. Хотя в принципе это возможно включить в строгий анализ, это становится технически (слишком?) Трудным. Кроме того, влияние потерь кэша на общее энергопотребление не было хорошо изучено.
Похоже, что огромные различия между платформами противоречат тщательному анализу, который может (на этот раз) не игнорировать специфику, потому что общие модели (т.е. до включения конкретных констант / функций) имеют ограниченное значение.
источник