Matrisberäkningar med för STM32?

[ahlsten]

Annat att titta på om du har lust:

*Bygg ditt bibliotek ovanpå CMSIS, så kanske du kan dra nytta av dess optimeringar som eventuella SIMD-instruktioner

*Vilken optimeringsflagga används? Embedded-mål kanske innebär -Os och det kanske premierar storleken på binär över loop unrolling.

[Al_Bundy]

> Jag körde SVD parallellt via GNU Octave. Supersnabbt.

Alltså, det var *Octave* var "supersnabbt"?

> Det har inte med minneshanteringen att göra, utan for-loopar. Det var JAG som påpekade detta innan,
> att for-loopar är ej vektoriserad kod, men många här slog mig på fingrarna och sade att det spelar ingen roll.

Jag menar att du är helt ute ock cyklar. Bara för att dina C kod *ser* enklare ut så betyder
inte det att plattformen du kör på stöder vektorberäkningar. Någonstans i en lib körs fortfarande
samma loopar. Visst, den som skrev det kan ju ha varit duktigare på optimering än vad du är,
men om din algoritm som sådan är korrekt så måste ju ända samma operationer utföras.

> Så for-loopar måste optimeras på något sätt.

Ja, det finns vissa problem med att cachen kan bli ineffektiv om man läser igenom
en array i "fel ordning", så att säga. Man bör läsa/loopa så som den är lagrad i minnet.

> Jag ser också att qr.c är boven i dramat. Utan den så kommer jag ned till några hundradelar av en sekund.

Jag har inte kollat vad qr.c gör, men får du alltså fortfarande rätt resultat utan den?
Om inte får det så spelar väl körtiden utan den inte så stor roll...

Jag tror att skillnaderna du ser antingen beror på ineffektiv kod rent generellt eller att
du använder en float typ som inte är optimal på din plattform.

Okej! Två förslag från dig.

1. for-llopar som lagras i minnet? Hur då?
2. Hur menar du med att float är inte optimal för min plattform? Jag sitter ju på en vanlig Dell 64 bit med Ubuntu linux.

Kanske man ska skippa det där med floats och endast köra heltal? Fast det blir riktigt svårt då jag använder mätdata.

[Al_Bundy]

Annat att titta på om du har lust:

*Bygg ditt bibliotek ovanpå CMSIS, så kanske du kan dra nytta av dess optimeringar som eventuella SIMD-instruktioner

*Vilken optimeringsflagga används? Embedded-mål kanske innebär -Os och det kanske premierar storleken på binär över loop unrolling.

Tror du att min kod skulle gå snabbare om jag använde CMSIS? Det tror inte jag. För övrigt så saknar CMSIS väldigt mycket av matrisberäkningar. För mig är detta bibliotek typ 1+2=2.

Nu vet jag inte direkt om jag använder en speciell flagga.

[mankan]

Nu har jag kört på min gamla Linuxburk.

Kod: Markera allt

[root@zombiezoo linalg]# ./SVDtest
Total speed of SVD was 2.154426,

La på -Os till gcc:

Kod: Markera allt

[root@zombiezoo linalg]# ./SVDtest
Total speed of SVD was 1.155789,

Varningar man får med -Wall:

Kod: Markera allt

gcc -g -Wall -std=c99 -Os -c SVDtest.c -o SVDtest.o
SVDtest.c: In function ‘main’:
SVDtest.c:75:13: warning: unused variable ‘H1_half’ [-Wunused-variable]
     matrix* H1_half = cut(H1, 0, 35, 0, 35);
             ^
gcc -g -Wall -std=c99 -Os -c LinearAlgebra/repmat.c -o LinearAlgebra/repmat.o
LinearAlgebra/repmat.c: In function ‘repmat’:
LinearAlgebra/repmat.c:59:4: warning: ‘vertz’ may be used uninitialized in this function [-Wmaybe-uninitialized]
    return vertz;
    ^
LinearAlgebra/repmat.c:57:14: warning: ‘horz’ may be used uninitialized in this function [-Wmaybe-uninitialized]
    freeMatrix(horz);

Sedan bör du flytta #endif sist i declareFunctions.h om den ska ha nån nytta.

-O3 ger lite till

Kod: Markera allt

[root@zombiezoo linalg]# ./SVDtest
Total speed of SVD was 0.910201,

Och för skojs skull -O2

Kod: Markera allt

[root@zombiezoo linalg]# ./SVDtest
Total speed of SVD was 1.742821,

[Al_Bundy]

Ja du se ju. Det är ooptimerad kod.

Okej. Jag ska lägga lite mer fokus på dessa varningar. Jag vet hur man kan åtgärda dessa rätt snabbt.

Det största problemet som jag ser är själva denna kod. Här kan man göra störst nytta. QR-faktorisering är ett utmärkt verktyg när det kommer till att lösa ekvationer som är stokastiska, dvs mycket brus och mätfel.
Problemet är att jag vet inte hur jag ska optimera denna qr.c fil. Jag tycker den nog är optimerad så mycket som det går.

Kod: Markera allt

void qr(matrix* a, matrix* q, matrix* r) {

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

	// Get data
	float* ptr_q = q->data;
	float* ptr_r = r->data;

	matrix* c1;
	matrix* c2;


	for(int k = 0; k < m; k++){
		// Insert vector
		for(int j = 0; j < n; j++)
			*((ptr_q + j*n) + k) = *((ptr + j*n) + k);

		// Do the dot product
		for(int i = 0; i < k; i++){
			c1 = cut(q, 0, n, i, i);
			c2 = cut(q, 0, n, k,k);
			*((ptr_r + i*n)+k) = dot(c1, c2);
			freeMatrix(c1);
			freeMatrix(c2);

			// Insert vector again
			for(int j = 0; j < n; j++)
				*((ptr_q + j*n) + k) = *((ptr_q + j*n) + k) - *((ptr_r + i*n)+k)*(*((ptr_q + j*n) +i));

		}

		c1 = cut(q, 0, n, k, k);
		*((ptr_r+k*n)+k) = -norm(c1); // Important with negative
		freeMatrix(c1);
		// Insert vector again
		for(int j = 0; j < n; j++){
			if(*((ptr_r + k*n) + k) ==  0){
				*((ptr_r + k*n) + k) = pow(2.2204, -16); // Same as eps command in MATLAB
			}
			*((ptr_q + j*n) + k) = (*((ptr_q + j*n) + k)) / (*((ptr_r + k*n) + k));
		}

	}

}

MATLAB koden är följande

Kod: Markera allt

function [Q,R] =  mgs(X)
    % Modified Gram-Schmidt.  [Q,R] = mgs(X);
    % G. W. Stewart, "Matrix Algorithms, Volume 1", SIAM, 1998.
    [n,p] = size(X);
    Q = zeros(n,p);
    R = zeros(p,p);
    for k = 1:p
        Q(:,k) = X(:,k);
        for i = 1:k-1
            R(i,k) = Q(:,i)'*Q(:,k);
            Q(:,i)'*Q(:,k)
            Q(:,k) = Q(:,k) - R(i,k)*Q(:,i);
        end
        R(k,k) = -norm(Q(:,k))';
        Q(:,k) = Q(:,k)/R(k,k);
    end
end

[mankan]

Som sagt, dags att profilera koden och antagligen se över minneshanteringen. Du skapar och kastar bort en massa matriser jättemånga gånger in din qr-funktion, tänk om du hade haft de på stacken istället.

-Ofast -funroll-loops (inte säkert -Ofast räknar rätt):

Kod: Markera allt

[root@zombiezoo linalg]# time ./SVDtest
Total speed of SVD was 0.552830,

[Al_Bundy]

Fast jag gör det mer i svd.c och svd.c går snabbare än qr.c

Orsaken varför jag har valt detta har med att biblioteket ska vara så MATLAB-likt som möjligt.
Jag vet inte vad du menar med profilera koden. Jag vet inte vad du menar med stack, men jag har för mig att det har med lite mer med minneshantering typ som kö och lista.

[bearing]

Det går ju alltid att googla på profiling.

I devcpp är det enkelt att köra profilering och att få fina siffror på vilka funktioner som tar mest tid.

Men det går nog med hjälp av några fiffig kommandon från din linuxprompt också. Jag vet dock inte hur.

[Mr Andersson]

Vad som menas är att du måste testa koden istället för att gissa.

Screenshot_22.png

Ursäkta att det en skärmbild istället för text men det går ju inte formattera text på det här forumet.

[Al_Bundy]

Snyggt! Här kan man verkligen se vad som behöver finslipas på. Jag har aldrig hört talas som detta. Helt nytt.

Hur kan cut.c vara en stor bov i dramat? Det är en enkel C-kod bara.

lu.c kan jag förstå. Det handlar om att skapa en nedre triangel matrix och övre triangel matris. Sådant kostar mycket.

Dot.c förstår jag inte heller. Den är ju den simplaste koden av alla.

[Mr Andersson]

Det må vara lite kod men det är extremt många anrop.

[bearing]

Funktionerna dot och cut anropas ju några hundratusen gånger enligt tabellen. Så det är ju en anledning till att även en enkel kod tar lång tid totalt. Men fokus ska ju helt klart läggas på cut, samt om den behöver anropas så ofta.

[Al_Bundy]

Jag har hittat ett sätt där jag kan minimera cut.c riktigt effektivt. Det är enkelt enkelt en sak som jag hade glömt att skriva dit.

[Mr Andersson]

[...] samt om den behöver anropas så ofta.

Det här är största problemet.
Han anropar cut för varenda loop-iteration fastän käll-matrisen är oförändrad.
Att flytta ut anropet utanför loopen, två kodrader behöver flyttas, tar bort 50% av körtiden.

[mankan]

Och i cut kan man köra radvis memcpy på de rader man vill ha istället för att loopa över alla element i källmatrisen.