PDF Archive

Easily share your PDF documents with your contacts, on the Web and Social Networks.

Share a file Manage my documents Convert Recover PDF Search Help Contact



representation formalisation de .pdf


Original filename: representation-formalisation-de.pdf

This PDF 1.5 document has been generated by LaTeX with hyperref package / pdfTeX-1.40.17, and has been sent on pdf-archive.com on 22/03/2018 at 09:42, from IP address 130.79.x.x. The current document download page has been viewed 218 times.
File size: 597 KB (10 pages).
Privacy: public file




Download original PDF file









Document preview


Représentation et formalisation de la parallélisation
d’une chaîne RIP
Ervin Altintas
22 mars 2018

Table des matières
1 Introduction

1

2 Hypothèses et représentation du système

2

3 Définitions des paramètres et formalisation
3.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Pire des cas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Meilleur des cas et chemin critique . . . . . . . . . . . . . . . . . . . .

3
3
4
5

4 Bufferisation
4.1 Exclusion mutuelle sur un buffer . . . . . . . . . . . . . . . . . . . . .
4.2 Buffer circulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5
6
7

5 Implémentation du consommateur
5.1 Implémentation naïve . . . . . . . . .
5.2 Solutions de l’interblocage . . . . . .
5.2.1 Solution naïve . . . . . . . . .
5.2.2 Allocation mémoire d’urgence

8
8
9
9
9

1

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

.
.
.
.

Introduction

Dans ce rapport, nous proposons de définir exactement et formellement les problèmes
à confronter lors de la parallélisation d’une chaîne RIP et de trouver des solutions à
ces problèmes. Dans la section 2, nous allons donner les hypothèses sur la résolution
du problème ainsi qu’une représentation du système. Dans la section 3, nous allons
définir les paramètres et formaliser le problème. Dans la section 4, nous allons nous
intéresser à la bufferisation des données. Dans la section 5, nous présenterons différentes
implémentations du consommateur.

1

2

Hypothèses et représentation du système

Tout d’abord, il est important de poser les hypothèses sur la forme du système
distribué. On propose que ce système soit constitué :
— D’un scheduler qui permet de distribuer, sous forme de tâches, les demandes des
imprimantes.
— De producteurs qui rastérisent les données à destination des imprimantes.
— De consommateurs qui bufferisent et organisent les données envoyées par les
producteurs.
— D’imprimantes qui passent des commandes pour recevoir des lignes de données
rastérisées.
On propose également que seules les machines possédant un consommateur soient
reliées aux imprimantes, ce qui permet aux imprimantes de pouvoir lire localement
les données qu’elles attendent. Ces lectures se font à débit constant. Les demandes
des imprimantes sont sous la forme de fourchettes de lignes, i.e. lignes de x à y. Les
imprimantes ne demandent les lignes qu’une seule fois, et demandent les lignes dans
l’ordre.
On propose que les éléments de ce système soient tous reliés à un commutateur (ou
plusieurs commutateurs) et peuvent donc communiquer en point-à-point. Il est possible
que certains éléments soient situés sur la même machine. Dans la suite de ce rapport,
l’idée est de borner le temps de résolution du problème. On supposera donc le pire des
cas : tous les éléments sont sur des machines différentes.
La figure 1 donne la représentation graphique d’un système composé d’un scheduler,
de 4 producteurs, 2 consommateurs, 3 imprimantes et un switch. Dans cet exemple,
tous les éléments sont situés sur des machines différentes. Il est possible que plusieurs
imprimantes soient reliées au même consommateur comme on le voit sur cette figure.

Figure 1 – Représentation graphique d’un exemple de système
2

3
3.1

Définitions des paramètres et formalisation
Définitions

Cette section a pour but de définir tous les paramètres du problème. Les définitions
de cette section seront utilisées dans toute la suite du rapport. Le but étant de borner
le temps de résolution du problème, les définitions porteront souvent sur la valeur
minimale possible ou la valeur maximale possible d’un paramètre. Par souci de lisibilité,
on omettra les indices min et max de chaque paramètre.
Dans la suite du rapport, on considérera une seule imprimante dans le système
et donc une seule image à imprimer. Il est également inutile dans ce scénario d’avoir
plusieurs consommateurs. La formalisation du problème dans ce scénario (figure 2) peut
ensuite s’étendre à un scénario plus général : le temps de résolution du problème devient
le temps de l’image la plus longue à imprimer.
Posons les paramètres suivants :
— D le débit du lien le plus lent.
— N le nombre de lignes à rastériser.
— vrast la vitesse de rastérisation du producteur le plus lent.
— vread la vitesse la plus lente de lecture de l’imprimante.
— Plign la taille maximale d’une ligne de données non-rastérisées.
— Prast la taille maximale d’une ligne de données rastérisées.
— Tnodata la taille maximale des messages contenant uniquement des tâches, des
requêtes ou des indications de synchronisation.
— Trasti la taille maximale des messages contenant i lignes rastérisées.
— task le temps qu’une demande d’une imprimante soit entendue par un consommateur.
— trspd le temps qu’un consommateur indique à une imprimante où lire les données
rastérisées.
— tsrch le temps maximal de recherche dans un buffer.
— tcom le temps maximal de commutation d’un paquet par un switch.
— tschd le temps maximal de génération de tâches par le scheduler.
— tres le temps de résolution du problème.

3

Figure 2 – Scénario du système pour la suite du rapport
Afin de simplifier les équations, toutes les tailles de messages comprennent les entêtes
des paquets. On ignore également les temps de propagation dans les liens. On considère aussi que les imprimantes impriment en même temps qu’elles lisent les données
rastérisées.

3.2

Pire des cas

Dans le pire des cas, l’imprimante demande les lignes une par une et aucune ligne
n’est bufferisée à l’avance. La procédure d’impression d’une ligne est donc la suivante :
— L’imprimante envoie une requête au consommateur pour imprimer une ligne.
— Le consommateur n’a pas la ligne demandée dans son buffer. Il envoie alors une
requête au scheduler.
— Le scheduler reçoit la requête, prépare une tâche pour un producteur, et envoie
cette requête à ce producteur.
— Le producteur reçoit la requête, n’a pas la ligne rastérisée en mémoire et donc
rastérise la ligne en question et l’envoie au consommateur.
— Le consommateur reçoit la ligne rastérisée et indique à l’imprimante où la lire
dans son buffer.
Le temps maximal d’impression d’une ligne tlign est donc :
+ tcom ) + tschd +
tlign = task + 2tsrch + 2( 2Tnodata
D

Plign
vrast

+

2Trast1
D

+ tcom + trspd +

Prast
vread

Le temps de résolution est alors borné par : tres < N × tlign . La figure 3 représente le chronogramme de l’impression d’une ligne pour le pire des cas. Les lignes P,
S, C et I correspondent respectivement au producteur, scheduler, consommateur et à
l’imprimante. Les flèches représentent les communications.

4

Figure 3 – Chronogramme du pire des cas pour l’impression d’une ligne

3.3

Meilleur des cas et chemin critique

Intéressons nous maintenant au meilleur des cas. Il est évidant que le facteur limitant
est la vitesse de lecture de l’imprimante. La parallélisation du problème est parfaite si et
seulement si l’imprimante travaille 100% du temps. Malheureusement, la parallélisation
parfaite est impossible. En effet, certaines étapes ne sont pas parallélisables :
— La demande de l’imprimante : task .
— La réponse du consommateur à l’imprimante : trspd .
Le temps de recherche de la ligne demandée par l’imprimante peut se faire en parallèle. En effet, on sait déjà quelle ligne l’imprimante demandera puisqu’elle demande
les lignes dans l’ordre. Dans le meilleur des cas, l’imprimante possède toutes les lignes
demandées. La borne supérieure la plus fine, en tenant compte de ces contraintes, est
donc :
tres < N × (task + trspd +

Prast
)
vread

Nous noterons cette borne B pour la suite du rapport. À l’aide de B, nous pouvons
également introduire la variable = tres − B. Dans le meilleur des cas, = 0. Dans la
suite du rapport, nous allons chercher toutes les solutions afin de réduire au maximum.
La figure 4 représente sur un chronogramme ce scénario du meilleur des cas.

Figure 4 – Chronogramme du meilleur des cas pour l’impression de deux lignes

4

Bufferisation

Afin de se rapprocher de cette situation idéale, le scheduler doit demander à l’avance,
la production des prochaines lignes de l’imprimante. Ceci engendre des problèmes de
5

concurrence dans le buffer : le consommateur doit écrire les lignes reçues par les producteurs et l’imprimante doit pouvoir également lire dans ce buffer. Afin de palier à ce
problème, des outils de synchronisation doivent être mis en place.

4.1

Exclusion mutuelle sur un buffer

L’implémentation la plus simple de synchronisation est la mise un place d’une exclusion mutuelle sur le buffer. Lorsque l’imprimante lit les données du buffer, elle verrouille
l’accès et redonne l’accès en fin de lecture. De même, lorsque les producteurs envoient
des données, ils verrouillent l’accès jusqu’à la fin de l’écriture. Avec cette implémentation, il est inutile que le buffer puisse accueillir plusieurs lignes. En effet, l’imprimante
ne peut lire qu’une fois que les producteurs n’écrivent plus dans le buffer. Dans cette
configuration, on élimine le temps de recherche du consommateur dans son buffer. Dans
le meilleur des cas, le scénario se déroule de la façon suivante :
— L’imprimante demande une ligne au consommateur.
— Le consommateur possède la ligne et indique à l’imprimante où la lire.
— Le scheduler, en parallèle, prend de l’avance et produit une tâche pour la prochaine ligne et l’envoi à un producteur.
— Le producteur cherche dans son buffer, possède la ligne, et envoi un message au
consommateur pour demander l’accès à son buffer.
— Quand l’imprimante termine sa lecture, elle l’indique au consommateur qui envoie un message au producteur pour lui laisser l’accès au buffer. L’indication de
l’imprimante ne nécessite pas de message spécial. En effet, lors de la demande
de la prochaine ligne par l’imprimante, le consommateur peut en déduire que le
buffer est de nouveau libre.
— Le producteur reçoit le message et entame le transfert de la ligne rastérisée.
— À la fin du transfert, le consommateur indique à l’imprimante où lire.
La figure 5 représente le meilleur des cas sur un chronogramme avec cette solution.

Figure 5 – Chronogramme du meilleur des cas avec une solution d’exclusion mutuelle
sur un buffer
Le temps de résolution est alors bornée par :
rast
tres < N × ( Pvread
+ task + tsynch + ttransf + trspd )
rast
⇒ tres < N × ( Pvread
+ task +

2Tnodata
D

6

+

2Trast1
D

+ 2tcom + trspd )

On obtient donc dans cette configuration :
+
= N × ( 2Tnodata
D

2Trast1
D

+ 2tcom )

Ce calcul de montre que les temps de synchronisation ainsi que d’envoi des lignes
rastérisées restent séquentiels.

4.2

Buffer circulaire

Dans le but de pouvoir paralléliser ces temps de communications, on peut imaginer implémenter un buffer circulaire du coté consommateur. Cette solution permet aux
producteurs de pouvoir remplir une zone du buffer pendant que l’imprimante lit dans
une autre zone en parallèle. On n’effectue plus d’exclusion mutuelle entre l’imprimante
et les producteurs. Néanmoins, on nécessite des messages de synchronisation afin d’assurer la disjonction entre la zone de lecture et la zone d’écriture. Également, on doit
s’assurer, cette fois-ci, de l’exclusion mutuelle des producteurs sur la zone d’écriture du
buffer. Évaluons, dans le meilleur des cas, la performance de cette solution. Le scénario
est le suivant :
— L’imprimante demande une ligne.
— Le consommateur a préalablement préparé l’adresse de cette ligne (rappelons
que l’imprimante demande les lignes dans l’ordre) et indique à l’imprimante où
la lire.
— En parallèle, le scheduler prépare une tâche pour la ligne suivante et l’envoie à
un producteur.
— Le producteur possède la ligne et demande au consommateur l’accès à son buffer.
— La zone de lecture est occupée, mais la zone d’écriture est disponible, donc le
consommateur envoie un message au producteur confirmant que le buffer est
disponible.
— Le producteur envoie la ligne, et le consommateur la reçoit et prépare l’adresse
où elle est stockée pour l’imprimante (tpnt ).
— L’imprimante prévient le consommateur qu’elle a fini de lire en demandant la
ligne suivante.
— Le consommateur indique à l’imprimante où lire cette ligne.

Figure 6 – Chronogramme du meilleur des cas avec un buffer circulaire
On a donc dans le meilleur des cas :
7

tres < N × (task + trspd +

Prast
)
vread

=B

Dans le meilleur des cas, on a donc la solution optimale avec = 0. Dans la suite du
rapport, nous analyserons donc cette solution afin de trouver l’implémentation optimale
qui gardera proche de 0 dans les pires cas.

5
5.1

Implémentation du consommateur
Implémentation naïve

Nous allons maintenant discuter de l’implémentation naïve du buffer circulaire.
Cette réflexion a pour but d’exposer les faiblesses d’une telle implémentation afin de
chercher par la suite, des optimisations ciblées.
Le buffer circulaire le plus simple est constitué de deux zones : une zone de lecture
et une zone d’écriture. Au début de la production, le buffer ne possède pas de zone
de lecture. Lors de la récupération de la ligne numéro 1, la région du buffer où est
stockée cette ligne devient la zone de lecture tandis que le reste du buffer reste une
zone d’écriture. Lorsqu’un producteur veut envoyer une ligne, il demande l’accès au
consommateur. Il inclus également la taille des données à envoyer dans son message. Si
personne n’écrit dans la zone d’écriture et si il reste assez de place dans le buffer, alors
le producteur reçoit un message de synchronisation confirmant le droit d’envoyer ses
données.
Lorsque l’imprimante a terminé de lire sa ligne, elle demande au consommateur
la prochaine ligne. L’ancienne zone de lecture est ajoutée à la zone d’écriture. Si aucun producteur n’est en train d’écrire et si la ligne en question est dans le buffer, le
consommateur assigne la zone mémoire qui contient cette ligne en zone de lecture.
Tout d’abord, cette solution présente un problème majeur : elle peut générer un
interblocage. En effet, imaginons le scénario suivant :
— L’imprimante a fini de lire la ligne i et demande au consommateur la ligne i + 1.
— Le consommateur passe donc la zone de lecture actuelle en zone d’écriture.
— Le consommateur ne possède pas la ligne i + 1 dans son buffer.
— La taille de la ligne i + 1 est supérieure à la taille de l’espace libre dans la zone
d’écriture.
— Le producteur voulant envoyer la ligne i + 1 ne reçoit donc jamais l’autorisation
d’écriture.
La résolution de ce problème n’est pas triviale. En effet, si on supprime une ligne
dans le buffer qui n’a pas encore été lue, il faut qu’un producteur ré-effectue un travail sur cette ligne. Cette solution n’est pas désirable car elle engendrerait un travail
supplémentaire pour le scheduler ainsi que du temps perdu à travailler deux fois sur la
même ligne. Afin de palier à ce problème, plusieurs autres solutions sont à envisager.
Listons maintenant ces solutions ainsi que leurs avantages et inconvénients.

8

5.2

Solutions de l’interblocage

5.2.1

Solution naïve

La solution naïve consiste à autoriser le producteur à envoyer une partie de sa ligne.
Examinons cette solution dans le scénario précédent. Considérons qu’il reste assez de
place dans la zone d’écriture afin d’accueillir la moitié de la ligne i + 1 :
— Le producteur veut envoyer la ligne i + 1.
— Le consommateur autorise le producteur à envoyer une partie de sa ligne.
— Le consommateur reçoit une partie de la ligne, passe la zone en zone de lecture,
et indique à l’imprimante où lire cette partie de la ligne.
— L’imprimante lit la partie de la ligne et indique à l’imprimante qu’elle veut la
suite.
— Le consommateur re-transfère la zone en zone d’écriture et indique au producteur
d’envoyer le reste de la ligne.
— Le consommateur reçoit le restant de la ligne, re-passe la zone en zone de lecture
et indique à l’imprimante où reprendre sa lecture.
La figure 7 représente le chronogramme de ce scénario.

Figure 7 – Chronogramme du scénario avec transmission partielle de ligne
On voit sur la figure 7, un temps séquentiel non négligeable. En effet, en notant n
le nombre de découpes nécessaires de la ligne, on obtient un temps séquentiel de :
tseq = n × (task + tsynch + trspd ) + ttransf +

Prast
vread

Ce temps séquentiel est évidemment à éviter à tout prix. Nous devons envisager une
solution plus élégante.
5.2.2

Allocation mémoire d’urgence

Afin d’éviter cette séquentialisation des travaux, nous proposons une solution alternative : si le buffer est plein et ne contient pas la ligne suivante pour l’imprimante, le
consommateur alloue temporairement un buffer (talloc et tunalloc ) de la taille de la ligne
en question. Cette solution permet deux choses. Tout d’abord, elle permet d’envoyer la
ligne en une seule fois ce qui réduit le temps de récupération de la ligne. Également,
elle permet de repasser tout le buffer original en zone d’écriture et de peut-être pouvoir
9


Related documents


representation formalisation de
dp jinnoveenweekend 1
cours1 digitalactive
presenceenligne gda
programmer ado avec delphi
tpcs2 fr


Related keywords