Ankündigung

Einklappen
Keine Ankündigung bisher.

cycles zählen

Einklappen

Neue Werbung 2019

Einklappen
X
  • Filter
  • Zeit
  • Anzeigen
Alles löschen
neue Beiträge

  • cycles zählen

    Hallo allerseits,
    gibt es eine allgemein genutzte Methode um Rechenoperationen (cycles) auszuzählen?

    Es geht bei mir um folgendes: Ich arbeite derzeit mit einem ARM Cortex M4 Prozessor @168MHz und muss ein paar Funktionen in C programmieren. Dazu möchte ich aber bei einigen Berechnungen Vorbetrachtungen implementieren und herausfinden, ob meine Vorbetrachtungen wirklich effizienter sind. Um darüber eine Entscheidung zu treffen, würde ich einfach beide Methoden implementieren und entsprechend die Cycles vergleichen.

    Kleines Beispiel: Was ist schneller zu berechnen:
    p6-1 oder (p2-1)*(p2(p2+1)+1)

    Der Square-and-Multiply Algorithmus liefert für 610= 1102 die Operationen: SMSM (S quadrieren, M multiplizieren):
    Initialisierung mit 1:

    p6-1=(((12)*p)2*p)2 -1
    Ich habe also 4 Multiplikationen (M) und eine Addition (A) (bei 168 MHz ist das wie teuer? ) bzw. wenn ich 1^2 ignoriere, erhalte ich 3 M und 1A.

    Andererseits berechne ich nur x:=p2 und kann diesen Wert entsprechend auslesen.
    (p2-1)*(p2(p2+1)+1) = (x-1)(x(x+1)+1)
    Ich habe also für x, x2 und das Verrechnen der Klammern jeweils eine Multiplikation = 2
    hinzu kommen 3 Additionen.

    Insgesamt kann ich aber auch die erste Methode dadurch verbessern, indem ich p2 in einem LUT speichere. Dadurch reduziert sich SQM zu: (x*p)2 -1, also 2 M, 1 A und ist damit günstiger.

    Ich gehe davon aus, dass eine M weniger teuer ist, als 2A, daher wäre die Vorbetrachtung günstiger (im Trad-of mit Speicher). Btw. p wird zwischen 256 und 521 Bit groß sein.

    Aber es gibt ja auch andere Methoden, wie die Sliding Window Methode, oder Montgomery Ladder..[1] (ich operiere letztendlich in einem endlichen Körper der Charakteristik p und Ordnung p^n-1 (F_q mit q=p^n)


    [1] https://en.wikipedia.org/wiki/Expone..._window_method

  • #2
    Kommt darauf an™
    Es ist immer etwas schwierig, bei einer Stromspar-CPU Cycles in Zeit umzurechnen. Aber wenn du wissen willst, was die wenigsten Zyklen verbraucht, dann kannst du dir den ASM-Code anschauen, den dein C-Source erzeugt.

    Du dabei musst im Grunde (mindestens) vier Faktoren berücksichtigen:
    • Gibt es eine direkte Unterstützung deiner Operation durch die CPU (= Instruction Set)?
    • Was für einen Compiler verwendest du? Heißt, wenn dein Compiler einen ARM Cortex M4 versteht und targeten kann, dann kann es sein, dass gewisse Operationen effizienter gelöst werden. Ggf gibt es schon eine Schablone, die einen effektiven Berechnungsweg findet. Bei X86 gibt es FYL2X was grob B*log2(E) entspricht.
    • Was für eine Architektur (32/64bit; soweit ich weiß, ist der ARM M4 ein 32er)?
    • Was für ein Datentyp hat p?
    Ich bin mit der Architektur eines ARM M4 nicht wirklich vertraut!

    Mit dem GCC5.4 für ARM64 hätte ich dann bei folgendem Code...

    PHP-Code:
    int calc1(int p) {
      return 
    pow(p6) - 1;
    }

    int calc2(int p) {
      return (
    pow(p,2)-1)*(pow(p,2)*(pow(p,2)+1)+1);
    }

    int calc3(int p) {
      return 
    p*p*p*p*p*p-1;

    ... folgenden Output...

    PHP-Code:
    calc1(int):
            
    stp     x29x30, [sp, -32]!
            
    add     x29sp0
            str     w0
    , [x2928]
            
    ldr     w0, [x2928]
            
    scvtf   d0w0
            fmov    d1
    6.0e+0
            bl      pow
            fmov    d1
    d0
            fmov    d0
    1.0e+0
            fsub    d0
    d1d0
            fcvtzs  w0
    d0
            ldp     x29
    x30, [sp], 32
            ret
    calc2
    (int):
            
    stp     x29x30, [sp, -48]!
            
    add     x29sp0
            stp     d8
    d9, [sp16]
            
    str     w0, [x2944]
            
    ldr     w0, [x2944]
            
    scvtf   d0w0
            fmov    d1
    2.0e+0
            bl      pow
            fmov    d1
    d0
            fmov    d0
    1.0e+0
            fsub    d8
    d1d0
            ldr     w0
    , [x2944]
            
    scvtf   d0w0
            fmov    d1
    2.0e+0
            bl      pow
            fmov    d9
    d0
            ldr     w0
    , [x2944]
            
    scvtf   d0w0
            fmov    d1
    2.0e+0
            bl      pow
            fmov    d1
    d0
            fmov    d0
    1.0e+0
            fadd    d0
    d1d0
            fmul    d1
    d9d0
            fmov    d0
    1.0e+0
            fadd    d0
    d1d0
            fmul    d0
    d8d0
            fcvtzs  w0
    d0
            ldp     d8
    d9, [sp16]
            
    ldp     x29x30, [sp], 48
            ret
    calc3
    (int):
            
    sub     spsp#16
            
    str     w0, [sp12]
            
    ldr     w1, [sp12]
            
    ldr     w0, [sp12]
            
    mul     w1w1w0
            ldr     w0
    , [sp12]
            
    mul     w1w1w0
            ldr     w0
    , [sp12]
            
    mul     w1w1w0
            ldr     w0
    , [sp12]
            
    mul     w1w1w0
            ldr     w0
    , [sp12]
            
    mul     w0w1w0
            sub     w0
    w0#1
            
    add     spsp16
            ret 
    Kein besonders schönes Ergebnis. BTW: Die ersten drei, sowie die letzten zwei Zeilen sind jeweils da, um die Funktion und dessen Parameter in ASM dazustellen.

    Wenn du dann noch mehr über die Cycle-Times einer ARM-CPU wissen willst, sei dir dieser Link ans Herz gelegt: http://infocenter.arm.com/help/index.../I1028171.html

    Und ja, ich habe deine eigentliche Frage damit wohl nicht beantwortet.

    Kommentar


    • #3
      Hey,
      ich muss sagen, dass ich ein absoluter Newbie in der µC (und C Programmierungswelt) bin. Ich habe bislang nur Mathematik studiert und einen kleinen Ausblick in die Informatik genossen. Ich beginne demnächst meine Einarbeitung in den ARM Cortex M4, aber so viel kann ich bereits sagen:
      Der CPU ist ein 32-Bit Prozessor. Es gibt eine ARM Toolchain, die die einzelnen Boards von STM32 unterstützt. (Ich habe hier zwei Boards liegen: STM32F4X mit X in {07, 29}. Der Unterschied ist im Prinzip nur die Größe des Flashspeichers.) Der Datentyp von p ist ebenfalls eine gute Frage. Als Integer oder longint werde ich p nicht speichern können. ( next_prime(2^{512}) ) Daher werde ich vermutlich zur Basis 16 konvertieren müssen und mit Bytes rechnen. Wie ich das in C definiere, weiß ich ebenfalls noch nicht. (Habe in C bislang nur die Grundfunktionen und Syntax gelernt. D.h. Schleifen, Anweisungen, Funktionen, "Klassen")

      Bei deinen Berechnungen oben lässt du aber p^2 häufiger berechnen. Ich hätte p^2 einfach gespeichert und auf den Speicher zurückgegriffen. pow(p,6) sollte man dann besser mit dem Square-and-Multiply Algorithmus machen, wobei ich nicht weiß, wie in C die pow(base,exp) definiert ist.
      Die verbrauchte Zeit ist mir egtl. egal ^^ ich will nur die benötigten Cycles zählen lassen.

      Btw. die Toolchain ist mit dem GCC kompatibel und man kann dann an "gcc test.c" noch Optionen für die Toolchain anhängen und den Prozessor definieren. Das Gute ist: Die Codes sind aufwärts vollständig kompatibel. Werden PINs angesprochen, müssen diese evtl. umdefiniert werden.


      In jedem Fall: Vielen Dank für deine Anregung. Sie hilft mir durchaus

      Kommentar


      • #4
        Zitat von Shalec Beitrag anzeigen
        pow(p,6) sollte man dann besser mit dem Square-and-Multiply Algorithmus machen, wobei ich nicht weiß, wie in C die pow(base,exp) definiert ist.
        pow(base,exp) ist als base^exp definiert. Ich weiß, du meinst die Implementierung, aber die ist nicht festgelegt. Jede C Library bringt ihre eigene Implementierung mit und die ist dann auch für die entsprechenden Plattform optimiert. WENN Square-and-Multiply für die Plattform sinnvoll ist, dann wird das sehr wahrscheinlich auch so implementiert sein.
        Das spielt in deinem Fall aber keine Rolle. Mit Standard C kannst du nicht mit Zahlen im Bereich von 2^512 rechnen. (selbst float kommt nicht annähernd in den Bereich) Dafür brauchst du eine spezielle Library (arbitrary precision mathematics) oder musst die Arithmetik selbst implementieren. Ersteres wird wahrscheinlich auch wieder Square-and-Multiply implementieren, wenn es sinnvoll ist.

        Zitat von Shalec Beitrag anzeigen
        Die verbrauchte Zeit ist mir egtl. egal ^^ ich will nur die benötigten Cycles zählen lassen.
        Das nennt sich Profiling. Mit dem Begriff solltest du bei Google was sinnvolles finden können.

        rkr anhand eines Assembler Listings kannst du in der Regel nicht die Laufzeit abschätzen. Dafür bräuchtest du eine sehr genaue Vorstellung von der Mikroarchitektur und selbst das reicht nicht aus. Sprungvorhersage, Pipeline flushs, Ressourcen Konflikte, Pipeline stalls, Speicherzugriffe und Caches, nicht lineare Ausführung, vorgezogenes lesen in der Pipeline usw. Wahrscheinlich ist der Cortex M4 noch relativ einfach gestrickt, aber auch das wird zum Ausführen im Kopf zuviel des guten sein und weit entfernt von Praxistauglich.

        Kommentar

        Lädt...
        X