Svenska ElektronikForumet

Hur skulle du vilja göra det

Al_Bundy skrev: Jag kan säga att det kommer inte bli en perfekt vektoriserad kod då jag använder for-loopar. Men som tur så är C riktigt snabbt.

Hur ser den perfekt vektoriserade koden ut då?

Fundera inte på det.
Fundera inte för mycket på prestanda. Börja med att få det att fungera.
Alla använder loopar. Låt kompilatorn optimera koden.

AndLi skrev:Hur skulle du vilja göra det

Al_Bundy skrev: Jag kan säga att det kommer inte bli en perfekt vektoriserad kod då jag använder for-loopar. Men som tur så är C riktigt snabbt.

Hur ser den perfekt vektoriserade koden ut då?

Allt skrivet på en enda rad. Det är det som kallas för vektorisering.

hawkan skrev:Fundera inte på det.
Fundera inte för mycket på prestanda. Börja med att få det att fungera.
Alla använder loopar. Låt kompilatorn optimera koden.

Ja. Jag vet att jag kan inte skriva optimerad C-kod. Men jag försöker göra så bra jag kan t.ex. använda mycket pekare för att spara på minne.

Du kanske har skrivit det innan, men hur stora matriser kommer du att ha?
Framförallt, ändrar de storlek från beräkning till beräkning?
Frågar för C är lite kass på matriser egentligen när det gäller deklarationer.

Al_Bundy skrev:

hawkan skrev:Fundera inte på det.
Fundera inte för mycket på prestanda. Börja med att få det att fungera.
Alla använder loopar. Låt kompilatorn optimera koden.

Ja. Jag vet att jag kan inte skriva optimerad C-kod. Men jag försöker göra så bra jag kan t.ex. använda mycket pekare för att spara på minne.

Första steget vid optimering är att välja rätt algoritm och sedan i detta fall titta på vad kompilatorn kan och gör för att få så bra prestanda (exvis hastighet eller storlek) som möjligt .

hawkan skrev:Du kanske har skrivit det innan, men hur stora matriser kommer du att ha?
Framförallt, ändrar de storlek från beräkning till beräkning?
Frågar för C är lite kass på matriser egentligen när det gäller deklarationer.

Jag kommer ha 36x36 matriser. Dem ändrar inte storlek.

C är ett jävligt dåligt språk. Synd att det finns inget som kan ersätta det.

hummel skrev:

Al_Bundy skrev:

hawkan skrev:Fundera inte på det.
Fundera inte för mycket på prestanda. Börja med att få det att fungera.
Alla använder loopar. Låt kompilatorn optimera koden.

Ja. Jag vet att jag kan inte skriva optimerad C-kod. Men jag försöker göra så bra jag kan t.ex. använda mycket pekare för att spara på minne.

Första steget vid optimering är att välja rätt algoritm och sedan i detta fall titta på vad kompilatorn kan och gör för att få så bra prestanda (exvis hastighet eller storlek) som möjligt .

Just nu löste jag QR faktorisering med modifierad Gram-Schmidt. Nu försöker jag hitta komplexa egenvärden med QR-metoden. Hur man gör det, vet jag inte.

Tittade just i
en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations

Det gäller alltså att ha bra algoritmer, men även med de snabbaste blir
det här opraktiskt i många reglersystem.


Matrix multiplication n×n matrices:
Schoolbook matrix multiplication O(n3)

Matrix inversion, n×n matrix:
Gauss–Jordan elimination O(n3)
Optimized CW-like algorithms O(n^2.373)

Determinant n×n matrix:
Laplace expansion O(n!)
Division-free algorithm O(n4)
LU decomposition O(n3)



För 36x36 matriser:
n**2.27 =3410.4 ; millisekunder.
n3 = 46656 ; nästan sekunder.
n4 = 1679616 ; många sekunder.
n! = Laplace expansion kan man glömma

Al_Bundy skrev:C är ett jävligt dåligt språk.

Kan du vidareutveckla detta lite?

Al_Bundy skrev:

AndLi skrev:Hur skulle du vilja göra det

Al_Bundy skrev: Jag kan säga att det kommer inte bli en perfekt vektoriserad kod då jag använder for-loopar. Men som tur så är C riktigt snabbt.

Hur ser den perfekt vektoriserade koden ut då?

Allt skrivet på en enda rad. Det är det som kallas för vektorisering.

Nej det är knappast vektorisering.

C är ett jävligt dåligt språk

Nej C är ett väldigt bra språk, men det är inte skapat för linjär algebra i första hand

För 36x36 matriser:
n**2.27 =3410.4 ; millisekunder.
n3 = 46656 ; nästan sekunder.
n4 = 1679616 ; många sekunder.
n! = Laplace expansion kan man glömma

Vad får du tiderna från: 1679616 instruktionet = 0.4 sekunder på en stm32h7

>> Vad får du tiderna från: 1679616 instruktionet = 0.4 sekunder på en stm32h7

Mina (grova) tidsuppskattningar är är för STM32F4 som väl var aktuell ??
Observera också att en cykel här är många maskincykler. Kanske tjogtals.

Ps. Jag var kanske lite pessimist här. Testade en skolboks-matris-multiplikation med (volatile )heltal.
36x36-matris. 46566 cykler. Det gick på ca 1 ms. Flyttal går väl lika fort ungefär.
En n4 , 1679616 instruktioner, tog 0,25 sekunder.
Men det är kanske inte alltid det går så här snabbt! Viktigt med rätt formulerad algoritm!

Rick81 skrev:

Al_Bundy skrev: Allt skrivet på en enda rad. Det är det som kallas för vektorisering.

Nej det är knappast vektorisering.

Och dessutom, även om det vore det så handlar det om ett kompilerat högnivåspråk. Det spelar ingen roll om källkoden är en rad eller 100 rader, den kompilerade filen kan bli identisk ändå.

säter skrev:

Al_Bundy skrev:C är ett jävligt dåligt språk.

Kan du vidareutveckla detta lite?

Behöver jag ens det? Visst.

För mig är C ett bråkigt språk som ej tillåter användaren att göra det den vill. Tänk om man skulle kunna programmera uC:s med Java eller annat högnivåspråk och samtidigt få det effektivt och lätt. Tydligen så har ingen gjort detta än, vilket jag måste ge C ett plus i kanten för.

Alltså, verklig vektorisering kräver två saker:

1. En hårdvara (processor osv) som har stöd för vektoroperationer. Cray1 kan nämnas, men det finns fler.
2. En programvara med stöd för att generera vektoroperationer. Förr ofta Fortran versioner med stöd för vektorhårdvaran.

Enbart att man har stöd för operationer som kan hantera en array utan att själv koda en loop
är inte vektorisering i sig. Processorn kommer ändå att hantera varje element i arrayen var för
sig sekvensiellt (mer eller mindre)...

Här finns t.ex en beskrivning av vektor implementeringen i VAX arkitekturen (en option):
https://www.computer.org/csdl/proceedin ... 134527.pdf