Aufgabenstellung
Schnelle Multiplikation in Zp

Die Menge ist ein endlicher Körper für die Operationen + (Addition modulo p) und (Multiplikation modulo p). In dieser Vorlesung beschränken wir uns auf mit . Alle Zahlen in (ganze Zahlen zwischen 0 und ) können dann auf 32-bit Computern mittels int dargestellt werden. In Anwendungen von endlichen Körpern werden Operation wie +, , usw. sehr häufig gebraucht. Es ist naheliegend, diese Operationen so gut wie möglich zu optimieren.

Das Ziel ist es, während der Vorlesung eine möglichst schnelle SPARC Assemblerroutine für die Multiplikation in zu programmieren. Diese Routine soll für den speziellen Fall implementiert und im Laufe der Vorlesung interaktiv optimiert werden.

Nachfolgend wird die Operation definiert und anhand von (nicht optimierten) Referenzimplementationen in C als auch SPARC-Assembler erläutert.

Definition der Multiplikation in , mit

Programm

Referenzimplementation in C

Referenzimplementation in Assembler

Download

Implementation
mit 32Bit Operationen:
Grading

unsigned int pmult(u,v,p) 
   unsigned int u,v,p;
{
   unsigned int u0,u1,v0,v1,w0,w1,wi,wi0,wi1,x0,x1;

   u1=u / 65536; u0=u % 65536;  
   v1=v / 65536; v0=v % 65536;  

   w0=  u0*v0; 
   wi=  u0*v1+u1*v0;
   wi1= wi / 65536; wi0= wi % 65536;
   w1=  u1*v1; 

   x0=(w0 % p + (wi0 * 65536) % p) % p;
   x1=(w1 % p + wi1 % p) % p;
   
   return (x0 + x1 * 2) % p;
}

        .text
        .align 4
        .global pmult
pmult:
        srl %o0,16,%g3
        sethi %hi(65535),%g2
        or %g2,%lo(65535),%g2
        and %o0,%g2,%o0
        srl %o1,16,%o4
        and %o1,%g2,%o1
        smul %o0,%o1,%o3
        smul %o0,%o4,%o0
        smul %g3,%o1,%o1
        add %o0,%o1,%o0
        srl %o0,16,%o1
        and %o0,%g2,%o0
        smul %g3,%o4,%g3
        wr %g0,%g0,%y
        nop
        nop
        nop
        udiv %o3,%o2,%g2
        smul %g2,%o2,%g2
        sub %o3,%g2,%o3
        sll %o0,16,%o0
        wr %g0,%g0,%y
        nop
        ....
pmult.s

pmult32.c
pmult32.s
Implementation mit 64Bit Operationen. Diese Implementation ist nicht 100% korrekt!

Grading

unsigned pmult(u,v,p) 
   unsigned u,v,p;
{
   unsigned long long x;

   x= u * v;
   return x % p; 
}       

        .text
        .align 4
        .global pmult
pmult:
        save %sp,-112,%sp
        mov %i2,%o2
        smul %i0,%i1,%o0
        mov %o0,%o1
        mov 0,%o0
        mov %o2,%o3
        call __urem64,0
        mov 0,%o2
        ret
        restore %g0,%o1,%o0

pmult64.c
pmult64.s

Wichtig: Die optimierten Assemblerprozeduren sollen die gleichen Schnittstelle wie die angegebene Referenzprozedur aufweisen (Funktionsname, Argumentanzahl und -typen, sowie Rückgabetyp identisch). Ausserdem soll die Assemblerprozedur für gegebene Argumente den gleichen Rückgabewert liefern bzw. die gleichen Seiteneffekte aufweisen wie die Referenzimplementationen.

Beachte ausserdem, dass die (konstante) Primzahl bei allen Prozeduren als Argument übergeben wird. Dadurch muss p nicht bei jedem Aufruf neu berechnet oder in einer globalen Variablen gespeichert werden.

Bewertung der Lösungen

Damit wir die Bewertung der Lösungen vollständig automatisieren können, müssen die Programme pmult.c oder pmult.s von den obigen Ausgangsbeispielen abgeleitet sein bzw. das gleiche Interface unterstützen. Die Lösung wird dann gemäss folgendem Schema bewertet:

Die folgende Tabelle zeigt, wieviele Taktzyklen verschiedene SPARC v8 Instruktionen dauern. Es handelt sich um Werte die auf einer UltraSPARC-IIi gemessen wurden. Diese Messungen sind unter anderen Rahmenbedingungen eventuell nicht nachvollziehbar. Dennoch sollten sie einen guten Anhaltspunkt geben.

Ausserdem ist zu beachten, dass UltraSPARC Prozessoren in der Lage sind, gleichzeitig 2 Integer-Operationen pro Zyklus zu verarbeiten. Dies kann aber nur erreicht werden, falls zwischen den Instruktionen keine Abhängigkeiten bestehen.

Zeitdauer von SPARC v8 Instruktionen in Taktzyklen

Instruktion

Anzahl Taktzyklen pro Instruktion

Bemerkung

Arithmetische Instruktionen
(add, sub, and, or, xor, sethi, ...)

1

 

rd %y, reg

5

 

smul, umul

5 - 20

abhängig von den Operanden

sdiv, udiv

38

 

Speicherzugriffe

3 - 12

abhängig davon, ob die Daten vom Cache oder vom Hauptspeicher geladen werden.

Aufruf einer Leaf-Prozedur
(inkl. Rücksprung)

2 - 22

abhängig vom Zustand der Registerwindows, ob Zieladresse zur Zeit des Kompilierens bekannt, usw.

Aufruf einer normalen Prozedur (inkl. Rücksprung)

4 - 24

ditto

Hilfestellung

Distributivität der Modulo-Operation

Für beliebige ganze Zahlen a, b und p gilt

Weitere Tips



Last update: Feb 2002

Author/Hrsg:
Thomas M. Stricker,< <tomstr@inf.ethz.ch>
Christian Kurmann, <kurmann@inf.ethz.ch