See discussions, stats, and author profiles for this publication at: https://ww

See discussions, stats, and author profiles for this publication at: https://www.researchgate.net/publication/281047183 Placement of tasks under uncertainty on massively multicore architectures Article · November 2013 CITATIONS 0 READS 6 1 author: Some of the authors of this publication are also working on these related projects: Smart Cities View project Konfido View project Oana Stan Atomic Energy and Alternative Energies Commission 28 PUBLICATIONS 108 CITATIONS SEE PROFILE All content following this page was uploaded by Oana Stan on 09 September 2020. The user has requested enhancement of the downloaded file. HAL Id: tel-01127570 https://tel.archives-ouvertes.fr/tel-01127570 Submitted on 7 Mar 2015 HAL is a multi-disciplinary open access archive for the deposit and dissemination of sci- entific research documents, whether they are pub- lished or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers. L’archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d’enseignement et de recherche français ou étrangers, des laboratoires publics ou privés. Placement of tasks under uncertainty on massively multicore architectures Oana Stan To cite this version: Oana Stan. Placement of tasks under uncertainty on massively multicore architectures. Computer Science [cs]. Université de Technologie de Compiègne, 2013. English. ￿NNT : 2013COMP2116￿. ￿tel- 01127570￿ Par Oana STAN Thèse présentée pour l’obtention du grade de Docteur de l’UTC Placement of tasks under uncertainty on massively multicore architectures Soutenue le 15 novembre 2013 Spécialité : Technologies de l’Information et des Systèmes D2116 UNIVERSITÉ DE TECHNOLOGIE DE COMPIÈGNE PLACEMENT OF TASKS UNDER UNCERTAINTY ON MASSIVELY MULTICORE ARCHITECTURES THÈSE DE DOCTORAT pour l'obtention du grade de docteur de l'Université de Technologie de Compiègne spécialité Technologies de l'Information et des Systèmes présentée et soutenue publiquement par Mme. Oana STAN le 15 novembre 2013 devant le jury composé de : Directeurs de thèse : Jacques Carlier Professeur, Université de Technologie de Compiègne Dritan Nace Professeur, Université de Technologie de Compiègne Rapporteurs : Alix Munier Professeur, Université Paris VI Walid Ben-Ameur Professeur, Institut TELECOM Sud-Paris Encadrant : Renaud Sirdey Ingénieur-chercheur, CEA, LIST This page is intentionally blank ! To my father This page is intentionally blank ! Acknowledgements First of all, I want to address my grateful acknowledgments to Mr. Jacques CARLIER and Mr. Dritan NACE, professors at Université de Technologie de Com- piègne, for directing my research work and guiding my steps with their eminent expertise in the eld of combinatorial optimization. Thanks to their constant and careful supervision, I learned the good practices required in order to ful ll a high quality research and I was able to nish my Phd dissertation in time without any further delay. My foremost appreciation also goes to Mr. Renaud SIRDEY, my Phd super- visor at CEA, for his permanent support, his endless ideas helping me progress during these last three years, for the con dence he had in me and for his contagious enthusiasm for Science. I wish to thank Mrs. Alix MUNIER, professor at Université Paris 6, and Mr. Walid BEN-AMEUR, professor at Telecom SudParis, for honoring me in accepting to report this thesis and for their valuable remarks and suggestions. Also, I want to address my thanks to Mr. Aziz MOUKRIM, professor at Université de Technologie de Compiègne, for accepting to be president of the examining committee. I want to address my gratitude to all those who made possible this work. I especially think of the members of LaSTRE laboratory, from CEA: the coee breaks, the discussions, the advices, the after-works together not only made this an enjoyable professional experience, they were also important for my personal growth and enrichment. A grateful thought goes to my Phd old fellows Nicolas, Ilias and Thomas for the good moments during the lunches we had together at Resto 1... Also, many thanks to my deskmates from the Phd cage at NanoInnov - Vincent, Simon, Safae, Karl, Moez, the two Amira - for all their help, for all the sweets we shared and for bearing with me and with my continuous complains - J'en ai marre, Ca marche pas!!!, Oh-la-la! just to name a few... A special thought for The Three Musketeers- Pascal, Sergiu and Julien - thanks to their jokes and their support, overcoming the inherent moments di cult of a Phd was less complicated. I want to express my acknowledgments to all those who helped improve this thesis, by re-readings or by providing experimental data: Safae, Vincent, Karl, Pascal, Julien, Sergiu (again) and also Cyril, Loïc, Paul and Lilia. Many thanks to my friends outside work - Linda, Corina, Mihaela & Marius, Valentin, Anca - due to their presence, I managed to keep my head outside the box of my Phd topic, see the outside world and realize that there is a life out there. Finally, my heartfelt thanks my family, for their comforting words and their support, from my earliest childhood until now. It's also thanks to them that I became what I am now and I succeeded to get so far. I wish to thank my mother for always being beside me, my aunt (Monica) and my grandmothers for their pieces of advice as well as my little cousins (Vladut and Alex) for their unconditional love. I would like to pay tribute to my father, which was the rst one to persuade me to follow this path and which would have been happy to live this moment. Last, but not least, my warmest thanks to Andrei, my constant supporter, for his kindness and his love, for his help and for the lost weekends, and for simply standing beside me, while facing the ups and downs of being a Phd student. Résumé Ce travail de thèse de doctorat est dédié à l'étude de problèmes d'optimisation combinatoire du domaine des architectures massivement parallèles avec la prise en compte des données incertaines tels que les temps d'exécution. On s'intéresse aux programmes sous contraintes probabilistes dont l'objectif est de trouver la meilleure solution qui soit réalisable avec un niveau de probabilité minimal garanti. Une analyse qualitative des données incertaines à traiter (variables aléatoires dépendantes, multimodales, multidimensionnelles, di ciles à caractériser avec des lois de distribution usuelles), nous a conduit à concevoir une méthode qui est non paramétrique, intitulée  approche binomiale robuste . Elle est valable quelle que soit la loi jointe et s'appuie sur l'optimisation robuste et sur des tests d'hypothèse statistique. On propose ensuite une méthodologie pour adapter des algorithmes de résolution de type approchée pour résoudre des problèmes stochastiques en intégrant l'approche binomiale robuste a n de véri er la réalisabilité d'une solution. La per- tinence pratique de notre démarche est en n validée à travers deux problèmes issus de la compilation des applications de type ot de données pour les architectures manycore. Le premier problème traite du partitionnement stochastique de réseaux de pro- cessus sur un ensemble xé de n÷uds, en prenant en compte la charge de chaque n÷ud et les incertitudes aectant les poids des processus. A n de trouver des solu- tions robustes, un algorithme par construction progressive à démarrages multiples a été proposé ce qui a permis d'évaluer le coût des solutions et le gain en robustesse par rapport aux solutions déterministes du même problème. Le deuxième problème consiste à traiter de manière globale le placement et le routage des applications de type ot de données sur une architecture clustérisée. L'objectif est de placer les processus sur les clusters en s'assurant de la réalisabilité du routage des communications entre les tâches. Une heuristique de type GRASP a été conçue pour le cas déterministe, puis adaptée au cas stochastique clusterisé. 1 Abstract This PhD thesis is devoted to the study of combinatorial optimization problems related to massively parallel embedded architectures when taking into account un- certain data (e.g. execution time). Our focus is on chance constrained programs with the objective of nding the best solution which is feasible with a preset probability guarantee. A qualitative analysis of the uncertain data we have to treat (dependent random variables, multimodal, multidimensional, di cult to characterize through classical distributions) has lead us to design a non parametric method, the so-called robust binomial approach, valid whatever the joint distribution and which is based on ro- bust optimization and statistical hypothesis testing. We also propose a methodology for adapting approximate algorithms for solving stochastic problems by integrating the robust binomial approach when verifying for solution feasibility. The practical relevance of our approach is validated through two problems arising in the compila- tion of data ow application for manycore platforms. The rst problem treats the stochastic partitioning of networks of processes on a xed set of nodes, by taking into account the load of each node and the uncertainty aecting the weight of the processes. For nding stochastic solutions, a semi-greedy iterative algorithm has been proposed which allowed measuring the robustness and cost of the solutions with regard to those for the deterministic version of the problem. The second problem consists in studying the global placement uploads/Science et Technologie/ placement-of-tasks-under-uncertainty-on-massively.pdf

Tags
Science et Technologiewhich stochastic optimization problem deterministic
Documents similaires
  • 17
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager