/**************/
+ 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*
1
typedefuint32_tarr[11];
2
voidleftshift(arrA,uint8_tcount)
3
for(inti=10;i>0;i--){
4
A[i]=((A[i]<<count)|(A[i-1]>>(32-count)));
5
}
6
A[0]<<=count;
7
}
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*
1
#define CLZ(x) (__builtin_clz(x))
2
...
3
intentry=10,neq=0;
4
while(G[2][entry]==0&&entry>0)entry-=1;
5
neq=CLZ(G[2][entry]);
anhand dieser Ergebnisse "shifte" ich nun Block und Elementweise:
*Alg.3*
1
voidleftshift_blocks(arrA,intblock)
2
{
3
inti;
4
for(i=10;i>=0;i--){
5
A[i]=A[block];
6
if(block==0)break;
7
block-=1;
8
}
9
for(i;i>=0;i--){
10
A[i]=0;
11
}
12
}
13
14
voidleftshift_entry(arrA,intblock,intneq){
15
for(inti=block+1;i>0;i--){
16
A[i]=((A[i]<<count)|(A[i-1]>>(32-count)));
17
}
18
A[0]<<=count;
19
}
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*
1
voidfoo(arrC,arrA){
2
arrG[3]={0};
3
split(C,A,G);
4
/* 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];*/
5
6
/*
7
Optimierter Fall: führe Alg. 2 & 3 aus und setze int N=1
8
nicht opimierter: Beginne mit int N=2;
9
*/
10
while(N--)
11
for(intj=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. :)
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.
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.
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.
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.
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.
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.
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...
1
#include<stdint.h>
2
3
intmain(void)
4
{
5
uint8_tA[5];
6
uint32_tB[5];
7
8
return0;
9
}
A und B sind konstante Pointer, die kannst du gar nicht verschieben,
denn dann wuerdest du den Anfang des Arrays verlieren.
1
*(A+1)=0;// A[1] = 0
2
*(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.
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.
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:
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.
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.
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.
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.
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.
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.
> 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.
constunsignedintmask=(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:
1
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?
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
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.
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.
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
1
(x<<n)|(x>>((-n)&31))
als das zu erkennen, was es ist und macht ein "ror" draus.
Also ich gucke mir
http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc.ddi0439b/Behcjiic.html
(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:
1
while(Bit_341_gesetzt(G[N])){
2
Bit_341(G[N])=0;
3
G[N]+=(2^{340}modp)
4
}
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.
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
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... ;-)
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>>
1
>(x<<n)|(x>>((-n)&31))
2
>
>> 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?
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...
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.
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
1
arrcpy(uint32_tA[11],uint32_tB[11])
2
{//A <- B
3
memcpy(A,B,44);
4
}
bei 60 cycles, als makro
1
#define arrcpy2(A,B) (memcpy(A,B,44);)
bei 38 cycles und der direkte Aufruf
1
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
1
(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.
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).
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.
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::
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::>>
>> 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:
1
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.
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:
1
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?
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.
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:
1
arm/neon
2
arm/v5
3
arm/v6
4
arm/v6t2
5
arm/v7a/corea15/neon
6
arm/v7a/core7
7
arm/v7a/core8
8
arm/v7a/core9
9
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.
Thread beobachten
Seitenaufteilung abschalten