Program Scheduling Based on Moldable Tasks Approach in Dynamic SMP Clusters with Communication on the Fly

Lukasz Masko, Marek Tudruj
Institute of Computer Science of the Polish Academy of Sciences

The presentation concerns parallel program graph scheduling using the concept of moldable computational tasks in a parallel architecture based on SMP processor clusters with data communication on the fly. The arcjitecture is based on dynamic (i.e. program run-time modifiable) processor clusters organized around shared memory modules. Data reads on the fly are provided in these clusters, which means that processors in a cluster can read data, which are written or read to/from a memory module through an internal cluster data exchange network. Processors switched between clusters at program run-time bring data in their data caches to be next used for reads on the fly (communication on the fly). SMP clusters implementation assumes network on chip (NoC) technology. The scheduling algorithm decomposes an initial program graph to sub-graphs, which fulfill the definition of a moldable task. The identified moldable tasks are then scheduled to NoC clusters using an algorithm with warranted schedule length. The algorithm assigns tasks to processors and inter-task shared memory communication to dynamic processor clusters, so as to obtain the minimal program execution time. It converts standard communication into reads on the fly and communication on the fly.

After having been at ID-IMAG now for 2 months, I would like to take this seminar as an opportunity to introduce some research I have been working on.  Several projects are discussed:
1)  Agent Survivability: Secret Sharing Transformation
    A model is shown that formalizes secret sharing of mobile agents as a chain constraint scheduling problem
2)  Survivability of Intelligent Transportation Systems
    A model is presented that views an ITS as a set of functionalities and component.  A survivability architecture is derived and applied to a real ITS.
3)  Low-level attack recognition
    A kernel-level attack recognition method is discussed which has been implemented in Lunix clusters.
4)  Certification of peer-to-peer applications
    If time permits, some current work of certification of applications with dependencies in the presence of possible massive attacks will be discussed.

In this talk we are going to present a new approach to the generalized tree alignment problem for large sets of genomic data. Our method is an extension of previously proposed PhylTree (PT) heuristics and is based on distributed caching. We show how PT has been parallelized and we highlight some of its properties which allowed us to apply caching. We discuss also possible applications of our approach targeted toward grid environments and distributed genbanks.

In this talk we present algorithms for scheduling and allocating parallel  jobs on commodity-based parallel supercomputers.  In this application,
whenever a parallel job is due to run, it is assigned to a  set of processors.  The objective is to choose a set of processors to  reduce the communication costs between the processors.

We first describe the algorithms that we have implemented in the Cplant System Software at Sandia National Laboratories.  We then address the more general allocation problem, giving approximation algorithms for the problem. Finally, we consider the continuous version of the processor allocation problem.


Michael A. Bender is an associate professor of computer science at SUNY Stony Brook.  His research interests include analysis of algorithms, data
structures, scheduling, parallel computing, cache- and I/O efficient computing, and robot algorithms. He has coauthored over 60 articles on
these and other topics in computer science. Professor Bender received his BA in Applied Mathematics from Harvard University in 1992 and obtained a DEA in Computer Science from the Ecole Normale Superieure de Lyon, France in 1993.  He completed a PhD on Scheduling Algorithms from Harvard University in 1998.     

This paper analyses of the way jobs are distributed in a computational grid environment where the brokering is done in such a way that each Computing Element has a probability to be chosen proportionnal to its number of CPUs and its speedup. We give the asymptotic behaviour for several metrics (queue sizes, slowdown ...) in several cases, or, in some case, an approximation of this behaviour.

La puissance de calcul offerte par les grilles de calcul est très intéressante pour les applications de couplage code. Cependant, il  apparaît nécessaire de masquer la complexité des grilles de calcul par un modèle de programmation adéquat tout en permettant une exécution  efficace. Les modèles de composant logiciels offrent un cadre prometteur pour gérer cette complexité. Cependant, certaines particularités des applications et/ou des grilles doivent être prises en compte. Par exemple, les applications visées sont typiquement parallèles. Une direction de recherche consiste donc à proposer des modèles de composant permettant de définir des composants parallèles. Certains d'entre eux supportent des redistributions de données lors des communications entre composants. Un autre exemple de la spécificité des grilles concerne la gestion des machines. Ainsi, les modèles de déploiement des composants logiciels peuvent être spécialisés pour rechercher des ressources pertinentes.

Cet exposé introduit la problématique de la programmation des grilles de calcul pour les applications de couplage de code et la réponse apportée par les modèles de composants logiciels ainsi que le support à l'exécution requis.

Les méthodes directes de résolution de systèmes linéaires creux sont connues pour leurs besoins mémoire importants qui peuvent constituer une barrière au traitement de problèmes de grande taille. De ce fait, les travaux présentés dans cet exposé porteront sur l'amélioration du comportement mémoire tout en gardant de bonnes performances. Ceci sera fait en concevant de nouvelles heuristiques d'ordonnancement. La méthode parallèle étudiée (en l'occurrence la méthode multifrontale) repose sur une combinaison d'approches d'ordonnancement statique et dynamique visant principalement l'obtention de bonnes performances lors de la factorisation. Les ordonnanceurs dynamiques sur lesquels nous insisterons sont distribués et locaux à chacun des processeurs prenant part à la factorisation. Ils requièrent des informations relatives à l'état des autres processeurs (charge, mémoire disponible,...) pour pouvoir prendre des décisions. Ainsi, une étude comparative de deux familles d'algorithmes distribués dont l'objectif est de fournir ces informations sera présentée. Les algorithmes étudiés sont d'une part les algorithmes "à la demande" reposant sur le concept de photographie d'un système distribué (distributed snapshot), et d'autre part des mécanismes visant le maintien de la vue du système au niveau de chacun des processeurs. Cette étude a été effectuée sur un solveur parallèle implémentant une méthode multifrontale (MUMPS). La deuxième partie de l'exposé portera sur la présentation de techniques d'ordonnancement dynamique ayant un double objectif de bonnes performances et de bon comportement mémoire. Ainsi, un ordonnaceur dynamique basé sur l'équilibrage de charge avec contraintes mémoire (mémoire disponible, taille des tampons de communication, etc ...) a été proposé.  De plus, la souplesse offerte par ce nouvel ordonnanceur a permis d'améliorer le processus d'estimation de la mémoire nécessaire au déroulement de la factorisation. Notons cependant que la réduction de la taille de la mémoire (estimée) nécessite l'ajout de nouvelles contraintes mémoire dans nos ordonnanceurs dynamiques. Une étude expérimentales illustrant l'intérêt de ce nouveau type d'ordonnanceurs aussi bien en terme de temps de factorisation qu'en terme de comportement mémoire sera présentée.
 

Je présenterai les résultats de mes travaux sur des stratégies d'ordonnancement et d'équilibrage de charge pour des plates-formes hétérogènes distribuées. Le problème est d'ordonnancer un ensemble de tâches indépendantes afin d'en réduire le temps total d'exécution. Ces tâches utilisent des
données d'entrée qui peuvent être partagées : chaque tâche peut utiliser plusieurs données, et chaque donnée peut être utilisée par plusieurs tâches. Les tâches ont des durées d'exécution différentes, et les données ont des tailles différentes. Toute la difficulté est de réussir à placer sur un même processeur des tâches partageant des données, tout en conservant un bon équilibrage de la charge des différents processeurs.

Le problème étudié est progressivement généralisé au cours de la présentation. Je me limite, dans un premier temps, au cas simple où il n'y a pas de partage de données, où les tailles des tâches et des données sont homogènes, et où la plate-forme est de type maître-esclave. Le partage des données est ensuite introduit, ainsi que l'hétérogénéité pour les tailles des tâches et des données. Le modèle de plate-forme est finalement généralisé à un ensemble décentralisé de serveurs reliés entre eux par un réseau d'interconnexion quelconque.

La complexité théorique du problème est étudiée. Pour les cas simples, des algorithmes calculant une solution optimale sont proposés, puis validés par des résultats expérimentaux avec une application scientifique réelle. Pour les cas plus complexes, nous proposons de nouvelles heuristiques pour résoudre le problème d'ordonnancement. Ces nouvelles heuristiques, ainsi que des heuristiques classiques comme min-min et sufferage, sont comparées entre elles à l'aide de nombreuses simulations. Nous montrons ainsi que nos nouvelles heuristiques réussissent à obtenir des performances aussi bonnes que les heuristiques classiques, tout en ayant une complexité algorithmique d'un ordre de grandeur plus faible.

Les détecteurs de défaillances, introduits par Chandra et Toueg,  s'imposent comme un élément de base dans la construction d'applications réparties.
Cet exposé décrit la conception et la réalisation d'un service de détection de défaillances adaptable optimisé pour les architectures de
type grilles de calcul.
Le premier aspect de ce travail consiste à optimiser la qualité de service de la détection et de concevoir une architecture permettant au
détecteur d'adapter son comportement en fonction de son environnement : les demandes des applications utilisatrices et de l'état courant du réseau... La deuxième spécificité est l'organisation hiérarchique de notre service qui réduit ainsi sa charge induite et donc permet son utilisation sur un grand nombre de machines.

Le modèle BSP (Bulk Synchronous Parallelism) est un modèle de
programmation data-parallèle explicite qui propose un modèle de coût
simple.

Dans cet exposé, je vous présenterai succintement deux machines
virtuelles pour le langage BSML qui associe BSP, la programmation
fonctionnelle et l'estimation des performances.  Puis je parlerai plus
largement de BSPA (Bulk Synchronous Process Algebra) : une algèbre de
processus étendue pour préserver les caractéristiques de programmes
BSP, ainsi que son modèle de coût associé. Je donnerai quelques
exemples d'application à des problèmes d'ordonnancement posés par
l'informatique globalisée ou meta-computing.

Enfin je montrerai comment le modèle de coût associé à BSPA peut être
associé à d'autres algèbres de processus. Je parlerai donc d'un modèle
de dépense de ressources mémoire pour l'algèbre de processus SPPA
dediée aux protocoles cryptographiques et en particulier au protocole
TCP.