11

11

Mécanismes de Mécanismes de communicationcommunication

22

Mécanismes de communicationsMécanismes de communications

DéfinitionsDéfinitions Système autour d’un busSystème autour d’un bus CrossCross--BarBar Réseaux DynamiquesRéseaux Dynamiques Réseaux statiquesRéseaux statiques Mécanismes de routageMécanismes de routage

33

Réseaux d'interconnexionRéseaux d'interconnexion Unité primordiale dans les machines Unité primordiale dans les machines

parallèlesparallèles Le réseau permet de relier les Le réseau permet de relier les

processeurs à la mémoire ou les processeurs à la mémoire ou les processeurs entre eux.processeurs entre eux.

44

DynamicitéDynamicité Les réseaux sont soit:Les réseaux sont soit: StatiquesStatiques: les liaisons entre les : les liaisons entre les

composants sont établies une fois pour composants sont établies une fois pour toute.toute. DynamiquesDynamiques: Les liaisons peuvent : Les liaisons peuvent

changer dans le temps. On utilise souvent changer dans le temps. On utilise souvent dans ce cas un algorithme de routage.dans ce cas un algorithme de routage.

55

SynchronisationSynchronisation Le fonctionnement de ce réseau estLe fonctionnement de ce réseau est SynchroneSynchrone: Une horloge globale rythme : Une horloge globale rythme

alors les échanges d'information (SIMD).alors les échanges d'information (SIMD). AsynchroneAsynchrone: Chaque noeud possède alors : Chaque noeud possède alors

son propre référentiel de temps (MIMD).son propre référentiel de temps (MIMD).

66

AccessibilitéAccessibilité Le type de communication est variable:Le type de communication est variable: CompletComplet: Tous les points du réseaux : Tous les points du réseaux

peuvent être reliés à chaque top d'horloge. peuvent être reliés à chaque top d'horloge. (avec une éventuelle réorganisation des (avec une éventuelle réorganisation des connexions existantes)connexions existantes) IncompletIncomplet: Seuls certains noeuds sont : Seuls certains noeuds sont

accessibles depuis chaque noeud du accessibles depuis chaque noeud du réseau. (on doit traverser le réseau réseau. (on doit traverser le réseau plusieurs fois dans certains cas)plusieurs fois dans certains cas)

22

77

FonctionnalitéFonctionnalité Le réseau établi une liaison entre un Le réseau établi une liaison entre un

port d'entré et un port de sortie. port d'entré et un port de sortie. Il permet ainsi un échange Il permet ainsi un échange

d'informations entre ces ports.d'informations entre ces ports.

88

Systèmes monoSystèmes mono--BusBus

99

Bus Interconnection SchemeBus Interconnection Scheme

1010

Extension naturelle du Extension naturelle du système mémoiresystème mémoire

P1Switch

Main memory

Pn

(Interleaved)

(Interleaved)

First-level $

P1

$

Interconnection network

$

Pn

Mem MemShared Cache

Centralized MemoryDance Hall, UMA

Scale

1111

Connexion par monoConnexion par mono--BUSBUS Par extension du modèle de Von Par extension du modèle de Von

Neumann, on peut simplement Neumann, on peut simplement réaliser un multiréaliser un multi--processeur en processeur en connectant plusieurs CPU sur un connectant plusieurs CPU sur un bus.bus. Cet organe de communication est Cet organe de communication est

alors partagé dans le temps pour alors partagé dans le temps pour réaliser les transfert réaliser les transfert

soit mémoire => CPU soit mémoire => CPU soit CPU => CPU. soit CPU => CPU. 1212

SMPSMP

Domination du marché du serveurDomination du marché du serveur Des gros systèmes aux stations de travailDes gros systèmes aux stations de travail Accès uniforme via loads/storesAccès uniforme via loads/stores Mouvement des data automatique, cohérence Mouvement des data automatique, cohérence

des cachesdes caches Bon marché Bon marché

Mécanismes d’accès identique au monoMécanismes d’accès identique au mono--processeur processeur

I/O devicesMem

P1

$ $

Pn

Bus

33

1313

FonctionnementFonctionnement Le bus ne pouvant assurer qu'1 seul Le bus ne pouvant assurer qu'1 seul

transfert à 1 instant donné, il convient de transfert à 1 instant donné, il convient de placer un arbitre sur le bus pour attribuer le placer un arbitre sur le bus pour attribuer le bus entre plusieurs demandeurs.bus entre plusieurs demandeurs. L'arbitrage des requêtes de Bus (BR:Bus L'arbitrage des requêtes de Bus (BR:Bus

Request) sélectionne un CPU et lui donne le Request) sélectionne un CPU et lui donne le bus (BG:Bus Grant)bus (BG:Bus Grant) Le CPU qui possède le BUS est appelé le Le CPU qui possède le BUS est appelé le

maître du BUS .maître du BUS .

1414

Bus TimeBus Time--sharedshared

Bus

Bus

Bus Request

Bus Grant

Bus Masters

...

1515

EfficacitéEfficacité Il y a augmentation de la vitesse du Il y a augmentation de la vitesse du

système si et seulement si la somme système si et seulement si la somme des transferts égale le débit du BUSdes transferts égale le débit du BUS Exemple:Exemple:

1 CPU utilisant 50% de son temps le 1 CPU utilisant 50% de son temps le BUS =>Maxi de 2 CPU sur le même BUS =>Maxi de 2 CPU sur le même BUS BUS (Rôle des mémoires caches)(Rôle des mémoires caches)

1616

TimingTiming

CoCo--ordination des événements sur le busordination des événements sur le bus SynchroneSynchrone Événements déterminé par les signaux de Événements déterminé par les signaux de

l’horlogel’horloge Control Bus inclus des lignes de Control Bus inclus des lignes de clockclock Front montant 1Front montant 1--0 comme bus cycle0 comme bus cycle Tous les composants peuvent lire Tous les composants peuvent lire clockclock

1717

Synchronous Timing DiagramSynchronous Timing Diagram

1818

Communication AsynchroneCommunication Asynchrone 2 signaux pour le transfert de contrôle de 2 signaux pour le transfert de contrôle de

Bus BR et BGBus BR et BG

Les transactions sont Les transactions sont synchronessynchrones ( temps ( temps de transaction connu à l'avance) ou de transaction connu à l'avance) ou asynchronesasynchrones (temps inconnu)(temps inconnu)

Maîtredemandeur

Maîtrecourant

Bus Request

Bus Grant

44

1919

Asynchronous Timing Asynchronous Timing –– Read Read DiagramDiagram

2020

Asynchronous Timing Asynchronous Timing –– Write Write DiagramDiagram

2121

Sur 2 signauxSur 2 signaux Mécanisme de "HandMécanisme de "Hand--shaking"shaking" 1:Demande de Bus par BR (demandeur 1:Demande de Bus par BR (demandeur

du bus)(actif état 0)du bus)(actif état 0) 2:Libération du Bus par BG (maître du 2:Libération du Bus par BG (maître du

bus)bus) 3:Désactivation du BR3:Désactivation du BR 4:Désactivation du BG4:Désactivation du BGBR

BG2222

Un 3ième signalUn 3ième signal

On utilise souvent un 3On utilise souvent un 3èmeème Signal BB: Signal BB: BusBus--Busy => Etat du Bus. Busy => Etat du Bus.

Maîtredemandeur

Maîtrecourant

Bus RequestBus GrantBus Busy

2323

Sur 3 signauxSur 3 signaux Le signal BG devient alors un signal de Le signal BG devient alors un signal de

prise en compte du BR par le demandeur prise en compte du BR par le demandeur mais le bus n'est libre que lorsque BB est mais le bus n'est libre que lorsque BB est inactif.inactif.

BR

BG

BB Géré par maître courantGéré par nouveau maître

Depuis le demandeur

Depuis le maître courant

2424

Requêtes multiplesRequêtes multiples Le maître reçoit plusieurs requêtes de Le maître reçoit plusieurs requêtes de

différents CPU. Lequel choisir ??différents CPU. Lequel choisir ?? On introduit une notion de On introduit une notion de prioritépriorité --

statique ou dynamique statique ou dynamique -- qui permet qui permet d'arbitrer entre les demandeurs.d'arbitrer entre les demandeurs.

55

2525

ArbitrageArbitrage Méthodes d'arbitrage sontMéthodes d'arbitrage sont ParallèlesParallèles: Les BR et BG entrent et : Les BR et BG entrent et

sortent en même temps de l'arbitresortent en même temps de l'arbitre SériesSéries: Un signal est véhiculé d'un : Un signal est véhiculé d'un

maître à l'autre jusqu'à obtention du maître à l'autre jusqu'à obtention du maître le plus prioritaire demandeur du maître le plus prioritaire demandeur du bus (daisy chaining)bus (daisy chaining) CentraliséesCentralisées: Un système unique de : Un système unique de

résolution.résolution. DécentraliséesDécentralisées: réparti sur les CPU: réparti sur les CPU

2626

Priorité parallèle CentraliséePriorité parallèle Centralisée

BG1BG2

BGn

BR1 BR2 BRn

. . . . .

B. Busy

ARBITRE

2727

Priorité Parallèle Centralisée(2)Priorité Parallèle Centralisée(2)

Chaque CPU peut générer un BR vers Chaque CPU peut générer un BR vers l'arbitre.l'arbitre. Lorsque l'un est choisi par l'arbitre, un Lorsque l'un est choisi par l'arbitre, un

unique BG est envoyé vers l'élu.unique BG est envoyé vers l'élu. BB permet de libérer le bus en fin de BB permet de libérer le bus en fin de

transfert transfert Un processeur peut utiliser le bus Un processeur peut utiliser le bus

quand il a reçu un BG et que le bus est quand il a reçu un BG et que le bus est libre. Il maintient le signal BR.libre. Il maintient le signal BR.

2828

Gestion de l'arbitrageGestion de l'arbitrage Une demande plus prioritaire est prise Une demande plus prioritaire est prise

en compte par l'arbitre: par en compte par l'arbitre: par désactivation du BG courant et désactivation du BG courant et activation du nouveau BG. activation du nouveau BG. Le maître courant du bus observe la Le maître courant du bus observe la

désactivation de son BG, il peut donc désactivation de son BG, il peut donc libérer le bus en fin de communication. libérer le bus en fin de communication. On évite ainsi l'interruption due à une On évite ainsi l'interruption due à une

requête d'un CPU plus prioritaire.requête d'un CPU plus prioritaire.

2929

Un exempleUn exemple Priorité statique : (8 CPU). Priorité statique : (8 CPU).

Ordre : 0 1 2 3 4 5 6 7Ordre : 0 1 2 3 4 5 6 7 L'arbitre devient le circuit suivant:L'arbitre devient le circuit suivant:

3030

REQ7

REQ6

REQ5

REQ4

REQ3

REQ2

REQ1

REQ0

Grant 7

Grant 6

Grant 5

Grant 4

Grant 3

Grant 2

Grant 1

Grant 0

66

3131

Arbitres en cascadeArbitres en cascade

Arbitre

Eout Arbitre

Eout Arbitre

Ein

Ein

3232

.......

Arbitrage à 2 niveaux

3333

Priorité parallèle décentraliséePriorité parallèle décentralisée

1 arbitre dans chaque CPU1 arbitre dans chaque CPU Les requêtes BR sont envoyées à Les requêtes BR sont envoyées à

tous les CPUtous les CPU L'arbitre local envoie 1 Grant à son L'arbitre local envoie 1 Grant à son

CPU si celuiCPU si celui--ci est élu.ci est élu.

3434

Parallèle décentralisée(suite) Parallèle décentralisée(suite) Plus fiable (panne d'un arbitre panne Plus fiable (panne d'un arbitre panne

d'un seul cpu)d'un seul cpu) Nécessite un TimeNécessite un Time--out pour libérer le out pour libérer le

bus en cas de pannebus en cas de panne Bus moins large, pas de BGBus moins large, pas de BG Réalisation avec des portes logiquesRéalisation avec des portes logiques

3535

Arbitrage parallèle Arbitrage parallèle décentralisédécentralisé

Grant Grant

BR BR

Bus resquest

Bus Busy 3636

Priorité SériePriorité Série Passage d'un signal d'un cpu vers un Passage d'un signal d'un cpu vers un

autre séquentiellementautre séquentiellement

" " Daisy chainDaisy chain""

77

3737

Sur le signal GrantSur le signal Grant

BG

BR

BB

+ Prioritaire - Prioritaire

3838

Sur le signal GrantSur le signal Grant Le plus répanduLe plus répandu 1 ligne de requête partagée1 ligne de requête partagée 1 ligne de "Grant" du premier CPU 1 ligne de "Grant" du premier CPU

vers les suivantsvers les suivants 1 ligne Busy1 ligne Busy

3939

FonctionnementFonctionnement Lorsqu'au moins un BR est activé, le Lorsqu'au moins un BR est activé, le

BG est validé par le contrôleur ou le BG est validé par le contrôleur ou le CPU le plus prioritaire. CPU le plus prioritaire. Le BG est transmis jusqu'au premier Le BG est transmis jusqu'au premier

CPU ayant émis un BR. CPU ayant émis un BR. CeluiCelui--ci prend alors le bus après le BB ci prend alors le bus après le BB

inactif.inactif.

4040

Sur le signal Request Sur le signal Request

BR

BG

BB

+ Prioritaire - Prioritaire

0

4141

Sur le signal Request Sur le signal Request Un CPU demande le bus par émission Un CPU demande le bus par émission

d'un BR vers la droite. d'un BR vers la droite. Lorsqu'un CPU reçoit un BR à gauche, Lorsqu'un CPU reçoit un BR à gauche,

il le transmet à droite s'il n'est pas il le transmet à droite s'il n'est pas maître du BUS, il libère le bus par un maître du BUS, il libère le bus par un BG sinon (car moins prioritaire que le BG sinon (car moins prioritaire que le demandeur).demandeur). Le CPU qui émet un BR et qui n'en Le CPU qui émet un BR et qui n'en

reçoit pas à gauche devient alors reçoit pas à gauche devient alors maître du bus. (cf 8086)maître du bus. (cf 8086) 4242

Priorité série décentraliséePriorité série décentralisée Sur signal GrantSur signal Grant Anneau de CPUAnneau de CPU Le signal Grant circule sur l'anneau Le signal Grant circule sur l'anneau

jusqu'à la prise du bus par 1 CPUjusqu'à la prise du bus par 1 CPU Priorité circulantePriorité circulante Réseau à jetonRéseau à jeton

Panne d'un CPU => Panne du réseauPanne d'un CPU => Panne du réseau

88

4343

Priorité série décentraliséePriorité série décentralisée

BR BG

Daisy ChainGrant

+ Prioritaire - Prioritaire

4444

Combinaison de Combinaison de série/Parallèlesérie/Parallèle

Arbitre parallèle

BG

BR

BB

BClear

---- ---- ----

4545

Arbitrage par scrutation:Arbitrage par scrutation: Un contrôleur recherche un CPU Un contrôleur recherche un CPU

demandeur du Bus.demandeur du Bus. Centralisé ou décentraliséCentralisé ou décentralisé

4646

CentraliséCentralisé Le contrôleur scrute tous les CPUs Le contrôleur scrute tous les CPUs

successivement (ordre = priorité)successivement (ordre = priorité) Le CPU demandeur émet un BR.Le CPU demandeur émet un BR. Le bus est alors attribué à ce cpu.Le bus est alors attribué à ce cpu. Le nombre de lignes de scrutation peut Le nombre de lignes de scrutation peut

être limité par numérotation des cpu.être limité par numérotation des cpu. Priorité statique: un compteur dans le Priorité statique: un compteur dans le

contrôleur, ou dynamique: pseudocontrôleur, ou dynamique: pseudo--random etc.random etc.

4747

Scrutation centraliséeScrutation centralisée

N lignes descrutation

BR

BB

Unité de

scrutation

4848

DécentraliséDécentralisé 1 contrôleur/CPU (1 décodeur 1 contrôleur/CPU (1 décodeur

d'adresse et 1 générateur d'adresse)d'adresse et 1 générateur d'adresse) 1 adresse est produite, elle est 1 adresse est produite, elle est

reconnue par le décodeurreconnue par le décodeur Si le cpu correspondant est Si le cpu correspondant est

demandeur il prend le bus demandeur il prend le bus

99

4949

(suite)(suite) Le décodeur transmet le BR si celuiLe décodeur transmet le BR si celui--ci ci

ne décode pas le numéro voulu.ne décode pas le numéro voulu. A la fin le générateur d'adresse produit A la fin le générateur d'adresse produit

les numéros des cpu suivants si un BR les numéros des cpu suivants si un BR arrive.arrive.

5050

Décodeur

Scrutation décentraliséeScrutation décentralisée

Générateur

N lignes d’adresse

Ack

Fin

5151

PerformancesPerformances 1 mémoire et plusieurs CPU1 mémoire et plusieurs CPU Chaque CPU accède la mémoire de Chaque CPU accède la mémoire de

façon aléatoirefaçon aléatoire

5252

ProbabilitésProbabilités Soit Soit rr la probabilité qu'un CPU requête la probabilité qu'un CPU requête

la mémoirela mémoire 11--rr : proba qu' 1 CPU ne demande pas : proba qu' 1 CPU ne demande pas

la mémoirela mémoire (1(1--r)r)pp : proba que p CPU ne demandent : proba que p CPU ne demandent

pas la mémoirepas la mémoire 1 1 -- (1(1--r)r)pp : proba qu'1 ou plusieurs CPU : proba qu'1 ou plusieurs CPU

envoient une requêteenvoient une requête

5353

Performances (suite)Performances (suite) Comme il n'y a qu'un seul bus à chaque Comme il n'y a qu'un seul bus à chaque

cycle on aura donc en moyenne cycle on aura donc en moyenne BW = 1 BW = 1 -- (1(1--r)r)pp requêtes. requêtes. On appelle On appelle bandwithbandwith cette valeur.cette valeur. Si r est grand alors le bus est vite Si r est grand alors le bus est vite

saturé.saturé. En cas de conflit (2 requêtes au même En cas de conflit (2 requêtes au même

cycle), les requêtes sont récycle), les requêtes sont ré--émises émises jusqu'à acceptation. On doit alors jusqu'à acceptation. On doit alors corriger la valeur de r.corriger la valeur de r. 5454

Bandwith simple BusBandwith simple Bus

0

0,2

0,4

0,6

0,8

1

1,2

0 5 10 15 20

r=0.8r=0.5r=0.2r=0.1

CPU

1010

5555

Connexion par multiConnexion par multi--busbus Extension du système avec b bus et p Extension du système avec b bus et p

processeursprocesseurs Une communication est possible par Une communication est possible par

connexion des deux unités au même connexion des deux unités au même bus.bus. Au même instant on peut ainsi Au même instant on peut ainsi

satisfaire b requêtes sans conflitsatisfaire b requêtes sans conflit

5656

ArbitrageArbitrage L'arbitrage demande 2 phases:L'arbitrage demande 2 phases: Les processeurs envoient un BR Les processeurs envoient un BR

pour un module mémoire donné. pour un module mémoire donné. Le premier niveau d'arbitre Le premier niveau d'arbitre sélectionne ainsi au plus une sélectionne ainsi au plus une requête par module mémoire, soit requête par module mémoire, soit m requêtes.m requêtes.

5757

(suite)(suite) Un arbitre sélectionne ensuite au Un arbitre sélectionne ensuite au

plus b requêtes parmi les m déjà plus b requêtes parmi les m déjà sélectionnées. Ces requêtes seront sélectionnées. Ces requêtes seront réalisées en même temps sur chacun réalisées en même temps sur chacun des bus.des bus.

5858

Multiple busMultiple busProcesseurs Mémoires

B Bus

5959

Arbitrage multi busArbitrage multi busRequêtes

1 arbitreparmodule

Arbitre de bus

BR 6060

CrossBarCrossBar

1111

6161

FonctionnementFonctionnement Tableau de connecteursTableau de connecteurs Toutes les permutations sont possibles Toutes les permutations sont possibles

à un instant donnéà un instant donné Un seul processeur avec un seul Un seul processeur avec un seul

module mémoiremodule mémoire Nombre de connecteurs = p*mNombre de connecteurs = p*m

6262

CrossBarCrossBarSwitchà0

Switchà1

p

m

6363

Commutateur de baseCommutateur de base Construction à partir d'une cellule de base Construction à partir d'une cellule de base

C22C22 2 entrées/2 sorties2 entrées/2 sorties

6464

Fonctionnement du CrossBarFonctionnement du CrossBar2 types de fonctionnement :2 types de fonctionnement :Architecture Architecture maître/esclavemaître/esclaveArchitecture Architecture décentraliséedécentralisée

6565

Maître/esclavesMaître/esclaves 1 processeur maître contrôle les 1 processeur maître contrôle les

connecteursconnecteurs Requêtes envoyées vers le maîtreRequêtes envoyées vers le maître Hardware et Software simplifiésHardware et Software simplifiés 1 seule connexion par ligne1 seule connexion par ligne 1 seule connexion par colonne1 seule connexion par colonne

6666

Maître/esclavesMaître/esclavesMaître

Esclaves

1212

6767

Architecture décentraliséeArchitecture décentralisée Chaque processeur contrôle les Chaque processeur contrôle les

connecteurs de son propre busconnecteurs de son propre bus Un circuit logique arbitre les conflitsUn circuit logique arbitre les conflits Un arbitre par moduleUn arbitre par module Si plusieurs requêtes au même module Si plusieurs requêtes au même module

l'une est choisie, les autres sont l'une est choisie, les autres sont retardées.retardées.

6868

DécentraliséDécentralisé

Requêtesmémoire

6969

Réseaux dynamiquesRéseaux dynamiques

7070

FonctionnementFonctionnement Interconnexion sans bus pour des Interconnexion sans bus pour des

architectures MIMD et SIMDarchitectures MIMD et SIMD Les connections s’établissent au Les connections s’établissent au

fur et à mesure des fur et à mesure des communicationscommunications

7171

Processeur

Mémoire

Processeur

Mémoire

Processeur

Mémoire

Processeur

Mémoire

RéseauDynamique

7272

Non bloquantNon bloquant Une nouvelle connexion entre une Une nouvelle connexion entre une

entrée libre et une sortie libre est entrée libre et une sortie libre est toujours possibletoujours possible Indépendant des connexions Indépendant des connexions

courantes.courantes.

1313

7373

RéRé--arrangeablearrangeable Simplification du hard (Complexité)Simplification du hard (Complexité) Une nouvelle connexion est toujours Une nouvelle connexion est toujours

possible, elle peut demander une possible, elle peut demander une modification des chemins existants modification des chemins existants pour être établiepour être établie

7474

BloquantBloquant Encore plus simpleEncore plus simple Certaines connexions peuvent ne pas Certaines connexions peuvent ne pas

être établies en fonction des être établies en fonction des connexions en coursconnexions en cours

7575

Degré du réseauDegré du réseau Simple étageSimple étage L'information ne traverse qu'un seul L'information ne traverse qu'un seul

étage de connecteursétage de connecteurs Ex: CrossEx: Cross--bar 1 n*m connecteurs O(n2)bar 1 n*m connecteurs O(n2)

Multi étagesMulti étages L'information traverse plusieurs L'information traverse plusieurs

connecteursconnecteurs Construction à partir de crossConstruction à partir de cross--bar ou à bar ou à

partir d'une cellule de basepartir d'une cellule de base Ex: Clos (cours de DEA)Ex: Clos (cours de DEA)

7676

Construction de réseauxConstruction de réseaux A partir de la cellule de baseA partir de la cellule de base

7777

Réseaux bloquantsRéseaux bloquants Conflit sur une liaison est irréductible.Conflit sur une liaison est irréductible. Exemple: réseau Exemple: réseau OmégaOméga Il y a conflit lorsque 0 et 2 connecte 4 et 5Il y a conflit lorsque 0 et 2 connecte 4 et 5

000001

011010

100101

111110

000001

011010

100101

111110

Bloquage

7878

Baseline 8x8Baseline 8x8000001

011010

100101

111110

000001

011010

100101

111110

Bloquage

1414

7979

AlgorithmeAlgorithme dede routageroutage Contrôlé par le numéro de destination Contrôlé par le numéro de destination => 0 sortie en haut=> 0 sortie en haut => 1 sortie en bas=> 1 sortie en bas Adapté à une transmission par paquetsAdapté à une transmission par paquets

8080

RéRé--arrangeablearrangeable:: Réseau de Réseau de BénesBénes construit à construit à

partir d'un baseline et de son partir d'un baseline et de son symétriquesymétrique 4 chemins différents pour un 4 chemins différents pour un

couple (E,S)couple (E,S) 4 choix possibles => ré 4 choix possibles => ré

arrangementarrangement

8181

BénesBénes

Baseline Baseline 8282

Non bloquant:Non bloquant: ClosClos nxmnxm non bloquant si (non bloquant si (mm ≥ 2≥ 2nn -- 1)1) Sinon Sinon réarrangeableréarrangeable

8383

R é se a u T yp eN o m b re d 'é ta g e C o û t

B a se lin e B lo q u a n t L o g N N /2 L o g N

B e n e s R é a rra n g e a b le 2L o g N - 1 N L o g N

C lo s N o n Blo q u a n t 2N L o g N 2N L o g N

8484

Réseaux statiquesRéseaux statiques

1515

8585

FonctionnementFonctionnement Les chemins sont fixés entre 2 Les chemins sont fixés entre 2

éléments => lien uni ou bidirectionneléléments => lien uni ou bidirectionnel On achemine des données entre les On achemine des données entre les

processeursprocesseurs Communications sont par messageCommunications sont par message Entête: numéro du destinataireEntête: numéro du destinataire Corps: donnéesCorps: données

8686

Terminologies des graphesTerminologies des graphes Le degré Le degré est défini comme étant le est défini comme étant le

nombre de liens à partir d’un noeud. On nombre de liens à partir d’un noeud. On introduit introduit maxmax et et minmin Si Si maxmax = = min min le graphe est régulierle graphe est régulier

La distance La distance dd est définit comme étant le est définit comme étant le plus court chemin entre deux noeuds.plus court chemin entre deux noeuds. Le diamètre Le diamètre DD du graphe est la plus du graphe est la plus

grande des distancesgrande des distancesD = max dD = max d

8787

CaractéristiquesCaractéristiques Diamètre: plus il est grand plus la Diamètre: plus il est grand plus la

distance entre 2 noeuds extrêmes est distance entre 2 noeuds extrêmes est grande. grande. Connectivité: Nombre de chemins Connectivité: Nombre de chemins

entre 2 noeuds. Résistance aux entre 2 noeuds. Résistance aux pannespannes Faisabilité: Facilement réalisable Faisabilité: Facilement réalisable --

degré fixe degré fixe -- symétriesymétrie Sous Sous --topologies: inclure des topologies: inclure des

topologies simplestopologies simples8888

Caractéristiques (suite)Caractéristiques (suite) Les autres caractéristiques des Les autres caractéristiques des

réseaux statiques sont :réseaux statiques sont : Routage facileRoutage facile Diffusion et autres macroDiffusion et autres macro--

communicationscommunications ExtensibilitéExtensibilité

8989

Réseau linéaireRéseau linéaire D = ND = N--11 max= 2max= 2

Numérotation des processeurs de 0 à NNumérotation des processeurs de 0 à N--1 1

9090

AnneauAnneau D = N/2 (très long)D = N/2 (très long) = 2= 2 Facile à programmerFacile à programmer

1616

9191

Réseau en anneau avec cordeRéseau en anneau avec corde Limite la longueur du cheminLimite la longueur du chemin Connections étendues à plusieurs Connections étendues à plusieurs

voisinsvoisinsCorde

9292

Réseaux complètement Réseaux complètement connectésconnectés

Tous les noeuds sont connectés 2 à 2Tous les noeuds sont connectés 2 à 2 Avec n noeuds :Avec n noeuds : On a nOn a n--1 liens par noeud 1 liens par noeud = n= n--11 n(nn(n--1)/2 chemins différents1)/2 chemins différents

L'accès est direct D = 1L'accès est direct D = 1

9393

ex: n=4ex: n=4 => pas de conflit=> pas de conflit => utilisable pour n petit=> utilisable pour n petit

9494

Réseaux 2 dimensionsRéseaux 2 dimensions

9595

Grille toriqueGrille torique 4 liens par noeud (ou 8 sur la MasPar, 4 liens par noeud (ou 8 sur la MasPar,

liens supplémentaires sur diagonale)liens supplémentaires sur diagonale) 2n liens sur le tore2n liens sur le tore = 4= 4 D = D = NN Numérotation P(i,j)Numérotation P(i,j)

9696

Grille toriqueGrille torique

(tore)

1717

9797

Grille

Pas de lien de rebouclageProche de l’algorithme4 voisins N E W S max = 4 D= 2 (N-1)

9898

Real World 2D meshReal World 2D mesh

1824 node Paragon: 16 x 114 array1824 node Paragon: 16 x 114 array

9999

Extensions en 2 dimensionsExtensions en 2 dimensions

dimensions logiques multiples par des dimensions logiques multiples par des liens plus longsliens plus longs

6 x 3 x 2

100100

Réseau étoileRéseau étoile nn--1 liens 1 liens Bottleneck sur le noeud du centreBottleneck sur le noeud du centre max = Nmax = N--11 min = 1min = 1 D = 2D = 2

101101

Réseau arborescentRéseau arborescent Exemple BinaireExemple Binaire = 3= 3 D = 2 LogD = 2 Log22(N)(N)

Racine

J niveaux

102102

FatFat--TreesTrees

Liens : plus épais plus on monteLiens : plus épais plus on monte BW fonction de NBW fonction de N

Fat Tree

1818

103103

CubeCube D = 3D = 3 = 3= 3

104104

Tore de dimension 3Tore de dimension 3 Même construction que les grilles Même construction que les grilles

toriques de 2 dimensionstoriques de 2 dimensions Produit de 3 anneauxProduit de 3 anneaux Extension à plusieurs dimensionsExtension à plusieurs dimensions

105105

HypercubeHypercube Construction par récurrence d'un Construction par récurrence d'un

hypercube de degré N à partir de hypercube de degré N à partir de deux hypercubes de degré Ndeux hypercubes de degré N--1. 1. Il suffit de relier deux à deux les Il suffit de relier deux à deux les

sommets correspondants des deux sommets correspondants des deux hypercubes initiaux.hypercubes initiaux.

106106

Hypercube 4Hypercube 4

107107

Hypercube (suite)Hypercube (suite) Pour un hypercube de degré Pour un hypercube de degré nn, on a, on a

N = 2N = 2n n noeudsnoeuds = n = log N= n = log N D = n = log ND = n = log N En tout on a 2En tout on a 2n n * n/2 liens* n/2 liens Réseau régulier, excellents diamètre et Réseau régulier, excellents diamètre et

connectivitéconnectivité

108108

Codage de GrayCodage de Gray Distance de Hamming = nombre de bits Distance de Hamming = nombre de bits

de même poids différentsde même poids différents Ex: dEx: dHH(101,110)=2(101,110)=2 On numérote les noeuds tels que la On numérote les noeuds tels que la

distance de Hamming entre 2 voisins distance de Hamming entre 2 voisins soit égale à 1soit égale à 1

1919

109109

NumérotationNumérotation Pour N=3Pour N=3 Les numéros sont attribués de telle Les numéros sont attribués de telle

sorte que sur une direction donnée, ce sorte que sur une direction donnée, ce soit toujours le bit de même poids qui soit toujours le bit de même poids qui varie. varie. On numérote les directions en fonction On numérote les directions en fonction

du poids du bit modifié.du poids du bit modifié.

110110

NumérotationNumérotation

000 001

011010

100 101

111110

111111

Routage sans tableRoutage sans table Pour émettre un message entre deux Pour émettre un message entre deux

processeurs:processeurs: On peut facilement trouver un On peut facilement trouver un

chemin valide en connaissant chemin valide en connaissant seulement le numéro du seulement le numéro du destinataire ainsi que les numéros destinataire ainsi que les numéros des noeuds traversés.des noeuds traversés.

Pas de vue globale du réseauPas de vue globale du réseau

112112

Informations localesInformations locales Chaque Noeud doit donc:Chaque Noeud doit donc: Connaître son numéroConnaître son numéro Connaître le numéro du destinataireConnaître le numéro du destinataire Les arcs sont numérotés en fonction Les arcs sont numérotés en fonction

du poids du bit qui varie entre 2 du poids du bit qui varie entre 2 voisinsvoisins

113113

Méthode du XORMéthode du XOR Par un XOR on obtient les arcs sur Par un XOR on obtient les arcs sur

lesquels on peut envoyer le messagelesquels on peut envoyer le message ex: de 111 vers 001 on obtientex: de 111 vers 001 on obtient

111111XORXOR 001001

110 => choix des arcs 1 110 => choix des arcs 1 210210 ou 2ou 2

on choisit 1 on arrive sur 101on choisit 1 on arrive sur 101101101

XORXOR 001001100 => choix de l'arc 2 100 => choix de l'arc 2

on arrive sur on arrive sur 001001114114

PropriétésPropriétés La distance entre 2 noeuds est égale à La distance entre 2 noeuds est égale à

la distance de Hamming entre les 2 la distance de Hamming entre les 2 numéros des noeudsnuméros des noeuds 2 noeuds diamétralement opposés ont 2 noeuds diamétralement opposés ont

une distance de Hamming de n ( N = une distance de Hamming de n ( N = 22nn), tous les bits sont différents), tous les bits sont différents

2020

115115

ComparaisonsComparaisonsTopology Degree Diameter Ave Dist Bisection D (D ave) @ P=1024

1D Array 2 N-1 N / 3 1 huge

1D Ring 2 N/2 N/4 2

2D Mesh 4 2 (N1/2 - 1) 2/3 N1/2 N1/2 63 (21)

2D Torus 4 N1/2 1/2 N1/2 2N1/2 32 (16)

k-ary n-cube 2n nk/2 nk/4 nk/4 15 (7.5) @n=3

Hypercube n =log N n n/2 N/2 10 (5)

116116

Hypercube à cycles Hypercube à cycles connectésconnectés

Chaque sommet est constitué d'un Chaque sommet est constitué d'un anneau de noeudsanneau de noeuds Nombre de noeuds de l'anneau = NNombre de noeuds de l'anneau = N

117117

Caractéristiques des liensCaractéristiques des liens Temps de cycle Temps de cycle TchTch: pour positionner un : pour positionner un

bit sur un fil (Bandwith = 1/Tch)bit sur un fil (Bandwith = 1/Tch) Largeur Largeur ww: nombre de bits transférés en : nombre de bits transférés en

même tempsmême temps Type de transmission : unidirectionnel et Type de transmission : unidirectionnel et

bidirectionnel.bidirectionnel.

118118

Machines réellesMachines réelles

119119

Méthodes de Méthodes de transmissiontransmission

120120

Les modes de communicationLes modes de communication Protocole d’acheminement des Protocole d’acheminement des

messagesmessages Découpage des messages?Découpage des messages? Blocage en cours de route?Blocage en cours de route? Routage des messages?Routage des messages?

2121

121121

Store and forwardStore and forward Message est stoppé sur chaque noeud, Message est stoppé sur chaque noeud,

déposé en mémoire locale puis déposé en mémoire locale puis réexpédié vers le processeur suivantréexpédié vers le processeur suivant Routage logicielRoutage logiciel Simplicité du circuit d’interconnexionSimplicité du circuit d’interconnexion Temps de traversée proportionnel à la Temps de traversée proportionnel à la

distancedistance Interruption du processeurInterruption du processeur

122122

Temps de transmissionTemps de transmission Pour un message de Pour un message de l l bits avec un header bits avec un header

de de HH on obtient:on obtient:

T = Tch [ d x ( l + H ) / w ]T = Tch [ d x ( l + H ) / w ]

dd : distance entre les deux noeuds: distance entre les deux noeuds (Méthode store and forward)(Méthode store and forward)

123123

Routage câbléRoutage câblé Routage matérielRoutage matériel Plus d'arrêt du message sur les noeudsPlus d'arrêt du message sur les noeuds Plusieurs modes d’acheminementPlusieurs modes d’acheminement CircuitCircuit--switchedswitchedWormWorm--holehole Virtual cut throughVirtual cut through PacketPacket--switchedswitched

124124

CircuitCircuit--SwitchedSwitched Emission de l’enEmission de l’en--tête du message tête du message

(numéro du destinataire)(numéro du destinataire) Etablissement des connexions le long Etablissement des connexions le long

du chemindu chemin Dès l’arrivée au destinataire, envoi d’un Dès l’arrivée au destinataire, envoi d’un

Ack sur ce cheminAck sur ce chemin Emission du message sur ce cheminEmission du message sur ce chemin Libération du cheminLibération du chemin

125125

CircuitCircuit--switchedswitchedExpéditeur Destinataire

Switch Switch Switch Switch

Message

En-tête

Liens établis

126126

Circuit-switchedExpéditeur Destinataire

Switch Switch Switch Switch

Message En-tête

Ack

2222

127127

Circuit-switchedExpéditeur Destinataire

Switch Switch Switch Switch

Paquet En-tête

Paquet

Paquet

PaquetPaquet

128128

Circuit-switchedExpéditeur Destinataire

Switch Switch Switch Switch

Paquet

Paquet

PaquetPaquet

Paquet

Liens relâchés

129129

WormWorm--holehole Envoi de l’enEnvoi de l’en--tête vers les destinatairestête vers les destinataires Mais le corps du message suit tout de Mais le corps du message suit tout de

suite l’ensuite l’en--têtetête En cas de blocage de l’entête, les En cas de blocage de l’entête, les

paquets sont mémorisés dans les paquets sont mémorisés dans les switches du cheminswitches du chemin On utilise le temps d'établissement du On utilise le temps d'établissement du

circuit pour la communicationcircuit pour la communication130130

Temps de transmissionTemps de transmission On obtient une réduction du temps de On obtient une réduction du temps de

transmission:transmission:

T = Tch [ d x H / w + l / w ]T = Tch [ d x H / w + l / w ]= Tch [ d x h + l / w ]= Tch [ d x h + l / w ]

avec avec h = H / wh = H / w temps de transfert du temps de transfert du headerheader

131131

Virtual cut ThroughVirtual cut Through Fonctionnement semblable au WormFonctionnement semblable au Worm--

holehole En cas de blocage les paquets sont En cas de blocage les paquets sont

acheminer jusqu’au switch sur lequel acheminer jusqu’au switch sur lequel l’enl’en--tête est bloquétête est bloqué On libère au plus vite les noeuds du On libère au plus vite les noeuds du

cheminchemin Pas de réalisation matérielle car il faut Pas de réalisation matérielle car il faut

des mémoires de switch très grandesdes mémoires de switch très grandes132132

Store&Forward vs CutStore&Forward vs Cut--Through RoutingThrough Routing

23 1 0

23 1 0

23 1 0

23 1 0

23 1 0

23 1 0

23 1 0

23 1 0

23 1 0

23 1 0

23 1 0

23 1

023

3 1 0

2 1 0

23 1 0

0

1

2

3

23 1 0Tim e

Store & Forw ard R outing C ut-Through R outing

S ourc e De st Dest

2323

133133

PacketPacket--switchedswitched Découpe du message en petits paquetsDécoupe du message en petits paquets Un enUn en--tête dans chaque paquettête dans chaque paquet Chemins différentsChemins différents Pas de réservation de lienPas de réservation de lien Risques d’interblocageRisques d’interblocage