Ile FLOP potrzebuje tanh?

Question

Chciałbym obliczyć, ile flopów potrzebuje każda warstwa LeNet-5 (paper). Niektóre dokumenty udostępniają FLOP-y dla innych architektur (1, 2, 3). Jednak w tych dokumentach nie podano szczegółów, jak obliczyć liczbę FLOPów i ​​nie mam pojęcia, ile FLOP jest koniecznych dla nieliniowych funkcji aktywacyjnych . Na przykład, ile FLOPów jest konieczne do obliczenia tanh(x)?

Domyślam się, że będzie to wdrożenie i prawdopodobnie również specyficzne dla sprzętu. Jednak jestem głównie zainteresowany uzyskaniem rzędu wielkości. Czy mówimy o 10 FLOPach? 100 FLOPów? 1000 FLOPów? Wybierz więc dowolną architekturę/implementację, jaką chcesz dla swojej odpowiedzi. (Chociaż doceniam odpowiedzi, które są bliskie "zwykłym" konfiguracjom, takim jak Intel i5/nvidia GPU/Tensorflow)

Answer 1

Uwaga: Ta odpowiedź nie jest specyficzna dla Pythona, ale nie sądzę, żeby coś takiego jak tanh było zasadniczo różne w różnych językach.

Tanh jest zwykle realizowany poprzez zdefiniowanie górnej i dolnej granicy, dla której zwracane są odpowiednio 1 i -1. Część pośrednia jest przybliżona z różnych funkcji w następujący sposób:

Interval 0 x_small    x_medium    x_large 
    tanh(x) | x | polynomial approx. | 1-(2/(1+exp(2x))) | 1 

Istnieją wielomiany, które są dokładne do pojedynczych punktów precisision pływających, a także o podwójnej precyzji. Algorytm ten nazywa się algorytmem Cody-Waite.

Powołując this description (można znaleźć więcej informacji na temat matematyki, również tam, na przykład, jak ustalić x_medium) Cody i racjonalna forma Waite wymaga czterech mnożenia, trzy dodatki i jeden oddział w pojedynczej precyzji i siedmiu mnożenia, sześć dodatków i jeden podział w podwójnej precyzji.

Dla ujemnego x można obliczyć | x | i odwróć znak. Potrzebne są zatem porównania, w których występuje przedział x, i oszacuj odpowiednie przybliżenie. To w sumie:

1. Biorąc wartość bezwzględna x
2. 3 porównań do przedziału
3. W zależności od przedziału i precyzji pływaka, od 0 do kilku japonki dla wykładniczy, sprawdź this question na jak obliczyć wykładniczy.
4. Jedno porównanie, aby zdecydować, czy odwrócić znak.

To jest raport z 1993 roku, ale nie sądzę, że wiele się tu zmieniło.

Answer 2

Jeśli spojrzymy na glibc-realizacji tanh(x) widzimy:

1. dla x większe wartości 22,0 i podwójnej precyzji, tanh(x) można bezpiecznie założyć, aby być 1,0, więc nie ma prawie żadnych kosztów.
2. dla bardzo małych x, (powiedzmy x<2^(-55)) możliwe jest inne tanie przybliżenie: tanh(x)=x(1+x), więc potrzebne są tylko dwie operacje zmiennoprzecinkowe.
3. dla wartości w beetween, można przepisać tanh(x)=(1-exp(-2x))/(1+exp(-2x)).Jednak jeden musi być dokładny, ponieważ 1-exp(t) jest bardzo problematyczny dla małych wartości t ze względu na utratę istotności, więc jeden używa expm(x)=exp(x)-1 i oblicza tanh(x)=-expm1(-2x)/(expm1(-2x)+2).

Zasadniczo, najgorszy przypadek to około 2 razy większa liczba operacji wymaganych dla expm1, co jest dość skomplikowaną funkcją. Najlepszym sposobem jest prawdopodobnie zmierzenie czasu potrzebnego do obliczenia tanh(x) w porównaniu z czasem potrzebnym do prostego mnożenia dwóch podwójnych.

My (niechlujny) eksperymenty na Intel procesor dało następujący wynik, który daje z grubsza:

Więc za bardzo małe i numery> 22 nie ma prawie żadnych kosztów, na liczbach do 0.1 płacimy 6 FLOPS, a następnie koszty rosną do około 20 FLOPS za tanh -klimulacji.

Kluczowe dania na wynos: koszty obliczania tanh(x) zależą od parametru x, a maksymalne koszty wynoszą od 10 do 100 operacji FLOP.

---

Jest Intel-nauka zwana F2XM1 który oblicza 2^x-1 dla -1.0<x<1.0, które mogłyby zostać wykorzystane do obliczenia tanh, przynajmniej do pewnego zakresu. Jednak jeśli wierzyć, że koszt ten wynosi około 60 FLOP-ów.

---

Kolejnym problemem jest wektoryzacja - normalna implementacja glibc nie jest wektoryzowana, o ile widzę. Więc jeśli twój program używa wektoryzacji i musi użyć niewulgaryzowanej implementacji tanh, spowolni to program jeszcze bardziej. W tym celu kompilator intel ma bibliotekę mkl, która między innymi jest jedną z wielu.

Jak widać w tabelach maksymalne koszty wynoszą około 10 zegarów na operację (koszty operacji pływakowej wynoszą około 1 zegara).

---

Chyba jest szansa, by wygrać jakieś japonki za pomocą -ffast-math opcję kompilatora, co powoduje szybsze, ale mniej precyzyjne programu (to opcja dla Cuda lub C/C++, nie wiem, czy to możliwe zrobić dla Pythona/numpy).

---

Kod C++, który wygenerował dane dla figury (skompilowany za pomocą g ++ -std = C++ 11 -O2). Jego zamiar nie dać dokładnej liczby, ale pierwsze wrażenie na temat kosztów:

#include <chrono> 
#include <iostream> 
#include <vector> 
#include <math.h> 

int main(){ 
    const std::vector<double> starts={1e-30, 1e-18, 1e-16, 1e-10, 1e-5, 1e-2, 1e-1, 0.5, 0.7, 0.9, 1.0, 2.0, 10, 20, 23, 100,1e3, 1e4}; 
    const double FACTOR=1.0+1e-11; 
    const size_t ITER=100000000; 


    //warm-up: 
    double res=1.0; 
     for(size_t i=0;i<4*ITER;i++){ 
     res*=FACTOR; 
    } 
    //overhead: 
    auto begin = std::chrono::high_resolution_clock::now(); 
    for(size_t i=0;i<ITER;i++){ 
     res*=FACTOR; 
    } 
    auto end = std::chrono::high_resolution_clock::now(); 
    auto overhead=std::chrono::duration_cast<std::chrono::nanoseconds>(end-begin).count(); 
    //std::cout<<"overhead: "<<overhead<<"\n"; 


    //experiments: 
    for(auto start : starts){ 
     begin=std::chrono::high_resolution_clock::now(); 
     for(size_t i=0;i<ITER;i++){ 
      res*=tanh(start); 
      start*=FACTOR; 
     } 
     auto end = std::chrono::high_resolution_clock::now(); 
     auto time_needed=std::chrono::duration_cast<std::chrono::nanoseconds>(end-begin).count(); 
     std::cout<<start<<" "<<time_needed/overhead<<"\n"; 
    } 

    //overhead check: 
    begin = std::chrono::high_resolution_clock::now(); 
    for(size_t i=0;i<ITER;i++){ 
     res*=FACTOR; 
    } 
    end = std::chrono::high_resolution_clock::now(); 
    auto overhead_new=std::chrono::duration_cast<std::chrono::nanoseconds>(end-begin).count(); 
    std::cerr<<"overhead check: "<<overhead/overhead_new<<"\n"; 
    std::cerr<<res;//don't optimize anything out... 
}