Schnelle Multiplikation von Bytes

**-tomas-** · 02.06.2006, 00:03

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

**Rage_Empire** · 02.06.2006, 07:23

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!

**robotxy** · 02.06.2006, 07:40

@-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

**-tomas-** · 02.06.2006, 09:43

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

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

**robotxy** · 02.06.2006, 09:56

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

**Mehto** · 02.06.2006, 10:47

Hier mal in Assembler, weniger als 3,3 sekunden

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

**SprinterSB** · 02.06.2006, 18:14

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...

**izaseba** · 02.06.2006, 19:59

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

**Hanni** · 02.06.2006, 20:02

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.

**Hanni** · 02.06.2006, 20:08

Zitat von izaseba

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.

Thema: Schnelle Multiplikation von Bytes

Themen-Optionen

Thema durchsuchen

Anzeige

Lesezeichen

Lesezeichen

Berechtigungen