Formalne pojęcie złożoności energetycznej problemów obliczeniowych

Złożoność obliczeniowa obejmuje badanie złożoności problemów obliczeniowych w czasie lub przestrzeni. Z punktu widzenia przetwarzania mobilnego energia jest bardzo cennym zasobem obliczeniowym. Czy istnieje dobrze zbadana adaptacja maszyn Turinga, które odpowiadają za energię zużywaną podczas wykonywania algorytmów. Czy istnieją ustalone klasy złożoności energetycznej dla problemów obliczeniowych?

Referencje są mile widziane.

Czy istnieje dobrze zbadana adaptacja maszyn Turinga, która odpowiada za energię zużywaną podczas wykonywania algorytmów? Nie!

Ale może wymyślisz jeden. Możliwe jest podzielenie kroków maszyny Turinga na odwracalne i nieodwracalne (nieodwracalne są tam, gdzie informacje są tracone). Teoretycznie tylko nieodwracalne kroki kosztują energię. Teoretycznie właściwym miernikiem byłby koszt jednej jednostki energii za każdy wymazany bit.

Istnieje twierdzenie Charlesa Bennetta, że ​​złożoność czasu wzrasta co najwyżej o stałą, gdy obliczenia stają się odwracalne (CH Bennett, Logical Reversible of Computation ), ale jeśli istnieją również ograniczenia przestrzeni, to uczynienie odwracalności obliczeniowej może spowodować znaczny wzrost czasu (odniesienie tutaj) . Zasada landauera mówi, że kasowanie trochę kosztuje energii, gdzie T jest temperaturą, a k jest stałą Boltzmanna. W prawdziwym życiu nie można zbliżyć się do osiągnięcia tego minimum. Możesz jednak budować układy, które wykonują kroki odwracalne, zużywając znacznie mniej energii niż zużywają w przypadku kroków nieodwracalnych. Jeśli podasz kroki odwracalne koszt α, a kroki nieodwracalne koszt β , wydaje się, że może to dać rozsądny model teoretyczny.$kT\, \ln 2$$T$$k$$\alpha$$\beta$

Nie wiem, w jaki sposób maszyny Turinga z pewnymi odwracalnymi krokami odnoszą się do układów z niektórymi odwracalnymi obwodami, ale myślę, że oba modele są warte zbadania.

Nie ma jeszcze klas złożoności energetycznej, ale zdecydowanie istnieje duże zainteresowanie badaniem sposobu projektowania algorytmów, które są energooszczędne w niektórych modelach. Nie znam całego zakresu pracy, ale jednym punktem wyjścia jest praca, którą Kirk Pruhs wykonuje w zakresie zrównoważonego przetwarzania. Kirk jest teoretykiem z doświadczeniem w planowaniu i aproksymacjach, a ostatnio stał się bardzo aktywny w tej dziedzinie, więc jego perspektywa jest dobra dla ludzi algorytmicznych.

Ps gabgoh o zasadzie Landauera jest dobry. Jeśli chcesz dowiedzieć się więcej o związku między energią a informacją, nie ma lepszego źródła niż książka Demona Maxwella .

To wcale nie jest bezpośrednia odpowiedź, ale niektóre potencjalnie przydatne powiązania z programami do rysowania / badań, które będą prowadzone zgodnie z pracami Staya i Baeza nad termodynamiką algorytmiczną: http://johncarlosbaez.wordpress.com/2010/10 / 12 / algorytmiczna termodynamika /

Zwróć jednak uwagę, że ta praca nie wyciąga faktycznych konsekwencji fizycznych - raczej ilustruje związek, który jak dotąd jest czysto matematyczny.

Kei Uchizawa i jego współautorzy badają złożoność energetyczną obwodów progowych. Określają to jako maksymalną liczbę bramek progowych, które dają 1 na wszystkich możliwych wejściach.

Ponieważ nie chodzi o maszyny Turinga, nie odpowiada to na pytanie. Ale mam nadzieję, że ich artykuły podają kilka pomysłów. Jego strona zawiera wskaźniki. http://www.nishizeki.ecei.tohoku.ac.jp/nszk/uchizawa/

Istnieje uzasadnienie dla zastosowania modelu pamięci zewnętrznej jako modelu obliczeń uwzględniających zużycie energii. Paolo Ferragina omówił to krótko w swoim zaproszonym wystąpieniu na ESA 2010, ale nie wiem, czy są jakieś opublikowane wyniki. Podstawową ideą jest to, że jeśli liczba I / O dominuje w czasie obliczeń, wówczas energia wymagana dla tych I / O prawdopodobnie będzie dominować w całkowitym zużyciu energii.

Raport z pierwszego warsztatu w Science of Power Management zawierał głównie otwartych pytań i problemów. Nie wiem, co wydarzyło się podczas Drugich Warsztatów , ale strony internetowe mówią, że będzie specjalny numer Sustainable Computing poświęcony teoretycznym, matematycznym i algorytmicznym podejściom do zrównoważonych obliczeń.

oto kilka nowszych / innych odniesień / punktów widzenia na to pozornie głębokie pytanie z trwającymi badaniami. jak wskazał P.Shor, wydaje się, że do tej pory obszar ten czeka na kompleksowe badanie, standaryzację i / lub unifikację. na pierwszym miejscu są bardziej abstrakcyjne / teoretyczne podejścia, a następnie bardziej stosowane: algorytmy energooszczędne, pomiar zużycia energii w urządzeniach mobilnych do sortowania, badanie czynników VLSI wpływających na złożoność energii / czasu.

• Model złożoności energetycznej dla algorytmów, Swapnoneel Roy Atri Rudra Akshat Verma ITCS 2013

• W kierunku złożoności energetycznej obliczeń Alain J. Martin, IPL 2001

• Złożoność a energia: teoria obliczeń i fizyka teoretyczna Yuri I. Manin

• W kierunku modelu złożoności energii dla algorytmów Ravi Jain, David Molnar, Zulfikar Ramzan

• Energooszczędne algorytmy Susanne Albers

• Yao, FF, Demers, AJ, Shenker, S. Model planowania dla zmniejszonej energii procesora. W materiałach 36. sympozjum IEEE na temat podstaw informatyki (1995), 374–382.

• Badanie zużycia energii przez algorytmy sortowania danych w środowiskach osadzonych i mobilnych Christian Bunse Hagen Ho ̈pfner Essam Mansour Suman Roychoudhury

• Złożoność algorytmów energii w czasie: modelowanie kompromisów CMOS VLSI (2007), autor: Brad D. Bingham

Złożoność czasu i przestrzeni jest niezależna od urządzenia. Nie widzę sposobu na uniezależnienie urządzenia o złożoności energetycznej.

$W$$W$$W$

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