Czy istnieje abstrakcyjna maszyna, która może rejestrować zużycie energii?

13

Zgłaszając złożoność algorytmu algorytmu, zakłada się, że obliczenia leżące u jego podstaw są wykonywane na jakiejś abstrakcyjnej maszynie (np. RAM), która przybliża nowoczesny procesor. Takie modele pozwalają nam raportować złożoność algorytmów w czasie i przestrzeni. Teraz, przy rozproszeniu GPGPU , zastanawia się, czy istnieją dobrze znane modele, w których można również wziąć pod uwagę zużycie energii.

Znane są procesory graficzne, które zużywają znaczną ilość energii, a niektóre instrukcje dzielą się na różne kategorie zużycia energii w zależności od ich złożoności i położenia w wyrafinowanym układzie scalonym. Stąd instrukcje, z energii widzenia, nie mają kosztu jednostkowego (ani nawet stałego). Trywialnym rozszerzeniem byłoby przypisywanie wag do kosztów operacyjnych, ale szukam silnego modelu, w którym operacja / instrukcja może kosztować niestałe jednostki energii, np. Wielkość wielomianową (lub nawet bardziej złożoną np .: funkcję czasu, który upłynął od początku algorytmu; lub biorąc pod uwagę prawdopodobieństwo awarii układu chłodzenia, która nagrzeje układy i spowolni częstotliwość taktowania itp.)

Czy istnieją takie modele, w których można uwzględnić nietrywialne koszty i usterki?

— Gopi
źródło

Czy masz powody sądzić, że ilość energii przypadającej na elementarne koszty operacyjne może ulec (złożonej) zmianie? Jeśli jesteś zainteresowany, wiem o pracy, która analizuje zużycie energii za pomocą narzędzi teoretycznych.

— Raphael

8

Nie ma jeszcze ustalonego modelu, ale obecnie jest to obszar aktywnych badań. Jednym z ekspertów od algorytmów jest Kirk Pruhs. Jego artykuły zawierają więcej informacji i możesz także przejrzeć tę prezentację .

— Suresh
źródło

Nie zgadzam się z faktem, że nie ma jeszcze ustalonego modelu: większość artykułów zgadza się co do skomplikowanego modelu fizycznego, po prostu koncentruje się na innej części tego modelu fizycznego. W przypadku insyncji Kirk koncentruje się na energii dynamicznej.

— Gopi,

Myślę, że mam na myśli, że nie ma ustalonego modelu kosztów obliczeniowych.

— Suresh

7

Modele zużycia energii

Skalowanie prędkości jest jednym z najczęściej używanych modeli (ostatnio) przy rozważaniu zużycia energii. Polega na modyfikacji napięcia zasilania. Obniżając napięcie zasilania lub częstotliwość taktowania procesora, można osiągnąć znaczne zmniejszenie zużycia energii; wyższe prędkości pozwalają na szybsze wykonanie, ale prowadzą również do znacznie wyższego (ponadliniowego) zużycia energii.

$s$ $s^3$ $s^3 \times d$ $d$

Jednak skalowanie prędkości nie jest jedyną rozważaną energią. Jest to tak zwana energia dynamiczna . Energia statyczna to moc wynikająca z „włączenia” procesora. Można pozbyć się tej mocy statycznej , wyłączając procesor w czasie bezczynności. Ma to jednak swój koszt. Dużo pracy wykonano na ten temat, który jest bardzo bliski problemowi z wypożyczaniem sprzętu narciarskiego .

Zwykle zużycie energii jest sumą statycznego i dynamicznego zużycia energii razy czas wykonania. Jednak większość papieru koncentruje się na jednym z tych problemów.

Wprowadzanie błędów w tym modelu

Myślę, że jest to najbardziej zaskakująca część modelu skalowania prędkości. Zwykle można by pomyśleć, że im szybciej wykonasz zadanie, tym bardziej prawdopodobne jest, że wykonanie nie powiedzie się. Przeciwnie, wykazano, że zmniejszenie prędkości procesora zwiększa liczbę przejściowych wskaźników awaryjności systemu; prawdopodobieństwo awarii rośnie wykładniczo, a tego prawdopodobieństwa nie można pominąć w obliczeniach na dużą skalę.

$\lambda$

λ (f) = λ_{0} e^{d \frac{f m a x - f}{f m a x - f m i n}},

$\lambda(f)=\lambda_0 e^{d\frac{fmax-f}{fmax-fmin}},$

f

$f$

[f m i n, f m a x]

$[fmin,fmax]$

λ_{0}

$\lambda_0$

d

$d$

w

$w$

f

$f$

R (f) = e^{- λ (f) \times \frac{w}{f}}

$R(f)=e^{-\lambda(f)\times\frac{w}{f}}$

To jest odniesienie, więc nie wiem, czy jest to doceniane tutaj, jednak jeśli jesteś zainteresowany, możesz znaleźć więcej informacji w tym artykule na temat dynamicznej części zużycia energii.

— Gopi
źródło

3

Podjęto próby analizy zużycia energii przez algorytmy w teorii (oczywiście przy użyciu rzeczywistych kosztów na operację); patrz np. [1]. Chociaż wyniki są wystarczająco zaskakujące - najszybszy algorytm nie zawsze wykorzystuje najmniej energii - pewne przeszkody pozostają.

W szczególności nowoczesne platformy wyłączają niektóre funkcje, co powoduje gwałtowny wzrost kosztów energii podczas ich ponownego włączania. Chociaż w zasadzie możliwe jest włączenie go do rygorystycznej analizy, staje się on (zbyt?) Trudny technicznie. Również wpływ braków pamięci podręcznej na całkowite zużycie energii nie został dobrze zbadany.

Wydaje się, że ogromne różnice między platformami sprzeciwiają się rygorystycznym analizom, które nie mogą (raz) zignorować specyfiki, ponieważ modele ogólne (tj. Przed podłączeniem konkretnych stałych / funkcji) mają ograniczone znaczenie.

Hannah Bayer i Markus E. Nebel: Ocena algorytmów na podstawie ich zużycia energii , obliczalności w Europie, 2009

— Raphael
źródło