Notion formelle pour la complexité énergétique des problèmes de calcul

La complexité informatique comprend l’étude de la complexité temporelle ou spatiale des problèmes informatiques. Du point de vue de l'informatique mobile, l'énergie est une ressource informatique précieuse. Alors, existe-t-il une adaptation bien étudiée des machines de Turing qui prend en compte l'énergie consommée lors de l'exécution d'algorithmes? De même, existe-t-il des classes de complexité énergétique établies pour les problèmes de calcul?

Les références sont appréciées.

Existe-t-il une adaptation bien étudiée des machines de Turing tenant compte de l'énergie consommée lors de l'exécution d'algorithmes? Non!

Mais peut-être que vous pourriez en trouver un. Il est possible de diviser les étapes de la machine de Turing en deux étapes: réversible et non réversible (les étapes non réversibles sont celles où l'information est perdue). Théoriquement, seules les étapes irréversibles coûtent de l'énergie. Un coût d'une unité d'énergie pour chaque bit effacé serait théoriquement la bonne mesure.

Il existe un théorème de Charles Bennett selon lequel la complexité temporelle augmente d'au plus constante lorsque le calcul est rendu réversible (CH Bennett, Réversibilité logique du calcul ), mais s'il existe également des limites d'espace, le fait de rendre le calcul réversible risque de générer une perte de temps. augmentation substantielle dans le temps (référence ici) . Le principe de Landauer dit que l'effacement coûte un peu d'énergie, où$kT\, \ln 2$ est la température et k est la constante de Boltzmann. Dans la vraie vie, il est impossible d’atteindre ce minimum. Cependant, vous pouvez construire des puces qui effectuent des étapes réversibles en utilisant sensiblement moins d'énergie qu'elles n'en utilisent pour des étapes irréversibles. Si vous donnez aux étapes réversibles un coût de α et aux étapes irréversibles un coût de β , il semble que cela puisse donner un modèle théorique raisonnable.$T$$k$$\alpha$$\beta$

Je ne sais pas comment les machines de Turing avec certaines étapes réversibles sont associées aux puces avec certains circuits réversibles, mais je pense que les deux modèles méritent d’être étudiés.

Il n’existe pas encore de classes de complexité énergétique, mais l’intérêt d’étudier comment concevoir des algorithmes écoénergétiques selon un modèle donné suscite beaucoup d’intérêt. Je ne connais pas tout le travail, mais le travail que Kirk Pruhs effectue sur l'informatique durable constitue un point d'entrée . Kirk est un théoricien spécialisé dans la planification et les approximations. Il est récemment devenu très actif dans ce domaine. Son point de vue est donc intéressant pour les spécialistes de l'algorithmique.

Le point de ps gabgoh sur le principe de Landauer est bon. Si vous voulez en savoir plus sur la relation entre énergie et information, il n'y a pas de meilleure source que le livre de Maxwell's Demon .

Ce n’est pas une réponse directe du tout, mais il existe des liens potentiellement utiles pour élaborer / mener des programmes de recherche dans le sens des travaux de Stay et Baez sur la thermodynamique algorithmique: http://johncarlosbaez.wordpress.com/2010/10 / 12 / thermodynamique algorithmique /

Notez cependant que ce travail n’entraîne pas de conséquences physiques réelles - il illustre plutôt un lien qui, jusqu’à présent, est purement mathématique.

Kei Uchizawa et ses coauteurs étudient la complexité énergétique des circuits à seuil. Ils le définissent comme le nombre maximum de portes de seuil qui émettent 1 sur toutes les entrées possibles.

Puisqu'il ne s'agit pas de machines de Turing, cela ne répond pas à la question. Mais j'espère que leurs papiers donnent des idées. Sa page Web contient des pointeurs. http://www.nishizeki.ecei.tohoku.ac.jp/nszk/uchizawa/

Il y a une certaine justification à utiliser le modèle de mémoire externe en tant que modèle de calcul prenant en compte l'énergie. Paolo Ferragina en a brièvement parlé lors de son discours invité à l'ESA 2010, mais je ne sais pas s'il existe des résultats publiés. L'idée de base est que si le nombre d'entrées / sorties domine le temps de calcul, l'énergie nécessaire à ces entrées / sorties dominera probablement la consommation totale d'énergie.

Le rapport du premier atelier sur la science de la gestion de l’énergie contenait principalement des questions et des problèmes en suspens. Je ne sais pas ce qui s'est passé lors du deuxième atelier , mais les pages Web indiquent qu'il y aura un numéro spécial sur l'informatique durable consacré aux approches théoriques, mathématiques et algorithmiques de l'informatique durable.

Voici quelques nouvelles / autres références / angles sur cette question apparemment profonde avec les recherches en cours. comme indiqué par P.Shor, jusqu'à présent, la région semble attendre une étude complète, une normalisation et / ou une unification. d’abord des approches plus abstraites / théoriques, suivies d’approches plus appliquées: algorithmes d’efficacité énergétique, mesure de la consommation d’énergie dans le tri mobile, étude des facteurs de VLSI affectant la complexité énergie / temps.

• Un modèle de complexité énergétique pour les algorithmes, Swapnoneel Roy Atri Rudra Akshat Verma ITCS 2013

• Vers une complexité énergétique du calcul Alain J. Martin, IPL 2001

• Complexité contre énergie: théorie du calcul et physique théorique Yuri I. Manin

• Vers un modèle de complexité énergétique pour les algorithmes Ravi Jain, David Molnar, Zulfikar Ramzan

• Algorithmes d'efficacité énergétique Susanne Albers

• Yao, FF, AJ, Shenker, S. Demers, Un modèle de planification permettant de réduire l’énergie du processeur. Dans Actes du 36e symposium de l'IEEE sur les fondements de l'informatique (1995), 374–382.

• Exploration de la consommation énergétique des algorithmes de tri des données dans les environnements mobiles et intégrés

• Complexité énergie-temps des algorithmes: modéliser les compromis du VLSI CMOS (2007) par Brad D. Bingham

Les complexités spatio-temporelles sont indépendantes de l'appareil. Je ne vois pas de moyen de rendre les appareils à complexité énergétique indépendants.

$W$$W$$W$

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