Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

Cortex M0 - Dzielenie 32b liczy przez 16b oszacowanie potrzebnej ilości cykli

SeerKaza 16 Lip 2014 20:48 2214 22
  • #1 16 Lip 2014 20:48
    SeerKaza
    Poziom 20  

    Hey

    Potrzebuje wiedzieć ile cykli ( z dokładnością do 48) STM32F042 potrzebuje by podzielić stałą wartość 32b przez zmienna 16 bit (realnie 12b). Niestety muszę dzielić i nie wykonam tego przesunięciem bitowym. Potrzebuje mniej-więcej oszacować ile czasu zajmie mi ta operacja. I czy dzielić normalnie wpisując kod y = 5000000/x czy i zostawic implementacje dzielenia kompilatorowi (linaro) czy tez implementować jakiś znaleziony w internecie algorytm do dzielenia. Podpowiem że dzielenie służy do obliczania okresu z częstotliwości. I inaczej nie mam pojęcia jak to zrobić. Operacji miało być robionych kilka ale tak dobrałem górny współczynnik że wystarczy już tylko go podzielić przez zmienną.

    Dodano po 5 [minuty]:

    Oczywiście chodzi o najgorszy przypadek

    0 22
  • #2 16 Lip 2014 21:26
    BlueDraco
    Specjalista - Mikrokontrolery

    A dlaczego nie zmierzysz czasu dzielenia timerem? Kompilator używa w miarę optymalnych procedur dzielenia, więc raczej nic nie przyspieszysz pisząc własne procedury.

    0
  • #3 16 Lip 2014 21:29
    el2010tmp
    Poziom 25  

    Weź najgorszy przypadek podejrzyj ASM i policz, w DS jest stosowna tabelka ile która instrukcja zajmuje.
    Możesz też policzyć dużo_razy, zmierzyć czas timerem cykle=(czas/dużo_razy)*f_cpu.

    0
  • #4 16 Lip 2014 21:35
    Freddie Chopin
    Specjalista - Mikrokontrolery

    Możecie liczyć [;

    Code:
    000001ec <__aeabi_uidiv>:
    
     1ec:   2900         cmp   r1, #0
     1ee:   d034         beq.n   25a <.udivsi3_skip_div0_test+0x6a>

    000001f0 <.udivsi3_skip_div0_test>:
     1f0:   2301         movs   r3, #1
     1f2:   2200         movs   r2, #0
     1f4:   b410         push   {r4}
     1f6:   4288         cmp   r0, r1
     1f8:   d32c         bcc.n   254 <.udivsi3_skip_div0_test+0x64>
     1fa:   2401         movs   r4, #1
     1fc:   0724         lsls   r4, r4, #28
     1fe:   42a1         cmp   r1, r4
     200:   d204         bcs.n   20c <.udivsi3_skip_div0_test+0x1c>
     202:   4281         cmp   r1, r0
     204:   d202         bcs.n   20c <.udivsi3_skip_div0_test+0x1c>
     206:   0109         lsls   r1, r1, #4
     208:   011b         lsls   r3, r3, #4
     20a:   e7f8         b.n   1fe <.udivsi3_skip_div0_test+0xe>
     20c:   00e4         lsls   r4, r4, #3
     20e:   42a1         cmp   r1, r4
     210:   d204         bcs.n   21c <.udivsi3_skip_div0_test+0x2c>
     212:   4281         cmp   r1, r0
     214:   d202         bcs.n   21c <.udivsi3_skip_div0_test+0x2c>
     216:   0049         lsls   r1, r1, #1
     218:   005b         lsls   r3, r3, #1
     21a:   e7f8         b.n   20e <.udivsi3_skip_div0_test+0x1e>
     21c:   4288         cmp   r0, r1
     21e:   d301         bcc.n   224 <.udivsi3_skip_div0_test+0x34>
     220:   1a40         subs   r0, r0, r1




     222:   431a         orrs   r2, r3
     224:   084c         lsrs   r4, r1, #1
     226:   42a0         cmp   r0, r4
     228:   d302         bcc.n   230 <.udivsi3_skip_div0_test+0x40>
     22a:   1b00         subs   r0, r0, r4
     22c:   085c         lsrs   r4, r3, #1
     22e:   4322         orrs   r2, r4
     230:   088c         lsrs   r4, r1, #2
     232:   42a0         cmp   r0, r4
     234:   d302         bcc.n   23c <.udivsi3_skip_div0_test+0x4c>
     236:   1b00         subs   r0, r0, r4
     238:   089c         lsrs   r4, r3, #2
     23a:   4322         orrs   r2, r4
     23c:   08cc         lsrs   r4, r1, #3
     23e:   42a0         cmp   r0, r4
     240:   d302         bcc.n   248 <.udivsi3_skip_div0_test+0x58>
     242:   1b00         subs   r0, r0, r4
     244:   08dc         lsrs   r4, r3, #3
     246:   4322         orrs   r2, r4
     248:   2800         cmp   r0, #0
     24a:   d003         beq.n   254 <.udivsi3_skip_div0_test+0x64>
     24c:   091b         lsrs   r3, r3, #4
     24e:   d001         beq.n   254 <.udivsi3_skip_div0_test+0x64>
     250:   0909         lsrs   r1, r1, #4
     252:   e7e3         b.n   21c <.udivsi3_skip_div0_test+0x2c>
     254:   1c10         adds   r0, r2, #0
     256:   bc10         pop   {r4}
     258:   4770         bx   lr
     25a:   2800         cmp   r0, #0
     25c:   d001         beq.n   262 <.udivsi3_skip_div0_test+0x72>
     25e:   2000         movs   r0, #0
     260:   43c0         mvns   r0, r0
     262:   b407         push   {r0, r1, r2}
     264:   4802         ldr   r0, [pc, #8]   ; (270 <.udivsi3_skip_div0_test+0x80>)
     266:   a102         add   r1, pc, #8   ; (adr r1, 270 <.udivsi3_skip_div0_test+0x80>)
     268:   1840         adds   r0, r0, r1
     26a:   9002         str   r0, [sp, #8]
     26c:   bd03         pop   {r0, r1, pc}
     26e:   46c0         nop         ; (mov r8, r8)
     270:   00000019    .word   0x00000019

    00000274 <__aeabi_uidivmod>:
     274:   2900         cmp   r1, #0
     276:   d0f0         beq.n   25a <.udivsi3_skip_div0_test+0x6a>
     278:   b503         push   {r0, r1, lr}
     27a:   f7ff ffb9    bl   1f0 <.udivsi3_skip_div0_test>
     27e:   bc0e         pop   {r1, r2, r3}
     280:   4342         muls   r2, r0
     282:   1a89         subs   r1, r1, r2
     284:   4718         bx   r3
     286:   46c0         nop         ; (mov r8, r8)

    00000288 <__aeabi_idiv0>:
     288:   4770         bx   lr
     28a:   46c0         nop         ; (mov r8, r8)


    <;

    4\/3!!

    0
  • #5 20 Lip 2014 11:56
    nsvinc
    Poziom 35  

    Pytanie co to za CM0... Serie LPC11U2x, LPC12xx mają wbudowane procedury dzielenia; lecz nie mam pojęcia, czy jest jakaś korzyść z ich uzywania oprócz zmniejszenie wielkości kodu.
    Jeśli twoja dzielna lub dzielnik jest stała, to można pokusić się o wykorzystanie algorytmów (są w necie) które są zoptymalizowane pod tym kątem.

    0
  • #6 20 Lip 2014 12:50
    SeerKaza
    Poziom 20  

    STM32F042K6

    0
  • #7 20 Lip 2014 17:24
    nsvinc
    Poziom 35  

    No to chyba nic Cie nie uratuje ;] Zwróc jednak uwagę na to, że istnieje kilka rodzajów algorytmów dzielenia. Jedne są takie, które mają bardzo duży rozrzut ilości cykli między najlepszym a najgorszym przypadkiem.
    Inne są bardziej deterministyczne, ktore w najlepszym przypadku zuzyją znacznie więcej cykli, za to w najgorszym znacznie mniej, w porównaniu do tych pierwszych.
    Jeśli to, co dzielisz, ma losowy charakter a zależy ci na najkrótszym czasie wykonania dowolnego dzielenia, to powinienes isc w kierunku tych drugich algorytmów.

    0
  • #8 21 Lip 2014 08:42
    atom1477
    Poziom 43  

    A w czym te drugie algorytmy są lepsze, skoro też mają duży rozrzut czasów wykonania oraz ten czas wykonania może być znacznie dłuższy do tych pierwszych algorytmów?

    0
  • #9 21 Lip 2014 09:26
    BlueDraco
    Specjalista - Mikrokontrolery

    Przede wszystkim cały czas nie wiemy, co to znaczy dla Ciebie "wystarczająco szybko" albo "zbyt wolno". Uprawiamy takie gdybanie w powietrzu - "czy można jakoś zoptymalizować coś, o czym nie wiemy, czy jest wystarczająco szybkie, czy nie".

    Zmierz timerem szybkość dzieleń, a potem dopiero można będzie rozpocząć bicie piany nt. optymalizacji dzielenia.

    Jeśli wyjdzie Ci, że jest za wolno, prawdopodobnie najprostszym sposobem będzie przesiadka na CM3 albo CM4, w których mamy sprzętowe dzielenie.

    Co chwila ktoś tu rozpoczyna wątek pod hasłem "jak uzyskać 20 KiB pamięci RAM i 10 MIPS na ATmega8". Przeceiż to kompletnie nie ma sensu. Postaw założenia co do sprzętu i wydajności obliczeniowej, a potem dobieraj mikrokontroler. Jeśli w Twoim zastosowaniu krytyczna jest szybkość dzielenia, to nie używaj CM0. Proste?

    0
  • #10 21 Lip 2014 10:38
    nsvinc
    Poziom 35  

    atom1477 napisał:
    A w czym te drugie algorytmy są lepsze, skoro też mają duży rozrzut czasów wykonania oraz ten czas wykonania może być znacznie dłuższy do tych pierwszych algorytmów?

    Nie do końca o to chodzi. Przyjmijmy, algorytm A bardzo szybko podzieli 69/3, za to bardzo długo będzie dzielił 6969/333. Algorytm B, zoptymalizowany pod determinizm, będzie dłużej dzielić 69/3, ale krócej 6969/333, w porównaniu do algorytmu A. W skrócie mówiąc, algorytm B zawsze zużywa podobną ilość cykli, niezależnie od tego, jak "trudne" jest dzielenie; a algorytm A ma duży rozrzut ilości cykli między best-case a worst-case.

    BlueDraco napisał:
    Zmierz timerem szybkość dzieleń, a potem dopiero można będzie rozpocząć bicie piany nt. optymalizacji dzielenia.

    Racja, kolejny raz ktoś robi na odwrót ;] a jak wszyscy wiemy, mikrokontroler dobiera się do układu, a nie układ do mikrokontrolera.

    0
  • #11 29 Lip 2014 23:47
    BeginEnd
    Poziom 14  

    Zakładając, że posiadasz ok 9k wolnego flasha oraz chcesz efektywnie dzielić przez liczbę 12 bitową to możesz to zrobić w ok 4-6 cyklach (tak na oko) używając metody tablicowej.
    Oto pseudokod:

    Kod: c
    Zaloguj się, aby zobaczyć kod


    Wartości graniczne indeksów musisz sprawdzić, bo pisane na szybko.
    Za pomocą różnych dziwnych sztuczek pewnie dałoby się zejść do 3~4 cykli, ale to już zależy od implementacji powyższego rozwiązania i dokładnego rozeznania problemu.

    0
  • #12 30 Lip 2014 09:10
    Marek_Skalski
    Moderator Projektowanie

    Tak, tak... 4 cykle. Z instrukcją warunkową.
    A jakiej wielkości będzie tablica oferująca wynik dzielenia (const uint32_t / uint16_t)?
    Dawno nie widziałem większej bzdury.

    0
  • #13 30 Lip 2014 09:59
    atom1477
    Poziom 43  

    Marek_Skalski napisał:
    Tak, tak... 4 cykle. Z instrukcją warunkową.

    To się w 10 pewnie nie zmieści nawet.

    Marek_Skalski napisał:
    A jakiej wielkości będzie tablica oferująca wynik dzielenia (const uint32_t / uint16_t)?
    Dawno nie widziałem większej bzdury.

    Tutaj jednak możesz się zdziwić. Pamiętaj że mówimy o dzieleniu gdzie dzielna/dzielnik jest stała.
    W przypadku uint32_t / uint16_t tablica mogła by mieć "tylko" 128kB.
    Dopiero przy implementacji pełnego dzielenia uint32_t / uint16_t trzeba by kolosalnej tablicy o wymiarze minimum 8GB (8GB po optymalizacjach, bo normalnie to 524TB).

    0
  • #14 30 Lip 2014 11:12
    grko
    Poziom 33  

    Autor przeciez napisał, że chce dzielić przez liczbę 12 bitową więc pomysł z LUT nie jest taki głupi.

    0
  • #15 30 Lip 2014 12:16
    SeerKaza
    Poziom 20  

    Dokładnego czasu nie mierzyłem jednak sądząc po przebiegach jakie miałem generować procesor się "wyrabia" Całość obliczeń w których oprócz omawianego dzielenia jest jeszcze kilka mnożeń przez stale liczby z ułamkiem mieści się w mniej niż 10us czyli dzielenie jest wykonywane w mniej niż 480 cykli zegara. Cały ten temat był spowodowany tym że bałem się że samo dzielenie to będzie więcej niż 100cykli ale podejrzewam że jednak jest to mniej

    0
  • #16 30 Lip 2014 20:08
    BeginEnd
    Poziom 14  

    Marek_Skalski napisał:
    Tak, tak... 4 cykle. Z instrukcją warunkową.
    A jakiej wielkości będzie tablica oferująca wynik dzielenia (const uint32_t / uint16_t)?
    Dawno nie widziałem większej bzdury.


    Po co się bierzesz za programowanie skoro czytać po polsku ze zrozumieniem nie umiesz.
    Pisałem na szybko więc podałem oszacowanie (4~6) wynikające z DOŚWIADCZENIA. I pomyliłem się o 1~2 cykle dla kodu napisanego w 20 minut.
    Ale w przeciwieństwie do Ciebie to sprawdziłem.

    Kod: c
    Zaloguj się, aby zobaczyć kod


    Kod: asm
    Zaloguj się, aby zobaczyć kod


    Code:

    arm-none-eabi-size test_out.o
       text      data       bss       dec       hex   filename
       8532         0         0      8532      2154   test_out.o


    To ile wyszło cykli?

    Czekam na przeprosiny!

    Pozdrawiam tych którzy nie wierzyli, ale skompilowali :P

    0
  • #17 30 Lip 2014 21:48
    Marek_Skalski
    Moderator Projektowanie

    To teraz jeszcze proponuję zmierzyć ten czas w rzeczywistym układzie.

    Kod: C
    Zaloguj się, aby zobaczyć kod

    W najbardziej przyjaznych warunkach dla wspomnianego uC, 24MHz @0 wait state, goła funkcja wymaga 11/15 cykli, a to ~300% więcej niż deklarowane 4 cykle. Czekam na te sztuczki :)
    Ponadto ten uC ma tylko 32KiB Flash, z czego na wyjątkowo ograniczony algorytm dzielenia chcesz przeznaczyć ponad 8KiB. I nie rozważajmy innego uC, ponieważ to jest ten konkretny przypadek.

    0
  • #18 30 Lip 2014 22:35
    BeginEnd
    Poziom 14  

    Marek_Skalski napisał:
    W najbardziej przyjaznych warunkach dla wspomnianego uC, 24MHz @0 wait state, goła funkcja wymaga 11/15 cykli, a to ~300% więcej niż deklarowane 4 cykle. Czekam na te sztuczki :)
    Ponadto ten uC ma tylko 32KiB Flash, z czego na wyjątkowo ograniczony algorytm dzielenia chcesz przeznaczyć ponad 8KiB. I nie rozważajmy innego uC, ponieważ to jest ten konkretny przypadek.


    Po pierwsze primo - to kod kompilatora, który generuje funkcję nie mając pojęcia o reszcie kodu. Mając algorytm wpleciony w docelowy kod kompilator na 95% wygeneruje bardziej optymalny kod więc zależy to od konkretnego przypadku (tak jak napisałeś). Nie było mowy o ograniczeniach co do ilości flasha - miało być szybko więc jest. Algorytm jest szyty na miarę postawionego tematu.

    Po drugie primo-ultimo: skoki powrotu nie należą do 'algorytmu dzielenia' - zastąp funkcję makrem to zobaczysz. Nawet wg twoich wyliczeń to sam algorytm zajmuje 8~9 cykli (jestem wspaniałomyślny, nie musisz już posypywać głowy popiłem :D) - tylko nie wiem coś ty się uczepił tych 4 cykli? Jak dasz odpowiednią kasę to ci to zoptymalizuje w rzeczywistym układzie lub raczej programie, że będą te 4 cykle (serio!).

    0
  • #19 31 Lip 2014 00:01
    nsvinc
    Poziom 35  

    Symulacja z Keila LPC1114FHN33,302

    armcc, -gnu -O0, Xtal=1MHz

    Code:

        35: unsigned long compute(unsigned short x) {
        36: 
    0x00000194 4601      MOV      r1,r0
        37:         if( x < 77 )
    0x00000196 294D      CMP      r1,#0x4D
    0x00000198 DA03      BGE      0x000001A2
        38:                  return tabs.words[x];
        39:         else
        40:                return tabs.half_words[x];
    0x0000019A 0088      LSLS     r0,r1,#2
    0x0000019C 4A0D      LDR      r2,[pc,#52]  ; @0x000001D4
    0x0000019E 5810      LDR      r0,[r2,r0]
        41: }
        42: 
        43: 
        44: int main(void)
        45: {
        46: 
    0x000001A0 4770      BX       lr
        40:                return tabs.half_words[x];
        41: }
        42: 
        43: 
        44: int main(void)
        45: {
        46: 
    0x000001A2 004A      LSLS     r2,r1,#1
    0x000001A4 480C      LDR      r0,[pc,#48]  ; @0x000001D8
    0x000001A6 5A80      LDRH     r0,[r0,r2]
    0x000001A8 E7FA      B        0x000001A0
        47: while(1)


    x=10 -> 10us
    x=100 -> 13us
    x=1000 -> 13us

    ---------------------------------------------------

    armcc, -gnu -O0, Xtal=24MHz ; kod jak wyzej

    x=10 -> 0.417us
    x=100 -> 0.542us
    x=1000 -> 0.542us

    ------------------------------------------------------

    armcc, -gnu -O3 -Otime, Xtal=24MHz

    Code:

    0x00000194 4911      LDR      r1,[pc,#68]  ; @0x000001DC
        37:         if( x < 77 )
    0x00000196 284D      CMP      r0,#0x4D
        35: unsigned long compute(unsigned short x) {
        36: 
        37:         if( x < 77 )
    0x00000198 D202      BCS      0x000001A0
        38:                  return tabs.words[x];
        39:         else
        40:                return tabs.half_words[x];
    0x0000019A 0080      LSLS     r0,r0,#2
    0x0000019C 5808      LDR      r0,[r1,r0]
        41: }
        42: 
        43: 
        44: int main(void)
        45: {
        46: 
        47: while(1)
        48:         {
    0x0000019E 4770      BX       lr
        40:                return tabs.half_words[x];
        41: }
        42: 
        43: 
        44: int main(void)
        45: {
        46: 
        47: while(1)
        48:         {
    0x000001A0 0040      LSLS     r0,r0,#1
    0x000001A2 1840      ADDS     r0,r0,r1
    0x000001A4 30FF      ADDS     r0,r0,#0xFF
    0x000001A6 3001      ADDS     r0,r0,#0x01
    0x000001A8 8F00      LDRH     r0,[r0,#0x38]
    0x000001AA 4770      BX       lr
        38:                  return tabs.words[x];


    x=10 -> 0.375us
    x=100 -> 0.542us
    x=1000 -> 0.542us

    --------------------------------------------

    Dla porownania zwykłe dzielenie (divres=5000000UL/x) funkcjami standardowych bibliotek keila:

    armcc, -gnu -O3 -Otime, Xtal=24MHz

    x=10 -> 0.500us
    x=100 -> 0.500us
    x=1000 -> 0.500us

    Dodano po 7 [minuty]:

    BeginEnd napisał:
    będą te 4 cykle (serio!).

    Kicha ;]

    co mamy?
    Code:

    0x00000194 4911      LDR      r1,[pc,#68]  ; wez ptr na 'words'
    0x00000196 284D      CMP      r0,#0x4D ; porownaj arg z 77
    0x00000198 D202      BCS      0x000001A0 ; jesli wiekszy to skocz, else idz dalej
    0x0000019A 0080      LSLS     r0,r0,#2 ; r0*=4
    0x0000019C 5808      LDR      r0,[r1,r0] ; r0=[r1+r0] czyli wez wartosc z LUTa 'words'
    0x0000019E 4770      BX       lr ; wróc


    To jest best case. Jak ty to chcesz lepiej napisac?... A to juz trwa te 375ns ;]
    I to sie idealnie zgadza:
    LDR - 2 takty
    CMP - 1 takt
    BCS - 1 takt
    LSLS - 1 takt
    LDR - 2 takty
    BX - 2 takty
    =9 taktów zegara rdzenia. @24MHz takt trwa 41.6(6)ns, więc 9*41.6(6) = 375ns. Lepiej nie zrobisz.

    Dodano po 1 [godziny] 3 [minuty]:

    Dla hardcorów - funkcja w RAMie, więc może się wydajnie wykonać @48MHz. W sumie 2 razy szybciej. Jednak dostęp do LUTa i tak będzie na FLASH. Więc to będzie troche mniej niż 2 razy szybciej.
    Dla większych hardcorów - i funkcja, i LUT w RAMie. Tylko po co to wszystko? Czy SeerKaza walczy o pojedyncze takty? Jeśli chcemy dzielić za wszelką cenę w ekspresowym tempie to moze warto jednak sięgać po procki, które to dzielenie sprzętowo wspomagają...

    0
  • #20 31 Lip 2014 11:01
    BlueDraco
    Specjalista - Mikrokontrolery

    Problem jest sztuczny, bo CM3 ma dzielenie sprzętowe, a cena jest niemal taka sama, jak CM0, to po pierwsze.

    Po drugie, w miarę eleganckie rozwiązanie problemu bez sprzętowego dzielenia dla krótkiego dzielnika, to funkcja odwrotności zrobiona przez LUT lub mały LUT (przybliżenie) z jedną iteracją Newtona-Raphsona i sprzętowe mnożenie przez tak uzyskaną odwrotność. (Tak to było zrobione np. przez AMD w K6-2 w 1997 roku :).)

    0
  • #21 31 Lip 2014 12:03
    nsvinc
    Poziom 35  

    BlueDraco napisał:
    CM3 ma dzielenie sprzętowe, a cena jest niemal taka sama, jak CM0

    ...ale prądu żre znacznie więcej ;] CM0 wybiera się przecież głównie ze względu na energooszczędność, więc nie zadaję autorowi pytań typu 'czemu nie CM3' ;)

    0
  • #22 03 Sie 2014 17:23
    domelfm
    Poziom 16  

    Z tym prądem to tak i nie :)
    Zależy co masz włączone w tym procku i jakie taktowanie.

    0
  • #23 03 Sie 2014 17:59
    SeerKaza
    Poziom 20  

    CM0 musiało być z powodu widzimisie kierownika. Zadanie zrobione projekt oddany. Obliczenia są wykonywane w wymaganym czasie. Pod koniec projektu okazało się że prędkość zmian wartości sygnału ma być zmniejszona o połowę. Więc procesor przez połowę czasu pracy pracuje w trybie WFI

    0
  Szukaj w 5mln produktów