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

35

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.

cc.complexity-theory physics

— Mohammad Al-Turkistany
źródło

1

Zużycie energii zależy od maszyny i kwestia praktyczna, tj. Stałe ukryte w klasycznej analizie są zwykle interesujące (każda jedyna różnica między czasem działania a zużyciem energii).

— Raphael

6

Teoretycznie możesz wykonywać odwracalne kroki bez kosztów energii. Praktycznie można budować układy, które wykonują kroki odwracalne przy znacznie niższym koszcie energii niż kroki nieodwracalne. To, jak przekłada się to na teorię, nie jest jasne, ale być może możemy zdefiniować model maszyny Turinga, który wykonuje kroki odwracalne po koszcie

i kroki nieodwracalne po koszcie

i rozpoczyna teoretyczne rozważania na temat zużycia energii. Przynajmniej jest to lepsze niż wzniecenie rozpaczy i powiedzenie „wszystko zależy od maszyny”.

α

$\alpha$

β

$\beta$

— Peter Shor,

Możliwe powiązane: ile mocy obliczeniowej mieści się w centymetrze sześciennym? , Algorytmy DNA i kompletność NP .

— Kaveh

Susanne Albers napisała doskonałą ankietę w komunikacie ACM, Algorytmy energooszczędne. cacm.acm.org/magazines/2010/5/87271-energy-efficient-algorithms/…

— Mohammad Al-Turkistany

28

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 jest temperaturą, a 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.

— Peter Shor
źródło

Peter, w dyskusjach na temat efektywnej tezy Kościoła-Turinga, pamiętam, że czytałem o uwzględnianiu ilości energii zużytej do obliczeń. Czy wiesz, czy istnieje dobre odniesienie do tematu? (Jeśli wolisz, mogę zamieścić to jako osobne pytanie).

— Kaveh

4

Jeśli martwisz się o czynniki wielomianowe, tak jak w przypadku tezy o efektywnym kościele Turinga, wszystko się udaje, ponieważ możesz uzyskać odwracalne obliczenia (dowolnie niewielka ilość zużytej energii) przy jedynie stałym wzroście współczynnika w czasie, a przestrzeń nie może być większa niż czas. Wydaje mi się, że widziałem dobrą ankietę na ten temat. Mam nadzieję, że ktoś to znajdzie.

— Peter Shor,

Dzięki Peter, chyba mogę go znaleźć za pomocą Google (opublikuję pytanie, jeśli go nie znajdę).

— Kaveh

ciekawe pomysły, które prowadzą do pytania, ile dowolnych algorytmów można przekształcić w obliczenia odwracalne? jak w przypadku obliczania qm jest to zawsze możliwe przy użyciu bitów „ancilla”, ale zachowanie tego „zadrapania” może w niektórych przypadkach obniżyć wydajność algorytmu i być może do tej pory nie jest on tak dobrze zrozumiany. uwaga williams ma pewne pomysły na energooszczędne obliczenia odwracalne

— wer

Nawet jeśli mamy maszynę do obliczania odwracalnego, nadal istnieją pewne „ukryte” koszty energii: jeśli chcemy uruchomić nowe obliczenia, musimy albo zbudować nowy bank pamięci, albo usunąć niektóre wcześniej zapisane dane, aby zrobić miejsce dla nowych danych wejściowych i obliczeń. Jak to wpływa na odpowiedź? (np. czy obliczenia odwracalne zwykle zakładają dostęp do części zainicjowanej „pustej” pamięci? wydaje się oszustwem ...)

— usul

7

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 .

— Suresh Venkat
źródło

+1 dzięki Suresh za odpowiedź.

— Mohammad Al-Turkistany

5

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.

— sclv
źródło

5

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/

— Yoshio Okamoto
źródło

4

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ń.

— Jouni Sirén
źródło

0

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

— vzn
źródło

-3

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))$

— Pratik Deoghare
źródło

Głosuję za odrzuceniem tej odpowiedzi, ponieważ wydaje mi się, że nie ma ona sensu. Myślę, że istnieje teoretyczne uzasadnienie dla ustalenia dolnej granicy zużycia energii przez dowolny algorytm oparty na zasadzie Landauera. Uważam to pytanie za bardzo rozsądne.

— gabgoh

@ gabgoh Obawiam się, że jakakolwiek ogólna dolna granica musiałaby przyjąć założenia dotyczące jednolitości, które mogłyby pokonać cel. @TheMachineCharmer W rzeczywistości rzeczywiste procesory mogą mieć różne kolejność poleceń pod względem wydajności. Głosujcie, choć drugi akapit mnie myli.

— Raphael

4

α

$\alpha$

β

$\beta$

α

$\alpha$

β

$\beta$

α

$\alpha$

β

$\beta$

1

@Konrad: gabgoh odnosi się do Rolfa Landauera, a nie do Lwa Landaua.

— Peter Shor,

1

@Peter: dzięki za informacje. Dla przypomnienia mówiłem o Edmundu Landauu, wynalazcy notacji big-O. Myślałem, że to właśnie gabgoh odnosi się do „zasady Landauera”.

— Konrad Rudolph