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

ATmega32 - Skrócenie obliczeń, elementy 13 bitowe i tablica 16 bitowa.

_pieczas 23 Lis 2013 15:13 2547 26
  • #1 12983566
    _pieczas
    Poziom 12  
    W programie mam taki oto kod funkcji:

    Kod: C / C++
    Zaloguj się, aby zobaczyć kod


    Zasadniczo mój problem polega na tym,że program wykonuj się stosunkowo długo na atmedze32 taktowanej 16mhz. Symulując zauważyłem, że największą zakałą jest pętla for w której następuje mnożenie.

    Dane które otrzymuje po SPI to pomiar z przetwornika który ma 13 bitów rozdzielczości. 256*b+c daje dokładnie 13 bitów, gdyż pierwsze 3 bity słowa b zeruję. Tak więc tablica tab[32] mogłaby mieć tym uint16 zamiast uint32, lecz jak się okazuje nie może. Właśnie nie może dlaczego? Czy zna ktoś odpowiedź bo dla mnie jak na razie jest to nie zrozumiałe. Gdy wysyłam wartości otrzymane w tablicy do terminala to dostaje losowe liczby wraz z ujemnymi. Zmiana typu tablicy na unsigned int czy też int również daje ten sam efekt. W takim układzie dostaje próbkę co ok 14 ms, gdyż próbkuje na 2 kanałach. Tak więc czy potrafi ktoś wskazać mi błąd jaki popełniam przez który liczby 13 bitowej nie mogę wpisac do tablicy której argumenty mają 16 bitów?
  • #2 12983723
    zumek
    Poziom 39  
    _pieczas napisał:
    ... Czy zna ktoś odpowiedź bo dla mnie jak na razie jest to nie zrozumiałe...

    Zastanów się przez chwilę i odpowiedz sobie na pytanie:
    Ile bitów trzeba przeznaczyć na wynik, by zapamiętać wynik mnożenia dwóch liczb szesnastobitowych :?:
  • #3 12983771
    _pieczas
    Poziom 12  
    Oczywiście 32 bity.
    Lecz w który miejscu mnożę dwie liczby 16 bitowe podczas zapisywania do tablicy?
    mnożę 8 bitowe b i 256 ( 8bitów ) i dodaję kolejne 5. Do tablicy próbuję zapisać liczbę 13 bitową, a mimo to nie mogę tej tablicy zapisać jako uint16_t.

    w skrajnej sytuacji gdy:
    b=11111111 i c = 11111111 mam
    b=b&00011111 = 00011111
    b<<8 ( mnoże x 256) = 1111100000000
    i dodaję 11111111 co daje ostatecznie 13 jedynek.
  • Pomocny post
    #4 12983815
    excray
    Poziom 41  
    _pieczas napisał:
    Lecz w który miejscu mnożę dwie liczby 16 bitowe podczas zapisywania do tablicy? mnożę 8 bitowe b i 256 ( 8bitów )

    Ty to rozumiesz. Ja to rozumiem. Kompilator tego NIE rozumie.
    Poza tym dziwny ten zapis:
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod
    Ani średnika na końcu ani sensu w środku.
  • #5 12983927
    _pieczas
    Poziom 12  
    kod przepisywałem więc zapomniałem o średniku
    w takim razie
    b= b & 0x1F;

    wniosek taki, że słowa 9-16 bitowe zajmują w pamięci 16 bitów, tak?
    Ma ktoś pomysł jak przyspieszyć tempo obliczeń?
    Na ile mogę polegać na symulatorze w avrstudio4? Jest to chociaż w części dokładne narzędzie? Chodzi mi o czas przeliczeń oraz trwanie rozkazów na podstawie wyświetlonych cykli ("Cycle counter") oraz czasu trwania operacji (Stop watch)

    ams("nop"), trwa wg symulatora 1 cykl więc chociaż na tym poziomie jest dokładność.
  • Pomocny post
    #7 12984060
    BlueDraco
    Specjalista - Mikrokontrolery
    Zacznij od wyrzucenia typu float, potem będzie już z górki.
  • Pomocny post
    #8 12984151
    grko
    Poziom 33  
    Jak chcesz się pozbyć zmiennego przecinka to spróbuj czegoś takiego:

    Kod: C / C++
    Zaloguj się, aby zobaczyć kod
    [/code]
  • #9 12984213
    _pieczas
    Poziom 12  
    [quote="excray"]
    _pieczas napisał:
    kod przepisywałem więc zapomniałem o średniku

    Zapomniałes też chyba że 00111111 to nie to samo co 0b00111111.

    Nie zapomniałem, zwyczajnie o tym nie wiedziałem - masz piwo!


    BlueDraco napisał:
    Zacznij od wyrzucenia typu float, potem będzie już z górki.

    floata to ja chę się pozbyć. On ma 32 bity i obliczenia na nim będą pewnie jeszcze dłuższe niż na uint32. A jeśli nie to zapewne nie będą krótsze.


    Zmienny przecinek nie jest aż tak bardzo uciążliwy bo występuje tylko w wyniku końcowym. Ta pętla trwa niemiłosiernie długo i to mnie wkurza.

    Próbowałem z rzutowaniem:
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod


    nawet gdy przypisuje na sztywno :
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod

    też się wysypuje.

    bardzo mnie to irytuje, już z sił opadam.
    Będę wdzięczny za podpowiedź co zrobić tym aby przyspieszyć obliczenia.
  • #10 12984350
    tmf
    VIP Zasłużony dla elektroda
    Podnosisz do kwadratu każdy element tablicy - zakładając, że masz w niej 13-bitowe wartości, to do kwadratu potrzebują one do zapisu 26 bitów, czyli więcej niż 16. A teraz dlaczego dla tablicy z elementami 16-bitowymi to nie działa - mnożenie uint16_t razy uint16_t daje uwaga uint16_t. Widzisz więc gdzie jest błąd. Gdyby kompilator wiedział, że ma zrobić mnożenie 32-bitowe to wynik byłby poprawny. A skąd ma wiedzieć? Ano trzeba mu powiedzieć, np. poprzez rzutowanie jednego z argumentów na uint32_t przed mnożeniem.
    Kolejna sprawa - jeśli suma przestanie być typu float to dodawanie 32-elementów tablicy pewnie przyśpieszy wielokrotnie.
  • Pomocny post
    #11 12984646
    pbuhne
    Poziom 15  
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod


    Tu masz literówkę, w deklaracji. intdeks
  • Pomocny post
    #12 12985660
    dreamy
    Poziom 12  
    _pieczas zauważ iż modyfikujesz tylko 1 element tablicy, liczenie za każdym razem sumy z całej tablicy nie jest potrzebne.

    Pseudokod:
    Kod: Text
    Zaloguj się, aby zobaczyć kod


    Przy czym suma musi być zmienną statyczną i dobrze gdyby to nie był float (patrz post GrzegorzKostka).

    Jeżeli potrzebujesz jeszcze szybszego kodu a nie zależy ci na pamięci, możesz zrezygnować z przechowywania wyników pomiarów na rzecz ich potęg, dzięki czemu nie będziesz musiał wyliczać "previous * previous;"
  • #13 12987168
    _pieczas
    Poziom 12  
    dreamy napisał:
    _pieczas zauważ iż modyfikujesz tylko 1 element tablicy, liczenie za każdym razem sumy z całej tablicy nie jest potrzebne.

    Pseudokod:
    Kod: Text
    Zaloguj się, aby zobaczyć kod


    Przy czym suma musi być zmienną statyczną i dobrze gdyby to nie był float (patrz post GrzegorzKostka).

    Jeżeli potrzebujesz jeszcze szybszego kodu a nie zależy ci na pamięci, możesz zrezygnować z przechowywania wyników pomiarów na rzecz ich potęg, dzięki czemu nie będziesz musiał wyliczać "previous * previous;"


    Ta podpowiedź pozwoliła mi skrócić czas obliczeń do tego stopnia, że wg symulacji procesor wyrobi się w czasie poniżej 0,5ms. Zasadniczo minimum już jest spełnione, ale skoro można wyciągnąć więcej to spróbuję. Dziękuję bardzo za tą podpowiedź.


    co do tego:
    tmf napisał:
    Podnosisz do kwadratu każdy element tablicy - zakładając, że masz w niej 13-bitowe wartości, to do kwadratu potrzebują one do zapisu 26 bitów, czyli więcej niż 16. A teraz dlaczego dla tablicy z elementami 16-bitowymi to nie działa - mnożenie uint16_t razy uint16_t daje uwaga uint16_t. Widzisz więc gdzie jest błąd. Gdyby kompilator wiedział, że ma zrobić mnożenie 32-bitowe to wynik byłby poprawny. A skąd ma wiedzieć? Ano trzeba mu powiedzieć, np. poprzez rzutowanie jednego z argumentów na uint32_t przed mnożeniem.
    Kolejna sprawa - jeśli suma przestanie być typu float to dodawanie 32-elementów tablicy pewnie przyśpieszy wielokrotnie.



    Owszem podnoszę do kwadratu każdy element ale nie zapisuję go do tablicy tylko z niej pobieram. Zapisuję to do sumy. kwadraty liczb 13 bitowych mają 26 bitów, a jest ich 20 czyli mniej niż 2^5, co powinno dac poniżej 31 bitów. Teoretycznie powinno to zmieścić się do sumy 32 bitowej.
    Rozumiem więc, że aby można było zapisać to do stałoprzecinkowej sumy powinienem to zapisać w ten sposób:

    Kod: C / C++
    Zaloguj się, aby zobaczyć kod


    dobrze myślę?
  • #14 12987322
    dreamy
    Poziom 12  
    Chyba tak, ale trochę to pokręciłeś.
    (2^13)^2 = 2^(13*2) = 2^26 czyli musi się zmieścić do 2^26.
    2^26 * 32 próbek / 2^32 = 2^26 * 2^5 / 2^32 = 2^(26+5) / 2^32 = 2^31 / 2^32 = 2^(-1) = 0.5 lub 50% pojemności uint32_t przy 32 próbkach.
    -> matma

    btw. masz błąd:
    Kod: C / C++
    Zaloguj się, aby zobaczyć kod
  • #15 12988982
    _pieczas
    Poziom 12  
    Tak masz rację, moje przeoczenie, to działałoby gdybym zwiększał licznik na końcu. Chociaż w aktualnej chwili udało mi się z waszą pomocą tak skrócić obliczenia, że mogę pozwolić sobie na tablice o pojemności 256 elementów i licznik typu uint8 automatycznie się przepełnia.


    Nie wiem jednak czy dobrze rozumiem o co chodzi tmf?

    tmf napisał:
    Podnosisz do kwadratu każdy element tablicy - zakładając, że masz w niej 13-bitowe wartości, to do kwadratu potrzebują one do zapisu 26 bitów, czyli więcej niż 16. A teraz dlaczego dla tablicy z elementami 16-bitowymi to nie działa - mnożenie uint16_t razy uint16_t daje uwaga uint16_t. Widzisz więc gdzie jest błąd. Gdyby kompilator wiedział, że ma zrobić mnożenie 32-bitowe to wynik byłby poprawny. A skąd ma wiedzieć? Ano trzeba mu powiedzieć, np. poprzez rzutowanie jednego z argumentów na uint32_t przed mnożeniem.
    Kolejna sprawa - jeśli suma przestanie być typu float to dodawanie 32-elementów tablicy pewnie przyśpieszy wielokrotnie.


    mam tablice uint16 tab[256] z elementami 16 bitowymi, które de facto mają wartości po 13 bitów maksymalnie.
    obieram sobie sumę, która w tej chwili będzie miała typ uint64, gdyż wymusza to liczba próbek.
    Problematyczne nie jest mnożenie/podnoszenie do kwadratu, lecz to, że do tablicy uint16 nie chcą się zapisać elementy 13 bitowe. Chociaż może chcą a błąd wynika z potęgowania, a ja źle myślę.
    Ja to widzę tak, że w tablicy są elementy 13 bitowe, a nawet niech sobie mają 16 bitów to do sumy zapisane będzie: 16 bitów do kwadratu czyli 32 bity i to razy 256 bo tyle teraz mam elementów czyli 2^32 * 2^8 = 2^40. suma ma 64 bity więc jest z zapasem.
    Irytuje mnie jednak to że tablica gdy ma typ uint16 - bo właśnie 13 bitowe liczby do niej zapisuę, nie działa poprawnie. Zaś gdy ma typ uint32 - wszsytko liczy się tak jak powinno.
  • Pomocny post
    #16 12989051
    tmf
    VIP Zasłużony dla elektroda
    Problematyczne nie jest zapisywanie do tablicy intów wartości 13-bitowych, tylko to, że w wyniku mnożenia tych wartości otrzymujesz wyniki 16-bitowy, a nie co najmniej 26 bitowy i tenże 16-bitowy wyniki sumujesz. W efekcie dostajesz śmieci. I nie, rzutowanie:
    suma+= (uint32_t) tab[indeks]*tab[indeks];
    nie załatwia sprawy, bo 16-bitowy wynik mnożenia konwertujesz na 32 bity, co kompilator i tak robi automatycznie, lecz od tej konwersji bitów w wyniku nie przybywa... Żeby to działało trzeba zamienić mnożenie 16-bitowe na 32-bitowe, czyli jeden z argumentów musi być 32-bitowy lub rzutowany na 32-bitowy.
  • Pomocny post
    #17 12989058
    BlueDraco
    Specjalista - Mikrokontrolery
    Już kilka razy pisano Ci powyżej, że problem leży w tym, że wynik mnożenia dwóch liczb 16-bitowych na AVR ma 16 bitów, i że wystarczy napisać:

    suma+= (uint32_t) tab[indeks]*tab[indeks];

    żeby iloczyn miał 32 bity, to po pierwsze.

    Po drugie - algorytm, który przyjąłeś, jest zabójczy dla 8-bitowego AVR.

    Co chwila zmieniasz założenia, a kompletnego kodu nie pokazałeś ani razu. naprawdę trudno Ci w tej sytuacji pomóc.

    Zauważ natomiast, że nie miałbyś 3/4 tych problemów, gdybyś użył małego Cortexa za 3 złote - ma większą pamięć RAM i kilkanaście razy szybciej od AVR dodaje liczby 32-bitowe oraz klkaset razy razy szybciej je mnoży.
  • Pomocny post
    #18 12989122
    grko
    Poziom 33  
    Cytat:

    Problematyczne nie jest zapisywanie do tablicy intów wartości 13-bitowych, tylko to, że w wyniku mnożenia tych wartości otrzymujesz wyniki 16-bitowy, a nie co najmniej 26 bitowy i tenże 16-bitowy wyniki sumujesz. W efekcie dostajesz śmieci. I nie, rzutowanie:
    suma+= (uint32_t) tab[indeks]*tab[indeks];
    nie załatwia sprawy, bo 16-bitowy wynik mnożenia konwertujesz na 32 bity, co kompilator i tak robi automatycznie, lecz od tej konwersji bitów w wyniku nie przybywa... Żeby to działało trzeba zamienić mnożenie 16-bitowe na 32-bitowe, czyli jeden z argumentów musi być 32-bitowy lub rzutowany na 32-bitowy.


    Ja uważam że:
    suma+= (uint32_t) tab[indeks]*tab[indeks];

    jednak załatwia sprawe.
  • #19 12989148
    _pieczas
    Poziom 12  
    Jak na razie algorytm się wyrabia w założonym czasie o ile symulacja mówi prawdę. Fakt trochę się naciąłem z tym wyborem sprzętu. Cortexa czy innego stm32 albo dsp niestety nie znam i właśnie dlatego wybór padł na atmege. Kod pokazałem praktycznie cały bo na tym w sumie polega program.
    Serdecznie dziękuję wszytkim za pomoc!
  • #20 12989224
    tmf
    VIP Zasłużony dla elektroda
    BlueDraco napisał:
    J
    Zauważ natomiast, że nie miałbyś 3/4 tych problemów, gdybyś użył małego Cortexa za 3 złote - ma większą pamięć RAM i kilkanaście razy szybciej od AVR dodaje liczby 32-bitowe oraz klkaset razy razy szybciej je mnoży.


    Myślę, że wyciągasz błędne wnioski - problemem nie jest wolny procesor, lecz zły algorytm obliczania wyniku. Bez poprawy algorytmu zmiana procesora na troszkę szybszy tylko na jakiś czas będzie maskować problem zamiast go rozwiązywać.
    BTW, Cortex M0 co najwyżej kilka razy szybciej dodaje liczby i co najwyżej kilkanaście razy szybciej je mnoży. Swoją drogą, ponieważ mnożenie floatów to de facto dodawanie wykładników, operacja ta wcale nie musi być wolna.
  • #21 12989418
    BlueDraco
    Specjalista - Mikrokontrolery
    Operacje 32-bitowe muszą być na 8-bitowym AVR kilkadziesiąt razy wolniejsze niż na 32-bitowym Cortex. Cortexy mają ponadto szybką sprzętową mnożarkę.

    Oczywiście najpierw wypadałoby "wyprostować" algorytm, ale obawiam się, że to nie wystarczy.

    Mnożenie float zabije AVR. To sporo więcej, niż dodawanie wykładników. Konkretnie - to rozbicie liczby na kawałki, uzupelnienie mantys, mnożenie 24x24 bity, dodawanie wykładników i normalizacja polegająca na przesuwaniu liczby 24-bitowej plus obsługa przypadków szczególnych. 32-bitowy Cortex bez FPU zrobi prawdopodobnie kilkaset razy szybciej od AVR.
  • #22 12989502
    tmf
    VIP Zasłużony dla elektroda
    AVR też ma sprzętową mnożarkę, co prawda 8x8 bitów, z 16-bitowym wynikiem, ale w efekcie różnice nie będą tak duże jak piszesz.
    Niemniej nie o te różnice chodzi, tylko właśnie o optymalizację algorytmu. Proste zmiany jakie zaproponowano spowodowały pewnie kilkudziesięciokrotne przyśpieszenie obliczeń, czyli różnicę większą niż wynikająca z przejścia z 8- na 32-bitowy procesor. A parę elementów jeszcze można poprawić...
  • #23 12992922
    _pieczas
    Poziom 12  
    To co z waszą pomocą spłodziłem działa świetnie na napięciu stałym. Wyniki są praktycznie bezbłędne i bardzo stabilne. Jednakże na AC jest beznadziejnie. Wyniki są totalnie losowe. Wnioskuję, że próbkowanie jest nierównomierne i stąd te problemy. Ustawiłem OCR na 2 przy preskalerze 1024 daje 2604 Hz. Przy częstotliwości sieciowej da to 52 próbki na sekunde. tablica ma 256 próbek więc mam pełne 5 okresów bez 4 próbek w tablicy. Wg symulacji w avr studio 4 algorytm powinien wyrobić się w założonym czasie, jednakże najwyraźniej tak nie jest.

    Zamieszczam mój kod:

    Kod: C / C++
    Zaloguj się, aby zobaczyć kod


    Czy waszym okiem można jeszcze jakoś to usprawnić?
    Wyżej zostało wspomniane, że lepiej byłoby użyć cortexa, lecz jak na razie pojęcia o tym sprzęcie nie mam. Obiektywnie patrząc to wiele musiałbym nadrobić aby odpalić na nim taki oto kod i zorganizować komunikacje spi?
  • #24 12993060
    tmf
    VIP Zasłużony dla elektroda
    Jeśli na symulacji procesor się wyrabia to w rzeczywistości też musi - liczba taktów w symulacji dokłądnie odpowiada rzeczywistej. Niepotrzebnie tracisz kilkanaści etaktów na transfery SPI - wykorzystaj tryb 2X, dzięki temu zegar SPI będzie miał 8 MHz, a nie 4 tak jak masz teraz. Poza tym jeśli w tablicy będziesz trzymał kwadraty, to odpadnie ci jedno mnożenie w każdej funkcji. Ja bym się przyjrzał zbieraniu próbek - jesteś pewien, że poprawnie komunikujesz się z ADC? Co to za układ? On zawsze na wyjściu ma gotowe próbki, czy nie trzeba czasem czekać na jego gotowość? BTW, jeśli ISR zdefiniujesz z atrybutem flatten, to nie będzie tracił czasu na wywołania funkcji - zostaną one osadzone w handlerze ISR.
    BTW, jeśli jedynym powodem stosowania float jest sqrt, to można to też zamienić na działania na liczbach całkowitych.
  • #25 12993138
    _pieczas
    Poziom 12  
    SPI nie puszczę przy preskalerze X2 bo atmega32 ma jedynie X4. Przetwornik to MC3302. Wg diagramu 6-4 w jego nocie katalogowej transmisja powinna trawac 24 takty, co przy preskalerze X4 dal spi daje 69 cykli. To praktycznie nic w porównaniu z resztą. Będę próbował zastosować twoje wskazówki. Szczerze mówiąc korci mnie ten cortex. Niby algorytm prosty i może dałoby się to przerzucić w miare bezboleśnie, aczkolwiek nie wiem nawet jaki procesor wziąć do ręki i jak zabrać się za jego podłączenie.
  • #26 12993412
    BlueDraco
    Specjalista - Mikrokontrolery
    Na początek np. STM32F030 i płytka DISCOVERY do zabaw, programowania i debugowania.
  • #27 12993873
    tmf
    VIP Zasłużony dla elektroda
    _pieczas napisał:
    SPI nie puszczę przy preskalerze X2 bo atmega32 ma jedynie X4. Przetwornik to MC3302. Wg diagramu 6-4 w jego nocie katalogowej transmisja powinna trawac 24 takty, co przy preskalerze X4 dal spi daje 69 cykli. To praktycznie nic w porównaniu z resztą.

    Dlaczego twierdzisz, że max to X/4? Dla SPI w trybie master max to X/2, przejrzyj dokładniej notę. Druga sprawa - cykle związane z wysyłką po SPI nie muszą być tracone tak jak to robisz teraz - wystarczy przepleść wysyłanie z wykonywaniem innych instrukcji, procesor może robić obie rzeczy równolegle.


    _pieczas napisał:
    Będę próbował zastosować twoje wskazówki. Szczerze mówiąc korci mnie ten cortex. Niby algorytm prosty i może dałoby się to przerzucić w miare bezboleśnie, aczkolwiek nie wiem nawet jaki procesor wziąć do ręki i jak zabrać się za jego podłączenie.


    Nie wiem czy masz poprawnie skonfigurowany przetwornik - używasz trybu różnicowego? Jeśli tak to musisz zadbać o odpowiednią propagację bitu znaku. Bo na razie traktujesz liczbę jako unsigned. Być może tu leży problem.
    Zmiana procesora i środowiska w tym przypadku to najgorszy pomysł jaki można wymyśleć. Jeśli już musiałbym zmieniać procesor (a nie musisz) to na twoim miejscu wybrałbym XMEGA - nie dlatego, że jest w jakiś sposób lepszy niż proponowany ARM, lecz dlatego, że to ten sam AVR, a więc to samo środowisko i przesiadka jest po prostu szybsza. Do tego jest 2-razy szybszy i ma 12-bitowy ADC to zapewne jest dla ciebie wystarczające bo jakoś super precyzyjnych obliczeń nie robisz.
REKLAMA