Supports d’exécution pour grappes de machines SMP

Supports d’exécution pour grappes de machines SMP

Raymond NamystProjet INRIA ReMaPLIP, ENS Lyon

Plan

Multithreading Introduction et rappels

Exploitation efficace des machines SMP Ordonnancement mixte, activations

Multithreading distribué Modèles de programmation Intégration des threads et des

communications Conclusion

Pas si simple…

Multithreading

Introduction et rappels

Rappel : les processus lourds

Caractéristiques Entité active directement supportée par

l’OS Flot d’exécution Espace d’adressage privé Ressources systèmes

Exécution séquentielle Coût de gestion élevé

Allocation des ressources Appels systèmes

Processus lourds

Ressources “noyau” + données “utilisateur”

processeur processeur processeur

Noyau

Processus

Ordonnanceur

Espace utilisateur

Processus Processus

Threads : Motivations

Difficulté de programmation Fil d’exécution unique

une seule chose à la fois !

Partage de données laborieux Réactivité aux sollicitations externes

Performances Opérations de base coûteuses Recouvrement des opérations d’E/S

difficiles

Simplicité de programmation

Objectif Mener plusieurs activités indépendantes

au sein d’un processus Exemples

Simulations Serveurs de fichiers Systèmes d’exploitation (!)

Seule solution (?) Automate à états finis implanté « à la

main »(sauvegardes d’états)

Structure d’un OS monolytique

Exemple

Séquence infinie d’opérations courtes Ordre et fréquence des scrutations ?

for (;;) {

if(networkMsgIn()) getNetworkMsg();

if(kbdReady()) getKey();

if(diskBlockReady()) handleDiskBlock();

…

}

Systèmes multiprogrammés

Exécution indépendante des activités Concurrence entre les différents

traitements

for (;;) {

wait for network msg;

getNetworkMsg();

}

for (;;) {

wait for key stroke;

getKey();

}

for (;;) {

wait for disk block;

handleDiskBlock();

}

Processus serveur classique

Sérialisation des requêtes

Pas de recouvrement des E/S Exploitation SMP délicate Prise en compte de priorités ?

OS OS

client serveur

Sur l’efficacité des E/S

Caractéristiques du serveur de fichiers Tps de traitement d’une requête = 15ms Tps supplémentaire pour l’accès disque =

75ms (pour 1/3 des requêtes)

Débit sans/avec recouvrement des E/S Sans recouvrement

25 requêtes/seconde

Avec recouvrement 33.33 requêtes/seconde (+33%)

Les processus légers

Principe Détacher flot d’exécution et ressources

Introduits dans divers langages & systèmes Programmation concurrente Recouvrement des E/S Exploitation des architectures SMP

thread

ressources

Caractéristiques de base

Thread = pile + contexte Partage de ressources

Code, tas, … : espace d’adressage Fichiers ouverts Etc.

Opérations de base performantes Création, destruction Synchronisation, commutation de contextes

Création d’un processus léger Adresse de fonction à exécuter +

paramètres

Performance des threads

Opérations critiques Création/destruction (gestion mémoire) Changement de contexte (temps-

partagé) Synchronisation (mode utilisateur)

Programme d’évaluation Création d’une activité (processus,

thread)+ synchronisation (terminaison de l’activité)

OS/Processeur Processus

Thread noyau

Thread utilisateur

PM2

Linux 2.2/PII 450 0.540 0.130 - 0.006

Solaris 2.7/PII 350

8.622 0.214 0.160 0.009

Repères historiques

L’ancêtre : les coroutines Entrelacement explicite des exécutions Langages : Simula (67), Modula2 (82) Primitives clés : create + resume

Les threads dans les systèmes Cthread (Mach) -> DecThread -> PThread

(~90) Chorus, Solaris (87), winNT, IRIX, Linux, etc.

Les threads dans les langages Ada (83), Java, etc. C++ //, Eiffel //, etc.

Multithreading

Premier contact

L’interface POSIX-Threads

Interface de programmation standard pour Unix Portabilité des applications Solaris, IRIX, HP-UX, Linux, etc.

Fonctionnalités Création/destruction de threads Synchronisation Ordonnancement, priorités Signaux Etc.

Exemple: création

Création d’un nouveau thread Éventuels attributs dans la structure attr Exécution de start_func avec le paramètre

arg *pid est l’identificateur du thread créé

int pthread_create( pthread_t *pid,

pthread_attr_t *attr,

void * (*start_func)(void *),

void *arg);

Attente de fin d’exécution

Attente de la terminaison du thread pid Récupération de son code de retour

status On peut contourner ce mécanisme en

« détachant » les threads :

int pthread_join( pthread_t pid,

void **status);

int pthread_detach( pthread_t pid);

« Hello World! »

#include <stdio.h>#include <pthread.h>

void *func(void *arg){

printf(“Thread %x says %s\n”, pthread_self(), arg);return NULL;

}

int main(void){

pthread_t pid;

pthread_create(&pid, NULL, func, “Hello World!”);printf(“This is the main thread\n”);pthread_join(pid, NULL);return 0;

}

Attributs

Ensemble fixé de caractéristiques Utilisé à l’initialisation Threads, verrous, variables de condition,

etc. Threads

Priorité Pile : taille, emplacement Détaché : oui/non Type d’ordonnancement

Verrous Inversion de priorités, récursivité

Attributs : exemple

#include <stdio.h>#include <pthread.h>

void *handle_request(void *arg){

…}

int main(void){ …

pthread_attr_t attr;

for(;;) {fd = accept(sock, …);pthread_attr_init(&attr);pthread_attr_setdetachstate(&attr,

PTHREAD_CREATE_DETACHED);pthread_create(NULL, &attr, handle_request, fd);

}}

Exemple bis : pile

À manipuler avec précaution ! Quelle taille de pile choisir ? Comment prévenir/détecter les

débordements ?

pthread_attr_t attr;

pthread_attr_init(&attr);pthread_attr_setstacksize(&attr, 128*1024);pthread_create(NULL, &attr, func, NULL);

Le standard OpenMP

Interface pour écrire des applications multithreads portables (sur SMP) Directives de compilation (C, C++, Fortran)

+ routines Objectif = simplicité + portabilité Constructeurs + fabricants de logiciels +

etc. Modèle de programmation

« Fork-Join » Parallélisation des boucles (#pragma omp)

Multithreading

Partage mémoire efficace

Les threads et la mémoire

Chaque thread possède sa propre pile Variables locales « privées » ( visibilité)

Les threads partagent l’espace d’adressage Variables globales Tas (malloc) Variables locales (piles) également !

Intérêt Communications par pointeurs ! Parallélisation de programmes séquentiels

aisée ?

Problèmes de réentrance

Exemple simple :int glob = 0;

void *inc(void *arg){ int i;

for(i=0; i<100; i++)glob++;

}

int main(void){

pthread_create(&t1, NULL, inc, NULL);pthread_create(&t2, NULL, inc, NULL);

pthread_join(t1, NULL); pthread_join(t2, NULL);printf(“glob = %d\n”, glob);

}

Résultat ?

Explication

glob++ n’est pas forcément une opération atomique

Scénario d’exécution concurrente par 2 threads :

Mov @glob, $r1 ; chargerInc r1 ; incrémenterMov $r1, @glob ; enregistrer

Mov @glob, $r1Inc r1

Mov @glob, $r1Inc r1Mov $r1, @glob…

Mov $r1, @glob

Mov @glob, $r1Inc r1

Mov @glob, $r1Inc r1Mov $r1, @glob…

Mov $r1, @glob

Outils pour la synchronisation

Exclusion mutuelle : les verrous

Synchronisations plus complexes : Variables de condition (cf moniteurs de

Hoare) pthread_cond_wait pthread_cond_signal, pthread_cond_bcast

int glob = 0;

void *inc(void *arg){

for(i=0; i<100; i++) {pthread_mutex_lock(&mutex);glob++;pthread_mutex_unlock(&mutex);

}}

Code réentrant

« code demeurant correct lorsqu’il estexécuté simultanément par plusieurs threads »

Exemples typiques Fonction n’utilisant que des variables locales Code protégé par un verrou

Quid du code que l’on écrit pas soi-même ? Malloc, free, …, la bibliothéque standard Fonctions « MT-safe »

Option –D_REENTRANT Certains prototypes changent…

Importance de la synchro.

Cohérence séquentielle de la mémoire ? Compilateurs/Optimiseurs

Instructions réordonnées

Processeurs modernes Ecritures réordonnées

On ne peut pas supposer l’ordre des écritures

Primitives de synchronisation Agissent comme des « barrières

mémoire »

Variables spécifiques

Pb : comment gérer les variables globales « privées »

int my_x;

void g(void){

…my_x…}

void f(void){

my_x = do_compute();…g();

}

Variables spécifiques

Principe Variable accessible à partir d’une clé Allocation globale (souvent à l’initialisation)

pthread_setspecific(clé, valeur) pthread_getspecific(clé) -> valeur

Exemple : la variable errno Fichier errno.h

#ifdef _REENTRANT#define errno (*__errno_location())

#elseextern int errno;

#endif

Multithreading

Quelques idées reçues ?

A propos d’efficacité…

Les threads sont-ils toujours meilleurs que MPI sur architectures SMP ?

Approche « processus communicants » Communications pénalisantes (copies) Surcoût en utilisation de ressources Recouvrement plus difficile

Approche « processus légers » Synchronisations additionnelles Accès aux variables spécifiques coûteux

Exploitation efficacedes machines SMP

Quelle catégorie de threads ?

Multithreading utilisateur

Deux ordonnanceurs indépendants :

processor processor processor

OS Kernel

Process Process Process

Scheduler

User Space

Scheduler Scheduler

Multithreading noyau

Un seul ordonnanceur :

processor processor processor

OS Kernel

Process Process Process

Scheduler

User Space

Multithreading mixte

Deux ordonnanceurs coopérants

processor processor processor

OS Kernel

Process Process Process

Scheduler

User Space

Scheduler Scheduler

Note: Quid des appels systèmes bloquants ?

Performances

Athlon 1.4GHz, DDR2100Opération Unix

(fork)pthrea

dclone Marce

l SMPMarce

l mono

Chgt contexte

600 ns

370 ns 350 ns

180 ns

65 ns

Création 80 us 35 us 14 us 1.7 us 0.82 us

Alpha 500MHzOpération Unix

(fork)pthrea

dclone Marcel

SMPMarc

el mono

Chgt contexte

1.750 us 1.740 us

1.7 us

815 ns 560 ns

Création 640 us 190 us 90 us

8 us 4 us

E/S et ordonnancement

Threads noyaux : OK Threads utilisateurs

Appel bloquant -> blocage du processus entier

Threads mixtes Idem au bout d’un certain nombre !

Solutions ? Appels toujours non-bloquants (polling) Appels effectués par des threads dédiés Support système spécifique

Exploitation efficacedes machines SMP

Scheduler Activations

Recouvrement des E/S

Au lieu de

Espace noyau

Espace utilisateur

Matériel

syscall

…on voudrait :

Espace noyau

Espace utilisateur

Matériel

I/O request interrupt

Temps CPU perdu

CPU utilisé

Scheduler Activations

Introduit par [Anderson et al. 91] Idée: la coopération entre les deux

ordonnanceurs est bidirectionnelle L’ordonnanceur utilisateur utilise des appels

systèmes L’ordonnanceur noyau utilise des upcalls!

Upcalls Informe l’application des événements noyaux

Activations Autant d’activations en exécution que de

processeurs Contrôlées par le noyau

Principe mis en œuvre dans Solaris

Illustration du principe

Process

User scheduler

Illustration du principe

Process

new

Illustration du principe

Process

new

Illustration du principe

Déroulement d’un appel bloquant…

Process

Appel système bloquant

Illustration du principe

Déroulement d’un appel bloquant…

Process

New + blocked

Illustration du principe

Déroulement d’un appel bloquant…

Process

Appel terminé

Illustration du principe

Déroulement d’un appel bloquant…

Process

Unblocked

Illustration du principe

Déroulement d’un appel bloquant…

Process

Difficultés de mise en œuvre

Retour d’un appel bloquant Un « unblock upcall » nécessite deux

appels systèmes supplémentaires… La généricité coûte cher !!

Perte du processeur Signalée par un upcall particulier

Objectif = éviter les attentes actives ! Conséquences

L’ordonnanceur de niveau utilisateur doit se prémunir contre ces interruptions intempestives

Le coût est prohibitif !

Coût de la préemption

Lorsqu’une activation est préemptée… L’ordonnanceur doit être averti Pourquoi ?

Un thread peut détenir un « spin-lock » ! Comment ?

En déclenchant un upcall preempt

Problèmes Une préemption peut survenir n’importe

quand Changements de contexte asynchrones Nécessité de protéger beaucoup de code

e.g. la fonction thread_yield() ...

Coût des appels bloquants

thread

blockingsyscall

spregisters

sp

activation

Coût des appels bloquants

thread

sp

thread

activation

spregisters

sp

spblocked

activation

Clock int.

registerssp

Coût des appels bloquants

thread

sp

thread

activation

spregisters

sp

registerssp

registersregisters

activation

Coût des appels bloquants

thread

sp

thread

activation

sp

registerssp

registersregisters

Coût des appels bloquants

thread

sp

thread

activation

jb sp

registersregisters

sys_restart

Coût des appels bloquants

thread

sp

thread

activation

registers

Un modèle revisité

Contexte = calcul haute performance Une application // à la fois sur la grappe Optimisations pour ce cas de figure

Les activations perdent rarement le processeur

Propositions Suppression des évènements « preempt » Utilisation d’une pile par processeur

Implantation Linux 2.2.x Bibliothèque de threads Marcel

A propos de réactivité…

Problèmes liés aux évènements « unblock » Coût important, réactivité non-garantie

Proposition Pour les notifications non-urgentes

Positionnement d’une variable partagée Test à chaque changement de contexte

Pour les notifications critiques Lors du retour en mode utilisateur :

- Déviation vers le thread « client » de l’événement

Déviation éventuellement différée…

Modifications du noyau Linux

Parties du noyau modifiées schedule(), do_fork() and do_exit()

Implantation des transitions

task_struct structure Nouveaux champs (état des activations, etc.)

Code ajouté Appels systèmes + API pour les upcalls Gestion des upcalls (~signaux) Code pour les changements d’état des

activations

Performance (PC)

Single processor Dual processor

Library Synchro test I/O test With computations

Marcel/user-level 0.308ms Infini 6932ms

Marcel/hybrid 0.435ms 0.761ms 3807ms

Marcel/activations 0.417ms 1.300ms 3551ms

LinuxThread 13.319ms 0.773ms 3566ms

MultithreadingDistribué

Principe et Enjeux

Principe

Introduire les threads dans les applications distribuées

procproc proc proc

réseau

Enjeux

Bénéfices escomptés Meilleur support du parallélisme à grain

fin Recouvrement naturel des

communications Uniformisation de la configuration

Machines monoprocesseur/machines SMP

Intérêts

Apports des threads Virtualisation de l’architecture

Threads = processeurs virtuels Passage à l’échelle (scalability) Bonne cible pour des compilateurs

Meilleure réactivité au réseau Traitement asynchrone des messages

Équilibrage de charge par migration de threads Équilibrage dynamique Régulateur indépendant de l’application (plug-

ins) !

MultithreadingDistribué

Quel modèle de programmation ?

Approche par juxtaposition

Principe : pas de modèle ! Simplement utiliser conjointement

Une bibliothèque de communication (ex: MPI) Une bibliothèque de multithreading

Problèmes Conceptuels

Pas de visibilité globale des threads Sémantique des communications ?

Techniques Compatibilité entre les bibliothèques Travail d’intégration spécifique -> non

réutilisable

Approche intégrée

Threads communicants A0, Chant

Pthreads + extensions Rthreads

Pthreads DSM-threads

Appels de procédure à distance « threadés » A0, Nexus, PM2

Threads communicants

Principe Envoi de message entre threads

Modèle « MPI-like » Modèle « Acteurs »

Nommage Nommage global des threads Ports de communication

Exemples Chant (M. Haines, ICASE) Athapascan-0b (J. Briat, INRIA Grenoble)

Modèle Pthreads étendu

Principe Threads + primitives étendues

Create/Join à distance Synchronisations distribuées

Particularités Nommage global des threads Restriction du modèle Pthreads

Exemples Chant (M.Haines, ICASE),

Rthreads (M. Zahn, Allemagne)

Modèle Pthreads distribué

Principe Adaptation complète (?) de Pthreads

Threads + mémoire virtuellement partagée

Transparence Cohérence assurée lors des défauts de

pages Restriction sur les E/S

Extensions Cohérences mémoires relâchées

Exemple DSM-Threads (F. Mueller, Berlin)

Modèle dérivé des RPC

Principe Appel de procédure à distance (A. Birell)

Extension du concept aux threads Création de threads pour exécuter les

procédures

Désignation globale des services Numéro fonction Souches (stubs) pour la transmission des

paramètres

Exemples Nexus (I. Foster, Argonne), PM2

MultithreadingDistribué

L’environnement PM2

Projet PM2 (95-xx)

Objectif ambitieux : virtualisation Indépendance de la machine cible

(#processeurs) Degré de parallélisme important (#processus) Parler de “traitement” / “processus”

mécanismes de décomposition parallèle

Propositions Mécanisme de décomposition

Appel de procédure à distance léger (LRPC)

Support des activités Processus légers (threads)

Régulateur dynamique de charge Placement + Migration

Appel de procédure à distance

Différentes déclinaisons Synchrone Attente différée Asynchrone

PM2 PM2

LRPC

Nos concurrents... Nexus : RSR Athapascan : appels de service

Mobilité des activités

Migration de processus légers

PM2 PM2

Pourquoi ? Régulation de charge Localité des données

Comment ? Transfert du contexte Programmes SPMD

MultithreadingDistribué

Communications dans un environnement multithreads

Communications performantes

Comment exploiter les réseaux rapides ? Faible latence

Quelques microsecondes Bande passante élevée

De l’ordre du Gb/s

Tendance actuelle Interaction directe avec la carte réseau

Communication en « mode utilisateur » Transmissions zéro-copie

La carte récupère/dépose les données au bon endroit

Ethernet

Cartes passives (sauf Giga-Ethernet) Interfaces : TCP, SBP, GAMMA, VIA, …

Network

TX reg

RX reg

Packet InterfacePacket InterfacePCI

Bridge

PCI

Bridge

PCI Bus

DMADMA

Memory

TX-ring

NIC

Myrinet

Produit Myricom (C. Seitz) Réseau commuté, routage wormhole

Carte programmable Protocoles de transmission

« intelligents » Stratégie adaptée à la taille des messages Déclenchement d’interruptions

NetworkRISC

Packet

Interface

DMADMA

PCI

Bridge

PCI

Bridge

PCI Bus

LANai

SRAMSRAM

NIC

Interface efficace pour Myrinet

BIP : Basic Interface for Parallelism Loic Prylli (ReMaP) en 1997

Performances Latence 5 s, bande passante > 125 Mo/s

Fonctionnalités réduites au minimum Messages courts : recopiés à l’arrivée Messages longs : mode zéro-copie (RDV)

Contrôle de flux minimal Matériel (msgs “évaporés” au dela de

50ms)

SCI : Scalable Coherent Interface

Réseau à “capacité d’adressage” Normalisé par IEEE en 1993 Principal constructeur : Dolphin ICS

Principe Accés mémoire distants

Implicites (après projection) Explicites (remote DMA)

Support matériel pour une MVP (?)

Performances Ecriture 2 s, lecture 4 s Bande passante 85 Mo/s (difficilement !)

Adressage à distance

Projections effectués par le pilote (SISCI) Zones de mémoire physiques souvent spécifiques

Accès mémoire effectués par le processeur Le processeur distant n’est pas (forcément) interrompu

Interconnexion SCI

Processus A

Espace d'adressage

virtuel

Bus PCI

PCI-SCI

Processus B

Espace d'adressage

virtuel

Bus PCI

PCI-SCI

Mémoire physique

Ce qu’il faut retenir

Interfaces de très bas niveau ! Fonctionnalités proches du matériel

Grande efficacité Paradigmes très différents Approche non généralisable

Pas de consensus Tentative de standard : VIA

- Virtual Interface Architecture (Intel, Microsoft, Compaq)

- But : dénominateur commun- Bas niveau, peu adapté à certaines technologies

Portabilité ???

Contexte et motivations

Concilier efficacité et portabilité

Il y a MPI…

Implantations efficaces existantes MPICH/BIP, MPICH/SISCI, etc.

Quid des schémas de communication de la vraie vie ?

Messages dont le contenu est inconnu a priori par le récepteur

- Transmissions zéro-copie ?

Messages asynchrones- Recouvrement des communications ?

Accès mémoire distants (PUT/GET)- Temps de réponse ?

Transmissions zéro-copie

Processus A Processus BRéseau

Préparation mémoire

Acquittement

Message

EntêteDonnées

DMA

Et la réactivité alors ?

Problèmes Assurer la progression des communications

asynchrones Réagir rapidement aux sollicitations extérieures

procproc proc proc

réseau

Envois asynchrones

Parvient-on vraiment à assurer du recouvrement ?

Processus A Processus B

Acquittement

MPI_Isend

MPI_recv

MPI_test

L’interface Madeleine

Principe

Madeleine

Interface de communication Efficace et portable

Double objectif Support de multiples paradigmes/modes Support de multiples réseaux simultanément

Proposition Programmation par « contrat »

Contrôle du niveau d’optimisation Transferts immédiats possibles

Statut Disponible sur BIP, SISCI, TCP et MPI. Portage en cours sur VIA

Construction des messages

Gestion des canaux (~ communicators) Choix explicite du dispositif physique

Interface

mad_begin_packing

mad_pack

mad_end_packing

mad_begin_unpacking

mad_unpack

mad_end_unpacking

Packing et Unpacking

Commandes : mad_pack (cnx, buffer, len, pack_mode, unpack_mode) mad_unpack (cnx, buffer, len, pack_mode,

unpack_mode)

Modes :Send_SAFER

Send_CHEAPER

Send_LATER

Receive_EXPRESS

Receive_CHEAPER

RPC efficaces avec Madeleine

LRPC, Migration

Madeleine

Gestion générique de tampons

Gestion des transmissions

BIP, SISCI, VIA, TCP, MPI

Emission : modes d’empaquetage

Version transmise

Pack

Modification

End_packing

Send_SAFER Send_LATER Send_CHEAPER

Réception : mode de déballage (1)

Unpack

Après Unpack

End_packing

Tampon

Données disponibles

RECV_EXPRESS

Réception : mode de déballage (2)

RECV_CHEAPER

Unpack

Après Unpack

End_packing

Tampon

Données disponibles ???

Données disponibles

Exemple

mad_end_unpacking(cnx);

send_CHEAPER,receive_CHEAPER);

mad_unpack(cnx, s, n,

s = malloc(n);

send_CHEAPER,receive_EXPRESS);

mad_unpack(cnx, &n, sizeof(int),

cnx = mad_begin_unpacking(channel);

p_mad_connection_t cnx;

char *s = NULL;

int n;

mad_pack(cnx, s, n,

send_CHEAPER, receive_CHEAPER);

mad_end_packing(cnx);

send_CHEAPER, receive_EXPRESS);

mad_pack(cnx, &n, sizeof(int),

n = strlen(s) + 1;

cnx = mad_begin_packing(channel, dest);

p_mad_connection_t cnx;

char *s = "Hello, World !";

int n;

Sending side Receiving side

Exemple

mad_end_unpacking(cnx);

send_CHEAPER,receive_CHEAPER);

mad_unpack(cnx, s, n,

s = malloc(n);

send_CHEAPER,receive_EXPRESS);

mad_unpack(cnx, &n, sizeof(int),

cnx = mad_begin_unpacking(channel);

p_mad_connection_t cnx;

char *s = NULL;

int n;

mad_pack(cnx, s, n,

send_CHEAPER, receive_CHEAPER);

mad_end_packing(cnx);

send_CHEAPER, receive_EXPRESS);

mad_pack(cnx, &n, sizeof(int),

n = strlen(s) + 1;

cnx = mad_begin_packing(channel, dest);

p_mad_connection_t cnx;

char *s = "Hello, World !";

int n;

Sending side Receiving side

Exemple

mad_end_unpacking(cnx);

send_CHEAPER,receive_CHEAPER);

mad_unpack(cnx, s, n,

s = malloc(n);

send_CHEAPER,receive_EXPRESS);

mad_unpack(cnx, &n, sizeof(int),

cnx = mad_begin_unpacking(channel);

p_mad_connection_t cnx;

char *s = NULL;

int n;

mad_pack(cnx, s, n,

send_CHEAPER, receive_CHEAPER);

mad_end_packing(cnx);

send_CHEAPER, receive_EXPRESS);

mad_pack(cnx, &n, sizeof(int),

n = strlen(s) + 1;

cnx = mad_begin_packing(channel, dest);

p_mad_connection_t cnx;

char *s = "Hello, World !";

int n;

Sending side Receiving side

Exemple

mad_end_unpacking(cnx);

send_CHEAPER,receive_CHEAPER);

mad_unpack(cnx, s, n,

s = malloc(n);

send_CHEAPER,receive_EXPRESS);

mad_unpack(cnx, &n, sizeof(int),

cnx = mad_begin_unpacking(channel);

p_mad_connection_t cnx;

char *s = NULL;

int n;

mad_pack(cnx, s, n,

send_CHEAPER, receive_CHEAPER);

mad_end_packing(cnx);

send_CHEAPER, receive_EXPRESS);

mad_pack(cnx, &n, sizeof(int),

n = strlen(s) + 1;

cnx = mad_begin_packing(channel, dest);

p_mad_connection_t cnx;

char *s = "Hello, World !";

int n;

Sending side Receiving side

Exemple

mad_end_unpacking(cnx);

send_CHEAPER,receive_CHEAPER);

mad_unpack(cnx, s, n,

s = malloc(n);

send_CHEAPER,receive_EXPRESS);

mad_unpack(cnx, &n, sizeof(int),

cnx = mad_begin_unpacking(channel);

p_mad_connection_t cnx;

char *s = NULL;

int n;

mad_pack(cnx, s, n,

send_CHEAPER, receive_CHEAPER);

mad_end_packing(cnx);

send_CHEAPER, receive_EXPRESS);

mad_pack(cnx, &n, sizeof(int),

n = strlen(s) + 1;

cnx = mad_begin_packing(channel, dest);

p_mad_connection_t cnx;

char *s = "Hello, World !";

int n;

Sending side Receiving side

Exemple

mad_end_unpacking(cnx);

send_CHEAPER,receive_CHEAPER);

mad_unpack(cnx, s, n,

s = malloc(n);

send_CHEAPER,receive_EXPRESS);

mad_unpack(cnx, &n, sizeof(int),

cnx = mad_begin_unpacking(channel);

p_mad_connection_t cnx;

char *s = NULL;

int n;

mad_pack(cnx, s, n,

send_CHEAPER, receive_CHEAPER);

mad_end_packing(cnx);

send_CHEAPER, receive_EXPRESS);

mad_pack(cnx, &n, sizeof(int),

n = strlen(s) + 1;

cnx = mad_begin_packing(channel, dest);

p_mad_connection_t cnx;

char *s = "Hello, World !";

int n;

Sending side Receiving side

Exemple

mad_end_unpacking(cnx);

send_CHEAPER,receive_CHEAPER);

mad_unpack(cnx, s, n,

s = malloc(n);

send_CHEAPER,receive_EXPRESS);

mad_unpack(cnx, &n, sizeof(int),

cnx = mad_begin_unpacking(channel);

p_mad_connection_t cnx;

char *s = NULL;

int n;

mad_pack(cnx, s, n,

send_CHEAPER, receive_CHEAPER);

mad_end_packing(cnx);

send_CHEAPER, receive_EXPRESS);

mad_pack(cnx, &n, sizeof(int),

n = strlen(s) + 1;

cnx = mad_begin_packing(channel, dest);

p_mad_connection_t cnx;

char *s = "Hello, World !";

int n;

Sending side Receiving side

Madeleine – structure

BMM1 BMMn

TM1 TMn

Network

Application

Generic BufferManagement

ModulesSwitch

Selection

BMM1 BMMm

TM1 TMn

Application

Switch

Selection

Specific Transmission Modules

Adaptativité

Sélection du mode de transmission adéquat

Interface

Gestion des

tampons

Gestionde

protocole

Pack

??

Implementation

Madeleine II a été portée sur : SISCI/SCI BIP/Myrinet MPI VIA TCP SBP

BIP/Myrinet

Latency: Madeleine II/BIP

0

2

4

6

8

10

12

0 64 128

Packet size (bytes)

Lat

ency

(µ

s)

Latency: Madeleine II/BIP

0

2

4

6

8

10

12

0 64 128

Packet size (bytes)

Lat

ency

(µ

s)

BIP/Myrinet

Bandwidth: Madeleine II/BIP

0

20

40

60

80

100

120

4 16 64 256

1024

4096

1638

4

6553

6

2621

44

1048

576

Packet size (bytes)

Ban

dw

idth

(M

B/s

)

Bandwidth: Madeleine II/BIP

0

20

40

60

80

100

120

4 16 64 256

1024

4096

1638

4

6553

6

2621

44

1048

576

Packet size (bytes)

Ban

dw

idth

(M

B/s

)

SISCI/SCI

Latency: Madeleine II/SCI

0123456789

10

0 64 128

Packet size (bytes)

Lat

ency

(µ

s)

Latency: Madeleine II/SCI

0123456789

10

0 64 128

Packet size (bytes)

Lat

ency

(µ

s)

SISCI/SCI

Bandwidth: Madeleine II/SCI

0

10

20

30

40

50

60

70

80

90

1 4 16 64 256

1024

4096

1638

4

6553

6

2621

44

1048

576

4194

304

1,7E

+07

Packet size (bytes)

Ban

dw

idth

(M

B/s

)

Bandwidth: Madeleine II/SCI

0

10

20

30

40

50

60

70

80

90

1 4 16 64 256

1024

4096

1638

4

6553

6

2621

44

1048

576

4194

304

1,7E

+07

Packet size (bytes)

Ban

dw

idth

(M

B/s

)

Quelques résultats

Latence 7 µs sur BIP/Myrinet 4 µs sur SISCI/SCI

Bande passante 125 Mo/s sur BIP/Myrinet 80 Mo/s sur SISCI/SCI

Migration (PM2) 24 µs sur SISCI/SCI 52 µs sur BIP/Myrinet

MPICH/Madeleine II

MPICH: general-purpose portable MPI implementation well-defined protocol interface Abstract Device

Madeleine: cluster-specific high-performance communication generic structure available on Gigabit networks highly optimized implementation

The best of both worlds! Madeleine as a MPICH device

MPICH/Madeleine II

MPI API

ADI

ProtocolInterface

Generic part (collective operations, context/group management, ...)

Generic ADI code, datatype management, request queues management

SMP_PLUG device

intra-node communication

CH_SELF device

self communication

CH_MAD device

inter-node communication

polling loopseager protocol rendez-vous-

protocol

Madeleine II

multi-protocol management

Fast-Ethernet SCI Myrinet

TCP SISCI BIP

Latency

Comparison: various MPI/SCI implementations

0

5

10

15

20

25

30

35

40

1 10 100 1000

Packet size (bytes)

Lat

ency

(µ

s)

SCI-MPICH

SCA-MPI

MPI/ MadII/ SCI

Comparison: various MPI/SCI implementations

0

5

10

15

20

25

30

35

40

1 10 100 1000

Packet size (bytes)

Lat

ency

(µ

s)

SCI-MPICH

SCA-MPI

MPI/ MadII/ SCI

Bandwidth

Comparison: various MPI/SCI implementations

0

10

20

30

40

50

60

70

80

1 4 16 64 256

1024

4096

1638

4

6553

6

2621

44

1048

576

Packet size (bytes)

Ban

dw

idth

(M

B/s

)

SCI-MPICH

SCA-MPI

MPI/ MadII/ SCI

Comparison: various MPI/SCI implementations

0

10

20

30

40

50

60

70

80

1 4 16 64 256

1024

4096

1638

4

6553

6

2621

44

1048

576

Packet size (bytes)

Ban

dw

idth

(M

B/s

)

SCI-MPICH

SCA-MPI

MPI/ MadII/ SCI

MultithreadingDistribué

Vers des communicationssur grappes de grappes…

Objectifs

Support des grappes de grappes Communications hétérogènes Transparence Efficacité du routage sur les machines

« passerelles » Minimisation des copies Maintien du débit par techniques de pipeline Utilisation des threads !

PC/MyrinetPC/SCI

Réseau rapide

PACX-MPI

2 nœuds sacrifiés pour les communications

Transparence pour l’application

Protocole TCP/IP entre les grappes

MPI MPI

TCP

Globus

Principe : Appel de Procédure à Distance

Librairie de communication : Nexus Multiprotocole Multithreading non nécessairement préemptif La passerelle est sacrifiée

Tout est à faire par l’utilisateur Pas de gestion explicite des grappes de

grappes

Pas adapté au problème

Madeleine II

Bibliothèque de communication Multiprotocole Canaux de communication

indépendants Un canal correspond à un adaptateur

réseau

Canal TCP

Canal TCP

Canal SCI

Structure interne

Couche générique de gestion de tampons

Couche de portabilité avec les protocoles

Réseau

Application

MGT1 MGTnMGT2

MT1 MTnMT2

Structure interne

MGT1 MGTn

MT1 MTn

Réseau

Application

Couche de

gestion de tampons

Couche de portabilité

Aiguillage

Sélection

MGT1 MGTn

MT1 MTn

Réseau

Application

Aiguillage

Sélection

Structure (suite)

Organisation des données Madeleine : données globales Driver : spécifique à un protocole Adapter : virtualisation d’une carte

réseau Channel : isolation des communications Connection : connexion point à point Link : virtualisation d’une méthode de

transfert

Ce qui manque

Utilisation de réseaux qui ne sont pas présents sur tous les nœuds

Envoi de messages entre des machines non directement reliées

SCI Myrinet

Intégration dans Madeleine

MTs : pas portable

MGTs : problèmes de conversion

Au-dessus : perte d’efficacité

Application

MGT1 MGT2 MGTn

MT1 MT2

Réseau

Solution retenue

MT générique entre les MTs et les MGTs

Pas de MGT au niveau de la passerelle

MT générique

MGT1 MGT2 MGTn

MT1 MT2

Réseau

Application

Canaux virtuels

Contiennent plusieurs canaux réels

Permettent de séparer les messages à retransmettre des messages normaux (canaux réels différents)

1 2 3 4

Canaux SCI

Canaux Myrinet

Canal spécial

Canal normal

Canal

virtuel

Réactivité et parallélisme

Retransmission des messages par des threads dédiés Une paire de threads par réseau

physique Mécanisme de pipeline

Réception des messages normaux sur la passerelle Pas d’informations à priori sur la

provenance Threads de scrutation

Principe de la passerelle

Application

Threads de

retransmission

Thread de scrutation

SCI

Myrinet

Tests de performances

Ping-pong entre 2 machines séparées par une passerelle

SCI Myrinet

321

Évaluation

SCI

BIP

BIP/SCI Avec une passerelle

Bande passante

80 Mo/s

116 Mo/s

41 Mo/s

Latence

5,3 μs

7,8 μs

32,5 μs

MultithreadingDistribué

Intégration des threadset des communications

Progression des communications

Problème Comment assurer la progression des

communications ?

procproc proc proc

réseau

Scrutation et interruptions

La scrutation est nécessaire API réseau ne fournissant pas d’appels

bloquants OS ne fournissant pas “d’activations”

Problème Fréquence difficile à assurer Coûteux en présence de multiple “pollers ”

Les interruptions sont nécessaires Réactivité

Problème Outils de synchronisation “interrupt safe” ?

Support de l’ordonnanceur

Ordonnanceur = serveur de scrutation Choix de la méthode d’accès

(scrutation/intr.) Support pour la scrutation

Fréquence contrôlée Factorisation des scrutations multiples

Support pour les interruptions Utilisation possible des activations Verrous spécifiques « interrupt-safe »

Scrutation par l’ordonnanceur

Ordonnanceurdes threads

Création d’une catégoriede polling (ex: MPI), assignation d’une fréquence et enregistrement de callbacks.

Polling jobsqueue

MPI

MPI_IsendMarcel_poll

Chaque thread candidat à une opération de polling adresse une requête à l’ordonnanceur et se bloque.

MPI_IrecvMarcel_poll

callbackcallback

Régulièrement, l’ordonnanceur appelle la fonction de scrutation définie par l’utilisateur...

Polling( )

MultithreadingDistribué

L’environnement PM2

PM2 : architecture logicielle

Légende Marcel : noyau de processus légers Madeleine : module de communication

Marcel PM2 Madeleine

Architecture (grappes, machines parallèles)

Unix (~10 versions)

Interface de programmation (RPC, migration, allocation iso-adresse)

Régulation HPF, C* C++//, Java

Applications

PM2PM2

MICRO-PM2MARCEL MADELEINE

Structure de PM2

API : non-threaded RPC (“packs” Madeleine), thread create, API MarcelAPI : non-threaded RPC (“packs” Madeleine), thread create, API Marcel

API : LRPC avec stubs, migration iso-adresse, DSMAPI : LRPC avec stubs, migration iso-adresse, DSM

PM2 Intrinsics

Migration LRPC “ancien style”

Iso-addr

DSM-PM2

Console

API : MICRO PM2 + PM2 IntrinsicsAPI : MICRO PM2 + PM2 Intrinsics

Structure

MultithreadingDistribué

Conclusion

Conclusion

Multithreading Exploitation efficace des architectures SMP Contrôle fin de l’ordonnancement

Conditionné par les fonctionnalités du système

Multithreading distribué Communications de type RPC

Support spécifique nécessaire

Intégration des threads et des communications Délicate !! Mieux maîtrisée si fonctionnement coopératif