Avr c, skrócenie obliczeń do minimum

[qwee]

Jedna z funkcji mojego programu ma taki kod:

uintt16_t pomiar(void)
{

static uint32_t tab[128];
static uint8_t intdeks;
float rms;
uint8_t b,c;

PORTB &=~(1<<PB0);
wyslij_spi(0b00011001);
b=wyslij_spi(x00);
c=wyslij_spi(0x00);
PORTB |= (1<<PB0);

b=0b&00011111
       //uint64_t; suma=0;
float suma =0
tab[indeks] = 256*b+c;
indeks++; 
if (indeks ==127) indeks=0;

for(int i=0 ; i <128 ; i++)		
{
	suma += (tab[i] *tab[i]);

{

rms = sqrt(suma/128);
return (rms);

}

Ta funkcja jednak musi wykonywać się bardzo szybko a wcale tak nie jest. Symulując program zauważyłem, że pętla for wykonuje się bardzo długo. Mnożenie liczb 13 bitowych zajmuje atmedze32 zbyt wiele czasu, lecz to akurat rozumiem. Jednak chciałbym zwrócić uwagę, na to, ze argumenty tablicy tab[128] mają maksymalnie po 16 bitów, a konkretnie dokładnie 13. 256*b+c jest liczbą 13 bitową, gdyż kasuje pierwsze 3 bity liczby b, więc pozostaje 5 bitów + 8 bitów liczby c co daje okrągłe 13. w pętli for sumuję kwadraty tych liczb. Kwadrat liczby 13 bitowej ma 28 bitów, mnożąc to razy 128 (2^7) ( zakładając, że 256*b+a będzie liczbą maksymalną = 13 jedynek.) suma powinna mieć 35 bitów.

Z tego wynika, że każda próbka mając max 16 bitów z czego 13 jest znaczących powinna zmieścić się do tablicy uint16. Jednak zmieniając typ tablicy program się wysypuję. Dlaczego?

Chcąc wyeliminować liczbę zmiennoprzecinkową chciałem zmienić float suma na uint_64 lub nawet uint_32 gdyż jestem pewien, że wartość nie zostanie przekroczona. Jednak gdy wysyłam wynik funkcji do konsoli to dostaje zmienne nieprzewidywalne wyniki.

Zasadniczo mógłbym również operować na wyniku w postaci samej sumy, bez dzielenia przez 128 i wyciąganiu pierwiastka w celu skrócenia obliczeń, lecz zmiana typu funkcji na uint_64 czy 32 a nawet na taki sam typ jaki ma suma czyli float również daje nieokreślone efekty.

Ma ktoś pomysł jak skrócić czas obliczeń?

Szyczytem oczekiwań byłoby wykonanie takiego pomiaru na 2 kanałach w ciągu 1ms, przy taktowaniu 16 mhz. Czyli około 16 tys cykli na cała akcję.

[MirekCz]

1. tab jako uint16, suma jako uint32

2. suma += ((uint32)(tab) * ((uint32)(tab)

3. rms = sqrt ( ((float)suma)/128.0f)

Powinno pomóc.

[marek1707]

A teraz wyobraź sobie, że nawet najbardziej badziewny procesor sygnałowy wykonuje operację mnożenia 16x16 ze znakiem (wynik 32 bitowy) i akumulację tej sumy w akumulatorze np. 40 bitowym (czyli możesz zrobić do 128 takich operacji bez obawy o przepełnienie) w jednym cyklu zegara. Twoja pętla zawierałaby dokładnie jedną instrukcję, bo taki procesor ma też sprzętowe powtarzanie fragmentów kodu więc nie musisz odliczać żadnych liczników pętli i robić skoków warunkowych a do tego generator adresów potrafi jednocześnie z wykonywaniem MACa (Multiply-ACcumulate) modyfikować adresy obu argumentów pobieranych z pamięci. Jeden takt na MACa oznacza, że nawet z zegarem 20MHz mógłbyś robić obliczenia RMS z częstotliwością ponad 150kHz. Tego właśnie brakuje małym kontrolerom i dlatego ich możliwości DSP są żadne. To nie jest oczywiście odpowiedź na Twoje pytanie ale jakoś tak mi przyszło do głowy, że czasem tracimy czas na rozwiązywanie problemów, które sobie sami stwarzamy.

Możesz np. ograniczyć dynamikę pomiarów do 10 bitów i stablicować wyniki podnoszenia do kwadratu. Wtedy zostanie tylko sumowanie. Może starczy FLASHa na 11 bitów? Pierwiastka rzeczywiście możesz nie liczyć a jeśli ma to być jakiś poziom alarmowy (i wynik rms nie jest jakoś dalej wykorzystywany) to może wystarczy tę drugą stronę przed porównaniem podnieść do kwadratu?

Jeśli boisz się o nadmiar 32-bitowy to spróbuj dodawać w dwóch pętlach do dwóch sum po 64 składniki a potem każą z nich przesunąć w prawo o 1 bit i zsumować, albo.. dodawać nie 13 a 12 bitów.

[BlackJack]

Zauważyłem że mnożysz przez 256, czyli potęgę 2. Zamiast stosować klasyczne mnożenie, można w takim przypadku zastosować przesuwanie bitowe w prawo o 8 bitów, co da dokładnie ten sam efekt, a może się okazać szybsze od operacji mnożenia "*".

Pewnie operację przesuwania da sie zoptymalizować, bo można zrobić jej cześć już przy zapisie do Tablicy pomiarów argumentu b, zapisując w odwrotnej kolejności MSB i LSB, potem trzeba tylko LSB (to zamienione) przesunąć w lewo o 5 bitów.

Chyba niczego nie pomyliłem, jak tak to poprawcie.

Taka nietypowa operacja mnożenia, powinna być jakieś 2 do 3x szybsza od klasycznego mnożenia, dodatkowo obliczenia wykonujesz już niejako przy przesyłaniu argumentów, z źródła do celu, takie programowo zrealizowane trochę MMX 😉 Przy czym najlepiej byłoby to zrobić jako wstawkę ASM, wtedy będziesz miał optymalne wykorzystanie mocy CPU.

PS. b i c to odpowiednio MSB i LSB wyniku pomiaru czy co ? Staraj się nadawać sensowne nazwy zmiennym, bo tak to domyślanie się co one robią ?

[Polecacz 101]

Produkcja i montaż PCB - wybierz sprawdzone PCBWay!
   • Darmowe płytki dla studentów i projektów non-profit
   • Tylko 5$ za 10 prototypów PCB w 24 godziny
   • Usługa projektowania PCB na zlecenie
   • Montaż PCB od 30$ + bezpłatna dostawa i szablony
   • Darmowe narzędzie do podglądu plików Gerber
Zobacz również » Film z fabryki PCBWay

[Harnas]

Wydaje mi się że najwięcej dało by Tobie zmienienie typu zmienne suma na jakiś uint. Ja widzę kilka możliwych błędów.

1. Brak średników na końcu tych linii:

b=0b&00011111
   float suma =0 

2. Zamień

   if (indeks ==127) indeks=0; 

na

   if (indeks ==127) 
   {
        indeks=0;
   } 

3. Jakoś

tab[i] *tab[i]

kojarzy mi się z wskaźnikami. Spróbuj może takiego zapisu

(tab[i]) * (tab[i])

I spróbuj typu uint dla zmiennej suma.

[BlackJack]

A teraz wyobraź sobie, że nawet najbardziej badziewny procesor sygnałowy wykonuje operację mnożenia 16x16 ze znakiem (wynik 32 bitowy) i akumulację tej sumy w akumulatorze np. 40 bitowym (czyli możesz zrobić do 128 takich operacji bez obawy o przepełnienie) w jednym cyklu zegara. Twoja pętla zawierałaby dokładnie jedną instrukcję, bo taki procesor ma też sprzętowe powtarzanie fragmentów kodu więc nie musisz odliczać żadnych liczników pętli i robić skoków warunkowych a do tego generator adresów potrafi jednocześnie z wykonywaniem MACa (Multiply-ACcumulate) modyfikować adresy obu argumentów pobieranych z pamięci. Jeden takt na MACa oznacza, że nawet z zegarem 20MHz mógłbyś robić obliczenia RMS z częstotliwością ponad 150kHz. Tego właśnie brakuje małym kontrolerom i dlatego ich możliwości DSP są żadne. To nie jest oczywiście odpowiedź na Twoje pytanie ale jakoś tak mi przyszło do głowy, że czasem tracimy czas na rozwiązywanie problemów, które sobie sami stwarzamy.

Ale ile można się po drodze nauczyć próbując zrobić obliczenia DSP czy 3D na takim AVRku, Nie mówiąc już o tej frajdzie jak się uda 🙂.

[marek1707]

Zauważyłem że mnożysz przez 256, czyli potęgę 2. Zamiast stosować klasyczne mnożenie, można w takim przypadku zastosować przesuwanie bitowe w prawo o 8 bitów, co da dokładnie ten sam efekt, a może się okazać szybsze od operacji mnożenia "*".

Optymalizator kompilatora AVR-GCC zjada takie rzeczy na śniadanie. Co więcej, potrafi też np. mnożenie x*10 zamienić na (x<<1)+(x<<3). Tutaj nic nie ugrasz.

Niech autor przedstawi rozwinięcie asemblerowe tej pętli z pełnego listingu - wtedy można podpatrzeć co by tu jeszcze zmienić. Gdybanie nie ma sensu - trzeba mówić o konkretach. I tak z pewnością suma - jeżeli jest typu int, dostaje atrybut register, wskaźniki do tablicy obliczane są tylko raz a potem inkrementowane itd.

Można uniknąć odliczania licznika pętli - jeżeli to jeszcze zostało w kodzie i rozwinąć pętlę w 128 operacji. Tak brzydkie, fe i w ogóle ale to jeden z typowych zabiegów przyśpieszających.

[MirekCz]

Marek, on operuje na float i ma sqrt a kombinujesz z rozwinięciem pętli? Zyskasz 0,01%. Szkoda sobie zawracać głowę o ile nie potrzeba tej resztki prędkości.

[marek1707]

Nie no, zakładam, że wszystko co w pętli bezwarunkowo jest na intach, kwadrat stablicowany, itd. Inaczej to w ogóle nie ma sensu. Ktoś tu już podrzucił taki pomysł i uznałem, że dla autora też jest to oczywiste. Dopiero końcowe obliczanie pierwiastka - jeżeli już konieczne, mogłoby być na float, choć i tu napisanie własnego, szybkozbieżnego i całkowitoliczbowego mogłoby być szybsze. Wtedy chudnięcie metodami obcinania paznokci może jeszcze przynieść jakieś efekty 🙂

W przypadku zapchania AVRa zmiennym przecinkiem robionym w pętli, szkoda czasu na jakiekolwiek optymalizacje chyba, że ilości zmarnowanego własnego czasu.

EDIT: Hm, to mój 1000 post na Forbocie. Ciekawe kiedy to zrobiłem? Może piwo dla wszystkich? 🙂

EDIT2: A może warto zauważyć, że za każdym pomiarem nie zmienia się cała tablica tab[] tylko jeden jej element? Można trzymać drugą, równoległą tablicę próbek podniesionych do kwadratu, np kwadraty[]. Wtedy po każdej nowej próbce robisz tylko jeden raz x*x i to wpisujesz do tej tablicy a potem tylko liczysz sumę.

Co więcej, przecież nie ma sensu liczyć od nowa całej sumy skoro tylko przybył i ubył jeden składnik z tablicy kwadratów, prawda? Wystarczy na początku sumę wyzerować a potem dodawać do niej nowo przybyły kwadrat i odejmować ten który usuwamy przez nadpisanie nowego. Wygląda na 128 razy szybsze 🙂 Zostaje tylko ten nieszczęsny pierwiastek, ale i w tym temacie ludzie już coś wymyślili:

http://www.azillionmonkeys.com/qed/sqroot.html

http://atoms.alife.co.uk/sqrt/SquareRoot.java

[qwee]

Spędziłem troche czasu, zaczerpnąłem troche więdzy i znacznie zmieniłem kod.

Mianowicie:

//#define F_CPU 16000000UL
#include <avr/io.h>
#include <util/delay.h>
#include <stdio.h>
#include <math.h>
#include <avr/interrupt.h>
#include "uart.h"


#define UART_BAUD_RATE 57600

#define MOSI PB5
#define SCK PB7
#define CS	 PB4

void init_spi(void);
uint8_t wyslij_spi(uint8_t bajt);
uint16_t  pomiar_u(void);
uint16_t  pomiar_i(void);
inline void pobudzenie_sygnalizacja(void);

volatile uint8_t u_pobudzenie=0;
volatile uint8_t i_pobudzenie=0;
uint16_t i_rozr = 1000;
uint16_t u_rozr = 5000;
volatile uint32_t licznik=0; 

int main(void)
{



TCCR0 |= (1<<WGM01);
TCCR0 |= (1<<CS02) | (1<<CS00);
OCR0 |=2;
TIMSK |= (1<<OCIE0);

 while (1)
 {

 }

   return 0;
}




uint16_t pomiar_u(void)
{
static uint16_t tab_u[256];
static uint8_t indeks_u;
 float rms_u;
static uint64_t suma_u;
	uint8_t b,c;
	PORTB &=~(1<<PB0);
	wyslij_spi(0b00011000);
	b=wyslij_spi(0x00);
	c=wyslij_spi(0x00);
	PORTB|=(1<<PB0);
	c=c;
	b=b&0x1F;
	indeks_u++;// if (indeks_u ==1023) indeks_u=0;
	suma_u -= (uint32_t)tab_u[indeks_u]*tab_u[indeks_u];

		tab_u[indeks_u] = (uint16_t)256*b+c;  
		suma_u += (uint32_t)tab_u[indeks_u]*tab_u[indeks_u];


		rms_u= sqrt(suma_u/256);
	return (rms_u);

}


inline void pobudzenie_sygnalizacja()
{
if(u_pobudzenie ) PORTC &=~(1<<PC0); else PORTC |= (1<<PC0);

if (i_pobudzenie ) PORTC &= ~(1<<PC1); else PORTC |= (1<<PC1);
}

ISR(TIMER0_COMP_vect)
{

uint16_t rms_u = pomiar_u();
uint16_t rms_i = pomiar_i();

if ( rms_u>= u_rozr ) u_pobudzenie = 1 ; else u_pobudzenie = 0;
if ( rms_i >= i_rozr) i_pobudzenie = 1 ; else i_pobudzenie = 0;
pobudzenie_sygnalizacja();

}

to fragment kodu. Pomiar wykonuje na dwóch kanałach "pomiar_u" i "pomiar_i". Zasadniczo wg symulacji w avr studio powinienem zmieścić się z wykonaniem tego wszystkiego w procedurze obsługi przerwania, która wywoływana jest z częstotliwością 2604Hz ( OCR = 2 , preskaler = 1024).

Na napięciu stałym działa bardzo dobrze, jednak napięcie przemienne jest przekłamane. Wyrzuca losowe wartości. Myślę, że chodzi o to, że program próbkuje nierównomiernie, chociaż pewnie się mylę. Co wy na to?

Bardzo chętnie użyłbym dsp, albo radzoni mi również numer z jakimś cortexem, ale tych sprzętów nie znam i nawet nie wiedziałbym który wziąć do ręki. Algorytm nie jest jakoś skomplikowany więc pewnie dałoby się go przenieść na inna platforme, dobrać timer, i obsłużyć spi, ale po prostu nie znam tego, a nie sądze że opanuję to w tydzień.

[MirekCz]

1. Kod, który przesłałeś, nie jest pełen i nic z niego nie wynika.

2. Jak chcesz mieć równy czas pomiędzy pomiarami to użyj do tego timera o najwyższym priorytecie i w nim czytaj wynik poprzedniego pomiaru i odpalaj nowy (pamiętaj tylko żeby w procedurze timera robić jak najmniej, bo jak zajmie za dużo czasu to blokujesz inne rzeczy np. transfer UART)

[marek1707]

No i to jest postęp 🙂 Oprócz zmiany sposobu liczenia sumy mógłbyś jeszcze - jak napisałem wczoraj - trzymać w tablicy kwadraty zamiast wartości próbek, ale może potrzebujesz ich jeszcze do czegoś.

Nie pokazałeś całego kodu, choć jak rozumiem wykomentowanie if-a zawijającego indeks modulo 1024 nie jest błędem, bo pewnie robisz to w funkcji mierzącej i_rms.

A teraz o samych wynikach. Zastanawiałeś się kiedyś co właściwie liczysz? Weź arkusz kalkulacyjny i stablicuj sobie jakąś funkcję okresową, niech będzie sinus np. do 1000 stopni co 20 stopni. W następnej kolumnie policz z tego kwadraty a potem je zsumuj. Jeśli zrobisz to dokładnie za jeden okres, możesz swoim okienkiem sumowania jeździć w każdą stronę i wynik zawsze będzie taki sam. A teraz wylicz sobie sumę za trochę więcej niż okres i przesuwaj ją po sinusie w lewo i prawo. Czy wyniki się zmieniają? No właśnie. Jeżeli nie jesteś (a nie jesteś) pewien, że liczysz dokładnie za jeden okres 20msec (i że wszystkie zakłócenia są całkowitą wielokrotnością 50Hz), musisz bazować na uśrednianiu. To z kolei zmusza do takiego dobrania okresu próbkowania, by był on wielokrotnie dłuższy niż okres przebiegu podstawowego. U Ciebie jest to, jak rozumiem, ok 0.5s. Niestety fluktuacje będą zawsze, to wynika z natury rzeczy (równanie 5):

http://www.raeng.org.uk/education/diploma/maths/pdf/exemplars_engineering/8_RMS.pdf

A teraz opisz dokładnie co znaczy wg Ciebie

"napięcie przemienne jest przekłamane. Wyrzuca losowe wartości"

bo jednak "przekłamane" to coś zupełnie innego niż "losowe".

Najprościej będzie, jak złapiesz te 1000 próbek z gniazdka 230V, zatrzymasz pomiary, wypiszesz tablicę na terminalu i policzysz sam jaki powinien być prawidłowy wynik. Tą metodą szybko znajdziesz ew. błąd pod warunkiem, że tam jest i nie jest to niezrozumienie samej idei tego pomiaru. Zacznij od analizy samych próbek i od tego, czy ADC na SPI oddaje sensowne wyniki. Potem tablica, kwadraty, sumowanie itd, wiadomo.

O ile jestem na bieżąco, Cortexy nie są DSP w żadnym wypadku i nikt, kto kiedykolwiek coś na DSP robił by ich tak nie nazwał. Są szybsze od AVR, fakt, ale nie mają właściwie żadnego z mechanizmów, który predystynował by je do tej klasy procesorów. To zwykłe, 32-bitowe ARMy wyposażone w kilka dodatkowych instrukcji SIMD - to nawet nie jest przedsionek DSP, choć zapewne producenci chcieliby inaczej. Nie mówię tu o 2-procesorowych hybrydach ARM-DSP np. Texasowych, to oczywiście jest pełnokrwisty DSP.

[qwee]

w głównej pętli jest tylko porównanie wartości obliczonych z nastawczymi i sterowanie diodami.

Wg symulacji w avr studio4 timer wyrabia się z obliczeniami. I to jest praktycznie cały kod. Używam tylko jednego timera więc to on zdaje się będzie miał najwyższy priorytet.

Otrzymuję wartości losowe z błędem około 20 %. Może nie do końca losowe bo jednak oscylują wokół wartości docelowej ale jednak to jeszcze nie jest to. Niestety nie uda mi się policzyć rms za 1000 próbek bo zwyczajnie zabraknie mi pamięci RAM.

Napięcie podaje przez transformator i dzielnik rezystancyjny, więc raczej nie powinno być specjalnych odksztauceń. Nawet jeśli one są to raczej powinny mieć charakter niezmienny i watrtość skuteczna powinna być w miare stablina.

Mam 256 próbek i wg timera 20 ms zapisuje w 52 próbkach więc tablica zawiera 5 okresów i 4 próbki na górkę. Ale czy to sprawiałoby aż taki bład?

[marek1707]

Niektóre obliczenia mogą mieć niedeterministyczne czasy wykonania, zależne od danych wejściowych. Dotyczy to np. sqrt. Jeżeli tak jest, to testy na symulatorze przeprowadzone na wybranym zestawie danych mogą być niewystarczające. Jaki masz margines/zapas czasu?

Jeżeli istnieje uzasadnione podejrzenie spóźniania się obsługi przerwań to zwiększ do testu okres timera np. dwukrotnie. Wyniki RMS nie powinny się zmienić. Zawsze możesz machać jakimś portem w obsłudze przerwania albo choćby oglądać sygnał wyboru przetwornika A/C na SPI i wyzwalać oscyloskop impulsami dłuższymi niż ileś-tam-milisekund oznaczającymi spóźnienie próbkowania z powodu przedłużonego czasu poprzednich obliczeń.

[qwee]

Z symulacji wynika, że obsługa przerwania zajmuje trochę ponad 4 tysiące cykli zaś timer odpalany jest co ponad 6 tysięcy (2*1024*3). Mam nieodparte wrażenie, że jednak jego wykonanie przeciąga się nieco. Oscyloskopu nie posiadam więc takiego manewru nie zrobię. Spróbuję walczyć jeszcze z sqrt.