Matrisberäkningar med för STM32?

PIC, AVR, Arduino, Raspberry Pi, Basic Stamp, PLC mm.
Shimonu
Inlägg: 325
Blev medlem: 21 oktober 2015, 22:44:33

Re: Matrisberäkningar med för STM32?

Inlägg av Shimonu »

mankan skrev:
Al_Bundy skrev:Fast 2D matriserna fungerar inte riktigt som du har tänkt det. 2D matriserna är raka som en 1D array. Så två for-loopar behövs.

Men jag ska göra ett försök!

Edit:

Kod: Markera allt

matrix* cut(matrix* a, int start_n, int stop_n, int start_m, int stop_m) {

	int n = a->row;
	float* data = a->data;

	// Create the output
	matrix* out = initMatrix(stop_n - start_n + 1, stop_m - start_m + 1);
	float* ptr = out->data;

	for (int i = start_n; i < stop_n + 1; i++) {
		memcpy(ptr++, data + i*n + start_m, sizeof(stop_m+1));
	}

	return out;
}
Funkar verkligen det där? Du skriver ju över dig själv flera gånger om eftersom du bara flyttar ptr 1 steg per varv. sizeof(stop_m+1) ser också skumt ut, borde vara antal floats*sizeof(float).
När man gör aritmetik på en pekare så kommer den stega i samma storleksordning som typen som pekaren pekar på. så ptr++ stegar inte 1 byte utan 1 float. Håller med om att sizeof ser konstig ut. stop_m + 1 kommer resultera i en int och då kommer sizeof(stop_m + 1) alltid bli storleken av int. Jag tror inte det är tanken.
bearing
Inlägg: 11675
Blev medlem: 2 mars 2006, 01:01:45
Ort: Ängelholm

Re: Matrisberäkningar med för STM32?

Inlägg av bearing »

Al_Bundy skrev:Japp. Det fungerar.

Testa vet jag :)
Testat:

Kod: Markera allt

Create matrix
  1.000000 76.000000 86.000000  1.000000  5.000000
  1.000000  5.000000 -6.000000  0.000000  3.000000
 -5.000000  7.000000  3.000000 87.000000  3.000000
 -8.000000  3.000000  1.000000  4.000000 -1.000000
  7.000000  9.000000  1.000000 28.000000  4.000000

Cut a matrix
  1.000000  1.000000 -5.000000
  0.000000  0.000000  0.000000
  0.000000  0.000000  0.000000
Inte riktigt som tänkt va? =)
Men helt som förväntat enligt koden.

Här är en fix:

Kod: Markera allt

matrix* cut(matrix* a, int start_n, int stop_n, int start_m, int stop_m) {

	int in_columns = a->column;
	float* data = a->data + start_n * in_columns + start_m;

	// Create the output
	matrix* out = initMatrix(stop_n - start_n + 1, stop_m - start_m + 1);
	float* ptr = out->data;
	int out_columns = out->column;

	// Instead of having two for loops, we just copy the whole row at once.
	for (int i = start_n; i < stop_n + 1; i++) {
		memcpy(ptr, data, sizeof(float) * out_columns);
		ptr += out_columns;
		data += in_columns;
	}

	return out;
}
Användarvisningsbild
Al_Bundy
Inlägg: 2889
Blev medlem: 11 september 2012, 23:59:50
Ort: The U.S - Chicago
Kontakt:

Re: Matrisberäkningar med för STM32?

Inlägg av Al_Bundy »

Tackar! Jag ska testa denna kod när jag kommer hem :)

Tror ni att det är bra om jag anpassar koden efter ANSI C, dvs C89?
Användarvisningsbild
mankan
EF Sponsor
Inlägg: 934
Blev medlem: 18 juli 2015, 11:23:22
Ort: Linköping

Re: Matrisberäkningar med för STM32?

Inlägg av mankan »

Jag tycker man lugnt kan kräva C99 åtminstone.
Användarvisningsbild
Al_Bundy
Inlägg: 2889
Blev medlem: 11 september 2012, 23:59:50
Ort: The U.S - Chicago
Kontakt:

Re: Matrisberäkningar med för STM32?

Inlägg av Al_Bundy »

Men brukar inte många företag köra med C89, bara för att dem har alltid gjort det?
Shimonu
Inlägg: 325
Blev medlem: 21 oktober 2015, 22:44:33

Re: Matrisberäkningar med för STM32?

Inlägg av Shimonu »

På förra jobbet körde vi MISRA C eller en egen anpassnign av den iaf.
Mr Andersson
Inlägg: 1409
Blev medlem: 29 januari 2011, 21:06:30
Ort: Lapplandet

Re: Matrisberäkningar med för STM32?

Inlägg av Mr Andersson »

Al_Bundy skrev:Har jag sagt det eller ?
Nej, men jag trodde du skulle förstå piken att det uppfattas som ganska arrogant att förvänta sig att någon annan ska göra jobbet just efter att jag förklarat exakt vad du bör göra och gett ett exempel på hur det ser ut.
Det handlar bokstavligt talat om några få sekunder att skriva 'valgrind filnamn'.

Men men, vi glömmer det. En viktigare sak är regressionstester. Som bearing visat hade du missat ett algoritmfel. Det är lätt hänt så jag gnäller inte över det utan tänkte ge ett tips istället. Använd automatiska tester istället för visuell verifiering via printf.
Du kan t.ex. skapa en matrix_equal-funktion och kontrollera alla resultat mot förifylld data. Då ser du direkt om en ändring påverkar resultatet negativt.
Ex

Kod: Markera allt

matrix* svd_result = create(known_data, m, n);
matrix* svd_test = create(start_data, m, n);
// kör algoritmer
// ...
if(!matrix_equal(svd_test, svd_result))
  printf("svd test failed\n");
else
  printf("svd test passed\n");
Användarvisningsbild
Al_Bundy
Inlägg: 2889
Blev medlem: 11 september 2012, 23:59:50
Ort: The U.S - Chicago
Kontakt:

Re: Matrisberäkningar med för STM32?

Inlägg av Al_Bundy »

Nu har jag testat med Valgrid och hittat ett minnesfel i triu.c filen. Lägg till detta i filen och då får ni inga minnesläckage när ni analyserar med Valgrind.

Kod: Markera allt

matrix* triu(matrix* a, int shift){

	// Get info about matrix a
	int n = a->row;
	int m = a->column;
	float* ptr_a = a->data;

	matrix* out = initMatrix(n, m);
	float* ptr_out = out->data;

	// Create a triangular matrix
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			// Do the "jump"
			if(j == 0){
				j = i + shift; // When we are at column 0 again, jump then n rows + shift at the right
			}
			// Write
			if(j != m)
				*((ptr_out + i*n) + j) = *((ptr_a + i*n) + j);
		}
	}

	return out;
}
Jag lägger upp min valgrind-testade kod. Jag är nu nöjd med biblioteket och kommer nu börja använda denna inom inbyggda system. Jag tror inte jag ska optimera något mera. Hellre att jag får sätta mig i rekursiv linjär algebra istället för att göra beräkningar, istället för att optimera C-koden. Risken att om jag optimerar så kan koden bli allt for otydlig. :)
Du har inte behörighet att öppna de filer som bifogats till detta inlägg.
Användarvisningsbild
mankan
EF Sponsor
Inlägg: 934
Blev medlem: 18 juli 2015, 11:23:22
Ort: Linköping

Re: Matrisberäkningar med för STM32?

Inlägg av mankan »

Har inte kollat senaste versionen men jag stämmer in i vad Mr Andersson säger (och jag också) om regressionstester.
Då man med ökad säkerhet labba, optimera och bygga ut samtidigt som man vet att man inte har haft sönder något annat.

Sedan tror jag inte optimerandet är slut här. Nu kommer du antagligen flytta över och köra på STM32 och skulle jag tippa på att du kommer slås av att initMatrix kommer kosta märkbar tid då desktopsystem har mycket mer optimerade malloc än inbäddade system. Men som en klok man sa: "premature optimization is the root of all evil", mao lös det då.
Användarvisningsbild
Al_Bundy
Inlägg: 2889
Blev medlem: 11 september 2012, 23:59:50
Ort: The U.S - Chicago
Kontakt:

Re: Matrisberäkningar med för STM32?

Inlägg av Al_Bundy »

Vid början av tråden så var det inte alls några problem med matrisberäkningar för en uC då uC:n har sina miljoner frekvens som den kör med. Nu verkar det som att uC inte är så bra trots allt?

Jag skulle nog tro att om jag vill optimera mera så måste jag troligtvis byta algoritmer totalt. SVD löses med QR-faktorisering. Dessa är två tunga metoder. Lösa ekvationer löses med LU-faktorisering, också en tung metod. Addition, multiplikation och subtraktion är också tunga metoder.

Övriga filer är mest bara ett "hello world".

Jag tror att istället för optimera, så får man helt enkelt använda andra algoritmer, vilket jag inte vet vad man kan använda. Nu är det så att SVD är ju den tyngsta beräkningen av dem alla. Men som tur så ska jag endast göra rekursiv linjär algebra, så SVD sker bara en gång.

Här kan ni läsa hur man tillämpar rekursiv SVD.
https://pdfs.semanticscholar.org/1944/a ... 48a039.pdf

Om jag bara skulle kunna göra flera operationer samtidigt, t.ex. multiplicera kolumn med rad. Detta skulle vara perfekt, istället för ett värde i taget.
Senast redigerad av Al_Bundy 25 januari 2019, 13:14:17, redigerad totalt 1 gång.
Användarvisningsbild
AndLi
Inlägg: 18254
Blev medlem: 11 februari 2004, 18:17:59
Ort: Knivsta
Kontakt:

Re: Matrisberäkningar med för STM32?

Inlägg av AndLi »

Du måste skilja på potatis och kameler, eller malloc och matriser.
Det är väl ingen som påstått att malloc var en bra ide på en uC?
Shimonu
Inlägg: 325
Blev medlem: 21 oktober 2015, 22:44:33

Re: Matrisberäkningar med för STM32?

Inlägg av Shimonu »

Det är väl ingen som sagt att det inte kommer funka på µC?
Användarvisningsbild
Al_Bundy
Inlägg: 2889
Blev medlem: 11 september 2012, 23:59:50
Ort: The U.S - Chicago
Kontakt:

Re: Matrisberäkningar med för STM32?

Inlägg av Al_Bundy »

Jag har inte hört kritik från det, förutom här på forumet. Orsaken varför jag har använt mig av malloc har med att 2D matriserna måste ligga i minnet. Dessutom ska dem vara dynamiska.
Shimonu
Inlägg: 325
Blev medlem: 21 oktober 2015, 22:44:33

Re: Matrisberäkningar med för STM32?

Inlägg av Shimonu »

Varför måste det vara dynamiskt?

Vettigast för inbyggda system är att allokera minne baserat på ett väl gissat maxantal matriser.

Du måste ställa upp krav på ditt system först där du bestämmer hur mycket minne som kommer behövas bl a. Sen kan man göra förenklad minneshanterat. Säg att du vill kunna ha 100 matriser och de ska som störst vara 36x36. Då allokerar du minne för det, sen även om du bara ska initera en 15x15 så gör du det i minnet för en 36x36. Sen kanske man får ha lite marginal med kanske 110 matriser om det är så man temporärt behöver några matriser eller vad det nu kan vara.
Såhär görs det oftast med kritiska inbyggda system.
Användarvisningsbild
Al_Bundy
Inlägg: 2889
Blev medlem: 11 september 2012, 23:59:50
Ort: The U.S - Chicago
Kontakt:

Re: Matrisberäkningar med för STM32?

Inlägg av Al_Bundy »

> Varför måste det vara dynamiskt?
För att matriser är dynamiska.

> Vettigast för inbyggda system är att allokera minne baserat på ett väl gissat maxantal matriser.
Men då tappar biblioteket sin MATLAB-struktur.

> Du måste ställa upp krav på ditt system först där du bestämmer hur mycket minne som kommer behövas bl a. Sen kan man göra förenklad minneshanterat. Säg att du vill kunna ha 100 matriser och de ska som störst vara 36x36. Då allokerar du minne för det, sen även om du bara ska initera en 15x15 så gör du det i minnet för en 36x36. Sen kanske man får ha lite marginal med kanske 110 matriser om det är så man temporärt behöver några matriser eller vad det nu kan vara.
Såhär görs det oftast med kritiska inbyggda system.

Kan du svära på att malloc är segt i alla uC? Eller tror du våra vetenskaps-C-forskare har kommit på ett bättre sätt som kan allokera minne på extremt snabbt sätt?
Skriv svar