DSpace
 

Dspace de universite Djillali Liabes de SBA >
Thèse de Doctorat en Sciences >
Informatique >

Veuillez utiliser cette adresse pour citer ce document : http://hdl.handle.net/123456789/3184

Titre: Contribution à l’optimisation d’ordonnancement de workflows dans un environnement cloud
Auteur(s): BENHAMMOUDA, Mohammed
Encadreur: MALKI, Mimoun
Mots-clés: Cloud computing
Planification des tâches
Workflow
Date de publication: 3-jan-2021
Résumé: الملخص (بالعربية) : تتكون الحوسبة السحابية ، التي تم تطويرها مبدئيًا من حوسبة الشبكة ، والحوسبة الموزعة ، والحوسبة المتوازية ، من مجموعة من الأجهزة الافتراضية المترابطة والمستخدمة ديناميكيًا والتي تم تقديمها كموارد للحوسبة. اتفاقيات مستوى الخدمة المستندة إلى الخدمة (SLAs) التي تم التوصل إليها عن طريق التفاوض بين مزود الخدمة والمستهلكين ، يُنظر إليها بشكل متزايد على أنها طريقة جديدة لاستخدام خدمات تكنولوجيا المعلومات والتخزين والشبكات عند الطلب بطريقة شفافة وفعالة. تتضمن العديد من التطبيقات العلمية في العديد من المجالات ، مثل المعلوماتية الحيوية وعلم الفلك ، العديد من المهام التي تقيدها علاقات الأولوية. يتم التعبير عن هذه التطبيقات غالبًا على أنها workflow "سير عمل" أو "تدفق عمل" ، وهي سلسلة من خطوات المعالجة (المهام) ذات الصلة ، حيث تأخذ كل خطوة بيانات الإدخال ، وتؤدي المعالجة ، وتخرج البيانات التي سيتم تمريرها إلى المستخدمين. بعد خطوات المعالجة. لسوء الحظ ، الخدمات السحابية ليست مجانية ، فاتفاقية مستوى الخدمة الموقعة بين المزود والمستخدم ستحدد السعر لدفع الموارد المستأجرة في نموذج الدفع عند الإستخدام. تعد مهام الجدولة خطوة مهمة عند تشغيل workflow في بيئة الحوسبة السحابية. يجب أن تجد خوارزمية الجدولة تخصيصًا فعالًا لمهام سير عمل المستخدم ، مما يقلل من الوقت اللازم لتنفيذ سير عمل المستخدم ويزيد من توفر الموارد السحابية إلى الحد الأقصى . بالإضافة إلى ذلك ، تعد جدولة المهام في بيئة الحوسبة السحابية مشكلة NP صعبة بشكل عام ، وتستخدم خوارزميات التحسين الاسترشادي على نطاق واسع لحل مثل هذه المشكلات في هذه الأطروحة ، نعالج مشكلة تخطيط سير العمل workflow على بنية تحتية للحوسبة السحابية غير المتجانسة ، ويقترح نهج قائم على موازاة خوارزمية محاكاة الصُلب تسمى PSA (Parallel Simulated Annealing) المنفذة على بنية GPU . تتمثل مهمتها في تخطيط مهام كل سير عمل يهدف إلى استخدام موارد بيئة السحابة. يتضمن التخطيط تعيين كل مهمة في سير العمل لمعالج معين للتنفيذ. يجب أن يتم تنفيذ العملية مع مراعاة قيود الأسبقية المتمثلة في احترام ترتيب المهام في سير العمل وفقًا لترابطها ، مع تقليل وقت الحوسبة (المكوّن) الذي يؤثر على استهلاك الطاقة إلى الحد الأدنى والتكلفة في حالة ما إذا كان المستخدم لديه ميزانية محدودة. الكلمات الرئيسية: الحوسبة السحابية ، جدولة المهام ، سير العمل ، وحدة معالجة الرسومات. ---------------------------------------------- Résumé (en Français) : Le cloud computing, initialement développée à partir de l'informatique en grille (grid computing), de l'informatique distribuée et de l'informatique parallèle, consiste en un ensemble d'ordinateurs virtuels interconnectés et utilisés dynamiquement, présentés sous forme de ressources informatiques unifiées basées sur des accords de niveau de service (SLA) établis par négociation entre le fournisseur de services, et les consommateurs, il est de plus en plus considéré comme un nouveau moyen d’utiliser les services informatiques, de stockage et de réseau à la demande de manière transparente et efficace. Plusieurs applications scientifiques dans de nombreux domaines, tels que la bioinformatique et l'astronomie, impliquent généralement de nombreuses tâches contraintes par des relations de priorité. Ces applications sont souvent exprimées sous forme de flux de travail, appelé aussi workflow, une série d'étapes de traitement connexes (tâches), où chaque étape prend des données en entrée, effectue un traitement et produit des données en sortie qui seront transmises aux étapes de traitement suivantes. Malheureusement, les services de cloud computing ne sont pas gratuits, un contrat d'accord de niveau de service (Service Level Agreement) signé entre le fournisseur et l'utilisateur fixera le prix à payer pour les ressources louées dans un modèle de paiement à l'utilisation. La planification des tâches est une étape importante lors de l'exécution d'un workflow dans un environnement de cloud computing. L’algorithme de planification doit trouver une répartition efficace des tâches du workflow de l’utilisateur sur le pool de ressources du fournisseur, en minimisant le temps nécessaire à l’exécution des workflow de l’utilisateur et en optimisant la disponibilité des ressources du cloud. En outre, la planification des tâches dans un environnement de cloud computing est un problème NP-difficile en général, et les algorithmes d'optimisation heuristiques sont largement utilisés pour la résolution de ce genre de problèmes. Un algorithme heuristique est utilisé pour trouver une solution sous-optimale du problème. Dans cette thèse, nous abordons le problème de la planification des workflows sur une infrastructure hétérogène de cloud computing, et une approche basée sur la parallélisation de l’algorithme de recuit simulé appelé PSA (Parallel Simulated Annealing) implémenté sur une architecture GPU est proposée. Sa mission est de planifier les tâches de chaque workflow destinée à utiliser les ressources de l’environnement cloud. La planification consiste à affecter chaque tâche du workflow à un processeur donné pour son exécution. Le processus doit être effectué en respectant la contrainte de précédence qui consiste à respecter l'ordre des tâches dans le workflow en fonction de leurs interdépendances, tout en minimisant le temps de calcul (makespan) qui a un impact sur la consommation d'énergie et le coût dans le cas où l'utilisateur dispose d'un budget limité. Les mots clés : Cloud computing, Planification des tâches, Workflow, Flux de travail, Gpu, Recuit simulée. ---------------------------------------------- Abstract (en Anglais) : Cloud computing, initially developed from grid computing, distributed computing, and parallel computing, consists of a set of interconnected and dynamically used virtual machines presented as computing resources. service-based level agreements (SLAs) established by negotiation between the service provider and consumers, it is increasingly seen as a new way to use IT, storage, and network services for request in a transparent and efficient way. Many scientific applications in many fields, such as bioinformatics and astronomy, usually involve many tasks constrained by priority relationships. These applications are often expressed as a workflow, also called a workflow, a series of related processing steps (tasks), where each step takes input data, performs processing, and outputs data that will be passed to users. Unfortunately, cloud services are not free, a service level agreement signed between the provider and the user will set the price to pay for the leased resources in a payment model use. Scheduling tasks is an important step when running a workflow in a cloud computing environment. The scheduling algorithm must find an efficient allocation of the user's workflow tasks to the provider's resource pool, minimizing the time required to execute the user's workflow and maximizing the availability of cloud resources. In addition, scheduling tasks in a cloud computing environment is an NP-hard problem in general, and heuristic optimization algorithms are widely used for solving such problems. A heuristic algorithm is used to find a sub-optimal solution of the problem. In this thesis, we address the problem of planning workflows on a heterogeneous cloud computing infrastructure, and an approach based on the parallelization of the simulated annealing algorithm called PSA (Parallel Simulated Annealing) implemented on a GPU architecture is proposed. Its mission is to plan the tasks of each workflow intended to use the resources of the cloud environment. Planning involves assigning each task in the workflow to a given processor for execution. The process must be carried out respecting the precedence constraint of respecting the order of tasks in the workflow according to their interdependencies, while minimizing the computing time (makespan) that has an impact on the cost in the case where the user has a limited budget. Keywords : Cloud Computing, Task Scheduling, Workflow, Gpu, Simulated Annealing
Description: Doctorat en sciences
URI/URL: http://hdl.handle.net/123456789/3184
Collection(s) :Informatique

Fichier(s) constituant ce document :

Fichier Description TailleFormat
DS_Inf_BENHAMMOUDA_Mohammed.pdf6,92 MBAdobe PDFVoir/Ouvrir
View Statistics

Tous les documents dans DSpace sont protégés par copyright, avec tous droits réservés.

 

Ce site utilise la plate-forme Dspace version 3.2-Copyright ©2014.