Формальное понятие для энергетической сложности вычислительных задач

Вычислительная сложность включает в себя изучение временной или пространственной сложности вычислительных задач. С точки зрения мобильных вычислений энергия является очень ценным вычислительным ресурсом. Итак, есть ли хорошо изученная адаптация машин Тьюринга, учитывающая энергию, потребляемую при выполнении алгоритмов. Кроме того, существуют ли классы сложности энергии для вычислительных задач?

Рекомендации приветствуются.

Существует ли хорошо изученная адаптация машин Тьюринга, учитывающая энергию, потребляемую при выполнении алгоритмов? Нет!

Но, может быть, вы могли бы придумать один. Возможно, вы могли бы разделить шаги машины Тьюринга на обратимые и необратимые (необратимые - это когда информация теряется). Теоретически, это только необратимые шаги, которые стоят энергии. Стоимость одной единицы энергии для каждого стираемого бита теоретически была бы правильной мерой.

Существует теорема Чарльза Беннетта о том, что сложность времени увеличивается не более чем на постоянную величину, когда вычисление становится обратимым (CH Bennett, Logical Reversibility of Computation ), но если существуют также ограничения на пространство, то создание обратимого вычисления может повлечь за собой значительное увеличение времени (ссылка здесь) . Принцип Ландауэра гласит, что стирание немного стоит энергии, где - температура, а - постоянная Больцмана. В реальной жизни вы не можете приблизиться к достижению этого минимума. Тем не менее, вы можете создавать чипы, которые выполняют обратимые шаги, используя значительно меньше энергии, чем они используют для необратимых шагов. Если вы дадите обратимым шагам стоимостьT k α $kT\, \ln 2$$T$$k$$\alpha$и необратимые шаги стоимость , кажется, что это может дать разумную теоретическую модель.$\beta$

Я не знаю, как машины Тьюринга с некоторыми обратимыми шагами относятся к чипам с некоторой обратимой схемой, но я думаю, что обе модели заслуживают изучения.

Классов энергетической сложности пока нет, но определенно есть большой интерес к изучению того, как разрабатывать алгоритмы, которые являются энергоэффективными в некоторой модели. Я не знаком со всей совокупностью работ, но одна точка входа - это работа, которую Кирк Прухс делает над устойчивыми вычислениями. Кирк - теоретик с опытом в планировании и аппроксимациях, и в последнее время он стал очень активным в этой области, поэтому его точка зрения хороша для алгоритмических людей.

Идея PS gabgoh о принципе Ландауэра является хорошей. Если вы хотите узнать больше об отношениях между энергией и информацией, нет лучшего источника, чем книга Максвелла о демонах .

Это вовсе не прямой ответ, но есть некоторые потенциально полезные связи с программами рисования / исследования, которые будут проводиться в соответствии с работами Стэй и Баэса по алгоритмической термодинамике: http://johncarlosbaez.wordpress.com/2010/10 / 12 / алгоритмическая-термодинамика /

Тем не менее, обратите внимание, что эта работа не выявляет реальных физических последствий - скорее, она иллюстрирует связь, которая до сих пор является чисто математической.

Кей Учизава и его соавторы изучают энергетическую сложность пороговых цепей. Они определяют его как максимальное количество пороговых вентилей, которые выводят 1 на все возможные входы.

Поскольку речь идет не о машинах Тьюринга, это не отвечает на вопрос. Но я надеюсь, что их бумаги дают некоторые идеи. Его веб-страница содержит указатели. http://www.nishizeki.ecei.tohoku.ac.jp/nszk/uchizawa/

Существует некоторое оправдание для использования модели внешней памяти в качестве модели вычислений, учитывающих энергию. Паоло Феррагина кратко обсуждал это в своей приглашенной лекции на ESA 2010, но я не знаю, есть ли опубликованные результаты. Основная идея заключается в том, что если число входов / выходов доминирует во времени вычислений, то энергия, необходимая для этих входов / выходов, вероятно, будет доминировать в общем потреблении энергии.

Отчет о первом рабочем совещании по науке управления питанием в основном содержали вопросы и открытые проблемы. Я не знаю, что произошло на втором семинаре , но на веб-страницах сообщается, что будет специальный выпуск Sustainable Computing, посвященный теоретическим, математическим и алгоритмическим подходам к устойчивым вычислениям.

Вот некоторые новые / другие ссылки / углы на этот, по-видимому, глубокий вопрос с продолжающимися исследованиями. как указал П.Шор, район, похоже, ожидает комплексного обследования, стандартизации и / или объединения. вначале перечислены более абстрактные / теоретические подходы, за которыми следуют более прикладные подходы: энергоэффективные алгоритмы, измерение использования энергии на мобильных устройствах для сортировки, изучение факторов в СБИС, влияющих на сложность энергии / времени.

• Модель энергетической сложности для алгоритмов, Swapnoneel Рой Атри Рудра Акшат Верма ITCS 2013

• На пути к энергетической сложности вычислений Ален Дж. Мартин, IPL 2001

• Сложность против энергии: теория вычислений и теоретическая физика Юрий Иванович Манин

• К модели энергетической сложности для алгоритмов Рави Джайн, Дэвид Молнар, Зульфикар Рамзан

• Энергоэффективные алгоритмы Сюзанны Альберс

• Яо Ф.Ф., Демерс А.Дж., Шенкер С. Модель планирования для снижения энергопотребления ЦП. В материалах 36-го симпозиума IEEE по основам информатики (1995), 374–382.

• Исследование энергопотребления алгоритмов сортировки данных в встраиваемых и мобильных средах Кристиан Бунс Хаген Хопфнер Эссам Мансур Суман Ройчоудхури

• Энерго-временная сложность алгоритмов: моделирование компромиссов CMOS VLSI (2007). Автор Brad D. Bingham

Временные и пространственные сложности не зависят от устройства. Я не вижу способа сделать энергозатратное устройство независимым.

$W$$W$$W$

$O(W f(n)) = O(f(n))$