of 26 /26
Étude d’un protocole de partage de travail entre systèmes Pair à Pair Université de Versailles Saint Quentin en Yvelines DEA MISI Option: Architecture haute performance Stage réalisé par: Khaled BENCHERIF sous la direction de: Olivier RICHARD

Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Embed Size (px)

DESCRIPTION

Université de Versailles Saint Quentin en Yvelines. DEA MISI Option: Architecture haute performance. Étude d’un protocole de partage de travail entre systèmes Pair à Pair. Stage réalisé par: Khaled BENCHERIF sous la direction de: Olivier RICHARD. Plan. Le contexte du stage - PowerPoint PPT Presentation

Citation preview

Page 1: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Université de Versailles Saint Quentin en YvelinesDEA MISI

Option: Architecture haute performance

Stage réalisé par:

Khaled BENCHERIF

sous la direction de: Olivier RICHARD

Page 2: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

• Le contexte du stage

• Les motivations des systèmes Pair à Pair

• L’état de l’art Les systèmes P2P existants Les algorithmes d’équilibrage de charge

• La conception et l’implantation

• Les expériences et l’évaluation

• Conclusion et perspectives

Plan

Page 3: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

• Le calcul parallèle évolue.

• Les supercalculateurs coûteux.

• L’évolution d ’Internet (Démocratisation du web).

• L’amélioration des capacités des machines connectées à des réseaux de plus en plus performants.

• La sous utilisation des machines.

La naissance d ’un nouveau concept de l’algorithme parallèle distribuée:

Les systèmes Pair à Pair.

Le contexte général

Page 4: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Les systèmes Pair à Pair

• Faire coopérer plusieurs machines pour résoudre un problème.

• Les machines connectées peuvent être très différentes (Hétérogènes).Supercalculateurs, PC, Téléphones portables,...

• Reliées entre elles par un réseau étendu (WAN).

• L’interface dit être unique et transparente pour l ’utilisateur

Exemples : SETI@home, Distributed.net, et beaucoup d ’autres

variation des débits et disparité des machines.

Page 5: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Les motivations du Pair à Pair

• Nombre important de ressources connectées en permanence à Internet.

• Évolution des capacités des ressources: machines, le réseau (bande

passante, latence).

• Sous utilisation de capacités de calcul et de stockage des machines

connectées à Internet.

• Applications multi paramètres (les simulations).

Page 6: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Propriétés recherchées des systèmes Pair à Pair

• La sécurité (authentification, sûreté)

• L’interactivité

Aspects techniques invisibles à l’utilisateur

• Répartition de charge

• Tolérance aux pannes

• Une meilleur utilisation des ressources

• Le passage à l’échelle

• L’auto organisation dynamique

• La sécurité des calcul (triches)

Importantes pour l’utilisateur

Page 7: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Problématique

Du partage de charge coopération entre représentants de communauté Pair à Pair

ReprésentantTâcheRessource disponible

Page 8: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Positionnement du travail

• L’exploitation à grande échelle des ressources reliées à Internet.

• Équilibrer la charge entre systèmes de calcul global.

• Implanter le partage de travail entre serveurs d’XtremWeb.

• Évaluer l’échange de tâches.

Page 9: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Démarche suivie

• Principe des systèmes Pair à Pair.

• Conception de la solution.

• Étudier les systèmes Pair à Pair existants.

• Étudier les algorithmes d’équilibrage de charge.

• Étudier XtremWeb en détail (installer, tester, examiner les sources).

• Implanter le vol de tâche.

• Évaluer les performances.

Page 10: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

État de l’art

• Les plates formes Pair à Pair existantes

• Les algorithmes d’équilibrage de charge (vol de tâche)

Page 11: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Système P2P

Calcul global documents

CentraliséDistribué

DistribuéIndexation, routage

CentraliséIndexation

Partage, échange Stockage persistant

Classification des systèmes globaux

Serv

ice

Arc

hite

ctur

e

OceanStore

Gnutella

Chord, FreeNet

Napster

Seti@HomeXtremWeb

Page 12: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Équilibrage de charge par vol de tâche

La charge des machines dans un système distribué peut être inégale

Amélioration des performances et exploitation des ressources disponibles

Prendre en considération:

1. La charge des processeurs

2. La vitesse d ’exécution sur les nœuds

3. Le temps de transfert des tâches

BUT:

Page 13: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Classe des algorithmes d’équilibrage de charge

• Statiques: cycliques, probabilistes...

• Dynamiques: État du système.

Collecte + stockage de données surcoût.

• Adaptatifs: Changement de politique, changement de paramètres.

Page 14: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Quelques Algorithmes d’équilibrage de charge

• Le vol de tâche aléatoire (Random Stealing RS)

• L’envoi préalable aléatoire (Random Pushing RP)

• Le vol de tâche hiérarchique (Cluster- aware Hierarchical Stealing CHS)

• Le vol de tâche selon la charge (Cluster-aware Load-based Stealing CLS)

• Vol de tâche aléatoire avec prise en considération du cluster : (Cluster-

aware Random Stealing CRS)

Page 15: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Présentation d ’XtremWeb

Le client soumet un travail au serveur.

Le serveur gère les tâches et les affecte aux worker

Le worker fourni des ressources de calculs pour exécuter les tâches qu’il a récupérées du serveur.

Le Result Collector sert à stocker les résultats envoyés par un worker qui a fini son traitement.

WAN

Serveur Pair à Pair

PC worker/Client

PC worker/Client PC worker/Client

PC worker/Client

PC worker/Client

Page 16: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Ensemble d’applications

Ensemble des tâches

Ensemble des résultats

Statistiques

Base de DonnéesSélection des tâchesGestionnaire des

priorités

Scheduleur Collecteur de résultats

Couche de communication

Java-RMI / XMLRPC TCP SSL

Tâches

Résultat

Serveur HTTP

Requêtes du Client

Requêtes du Worker

Soumettre des tâchesRécupération des résultats

Pour une tâche et un hôte donnés :- Sélectionner le binaire et les paramètres de l’application.

- MAJ des infos de statistiques.

- Sauvegarder les résultats.

Architecture du serveur XtremWeb

Page 17: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Architecture du Worker XtremWeb

Contrôleur d’activité

Contrôle

Les threads démons

Contrôleur d’activité

Alive

Requête de fin de tâche

Mode utilisateurMode worker

Page 18: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Vol de tâches entre serveurs XtremWeb

No work

workRequest

workRequest

workRequest

Tâche

Tâche

Résultat

Résultat

Page 19: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Vol de tâches par les workers XtremWeb

@ des serveurs

workRequest

No work

workRequest

hostRegister

workRequest

Tâche

Résultat

Page 20: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

L’impact de l’équilibrage de charge

Exécution d ’XW sans équilibrage de charge

Exécution d ’XW avec équilibrage de charge

Rmq: Le vol de tâche est synchrone

Page 21: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Le surcoût de l’équilibrage de charge

Temps d’exécution total avec et sans équilibrage de charge

Exécution d ’XW avec équilibrage de charge

Page 22: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Temps d’attente pour la réception d’une tâche

Le vol de tâche est synchrone

Page 23: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Conclusion

• Une taxonomie des systèmes Pair à Pair. Service, architecture et l’échelle

• Deux algorithmes de distribution de charge: Vol de tâche entre serveurs.

Vol de tâche par le worker.

• Une nouvelle architecture d’XtremWeb.

• Evaluation des algorithmes proposés. Tâches à gros grains.

Surcoût dépend de: nombre, taille des tâches et le temps de recherche d ’une

tâche .

Diminuer la charge sur un seul noeud.

Exploiter toutes les ressources disponibles.

Améliorer le temps d’exécution global.

Page 24: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Perspectives (1)

• Maximiser l’exploitation des ressources par:

L’optimisation et l’amélioration des algorithmes de distribution de charge.

L’atténuation de la complexité de ces algorithmes.

• Notre algorithme fait du vol de tâche synchrone:

L’étendre pour fait du vol de tâche asynchrone (récupérer plus d’une tâche,

prévoire la disponibilité des ressources).

Implanter le deuxième algorithme et les comparer.

Tester avec des application réelles, et dans des conditions variables de charge.

Page 25: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

• Proposer de nouvelles architectures pour les systèmes Pair à Pair.

• La coopération entre communautés Pair à Pair peut s’étendre à un

modèle économique.

• Les systèmes Pair à Pair ouvrent la voie à beaucoup d ’axes de

recherche: Le passage à l ’échelle, la tolérance aux pannes, l ’hétérogénéité, la

sécurité...

Perspectives (2)

Page 26: Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Étude d’un protocole de partage de travail entre systèmes Pair à Pair

Université de Versailles Saint Quentin en YvelinesDEA MISI

Option: Architecture haute performance

Stage réalisé par:

Khaled BENCHERIF

sous la direction de: Olivier RICHARD