logo elektroda
logo elektroda
X
logo elektroda
Adblock/uBlockOrigin/AdGuard mogą powodować znikanie niektórych postów z powodu nowej reguły.

AVR - Optymalizacja dzielenia przez stałą 8-bitową bez sprzętowego dzielenia

pawlik118 01 Lut 2014 12:29 2955 7
  • #1 13247485
    pawlik118
    Poziom 32  
    Witam serdecznie,

    Chciałbym się podzielić z Państwem programowym rozwiązaniem szybkiego dzielenia przez (małą) stałą liczby 8 bit.
    Długo szukałem jakiegokolwiek wytłumaczenia dlaczego AVRy nie zostały wyposażone w moduł sprzętowego dzielnia, i niestety wprost tej informacji nie

    znalazłem.
    Uniwersalne procedury, zgodnie z opracowaniem Atmela o nazwie AVR200 na wykonadzie dzielenia zużywają 58 lub 97 cykli, oraz 66 lub 14 bajtów kodu.
    Celem zwiększenia szybkości wykonywania kodu można zastosować poniższy sposób:


    Dla przykładu, dzielenie zmiennej U (8bit) przez 3:

    Dzielenie przez 3, to inaczej mnożenie przez 0,3333.. Część AVRów atmela ma sprzętowy moduł mnożenia, wykonujący mnożenie w 2 cyklach.

    Przykład dla Bascom:

    Kod: text
    Zaloguj się, aby zobaczyć kod


    potencjometr podłączony pod ADC(7). W zmiennej Pot, w zależności od wartości z potencjometru mamy wartości od 15 do 100.
    Niestety BASCOM dla Atmegi328P podczas kompilacji nie wykorzystuje sprzętowego mnożenia (MUL) tylko programowe, przez co zysk z takiego dzielenia nie jest aż

    tak duży. Dla porównania:

    Dzielenie w Bascomie U = U / 3 zajmuje 112 cykli, a dzielenie jak wyżej 48 cykli.

    Przy okazji będę wdzięczny za informację (jeśli ktoś wie) dlaczego AVRy nie mają dzielenia będę wdzieczny.


    pozdrawiam

    Moderowany przez dondu:

    SYNTAX - Wklejając kod programu używaj proszę znacznika SYNTAX. Składnia jest wtedy kolorowana i łatwo kod analizować, a dodatkowo posty są krótkie.

  • #2 13248307
    excray
    Poziom 41  
    AVRy to procesory RISC i jak na RISC to i tak za dużo mają rozkazów. A jeśli chcesz pisac oszczędne programy to porzuć Bascom na rzecz asemblera. Albo chociaż C.
  • #3 13248344
    BlueDraco
    Specjalista - Mikrokontrolery
    Dlaczego nie mają dzielenia? To proste - dzielenie jest najtrudniejszym w implementacji sprzętowej z podstawowych działań arytmetycznych - złożoność sprzętowej dzialarki jest wielokrotnie większa, niż sprzętowej mnożarki, a mnożarki - wielokrotnie większa od sumatora. instrukcji dzialenia nie ma również Cortex M0, a procesory, które ją mają, wykonują jł zwykle kilka..kilkadziesiąt razy wolniej od instrukcji mnożenia.
    Sprzętowe dzielenie miały '51, ale tylko 8/8 bitów, a pożytek z niego jest znikomy.

    Dzielenie przez stałą, które nie musi być idealnie dokładne, zawsze można zrobić jako mnożenie przez licznik ułamka, którego mianownik jest potęgą dwójki, z dzieleniem przez mianownik zrealizowanym jako przesuwanie lub wybór odpowiedniej części wyniku.

    Z kolei mnożenie przez stałą często najszybciej jest wykonać jako serię dodawań lub odejmowań.
    Dzielenie przez 3 możesz zrobić jako:
    y = x * 86 / 256 = (x * 64 + x * 16 + x * 4) / 256 =
    = (((x << 2) + x) << 2) + x) << 2) / 256

    Czyli inaczej - trzy przesunięcia, dwa dodawania (16-bitowe) i wybór bardziej znaczącego bajtu. Powinno to zająć nie więcej niż 20 instrukcji AVR.
  • #4 13248627
    pawlik118
    Poziom 32  
    Jasne, wiadomo że kod wynikowy po kompilacji w Bascomie nie będzie optymalny. Akurat ten program do złożonego sterownika CO pisałem w Bascomie bo nie zależało mi na szybkości i wielkości, tylko na tym żeby działał i by szybko go napisać.
    Przykład ten zrobiłem w celu edukacyjnym. Dzięki za rozwinięcie mnożenia x*86 jako ciąg przesuwań. Atmega jednak ma sprzętowe mnożenie więc wystarczy użyć dobrego kompilatora i cały mój algorytm wykona się w kilku cyklach.


    Co do braku DIV to jedyne co mnie przekonuje to jak pisał kolega wyżej - trudność w implementacji tej struktury w ALU procesora i brak większej użyteczności. jednakże AVR to już prawie Risc bo właściwie mają nie mniej instrukcji niż CISC. Z drugiej strony to choć rzadko to czasem przydaje się dzielenie, to myślę że implementacja rozkazu DIV znacząco kosztu procesora by nie zwiększyła.
  • #5 13248884
    tmf
    VIP Zasłużony dla elektroda
    Jak sam zauważyłeś wiele problemów rozwiązuje sprawny kompilator - gcc sam od siebie robi optymalizacje o których nawet średnio zaawansowani programiści nie wiedzą. Dlatego przykład Bascoma jakby kłóci się z optymalizacjami i szybkością.
    Co do braku dzielenia na AVR - kolega BluDraco to sensownie uzasadnił, ja dodam od siebie tylko conieco. Jak BlueDraco napisał dzielenie 8b/8b jest bez sensu - praktyczna przydatność jest żadna. Z dzielenia 16b/8b też za wiele nie wynika - praktycznie to samo można osiągnąć niewiele wodniej trikami jakie pokazał BlueDraco, a unika się wprowadzenia dodatkowego bloku w procesorze. Z kolei dzielenie 32b/8b lub 32b/16b byłoby może i fajne, tylko jak spojrzysz na biednego AVRa to wymagałoby wykorzystania aż sześciu z jego 32 rejestrów (+ opcjonalnie 6 rejestrów na wynik). Czyli trzebaby wyodrębnić jakieś rejestry specjalne (np. na wynik) tak jak jest w przypadku instrukcji MUL i pochodnych, czyli nasza piękna ortogonalna lista instrukcji właśnie idzie do piachu. Dla programisty w asemblerze to pikuś, ale dla developera kompilatora C/C++ robi się z tego koszmar. Bo trzeba uwzględniać wyjątki, prewencyjnie zachowywać rejestry na stosie, bo nie wiadomo czy handler przerwań ich nie zepsuje itd. W efekcie więcej z tego strat niż pożytku, a dobrze napisana funkcja dzielenia całkowitego nie jest aż tak czasochłonna, z kolei dzielenie przez stałą prosto można zoptymalizować. No i jeszcze jedna rzecz - sprzętowa dzielarka to także zużycie energii, a przecież mówimy o prockach, króych jedną z zalet jest niski pobór energii. Czyli wprowadzenie DIV dużo komplikuje, a nic nie daje.
  • #6 13249591
    pawlik118
    Poziom 32  
    Witam,
    Nie twierdzę że mój sposób sprawdzi się w Bascomie, dużo lepiej sprawdzi się asemblerze. Napisałem w Bascomie tak dla przykładu, myślę że tak jest przejrzyście, a chodzi po prostu o zasadę - sposób.

    AVR - serii Atmega to 8bitowce, więc tutaj w grę wchodziłoby tylko 8bit/8bit. Natomiast co ciekawe, AVR32 też nie ma dzielenia sprzętowego.
    Całkiem prosty przykład z życia wzięty - sterowanie silnikami krokowymi w osiach x,y, gdzie danymi wejściowymi są funkcje (np okrąg lub prosta), oparte o argumenty z 32bitową dokładnością. Rozdzielczość silników krokowych 1=1 powiązana z wartością w rejetrze (np x=100 silnik jedzie o 100kroków). W takim sterowaniu Y trzeba wyznaczać w każdym kroku aby mieć max dokładność (rozdzielczość) Aby wyznaczyć y=f(x) trzeba wykonywać dzielenie liczby 32bit. Niestety, nawet AVR32 nie oferuje dzielenia więc sprawa się komplikuje. W rzeczywistości, ze względu na długi czas liczenia silniki są wolne.
    De facto nie ma nawet opcji - droższego procka z modułem dzielenia, co zmusza niejako na zmianę rodziny, na np. dsPic32.

    Co do poboru mocy to myślę że akurat sprzętowy moduł dzielenia zużył by mniej Wh energii robiąc dzielenie w kilku prądożernych cyklach zamiast je robić w kilkuset oszczędnych - więc sprawa nie jest taka jednoznaczna :)
  • #7 13249687
    BlueDraco
    Specjalista - Mikrokontrolery
    Proble z obliczeniami w AVR ie polega na braku dzielenia, a na tym, że liczymy na 8 bitach. Prosta operacja 16-bitowa - to min. 2..3 instrukcje, 32-bitowe - 8..12 instrukcji.
    W 8-bitowym procesorze nie ma żadnego pożytku z dzielenia, bo w programach, w których potrzebne jest dzielenie, używa się danych 16- lub 32-bitowych, a w przeciwieństwie do mnożenia "składanie" dłuższego dzielenia z krótszych nie jest możliwe. Dzielenie w AVR byłoby istotnie szybsze, gdyby procesor potrafił wykonywać 16-bitowe dodawanie, odejmowanie i przesunięcia.

    O tym, że rezygnacja z dzielenia jest istotna dla złożoności procesora, świadczy przytoczony przeze mnie wyżej fakt, że 32-bitowy Cortex-M0 nie ma dzielenia (a większy, chociaż starszy M3 ma).
  • Pomocny post
    #8 13249770
    tmf
    VIP Zasłużony dla elektroda
    pawlik118 napisał:
    Witam,
    Nie twierdzę że mój sposób sprawdzi się w Bascomie, dużo lepiej sprawdzi się asemblerze. Napisałem w Bascomie tak dla przykładu, myślę że tak jest przejrzyście, a chodzi po prostu o zasadę - sposób.

    AVR - serii Atmega to 8bitowce, więc tutaj w grę wchodziłoby tylko 8bit/8bit. Natomiast co ciekawe, AVR32 też nie ma dzielenia sprzętowego.
    Całkiem prosty przykład z życia wzięty - sterowanie silnikami krokowymi w osiach x,y, gdzie danymi wejściowymi są funkcje (np okrąg lub prosta), oparte o argumenty z 32bitową dokładnością. Rozdzielczość silników krokowych 1=1 powiązana z wartością w rejetrze (np x=100 silnik jedzie o 100kroków). W takim sterowaniu Y trzeba wyznaczać w każdym kroku aby mieć max dokładność (rozdzielczość) Aby wyznaczyć y=f(x) trzeba wykonywać dzielenie liczby 32bit. Niestety, nawet AVR32 nie oferuje dzielenia więc sprawa się komplikuje. W rzeczywistości, ze względu na długi czas liczenia silniki są wolne.
    De facto nie ma nawet opcji - droższego procka z modułem dzielenia, co zmusza niejako na zmianę rodziny, na np. dsPic32.

    Co do poboru mocy to myślę że akurat sprzętowy moduł dzielenia zużył by mniej Wh energii robiąc dzielenie w kilku prądożernych cyklach zamiast je robić w kilkuset oszczędnych - więc sprawa nie jest taka jednoznaczna :)


    Nie wydaje mi się aby akurat przy silnikach był to istotny problem - ile takich operacji na sekundę trzeba wykonać? Nie sądzę aby akurat dzielenie tu było wąskim gardłem, prędzej niepotrzebne obliczenia na niepotrzebnie zbyt długich typach, lub ogólnie nieoptymalny algorytm.
    Druga sprawa - są AVR32, które mają FPU, można je wykorzystać do takich celów jeśli ktoś naprawdę potrzebuje.
REKLAMA