RAPPORT DE STAGE

Hazem FKAIER

J’ai effectué, pendant la période entre les 8 juin 2005 et 6 août 2005, un stage en France sur invitation de Mr. Christophe Cérin (Université de Paris 13- Laboratoire LIPN). Ce stage s’inscrit dans la préparation de ma thèse ayant pour objet le « tri sur des grilles de calcul et les problèmes de stockage reliés » co-encadrée par Mr. Mohamed Jemni et Mr. Christophe Cérin. Le stage était une occasion pour avancer sur nos travaux, améliorer nos codes et étudier un cas réel de problème de tri.

Nous avons saisie l’occasion de stage pour concevoir une application parallèle qui trie des chaînes de 100 caractères, conformément aux spécifications énoncées dans la page :

http://research.microsoft.com/barc/SortBenchmark/.

Dans cette page, sont indiqués les meilleures performances dans les compétitions Pennysort, Minute-Sort et Téra-Sort. Nous souhaitons arriver au niveau de performance de Minute-Sort 2005 : 116Go triés en 1 minute. Pour cette raison nous avons été amené à récrire notre tri parallèle et notamment à re-penser la phase de communication de manière à utiliser au mieux le réseau de communication sans risquer de le congestionner.

Pour éviter (ou repousser) le risque de congestion, il ne faut pas encombrer le réseau par beaucoup de messages en même temps. Il faut intercepter les messages aussitôt qu’ils sont envoyés. Nous avons prévu d'isoler des processeurs récepteurs en même temps que les autres font des envois pour vider le réseau.

Cette solution a réduit considérablement le temps d’exécution, et a rendu l’application plus efficace et a repoussé très loin la barrière de congestion du réseau. Ainsi, avec l'implémentation réalisée on est arrivé à des tailles de problème l’ordre de quelques centaines de mégas de clefs soit quelques dizaines de gigas d’octets, et à faire participer jusqu’à 31 processeurs (les processeurs disponibles sur la machine utilisée) avec un risque de congestion relativement réduit mais non nul. Nous proposons, dans nos futurs travaux, de l’améliorer encore pour garantir le bon déroulement quelque soit la taille du problème et quelque soit le nombre de processeurs dans le système. Une étude théorique complémentaire à cette phase expérimentale sera envisagée.

Rappel : nos algorithmes sont aussi prévus pour fonctionner en milieu hétérogène (CPU tournant a différentes vitesses)

Notre deuxième centre d’intérêt pendant ce stage, a été l’étude d’un cas réel de données scientifiques à trier et de la manière la plus efficace possible de le faire en respectant des spécificités. Nous avons étudié le cas du tri de données sismiques dans une société spécialisée dans le domaine de la géophysique : Compagnie Générale de Géophysique.

Pour des besoins de traitement des traces sismiques, les géophysiciens veulent traiter les données dans un ordre spécifique suivant un ou plusieurs critères. Pour cette raison, les traitements commencent souvent par une opération de sélection puis un tri suivant deux ou trois mots de l’entête ; ensuite le traitement proprement dit est appliqué aux objets.

L’application utilisée actuellement est une application séquentielle qui sous-utilise les ressources disponibles. Nous nous proposons, donc, de développer une application parallèle de tri multi-critère adapté à ces spécifications.

Compte tenu du fait que les données peuvent être pré ou presque triées initialement, nous pouvons profiter de cette propriété pour nous renseigner sur les critères communs entre le tri initial et le tri final. Notre but est d’extraire le plus propriétés de l’état initial pour réduire le travail à exécuter pour arriver à l’état final. Nous proposons d’appliquer un raisonnement par cas pour traiter ce problème. En effet, plusieurs cas de figures sont envisageables notamment si le tri se fait sur trois mots ce qui est souvent le cas dans la pratique.

De plus, et outre les discussions algorithmiques, d’autres considérations matérielles et architecturales sont à prendre en compte tel que le choix des machines sur lesquelles nous allons exécuter notre application parallèle, comment lire et distribuer initialement les données et l’optimisation des entrées/sorties (lectures/écritures sur disques).. etc.

Le stage à été également une opportunité pour visiter les laboratoires de recherche en informatique, suivants : LIPN à l’université de Paris Nord et LRI à Orsay (Franck Cappello), et d'échanger des idées avec leurs membres. Nous avons aussi eu l’occasion de faire des réunions de travail entre Christophe Cérin (LIPN), Michel Koskas (LAMSADE et LAMFA) et Mohamed Jemni (ESSTT).