Preparation Exercises for Final Examination in Embedded Systems

autre étage (chemins d’envoi).

ER

EX

MEM

EX

DI

1 On parle alors d’un branchement avec délai (branch delay)

Page 3 de 14

INF3610 – Exercices final (chapitre 3)

QUESTION #2 Architecture RISC, aléas et superscalaire

Soit comme à la question précédente un pipeline à 5 niveaux semblable au DLX et soit la

boucle suivante (Figure 2.1) qui réalise l’opération vectorielle Z = X - Y + Z pour des

vecteurs de dimension 16:

Soit la boucle suivante qui réalise l’opération vectorielle Z = X - Y + Z pour des vecteurs de

dimension 16:

etiq : LD

LD

SUBF

LD

ADDF

SD

ADDI

ADDI

ADDI

SGEI

BEQZ

où

F0, 0(R1)

F10, 0(R2)

F20, F0, F10

F30, 0(R3)

F40, F30, F20

0(R3), F40

R1, R1, 8

R2, R2, 8

R3, R3, 8

R5, R1, R4

R5, etiq

; charge X(i)

;  Y(i)

; X(i) - Y(j)

; charge Z(i)

; X(i) – Y(i) + Z(i)

; range Z(i)

; incrémente l’indice X

;   Y

;   Z

; teste si plus grand ou égal à 16*8

; boucle sinon

 X(0), Y(0) et Z(0) se trouve à partir de l’adresse R1, R2 et R3

 R1, R2 et R3 sont initialisés à 0, 128 et 256 respectivement.

 R4 est initialisé à 128.

Figure 2.1

Détails des d’instructions

pouvant être pipelinées

Nom de l’instruction

LD F10, 0(R1)

Charg. mot dans F10

ADDF F20, F0, F10

SUBF F20, F0, F10

ADDI R1, R1, 8

SGTI R3, R1, R4

SD 0(R2), F6

BEQZ R3, etiq

Additionne F0 et F10

Soustrait F0 de F10

Add immédiat

si (R1 > R4) alors R3  1

sinon R3  0

Rang. d’un mot à partie de F6

Branch. si zéro

Nombre de

cycles dans

EX

Cycle du pipeline où l’opération

termine

1

4

1

1

1

1

ER (le résultat est dans

l’accumulateur après MEM)

ER (le résultat est mis dans

l’accumulateur après EX4)

EX (le résultat est mis dans

l’accumulateur après EX)

ER ((le résultat est mis dans

l’accumulateur après EX)

MEM

EX

Table 2.1 Instructions

À partir de cette boucle et à l’aide de la table 2.1:

Page 4 de 14

INF3610 – Exercices final (chapitre 3)

a) Donnez la boucle non ordonnancée, en tenant compte des cycles de suspension ou

d’attente. Considérez un modèle de pipeline avec une seule unité EX (elle aussi

pipelinée) qui peut jouer le rôle d’entier et de flottant. Donnez le temps d’exécution.

b) À partir du résultat obtenu en a), dépliez la boucle 4 fois et ordonnancé les

instructions afin de minimiser le nombre de cycles par itération. Au besoin vous

pouvez ajouter des registres Ri ou Fi. Donnez le nombre de cycles par itération

résultant.

c) Soit une machine superscalaire à deux pipelines distincts: un pipeline pour les

instructions entière (et les accès mémoire) et un pipeline pour le point flottant.

Ordonnancez la boucle dépliée obtenue en b). Donnez le nombre de cycles par

itération résultant.

Page 5 de 14

INF3610 – Exercices final (chapitre 3)

QUESTION #3 Pipeline et parallélisme d’instructions

Soit une boucle qui réalise l’opération vectorielle Y=a*X+Y/b pour un vecteur de

longueur de 100 selon le jeu d’instructions du tableau 3.1:

L:

LD

MULT F

LD

DIVF

ADDF

SD

ADDI

ADDI

STGI

BEQZ

F10, 0(R1)

F20, F10, F0

F30, 0(R2)

F40, F30, F1

F40, F40, F20

0(R2), F40

R1, R1, 8

R2, R2, 8

R3, R1, fait

R3, L

où F0 = a, F1=b et fait = 100

Instructions pipelinées

Signification

LD F0, 0(R3)

F0  Mem[0 + R3]

ADDF F8, F6, F1

F8  F6 + F1

MULTF F4, F2, F0

F4  F2 * F0

DIVF F8, F6, F1

F8  F6 + F1

ADDI R1, R1, 8

R1  R1 + 8

SD 0(R2), F8

STGI R3, R1, fait

BEQZ R3, etiq

Mem[0 + R2]  F8

si R1 > fait alors R3=0

Branchement si zéro

Nombre de

cycles dans

EX

1

2

4

6

1

1

1

1

Cycle du pipeline où l’opération termine (le

résultat étant disponible 1 cycle plus tard)

ER (le résultat est dans l’accumulateur

après MEM)

ER (le résultat est mis dans l’accumulateur

après EX2)

ER (le résultat est mis dans l’accumulateur

après EX4)

ER (le résultat est mis dans l’accumulateur

après EX6)

ER (le résultat est mis dans l’accumulateur

après EX)

MEM

EX

EX

Tableau 3.1 Instructions pipelinées

a) Complétez la trace de ce programme (Tableau 3.2, page suivante) pour l’exécution

d’une seule boucle. Considérez un modèle de pipeline sauf pour EX qui supporte à la

fois les opérations entières et flottantes. Donnez le nombre de cycles pour une itération.

b) Déroulez le code donné en a) autant de fois que nécessaire pour l’ordonnancer sans

aucune suspension, en déplaçant du code au besoin et en diminuant les instructions

de gestion de boucle, le tout en évitant les aléas. Montrez l’ordonnancement et le

gain par rapport à a).

Page 6 de 14

##

Instruction/Cycl 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

1 L: LD F10, 0(R1)

2 MULTF F20,F10,F0

3

LD F30,0(R2)

DIVF F40,F30,F20

4

5

6

7

8

9

10

ADDF F40, F40, F20

SD 0(R2),F40

ADDI R1, R1, 8

ADDI R2, R2, 8

STGI R3,R1,fait

BEQZ R3, L

Tableau 3.2 À compléter pour la question a)

Question #4 Protocole OPB

Soit le diagramme temporel suivant que nous avons vu en classe, expliquez cycle par

cycle le comportement auquel correspond ce diagramme correspond. (Attention : un

périphérique peut être à la fois maître ou esclave).

INF3610 – Exercices final (chapitre 3)

QUESTION #5 Modèle transactionnel et protocole OPB

Soit le sous-système transactionnel de la figure 5.1 intégrant 2 maîtres (A et F) de 32 bits

branchés directement sur un bus OPB, ainsi qu’un esclave D représentant un IP acheté

dont le code source est protégé relié au bus par un adaptateur de protocole (wrapper)

WD. Le wrapper ne fait aucun traitement particulier, à part convertir les protocoles.

Considérez qu’il est le wrapper que vous avez programmé au laboratoire 3. Enfin, cet IP

se connecte à un FIFO pour son bon fonctionnement. Comme ce circuit sera implanté sur

FPGA, avec des ressources matérielles limitées, le FIFO qui reliera le wrapper WD à l’IP

D sera de profondeur 4.

Figure 5.1

Une partie de l’implantation transactionnelle des maîtres A et F est représentée ci-

dessous.

A::thread()

{

unsigned long AddressD = 0x1000;

unsigned long data = 0;

F::thread()

{

unsigned long AddressD = 0x2000;

unsigned long data = 4;

// priorité la plus élevée

opb_set_master_priority(1);

// priorité la plus faible

opb_set_master_priority(2);

while(1)

{

opb_bus_write(AddressD, &data,

sizeof(data));

while(1)

{

opb_bus_write(AddressD, &data,

sizeof(data));

TraitementA(); // 2 cycles

TraitementF(); // 3 cycles

// on suppose que la fonction de

// traitement s’occupe de

// l’incrémentation de l’adresse

// on suppose que la fonction de

// traitement s’occupe de

// l’incrémentation de l’adresse

}

}

Vous savez que l’esclave D a besoin de 8 cycles pour répondre à une demande d’écriture

ou de lecture (incluant le temps de fifo). L’esclave D retire du fifo les données une à la

fois (extraction; traitement; extraction, traitement, etc.), qui lui sert donc de registre

tampon. TraitementA() nécessite 2 cycles pour s’exécuter et TraitementF() nécessite 3

cycles pour s’exécuter. La fonction opb_bus_write effectue des requêtes OPB, tel que vu

en classe et au laboratoire, à savoir : demander un accès au bus, fixer les options, placer

la requêtes sur le bus, attendre la réponse, vérifier l’acquittement, etc.

Page 9 de 14

INF3610 – Exercices final (chapitre 3)

a) Quoi que ce système semble fonctionner, il n’est pas en équilibre et un problème

majeur se produit.

 Décrivez ce problème.

 Une solution simple et efficace existe et permet de solutionner ce problème très

facilement tout en respectant des contraintes ci-dessus. Énoncez cette solution et

mentionnez les effets sur les performances du système.

b) Soit le modèle transactionnel de l’OPB vu au laboratoire.

i. À partir du code de la figure 5.2 (page suivante), donnez le code SystemC qui

décrirait la fonction opb_bus_write, en supposant les éléments suivants :

la déclaration data est unsigned long data[32] ;

o

o D est un esclave de 16 bits (OPB_HW) ;

o Le wrapper WD met 1 cycle pour se synchroniser pour chaque requête;

o Le maître possède un port d’horloge d’entrée nommé clk;

o Le wrapper supporte le mode verrouillage, mais pas le mode séquentiel.

Votre fonction doit être la plus performante possible (et évidemment, elle doit être

en mesure de transporter tout le tableau!) Toute hypothèse justifiée est acceptable.

Dans votre cahier de réponse, donnez le code associé aux éléments //(0) à //(7) ci-

dessous, //(0) étant facultatif. Chaque élément représente une ou plusieurs lignes

de code.

ii. Donnez également le nombre de cycles que requiert votre implantation pour

transférer ce tableau. Tenez compte des temps de demande de bus, temps de

propagation des signaux sur le bus, temps d’esclave et d’acquittement et tout autre

délai de votre code. Voici des hypothèses qui vont certainement vous aider :

o Supposez que le bus est libre au moment de votre demande,

o Supposez que le fifo entre D et WD est de taille infinie

c) Lorsqu’on utilise le mode verrouillage (buslock), on dit qu’il est important de faire

attention au temps de préparation (i.e. le temps créer le(s) paquet(s)) du message à

transiger. En effet, comme le mode verrouillage empêche tout autre maître d’utiliser

le bus, le maître qui verrouille et qui prend son temps pour préparer ses messages

gaspille de précieux cycles de simulation. Pourquoi ce problème ne se pose-t-il pas

dans un modèle transactionnel programmé avec SystemC ?

Page 10 de 14

INF3610 – Exercices final (chapitre 3)

void opb_bus_write(unsigned long destination_address,

unsigned long* data,

unsigned long size_of_data)

{

OPB_TRANSACTION_REQUEST opb_request;

OPB_TRANSACTION_PAYLOAD opb_payload;

unsigned long temp1, temp2, temp3;

// (0) : facultatif -- vos délarations et initialization

opb_request.request = true;

while (opb_bus_port->request_bus(&opb_request) != //(1) )

{

//(2)

}

//(3)

opb_bus_port->set_options(&opb_request);

opb_payload.address = destination_address;

// obtenir le 1er demi-mot de données

opb_payload.data = ((unsigned short)(*data)) & OPB_HW0_MASK;

while ( //(4) )

{

if ( opb_bus_port->put_request(&opb_request, &opb_payload) == OPB_STATUS_SUCCESS) )

{

if ( //(5) )

{

cout << "toute erreur de requête est implantée de sorte que "

<< "nous reprenons la transaction précédente telle quelle" << endl;

break;

}

else

{

//(6)

}

} // si la transaction échoue

else

{

//(7)

}

}

}

Figure 5.2 Blocs de code à compléter

Page 11 de 14

INF3610 – Exercices final (chapitre 3)

QUESTION #6 Processeurs embarqués et architectures

a) Soit la figure 6.1 présentée en classe. Présentez et expliquez les grandes différences

(avantages/désavantage) entre ces quatre technologies à partir des axes X et Y

(suggestion : décrivez de droite à gauche).

Figure 6.1

b) Quelles sont les principales différences entre un RISC et un DSP au niveau architectural.

c) Quelles sont les principales différences entre une puce (chip) et un noyau (core)?

d) Qu’est-ce qu’un ASIP (Application Specific Instruction Processor)? Quels sont ses

avantages/désavantages par rapport au processeur d’usage général. Donnez un exemple

de produit commercial ASIP.

e) Dans la plupart des processeurs DSP on utilise l’expression zero-overhead looping.

Expliquez en quelques lignes ce que signifie cette expression.

f) Dans quel(s) blocs(s) de la figure 6.2 (page suivante) peut-on considérer le

Microblaze utilisez comme « softcore » dans un FPGA de Xilinx. Justifiez.

g) Expliquez les raisons qui font que le 545CK de Tensilica se classe parmi les noyaux

de processeurs DSP.

Page 12 de 14

INF3610 – Exercices final (chapitre 3)

Figure 6.2 (tiré de Trends in Embedded Microprocessor Design)

Page 13 de 14

INF3610 – Exercices final (chapitre 3)

QUESTION #7 FIR et architecture VLIW

Soit l’application du filtre 1D FIR N TAP :

y(n) = a0x(n) + a1x(n-1) + a2x(n-2) + ... + aN-1x(n-N-1)

où on a2

 une table de N coefficients, a0 à aN-1

 une table de N échantillons, allant de l’échantillon courant x(n) à l’échantillon le

plus ancien x(n-N-1)

 pour chaque échantillon résultat y(n) courant, la nécessitée d’effectuer N opérations

MAC.

 une structure itérative, l’échantillon d’entrée x(n) courant devenant l’échantillon

précédant à chaque calcul du nouvel échantillon de sortie y(n)

En considérant le cas N=3 proposez une architecture VLIW qui sera capable de faire une

instruction de filtrage par cycle. Considérez que la latence de l’unité qui fera l’addition et le

chargement/rangement demande 1 cycle alors que l’unité qui fait la multiplication demande

3 cycles. Donnez aussi l’ordonnancement du code pour cette architecture. Finalement,

comparez cette accélération à l’utilisation d’un processeur DSP d’usage générale.

2 Pour plus d’information référez à http://b.l.free.fr/Page7.html

Page 14 de 14