http://hdl.handle.net/2332/462 Tue, 18 Jun 2013 06:51:40 GMT 2013-06-18T06:51:40Z http://hdl.handle.net/2332/1346 Minimizing the stretch when scheduling flows of divisible requests Legrand, Arnaud; Su, Alan; Vivien, Frédéric; Laboratoire de l'informatique du parallélisme (eng) In this paper, we consider the problem of scheduling distributed biological sequence comparison applications. This problem lies in the divisible load framework with negligible communication costs. Thus far, very few results have been proposed in this model. We discuss and select relevant metrics for this framework: namely max-stretch and sum-stretch. We explain the relationship between our model and the preemptive uni-processor case, and we show how to extend algorithms that have been proposed in the literature for the uni-processor model to the divisible multi-processor problem domain. We recall known results on closely related problems, we show how to minimize the max-stretch on unrelated machines either in the divisible load model or with preemption, we derive new lower bounds on the competitive ratio of any on-line algorithm, we present new competitiveness results for existing algorithms, and we develop several new on-line heuristics. We also address the Pareto optimization of max-stretch. Then, we extensively study the performance of these algorithms and heuristics in realistic scenarios. Our study shows that all previously proposed guaranteed heuristics for max-stretch for the uni-processor model prove to be inefficient in practice. In contrast, we show our on-line algorithms based on linear programming to be near-optimal solutions for maxstretch. Our study also clearly suggests heuristics that are efficient for both metrics, although a combined optimization is in theory not possible in the general case. (fre) Dans ce rapport, nous nous intéressons à l’ordonnancement d’applications comparant de manière distribuée des séquences biologiques. Ce problème se situe dans le domaine des tâches divisibles avec coûts de communications négligeables. Jusqu’à présent, très peu de résultats ont été publiés pour ce modèle. Nous discutons et sélectionnons des métriques appropriées pour notre cadre de travail, à savoir le max-stretch et le sum-stretch. Nous expliquons les relations entre notre modèle et le cadre mono-processeur avec préemption, et nous montrons comment étendre au cadre des tâches divisibles sur multi-processeur les algorithmes proposés dans la littérature pour le cas mono-processeur avec préemption. Nous rappelons les résultats connus pour des problématiques proches, nous montrons comment minimiser le max-stretch sur des machines non corrélées (que les tâches soient divisibles ou simplement préemptibles), nous obtenons de nouvelles bornes inférieures de compétitivité pour tout algorithme on-line, nous présentons de nouveaux résultats de compétitivité pour des algorithmes de la littérature, et nous proposons de nouvelles heuristiques on-line. Nous nous intéressons également au problème de la minimisation Pareto du max-stretch. Ensuite, nous étudions, de manière extensive, les performances de tous ces algorithmes et de toutes ces heuristiques, et ce dans un cadre réaliste. Notre étude montre que les solutions garanties existantes minimisant le max-stretch sur un processeur sont inefficaces dans notre cadre de travail. Cependant, nous montrons que nos algorithmes on-line basés sur la programmation linéaire ont des performances proches de l’optimal pour le max-stretch. En outre, notre étude suggère clairement les heuristiques qui sont efficaces pour les deux métriques, bien que l’optimisation simultanée pour ces deux métriques soit en théorie impossible dans le cas général. 62 pages, tableaux, 37 références bibliographiques Thu, 31 Jan 2008 23:00:00 GMT http://hdl.handle.net/2332/1346 2008-01-31T23:00:00Z http://hdl.handle.net/2332/1271 Panorama des biotechnologies et de leurs applications aux médicaments des années 2000 à 2005 Tisserand-Bedri, Françoise; Hansen, Catherine; Fabry, Cécilia; Tramonti, Alain; Institut de l'information scientifique et technique Les biotechnologies, si elles s’inscrivent dans le cadre d’un développement durable conciliant enjeux économiques et éthiques, semblent promises à une forte croissance. La mise en place d’un cadre statistique international devrait accompagner leur essor, facilitant le suivi et les comparaisons. Les études réalisées font le constat d’un retard de la France et plus globalement de l’Europe par rapport aux Etats-Unis. Le CNRS via son implication dans le Genopole® d’Evry, ses partenariats industriels, son soutien à la création de sociétés et le dynamisme de ses laboratoires est un acteur important de ce domaine où « le continuum formation, recherche et innovation » se trouve être un facteur clé pour réussir. Pour l’industrie pharmaceutique, les biotechnologies sont considérées comme une source fondamentale d’innovation appliquée aux différents stades de l’élaboration d’un médicament : génomique structurale et fonctionnelle, thérapie génique, pharmacogénomique... Elles tendent vers le développement de traitements ciblés, plus efficaces, moins toxiques et adaptés à chacun. La recherche dans ces différentes thématiques nécessite une approche multidisciplinaire et la mise en place de partenariats entre les acteurs. Le CNRS de part sa taille et ses prédispositions devrait au niveau français et européen jouer un rôle majeur. 44 pages, 99 références biographiques, webographie disséminée en bas de pages Tue, 28 Feb 2006 23:00:00 GMT http://hdl.handle.net/2332/1271 2006-02-28T23:00:00Z http://hdl.handle.net/2332/945 Minimizing the stretch when scheduling flows of divisible requests Legrand, Arnaud; Su, Alan; Vivien, Frédéric; Laboratoire de l'informatique du parallélisme (eng) In this paper, we consider the problem of scheduling distributed biological sequence comparison applications. This problem lies in the divisible load framework with negligible communication costs. Thus far, very few results have been proposed in this model. We discuss and select relevant metrics for this framework: namely max-stretch and sum-stretch. We explain the relationship between our model and the preemptive uni-processor case, and we show how to extend algorithms that have been proposed in the literature for the uni-processor model to the divisible multi-processor problem domain. We recall known results on closely related problems, we show how to minimize the max-stretch on unrelated machines either in the divisible load model or with preemption, we derive new lower bounds on the competitive ratio of any on-line algorithm, we present new competitiveness results for existing algorithms, and we develop several new on-line heuristics. We also address the Pareto optimization of max-stretch. Then, we extensively study the performance of these algorithms and heuristics in realistic scenarios. Our study shows that all previously proposed guaranteed heuristics for max-stretch for the uni-processor model prove to be inefficient in practice. In contrast, we show our on-line algorithms based on linear programming to be near-optimal solutions for maxstretch. Our study also clearly suggests heuristics that are efficient for both metrics, although a combined optimization is in theory not possible in the general case. (fre) Dans ce rapport, nous nous intéressons à l’ordonnancement d’applications comparant de manière distribuée des séquences biologiques. Ce problème se situe dans le domaine des tâches divisibles avec coûts de communications négligeables. Jusqu’à présent, très peu de résultats ont été publiés pour ce modèle. Nous discutons et sélectionnons des métriques appropriées pour notre cadre de travail, à savoir le max-stretch et le sum-stretch. Nous expliquons les relations entre notre modèle et le cadre mono-processeur avec préemption, et nous montrons comment étendre au cadre des tâches divisibles sur multi-processeur les algorithmes proposés dans la littérature pour le cas mono-processeur avec préemption. Nous rappelons les résultats connus pour des problématiques proches, nous montrons comment minimiser le max-stretch sur des machines non corrélées (que les tâches soient divisibles ou simplement préemptibles), nous obtenons de nouvelles bornes inférieures de compétitivité pour tout algorithme on-line, nous présentons de nouveaux résultats de compétitivité pour des algorithmes de la littérature, et nous proposons de nouvelles heuristiques on-line. Nous nous intéressons également au problème de la minimisation Pareto du max-stretch. Ensuite, nous étudions, de manière extensive, les performances de tous ces algorithmes et de toutes ces heuristiques, et ce dans un cadre réaliste. Notre étude montre que les solutions garanties existantes minimisant le max-stretch sur un processeur sont inefficaces dans notre cadre de travail. Cependant, nous montrons que nos algorithmes on-line basés sur la programmation linéaire ont des performances proches de l’optimal pour le max-stretch. En outre, notre étude suggère clairement les heuristiques qui sont efficaces pour les deux métriques, bien que l’optimisation simultanée pour ces deux métriques soit en théorie impossible dans le cas général. 68 pages, tableaux, graphiques, 33 références bibliographiques Sat, 30 Sep 2006 22:00:00 GMT http://hdl.handle.net/2332/945 2006-09-30T22:00:00Z