mikrocontroller.net

Forum: Compiler & IDEs Cycle Count auswerten und verstehen anhand von Shifts und Arrays


Autor: Christopher S. (shalec)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
/**************/
+ ARM-Cortex M4
+ MCJU-407
+ STM32F407VGT6
+ arm-none-eabi-gcc
/*************/

Schon mal im Vorfeld: Sry, dass es so viel Text wird. Aber es ist ein 
Problem, dass ich mir nicht erklären kann und das durchaus mehr Input 
benötigt, als 1-3 Zeilen geben könnten. Ich bedanke mich im Voraus für 
die genommene Zeit. Ich habe auch versucht Elemente fett hervorzuheben, 
aber da war ich leider erfolglos :(

Hallo allerseits,
was ich bereits durch das Board hier gelernt hatte, ist die korrekte 
Anwendung zum Cycles zählen. Nun stehe ich aber vor einem kleinen 
"Problem" und verstehe das Resultat nicht.

Angenommen ich habe eine Funktion, die einen Array  (uint32_t [11]) 
340-Mal nach links shiftet und nach jedem Shift das Bit "341" (Bit 20 in 
Array entry 10) auf ==1 testet. Ist das Ergebnis wahr, wird noch was 
anderes gemacht. Aber der Einfachheit halber können wir das auf 340 
leftshifts abkürzen.

Ein Leftshift wird wie folgt realisiert:

*Alg.1*
typedef uint32_t arr[11];
void leftshift(arr A, uint8_t count)
    for(int i=10; i>0; i--){
        A[i] = ( ( A[i]<< count ) | ( A[i-1]>> (32-count) ) );
    }
    A[0] <<= count;
}

Ich shifte den Eintrag um 1 Bit nach links und verklebe das mit dem 1. 
Bit aus dem vorherigen Eintrag durch leftshift(A,1). Ich denke, dass es 
dafür keinen effizienteren Weg gibt. In jedem Fall kostet diese 
Operation ca. 90-94 Cycles. (In der Summe würde mich das dann 3*340*90 = 
91.800 Cycles kosten, also sehr teuer :( )

*1. Frage:* Ist das wirklich die effizienteste Methode um solch einen 
Shift durchzuführen?

Die Arrays werden anhand einer Barett/Montgomery Reduktion erstellt und 
füllen die "Matrix" arr G[3]. Nun habe ich mir bei 1k zufälligen 
Eingaben die Arrays angeguckt und festgestellt, dass G[2] häufig ein 
0-Array oder mit maximal 20 Bits besetzt ist. Demnach nutze ich die 
Buildin vom Compiler "CLZ" als makro "#define CLZ(x) 
(__builtin_clz(x))", um an einer Stelle "G[2][i] die führenden Nullen zu 
zählen. Mein Ablauf ist nun wie folgt.

*Alg.2*
#define CLZ(x) (__builtin_clz(x))
...
int entry=10, neq=0;
while(G[2][entry] == 0 && entry > 0) entry -=1;
neq = CLZ(G[2][entry]);

anhand dieser Ergebnisse "shifte" ich nun Block und Elementweise:

*Alg.3*
void leftshift_blocks(arr A, int block)
{
    int i;
    for(i=10; i>=0; i--){
        A[i]= A[block];
        if(block == 0) break;
        block -=1;
    }
    for(i; i>=0;i--){
        A[i]=0;
    }
}

void leftshift_entry(arr A, int block, int neq){
    for(int i=block + 1; i>0; i--){
        A[i] = ( ( A[i]<< count ) | ( A[i-1]>> (32-count) ) );
    }
    A[0] <<= count;
}

Dieses Prozedere, inkl. auszählen der Blocks und Count leading zeros, 
verbraucht 1500 cycles vs. 340*90~31k.

Ich würde nun erwarten, dass meine Auslagerung im gesamten Code zu einer 
entsprechenden Verbesserung führt. D.h. dass ich nun "nur" noch 
91800-30600+1500 = 62700. Aber das Resultat sieht nun so aus, dass ich 
nur (!) 3k Cycles dadurch spare.

*2. Frage* Warum ist das so?

Schalte ich im Compiler die Funktion "-Ofast -funroll-all-loops" ein, 
reduzieren sich die notwendigen Cycles auf 78k vs. 81k.






Meine Tests hatten lokal definierte Variablen genutzt. D.h. ich habe die 
Variablen definiert und dann die Funktionen auf diese Variablen 
ausgeführt.

Der andere Test verwendet innerhalb einer Funktion diese Funktionen. 
Darin werden die Arrays übergeben, jedoch dann lokal gespeichert. D.h. 
ich habe:

*Alg.4*
void foo(arr C, arr A){
    arr G[3]={0};
    split(C,A,G); 
/* nimmt aus A 340 Bits, speichert in G[0]. Nimmt den Rest aus A und füllt mit C auf 340 Bits auf, speichert in G[1]. Nimmt den Rest von C und speichert das in G[2];*/

/* 
   Optimierter Fall: führe Alg. 2 & 3 aus und setze int N=1
   nicht opimierter: Beginne mit int N=2;
*/
while(N--) 
    for(int j=0; j<340; j++) leftshift(G[N], 1);

Meine Tests hatten die gleichen Einträge für A und C genommen, G[2]={5} 
(Beispiel) war dabei ein möglicher Eintrag. Dennoch habe ich nur solch 
einen minimalen Geschwindigkeitsschub bekommen und ich kann es mir 
einfach nicht erklären. Um in den ASM Code zu gucken, fehlt mir leider 
die notwendige Zeit, um hier entsprechend zu optimieren. Wenn das jemand 
für meinen Prozessor kann, bin ich gerne bereit weiteres per PN zu 
klären. :)

: Bearbeitet durch User
Autor: Wolfgang (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Christopher S. schrieb:
> Ich habe auch versucht Elemente fett hervorzuheben,
> aber da war ich leider erfolglos :(

Irgendwelche Leerzeichen oder Interpunktion mag die Forensoftware 
überhaupt nicht innerhalb vorzuhebenden Zeichen. Das it ein uralter 
Fehler.
Die Hervorhebung mit "*...*" war schon richtig gedacht.

Autor: Ruediger Asche (Firma: keine) (rac)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Du kannst mal in Kap. 2 meines Buches gucken, da beschäftige ich mich 
recht ausführlich mit den Auswirkungen von Optimierungen auf die 
Zykluspenalty beim Cortex M. Speziell das Unrolling von Code (das 
i.d.Regel zu wesentlich grösserem Codefootprint, aber zuweilen extrem 
dramatischen Reduktionen der Zyklen führen kann) ist eine nicht ganz 
einfach zu verstehende, aber extrem effiziente Möglichkeit, so viel Code 
wie möglich im Prozessorkern (bestehend aus ICode Bus, DCode Bus,Cache 
und Prozessorergistern) zu halten.

Bevor Du Jemanden da ran lässt, den Code per Hand zu optimieren (das 
geht, wird aber vermutlich nicht umsonst gemacht, dazu ist das viel zu 
spezielles Wissen), könntest Du mal den gcc gegen den kommerziellen 
Cortex Compiler von ARM tauschen. Es werden zwar beide von ARM 
hergestellt, aber natürlich ist added value im kommerziellen Produkt, 
und der liegt bei der Cortex Familie zum nicht unbeträchtlichen Teil im 
Finetuning der performance.

Alternativ kannst Du mal bei Somnium nachfragen, ob deren Produkte Dir 
bei der Problemstellung auch weiterhelfen könnten.

Autor: Shalec#Guest (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hallo und vielen Dank für die Hinweise.

Kostenfrei hätte ich auch nicht erwartet. Im prinzip verstehe ich nicht, 
wie meine optimierte Version im Einzelvergleich auf einen Unterschied 
von 1,5k vs 36k Cycles kommt und im Code (wo 2 exakt gleiche Teile noch 
ausgeführt werden) nur einen Unterschied von 3k Cycles hat.

Ich habe ja eine Schleife, die 2x durchläuft und anschließend eine 
dritte Operation ausführt. Ich habe nur den 1. Durchlauf ersetzt und im 
Einzelvergleich bei gleichem Input diese Werte erhalten.

Ich bin von meinem derzeitigen Stand aus nicht in der Lage diese 
Entwicklung nachzuvollziehen. Erwartet hätte ich eben auch ungefähr 
diesen Unterschied.

Autor: Achim S. (achs)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
darf ich fragen, warum Du das Array schiftest? Also, was mit dem Array 
dann passiert? Der Test des jeweils einen Bits rechtfertigt das ja 
erstmal nicht, dafür würde niemand soviel schieben.

Autor: Shalec#Gast (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Das ist eine spezielle Form der Montgomery Reduktion. Diese zerlegt den 
input in gleich große Teile der Länge der Primzahl und shiftet so lange, 
bis bit 'Primzahllange+1' ==1. Dann wird eine op so oft ausgeführt, bis 
das Bit  wieder 0 ist. Danach wird weiter gestiftet, bis 340 Shifts 
durchgeführt wurden. Das Resultat wird mit dem anderen 340 bit langen 
array verrechnet, welches dann der neue input ist.

Diese Reduktion ist relativ schnell. Meine Primzahl hat 340 bits. Daher 
oben die 340. Wenn ich exakt wüsste, wie ein array im Speicher 
hinterlegt ist, könnte ich das Shiften optimieren. Ein input kann mit 
Übertrage  größer als 680 bit sein. (Produkt)

Sry für Schreibfehler, schreibe über das Handy.

Autor: Kaj G. (Firma: RUB) (bloody)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Shalec#Gast schrieb:
> Wenn ich exakt wüsste, wie ein array im Speicher
> hinterlegt ist
Was genau meinst du?
Die Elemente eines Arrays liegen linear, ohne Luecken, im Speicher.

Autor: Shalec#Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Dann würde ein leftshift eine Verschiebung des pointers auf den neuen 
Anfang sein. Ich denke aber, dass diese nur byteweise verschoben werden 
können.

Autor: Ruediger Asche (Firma: keine) (rac)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Beim Cortex kannst Du überlegen, auf shifts komplett zu verzichten und 
auf Bitband Aliases zu arbeiten.

Autor: Kaj G. (Firma: RUB) (bloody)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Shalec#Gast schrieb:
> Dann würde ein leftshift eine Verschiebung des pointers auf den neuen
> Anfang sein. Ich denke aber, dass diese nur byteweise verschoben werden
> können.
Ich kann dir, ehrlich gesagt, nicht folgen...
#include <stdint.h>

int main( void)
{
    uint8_t  A[5];
    uint32_t B[5];

    return 0;
}
A und B sind konstante Pointer, die kannst du gar nicht verschieben, 
denn dann wuerdest du den Anfang des Arrays verlieren.
    *(A + 1) = 0;   //  A[1] = 0
    *(B + 1) = 0;   //  B[1] = 0
Es wird jeweils die groesse eines Elementes auf die Adresse von A bzw. B 
addiert. Bei A bedeutet das + 1 (weil die Elemente von A 1 Byte gross 
sind) und bei B bedeutet das + 4 (weil die Elemente von B 4 Byte gross 
sind).

In deinem Code shiftest du keine Pointer, sondern die Werte auf die der 
Pointer zeigt, nicht mehr, und nicht weniger.

Das die Elemente hintereinander im Speicher liegen kannst du ganz 
einfach dadurch evaluieren, indem du die Adresse des letzten 
Arrayelementes von der Startadresse abziehst.
#include <stdint.h>
#include <stdio.h>

int main( void)
{
    uint8_t  A[5];
    uint32_t B[5];

    printf("\n\n");
    printf("Startaddr. A: %p\nEndaddr.   A: %p\n\n", A, &A[4]);
    printf("Startaddr. B: %p\nEndaddr.   B: %p\n\n", B, &B[4]);

    return 0;
}
Startaddr. A: 0x7fff949c1a03
Endaddr.   A: 0x7fff949c1a07

Startaddr. B: 0x7fff949c19e0
Endaddr.   B: 0x7fff949c19f0

A[0] liegt an 0x03
A[1] liegt an 0x04
A[2] liegt an 0x05
A[3] liegt an 0x06
A[4] liegt an 0x07

B[0] liegt an 0xe0
B[1] liegt an 0xe4
B[2] liegt an 0xe8
B[3] liegt an 0xec
B[4] liegt an 0xf0

Autor: Christopher S. (shalec)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ruediger A. schrieb:
> Beim Cortex kannst Du überlegen, auf shifts komplett zu verzichten und
> auf Bitband Aliases zu arbeiten.

Davon wusste ich noch nichts. Danke für das Stichwort.

Autor: Christopher S. (shalec)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Genau. Ich hatte entsprechend gedacht, wenn ich um 8 Bit shiften will, 
könnte ich auch einfach die &A[0] Adresse verschieben. Dabei resultiert 
aber ein Problem mit dem letzten Element in &A[n].  Dieses würde dann 
auf Speicher zugreifen, der nicht unbedingt als 0 initialisiert ist und 
zu einem anderen Bereich gehört. Gemäß dieser "cycle-Abkürzung" müsste 
ich von vorn herein die Arrays doppelt so groß machen, wie sie sein 
müssen, damit ich weiß, dass der Speicher dahinter entsprechend als 0 
initialisiert wird.

Zur Frage
Es geht ja prinzipiell um Algorithmus 4, der, je nach Methode, 78k oder 
81k Cycles braucht. Vergleiche ich nur den ersten Iterationsschritt habe 
ich einen Unterschied von 1.5k zu 36k. Vermurkst das der Compiler, kann 
man das allgemein beantworten, oder muss man dafür tatsächlich direkt in 
den Code und entsprechenden ASM Output gucken?


Nebenfrage
Gibt es eine zuverlässige Methode herauszufinden, wie "teuer" das 
initialisieren "uint32_t A[20] = {0};" ist? Über meinen Test mit dem 
Cycle-Counter bekomme ich stets 1 cycle als Ausgabe oder (in einer 
Funktion ausgelagert) 8 +- 2 cycle.

Auch würde mich der Cyclecount für das Aufrufen einer Funktion 
interessieren. Es ist auffällig dass ich z.B. mit der Lib "string.h" 
folgende Werte bekomme:

uint32_t A[11] = {0}, B = {0xff,0xee,...,0x44}
//start count
memcpy(A, B ,44); // A \gets B by 44 byte.
//end count, print count
>> 30

oder ich habe eine Funktion
void arr_cpy(uint32_t *A, uint32_t *B){
    memcpy(A,B,44);
}

uint32_t A[11] = {0}, B = {0xff,0xee,...,0x44}
//start count
arr_cpy(A, B ,44); // A \gets B by 44 byte.
//end count, print count
>> 60

oder als Makro
#define arr_cpy(A,B) (memcpy(A,B,44))
uint32_t A[11] = {0}, B = {0xff,0xee,...,0x44}
//start count
arr_cpy(A, B ,44); // A \gets B by 44 byte.
//end count, print count
>> 38

Autor: Karl (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Du solltest dir wirklich den erzeugten Code des compilers ansehen. 
Sonst ist es nur Rätselraten.

Weiter lässt sich ein shift mit Überlauf in Assembler sehr effizient 
realisieren. Normalerweise würde ich dem compiler zutrauen das zu 
erkennen, falls nicht eben diesen kleinen Teil in Assembler.

Und noch was: lokale Variablen lassen dem compiler viel mehr Freiheiten 
bei der Optimierung als globale. Also mach Lokal was nicht Global sein 
muss.

Loop unrolling kann man bei so kleinen schleifen von Hand machen. Dann 
weiß man was man hat.

Autor: Ruediger Asche (Firma: keine) (rac)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Karl schrieb:
> Du solltest dir wirklich den erzeugten Code des compilers ansehen.
> Sonst ist es nur Rätselraten.
>

+1.

> Weiter lässt sich ein shift mit Überlauf in Assembler sehr effizient
> realisieren. Normalerweise würde ich dem compiler zutrauen das zu
> erkennen, falls nicht eben diesen kleinen Teil in Assembler.
>
> Und noch was: lokale Variablen lassen dem compiler viel mehr Freiheiten
> bei der Optimierung als globale. Also mach Lokal was nicht Global sein
> muss.
>

Jein. Auch da gibt es kleine aber feine Unterschiede. Ein guter Compiler 
wird versuchen, so viele lokale Variablen wie möglich in Registern 
vorzuhalten, da der Zugriff im Kern der schnellstmögliche und 
zyklensparendste ist. Wo das nicht geht, werden die Variablen auf dem 
Stack gehalten, und die Zugriffspenalty darauf hängt beim Cortex davon 
ab, in welchem Speicher der Stack gehalten wird (Zugriff über DCode oder 
Systembus). Dazwischen können atemberaubende Grössenordnungen liegen. 
Bei manchen Cortex PODs lassen sich über Tricks auch externe Speicher 
über den DCode Bus adressieren, was dann abgesehen von unoptimierbaren 
Verzögerungen wie wait states auch noch mal Zyklen spart. Kann der TO 
Alles im Kapitel 2... nachlesen...

> Loop unrolling kann man bei so kleinen schleifen von Hand machen. Dann
> weiß man was man hat.

Wenn man das in C macht, hat man zwar die Gewissheit, dass der loop code 
dabei im Cachezugriff liegt, aber nicht notwendigerweise, dass die 
lokalen Variablen in Registern alloziiert werden (s.o.). Der TO hat nach 
deterministischen Zahlen gefragt. Wenn also noch mehr Variablen lokal 
angelegt werden oder aber durch andere Optimierungen mehr Register in 
Benutzung sind, kann der Compiler plötzlich einige der Variablen wieder 
von Registern in den Stack legen, also können im Quellcode scheinbar 
kleine Änderungen eine signifikante, ohne Kenntnis der Optimierungen 
unerklärliche Erhöhungen der Umlaufzeit nach sich ziehen.

Um alle Möglichkeiten des Zyklensparens auszunutzen sowie 
deterministisches Verhalten zu erzwingen, ist (Inline) Assembler 
unausweichlich.

Autor: Karl (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Ruediger A. schrieb:
> Wo das nicht geht, werden die Variablen auf dem Stack gehalten, und die
> Zugriffspenalty darauf hängt beim Cortex davon ab, in welchem Speicher
> der Stack gehalten wird (Zugriff über DCode oder Systembus).

Naja. Stm32f407. Von externen Speichern lese ich nichts. Jeglicher RAM 
hat 0 waitstates. Idealerweise liegt der Stack im ccm.

Ruediger A. schrieb:
> aber nicht notwendigerweise, dass die lokalen Variablen in Registern
> alloziiert werden (s.o.). Der TO hat nach deterministischen Zahlen
> gefragt. Wenn also noch mehr Variablen lokal angelegt werden oder aber
> durch andere Optimierungen mehr Register in Benutzung sind, kann der
> Compiler plötzlich einige der Variablen wieder von Registern in den
> Stack legen, also können im Quellcode scheinbar kleine Änderungen eine
> signifikante, ohne Kenntnis der Optimierungen unerklärliche Erhöhungen
> der Umlaufzeit nach sich ziehen.

Compiler sortieren Anweisungen nach Belieben um und das hoffentlich 
nicht ohne Grund, sondern um z.b. Stack Zugriffe zu reduzieren. Ich 
glaube das ist dir klar, aber evtl nicht jedem. Wenn der Register Druck 
zu groß wird bleibt ja kaum was als der Stack, oder?
Wenn es um zyklengenauen Determinismus geht sind wir sowieso beim 
falschen Prozessor. Der Code kommt idR aus gecachtem flash mit prefetch. 
Es gibt mehrere busmaster (DMA) und auch manche Befehle dauern abhängig 
von den Daten unterschiedlich lange etc. Da kann man auch mit Assembler 
nur unter sehr spezifischen Umständen Zyklen halbwegs Vorhersagen. Itcm 
und dtcm wären Stichworte.

PS: der ständige Verweis auf dein Buch macht deine Beiträge imho weniger 
sympathisch als es der Inhalt Wert wäre.

Autor: Ruediger Asche (Firma: keine) (rac)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl schrieb:
> Ruediger A. schrieb:
>> Wo das nicht geht, werden die Variablen auf dem Stack gehalten, und die
>> Zugriffspenalty darauf hängt beim Cortex davon ab, in welchem Speicher
>> der Stack gehalten wird (Zugriff über DCode oder Systembus).
>
> Naja. Stm32f407. Von externen Speichern lese ich nichts.

Der Stm32f407 selber unterstützt den FSMC, d.h. OB die Auswahl zwischen 
externem oder internem Speicher ein Thema ist oder nicht, hängt erstmal 
von der konkreten Hardware ab (also ob am FSMC etwas angebunden ist oder 
nicht). Der TO schreibt etwas von MCJU-407, ich vermute das ist ein 
fertiges Board, zu dem ich im Internet auf die Schnelle aber nichts 
finde. In sofern ist zumindestens die Erwähnung dieses Unterschiedes 
relevant für Jemanden, der sich für Zylen interessiert.

> Jeglicher RAM hat 0 waitstates.

Meintest Du das genau so wie Du es geschrieben hast?

> Idealerweise liegt der Stack im ccm.
>

In so einer Anwendung vermutlich schon, aber generell ist die 
Entscheidung darüber, welcher Speicherbereich auf welches Modul 
abgebildet werden sollte, abhängig von der Anwendung.

> Ruediger A. schrieb:
>> aber nicht notwendigerweise, dass die lokalen Variablen in Registern
>> alloziiert werden (s.o.). Der TO hat nach deterministischen Zahlen
>> gefragt. Wenn also noch mehr Variablen lokal angelegt werden oder aber
>> durch andere Optimierungen mehr Register in Benutzung sind, kann der
>> Compiler plötzlich einige der Variablen wieder von Registern in den
>> Stack legen, also können im Quellcode scheinbar kleine Änderungen eine
>> signifikante, ohne Kenntnis der Optimierungen unerklärliche Erhöhungen
>> der Umlaufzeit nach sich ziehen.
>
> Compiler sortieren Anweisungen nach Belieben um und das hoffentlich
> nicht ohne Grund, sondern um z.b. Stack Zugriffe zu reduzieren. Ich
> glaube das ist dir klar, aber evtl nicht jedem. Wenn der Register Druck
> zu groß wird bleibt ja kaum was als der Stack, oder?

D'Accord, und in den meisten Anwendungsfällen sind die Entscheidungen 
des Compilers für den Anwender komplett transparent und optimal, aber 
der TO interessiert sich hier für zyklengenaue Analysen, und dabei macht 
es sehr wohl einen Unterschied, wenn ein Programm, das vorher x(Parm) 
Zyklen gebraucht hat, durch Einführung einer zusätzlichen Variable 
plötzlich x*1,5(Parm) braucht.

> Wenn es um zyklengenauen Determinismus geht sind wir sowieso beim
> falschen Prozessor. Der Code kommt idR aus gecachtem flash mit prefetch.

Korrekt, und eine Menge Optimierungsarbeit geht genau in die Frage, wie 
so viel Code wie möglich im Cache gehalten werden kann. Recht hast Du 
natürlich damit, dass auf den Cacheinhalt kein Verlass ist (wo z.B. 
Interrupthandler eine im Cache liegende Schliefe unterbrechen und 
Refetches erzwingen können).

> Es gibt mehrere busmaster (DMA) und auch manche Befehle dauern abhängig
> von den Daten unterschiedlich lange etc. Da kann man auch mit Assembler
> nur unter sehr spezifischen Umständen Zyklen halbwegs Vorhersagen.

Korrekt was die Bus Matrix betrifft, aber mglw. in der gegebenen 
Konfiguration hinreichend (müsste der TO sich dazu äußern).

Was die unterschiedliche Zyklenzahl der Befehle angeht, so hast Du zwar 
recht, was das Verhältnis Befehle<->Zyklen angeht, aber das ist ein 
konstanter Verzerrungsfaktor.

> Itcm und dtcm wären Stichworte.
>

Guter und wertvoller Hinweis.

> PS: der ständige Verweis auf dein Buch macht deine Beiträge imho weniger
> sympathisch als es der Inhalt Wert wäre.

Nach Bestem Wissen und Gewissen verweise ich auf mein Buch nur dort, wo 
eine Frage dort relevant und in einer Tiefe beantwortet wird, die hier 
im Forum zu weit führen würde. Meiner Meinung nach hätte sich der TO 
eine Menge Schreibarbeit und Zeit ersparen können, wenn er das relevante 
Kapitel gelesen hätte. Ich habe auch nur deswegen ein zweites Mal in 
diesem thread darauf verwiesen, weil viele in der Zwischenzeit 
aufgekommenen Punkte dort ebenfalls behandelt werden. Aber gut: Lasse 
ich eben in Zukunft die Beteiligung an allen threads sein, in denen ich 
Wissen beisteuern könnte, das aus dem Buch (oder Anderen Quellen) 
schneller und effizienter erworben werden kann.

Was "der Inhalt wert ist," kann nur jeder Leser/jede Leserin für sich 
selbst beantworten, das ist die Definition eines Buches.

: Bearbeitet durch User
Autor: Karl (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Ruediger A. schrieb:
> In sofern ist zumindestens die Erwähnung dieses Unterschiedes relevant
> für Jemanden, der sich für Zylen interessiert.

Da hast du ohne Zweifel Recht.

Ruediger A. schrieb:
> Meintest Du das genau so wie Du es geschrieben hast?

Bei nochmaligem lesen natürlich nicht. Danke für den Hinweis. Ich 
meinte, dass jeder SRAM in diesem konkreten Controller 0 waitstates hat. 
Extern oder gar dram oder andere Controller können da gaaaanz anders 
aussehen.

Ruediger A. schrieb:
>> Idealerweise liegt der Stack im ccm.
>
> In so einer Anwendung vermutlich schon, aber generell ist die
> Entscheidung darüber, welcher Speicherbereich auf welches Modul
> abgebildet werden sollte, abhängig von der Anwendung.

Ja, klar. Ccm hat halt den Vorteil, dass bei diesem Controller sonst 
niemand darauf Zugriff hat und dementsprechend auf dem Stack keine 
Konkurrenz entstünde.

Ruediger A. schrieb:
> Was die unterschiedliche Zyklenzahl der Befehle angeht, so hast Du zwar
> recht, was das Verhältnis Befehle<->Zyklen angeht, aber das ist ein
> konstanter Verzerrungsfaktor.

Hm. Ich muss normalerweise nicht auf dieses extreme Niveau der 
Optimierung herab aber ich lese bzw überfliege gern einmal das Manual 
bevor ich für einen Controller programmiere. War es nicht so, dass bei 
thumb2 nicht immer alles in 16 Bit codiert werden kann und deshalb 
manche Befehle abhängig von den Daten in 32 Bit codiert werden? Weiter 
meine ich mich zu erinnern dass ein div abhängig von den konkret zu 
bearbeitenden Daten unterschiedlich lange braucht.

Ruediger A. schrieb:
>> PS: der ständige Verweis auf dein Buch macht deine Beiträge imho weniger
>> sympathisch als es der Inhalt Wert wäre.
>
> Nach Bestem...

Ich meinte das nicht so böse. Sorry.
Offensichtlich hast du Ahnung und wahrscheinlich ist dein Buch auch 
dementsprechend gut.
Ich meine auch dass deine Beiträge hier gut sind. Es klingt nur in 
meinen Ohren ein bisschen wie "hättest du Mal mein Buch gelesen". Alles 
imho wie gesagt. Und lass dich bitte nicht davon abhalten hier zu 
schreiben. Eher höre ich auf, weil Ahnung hast du sicher mehr.

Autor: Ruediger Asche (Firma: keine) (rac)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Karl schrieb:
> Ruediger A. schrieb:
>
> Eher höre ich auf, weil Ahnung hast du sicher mehr.

Neee, bloss nicht! Wenn ich "mehr Ahnung" hätte, dann sicher nur in 
manchen speziellen Teilaspekten, und auch nur deswegen, weil ich (im 
Zusammenhang mit dem B...Projekt) verstärkt in den Bereichen 
recherchiert habe. Ansonsten bin ich mir sicher, dass wir uns 
gegenseitig viel in brainstorms helfen könnten und würden, wenn wir 
zusammen schaffen täten. Denn darum geht es ja am Ende des Tages, 
gemeinsam die beste Lösung für ein gegebenes Projekt hervorzubringen. 
Sich gegenseitig outzunerden war noch nie mein kink. Auf Augenhöhe in 
jeder Tiefe mit Anderen Techiebegeisterten über Dinge zu kommunizieren, 
die Spass machen, schon.

Aber die Nachricht ist angekommen, ich versuche mich mit den Hinweisen 
auf das ...ding... zu beschränken, Danke.

Autor: Christopher S. (shalec)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
> Aber die Nachricht ist angekommen, ich versuche mich mit den Hinweisen
> auf das ...ding... zu beschränken, Danke.

Ich fand den Hinweis auf das Buch schon ganz gut. Ich hätte dem dann nur 
wesentlich früher mit mehr Wissen nachgehen sollen. Aktuell sind noch 
~13 Tage Zeit, bis zur Abgabe und solche Kleinigkeiten halten dann schon 
etwas auf.

Ich würde es mir sogar bestellen oder aus der Bib ausleihen, wenn mir 
mehr Zeit zur Verfügung stehen würde, jedoch möchte ich gar nicht noch 
mehr Zeit dafür haben. :)

Kurz zu mir: Ich bin absoluter Neuling in C und der Programmiererwelt. 
Ich habe keine Ahnung von Architekturen, Netzwerken (ich würde die 
Verbindungen innerhalb eines Boards und Prozessors irgendwie als 
Netzwerk betrachten) und anderen Dingen, die man durch Erfahrungen 
erlernt. Mittlerweile kann ich ein wenig ASM (jedoch für PIC18, M4 wird 
nicht gaaanz anders sein), C und Compilerkrams. So ganz überblicken kann 
ich die ganzen Optionen noch nicht, dafür sind es einfach zu viele.

Ich hatte gehofft, dass es ein "Erfahrungswissen" zum compiler gibt. Ich 
nutze übrigens die Version "6.3.1 20170215" vom arm-none-eabi-gcc 
Crosscompiler auf Windows und als "Entwicklungsumgebung" das gute alte 
Notepad++.

Für mich war es am Anfang sehr schwer, überhaupt eine LED auf dem Ding 
blinken zu lassen. Mittlerweile bekomme ich Outputs via USART, jedoch 
bin ich auch da nur über Ubuntu in der Lage den Kram zu "überwachen". 
Bei Windows schien mir der zeitliche Aufwand als unangemessen, einen 
USART-Watcher einzurichten. Bei Ubuntu sind es nur ein paar Zeilen 
Bash-Code.

Am Anfang meiner Arbeit hatte ich die Wahl zwischen dem Cortex M0 und 
dem M4. Ich bin froh, mich für den M4 entschieden zu haben, da ich so 
keine Probleme mit dem RAM erwarten brauche. Einige Teile, die ich 
zwischengeneriere oder als externe Konstanten vorliegen habe (Primzahl, 
Generatoren, ...) verbrauchen doch schon an einigen Stellen mehr, als 
der M0 hat, aber wesentlich weniger, als der M4 bietet. Noch habe ich 
keine LUTs implementiert, ich wüsste auch an keiner Stelle, wie mir 
diese helfen sollten - bis auf der Skalarmultiplikation. Das würde dann 
nochmal Flash und ggf. etwas RAM-Speicher verbrauchen. Aber auch dann, 
bin ich noch lange nicht am Limit.

Mir fehlen, um wirklich effizient zu programmieren, Erfahrungen über 
Verbindungen (Geschwindigkeiten), Speicherverwaltungen, verschiedene 
Herangehensweisen exakt das gleiche zu programmieren, jedoch mit 
unterschiedlicher Effizienz. Beispiel: Ich arbeite viel mit Arrays, ich 
hätte aber auch direkt Pointer initialisieren und entsprechend Speicher 
allokieren können. Ein 8-Bit-Shift könnte durch ein verschieben des 
Pointers realisiert werden (wesentlich effizienter als shiften und 
"kleben"), jedoch müsste ich dann doppelt so viel Speicher bereit 
stellen und mit 0 initialisieren, als nötig, damit ich auch sicher sein 
kann, dass am Ende eine 0 steht. Betrachte ich left-und rightshifts 
müsste ich sogar 3x so viel Speicher reservieren. Also blöde Idee. :)

Nach dem Manual von ARM sind Shifts immer gleich teuer (1cycle) egal, ob 
right- oder leftshift.

Naja..so viel zu "kurz" :D

Ich habe z.B. keine Erfahrungen in C, auf die ich zurückgreifen kann, um 
zu Wissen, dass Funktionsaufrufe nicht kostenfrei sind. Auch bin ich 
nicht in der Lage mir zu erklären, wie der Cycleunterschied zustande 
kommt, bei dem memcpy Beispiel. Da hatte ich ja auch Ergebnisse 
unterschiedlichster Art: memcpy direkt: 30c, als makro: 38c, in einer 
Funktion 60+c.
Auch dachte ich, dass die effizienteste Methode zum "kopieren" eine 
for-Schleife mit "A[i]=B[i]" wäre. Tests haben mir das Gegenteil gezeigt 
:( Insgesamt war ich in der Lage knapp 30k Cycles bei einer 
Polynomdivision (n^2 + [2](n-1)^2 cycles, von ursprünglich [4]) mit 
anschließender Reduktion (von 106k auf 78k cycles) einzusparen.

Ich bin jedoch der Meinung, dass 78k Cycles unnötig viele sind. Da hier 
einfach ewig geshiftet wird und jeder Shift eben 90-96c kostet. Daher 
sah ich nur drei Ansätze: reduziere die notwendige Anzahl an Shifts, 
ersetze einige Shifts durch andere Operationen und verbessere das 
Shiften.

Ich denke, dass viel durch den Compiler bei der Übersetzung vermurkst 
wird, da die Schleifen wesentlich günstiger sein sollten.

Autor: Ruediger Asche (Firma: keine) (rac)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Btw, vielleicht hilft das Folgende ja zur Beantwortung der originalen 
Frage (dein ursprüngliches Codefragment ist ja die Standard 
Implementation von ROTATE mit Hilfe von Shifts):

https://stackoverflow.com/questions/31387778/near-...

Autor: Christopher S. (shalec)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ruediger A. schrieb:
> Btw, vielleicht hilft das Folgende ja zur Beantwortung der originalen
> Frage (dein ursprüngliches Codefragment ist ja die Standard
> Implementation von ROTATE mit Hilfe von Shifts):
>
> 
https://stackoverflow.com/questions/31387778/near-...

Oh cool. Soweit ich das sehe, hat er ganz am Ende sogar meinen 
praktischen Ansatz und sagt dazu, dass GCC daraus langsamen Code 
produziert. Er verlinkt auch auf diesen Beitrag:
https://blog.regehr.org/archives/1063

Darin wird durch den Trick "32-n" == "-n&31" (also -n mod 32) optimiert. 
Daran hätte ich so erstmal nicht gedacht.

Ich verstehe nur folgendes nicht so ganz. Es wird definiert:
 const unsigned int mask = (CHAR_BIT*sizeof(x)-1);  // e.g. 31 
(Gefunden habe ich dazu "CHAR_BIT is the number of bits in char", damit 
ist CHAR_BIT = 4.)
und verwendet:
n&= mask;

Wenn ich das richtig verstehe, skaliere ich darüber das übergebene n auf 
einen Wert zwischen 0 und 31. Wenn ich aber als Programmierer darauf 
achte, dass kein Wert größer als 31 wird, weiß der Compiler das 
vermutlich zur compile-time nicht und kann deshalb nicht optimieren. 
Sehe ich das richtig? Ich könnte hier doch auf "mask" verzichten und 
direkt "n&=31" machen?

Autor: Oliver S. (oliverso)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Christopher S. schrieb:
> Ich denke, dass viel durch den Compiler bei der Übersetzung vermurkst
> wird, da die Schleifen wesentlich günstiger sein sollten.

Das ist das einzige, was mit Sicherheit nicht passiert.

Ansonsten hab ich ein paar Fragen:
Woher weißt du, daß dein Code zu langsam ist?
Wie schnell müsste er sein?

Brauchst du bei dem left Shift alle 340 Zwischenergenisse, oder nur 
bestimmte?

Oliver

Autor: Christopher S. (shalec)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich brauche praktisch nur das Ergebnis, dass an Stelle 341 eine 1 steht. 
Mehr soll dieser Leftshift nicht machen. Eine "Optimierung" (Abstand vom 
MSB zu 341 und Leftshift um diese Anzahl) hat die Laufzeit verdreifacht.

Das große Ziel ist: Ein Pairing durchzuführen in unter 46 ms (aktueller 
Durchschnitt). Dazu werden Cycles der einzelnen OP angegeben. Leider 
decken die sich so gar nicht mit meiner Reduktion.

Es werden 32k Multiplikationen durchgeführt in 46ms auf vergleichbarer 
Hardware. Eine kostet bei mir 78k cycles. Es sind also 2,496 * 10^{9} 
cycles notwendig. Sollte ich richtig liegen, entsprechen 168 MHz dem 
durchlauf von 168*10^6 Cycles pro Sekunde. Damit würde ich auf 
rechnerisch 2496/168 = 14 Sekunden kommen. Das halte ich für zu lange, 
im Vergleich.

Autor: Ruediger Asche (Firma: keine) (rac)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Christopher S. schrieb:
>
> Das große Ziel ist: Ein Pairing durchzuführen in unter 46 ms (aktueller
> Durchschnitt). Dazu werden Cycles der einzelnen OP angegeben. Leider
> decken die sich so gar nicht mit meiner Reduktion.
>

Also das ist jetzt mein letzter Beitrag in diesem thread.

Du hast Dich irgendwie gehirnmässig darin festgebissen, dass Du deinen 
shift eines 340 bit grossen Wertes mit Gedeih und Verderb über 32 bit 
weise Rotates (die in C/C++ ja mit doppelten shifts simuliert werden 
müssen) implementieren musst.

Wie bereits gesagt: Du kommst komplett ohne shifting aus, wenn Du Bit 
Banding benutzt. Dann brauchst Du lediglich in einer Schleife den 32bit 
Wert des Aliases (per Def. immer 0 oder 1) von jedem Bit um x (= Anzahl 
der zu shiftenden bits) Arraypositionen umzukopieren, fertig. Dann noch 
ggf. die restlichen bits hinten ausnullen, entweder auf der 
Originalposition oder in den Aliases. Würde mich nicht wundern, wenn 
damit plötzlich die Zyklenzahl gen vernachlässigbar geht.

Das Codieren erspart Dir aber Niemand dabei.

Autor: Markus F. (mfro)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Ruediger A. schrieb:
> (die in C/C++ ja mit doppelten shifts simuliert werden
> müssen) implementieren musst.

Das ist zwar richtig, aber auch wieder nicht. arm-none-eabi-gcc ist 
beispielsweise durchaus in der Lage
(x << n) | (x >> ((-n) & 31))

als das zu erkennen, was es ist und macht ein "ror" draus.

Autor: Christopher S. (shalec)
Datum:

Bewertung
-1 lesenswert
nicht lesenswert
Also ich gucke mir 
http://infocenter.arm.com/help/index.jsp?topic=/co... 
(bzw. die pdf) an.

Bevor ich das genau nachlese, ist mir noch was aufgefallen. Ich nutze 
die Arrays ja, um sehr große Zahlen darzustellen. D.h. Zahlen bis 
352-Bits, bzw. bis 704 Bits. Dabei wird eine Zahl entsprechend zerlegt:

A = A[0] B^0 + ... + A[n] B^n

B ist dabei 2^32
n = 10.

Eine solche Zahl hat bei mir immer höchstens 340 Bits.

Ein sehr viel größerer Array kann nur bei der Multiplikation entstehen. 
Dort habe ich dann für zwei Zahlen a,b, mit obiger Darstellung

c = a*b = C1 . C0
mit lsb(c) = C0 und msb(c)=C1

Dieses Produkt hat höchstens 680 Bits + einen Überlauf wegen der 
Darstellung.

Die Reduktion zerlegt dann diese beiden (C0 und C1) in maximal drei 
Arrays, mit jeweils 340 Bits gesetzt. Nennen wir die drei Arrays G[2] 
bis G[0].

Es kann sein, dass G[2] = 0 oder G[2] != 0. Im zweiten Fall sind dann 
hier jedoch nur die Bits das Überlaufs drin, d.h. wenn a[10]*b[10] + 
carry mehr als 32-Bits belegt.

Wie man sich nun vorstellen kann, ist der Überlauf maximal 32-Bits groß, 
im Allgemeinen jedoch kleiner.

Der Algorithmus sieht vor, dass man die Zahl so lange shiftet, bis sie 
341 Bits hat. Erst wenn das 341. Bit gesetzt ist, wird eine Operation 
ausgeführt. Jedoch werden dabei maximal (es müssen tatsächlich exakt) 
340 Shifts überhaupt durchgeführt. Damit man eine Vorstellung von der 
Operation hat, die bei "bit_341_gesetzt()" ausgeführt wird:
while(Bit_341_gesetzt(G[N])){
    Bit_341(G[N])=0;
    G[N] += (2^{340} mod p)
}

sind die 340 Runden rum, wird N -=1 gesetzt und mit G[1] der gleiche 
Krams betrieben. G[1] ergibt sich jedoch aus der Ausgabe der 340-Runden 
verrechnet mit den Werten in G[1].

Bei G[0] findet nur eine Verrechnung mit G[1] statt und anschließend 
eine sukzessive Reduktion um p. Dieser Algo ist praktisch eine Mischung 
aus der Barrett und Montgomery Reduktion.

Autor: Oliver S. (oliverso)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Christopher S. schrieb:
> Eine "Optimierung" (Abstand vom
> MSB zu 341 und Leftshift um diese Anzahl) hat die Laufzeit verdreifacht.

Zeig doch mal den Code.

Oliver

Autor: Ruediger Asche (Firma: keine) (rac)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Ruediger A. schrieb:
>
> Also das ist jetzt mein letzter Beitrag in diesem thread.
>

Leider schon verloren - Memo an mich selbst: ERST Nachdenken oder 
ausprobieren, DANN posten!

>
> Wie bereits gesagt: Du kommst komplett ohne shifting aus, wenn Du Bit
> Banding benutzt. Dann brauchst Du lediglich in einer Schleife den 32bit
> Wert des Aliases (per Def. immer 0 oder 1) von jedem Bit um x (= Anzahl
> der zu shiftenden bits) Arraypositionen umzukopieren, fertig. Dann noch
> ggf. die restlichen bits hinten ausnullen, entweder auf der
> Originalposition oder in den Aliases. Würde mich nicht wundern, wenn
> damit plötzlich die Zyklenzahl gen vernachlässigbar geht.
>

Die Aussage meinerseits ist natürlich völliger Unfug. Wenn man auf Bits 
statt Bytes arbeitet, fallen im worst case 32* soviel 
Schleifendurchläufe an. Haben meine Tests gestern Abend ziemlich genau 
bestätigt... sorry for the noise.

Der Einzige Vorteil von Bitbanding ist, dass man dabei beliebig grosse 
Shiftgrössen (also auch >32) ohne Codeänderungen machen kann.


> Das Codieren erspart Dir aber Niemand dabei.

Dabei bleibe ich aber... ;-)

Autor: Ruediger Asche (Firma: keine) (rac)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Markus F. schrieb:
> Ruediger A. schrieb:
>> (die in C/C++ ja mit doppelten shifts simuliert werden
>> müssen) implementieren musst.
>
> Das ist zwar richtig, aber auch wieder nicht. arm-none-eabi-gcc ist
> beispielsweise durchaus in der Lage
>
>
> (x << n) | (x >> ((-n) & 31))
> 
>
> als das zu erkennen, was es ist und macht ein "ror" draus.

Mit welchen Optimierungsstufen hast Du das probiert? Mit gcc 4.7.4 und 
-Ofast ist im Disassembly Output nichts von einer rotate Operation zu 
sehen?

Autor: Markus F. (mfro)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ruediger A. schrieb:
> Mit welchen Optimierungsstufen hast Du das probiert? Mit gcc 4.7.4 und
> -Ofast ist im Disassembly Output nichts von einer rotate Operation zu
> sehen?

arm-none-eabi-gcc 5.4.1 -O2

Ist nicht das Neueste, aber was Du da hast ist schon ziemlich 
antiquarisch...

Autor: Ruediger Asche (Firma: keine) (rac)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Markus F. schrieb:
> Ruediger A. schrieb:
>> Mit welchen Optimierungsstufen hast Du das probiert? Mit gcc 4.7.4 und
>> -Ofast ist im Disassembly Output nichts von einer rotate Operation zu
>> sehen?
>
> arm-none-eabi-gcc 5.4.1 -O2
>

Danke.

> Ist nicht das Neueste, aber was Du da hast ist schon ziemlich
> antiquarisch...

yo, aber das ist womit WinIdeaOpen (letzte releaste Version) shippt.

In 4.7.4 Version ist auch mit -O2 nichts von ror zu sehen. Wenn ich mal 
ein paar Zyklen Zeit habe (beabsichtugtes Wortspiel! ;-)) versuche ich 
mal eine neuere Version mit WinIdeaOpen zum Laufen zu kriegen und etwas 
zu experimentieren, um empirisch zu ermitteln wieviel wir dabei genau 
gewinnen.

Autor: Christopher S. (shalec)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Erstmal ist es schön, dass der Thread noch lebt.
Mit dem Bitbanding habe ich auch ein wenig anders gedacht, als erklärt. 
Im Prinzip ist ein Shift ja nichts anderes, als das Abschneiden der 
oberen n Plätze und von unten durch 0 ergänzen.
Ich bin mit dem Bitbanding noch nicht so ganz warm, zumal dafür der 
1MB-Array (der ist kleiner.. ;) ) im richtigen Speicher liegen muss.
Dann würde ich mir tatsächlich das ganze geshifte ersparen und exakt das 
erste Bit ansteuern und von dort aus entsprechend genug Bytes kopieren, 
sowie die fehlenden 0-3 Bits einsetzen. Dadurch muss ich nicht die 
Funktion durchrangeln, sondern kann etwas präziser arbeiten. Ob das 
cycles spart, sei dahin gestellt. Ich weiß nämlich auch nicht genau, wie 
"optimal" memcpy auf dem M4 arbeitet und was der Compiler daraus macht. 
Interessanterweise haben sowohl Compiler, µC als auch C (string.h) die 
Funktion "memcpy" parat.

Was meint ihr, welche arbeitet wie eingesetzt schneller um 44 Byte zu 
kopieren?

Zur Unterscheidung: string_memcpy vs. gcc_memcpy vs. m4_memcpy.

Noch eine letzte Frage zum Thema "Geschwindigkeit von memcpy": Warum 
brauche ich doppelt so viele cycles, wenn ich memcpy nochmal extra in 
einer weiteren Funktion verpacke?

D.h. warum liegt
arrcpy(uint32_t A[11], uint32_t B[11])
{ //A <- B
    memcpy(A,B,44);
}
bei 60 cycles, als makro
#define arrcpy2(A,B) (memcpy(A,B,44);)
bei 38 cycles und der direkte Aufruf
memcpy(A,B,44);
bei 30 cycles?

Sollte ich sowas lieber in einen extra Thread verpacken?


Zum Leftshift: Ich denke nicht, dass diese Codezeile wirklich eine 
rot-Instruction aufrufen würde
(x << n) | (x >> ((-n) & 31))

Ein kleiner Nachtrag noch zum Bitbanding
Angenommen ich möchte einen leftshift um 31-Bit realisieren. Da mein 
Array nur 44 Byte verbraucht und ich genau einen MB mit Bitbanding 
adressieren kann, würde ich direkt beim "rüber kopieren" in diesen 
Speicherbereich 44*3 Byte reservieren und mit 0 initialisieren. Dann 
muss ich nur den "Zeiger" auf den Anfang um diese 31-Bit reduzieren und 
ab da an die vollen 44 Byte zurück kopieren. (Das geht natürlich auch 
für beliebig große Shifts)
Am Ende sollte man jedoch sicher sein, dass die geänderten Bits wieder 
alle auf 0 gestellt werden.

Wenn ich das mit dem Bitbanding richtig verstanden habe, sind 32-MB 
"Zeiger" auf die einzelnen Bits vorhanden. Demnach müsste eine Operation 
auf solch einen Zeiger (Addition oder Subtraktion) entsprechend um diese 
Anzahl an Bits weitergehen, oder irre ich mich? Also die Adressierung 
sollte doch linear erfolgen.


Wie schnell das ist: Keine Ahnung,
wie ich dem Compiler mitteile, dass genau dieser Kram nun in diesen 
Speicherbereich verschoben wird: Ebenfalls keine Ahnung.
Wie ich mit dem Bitbanding arbeite.. naja, siehe die zwei Aussagen 
zuvor. Das müsste ich mir noch alles beibringen.

Mit dem Bitbanding ließe sich auch jedes einzelne Bit der Reihe nach 
testen und erst dann shiften.

: Bearbeitet durch User
Autor: Ruediger Asche (Firma: keine) (rac)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
sigh

Ich glaube nicht, dass Du BitBanding richtig verstanden hast. Du 
brauchst dafür nichts zu kopieren, zu initialisieren oder sonst 
irgendwelche Magie. Der Cortex Kern stellt schlicht und einfach nur 2 
identische Kopien jedes Bits von 0x20000000-0x21000000 (oder wieviel 
immer im gegebenen POD realisiert ist) zur Verfügung - einmal in einem 
Long verpackt, einmal mit 31 0 gepadded in einer Anderen Speicherstelle 
(0x22000000+), nach einer festen Formel aufeinander abbildbar. Da 
brauchst Du überhaupt nix zu tun; eine Änderung an der einen Stelle wird 
automatisch auf die Andere übernommen.

Ein Shift auf einem Bitband Array ist ein Nobrainer; einfach nur die 
Aliasregion als (unsigned long *) umcasten und (natürlich richtig rum) 
in einer Schleife jeden betroffenen Eintrag im Array um x Stellen 
verschieben. Keinerlei Magie bzgl. Bitpopeln nötig.

Allerdings wie gesagt: Effizienz kannst Du in die Tonne treten. Ich habe 
es mal ausgemessen. Macht auch Sinn: 32 Verschiebungen sind IMMER mehr 
Zyklen als ein Rotate und das Weiterschieben des Shiftrestes, und zwar 
signifikant mehr.

Nochmals Bitte um Entschuldigung, dass ich Dich auf die falsche Fährte 
gelockt habe (zumindestens was Effizienz angeht. Codierung ist 
WESENTLICH einfacher mit Bit Banding, speziell wenn Du Shiftgrössen > 31 
berücksichtigen musst, die werden recht umständlich bei der ror 
Simulation).

: Bearbeitet durch User
Autor: Marcus Harnisch (mharnisch) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich weiß, mein Vorschlag klingt extrem langweilig, aber hast Du schon 
mal eine der zahlreichen Arbitrary Precision Math Bibliotheken 
angesehen? Die sind oft stark optimiert und enthalten üblicherweise auch 
Shift Funktionen.

Autor: Markus F. (mfro)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
Christopher S. schrieb:
> Zum Leftshift: Ich denke nicht, dass diese Codezeile wirklich eine
> rot-Instruction aufrufen würde(x << n) | (x >> ((-n) & 31))

Nun, glauben ist beim Programmieren immer gaaanz schlecht, da hilft nur 
wissen::
unsigned int rotate_left(unsigned int value, const unsigned int amount)
{
        return (value << amount) | (value >> ((-amount) & 31));
}
Disassembly of section .text:

00000000 <rotate_left>:
   0:  e2611020   rsb  r1, r1, #32
   4:  e1a00170   ror  r0, r0, r1
   8:  e12fff1e   bx  lr

Das macht der Compiler allerdings nur, wenn die Optimierungsstufe >= -O1 
ist.

Autor: Ruediger Asche (Firma: keine) (rac)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Markus F. schrieb:
> Christopher S. schrieb:
>> Zum Leftshift: Ich denke nicht, dass diese Codezeile wirklich eine
>> rot-Instruction aufrufen würde(x << n) | (x >> ((-n) & 31))
>
> Nun, glauben ist beim Programmieren immer gaaanz schlecht, da hilft nur
> wissen::
>
>
> unsigned int rotate_left(unsigned int value, const unsigned int amount)
> {
>         return (value << amount) | (value >> ((-amount) & 31));
> }
> 
>
>
> Disassembly of section .text:
> 
> 00000000 <rotate_left>:
>    0:  e2611020   rsb  r1, r1, #32
>    4:  e1a00170   ror  r0, r0, r1
>    8:  e12fff1e   bx  lr
> 
>
> Das macht der Compiler allerdings nur, wenn die Optimierungsstufe >= -O1
> ist.

Das ist korrekt, hat aber (wie ich beim Austesten gerade festgestellt 
habe) keine Relevanz für die Problemstellung... Der Originalcode sieht 
nämlich so aus:
A[i] = ( ( A[i]<< count ) | ( A[i-1]>> (32-count) ) );

Es geht also darum, die Fragmente der Rotierung aus zwei verschiedenen 
32-bit Werten (nämlich A[i] und A[i-1]) zusammenzubauen. Das ist aber 
etwas Anderes, als einen 32 Bit Wert in sich zu rotieren. Mglw. lässt 
sich die Optimierung immer noch verwenden, dann muss aber der 
Algorithums umgeschrieben werden.

Autor: Christopher S. (shalec)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Wie würde ich denn diese Funktion in ASM schreiben? Reduzieren wir das 
mal auf den einfachen Fall:

Ich habe A und B und möchte von A . B einen Leftshift um 13 Bit 
durchführen. Leftshift ist für Cortex M4 so definiert:
LSL Rd, Rn, #13
 (ich habe die Anzahl bereits eingefügt. Im Prinzip sind es doch 
folgende notwendige Instruktionen: Leftshift, Rightshift, OR, Speichern. 
Oder sehe ich das falsch?

Autor: Marcus Harnisch (mharnisch) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Du wirst da mit Assembler auch nicht viel weiter kommen. Pro Wort werden 
drei arithmetische Operationen ausgeführt. Die Werte müssen aus dem 
Speicher geladen, und das Ergebnis zurückgespeichert werden. Dann gibt 
es einen Schleifenzähler und den dazugehörigen bedingten Sprung. Da bist 
Du überschlagsmäßig (ohne loop-unrolling) schon bei 8-9 Takten pro Wort. 
Dein Array besteht aus 11 Worten, womit die 90 Takte, die Du beobachtet 
hast schon mal passen.

Mit loop-unrolling kannst Du unter anderem das redundante Laden des A[i] 
sparen, da das ja schon in der vorherigen Iteration als A[i-1] geladen 
wurde.

Überlass es dem Compiler.

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Schon mal an GMP gedacht?

https://gmplib.org/

Schau mal in den Quellen, wie mpn implmentiert ist (das "n" steht für 
"Natürliche Zahlen").  Die Basisfunktionen sind da fein säuberlich in 
ASSEMBLER impementiert, wobei für ARM jeweils folgende Varianten 
ausgetextet sind:
arm/neon
arm/v5
arm/v6
arm/v6t2
arm/v7a/corea15/neon
arm/v7a/core7
arm/v7a/core8
arm/v7a/core9
arm64

Um das besser als in Assembler und stabiler als GMP hinzubekommen, 
brauchst schon ne Zeit...

Die GMP gibt's als old school C und via C++ Interface.

Zu Loop-Unrolling:

Ein zweischneidiges Schwert, das durchaus nach hinten losgehen kann: 
Falls durch die langen Instruktionssequenzen ständig das 
Instruction-Cache leer läuft, ist man mit einer kleinen Schleife, die 
zwar mehr Befehler enthält, aber nicht ständig Cache-Misses erzeugt, 
u.U. besser bedient.  Dies ist abhängig von der verwendeten Hardware und 
der Memory- und Cache-Konfiguration.  Ob es für ARM eine Rolle spielt, 
kann ich nicht sagen.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.