Noção formal para complexidade energética de problemas computacionais

35

A complexidade computacional inclui o estudo da complexidade do tempo ou espaço de problemas computacionais. Do ponto de vista da computação móvel, a energia é um recurso computacional muito valioso. Portanto, existe uma adaptação bem estudada das máquinas de Turing que respondem pela energia consumida durante a execução dos algoritmos. Além disso, existem classes de complexidade energética estabelecidas para problemas computacionais?

Referências são apreciadas.

Mohammad Al-Turkistany
fonte
11
O consumo de energia depende da máquina e é uma questão prática, ou seja, as constantes ocultas na análise clássica são geralmente de interesse (qualquer diferença entre tempo de execução e consumo de energia).
Raphael
6
Teoricamente, você pode executar etapas reversíveis sem custo de energia. Praticamente, pode-se construir chips que executam etapas reversíveis a um custo de energia substancialmente mais baixo do que etapas não reversíveis. Como isso se traduz em teoria não está claro, mas talvez possamos definir um modelo de máquina de Turing que execute etapas reversíveis no custo e etapas não reversíveis no custo β e comece a raciocinar teoricamente sobre o consumo de energia. Pelo menos é possivelmente melhor do que levantar as mãos em desespero e dizer "tudo depende da máquina". αβ
quer
Susanne Albers escreveu uma excelente pesquisa na Comunicação do ACM, algoritmos de eficiência energética. cacm.acm.org/magazines/2010/5/87271-energy-efficient-algorithms/…
Mohammad Al-Turkistany

Respostas:

28

Existe uma adaptação bem estudada das máquinas de Turing que respondem pela energia consumida durante a execução de algoritmos? Não!

Mas talvez você possa inventar um. É possível que você possa dividir as etapas da máquina de Turing em reversíveis e não reversíveis (as não reversíveis são onde as informações são perdidas). Teoricamente, são apenas as etapas não reversíveis que custam energia. Um custo de uma unidade de energia para cada bit que é apagado seria teoricamente a medida certa.

Existe um teorema de Charles Bennett de que a complexidade do tempo aumenta no máximo uma constante quando um cálculo é tornado reversível (CH Bennett, Reversibilidade Lógica de Computação ), mas se houver também limites no espaço, a reversibilidade computacional pode resultar em aumento substancial no tempo (referência aqui) . O princípio de Landauer diz que apagar um pouco custa de energia, onde T é temperatura ek é constante de Boltzmann. Na vida real, você não pode chegar nem perto de atingir esse mínimo. No entanto, você pode criar chips que executam etapas reversíveis usando substancialmente menos energia do que eles usam para etapas irreversíveis. Se você der passos reversíveis, um custo de αkTln2Tkα e aos passos irreversíveis um custo de , parece que isso pode dar um modelo teórico razoável.β

Não sei como as máquinas de Turing com algumas etapas reversíveis se relacionam com os chips com alguns circuitos reversíveis, mas acho que vale a pena investigar os dois modelos.

Peter Shor
fonte
Peter, nas discussões sobre a tese eficiente de Church-Turing, lembro-me de ler sobre levar em consideração a quantidade de energia usada na computação. Você sabe se existe uma boa referência sobre o assunto? (Eu posso postar isso como uma questão separada, se você preferir isso.)
Kaveh
4
Se você está preocupado apenas com fatores polinomiais, como na tese de Efficient Church-Turing, tudo dá certo, porque você pode obter computação reversível (quantidade arbitrariamente pequena de energia gasta) com apenas um aumento constante de fator no tempo, e o espaço não pode ser maior que o tempo. Acho que vi uma boa pesquisa recente sobre essas coisas. Espero que alguém possa localizá-lo.
quer
Obrigado Peter, acho que posso encontrá-lo usando o Google (postarei uma pergunta se não encontrar).
Kaveh
idéias interessantes que levam à pergunta: quanto os algoritmos arbitrários podem ser transformados em cálculos reversíveis? como na computação qm, isso sempre é possível com bits "ancilla", mas manter esse "scratch" pode diminuir a eficiência do algoritmo em alguns casos e talvez até agora não seja tão bem compreendido quanto. nota Williams tem algumas ideias sobre cálculos reversíveis espaço-eficiente
vzn
Mesmo que tenhamos uma máquina de computação reversível, ainda existem alguns custos de energia "ocultos": quando queremos executar uma nova computação, precisamos criar um novo banco de memória ou apagar alguns dos dados escritos anteriormente para liberar espaço. para a nova entrada e cálculos. Como isso afeta a resposta? (por exemplo, o cálculo reversível geralmente assume acesso a uma seção da memória inicial "em branco"? Parece trapaça ...)
usul
7

Ainda não há classes de complexidade de energia, mas definitivamente há muito interesse em estudar como projetar algoritmos que são eficientes em termos de energia em algum modelo. Não estou familiarizado com todo o corpo do trabalho, mas um ponto de entrada é o trabalho que Kirk Pruhs está fazendo em computação sustentável. Kirk é um teórico com experiência em programação e aproximações e recentemente se tornou muito ativo nessa área, portanto sua perspectiva é boa para pessoas algorítmicas.

O argumento de ps gabgoh sobre o princípio de Landauer é bom. Se você quiser aprender mais sobre a relação entre energia e informação, não há fonte melhor do que o livro Demônio de Maxwell .

Suresh Venkat
fonte
+1 Obrigado Suresh pela sua resposta.
Mohammad Al-Turkistany
5

Esta não é uma resposta direta, mas existem algumas conexões potencialmente úteis para desenhar / pesquisar programas a serem conduzidos de acordo com o trabalho de Stay e Baez sobre termodinâmica algorítmica: http://johncarlosbaez.wordpress.com/2010/10 / 12 / termodinâmica algorítmica /

Observe, no entanto, que este trabalho não gera consequências físicas reais - mas ilustra uma conexão que é, até agora, puramente matemática.

sclv
fonte
5

Kei Uchizawa e seus co-autores estudam a complexidade energética dos circuitos de limiar. Eles o definem como o número máximo de portas de limiar que emitem 1 sobre todas as entradas possíveis.

Como não se trata de máquinas de Turing, isso não responde à pergunta. Mas espero que os documentos deles dêem algumas idéias. Sua página contém indicadores. http://www.nishizeki.ecei.tohoku.ac.jp/nszk/uchizawa/

Yoshio Okamoto
fonte
4

Há alguma justificativa para usar o modelo de memória externa como um modelo de computação com reconhecimento de energia. Paolo Ferragina discutiu isso brevemente em sua palestra convidada na ESA 2010, mas não sei se existem resultados publicados. A idéia básica é que, se o número de E / S dominar o tempo de computação, a energia necessária para essas E / S provavelmente dominará o consumo total de energia.

O relatório do Primeiro Workshop sobre a Ciência do Gerenciamento de Energia continha principalmente perguntas e problemas em aberto. Não sei o que aconteceu no Segundo Workshop , mas as páginas da web informam que haverá uma edição especial de Computação Sustentável dedicada a abordagens teóricas, matemáticas e algorítmicas da computação sustentável.

Jouni Sirén
fonte
0

Aqui estão algumas / outras referências / ângulos mais recentes sobre essa questão aparentemente profunda com pesquisas em andamento. como indicado por P.Shor, a área até agora parece aguardar uma pesquisa abrangente, padronização e / ou unificação. existem abordagens mais abstratas / teóricas listadas em 1º, seguidas por abordagens mais aplicadas: algoritmos de eficiência energética, medição do uso de energia em dispositivos móveis para classificação, estudo de fatores no VLSI que afetam a complexidade energia / tempo.

vzn
fonte
-3

As complexidades de tempo e espaço são independentes do dispositivo. Não vejo uma maneira de tornar independente o dispositivo de complexidade energética.

WWW

O(Wf(n))=O(f(n))

Pratik Deoghare
fonte
Estou votando negativamente nesta resposta, pois acho que ela está errada. Eu acho que há alguma justificativa teórica para colocar um limite mais baixo no consumo de energia de qualquer algoritmo baseado no princípio de Landauer. Acho a pergunta muito sensata.
gabgoh
@gabgoh Receio que qualquer limite inferior geral tenha que fazer suposições de uniformidade que derrotariam o objetivo. @TheMachineCharmer De fato, processadores reais podem ter diferentes ordens de comandos por eficiência. Voto positivo, embora seu segundo parágrafo me confunda.
Raphael
4
αβαβαβ
11
@ Konrad: gabgoh está se referindo a Rolf Landauer, não a Lev Landau.
quer
11
@ Peter: obrigado pela informação. Só para constar, eu estava falando sobre Edmund Landau, inventor da notação big-O. Eu pensei que era a isso que gabgoh estava se referindo com o "princípio de Landauer".
Konrad Rudolph