ASM rutin segítség kérés

[Csuhas]

Egy pár soros pascal rutint kellene átírnom xmega procira de sebességkritikus volta miatt assembly rutin szükséges. ( Egyébként a program többi része bascom alatt íródik. ) Mivel assemblyben nem programoztam még atmel procit ezért csak kínlódok vele. Erről volna szó:

var
a: array [0..1400] of byte;
c: array [0..750] of integer;
k,n,i: integer;
.....
for k:=90 to 650 do begin
n:=0;
for i:=1 to 700 do n:=n+abs(a-a[k+i]);
c[k]:=n;
end;

Tudna valaki segíteni?

[kapu48]

Ezt a részt neme értem:
a-a[k+i]
Az a(n) tömb. És magában nem lehet rá hivatkozni!
Csak valamelyik elemére mondjuk: a(1)-a(k+i)

Először Bascomba tegyük.

Kód: Egész kijelölése

$regfile = "m128def.dat"
$crystal = 16000000
$hwstack = 220
$swstack = 220
$framesize = 330
'(
var
a: array [0..1400] of byte;
c: array [0..750] of integer;
k,n,i: integer;
.....
for k:=90 to 650 do begin
n:=0;
for i:=1 to 700 do n:=n+abs(a-a[k+i]);
c[k]:=n;
End;
')

Dim A(1401) As Byte
Dim C(751) As Integer

Dim K As Integer , N As Integer , I As Integer , T As Integer , T2 As Integer

For K = 90 To 650
   N = 0
   For I = 1 To 700
      T = K + I
      T2 = A(k) - A(t)
      T = Abs(t2)
      N = N + T
   Next I
   C(k) = N
Next K

End                                                         'end program

Valahogy így.

Ebből mi kel ASM-ban?
Az ABS() függvény ASM-ba át írása nagy munka lesz.

[Csuhas]

Az a sor hibás talán a fórummotor szabta át, vagy én voltam figyelmetlen. Helyesen n := n + abs ( a (k) - a (k+i) );
Ez egyébként ez egy egyszerűsített autokorrelációs rutin. Időkritikus a futása, a PC-n futó pascal programban is
ez a kettős ciklus asm betét volt, de még igy is a futásidő kilenc tizede erre jutott. Most ezt a programot kellene egy
xmegába gyömöszölnöm. Jelenleg 1800mS a futási idő basicben megírva, ezt kellene pár mS-ra optimalizálni.
Ha nem sikerül akkor valami erősebb procit kell majd keresnem, de akkor új nyák és új engedélyek kellenek.

[kapu48]

8 BIT-es Procival ne remélj csodát!

Hiszen Integerben számolsz. És az 2 Byte.

A belső for ciklus durván 600*700=240 000 fut le.
1 ciklus 160 órajel most.

[Robert]

700x fut le a belső, a külső 550x. Azaz a belső mag: 550*700 = 385.000
Az xMega 1 utasítás/órajellel számolva így a ciklusmagod hossza. Mondjuk 10 ms-ba akarod belegyömöszölni:
32 MHz-n a 10 ms alatt van 32.000.000 - 1 sec -> 32.000 -> 1 msec
Hát, semmi jót nem vetít előre....

Kérdés: online kell tudni, vagy amikor odafordulok kellene?
Utóbbi esetben esetleg külső processzor(ok)ra kiszervezni az adatot és I2C/SPI-n berántani?
Vagy nagy memóriába letárolni valami kész adattáblát azt behúzni?

Számoljunk:
xMega 32 MIPS.

Neked kellene 160 utasításos ciklusmaggal, 600*700 -> 420.000 lefutás: =>
420.000*160 = 64.200.000 utasítás 2 msec alatt.
1 Sec esetén ez ennek 50x-ese, azaz 3.360.000.000. Ház ez testvérek közt 3.360 MIPS

http://hu.wikipedia.org/wiki/Instructions_per_second
Arm A8 mag 1 GHz 2.000 MIPS -> kevés.
PS3 Cell proc. 3.2 GHz - 6.400 MIPS

Ez sem a mikrokontroller kategória


Vagy hülye tipp: vektorprocesszor? Azonos folyamatokat hajtasz végre egész számokkal....
Esetleg egy OpenGL VGA kártyát beizzítani mellé?


Vagy a függvényt nem lehet optimalizálni valahogy? Az ilyen szintű matek nálam már elment a végtelenbe .

[Csuhas]

Köszi Robert!

Ez meggyőző rövid számítás volt. A készülék eddig adatot gyűjtött sd kártyára majd elküldte gsm modemen és a szerver dolgozta fel az adatokat. Ezt szerette volna a főnököm az atmelre bízni. Nos tisztán látszik hogy minden optimalizálási lehetőséget kihasználva sem fér bele ez az algoritmus ebbe a prociba.
A kezdetekben ez a pascal program asm betéttel még éppen elfutott a 486 75MHz-es asztali gépen.

Egyébként a bascom sem csinál nagyon rossz kódot hiszen durván 147 utasítás jut átlagosan egy ciklusra.

[Robert]

A 486-os processzor kb. dupla teljesítményű, mint az AVR (nyers MIPS alapon). Azonban a 486-osban (DX) ott van benne a matematikai koprocesszor... Na ilyen koprocesszor nincs az AVR-ben. HW-es szorzó mintha lenne, de több nem sok...
Bár lehetne csinálni egy prcesszorfarmos holmit

Hülye tipp, hátha:
Raspberry Pi? Azon ~900 MHz-s a ARM11 mag és minden ott van készen. linux ala + pascal fordító... És ha nagyon kell a számolást kiszervezed videókártyára .... (és abban is mintha lenne matematikai segédprocesszor)

[csabeszq]

Szerintem simán meglehetne 16MHz-es AVR-rel csinálni.

Legalábbis én informatikusként teljesen másként állnék a dologhoz, nem úgy, hogy 700x700 elemen végigmenjek ha esik, ha fúj.

A számításigényes munkákat mi cache-eljük: ez azt jelenti, hogy egyszer végigmész és kiszámolsz mindent, eltárolod a részeredményeket.
A következő alkalommal a részeredményeket felhasználva sokkal gyorsabban tudsz végeredményt mondani.

Jelen példa esetén:
- egyszer kiszámolod 700x700 elemre
- ha A[13] megváltozik 5-ről 7-re, akkor hogyan változik meg C[x] értéke? Ez kiszámolható, matematika.

Mélyebben nincs időm belemászni, de amennyiben az 'A' tömb értékei ritkán változnak, úgy a négyzetes algoritmus lineárissal felváltható és onnantól 1MHz-en is elmegy.

[Csuhas]

No igen ezen a lehetőségen töröm épp a fejem ( nem sok eredménnyel

Az A tömb szisztematikusan változik. A bejövő új adatok shiftelik a tömb elemeit. ( az utolsó mindig elveszik. )
Minden 400. új adat után kell futtatni a teljes ciklust.

A tömb jelentős része nem változik meg két futás között.
Illetve lehetőség volna minden egyes új érték érkezésekor elvégezni néhány műveletet ( beszámítani az új értéket, és "kivonni" a kieső byte hatását. )

[csabeszq]

A shiftelést egy ciklikus pointerrel növelésével szoktuk csinálni.

int ptr = 13;
int arraySize = 1400;
int value = array[(ptr+index)%arraySize];

C-re ás A-ra is ilyen ciklikus pointer fog kelleni.

Az algoritmus nálad:
- kivonod az utolsó kishiftelendő értékeket az összes C[x]-ből. (lineáris)
- növeled a ciklikus pointereket (O(1))
- hozzáadod az új értékeket az összes érintett C[x]-hez. (lineáris)

[Csuhas]

Jelenleg a pascal program úgy működik hogy minden bejvő adat beíródik három tömbbe, rendre x, x+400, és az x+800 helyre. A 400. adatnál az egyik tömbben rendelkezésre áll 3*400 adat. Ez másolódik át a a korreláció kiinduló adataként. Így az a tömb első 1200 eleme érték míg a többi zérus. A kérdéses ciklus előtt még egy mozgó átlagolás is végigfut a tömbön ( aluláteresztő szűrő )

[kapu48]

Robert írta: Arm A8 mag 1 GHz 2.000 MIPS -> kevés.
Ez így nem biztos!

Mivel 32 BITES proci.
És nem 2 külön műveletben dolgozza fel a 16 Bites integert.
+Itt kevesebb az 1 órajelre eső idő.
+Van GPU benne.
Ezért kb. 1 ciklus orajel akár a ¼-e lenne, mint az AVR-en.
+
Na meg az autógyártók beérik a 480MHz ARMokal is.

[csabeszq]

Ebben a formában sajnos a négyzetes ciklust nem tudod elkerülni.

[Csuhas]

Időközben hosszas egyeztetések után kiderült, hogy elég lesz ezt a kettős ciklust másodpercenként futtatni.
Mivel egyéb dolga is van a procinak ezért még mindig szükség volt az átírásra, hogy a most 1800mS ciklus beleférjen ebbe a bővebb időkeretbe.

Elsőként még mindig basicben a belső ciklust
átírtam három, byteos ciklusváltozójú rutinra.
Ezzel lement a futásidő 1400ms-ra

Ezután a ciklusokat asm-ben kódolva kihasználva az autoinkremens indexelést és minden változót regiszterben tárolva sikerült levinni a teljes futási időt kb 175ms-ra.
A ciklusmagban kb egy tucat utasítás fut, de ez függ az adatoktól is.

Ez az idő már jól megfelel az enyhített feltételeknek így haladhatok tovább.

Köszönöm a tanácsokat!