HLS chap3 optim code - people.rennes.inria.frpeople.rennes.inria.fr/Olivier.Sentieys/teach/HLS_chap3_optim_code.pdf · TMS320C54/ T TMS320C62/ TI P roc e su ... • DSP matériel

Synthèse d’architecture et optimisation de code ENSSAT EII/MASTER SISEA - systèmes embarqués

Olivier Sentieys, ENSSAT-IRISA 1

PLAN

1. Optimisations algorithmiques

2. Synthèse architecturale

3. Synthèse logicielle, optimisation de code 1. Compilation et optimisation de code embarqué

2. Optimisation de code 1. Méthodologie 2. Optimisation sur DSP conventionnel 3. Optimisation sur processeur avec parallélisme d’instruction (ILP) Déroulage de boucles Pipeline logiciel EII3/M2R - 2

Compilateur D’un langage de « haut niveau » vers un code

assembleur

Langage 1 C/C++

Langage 2 Fortran

Langage N Java

Fron

t-End

Bac

k-E

nd

IR

Machine 1 ARM

Machine 2 C6x

Machine N C55x

Optimisations Optimisations Optimisations

EII3/M2R - 3

Analyse lexicale

Analyse syntaxique

Analyse sémantique

Génération I.R.

Optimisation I.R.

y = k + 60 * x !

id1= id2+60*id3 !

id1!id2!

id3!

=!+!

*!

60!

Entier Réel!

y id1 réels ….

k id2 réels ….

x id3 réels ….

Table des symboles

id1!

id2!

id3!

=!

+!

*!

60.0!

id1!id2!

id3!

=!+!

*!

60!

Gestion des erreurs

Partie frontale (front-end) But: transformation du code source en une

représentation intermédiaire (IR) • e.g. (C)DFG

EII3/M2R - 4

Partie frontale (front-end) Code source vers un formalisme intermédiaire (e.g.

CDFG) Extraction du parallélisme si il n’est pas explicite dans

le langage Optimisations indépendantes de l’architecture

• Propagation de constantes • Elimination des expressions communes et des invariants • Mise en ligne de fonctions • Déroulage de boucles • ...



EII3/M2R - 5

Begin!! tmp := 0;!

! For i := 1 to N Loop!

! ! tmp := tmp + x(i) * h(i);!

! Endloop;!! y <= tmp;!End;!

Begin

01

y

tmpi

:= :=

loop

i

<h(i) x(i)

+

+

x

AdrAdr

tmp

tmp h x 1 N

endloop

<=

end

Note : On peut séparer graphe de contrôle et graphe de données

CDFG Représentation interne

• Control and Data Flow Graph (CDFG)

EII3/M2R - 6

Extraction de parallélisme

Les fausses dépendances peuvent être cassées grâce à des transformations de code

Deux instructions a et b peuvent être exécutées dans un ordre quelconque (a avant b, b avant a) à condition de ne pas être dépendante l'une de l'autre

expression a : x = m + n; L(a) : ensemble des variables lues dans l'expression 'a' expression b : p = x + n; M(a) : ensemble des variables modifiées par 'a'.

Conditions de Bernstein

'a' et 'b' sont indépendantes si : (1) : M(a) ∩ L(b) = 0 dépendance vraie (2) : L(a) ∩ M(b) = 0 anti-dépendance (ou consommateur-producteur) (3) : M(a) ∩ M(b) = 0 dépendance de sortie (ou producteur-producteur)

Assignation unique des variables : seule la dépendance vraie existe

EII3/M2R - 7

Propagation des constantes

Elimination des expressions communes

Remplacement d'instructions

Avant : j := 4 k := j*2

Après : j := 4 k := 8

Avant : j := b + sinx*b k := (sinx*b)*2

Après : temp := sinx*b j := b + temp k := temp * 2

Avant : Pour i depuis 1 à 10 faire a(i) := i*4 fait

Après : t := 0 Pour i depuis 1 à 10 faire a(i) := t; t := t + 4 fait

Optimisations classiques

EII3/M2R - 8

Optimisations classiques



EII3/M2R - 9

Invariants de boucle

EII3/M2R - 10

Clonage de fonctions

EII3/M2R - 11

Avant : Pour i depuis 1 à 100 faire a(i) := a(i) + b(i) i := i + 1 fait

Après : Pour i depuis 1 à 100 faire a(i) := a(i) + b(i) a(i+1) := a(i+1) + b(i+1) i:=i+2 fait

S'il y a 2 additionneurs dans l'unité de traitement, le temps d'exécution est divisé par 2.

Optimisations spécifiques Déroulage de boucles (loop unrolling)

• Permet d’augmenter le parallélisme dans la boucle o Déroulage total (dans la plupart des cas) o Déroulage partiel

EII3/M2R - 12

Graphe flot de données DFG Déroulage des boucles

Renommage de variables pour assignation unique

Résolution du contrôle (e.g. conditions)

y(0) := x(0) * h(0); y(0) := x(0) * h(0); for i in 1 to n-1 loop y(1) := y(1-1) + x(1) * h(1); y(i) := y(i-1) + x(i) * h(i); y(2) := y(2-1) + x(2) * h(2); end loop; y(3) := y(3-1) + x(3) * h(3);

b := x + z ; b := x + z ; a := b + c ; a := b + c ; b := e + f ; b0001 := e + f ; y := b; y := b0001;



EII3/M2R - 13

#define N 4 int main(int xn, int yn) { int tmp; int h[N] = {98,-39,-327,439,950,-2097,-1674,

9883, 9883,-1674,-2097, 950,439,-327,-39, 98}; int x[N]; tmp = xn * h[N-1]; for (int i=1; i<N; i++) { tmp += x[i] * h[N-i-1]; } for (i=0; i<N-2; i++) { x[N-1-i] = x[N-2-i]; } x[1] = xn; yn = tmp; return tmp;}

Graphe flot de données DFG Déroulage des boucles Renommage de variables pour assignation unique

EII3/M2R - 14

x +

x

a

x(n) b

D

Graphe flot de signal SFG

Rebouclage

y(n) := a.x(n) + b.y(n-1); • • • y(n-1) := y(n);

EII3/M2R - 15

Résolution des conditions Corps de programme

identiques sans opérations

Corps de programme

identiques, données différentes

Corps de programme différents

Corps de programme et données différents

01

XY1

Y2

>ab

IF A > B THEN X := Y1; ELSE X := Y2; END IF;

IF A = B THEN X := R*Z + U0; ELSE X := Z + U1; END IF;

*

+ +

Z

U1

R

U0

X

0 1

A B=

X := ••• Y := ••• ••• IF A = B THEN X := Z + U0; ELSE Y := Z + U1; END IF;

+U0

X

0 1

+U1

Z

A B=

Y

0 1

Z

XY

01

A B

01

01

Y0

Y1

Z0

Z1

U0

U1

X

IF A = B THEN X := Y0*Z0 + U0; ELSE X := Y1*Z1 + U1; END IF;

=

*

+

EII3/M2R - 16

Exemple : gcc Optimization level : -OLEVEL, where LEVEL in 0 to 3

• -O0 or no -O option (default) : no optimization, use it for debug (-g) • -O1 or -O: turns on the most common forms of optimization • -O2 : turns on further optimizations, in addition to those used by -O1

o provides maximum optimization without increasing the executable size, default optimization level for releases of GNU packages

• -O3 : turns on more expensive optimizations such as function inlining o -O3 optimization level may increase the speed of the resulting executable,

but can also increase its size

• -funroll-loop : turns on loop-unrolling o will increase the size of an executable

• -Os : selects optimizations which reduce the size of an executable o produce the smallest possible executable



EII3/M2R - 17

Partie finale But: génération d’un code cible à partir de la

représentation intermédiaire Sélection d’instructions

o Reconnaissance de motifs [Leupers97, Leupers99] o Couverture d’arbre Programmation dynamique

Allocation et assignation de registres o allocation de registres Coloration de graphe o assignation de registres [Araujo95, Wess95]

Ordonnancement • Ordonnancement par liste, ILP, de traces

Optimisations dépendantes de l’architecture o adresses mémoire [Liao96, Sudarsanam95]

EII3/M2R - 18

+!

*!

/!c!

e!d!

+!

b!a!(3,2,2)

(5,4,4) S2 S1

(8,8,7)

(0,1,1) (0,1,1)

(0,1,1) (0,1,1) (0,1,1)

(C[0], C[1], C[2])

Ri = Rj C =1 Rj = Ri op Rj C =1 Ri = Ri op Mj C =1 Ri = Rj C =1 Mi = Ri C =1

Jeu d ’instructions"

2 registres : R0, R1 3 opérateurs : *,+,/ tlatence_op = 1 cycle

Architecture de la machine"

Op!

E2

E1

E:= E1 Op E2

Rj = Ri op Rj Ri = Ri op Mj C=2+4+1

(3,2,2)

Hypothèses

Sélection de code Principe :

• découpage du problème de production de code optimal pour E en sous-problèmes optimaux de production de code pour les sous-expressions E1 et E2

EII3/M2R - 19

Post-optimisations Post-optimisations

• instructions de changement de mode • assignation des bancs de mémoire • l’allocation mémoire et la génération des adresses

Génération des adresses : exploiter les U.G.A. registres d’adresse : ARi post-modifications (ARi++, ARi--) registres d’offset : MRk (ARi= ARi ± MRk )

Optimiser le placement des données en mémoire afin d’utiliser efficacement les UGA

EII3/M2R - 20

Code C

!Ctrl

9%

Code C

DSP

8%

Assembl

er DSP

55%

Assembl

er MCU

28%

Compilation de code embarqué Compilateur C vs développement assembleur

• Facteur 4 à 10 pour les DSP virgule fixe • Facteur 2 à 4 en virgule flottante

Conception de code enfoui dans l'industrie • e.g. STMicrolectronics

[Paulin97]

Assembler

DSP

25%Code C

DSP

45%

Assembler

MCU

25%

Code C

MCU

5%

[Paulin00]



EII3/M2R - 21

Benchmark OverheadClock cycles %

ProgramMemory %

Data Memory%

N Real Update 373 1306 53N Compx Update 137 882 26Dot Product 620 1309 680Matrix 24 414 5Convolution 1076 1545 100FIR 1045 769 97FIR 2D 427 743 158IIR N Biquad 140 764 55LMS 406 -35 78

Inefficacité des compilateurs C Overhead de la version compilée sur celle optimisée

à la main en assembleur • C54x [Ropers99]

EII3/M2R - 22

Inefficacité des compilateurs C Analyse du surcoût associé au compilateur C

• Meilleurs performances pour les DSP plus généraux et les DSP virgule flottante (architecture homogène)

0

200

400

600

800

1000

1200

Sur c

oût (

%)

ADSP21xx/ADI

DSP56002/Motorola

TMS320C51/TI

TMS320C54/TI

TMS320C62/TI

Processeurs

Sur coût temps d'execution

ANSI C

C modifié

-100

-50

0

50

100

150

200

250

300

350

400

Sur c

oût (

%)

ADSP21xx/ADI

DSP56002/Motorola

TMS320C51/TI

TMS320C54/TI

TMS320C62/TI

Processeurs

Sur coût taille du code

ANSI C

C modifié

EII3/M2R - 23

Raisons de l’inefficacité Inadéquation du langage C pour le TS

• Absence de support de l’arithmétique virgule fixe – extensions du langage C – langage orienté signal

Inefficacité des techniques classiques de développement des compilateurs • développement de l'architecture puis du compilateur

Inefficacité des techniques classiques de compilation • architecture hétérogène des DSP • matériel efficace mais architecture non orthogonale

Absence de support des spécificités des DSP • registres, modes d’adressage (modulo, bit-reverse), ...

EII3/M2R - 24

Profiling Codeur JPEG

Benchmark applicatif Lecture-écriture de l'image non pris en compte Image supposée être dans la mémoire interne du

DSP

Function Cycles/8x8 Block Cycles/FrameColor Conversion 192 589824DCT 320 983040Quantisation 64 19660

8Encoding 160 491520



EII3/M2R - 25

Résultats pour une image 256x256 : Environ 800 cycles/pixel

Initialisation of the board 11Initialisation of the application 246765Reading the input file 574751297Color conversion 11753360Downsampling 1592394Extract MCUs and Blocks 2539624FDCT 17306112Quantification and Zig-Zag 9664396Huffman 9226146Write the output file 76719698Others 61982607

23%

3%

5%

32%

19%

18%

Color conversion Downsampling Extract MCUs and BlocksFDCT Quantification and Zig-Zag Huffman

Profiling de l'application (1) Outils de profiling

• gprof, outils associés aux chaînes de compilation

Codeur JPEG

EII3/M2R - 26

Profiling de l'application (2) Kernel Benchmarking => DCT

• Assembleur => 2187 cycles • C => 10579 cycles

Pour un bloc 8x8 • Complexité => 10 cycles/pixel • Benchmarking en assembleur

o => 51 cycles/pixel

• Benchmarking en C o => 248 cycles/pixel

Facteur entre l'assembleur et le compilateur C = 5

EII3/M2R - 27

Profiling : gprof gprof

• nécessite de compiler les programmes avec l'option -pg • exécution du programme crée alors un fichier gmon.out • gprof mpeg2decode gmon.out > mpeg2decode.gprof!

% cumulative self self total time seconds seconds calls ms/call ms/call name 79.25 56.21 56.21 356400 0.16 0.16 Reference_IDCT 4.79 59.61 3.40 375324 0.01 0.01 form_component_prediction 4.78 63.00 3.39 356400 0.01 0.01 Saturate 4.44 66.15 3.15 356400 0.01 0.01 Add_Block 3.20 68.42 2.27 internal_mcount 2.03 69.86 1.44 356400 0.00 0.00 Clear_Block 0.27 70.05 0.19 1201821 0.00 0.00 Flush_Buffer 0.18 70.18 0.13 59400 0.00 1.12 motion_compensation 0.16 70.29 0.11 55661 0.00 0.04 decode_macroblock 0.13 70.38 0.09 1261424 0.00 0.00 Show_Bits 0.13 70.47 0.09 125108 0.00 0.03 form_prediction 0.10 70.54 0.07 55661 0.00 0.00 macroblock_modes 0.08 70.60 0.06 _mcount 0.07 70.65 0.05 211946 0.00 0.00 decode_motion_vector

index % time self children called name 0.00 68.60 1/1 _start [2] [1] 96.8 0.00 68.60 1 main [1] .... .... 0.00 68.60 1/1 main [1] [3] 96.8 0.00 68.60 1 Decode_Bitstream [3] 0.00 68.60 1/1 video_sequence [4] 0.00 0.00 2/47 Headers [41] ..... ----------------------------------------------- 0.13 66.27 59400/59400 slice [5] [8] 93.7 0.13 66.27 59400 motion_compensation [8] 56.21 0.00 356400/356400 Reference_IDCT [9] 0.03 3.49 46719/46719 form_predictions [10] 3.39 0.00 356400/356400 Saturate [13] 3.15 0.00 356400/356400 Add_Block [14] ----------------------------------------------- 56.21 0.00 356400/356400 motion_compensation [8] [9] 79.3 56.21 0.00 356400 Reference_IDCT [9]

PLAN

1. Optimisations algorithmiques

2. Synthèse architecturale

3. Synthèse logicielle, optimisation de code 1. Compilation et optimisation de code embarqué

2. Optimisation de code 1. Méthodologie 2. Optimisation sur DSP conventionnel 3. Optimisation sur processeur avec parallélisme d’instruction (ILP) Déroulage de boucles Pipeline logiciel



EII3/M2R - 29

2. Optimisation La connaissance de l'architecture interne est

importante pour bien optimiser • Placement des données et du programme • Architecture des PU, AGU, ...

Effort sur la précision des calculs ou le temps de calcul

Isoler la partie critique de l'algorithme qui est souvent à optimiser en assembleur • Règle des 80%-20%

Construire une bibliothèque optimisée de fonctions de base

EII3/M2R - 30

1. Méthodologie Algorithmes

spécifié en C fixe ou flottant

Profiling – Extraction d'une primitive (motif) – Représentation sous forme de SFG

Sélection d'un DSP Conception d’un DSP

Optimisation sur un DSP particulier

EII3/M2R - 31

Méthodologie (suite)

Synthèse – ordonnancement du SFG – allocation des opérations sur les ressources – allocation des variables sur les registres – optimisation

– imbrication des calculs – pipeline logiciel

Sélection d'un DSP Modèle du DSP idéal

Optimisation sur un DSP Modèle du DSP

Gestion de l'adressage – organisation des mémoires – table de transferts, gestion de la cohérence – gestion des modes d'adressage

Sélection d'un DSP Comparaison UT/jeu d'instructions

Optimisation sur un DSP Code du DSP (pseudo assembleur) EII3/M2R - 32

Pseudo-assembleur générique Affectation de ressources

Ressource = {bus, registre} e.g. R2 = Bus1 * R1; Acc = Acc + P;

Instructions Séquentielles : intsruction1; instruction2; Parallèles : intsruction1 || instruction2; e.g. P = bus1 || Acc = Acc + P;

Opérations arithmétiques



EII3/M2R - 33

2. DSP conventionnel DSP conventionnel

• Structure des registres « non orthogonale » o Registres dédiés à certaines unités

• Bande passante mémoire limitée • Peu de parallélisme d’instructions (ILP) • Jeu d'instructions complexe

Optimisation • Ordonnancement du SFG (cœur de la boucle) • Allocation des opérations sur les ressources • Allocation des variables sur les registres

EII3/M2R - 34

TAP

Exemple Fil Rouge Filtre Numérique RIF sur N points

y(n) +

x

+

x

+

x

+

x x

x(n)

h(0) h(1) h(2) h(3) h(4)

D D D D

EII3/M2R - 35

FIR sur DSP conventionnel (1) TMS 320C25

loop:!! acc=acc+P!// P=T*PM(*r0+)!// T=DM(*r1+)!! jnz loop!

Data Path

Program Memory

Exécution en N cyclec Data

Memory

ALU

P

MULT

T

ACC

EII3/M2R - 36 2 ACC

ALU

MULT

FIR sur DSP conventionnel (2) Lucent DSP 16xx

DO N TIME:!! acc=acc+P!// P=X*Y!//!Y=*r0++!// X=*r1++!! !

Exécution en N cycles

Bus X 16b

Bus I 16b



EII3/M2R - 37

DO N/2 TIME:!! acc=acc+P0+P1!// P0=X0*Y0 !// P1=X1*Y1!//!Y=*r0++!// X=*r1++!! !

Exécution en N/2 cycles

8 ACC

ALU

MULT

Bus X 32b

ADDER

MULT

Bus I 32b

FIR sur DSP conventionnel (3) Lucent DSP 16xxx

• Architecture Dual-MAC o 400 MIPS, 380mW o $5 - $80

EII3/M2R - 38

Exemple 1 Filtrage LMS

1ère étape : extraction du motif répétitif

1..0)1().1(.)()()3(

)()()()2(

)().()()1(

1

1

0

−=

−−−+=

−=

−=

−

−

=∑

Nnpourinxneihih

nyndne

inxihny

nn

N

in

µ

! LIRE x(n)!! y=0!! POUR i de 0 à N-1 FAIRE!! ! h(i) = h(i) + err * x(n-i-1)!! ! y = y + h(i) * x(n-i)!! FAIT!! ECRIRE(y)!! err = (d-y) * µ

x x(i-1)

err +

h(i)

x x(i)

+ y

h(i) y

Tcycle

EII3/M2R - 39

Exemple 1 (suite) • UT du DSP idéal

• Table d'occupation des ressources

• Code pseudo-assembleur

Add

R4

R3 Mult

B

R1 R2

B

Ressource Cycle 1 Cycle 2 Cycle 3 Cycle 4R1 err err err errR2 ---- err.x(i-1) ---- h(i).x(i)R3 ---- ---- h(i) h(i)R4 y y y yB x(i-1) h(i) (lecture) x(i) h(i) (écriture)

R2 = Bus B * R1 avec x(i-1) sur le bus B R3 = R2 + Bus B avec h(i) sur le bus B R2 = Bus B * R3 avec x(i) sur le bus B R4 = R4 + R2 || Bus B = R3 h(i) est écrit sur le bus B

EII3/M2R - 40

Exemple 1 (suite) TMS 320 C25

DSP16x

Add

Acc

Mult Bus

T P

Add

A

Mult

Bus X

P Y

B

1

2

T = err P = T * bus Acc = bus Acc = Acc + P bus = Acc // sauve h(i) T = bus P = T * bus Acc = bus // charge y Acc = Acc + P bus = Acc // sauve y



EII3/M2R - 41

Exemple 1 (suite) TMS 320 C54

... DB PB

CB DB CB DB CB EB

DB

EII3/M2R - 42

Exemple 1 (suite)

EII3/M2R - 43

3. Optimisation sur DSP avec ILP DSP avec parallélisme d’instructions (ILP)

• Structure des registres « orthogonale » o Registres généraux

• Unités d’exécution en parallèle o e.g. VLIW, clusterisé

• Subword Parallelism (SWP)

Optimisation • Déroulage de boucles : parallélisme • Ordonnancement du SFG (cœur de la boucle) • Pipeline logiciel • Allocation des opérations sur les ressources • Allocation des variables sur les registres

EII3/M2R - 44

Subword Parallelism (SWP) Opérations parallèles sur des données de précision

inférieure empaquetés dans un mot • Split d'unités d'exécution • Unités d'exécution multiples

Exemples • Lucent C64x, DSP16xxx, ADI ADSP-2116x, ADI TigerSHARC

16 bits

x,+,-

16 bits 16 bits

x,+,-

16 bits

16 bits 16 bits

e.g. 2 opérations 16 bits



EII3/M2R - 45

a b

c d

a-c b-d a+c b+d 63

31

0

0

0

31

31

Exemple : _addsub2(signed, signed)

res = _addsub2(in1,in2)

res

in2

in1

Subword Parallelism (SWP) Utilisation des intrinsèques

• Fonctions C (_func) ASM • Instructions ASM spécifiques s’exprimant en plusieurs ligne

de code C

EII3/M2R - 46

for (j=0;j<4;j++) { for (i=0;i<2;i++) { i1=3-i; m5[i] = i_block[idx_1 + i + (j+idx_2)*16]+ i_block[idx_1 + i1 + (j+idx_2)*16]; m5[i1]= i_block[idx_1 + i + (j+idx_2)*16]- i_block[idx_1 + i1 + (j+idx_2)*16]; } i_block[idx_1 + 0 + (j+idx_2)*16] = m5[0] + m5[1]; i_block[idx_1 + 2 + (j+idx_2)*16] = m5[0] - m5[1]; i_block[idx_1 + 1 + (j+idx_2)*16] = m5[2] + (m5[3] * 2); i_block[idx_1 + 3 + (j+idx_2)*16] = m5[3] - (m5[2] * 2); }

for (j=0; j < 4; j++) { s32* ptr_i_block = (s32*)&i_block[idx_1 + (j+idx_2)*16]; u64 addsub2_m5 =_addsub2(_rotl(*ptr_i_block,0x10),*(ptr_i_block+1)); u64 m5_0_1 =_addsub(_ext(_hill(addsub2_m5),0,16),_hill(addsub2_m5)); s16 m5_2 = (s16)_loll(addsub2_m5); s16 m5_3 = _ext(_loll(addsub2_m5),0,16); *ptr_i_block++ = _pack2(m5_2 + (m5_3 * 2),_hill(m5_0_1)); *ptr_i_block++ = _pack2(m5_3 - (m5_2 * 2),_loll(m5_0_1)); }

3230 cycles

369 cycles

89% C original

25% C optimisé

Subword Parallelism (SWP)

EII3/M2R - 47

Exploitation du parallélisme Déroulage des boucles : augmente l'ILP

LOAD MULT

ACC

LOAD

MULT ACC

LOAD MULT

ACC 100%

N/3

Taux d’utilisation du processeur

For(i=0;i<N;i++)!{! ACC=ACC + x[i].h[i]!}

For(i=0;i<N;i+=3)!{! ACC=ACC + x[i].h[i]! ACC=ACC + x[i+1].h[i+1]! ACC=ACC + x[i+2].h[i+2]!}!

EII3/M2R - 48

Exploitation du parallélisme Pipeline logiciel : ILP maximum

• Optimisation du code assembleur

LOAD

MULT

ACC

LOAD

MULT

ACC

LOAD

MULT

ACC 100%

N

Prologue

Épilogue

Taux d’utilisation du processeur



EII3/M2R - 49

Exemple 2 Filtre FIR sur DSP VLIW

x[0] = input; // Update most recent sample. acc = 0; // Zero accumulator. for (i=0; i<8; i++) // 8 taps { prod = (h[i]*x[i]); // perform Q.15 multiplication acc = acc + prod; // Update 32-bit accumulator } output = (short) (acc>>15); // Cast output to 16 bits.

1 Start MVKL .S2 8, B0 ; Intialize the loop counter (B0) to 8 2 MVKL .S1 0, A5 ; Intialize the accumulator (A5) to 0 3 Loop LDH .D1 *A8++,A2 ; Load x(i) in A2 4 LDH .D1 *A9++,A3 ; Load h(i) in A3 5 NOP 4 ; LDH has a latency of 5 cycles 6 MPY .M1 A2,A3,A4 ; Multiply x(i) and h(i) in A4 7 NOP ; MPY has a latency of 2 8 ADD .L1 A4,A5,A5 ; Add A4 to the accumulator A5 9 [B0] SUB .L2 B0,1,B0 ; Sub 1 to the counter B0 10 [B0] B .S1 loop ; Branch to loop if B0 <> 0

EII3/M2R - 50

Exemple 2 (suite)

Instruction Description Nombre de cycles

Unités .M Unités .L Unités .S Unités .D

LDH Charge une donnée 16 bits venant de la mémoire dans un registre

5 - - - .D1 .D2

LDW Charge deux données 16 bits consécutives venant de la mémoire

5 - - - .D1 .D2

MPY Multiplication entre 2 registres, résultat dans un troisième

2 .M1 .M2

- - -

ADD Addition 1 - .L1 .L2

.S1

.S2 .D1 .D2

SUB Soustraction 1 - .L1 .L2

.S1

.S2 .D1 .D2

B Branchement 5 - - .S1 .S2

-

NOP aucune opération 1 - - - -

Functional Unit

.L1

Functional Unit

.S1

Functional Unit

.M1

Functional Unit

.D1

Functional Unit

.D2

Functional Unit

.M2

Functional Unit

.S2

Functional Unit

.L2

Register File A Register File B

Data Memory Controller

EII3/M2R - 51

Exemple 2 (suite) Nombre de cycles ?

Optimisations 1. Instructions parallèles 2. Réduction des NOP

o ré-ordonnancement de certaines instructions

Cycle .D1 .D2 .L1 .L2 .M1 .M2 .S1 .S2 NOP1 LDH2345678910111213141516

Table d'allocation

EII3/M2R - 52

Exemple 2 (suite) Optimisations

3. Déroulage de boucles : suppression de la gestion de la boucle

Cycle .D1 .D2 .L1 .L2 .M1 .M2 .S1 .S2 NOP 1 LDH 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20



EII3/M2R - 53

Exemple 2 (suite) 4. Software Pipelining

• Graphe de dépendances • Nb cycles de chaque nœud

• Allocation de ressources o Unités, registres

• Table d’ordonnancement

• Recherche prologue/épilogue

5. Accès mot double

a b

*

+

LDH LDH

MPY

ADD

5 5

2

1 loop

count

B

SUB

6

1

EII3/M2R - 54

Exemple 2 (suite) Cycle .D1 .D2 .L1 .L2 .M1 .M2 .S1 .S21 LDH234567891011121314151617181920

Cycle .D1 .D2 .L1 .L2 .M1 .M2 .S1 .S21 LDH234567891011121314151617181920

EII3/M2R - 55

Références [David00] R. David Etat de l'art des cœurs de DSP, Rapport DEA, ENSSAT, 2000. [Sentieys00] O. Sentieys Conception de systèmes enfouis : état de l'art des DSP, École thématique du

CNRS, Seix (Ariège), 20-23 novembre 2000. [Sentieys01] O. Sentieys DSP et processeur superscalaire : la convergence ?, Symposium en Architectures

Nouvelles de Machines, Paris, 2001. [ICE97] B. McClean, “Status 1997: A Report on the Integrated Circuit Industry”, Integrated Circuit

Engineering Corporation (ICE), Scottsdale, 1997 [Bhaskaran95] V. Bhaskaran & K. Konstantinides, “Image and Video Compression Standards - Algorithms

and Architectures”, Kluwer Academic Publishers, Boston, 1995. [Bier97] J. Bier, P. Lapsley & G. Blalock, “Choosing a DSP Processor”, Berkeley Design Technology (BDT),

1997. [DeMan97] H. De Man and al., “Language Based Design of Digital Systems”, AI Course, KU Leuven/IMEC,

april 1997. [Lapsley96] P. Lapsley and G. Blalock, “How to Estimate DSP Processor Performance”, IEEE Spectrum, July

1996. [Pirsch97] P. Pirsch: “Video and Image Processing Architectures - Dedicated and Programmable Solutions”,

NFWO Symposium on Video Processing Architectures, January 1997. [Ackland98] B. Ackland and C. Nicol, "High Performance DSPs - What's Hot and What's Not?", IEEE Int.

Symposium on Low Power Electronic Design ISLPED, 1998. [Ropers99] A. Ropers and al., "DSPstone : TI C54x" Report IISPS AAchen University of Technology, 1999. [Madisetti98] V. Madisetti, "VLSI Signal Processors" IEEE Press, 1998.

EII3/M2R - 56

Loop alignment

Loop guarding

Loop fusion scalar replacement

An example



EII3/M2R - 57

Optimisations (1/5) 1) Présentation de

THALES 2) Sujet du stage 3) Travail réalisé

Démarche :

• Détermination des fonctions consommatrices

• Réécriture de ces fonctions en C

• Utilisation d’intrinsèques (_add, _sub …)

• Réécriture en ASM

S’assurer du bon résultat au bit près à chaque modification

EII3/M2R - 58



Réécriture de parties de code en C :

• Boucles

• Utilisation de pointeurs

• Factorisation des calculs (suppression des calculs « inutiles »)

• Déroulage de boucles

• Si possible, suppression des appels de fonctions et d’appels conditionnels (if)

• Mémoire

• Déclaration des variables les plus utilisées en mémoire cache (accès plus rapide)

EII3/M2R - 59



Réécriture de parties de code en C – Exemple :

for (j=0;j<4;j++) { for (i=0;i<2;i++) { i1=3-i; m5[i] = i_block[idx_1 + i + (j+idx_2)*16]+i_block[idx_1 + i1 + (j+idx_2)*16]; m5[i1]= i_block[idx_1 + i + (j+idx_2)*16]-i_block[idx_1 + i1 + (j+idx_2)*16]; } i_block[idx_1 + 0 + (j+idx_2)*16] = m5[0] + m5[1]; i_block[idx_1 + 2 + (j+idx_2)*16] = m5[0] - m5[1]; i_block[idx_1 + 1 + (j+idx_2)*16] = m5[2] + (m5[3] * 2); i_block[idx_1 + 3 + (j+idx_2)*16] = m5[3] - (m5[2] * 2); }

for (j=0;j<4;j++) { ptr1 = &i_block[idx_1 + (j+idx_2)*16]; m5_0 = *ptr1 + *(ptr1+3); m5_3 = *ptr1 - *(ptr1+3); m5_1 = *(ptr1+1) + *(ptr1+2); m5_2 = *(ptr1+1) - *(ptr1+2); *ptr1++ = m5_0 + m5_1; *ptr1++ = m5_2 + (m5_3 * 2); *ptr1++ = m5_0 - m5_1; *ptr1++ = m5_3 - (m5_2 * 2); }

3230 cycles

489 cycles

85%

ANNEXES

1. Compilation pour DSP



EII3/M2R - 61

Méthode : exemple

x0 x1 x2 x3 x4 x5 x6 x7

X0 X4 X2 X6 X1 X5 X3 X7

x Y

X' = X + W.Y Y' = X - W.Y

Papillon:

X'r = Xr + (Wr.Yr - Wi.Yi) X'i = Xi + (Wi.Yr + Wr.Yi) Y'r = Xr - (Wr.Yr - Wi.Yi) Y'i = Xi - (Wr.Yi + Wi.Yr)

*

*

* *

yr

yi wr

wi

-

+

+

+

-

-

x'r

y'r

x'i

y'i xr xi

1

2

3

4

5

6

7

8

9

10

* +

A

B

C

D

Exemple: la transformée de Fourier Rapide

Graphe flot de données Architecture formelle

EII3/M2R - 62

Méthode : Ordonnancement yr

wr

yi

wi

xr xi xr xiy'rx'r

yrwryiwi

x'i y'i

Cycle 1 2 3 4 5 6 7 8A Yr ->

YiYr-> Yi

B Wr ->Wi

->Wi

Wr

C Yr.Wr -> yrwr-yiwi ->Yi.Wr ->

yrwi+yiwr ->

D Yi.Wi XrYr.Wi

->-> ->

Xi ->

Mult x(1) x(2) x(3) x(4)UAL -(5) +(7) -(9) +(6) +(8) -(10)bus A Yr Yibus B Wr Wibus D Xr Xiécriture X'r Y'r X'i Y'i

Temps

Ordonnancement

• Les registres A, B, C et D doivent être doublés

EII3/M2R - 63

Méthode : Ordonnancement yr

wr

yi

wi

xr xi xr xi y'r x'r

yr

wr

yi

wi

x'i

Cycle 1 2 3 4 5 6 7 8 A Yr ->

Yi -> ->

Yr -> Yi

B Wr -> Wi

-> ->

-> Wi

Wr

C Yr.Wr -> yrwr-yiwi -> Yi.Wr yrwi+yiwr -> D Yi.Wi Xr ->

Yr.Wi -> Xi ->

Mult x(1) x(2) x(3) x(4) UAL -(5) +(7) -(9) +(6) +(8) -(10) bus A Yr Yi bus B Wr Wi bus D Xr Xi écriture X'r Y'r X'i Y'i

Temps

Ordonnancement

• Optimisation du registre C EII3/M2R - 64

Méthode : Optimisation Cycle 1 2 3 4 5 6A Yr ->

Yi->->

Yr-> Yi

B Wr ->Wi

->->

->Wi

Wr

Cyrwi+yiwr

Yr.Wr->

-> yrwr-yiwi -> Yi.Wr

D Xi -> Yi.Wi Xr ->Yr.Wi ->

Mult x(1) x(2) x(3) x(4)UAL +(8) -(10) -(5) +(7) -(9) +(6)bus A Yr Yibus B Wr Wibus D Xi Xrécriture X'i Y'i X'r Y'r

Imbrication des calculs Calculs enchainés en 6 cycles

Cohérence des données en mémoireModèle de l'unité de mémorisation

X et Y variables, W coefficients



EII3/M2R - 65

Méthode : Mémoire

1: Xr 1: Xi 1: Yr 1: Yi 2: Xr 2: Xi 2: Yr 2: Yi

Trai

tem

ent

du p

apill

on 1

1: Xr 1: Xi 2: Xr 2: Xi 1: Yr 1: Yi 2: Yr 2: Yi

Trai

tem

ent

du p

apill

on 1

1: X'r 1: X'i

1: Y'r 1: Y'i

1: X'r 1: X'i 1: Y'r 1: Y'i

Cycle 1 2 3 4 5 6 A -> ->

Yi -> ->

Yr -> Yi

Yr

B Wr -> Wi

-> ->

-> Wi

Wr

C yrwi+yiwr

Yr.Wr ->

-> yrwr-yiwi -> Yi.Wr

D Xi -> Yi.Wi Xr -> Yr.Wi ->

Mult x(1) x(2) x(3) x(4) UAL +(8) -(10) -(5) +(7) -(9) +(6) bus A Yi Yr bus B Wr Wi bus D Xi Xr écriture X'i Y'i X'r Y'r

Cohérence des données en mémoire

EII3/M2R - 66

Méthode : Modèle d’architecture

* +

A1,A2

B1,B2 C1,C2

D1,D2

bus 1

bus 2

mémoire des coefficients

mémoire des données

2 x adressages: indirect-post-incrémenté indexé

Modèle de l'architecture optimale: registres dédiés

Ex. DSP 56000

XRAM YRAM

XDATA YDATA

24 bit

24 bit

56 bit

24 bit

X0 X1 Y0 Y1

56 bit

MU

LTA

LU

24 bit

A B

EII3/M2R - 67

Méthode : Modèle d’architecture bus 1

bus 2

mémoire des coefficients

mémoire des données

2 x adressages: indirect-post-incrémenté indexé

* + banc de 8 registres

MUX

DDATA

CPU1 CPU2 REG1 REG2

40 bit

32 bit

ALU 32 bit Barrel shifter

R0

R1

R2

40 bit

Mult

Modèle de l'architecture optimal: registres généraux

Ex. TMS 320C40

EII3/M2R - 68

Caractéristiques des DSP Applications embarquées et « grand public »

• Très faible coût o le coût est proportionnel à la surface du circuit

• Faible consommation o Pmoy = α . C . Vdd 2 . F

• α: facteur d'activité défini comme le nombre moyen de transitions (0 à 1) pendant une période d'horloge.

o Hiérarchie mémoire • registres, mémoire on-chip

o Opérateurs spécialisés

• Temps réel o Implémentation efficace des applications de TS

• Sûreté de fonctionnement



EII3/M2R - 69

Énergie Gestion de la puissance

• Opération à basse tension d'alimentation • Modes “Sleep” ou “Idle” • Gestion de l'horloge programmable : PLL, clock dividers • Contrôle des périphériques

Attention aux données typiques ou maximales

DSP MACS CMOS Actif Veille16210 200 0.35u 325mW 5.4mW1609 80 0.3u 265mW 0.5mWRISC uC - 0.35u 93mW 75uW

Lucent DSPs à 3.3 Volts [Ackland ISLPD98] EII3/M2R - 70

Organisation de la mémoire Harvard architecture linked to memory bandwidth Size of supported on- and off-chip memory

• FixP DSPs o small-to-medium on-chip memories (256 - 32K words) o small external data busses

• e.g. AD, AT&T, Motorola and TI: 16bit or less address busses

• FloP DSPs o little (or no) on-chip memory o large external busses

• e.g. AD ADSP-21020: no on-chip memory, 32-bit external data address bus + 24-bit external program bus.

• e.g. TI TMS320C30: 6K words on-chip, one 24-bit and one 13-bit external address bus

• Both chips provide instruction caches • exception: ADSP-21060: 4Mbits on-chip memory, configurable in various

combinations (e.g. 64K 32-bit words and 40K 48-bit words)

Trade-off between application area and performance

EII3/M2R - 71

Outils de développement Spécifications flots de données du TS, prototypage rapide,

simulation, validation • Matlab/Simulink, Cadence SPW, Synopsys Cossap, Ptolemy

Outils de profiling • gprof, ...

Compilateurs depuis des langages de haut-niveau • DSP en virgule fixe ou flottante

Optimisations de l'assembleur Critères de sélection des outils et du langage

• Compilateurs : taille et vitesse du code • Simulateurs : vitesse

EII3/M2R - 72

From the C54x core …



EII3/M2R - 73

To the C55x

EII3/M2R - 74

C55x vs C54x Leading to higher energy efficiency (?)

EII3/M2R - 75

Pour i depuis 1 à 10 faire a(i) := x + y fait

temp := x + y Pour i depuis 1 à 10 faire a(i) := temp fait

Documents

HLS chap3 optim code - people.rennes.inria.frpeople.rennes.inria.fr/Olivier.Sentieys/teach/HLS_chap3_optim_code.pdf · TMS320C54/ T TMS320C62/ TI P roc e su ... • DSP matériel