Schnelle Multiplikation von Bytes

Du warst zu schnell, wollte noch zur Info den gesamten Bascom-Assembler posten für die drei Zeilen:

For N = 0 To 10000000
A = 5 * 2
Next

Code:

; For N = 0 To 10000000 +00000043: E080 LDI R24,0x00 Load immediate +00000044: E090 LDI R25,0x00 Load immediate +00000045: E6A1 LDI R26,0x61 Load immediate +00000046: E0B0 LDI R27,0x00 Load immediate +00000047: 938D ST X+,R24 Store indirect and postincrement +00000048: 939C ST X,R25 Store indirect loc_49: +00000049: E840 LDI R20,0x80 Load immediate +0000004A: E956 LDI R21,0x96 Load immediate +0000004B: E968 LDI R22,0x98 Load immediate +0000004C: E070 LDI R23,0x00 Load immediate +0000004D: E6A1 LDI R26,0x61 Load immediate +0000004E: E0B0 LDI R27,0x00 Load immediate +0000004F: 910D LD R16,X+ Load indirect and postincrement +00000050: 911D LD R17,X+ Load indirect and postincrement +00000051: FB17 BST R17,7 Bit store from register to T +00000052: F41E BRTC PC+0x04 Branch if T flag cleared +00000053: EF2F SER R18 Set Register +00000054: EF3F SER R19 Set Register +00000055: C002 RJMP loc_58 Relative jump loc_56: +00000056: 2722 CLR R18 Clear Register +00000057: 2733 CLR R19 Clear Register loc_58: +00000058: 940E0090 CALL 0x00000090 Call subroutine +0000005A: F01C BRLT loc_5E Branch if less than, signed ;Adr= +0000005B: F011 BREQ loc_5E Branch if equal +0000005C: 940C0067 JMP loc_67 Jump ; A = 5 * 2 loc_5E: +0000005E: E08A LDI R24,0x0A Load immediate +0000005F: 93800060 STS 0x0060,R24 Store direct to data space 10: Next +00000061: E6A1 LDI R26,0x61 Load immediate +00000062: E0B0 LDI R27,0x00 Load immediate +00000063: 940E006F CALL loc_6F Call subroutine +00000065: 940C0049 JMP loc_49 Jump loc_67: +00000067: ; SCHLEIFENENDE -> WEITER IM CODE ; ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦ S U B R O U T I N E ¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦¦ loc_6F: +0000006F: 91ED LD R30,X+ Load indirect and postincrement +00000070: 91FC LD R31,X Load indirect +00000071: 9631 ADIW R30,0x01 Add immediate to word +00000072: 93FC ST X,R31 Store indirect +00000073: 93EE ST -X,R30 Store indirect and predecrement +00000074: 9508 RET Subroutine return

das sind dann 26 Words in der Schleife

und jetzt mal in WinAVR:
uint32_t n;
uint8_t a;
for (n=0; n < 10000000; n++)
{
a=TCNT0; //damit der Compiler es nicht wegoptimiert
}

Code:

; for (n=0; n < 10000000; n++) +0000005C: E020 LDI R18,0x00 Load immediate +0000005D: E030 LDI R19,0x00 Load immediate +0000005E: E040 LDI R20,0x00 Load immediate +0000005F: E050 LDI R21,0x00 Load immediate ; a=TCNT0; loc_60: +00000060: B782 IN R24,0x32 In from I/O location +00000061: 5F2F SUBI R18,0xFF Subtract immediate +00000062: 4F3F SBCI R19,0xFF Subtract immediate with carry +00000063: 4F4F SBCI R20,0xFF Subtract immediate with carry +00000064: 4F5F SBCI R21,0xFF Subtract immediate with carry +00000065: 3820 CPI R18,0x80 Compare with immediate +00000066: E986 LDI R24,0x96 Load immediate +00000067: 0738 CPC R19,R24 Compare with carry +00000068: E988 LDI R24,0x98 Load immediate +00000069: 0748 CPC R20,R24 Compare with carry +0000006A: E080 LDI R24,0x00 Load immediate +0000006B: 0758 CPC R21,R24 Compare with carry +0000006C: F398 BRCS loc_60 Branch if carry set

das sind dann 12 Words in der Schleife

Die schleife frisst viel, egal mit was compiliert wird. Zudem Hat es Marco schon angesprochen, daß der Ablauf ja nicht nur die Multiplikation abarbeitet.
Wie e-fan schon geschildert würde ich auch versuchen mit 8bit-Schlaufen manuel zu arbeiten, welche ineinander greifen....denn....2schlaufen von 8bit sind schon 65025, nochmal 8 bit wären 16581375!
Also 3 Schlaufen a 8Bit. Und wenns richtig schnell werden soll am besten ASM!

@-tomas
Auch eine Multiplikation von A = A*2 und danach A = 2 dauert nicht mal 1/20 länger.

Werde dann wohl am besten Bascom nehmen und ASM Routinen für die Berechnungen.
Gruß,
Rasmus

wie ich schon sagte, alles zu theoretisch ( A = A*2)
Du müsstes mal den Codeausschnitt oder den Algorithmus zeigen.

Zitat:

ASM Routinen für die Berechnungen

gute Idee, da Bascom in ASM direkt die Bascom-Variablen ansprechen kann:
Hier mal ein Codeschnipsel für eine NoSave-ISR mit zwei Variablen in den verschiedenen Schreibweisen (Pointer etc)

Code:

Config Timer0 = Timer , Prescale = 1024 'Takt: 64µs On Timer0 Timer_irq Nosave 'Timerüberlauf ISR Const Timervorgabe = 0 Dim Ueberlauf As Byte 'wegen Assembler als Byte Timer_irq: 'Nosave ISR -> save used register push r24 in r24,sreg push r24 'Timer0 laden ldi r24, Timervorgabe !out Tcnt0 , R24 'Set Ueberlauf ldi r24, $01 sts {Ueberlauf}, r24 'restore used register pop r24 !out sreg,r24 pop r24 Return

Danke!
Ich denke mal C und ASM-Rechenroutinen oder Bascom und ASM-Rechenroutinen machen keinen großen Unterschied, oder?

Bin gerade erst in das Projekt eingestiegen und soll jetzt die Umsetzung auf nem AVR Realisierung. Werde hier dann demnächst mal in diesem Thread berichten wie das Projekt verläuft.(Muss jetzt erstmal Robocup machen ;-) ).

Gruß,
Rasmus

Hier mal in Assembler, weniger als 3,3 sekunden O:)

Code:

.include "m32def.inc" .def temp = r16 .def temp2 = r17 .def temp3 = r18 .def counter1 = r20 .def counter2 = r21 .def counter3 = r22 init: ldi temp, 0xff ;Ausgänge schalten um das Ende mit out DDRB, temp ;einer LED mitzuteilen out PortB, temp ldi counter1, 128 ;24bit Zahl (=1000000) ldi counter2, 150 ldi counter3, 152 start: ldi temp, 5 ;Werte laden ldi temp2, 2 multiplikation: mul temp, temp2 ;multiplizieren dec counter1 ;Schleife abarbeiten brne multiplikation dec counter2 brne multiplikation dec counter3 brne multiplikation fertig: cbi PortB, 2 ;LED an um Ende zu singalisieren ende: rjmp ende

Zu multiplizierende Werte in temp und temp2 laden, das Ergebniss steht dann in r0 und r1.

Das Ergebniss könnte man dann auch gleich verarbeiten, nach erfolgter multiplikation kurze subroutine aufrufen und wieder zurückspringen.

Code:

.include "m32def.inc" .def temp = r16 .def temp2 = r17 .def temp3 = r18 .def counter1 = r20 .def counter2 = r21 .def counter3 = r22 init: ldi temp,high(RAMEND) ;Stack einrichten out SPH,temp ldi temp,low(RAMEND) out SPL,temp ldi temp, 0xff ;Ausgänge schalten um das Ende mit out DDRB, temp ;einer LED mitzuteilen out PortB, temp ldi counter1, 128 ;24bit Zahl (=1000000) ldi counter2, 150 ldi counter3, 152 start: ldi temp, 5 ;Werte laden ldi temp2, 2 multiplikation: mul temp, temp2 ;multiplizieren rcall subroutine ;Ergebniss auswerten ;schneller wäre es die subroutine gleich hier auszuführen dec counter1 ;Schleife abarbeiten brne multiplikation dec counter2 brne multiplikation dec counter3 brne multiplikation fertig: cbi PortB, 2 ;LED an um Ende zu singalisieren ende: rjmp ende ;=========================== subroutine: ;hier kann man etwas mit dem in r0 und r1 stehenden Ergebniss machen ldi temp, 4 ;neue Werte laden inc temp2 ret ;zurück zum rechnen

Allerdings braucht das dann schon 9 Sekunden.

Wie weit wird denn das Ergebniss verarbeitet?
das sollte auf jeden fall auch in Assembler erfolgen, sonst werden aus den 3,3 Sekunden 3,3 Minuten :-(

Gruß,
Sven

Zitat:

Zitat von izaseba

Es hat mich wirklich interessiert, wie lange das mit gcc etwa dauern könnte, hier ein Pseudocode mit Mega8 und 16 MHz:

Code:

uint8_t zahlen[] = { 1,2,3,4,5,6,7,8,9,0 }; uint32_t loop = 10000000; uint8_t resultat; uint8_t a = 0; uint8_t b = 9; uart_init(); while(loop){ resultat = zahlen[a] * zahlen[b]; a++; b--; if (a == 10) a=0; if (b == 0 ) b=9; loop--; }

Naja, sinnlos...
Nach etwa 14 Sekunden war er damit fertig...

Gruß Sebastian

Wobei auch hier das wesentliche in der Tonne landet: result wird nirgends verwendet, also von gcc wegoptimiert...

Zitat:

Wobei auch hier das wesentliche in der Tonne landet

Stimmt, wobei irgendwoher müssen die 14 Sekunden kommen.
Aber wie man schon oben gesagt hat wird die meiste Zeit dafür draufgehen, die Daten zu besorgen und zu speichern/weiterverarbeiten und nicht für das nackte rechnen :-)

Gruß Sebastian

Zitat:

Zitat von robotxy

So! Ich habe jetzt mal mit Stopuhr gestoppt(AVR Resetet und gleichzeitig Uhr gestartet)

Für 10 Millionen Multiplikationen hat er 41,31 Sekunden gebraucht.

Dieser Assemblerschnippsel benötigtmit halbwegs realistischen Bedingungen ca: 9,4 sek (so um die 150 Mio Takte).

Anzeige wenn fertig mittels LED an PIN PD0

Halbwegs realistisch heisst:
Ich hole mir die 2 Faktoren aus dem Speicher und das 16 Bit ergebniss wandert auch dort hin.

Das Halbwegs kommt übrigens daher, das 10 Mio Multiplikationen doch schon leicht übertrieben sind. Denn:

1. alleine für die Faktoren würde man so ca: 19 MB Ram benötigen.
2. nur für die Ergebnisse ebenfalls.

Also, wenn man mit dem Mega mal ebend 38 MB externen RAM angesteuert bekommt ist das sicherlich kein Problem.

Code:

; ; Definitionsfile .include "m32def.inc" ; ; Registeraliase .def temp = r16 .def fak1 = r17 .def fak2 = r18 .def count1 = r20 .def count2 = r21 .def count3 = r22 .cseg .org 0x00 ; ; ISR Vektoren jmp isr_reset ; Reset .org 0x2A ; ; HW Initialisierung isr_reset: ldi temp, high(RAMEND) ; Stackpointer out SPH, temp ldi temp, low(RAMEND) out SPL, temp ldi temp, 0xFF ; alle ungenutzten Ports -> Eingang + Pullup out PORTA, temp out PORTB, temp out PORTC, temp out PORTD, temp ldi temp, 1 ; Pin D0 -> Ausgang +H out DDRD, temp ; ; Definierte Werte schaffen ldi ZH, high(SRAM_START) ldi ZL, low(SRAM_START) ldi temp, 2 st Z, temp ldi temp, 5 std Z+1, temp ; Main Loop loop_init: ldi count3, 0x98 ldi count2, 0x96 ldi count1, 0x7F loop: ld fak1, Z ldd fak2, Z+1 mul fak1, fak2 std Z+2, r0 std Z+3, r1 subi count1, 1 sbci count2, 0 sbci count3, 0 brne loop cbi PORTD, 0 break jmp loop_init

Grüße,

da Hanni.

Zitat:

Zitat von izaseba

Zitat:

Wobei auch hier das wesentliche in der Tonne landet

Stimmt, wobei irgendwoher müssen die 14 Sekunden kommen.
Aber wie man schon oben gesagt hat wird die meiste Zeit dafür draufgehen, die Daten zu besorgen und zu speichern/weiterverarbeiten und nicht für das nackte rechnen :-)

Die meiste Zeit geht fürs Datenholen und den Loop drauf ...

Faktoren holen: 4 Takte
Multiplikation: 2 Takte
Ergebnis sichern: 4 Takte
der Loop: 5 Takte

man sieht, es läppert sich zusammen ... von 15 Takten die diese Schleife je Durchlauf braucht gehen mal eben 13 für den Rest drauf, was mal eben einen Anteil von 86% an der Gesamtzeit ist.

Grüße,

da Hanni.