To see the other types of publications on this topic, follow the link: Scheduling tasks.
Dissertations / Theses on the topic 'Scheduling tasks'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Scheduling tasks.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Olsson, Granlund David. "Automated Scheduling of Mining Operation Tasks." Thesis, Luleå tekniska universitet, Institutionen för system- och rymdteknik, 2021. http://urn.kb.se/resolve?urn=urn:nbn:se:ltu:diva-83222.
Full textAbstract:
The task of scheduling mining operations is a strikingly tough task yet it is still largely done manually by hand or with the help of simple gantt planning tools. This thesis aim is to explore the feasibility of an automatic scheduling solution that can incorporate the constraints specific to mining operations. A constraint programming based solution is presented and evaluated based on its correctness, viability and performance. With its rich set of operators, the constraint programming library OR-Tools is able to capture most of the mining specific constraints and two different objective functions are developed to suit different use cases. One is the well established makespan objective which purpose is to minimize the completion time of the last task. The second objective function, named the sub goal deviation objective, minimizes the deviation from the overall production goal divided into sub goals. The underlying scheduling problem is notoriously hard to solve optimally for large instances. This is supported by several related studies and also by experimental results. To mitigate the performance degradation for large scheduling instances, an iterative solver strategy is presented. With this strategy the scheduler is able to solve much larger instances and initial tests resulted in the same objective values as the optimal strategy. A rescheduling procedure is presented to support schedule maintenance due to unforeseen circumstances such as delays or machine breakdowns. It is concluded that automatic scheduling and rescheduling is feasible but that it first needs to be evaluated by experienced schedulers in the field before being applied in a production environment.
2
Bast, Holger. "Provably optimal scheduling of similar tasks." [S.l. : s.n.], 2000. http://www.bsz-bw.de/cgi-bin/xvms.cgi?SWB10976167.
Full text
3
Eygelaar, Anton Burger. "Resource constrained step scheduling of project tasks." Thesis, Stellenbosch : University of Stellenbosch, 2008. http://hdl.handle.net/10019.1/4494.
Full textAbstract:
Thesis (MScEng (Civil Engineering))--University of Stellenbosch, 2008.Thesis presented in partial fulfilment of the requirements for the degree of Master of Science in Civil Engineering at the University of Stellenbosch.
ENGLISH ABSTRACT: The logical scheduling of activities in an engineering project currently relies heavily on the experience and intuition of the persons responsible for the schedule. In large projects the complexity of the schedule far exceeds the capacity of human intuition, and systematic techniques are required to compute a consistent sequence of activities. In this study a simple model of the engineering process is described. Based on certain specified relationships between components of the model, a consistent sequence of activities is determined in the form of a logical step schedule. The problem of resource constraints receives special attention. Engineering projects are often executed with limited resources and determining the impact of such restrictions on the logical step schedule is important. This study investigates activityshifting strategies to find a near-optimal sequence of activities that guarantees consistent evolution of deliverables while resolving resource conflicts within the context of logical step schedules.
AFRIKAANSE OPSOMMING: Die logiese skedulering van aktiwiteite in ‘n ingenieursprojek steun swaar op die ondervinding en intuisie van die persone wat verantwoordelik is vir die skedule. In groot projekte is die kompleksiteit van die skedule veel hoër as die kapasiteit van die menslike intuisie, en sistematiese tegnieke word benodig om ‘n konsekwente volgorde van aktiwiteite te bereken. In hierdie studie word ‘n eenvoudige model van die ingenieursproses beskryf. Gebasseer op sommige relasies tussen komponente van die model, kan ‘n konsekwente volgorde van aktiwiteite bepaal word in die vorm van ‘n logiese stap-skedule. Die probleem van beperkte hulpbronne ontvang spesiale aandag. Ingenieursprojekte word dikwels uitgevoer met beperkte hulpbronne en dit is belangrik om die impak daarvan op die logiese stap-skedule te bepaal. Die studie ondersoek die gebruik van aktiwiteit-skuiwende strategieë om ‘n nabyoptimale volgorde van aktiwiteite te vind wat konsekwente ontwikkeling van die projekprodukte waarborg, terwyl hulpbron konflikte opgelos word binne die konteks van ‘n logiese stap-skedule.
4
Jovanovska, Delfina. "Scheduling Time-Sensitive Tasks using a Combination of Proportional-Share and Priority Scheduling Algorithms." Ohio University / OhioLINK, 2011. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1300244698.
Full text
5
Teller, Justin Stevenson. "Scheduling Tasks on Heterogeneous Chip Multiprocessors with Reconfigurable Hardware." The Ohio State University, 2008. http://rave.ohiolink.edu/etdc/view?acc_num=osu1211985748.
Full text
6
Müller, Dirk, and Matthias Werner. "Improved Heuristics for Partitioned Multiprocessor Scheduling Based on Rate-Monotonic Small-Tasks." Universitätsbibliothek Chemnitz, 2012. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-80762.
Full textAbstract:
Partitioned preemptive EDF scheduling is very similar to bin packing, but there is a subtle difference. Estimating the probability of schedulability under a given total utilization has been studied empirically before. Here, we show an approach for closed-form formulae for the problem, starting with n = 3 tasks on m = 2 processors.
7
Lowe, Timothy James. "Constraint techniques applied to teamworking tasks in clothing industry production." Thesis, Manchester Metropolitan University, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.389493.
Full text
8
Nemati, Farhang. "Partitioned Scheduling of Real-Time Tasks on Multi-core Platforms." Licentiate thesis, Mälardalen University, School of Innovation, Design and Engineering, 2010. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-9595.
Full textAbstract:
In recent years multiprocessor architectures have become mainstream, and multi-core processors are found in products ranging from small portable cell phones to large computer servers. In parallel, research on real-time systems has mainly focused on traditional single-core processors. Hence, in order for real-time systems to fully leverage on the extra capacity offered by new multi-core processors, new design techniques, scheduling approaches, and real-time analysis methods have to be developed.
In the multi-core and multiprocessor domain there are mainly two scheduling approaches, global and partitioned scheduling. Under global scheduling each task can execute on any processor at any time while under partitioned scheduling tasks are statically allocated to processors and migration of tasks among processors is not allowed. Besides simplicity and efficiency of partitioned scheduling protocols, existing scheduling and synchronization methods developed for single-core processor platforms can more easily be extended to partitioned scheduling. This also simplifies migration of existing systems to multi-cores. An important issue related to partitioned scheduling is distribution of tasks among processors which is a bin-packing problem.
In this thesis we propose a partitioning framework for distributing tasks on the processors of multi-core platforms. Depending on the type of performance we desire to achieve, the framework may distribute a task set differently, e.g., in an application in which tasks process huge amounts of data the goal of the framework may be to decrease cache misses.Furthermore, we propose a blocking-aware partitioning heuristic algorithm to distribute tasks onto the processors of a multi-core architecture. The objective of the proposed algorithm is to decrease blocking overhead of tasks which reduces the total utilization and has the potential to reduce the number of required processors.Finally, we have implemented a tool to facilitate evaluation and comparison of different multiprocessor scheduling and synchronization approaches, as well as different partitioning heuristics. We have applied the tool in the evaluation of several partitioning heuristic algorithms, and the tool is flexible to which any new scheduling or synchronization protocol as well as any new partitioning heuristic can easily be added.
9
Varghese, B., M. Alamgir Hossain, and Keshav P. Dahal. "Scheduling of tasks in multiprocessor system using hybrid genetic algorithms." Springer Verlag, 2007. http://hdl.handle.net/10454/2552.
Full textAbstract:
This paper presents an investigation into the optimal scheduling of realtime
tasks of a multiprocessor system using hybrid genetic algorithms (GAs). A comparative
study of heuristic approaches such as `Earliest Deadline First (EDF)¿ and
`Shortest Computation Time First (SCTF)¿ and genetic algorithm is explored and
demonstrated. The results of the simulation study using MATLAB is presented and
discussed. Finally, conclusions are drawn from the results obtained that genetic algorithm
can be used for scheduling of real-time tasks to meet deadlines, in turn to obtain
high processor utilization.
10
Han, Kai. "Scheduling Distributed Real-Time Tasks in Unreliable and Untrustworthy Systems." Diss., Virginia Tech, 2010. http://hdl.handle.net/10919/26917.
Full textAbstract:
In this dissertation, we consider scheduling distributed soft real-time tasks in unreliable
(e.g., those with arbitrary node and network failures) and untrustworthy systems (e.g., those
with Byzantine node behaviors). We present a distributed real-time scheduling algorithm
called Gamma. Gamma considers a distributed (i.e., multi-node) task model where tasks are
subject to Time/Utility Function (or TUF) end-to-end time constraints, and the scheduling
optimality criterion of maximizing the total accrued utility. The algorithm makes three novel
contributions. First, Gamma uses gossip for reliably propagating task scheduling parameters
and for discovering task execution nodes. Second, Gamma achieves distributed real-time
mutual exclusion in unreliable environments. Third, the algorithm guards against potential
disruption of message propagation due to Byzantine attacks using a mechanism called
Launcher-Attacker-Infective-Susceptible-Immunized-Removed-Consumer (or LAISIRC). By
doing so, the algorithm schedules tasks with probabilistic termination-time satisfactions,
despite system unreliability and untrustworthiness.
We analytically establish several timeliness and non-timeliness properties of the algorithm
including probabilistic end-to-end task termination time satisfactions, optimality
of message overheads, mutual exclusion guarantees, and the mathematical model of the
LAISIRC mechanism. We conducted simulation-based experimental studies and compared
Gamma with its competitors. Our experimental studies reveal that Gammaâ s scheduling algorithm
accrues greater utility and satisfies a greater number of deadlines than do competitor
algorithms (e.g., HVDF) by as much as 47% and 45%, respectively. LAISIRC is more tolerant
to Byzantine attacks than competitor protocols (e.g., Path Verification) by obtaining as much as 28% higher correctness ratio. Gammaâ s mutual exclusion algorithm accrues greater
utility than do competitor algorithms (e.g., EDF-Sigma) by as much as 25%. Further, we
implemented the basic Gamma algorithm in the Emulab/ChronOS 250-node testbed, and
measured the algorithmâ s performance. Our implementation measurements validate our
theoretical analysis and the algorithm's effectiveness and robustness.Ph. D.
11
Qamhieh, Manar. "Scheduling of parallel real-time DAG tasks on multiprocessor systems." Thesis, Paris Est, 2015. http://www.theses.fr/2015PEST1030/document.
Full textAbstract:
Les applications temps réel durs sont celles qui doivent exécuter en respectant des contraintes temporelles. L'ordonnancement temps réel a bien été étudié sur mono-processeurs depuis plusieurs années. Récemment, l'utilisation d'architectures multiprocesseurs a augmenté dans les applications industrielles et des architectures parallèles sont proposées pour que le logiciel devienne compatible avec ces plateformes. L'ordonnancement multiprocesseurs de tâches parallèles dépendantes n'est pas une simple généralisation du cas mono-processeur et la problématique d'ordonnancement devient plus complexe et difficile. Dans cette thèse, nous étudions le problème d'ordonnancement temps réel de graphes de tâches parallèles acycliques sur des plateformes multiprocesseurs. Dans ce modèle, un graphe est composé d'un ensemble de sous-tâches dépendantes sous contraintes de précédence qui expriment les relations de précédences entre les sous-tâches. L'ordre d'exécution des sous-tâches est dynamique, c'est-à-dire que les sous-tâches peuvent s'exécuter en parallèle ou séquentiellement par rapport aux décisions de l'ordonnanceur temps réel. Pour traiter les contraintes de précédence, nous proposons deux méthodes pour l'ordonnancement des graphes : par transformation du modèle de graphe de sous tâches parallèles en un modèle de tâches séquentielles indépendantes, plus simple à ordonnancer et par ordonnancement direct des graphes en prenant en compte les relations de dépendance entre les sous-tâches. Nous proposons un ordonnancement des graphes en prenant directement en compte les paramètres temporels des graphes et un ordonnancement au niveau des sous-tâches, par rapport à des paramètres temporels attribués aux sous-tâches par un algorithme spécifique. Enfin, nous prouvons que les deux méthodes d'ordonnancement de graphes ne sont pas comparables. Nous fournissons alors des résultats de simulation pour comparer ces méthodes en utilisant les algorithmes d'ordonnancement globaux EDF et DM. Nous avons développé un logiciel nommé YARTISS pour générer des graphes aléatoires et réaliser les simulationsThe interest for multiprocessor systems has recently been increased in industrial applications, and parallel programming API's have been introduced to benefit from new processing capabilities. The use of multiprocessors for real-time systems, whose execution is performed based on certain temporal constraints is now investigated by the industry. Real-time scheduling problem becomes more complex and challenging in that context. In multiprocessor systems, a hard real-time scheduler is responsible for allocating ready jobs to available processors of the systems while respecting their timing parameters. In this thesis, we study the problem of real-time scheduling of parallel Directed Acyclic Graph (DAG) tasks on homogeneous multiprocessor systems. In this model, a DAG task consists of a set of subtasks that execute under precedence constraints. At all times, the real-time scheduler is responsible for determining how subtasks execute, either sequentially or in parallel, based on the available processors of the system. We propose two DAG scheduling approaches to determine the execution form of DAG tasks. The first approach is the DAG Stretching algorithm, from the Model Transformation approach, which forces DAG tasks to execute as sequentially as possible. The second approach is the Direct Scheduling, which aims at scheduling DAG tasks while respecting their internal dependencies. We provide real-time schedulability analyses for Direct Scheduling at DAG-Level and at Subtask-Level. Due to the incomparability of DAG scheduling approaches, we use extensive simulations to compare performance of global EDF with global DM scheduling using our simulation tool YARTISS
12
Chen, Lin. "Process migration and runtime scheduling for parallel tasks in computational grids." Click to view the E-thesis via HKUTO, 2007. http://sunzi.lib.hku.hk/hkuto/record/B38574172.
Full text
13
Nie, Yonggao. "Limited-preemptive fixed priority scheduling of real-time tasks on multiprocessors." Thesis, Mälardalens högskola, Inbyggda system, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-28265.
Full text
14
Chen, Lin, and 陳琳. "Process migration and runtime scheduling for parallel tasks in computational grids." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2007. http://hub.hku.hk/bib/B38574172.
Full text
15
Shi, Hehuan. "Scheduling Batching Computing and Communication Tasks : Theoretical Foundation and Algorithm Design." Electronic Thesis or Diss., université Paris-Saclay, 2021. http://www.theses.fr/2021UPASG025.
Full textAbstract:
Dans cette thèse, nous formulons et analysons une classe de problèmes fondamentaux d'ordonnancement de tâches découlant d'une variété de systèmes informatiques et de communication émergents: les tâches sont divisées en groupes; ceux d'un groupe peuvent être regroupés et exécutés simultanément; le but de l'ordonnanceur est de concevoir des algorithmes d'ordonnancement maximisant l'utilité globale du système. Sous le parapluie générique ci-dessus, nous étudions différentes classes de problèmes de planification de tâches de traitement par lots, établissant le cadre théorique correspondant, concevant des algorithmes de planification à la fois hors ligne et en ligne et illustrant leur application dans la planification des tâches de communication et de calcul. Nous commençons par le scénario de base de la planification des tâches de traitement par lots. Il existe un ensemble de tâches à exécuter sur un certain nombre de machines. Certaines tâches peuvent être exécutées simultanément sur une seule machine, tandis que d'autres nécessitent l'utilisation exclusive d'une machine entière. Nous recherchons une politique de planification optimale pour maximiser l'utilité globale du système. Nous développons un cadre algorithmique pour le problème d'ordonnancement ci-dessus sous la forme générique qui peut atteindre 1/2-optimalité, surpassant le meilleur résultat connu. Le cœur technique de notre conception est un mécanisme de relaxation LP adapté et une approche d'arrondi et de coloration qui transforme la solution de la relaxation LP en une politique d'ordonnancement réalisable 1/2-optimale. Nous démontrons ensuite l'application de notre cadre algorithmique pour résoudre le problème généralisé de diffusion proportionnelle en développant un algorithme d'approximation déterministe produisant une politique d'ordonnancement optimale l_min / (2 (l_min + 1)), alors qu'il n'existe que des algorithmes aléatoires dans la littérature. Nous formulons et analysons ensuite un problème fondamental d'ordonnancement de transmission en liaison descendante dans les systèmes de communication sans fil, composés d'une station de base et d'un ensemble d'utilisateurs, chacun demandant qu'un paquet soit servi dans une fenêtre temporelle. Certains paquets sont demandés par plusieurs utilisateurs et peuvent être servis simultanément en raison de la nature de diffusion du support sans fil. Par rapport au modèle de base, il existe deux particularités. Premièrement, chaque demande peut être servie par un sous-ensemble de stratégies de transmission. Deuxièmement, les demandes doivent être servies selon la méthode FIFO. Nous recherchons un algorithme de planification de transmission de liaison descendante maximisant l'utilité globale du système. Nous développons un cadre algorithmique du problème de planification de transmission de données de liaison descendante formulé dans les paramètres hors ligne et en ligne. Nous établissons d'abord sa dureté, puis développons des algorithmes d'approximation avec une garantie de performance mathématiquement prouvée en termes d'approximation et de ratios compétitifs pour les paramètres hors ligne et en ligne, respectivement. La troisième contribution de cette thèse concerne l'ordonnancement des tâches de batching de ressources contiguës. Un ensemble de tâches doit être exécuté sur un pool de ressources continues, chacune nécessitant un certain temps et une ressource contiguë; certaines tâches peuvent être exécutées simultanément par lots en partageant la ressource, tandis que d'autres nécessitent une utilisation exclusive de la ressource; les tâches sont servies à la manière FIFO. Nous recherchons une allocation optimale des ressources et la politique de planification associée maximisant l'utilité globale du système. Nous fournissons une analyse algorithmique complète du problème en établissant sa dureté et en développant des algorithmes de planification d'approximation pour les paramètres hors ligne et en ligneIn this thesis we formulate and analyze a class of fundamental task scheduling problems arising from a variety of emerging computing and communication systems: tasks are partitioned into groups; those in a group can be batched and executed simultaneously; the goal faced by the scheduler is to design scheduling algorithms maximizing the overall system utility. Under the above generic umbrella, we investigate different classes of batching task scheduling problems, establishing the corresponding theoretical framework, designing both offline and online scheduling algorithms, and illustrating their application in scheduling communication and computing tasks. We start by the baseline scenario of batching task scheduling. There is a set of tasks to be executed on a number of machines. Some tasks can be executed simultaneously on a single machine, while others require exclusive use of an entire machine. We seek an optimal scheduling policy to maximize the overall system utility. We develop an algorithmic framework for the above scheduling problem in the generic form that can achieve 1/2-optimality, outperforming the best known result. The core technicality in our design is an adapted LP relaxation mechanism and a rounding and coloring approach that turns the solution of the LP relaxation to a 1/2-optimal feasible scheduling policy. We then demonstrate the application of our algorithmic framework to solve the generalized proportional broadcast problem by developing a deterministic approximation algorithm outputting an l_min/(2(l_min+1))-optimal scheduling policy, while there exist only randomized algorithms in the literature. We then formulate and analyze a fundamental downlink transmission scheduling problem in wireless communication systems, composed of a base station and a set of users, each requesting a packet to be served within a time window. Some packets are requested by several users and can be served simultaneously due to the broadcast nature of the wireless medium. Compared to the baseline model, there are two particularities. First, each request can be served by a subset of transmission strategies. Second, requests need to be served in the FIFO manner. We seek a downlink transmission scheduling algorithm maximizing the overall system utility. We develop an algorithmic framework of the formulated downlink data transmission scheduling problem in both offline and online settings. We first establish its hardness, and then develop approximation algorithms with mathematically proven performance guarantee in terms of approximation and competitive ratios for the offline and online settings, respectively. The third contribution of this thesis concerns the contiguous-resource batching task scheduling. A set of tasks need to be executed on a pool of continuous resource, each requiring a certain amount of time and contiguous resource; some tasks can be executed simultaneously in batch by sharing the resource, while others requiring exclusive use of the resource; tasks are served in the FIFO manner. We seek an optimal resource allocation and the related scheduling policy maximizing the overall system utility. We deliver a comprehensive algorithmic analysis on the problem by establishing its hardness and developing approximation scheduling algorithms for both offline and online settings
16
AULUCK, NITIN. "REAL-TIME SCHEDULING ALGORITHMS FOR PRECEDENCE RELATED TASKS ON HETEROGENEOUS MULTIPROCESSORS." University of Cincinnati / OhioLINK, 2005. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1109288052.
Full text
17
Singh, Abhishek Jeffay Kevin. "Co-scheduling real-time tasks and non real-time tasks using empirical probability distribution of execution time requirements." Chapel Hill, N.C. : University of North Carolina at Chapel Hill, 2009. http://dc.lib.unc.edu/u?/etd,2724.
Full textAbstract:
Thesis (Ph. D.)--University of North Carolina at Chapel Hill, 2009.Title from electronic title page (viewed Mar. 10, 2010). "... in partial fulfillment of the requirements for the degree of Doctor of Philosophy in the Department of Computer Science." Discipline: Computer Science; Department/School: Computer Science.
18
Podobas, Artur, and Mats Brorsson. "Architecture-aware Task-scheduling : A thermal approach." KTH, Programvaru- och datorsystem, SCS, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-89634.
Full textAbstract:
Current task-centric many-core schedulers share a “naive” view of processor architecture; a view that does not care about its thermal, architectural or power consuming properties. Future processor will be more heterogeneous than what we see today, and following Moore’s law of transistor doubling, we foresee an increase in power consumption and thus temperature. Thermal stress can induce errors in processors, and so a common way to counter this is by slowing the processor down; something task-centric schedulers should strive to avoid. The Thermal-Task-Interleaving scheduling algorithm proposed in this paper takes both the application temperature behavior and architecture into account when making decisions. We show that for a mixed workload, our scheduler outperforms some of the standard, architecture-unaware scheduling solutions existing today.QC 20120215
19
Gaid, MEMB, AS Cela, and Y. Hamam. "Optimal Real-Time Scheduling of Control Tasks with State Feedback Resource Allocation." IEEE Transactions on Control Systems Technology, 2009. http://encore.tut.ac.za/iii/cpro/DigitalItemViewPage.external?sp=1001370.
Full textAbstract:
Abstract—This paper proposes a new approach for the optimal
integrated control and real-time scheduling of control tasks.
First, the problem of the optimal integrated control and nonpreemptive
off-line scheduling of control tasks in the sense of
the H2 performance criterion is addressed. It is shown that this
problem may be decomposed into two sub-problems. The first
sub-problem aims at finding the optimal non-preemptive off-line
schedule, and may be solved using the branch and bound method.
The second sub-problem uses the lifting technique to determine
the optimal control gains, based on the solution of the first
sub-problem. Second, an efficient on-line scheduling algorithm
is proposed. This algorithm, called Reactive Pointer Placement
(RPP) scheduling algorithm, uses the plant state information to
dispatch the computational resources in a way that improves
control performance. Control performance improvements as well
as stability guarantees are formally proven. Finally, simulations
as well as experimental results are presented in order to illustrate
the effectiveness of the proposed approach.
20
Huang, Lin. "Scheduling tasks with conditional and preemptive attributes on a parallel and distributed system /." Title page, table of contents and abstract only, 1999. http://web4.library.adelaide.edu.au/theses/09PH/09phh87391.pdf.
Full text
21
Zhu, Kaiqian. "Limited Preemptive Earliest Deadline First Scheduling of Real-Time Tasks on Multiprocessors." Thesis, Mälardalens högskola, Inbyggda system, 2015. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-28252.
Full textAbstract:
Real-time systems are employed in many areas, such as aerospace and defenses. In real-time systems, especially in hard real-time systems, it is important to meet the associated time requirements. With the increasing demand for high speed processing capabilities, the requirement for high computing power is becoming more and more urgent. However, it is no longer possible to increase processor speeds because of thermal and power constraints. Consequently, industry has focused on providing more computing capabilities using more number of processors.As to the scheduling policies, they can be classified into two categories, preemptive and non-preemptive. Preemptive scheduling allows preemptions arbitrarily, whereas it implies prohibitively high preemption related overheads. On the contrary, the non-preemptive scheduling which do not allow preemption at all, will not have such overheads, but suffers due to the block time on high priority tasks. Limited preemptive scheduling, that builds on the best of preemptive and non-preemptive scheduling, benefits from the limited number of preemptions without a major effect on real-time properties. It is proved that limited preemptive scheduling dominates preemptive and non-preemptive scheduling on uniprocessors under fixed priority. However, less work has been done on multiprocessor limited preemptive scheduling, especially under Earliest Deadline First (EDF). On a multiprocessor, limited preemptively scheduling real-time tasks imply an additional challenge with respect to determining which of the running task to preempt. On one extreme, the scheduler can preempt the lowest priority running task and this is referred to as Adaptive Deferred Scheduling (ADS). On the other hand, the scheduler can preempt any lower priority running task that becomes pre-emptible. Such a scheduler is referred to as Regular Deferred Scheduling (RDS)In this work, we empirically investigate the performance of ADS and RDS, and compare it with the global preemptive and non-preemptive scheduling, in the context of an EDF based scheduler. Our empirical investigation revealed that the number of preemptions under ADS is less compared to RDS, at runtime. This is due to the fact that by delaying preemptions, the higher priority tasks that are released subsequently will run in priority order thereby avoiding the need for more preemptions. Also, by delaying preemptions, the possibility of one or more processors becoming available increases. Experiments investigating the schedulability ratio shows that ADS and RDS performs almost equally well, but better than fully non-preemptive scheduling.
22
Zuhily, Areej. "Scheduling analysis of fixed priority hard real-time systems with multiframe tasks." Thesis, University of York, 2009. http://etheses.whiterose.ac.uk/11090/.
Full text
23
Zahaf, Houssam-Eddine. "Energy efficient scheduling of parallel real-time tasks on heterogeneous multicore systems." Thesis, Lille 1, 2016. http://www.theses.fr/2016LIL10100/document.
Full textAbstract:
Les systèmes cyber-physiques (CPS) et d’Internet des objets génèrent un volume et une variété des données sans précédant. Le temps que ces données parcourent le réseau dans son chemin vers le cloud, la possibilité de réagir à un événement critique pourrait être tardive. Pour résoudre ce problème, les traitements de données nécessitant une réponse rapide sont faits à proximité d’où les données sont collectées. Ainsi, seuls les résultats du pré-traitement sont envoyées au cloud et la réaction pourrai être déclenché suffisamment rapide pour préserver l’intégrité du système. Ce modèle de calcul est connu comme Fog Computing. Un large spectre d’applications de CPS ont des contraintes temporelle et peuvent être facilement parallélisées en distribuant les calculs sur différents sous-ensembles de données en même temps. Ceci peut permettre d’obtenir un temps de réponse plus court et un temps de creux plus large. Ainsi, on peut réduire la fréquence du processeur et/ou éteindre des parties du processeur afin de réduire la consommation d’énergie. Dans cette thèse, nous nous concentrons sur le problème d'ordonnancement d’un ensemble de taches temps-réels parallèles sur des architectures multi-coeurs dans l’objectif de réduire la consommation d’énergie en respectant toutes les contraintes temporelles. Nous proposons ainsi plusieurs modèles de tâches et des testes d'ordonnançabilité pour résoudre le problème d’allocation des threads aux processeurs. Nous proposons aussi des méthodes qui permettent de sélectionner les fréquences et les états des processeurs. Les modèles proposés peuvent être implantés comme des directives dans la même logique que OpenMPCyber physical systems (CPS) and Internet of Objects (IoT) are generating an unprecedented volume and variety of data that needs to be collected and stored on the cloud before being processed. By the time the data makes its way to the cloud for analysis, the opportunity to trigger a reply might be late. One approach to solve this problem is to analyze the most time-sensitive data at the network edge, close to where it is generated. Thus, only the pre-processed results are sent to the cloud. This computation model is know as *Fog Computing* or *Edge computing*. Critical CPS applications using the fog computing model may have real-time constraints because results must be delivered in a pre-determined time window. Furthermore, in many relevant applications of CPS, the processing can be parallelized by applying the same processing on different sub-sets of data at the same time by the mean parallel programming techniques. This allow to achieve a shorter response time, and then, a larger slack time, which can be used to reduce energy consumption. In this thesis we focus on the problem of scheduling a set of parallel tasks on multicore processors, with the goal of reducing the energy consumption while all deadlines are met. We propose several realistic task models on architectures with identical and heterogeneous cores, and we develop algorithms for allocating threads to processors, select the core frequencies, and perform schedulability analysis. The proposed task models can be realized by using OpenMP-like APIs
24
Babbar, Davender. "On-line hard real-time scheduling of parallel tasks on partitionable multiprocessors /." The Ohio State University, 1994. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487858417983777.
Full text
25
Augonnet, Cédric. "Scheduling Tasks over Multicore machines enhanced with Accelerators : a Runtime System’s Perspective." Thesis, Bordeaux 1, 2011. http://www.theses.fr/2011BOR14460/document.
Full textAbstract:
Bien que les accélérateurs fassent désormais partie intégrante du calcul haute performance, les gains observés ont un impact direct sur la programmabilité, de telle sorte qu'un support proposant des abstractions portables est indispensable pour tirer pleinement partie de toute la puissance de calcul disponible de manière portable, malgré la complexité de la machine sous-jacente. Dans cette thèse, nous proposons un modèle de support exécutif offrant une interface expressive permettant notamment de répondre aux défis soulevés en termes d'ordonnancement et de gestion de données. Nous montrons la pertinence de notre approche à l'aide de la plateforme StarPU conçue à l'occasion de cette thèseMulticore machines equipped with accelerators are becoming increasingly popular in the HighPerformance Computing ecosystem. Hybrid architectures provide significantly improved energyefficiency, so that they are likely to generalize in the Manycore era. However, the complexity introducedby these architectures has a direct impact on programmability, so that it is crucial toprovide portable abstractions in order to fully tap into the potential of these machines. Pure offloadingapproaches, that consist in running an application on regular processors while offloadingpredetermined parts of the code on accelerators, are not sufficient. The real challenge is to buildsystems where the application would be spread across the entire machine, that is, where computationwould be dynamically scheduled over the full set of available processing units.In this thesis, we thus propose a new task-based model of runtime system specifically designedto address the numerous challenges introduced by hybrid architectures, especially in terms of taskscheduling and of data management. In order to demonstrate the relevance of this model, we designedthe StarPU platform. It provides an expressive interface along with flexible task schedulingcapabilities tightly coupled to an efficient data management. Using these facilities, together witha database of auto-tuned per-task performance models, it for instance becomes straightforward todevelop efficient scheduling policies that take into account both computation and communicationcosts. We show that our task-based model is not only powerful enough to provide support forclusters, but also to scale on hybrid manycore architectures.We analyze the performance of our approach on both synthetic and real-life workloads, andshow that we obtain significant speedups and a very high efficiency on various types of multicoreplatforms enhanced with accelerators
26
Zhu, Wenjing. "Adaptive threshhold-based scheduling for real-time and non-real-time tasks." Thesis, University of British Columbia, 1991. http://hdl.handle.net/2429/29913.
Full textAbstract:
This thesis documents our study on scheduling mixed real-time and non-real-time tasks with different performance metrics. The work is motivated by the need to provide satisfactory performance trade-offs in a dynamic environment where the arrival rates and proportions of the real-time and non-real-time tasks vary with time. We first examine two threshold-based schemes, Queue Length Threshold and Minimum Laxity Threshold, and propose the corresponding
adaptive schemes based on our results from approximate analysis and simulation. The idea is to improve performance by adjusting trade-off points adaptively as the arrival rates change. We further discuss the idea of integrating the two thresholds. The new algorithm, ADP, is evaluated by simulation under various load conditions and compared with other common
scheduling disciplines as well as an optimal algorithm. Some implementation issues are also discussed. We conclude that by setting appropriate threshold functions in accordance to the requirements of applications, we can achieve satisfactory bounded loss ratio for real-time tasks and acceptably low average delay for non-real-time tasks in a wide range of workload conditions.Science, Faculty of
Computer Science, Department of
Graduate
27
Kunis, Raphael. "Realisierung einer Schedulingumgebung für gemischt-parallele Anwendungen und Optimierung von layer-basierten Schedulingalgorithmen." Doctoral thesis, Universitätsbibliothek Chemnitz, 2011. http://nbn-resolving.de/urn:nbn:de:bsz:ch1-qucosa-64584.
Full textAbstract:
Eine Herausforderung der Parallelverarbeitung ist das Erreichen von Skalierbarkeit großer paralleler Anwendungen für verschiedene parallele Systeme. Das zentrale Problem ist, dass die Ausführung einer Anwendung auf einem parallelen System sehr gut sein kann, die Portierung auf ein anderes System in der Regel jedoch zu schlechten Ergebnissen führt.
Durch die Verwendung des Programmiermodells der parallelen Tasks mit Abhängigkeiten kann die Skalierbarkeit für viele parallele Algorithmen
deutlich verbessert werden. Die Programmierung mit parallelen Tasks führt zu Task-Graphen mit Abhängigkeiten zur Darstellung einer parallelen Anwendung, die auch als gemischt-parallele Anwendung bezeichnet wird. Die Grundlage für eine effiziente Abarbeitung einer gemischt-parallelen Anwendung bildet ein geeigneter Schedule, der eine effiziente Abbildung der parallelen Tasks auf die Prozessoren des parallelen Systems vorgibt. Für die Berechnung eines Schedules werden Schedulingalgorithmen eingesetzt.
Ein zentrales Problem bei der Bestimmung eines Schedules für gemischt-parallele Anwendungen besteht darin, dass das Scheduling bereits für Single-Prozessor-Tasks mit Abhängigkeiten und ein paralleles System mit zwei Prozessoren NP-hart ist. Daher existieren lediglich Approximationsalgorithmen und Heuristiken um einen Schedule zu berechnen. Eine Möglichkeit zur Berechnung eines Schedules sind layerbasierte Schedulingalgorithmen. Diese Schedulingalgorithmen bilden zuerst Layer unabhängiger paralleler Tasks und berechnen den Schedule für jeden Layer separat.
Eine Schwachstelle dieser Schedulingalgorithmen ist das Zusammenfügen der einzelnen Schedules zum globalen Schedule. Der vorgestellte Algorithmus Move-blocks bietet eine elegante Möglichkeit das Zusammenfügen zu verbessern. Dies geschieht durch eine Verschmelzung der Schedules aufeinander folgender Layer.
Obwohl eine Vielzahl an Schedulingalgorithmen für gemischt-parallele Anwendungen existiert, gibt es bislang keine umfassende Unterstützung des Schedulings durch Programmierwerkzeuge. Im Besonderen gibt es keine Schedulingumgebung, die eine Vielzahl an Schedulingalgorithmen in sich vereint. Die Vorstellung der flexiblen, komponentenbasierten und erweiterbaren Schedulingumgebung SEParAT ist der zweite Fokus dieser Dissertation. SEParAT unterstützt verschiedene Nutzungsszenarien,
die weit über das reine Scheduling hinausgehen, z.B. den Vergleich von
Schedulingalgorithmen und die Erweiterung und Realisierung neuer Schedulingalgorithmen. Neben der Vorstellung der Nutzungsszenarien werden sowohl die interne Verarbeitung eines Schedulingdurchgangs als auch die komponentenbasierte Softwarearchitektur detailliert vorgestellt.
28
Silva, Jaquilino Lopes. "A distributed platform for the volunteer execution of workflows on a local area network." Master's thesis, Faculdade de Ciências e Tecnologia, 2014. http://hdl.handle.net/10362/13102.
Full textAbstract:
Thesis submitted in fulfilment of the requirements for the Degree of Master of Science in Computer ScienceAlbatroz Engineering has developed a framework for over-head power lines inspection data acquisition and analysis, which includes hardware and software. The framework’s software components include inspection data analysis and reporting tools, commonly known as PLMI2 application/platform. In PLMI2, the analysis of over-head power line maintenance inspection data consists of a sequence of Automatic Tasks (ATs) interleaved with Manual Tasks (MTs). An AT consists of a set of algorithms that receives as input one or more datasets, processes them and returns new datasets. In turn, an MT enables human supervisors (also known as lines inspection operators) to correct, improve and validate the results of ATs. ATs run faster than MTs and in the overall work cycle, ATs take less than 10% of total processing time, but still take a few minutes. There is data flow dependency among tasks, which can be modelled with a workflow and even if MTs are omitted from this workflow, it is possible to carry the sequence of ATs, postponing MTs. In fact, if the computing cost and waiting time are negligible, it may be advantageous to run ATs earlier in the workflow, prior to validation. To address this opportunity, Albatroz Engineering has invested in a new procedure to stream the data through all ATs fully unattended. Considering these scenarios, it could be useful to have a system capable of detecting available workstations at a given instant and subsequently distribute the ATs to them. In this way, operators could schedule the execution of future ATs for a given inspection data, while they are performing MTs of another. The requirements of the system to implement fall within the field Volunteer Computing Systems and we will address some of the challenges posed by these kinds of systems, namely the hosts volatility and failures. Volunteer Computing is a type of distributed computing which exploits idle CPU cycles from computing resources donated by volunteers and connected through the Internet/Intranet to compute large-scale simulations. This thesis proposes and designs a new distributed task scheduling system in the context of Volunteer Computing Systems, able to schedule the ATs of PLMI2 and exploit idle CPU cycles from workstations within the company’s local area network (LAN) to accelerate the data analysis, being aware of data flow interdependencies. To evaluate the proposed system, a prototype has been implemented, and the simulations results have shown that it is scalable and supports fault-tolerance of tasks execution, by employing the rescheduling mechanism.
29
Katre, Kedar Maheshwar. "Policies for Migration of Real-Time tasks in Embedded Multicore Systems." OpenSIUC, 2010. https://opensiuc.lib.siu.edu/theses/264.
Full textAbstract:
There has been a lot of work that has been done on timing predictability of real-time tasks on embedded systems. The main assumption in these studies has been that the timing behavior has been based on single processor systems. The scenario has changed entirely when the single core systems have been replaced with the new Multicore systems. The timing predictability is controlled by the migrating tasks, the network topology connecting the cores and the number of cores on the system. In this thesis we come up with a feasibility analysis which depends on the characteristics of the tasks viz. number of cache lines, time of migration, available bandwith, number of tasks etc. We also test this analysis on novel mechanisms of migration which have been proposed recently and present its results.
30
Courbin, Pierre. "Scheduling sequential or parallel hard real-time pre-emptive tasks upon identical multiprocessor platforms." Thesis, Paris Est, 2013. http://www.theses.fr/2013PEST1081/document.
Full textAbstract:
L'ordonnancement de tâches sur un système temps réel dur correspond à trouver une façon de choisir, à chaque instant, quelle tâche doit être exécutée sur le processeur pour que chacune ait le temps de terminer son travail avant son échéance. Ce problème, dans le contexte monoprocesseur, est déjà bien étudié et permet des applications sur des systèmes en production (aérospatiale, bourse etc.). Aujourd'hui, les plateformes multiprocesseur se sont généralisées et ont amené de nombreuses questions telles que l'utilisation efficace de tous les processeurs. Dans cette thèse, nous explorons les approches existantes pour résoudre ce problème. Nous étudions tout d'abord l'approche par partitionnement qui consiste à utiliser les recherches existantes en ramenant ce problème à plusieurs systèmes monoprocesseur. Ici, nous proposons un algorithme générique dont les paramètres sont adaptables en fonction de l'objectif à atteindre. Nous étudions ensuite l'approche par semi-partitionnement qui permet la migration d'un nombre restreint de tâches. Nous proposons une solution avec des migrations restreintes qui pourrait être assez simplement implémentée sur des systèmes concrets. Nous proposons ensuite une solution avec des migrations non restreintes qui offre de meilleurs résultats mais est plus difficile à implémenter. Enfin, les programmeurs utilisent de plus en plus le concept de tâches parallèles qui peuvent utiliser plusieurs processeurs en même temps. Ces tâches sont encore peu étudiées et nous proposons donc un nouveau modèle pour les représenter. Nous étudions les ordonnanceurs possibles et nous définissons une façon de garantir l'ordonnançabilité de ces tâches pour deux d'entre euxThe scheduling of tasks on a hard real-time system consists in finding a way to choose, at each time instant, which task should be executed on the processor so that each succeed to complete its work before its deadline. In the uniprocessor case, this problem is already well studied and enables us to do practical applications on real systems (aerospace, stock exchange etc.). Today, multiprocessor platforms are widespread and led to many issues such as the effective use of all processors. In this thesis, we explore the existing approaches to solve this problem. We first study the partitioning approach that reduces this problem to several uniprocessor systems and leverage existing research. For this one, we propose a generic partitioning algorithm whose parameters can be adapted according to different goals. We then study the semi-partitioning approach that allows migrations for a limited number of tasks. We propose a solution with restricted migration that could be implemented rather simply on real systems. We then propose a solution with unrestricted migration which provides better results but is more difficult to implement. Finally, programmers use more and more the concept of parallel tasks that can use multiple processors simultaneously. These tasks are still little studied and we propose a new model to represent them. We study the possible schedulers and define a way to ensure the schedulability of such tasks for two of them
31
Bester, Margarete Joan. "Design of an automated decision support system for scheduling tasks in a generalized job-shop." Thesis, Stellenbosch : Stellenbosch University, 2006. http://hdl.handle.net/10019.1/21734.
Full text
32
Valentin, Eduardo Bezerra, and 92-36710870. "Scheduling hard real-time tasks in heterogeneous multiprocessor platforms subject to energy and temperature constraints." Universidade Federal do Amazonas, 2017. http://tede.ufam.edu.br/handle/tede/6148.
Full textAbstract:
Submitted by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-02-08T12:48:35Z
No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Tese_Eduardo Bezerra Valetim.pdf: 1753904 bytes, checksum: b47b056ce4f5f67a30051e12c578323a (MD5)Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-02-08T12:49:13Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_Eduardo Bezerra Valetim.pdf: 1753904 bytes, checksum: b47b056ce4f5f67a30051e12c578323a (MD5)
Made available in DSpace on 2018-02-08T12:49:13Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Tese_Eduardo Bezerra Valetim.pdf: 1753904 bytes, checksum: b47b056ce4f5f67a30051e12c578323a (MD5) Previous issue date: 2017-09-29
The power wall is a barrier to improvement in the processor design process due to the power consumption of components. The production of energy optimum systems demands knowledge of different disciplines. The usage of heterogeneous multicore platforms is appealing for recent applications, e.g., hard real-time systems. The motivation is the potential reduced energy consumption offered by such platforms. Hard real-time systems are present in life critical environments. Reducing the energy consumption on such systems is an onerous process. Scheduling becomes particularly challenging to improve system utilization and minimize system energy consumption and peak temperature on such platforms, specially subject to hard real-time constraints. Therefore, we propose a study to effectively answer the pertinent research question: “How to offer users timing correctness and guarantees of hard real-time systems executed on heterogeneous multicore systems with energy and temperature constraints?”. Finding optimal solutions for such question has still several open research questions. The main aim of this thesis is to propose an energy optimization method for hard realtime system on heterogeneous multicore platform demonstrating that it is possible to timely compute timing correctness and guarantees using a sufficient and necessary condition; accounting for energy, temperature, preemption, precedence, shared resources constraints, and architectural interference. The proposal is a two fold approach. First, we investigate the process of finding the optimal task to core and frequency to task processes by means of applying exact schedulability tests for heterogeneous multicore platforms. Second, the outcome of the optimization analysis shall be used as reference to the on-line scheduler. We believe that we have achieved the main objective of this research by combining: (a) schedulability analysis from hard real-time systems, (b) representative mathematical formulations, based on integer linear programming, covering modern processors technological characteristics and using a classical combinatorial mathematical formulation (Multilevel Generalized Assignment Problem), and (c) robust exact implicit enumeration algorithmic strategies from combinatorial optimization, such as branch-and-cut and branch-and-price. The systematic literature review in the research subject reveals that the field has open questions to be answered. For instance, to the knowledge of the author only five works in the state-of-the-art literature deal with the problem by providing optimal solutions. Typically, the existing approaches focus on either heuristics or approximation algorithms. Also, only one work has a proposal to evaluate the schedulability in this scenario with an exact test. The typical formulation in the specialized literature is a 0/1 integer linear programming model which considers a continuous processor frequency domain and determines a single operating frequency per processor. One of the hypotheses tested in this research is: stronger feasibility analysis offers tighter bounds for the problem. We believe that this can be observed, for example, in the results produced by solvers for fixed priority schedulers, by means of an analysis based on a comparative study. By applying less accurate schedulability tests, such as utilization based, the solvers take longer to converge to optimal solutions, when compared to solvers that apply exact schedulability tests based on response time analysis. Another hypothesis tested in this research is: practical instances of the problem are timely solvable to optimal. We have experimented, by means of a comparative study, on finding feasible solutions for workload for fixed priority schedulers with up to 50 tasks distributed on four processors with seven different available frequencies. On independent hard real-time tasks scheduled using EDF policy, we found optimal distribution of up to 90 tasks on four processors with seven different available frequencies. In both cases, the solutions were found within 30 min of execution time. Similarly, on dependent tasks workload, we have optimally distributed 22 tasks, from an automotive control hard real-time application, on four processors with seven different available frequencies, with two shared resources and 23 precedence constraints within 1.5 h. We consider a few hours in the design phase a price worth paying in this context.
.
33
Belaid, Ikbel. "On line-off line placement and scheduling of real time hardware tasks on dynamically reconfigurable platforms." Nice, 2011. http://www.theses.fr/2011NICE4019.
Full textAbstract:
Le placement et l’ordonnancement des tâches matérielles sont les éléments clés du système d’exploitation temps réel. Ces deux problèmes doivent être traités efficacement afin d’améliorer la qualité du placement exprimée par le taux de fragmentation de ressources et la latence de reconfiguration, et la qualité d’ordonnancement représentée par la durée d’exécution de l’application et la garantie des échéances. En utilisant les systèmes sur puce programmable, nous proposons d’exploiter les caractéristiques physiques de ces puces, en particulier la reconfiguration partielle dynamique. Nous traitons, dans premier temps, les tâches indépendantes. Nous suggérons une résolution analytique par des solveurs de programmation en nombres entiers mixtes qui se basent sur la méthode de séparation et évaluation pour réaliser le placement hors-ligne de ces tâches sur puce. La métaheuristique des abeilles est aussi proposer pour traiter ce problème. Nous proposons d’employer l’algorithme « Earliest deadline first » pour construire l’ordonnancement temps réel en ligne. Nous nous intéressons ensuite aux tâches dépendantes. En se basant également sur la programmation en nombres entiers mixtes, le placement et l’ordonnancement statiques des tâches matérielles périodiques, constituant un graphe acyclique orienté, sont élaborés. Quatre approches dynamiques sont proposées pour effectuer le placement et l’ordonnancement dynamique de plusieurs graphes sur différentes puces. Par les techniques de réutilisation et de prédiction, ces approches visent la réduction des temps d’exécution des graphes, la garantie des échéances et l’efficacité des ressourcesThe placement and scheduling of hardware tasks are the cores of the real-time operating system. Both problems must be solved efficiently to enhance the placement quality expressed by the rate of resource fragmentation and configuration overhead, and to improve the scheduling quality represented by the temporal spanning of the application and the guarantee of real-time constraints. In the context of the mixed architectures such as System on Programmable Chip (SoPC), we suggest exploiting the physical features of these architectures especially the partial run-time reconfiguration. The first part of the thesis deals with preemptive independents tasks. It suggests analytic resolution by means of mixed integer programming solver using the Branch and Bound method to achieve off-line placement of these tasks on a SoPC. The Bees metaheuristic is also proposed to handle this problem and we suggest employing dynamically the Earliest Deadline First algorithm to perform the real-time scheduling. The second part of the thesis focuses on dependent tasks where each one runs after the completion of all its proposed to resolve statically the placement and scheduling of periodic hardware tasks in a sole directed acyclic graph (DAG) on a SoPC. . Four dynamic approaches are also proposed to place and schedule dynamically multiple DAGs with unknown behavior on several SoPCs. Basing on prefetch and reuse techniques, these approaches aim to reduce the temporal spanning of DAGs, and to improve the guarantee of real-time constraints and resource efficiency
34
Falavinha, Junior José Nelson. "Escalonamento de tarefas em sistemas distribuídos baseado no conceito de propriedade distribuída /." Ilha Solteira : [s.n.], 2009. http://hdl.handle.net/11449/100313.
Full textAbstract:
Orientador: Aleardo Manacero JuniorCoorientador: Miron Livny
Banca: Sergio Azevedo de Oliveira
Banca: Renata Spolon Lobato
Banca: Alfredo Goldman Lejbman
Banca: Henrique Mongelli
Resumo: Em sistemas distribuídos de larga escala; onde os recursos compartilhados são de propriedade de entidades distintas; existe a necessidade de refletir o fator propriedade dos recursos no processo de escalonamento de tarefas e alocação de recursos. Um sistema de gerenciamento de recursos apropriado deve garantir que os proprietários de recursos tenham acesso aos seus recursos ou ao menos a uma parcela de recursos que seja equivalente a eles. Diferentes políticas podem ser estabelecidas para que o sistema garanta esse direito aos proprietários de recursos; e nessa tese defende-se uma política de escalonamento e alocação de reucrsos chamada Owner-Share Enforcement Policy (OSEP) ou Política de Garantia da Porção do Proprietário; que tem por objetivo garantir o direito de acesso aos recursos através de um sistema de escalonamento baseado em preempção de tarefas e realocação de recursos. Avalia-se a política através da análise de testes e resultados envolvendo métricas de desempenho que descrevem fatores como violação da política; perdada capacidade de processamento; custo da política e satisfação do usuário. Os testes ainda envolveram a análise de desempenho da política em ambientes com a possibilidade de chekcpointing de tarefas; minimizando assim o desperdício de processamento. Fez-se ainda comparações com a política de compartilhamento justo Fair-Share; que permitiram estabelecer as vantagens e desvantagens de cada política e ainda identificar futuros problemas. Por fim; conclui-se a tese identificando as contribuições oferecidas por este trabalho e os trabalhos futuros que podem ser desenvolvidos.
Abstract: In large distributed systems, where shared resources are owned by distinct entities, there is a need to reflect resource ownership in resource allocation. An appropriate resource management system should guarantee that owners of resources have access to their resources or at least to a share of resources proportional to the share of resources they provide. Different policies can be established for guaranteeing the access to resources, and in this thesis we introduce a policy for scheduling and resource allocation named Owner Share Enforcement Policy (OSEP). This policy is based on the concept of distributed ownership and itguarantees the owner's right of accessing their share of resources in a distributed system with a preemptive share space. We evaluate this policy through tests and results analysis involving performance metrics that describe policy violation, loss of capacity, policy cost and user satisfaction. The tests were also conducted in environments withand without job checkpointing, and comparisons with the Fair-Share scheduling policy were made in order to capture the trade-offs of each policy. Finally, we conclude the thesis describing the contributions achieved with this work and pointing directions for future work.
Doutor
35
Motakpalli, Sankalpanand. "Aperiodic Job Handling in Cache-Based Real-Time Systems." OpenSIUC, 2017. https://opensiuc.lib.siu.edu/dissertations/1474.
Full textAbstract:
Real-time systems require a-priori temporal guarantees. While most of the normal operation in such a system is modeled using time-driven, hard-deadline sporadic tasks, event-driven behavior is modeled using aperiodic jobs with soft or no deadlines. To provide good Quality-of- Service for aperiodic jobs in the presence of sporadic tasks, aperiodic servers were introduced. Aperiodic servers act as a sporadic task and reserve a quota periodically to serve aperiodic jobs. The use of aperiodic servers in systems with caches is unsafe because aperiodic servers do not take into account, the indirect cache-related preemption delays that the execution of aperiodic jobs might impose on the lower-priority sporadic tasks, thus jeopardizing their safety. To solve this problem, we propose an enhancement to the aperiodic server that we call a Cache Delay Server. Here, each lower-priority sporadic task is assigned a delay quota to accommodate the cache-related preemption delay imposed by the execution of aperiodic jobs. Aperiodic jobs are allowed to execute at their assigned server priority only when all the active lower-priority sporadic tasks have a sufficient delay quota to accommodate it. Simulation results demonstrate that a Cache Delay Server ensures the safety of sporadic tasks while providing acceptable Quality-of-Service for aperiodic jobs. We propose a Integer Linear Program based approach to calculate delay quotas for sporadic tasks within a task set where Cache Delay Servers have been pre-assigned. We then propose algorithms to determine Cache Delay Server characteristics for a given sporadic task set. Finally, we extend the Cache Delay Server concept to multi-core architectures and propose approaches to schedule aperiodic jobs on appropriate Cache Delay Servers. Simulation results demonstrate the effectiveness of all our proposed algorithms in improving aperiodic job response times while maintaining the safety of sporadic task execution.
36
Liberg, Tim, and Per-Erik Måhl. "GPU-accelerated Model Checking of Periodic Self-Suspending Real-Time Tasks." Thesis, Mälardalens högskola, Akademin för innovation, design och teknik, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-14661.
Full textAbstract:
Efficient model checking is important in order to make this type of software verification useful for systems that are complex in their structure. If a system is too large or complex then model checking does not simply scale, i.e., it could take too much time to verify the system. This is one strong argument for focusing on making model checking faster. Another interesting aim is to make model checking so fast that it can be used for predicting scheduling decisions for real-time schedulers at runtime. This of course requires the model checking to complete within a order of milliseconds or even microseconds. The aim is set very high but the results of this thesis will at least give a hint on whether this seems possible or not. The magic card for (maybe) making this possible is called Graphics Processing Unit (GPU). This thesis will investigate if and how a model checking algorithm can be ported and executed on a GPU. Modern GPU architectures offers a high degree of processing power since they are equipped with up to 1000 (NVIDIA GTX 590) or 3000 (NVIDIA Tesla K10) processor cores. The drawback is that they offer poor thread-communication possibilities and memory caches compared to CPU. This makes it very difficult to port CPU programs to GPUs.The example model (system) used in this thesis represents a real-time task scheduler that can schedule up to three periodic self-suspending tasks. The aim is to verify, i.e., find a feasible schedule for these tasks, and do it as fast as possible with the help of the GPU.
37
RAMACHANDRAN, GOWRI SANKAR. "Integration of enhanced slot-shifting in uc/os-II." Thesis, Mälardalens högskola, Akademin för innovation, design och teknik, 2011. http://urn.kb.se/resolve?urn=urn:nbn:se:mdh:diva-12981.
Full text
38
Reis, Valéria Quadros dos. "Escalonamento em grids computacionais: estudo de caso." Universidade de São Paulo, 2005. http://www.teses.usp.br/teses/disponiveis/55/55134/tde-18092006-115903/.
Full textAbstract:
Esta dissertação tem por objetivo apresentar a proposta de uma política de escalonamento para grids computacionais. Essa política, intitulada Dynamic Max-Min2x, é orientada ao escalonamento de aplicações cujas tarefas não realizam comunicação entre si e visa a redução do tempo de resposta dessas aplicações através da utilização de atribuição dinâmica de tarefas e replicação das mesmas. Experimentos, feitos através de simulação, mostram que o tempo médio de resposta de aplicações utilizando-se a Dynamic Max-Min2x é inferior ao de outras políticas da literatura. Análises dos resultados desses experimentos apontam que esse tempo tende a ser mais atrativo principalmente quando as tarefas necessitam de muito processamento e quando há grande variação de carga no sistema, caracteristicas comuns em grids computacionais. Além disso, esta dissertação apresenta a implementação de um framework utilizando-se o Globus Toolkit, onde é possível a inserção de políticas de escalonamento para a submissão inteligente de tarefas em um grid computacional.This Master thesis proposes a new grid scheduling policy called Dynamic Max-Min2x. This policy focuses on applications in which tasks do not communicate among themsenves and targets a response time reduction of these applications through the use of dynamic task distribution and replication techniques. Experiments, done using simulations, have shown that the response time related to Dynamic Max-Min2x is smaller than others policies found in literature. Analysis of the results have demonstrated that this time tends to become more attractive when tasks do not need much processing power and when there is a great load variation in the system, characteristics frequently found in grids. Furthermore, this thesis presents the implementation of a framework using Globus Toolkit, which makes possible the new scheduling policies insertion to provide an intelligent submission tasks in a computational grid system.
39
Ndoye, Falou. "Ordonnancement temps réel préemptif multiprocesseur avec prise en compte du coût du système d’exploitation." Thesis, Paris 11, 2014. http://www.theses.fr/2014PA112056/document.
Full textAbstract:
Dans cette thèse nous étudions le problème d'ordonnancement temps réel multiprocesseur préemptif avec prise en compte du coût exact du système d'exploitation. Ce coût est formé de deux parties : une partie facile à déterminer, correspondant au coût de l'ordonnanceur et une partie difficile à déterminer, correspondant au coût de la préemption. Cette difficulté est due au fait qu'une préemption peut en engendrer une autre, pouvant ainsi créer un phénomène d'avalanche. Dans un premier temps, nous avons étudié l'ordonnancement hors ligne multiprocesseur de tâches indépendantes avec prise en compte du coût exact de la préemption et proposé une analyse d'ordonnançabilité fondée sur une heuristique d'ordonnancement multiprocesseur. Cette heuristique utilise la stratégie d'ordonnancement multiprocesseur par partitionnement. Pour prendre en compte le coût exact de la préemption sur chaque processeur nous avons utilisé la condition d'ordonnançabilité proposée par Meumeu et Sorel. Cette condition d'ordonnançabilité pour des tâches à priorités fixes, est basée sur une opération binaire d'ordonnancement qui permet de compter le nombre exact de préemption et d'ajouter leur coût dans l'analyse d'ordonnançabilité des tâches. L'heuristique proposée permet de maximiser le facteur d'utilisation restant afin de répartir équitablement les tâches sur les processeurs et de réduire leur temps de réponse. Elle produit une table d'ordonnancement hors ligne. Dans un second temps, nous avons étudié l'ordonnancement hors ligne multiprocesseur de tâches dépendantes avec prise en compte du coût exact de la préemption. Puisque la condition d'ordonnançabilité utilisée pour ordonnancer les tâches indépendantes ne s'applique qu'à des tâches à priorités fixes, elle ne permet pas de gérer les inversions de priorités que peuvent entraîner les tâches dépendantes. Nous avons donc proposé une nouvelle condition d'ordonnançabilité pour des tâches à priorités dynamiques. Elle prend en compte le coût exact de la préemption et les dépendances sans aucune perte de données. Ensuite en utilisant toujours la stratégie d'ordonnancement par partitionnement, nous avons proposé pour des tâches dépendantes une heuristique d'ordonnancement multiprocesseur qui réutilise cette nouvelle condition d'ordonnançabilité au niveau de chaque processeur. Cette heuristique d'ordonnancement prend en compte les coûts de communication inter-processeurs. Elle permet aussi de minimiser sur chaque processeur le makespan (temps total d'exécution) des tâches. Cette heuristique produit pour chaque processeur une table d'ordonnancement hors ligne contenant les dates de début et de fin de chaque tâches et de chaque commmunication inter-processeur. En supposant que nous avons une architecture multiprocesseur de type dirigée par le temps (Time-Triggered) pour laquelle tous les processeurs ont une référence de temps unique, nous avons proposé pour chacun des processeurs un ordonnanceur en ligne qui utilise la table d'ordonnancement produite lors de l'ordonnancement hors ligne. Cet ordonnanceur en ligne a l'avantage d'avoir un coût constant qui de plus est facile à déterminer de manière exacte. En effet il correspond uniquement au temps de lecture dans la table d'ordonnancement pour obtenir la tâche sélectionnée lors de l'analyse d'ordonnançabilité hors ligne, alors que dans les ordonnanceurs classiques en ligne ce coût correspond à mettre à jour la liste des tâches qui sont dans l'état prêt à l'exécution puis à sélectionner une tâche selon un algorithme, par exemple RM, DM, EDF, etc. Il varie donc avec le nombre de tâches prêtes à s'exécuter qui change d'une invocation à l'autre de l'ordonnanceur. C'est ce coût qui est utilisé dans les analyses d'ordonnançabilités évoquées ci-dessus. Un autre avantage est qu'il n'est pas nécessaire de synchroniser l'accès aux mémoires de données partagées par plusieurs tâches, car cette synchronisation a été déjà effectuée lors de l'analyse d'ordonnançabilité hors ligneIn this thesis we studied the problem of multiprocessor preemptive real-time scheduling taking into account the exact cost of the operating system (OS). This cost is composed of two parts: a part easy to determine, corresponding to the scheduler cost and another part difficult to determine, corresponding to the preemption cost. This difficulty is due to the fact that a preemption can involve another one, being able to so create an avalanche phenomenon. First, we studied the off-line multiprocessor real-time scheduling of independent tasks taking into account the exact preemption cost. We proposed a schedulability analysis based on a multiprocessor scheduling heuristic. This heuristic uses the partitioned multiprocessor scheduling approach. In order to take into account the exact preemption cost on every processor we use the schedulability condition proposed by Meumeu and Sorel. This schedulability condition for fixed priorities tasks, is based on a binary scheduling operation which counts the exact number of preemptions and add their cost in the schedulability analysis. The proposed heuristic maximizes the remaining utilization factor to fairly distribute the tasks on processors and to reduce their response time. It produces an off-line scheduling table. Secondly, we studied the off-line multiprocessor real-time scheduling of dependent tasks taking into account the exact preemption cost. Because the schedulability condition used for scheduling independent tasks can be applied only to fixed priorities tasks, it does not allow to manage priorities inversions that are involved by dependent tasks. We proposed a new schedulability condition for dependent tasks which enables fixed and dynamic priorities. This schedulability condition takes into account the exact preemption cost and dependences between tasks without any loss of data. Always with the partitioned scheduling approach, we proposed for dependent tasks a multiprocessor scheduling heuristic which reuses, on every processor, the schedulability condition proposed previously. In addition, this scheduling heuristic takes into account the interprocessors communication costs. It also minimizes on every processor the makespan (total execution time of the tasks on all the processors). This heuristic produces for every processor an off-line scheduling table. Supposing that we have a time-triggered multiprocessor architecture such that all the processors have a unique time reference, we proposed for every processor an on-line scheduler which uses the scheduling table produced during the off-line schedulability analysis. This on-line scheduler has the advantage to have a constant cost that is easy to determine exactly.Indeed, this cost corresponds only to the time necessary to read in the scheduling table the task selected for execution. In the on-line classical scheduler, this cost corresponds to the time necessary to update the list of ready tasks in order to select a task, according to a given scheduling algorithm, for example RM, DM, EDF, etc. In this case, the cost for selecting a task varies with the number of ready tasks which changes from an invocation of the scheduler to another one. Another advantage of the proposed on-line scheduler is that it is not necessary to synchronize the access to the data shared by several tasks, because this synchronization was already done during the off-line schedulability analysis
40
Jørgensen, Carl-Johan. "Scheduling activities under spatial and temporal constraints to populate virtual urban environments." Thesis, Rennes 1, 2015. http://www.theses.fr/2015REN1S033/document.
Full textAbstract:
Les modèles de simulation de foules visent généralement à produire des foules visuellement crédibles avec l'intention d'insuffler de la vie à des environnements virtuels. Notre travail se concentre sur la génération de comportements statistiquement cohérents qui peuvent être utilisés pour piloter des modèles de simulation de foules sur de longues périodes de temps, jusqu'à plusieurs jours. Dans les foules réelles, les comportements des individus dépendent principalement de l'activité qu'ils ont l'intention d'effectuer. La façon d’ordonnancer cette activité repose sur l'interaction étroite qui existe entre l'environnement, les contraintes spatiales et temporelles associées à l'activité et les caractéristiques personnelles des individus. Par rapport à l'état de l'art, notre modèle gérer mieux cette interaction. Nos principales contributions se situent dans le domaine de l'ordonnancement d'activités et de la planification de chemin. Dans un premier temps, nous proposons un processus d'ordonnancement d'activités individuelles et son extension aux activités coopératives. Basé sur les descriptions de l'environnement, des activités désirées et des caractéristiques des agents, ces processus génèrent une séquence de la tâche pour chaque agent. Des lieux où ces tâches doivent être effectuées sont sélectionnés et un timing relâché est produit. Cet ordonnancement est compatible avec les contraintes spatiales et temporelles liées à l'environnement et à l'activité prévue par l'agent et par d'autres agents en coopération. Il prend également en compte les caractéristiques personnelles des agents, induisant de la diversité dans les ordonnancements produits. Nous montrons que notre modèle produit des comportements statistiquement cohérents avec ceux produits par des personnes dans les mêmes situations. Dans un second temps, nous proposons un processus de planification de chemins hiérarchique. Il repose sur un processus d'analyse de l'environnement automatique qui produit une représentation hiérarchique sémantiquement cohérente des villes virtuelles. La nature hiérarchique de cette représentation est utilisée pour modéliser différents niveaux de prise de décisions. Un chemin grossier est d'abord calculé, puis raffiné pendant la navigation lorsque de l'information pertinente est disponible, permettant ainsi à l'agent d'adapter son chemin à des événements inattendus. Le modèle proposé gère des décisions rationnelles à long terme guidant la navigation des agents dans les villes virtuelles. Il prend en compte la forte relation entre le temps, l'espace et l'activité pour produire les comportements des agents plus crédibles de. Il peut être utilisé pour peupler facilement des villes virtuelles avec des foules au sein desquelles des phénomènes observables émergent de l'activité individuelleCrowd simulation models usually aim at producing visually credible crowds with the intent of giving life to virtual environments. Our work focusses on generating statistically consistent behaviours that can be used to pilot crowd simulation models over long periods of time, up to multiple days. In real crowds, people's behaviours mainly depend on the activities they intend to perform. The way this activity is scheduled rely on the close interaction between the environment, space and time constraints associated with the activity and personal characteristics of individuals. Compared to the state of the art, our model better handle this interaction. Our main contributions lie in the domain of activity scheduling and path planning. First, we propose an individual activity scheduling process and its extension to cooperative activity scheduling. Based on descriptions of the environment, of intended activities and of agents' characteristics, these processes generate a task schedule for each agent. Locations where the tasks should be performed are selected and a relaxed agenda is produced. This task schedule is compatible with spatial and temporal constraints associated with the environment and with the intended activity of the agent and of other cooperating agents. It also takes into account the agents personal characteristics, inducing diversity in produced schedules. We show that our model produces schedules statistically coherent with the ones produced by humans in the same situations. Second, we propose a hierarchical path-planning process. It relies on an automatic environment analysis process that produces a semantically coherent hierarchical representation of virtual cities. The hierarchical nature of this representation is used to model different levels of decision making related to path planning. A coarse path is first computed, then refined during navigation when relevant information is available. It enable the agent to seamlessly adapt its path to unexpected events. The proposed model handles long term rational decisions driving the navigation of agents in virtual cities. It considers the strong relationship between time, space and activity to produce more credible agents' behaviours. It can be used to easily populate virtual cities in which observable crowd phenomena emerge from individual activities
41
Nelissen, Geoffrey. "Efficient optimal multiprocessor scheduling algorithms for real-time systems." Doctoral thesis, Universite Libre de Bruxelles, 2013. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/209528.
Full textAbstract:
Real-time systems are composed of a set of tasks that must respect some deadlines. We find them in applications as diversified as the telecommunications, medical devices, cars, planes, satellites, military applications, etc. Missing deadlines in a real-time system may cause various results such as a diminution of the quality of service provided by the system, the complete stop of the application or even the death of people. Being able to prove the correct operation of such systems is therefore primordial. This is the goal of the real-time scheduling theory.These last years, we have witnessed a paradigm shift in the computing platform architectures. Uniprocessor platforms have given place to multiprocessor architectures. While the real-time scheduling theory can be considered as being mature for uniprocessor systems, it is still an evolving research field for multiprocessor architectures. One of the main difficulties with multiprocessor platforms, is to provide an optimal scheduling algorithm (i.e. scheduling algorithm that constructs a schedule respecting all the task deadlines for any task set for which a solution exists). Although optimal multiprocessor real-time scheduling algorithms exist, they usually cause an excessive number of task preemptions and migrations during the schedule. These preemptions and migrations cause overheads that must be added to the task execution times. Therefore, task sets that would have been schedulable if preemptions and migrations had no cost, become unschedulable in practice. An efficient scheduling algorithm is therefore an algorithm that either minimize the number of preemptions and migrations, or reduce their cost.
In this dissertation, we expose the following results:
- We show that reducing the "fairness" in the schedule, advantageously impacts the number of preemptions and migrations. Hence, all the scheduling algorithms that will be proposed in this thesis, tend to reduce or even suppress the fairness in the computed schedule.
- We propose three new online scheduling algorithms. One of them --- namely, BF2 --- is optimal for the scheduling of sporadic tasks in discrete-time environments, and reduces the number of task preemptions and migrations in comparison with the state-of-the-art in discrete-time systems. The second one is optimal for the scheduling of periodic tasks in a continuous-time environment. Because this second algorithm is based on a semi-partitioned scheme, it should favorably impact the preemption overheads. The third algorithm --- named U-EDF --- is optimal for the scheduling of sporadic and dynamic task sets in a continuous-time environment. It is the first real-time scheduling algorithm which is not based on the notion of "fairness" and nevertheless remains optimal for the scheduling of sporadic (and dynamic) systems. This important result was achieved by extending the uniprocessor algorithm EDF to the multiprocessor scheduling problem.
- Because the coding techniques are also evolving as the degree of parallelism increases in computing platforms, we provide solutions enabling the scheduling of parallel tasks with the currently existing scheduling algorithms, which were initially designed for the scheduling of sequential independent tasks.
Doctorat en Sciences de l'ingénieur
info:eu-repo/semantics/nonPublished
42
Simon, Bertrand. "Ordonnancement de graphes de tâches sur des plates-formes de calcul modernes." Thesis, Lyon, 2018. http://www.theses.fr/2018LYSEN022/document.
Full textAbstract:
Cette thèse porte sur trois thématiques principales liées à l'ordonnancement de graphes de tâches sur des plates-formes de calcul modernes. Un graphe de tâches est une modélisation classique d'un programme à exécuter, par exemple une application de calcul scientifique. La décomposition d'une application en différentes tâches permet d'exploiter le parallélisme potentiel de cette application sans adapter le programme à la plate-forme de calcul visée. Le graphe décrit ces tâches ainsi que leurs dépendances, certaines tâches ne pouvant être exécutées avant que d'autres ne soient terminées. L'exécution d'une application est alors déterminée par un ordonnancement du graphe, calculé par un logiciel dédié, qui décrit entre autres quelles ressources sont allouées à chaque tâche et à quel moment. Les trois thèmes étudiés sont les suivants: exploiter le parallélisme intrinsèque des tâches, utiliser des accélérateurs tels que des GPU, et prendre en compte une mémoire limitée.Certaines applications présentent deux types de parallélisme que l'on peut exploiter: plusieurs tâches peuvent être exécutées simultanément, et chaque tâche peut être exécutée sur plusieurs processeurs afin de réduire son temps de calcul. Nous proposons et étudions deux modèles permettant de régir ce temps de calcul, afin d'exploiter ces deux types de parallélisme.Nous étudions ensuite comment utiliser efficacement des accélérateurs de calcul tels que des GPU, dans un contexte dynamique où les futures tâches à ordonnancer ne sont pas connues. La difficulté principale consiste à décider si une tâche doit être exécutée sur l'un des rares accélérateurs disponibles ou sur l'un des nombreux processeurs classiques. La dernière thématique abordée concerne le problème d'une mémoire principale limitée, et le recours à des transferts de données coûteux. Nous avons traité ce problème via deux scénarios. S'il est possible d'éviter de tels transferts, nous avons proposé de modifier le graphe afin de garantir que toute exécution ne dépasse pas la mémoire disponible, ce qui permet d'ordonnancemer les tâches dynamiquement au moment de l'exécution. Si tout ordonnancement nécessite des transferts, nous avons étudié le problème consistant à minimiser leur quantité.L'étude de ces trois thèmes a permis de mieux comprendre la complexité de ces problèmes. Les solutions proposées dans le cadre d'étude théorique pourront influencer de futures implémentations logiciellesThis thesis deals with three main themes linked to task graph scheduling on modern computing platforms. A graph of tasks is a classical model of a program to be executed, for instance a scientific application. The decomposition of an application into several tasks allows to exploit the potential parallelism of this application without adaptating the program to the computing platform. The graph describes the tasks as well as their dependences, some tasks cannot be initiated before others are completed. The execution of an application is then determined by a schedule of the graph, computed by a dedicated software, which in particular describes which resources should be allocated to each task at which time. The three studied themes are the following: exploit inner task parallelism, use accelerators such as GPUs, and cope with a limited memory.For some applications, two types of parallelism can be exploited: several tasks can be executed concurrently, and each task may be executed on several processors, which reduces its processing time. We propose and study two models allowing to describe this processing time acceleration, in order to efficiently exploit both types of parallelism.We then study how to efficiently use accelerators such as GPUs, in a dynamic context in which the future tasks to schedule are unknown. The main difficulty consists in deciding whether a task should be executed on one of the rare available accelerators or on one of the many classical processors. The last theme covered in this thesis deals with a available main memory of limited size, and the resort to expensive data transfers. We focused on two scenarios. If it is possible to avoid such transfers, we propose to modify the graph in order to guarantee that any execution fits in memory, which allows to dynamically schedule the graph at runtime. If every schedule needs transfers, we studied how to minimize their quantity.The work on these three themes has led to a better understanding of the underlying complexities. The proposed theoretical solutions will influence future software implementations
43
Falavinha, Junior José Nelson [UNESP]. "Escalonamento de tarefas em sistemas distribuídos baseado no conceito de propriedade distribuída." Universidade Estadual Paulista (UNESP), 2009. http://hdl.handle.net/11449/100313.
Full textAbstract:
Made available in DSpace on 2014-06-11T19:30:50Z (GMT). No. of bitstreams: 0
Previous issue date: 2009-05-25Bitstream added on 2014-06-13T21:01:23Z : No. of bitstreams: 1
falavinhajunior_jn_dr_ilha.pdf: 3487083 bytes, checksum: 5eeeb56b23091b46b46acaafba4babe4 (MD5)Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)
Em sistemas distribuídos de larga escala; onde os recursos compartilhados são de propriedade de entidades distintas; existe a necessidade de refletir o fator propriedade dos recursos no processo de escalonamento de tarefas e alocação de recursos. Um sistema de gerenciamento de recursos apropriado deve garantir que os proprietários de recursos tenham acesso aos seus recursos ou ao menos a uma parcela de recursos que seja equivalente a eles. Diferentes políticas podem ser estabelecidas para que o sistema garanta esse direito aos proprietários de recursos; e nessa tese defende-se uma política de escalonamento e alocação de reucrsos chamada Owner-Share Enforcement Policy (OSEP) ou Política de Garantia da Porção do Proprietário; que tem por objetivo garantir o direito de acesso aos recursos através de um sistema de escalonamento baseado em preempção de tarefas e realocação de recursos. Avalia-se a política através da análise de testes e resultados envolvendo métricas de desempenho que descrevem fatores como violação da política; perdada capacidade de processamento; custo da política e satisfação do usuário. Os testes ainda envolveram a análise de desempenho da política em ambientes com a possibilidade de chekcpointing de tarefas; minimizando assim o desperdício de processamento. Fez-se ainda comparações com a política de compartilhamento justo Fair-Share; que permitiram estabelecer as vantagens e desvantagens de cada política e ainda identificar futuros problemas. Por fim; conclui-se a tese identificando as contribuições oferecidas por este trabalho e os trabalhos futuros que podem ser desenvolvidos.
In large distributed systems, where shared resources are owned by distinct entities, there is a need to reflect resource ownership in resource allocation. An appropriate resource management system should guarantee that owners of resources have access to their resources or at least to a share of resources proportional to the share of resources they provide. Different policies can be established for guaranteeing the access to resources, and in this thesis we introduce a policy for scheduling and resource allocation named Owner Share Enforcement Policy (OSEP). This policy is based on the concept of distributed ownership and itguarantees the owner's right of accessing their share of resources in a distributed system with a preemptive share space. We evaluate this policy through tests and results analysis involving performance metrics that describe policy violation, loss of capacity, policy cost and user satisfaction. The tests were also conducted in environments withand without job checkpointing, and comparisons with the Fair-Share scheduling policy were made in order to capture the trade-offs of each policy. Finally, we conclude the thesis describing the contributions achieved with this work and pointing directions for future work.
44
Schewior, Kevin [Verfasser], Nicole [Akademischer Betreuer] Megow, Nicole [Gutachter] Megow, Martin [Gutachter] Skutella, and Clifford [Gutachter] Stein. "Handling critical tasks online : deadline scheduling and convex-body chasing / Kevin Schewior ; Gutachter: Nicole Megow, Martin Skutella, Clifford Stein ; Betreuer: Nicole Megow." Berlin : Technische Universität Berlin, 2016. http://d-nb.info/1156014913/34.
Full text
45
Lacoste, Xavier. "Scheduling and memory optimizations for sparse direct solver on multi-core/multi-gpu duster systems." Thesis, Bordeaux, 2015. http://www.theses.fr/2015BORD0016/document.
Full textAbstract:
L’évolution courante des machines montre une croissance importante dans le nombre et l’hétérogénéité des unités de calcul. Les développeurs doivent alors trouver des alternatives aux modèles de programmation habituels permettant de produire des codes de calcul à la fois performants et portables. PaStiX est un solveur parallèle de système linéaire creux par méthodes directe. Il utilise un ordonnanceur de tâche dynamique pour être efficaces sur les machines modernes multi-coeurs à mémoires hiérarchiques. Dans cette thèse, nous étudions les bénéfices et les limites que peut nous apporter le remplacement de l’ordonnanceur interne, très spécialisé, du solveur PaStiX par deux systèmes d’exécution génériques : PaRSEC et StarPU. Pour cela l’algorithme doit être décrit sous la forme d’un graphe de tâches qui est fournit aux systèmes d’exécution qui peuvent alors calculer une exécution optimisée de celui-ci pour maximiser l’efficacité de l’algorithme sur la machine de calcul visée. Une étude comparativedes performances de PaStiX utilisant ordonnanceur interne, PaRSEC, et StarPU a été menée sur différentes machines et est présentée ici. L’analyse met en évidence les performances comparables des versions utilisant les systèmes d’exécution par rapport à l’ordonnanceur embarqué optimisé pour PaStiX. De plus ces implémentations permettent d’obtenir une accélération notable sur les machines hétérogènes en utilisant lesaccélérateurs tout en masquant la complexité de leur utilisation au développeur. Dans cette thèse nous étudions également la possibilité d’obtenir un solveur distribué de système linéaire creux par méthodes directes efficace sur les machines parallèles hétérogènes en utilisant les systèmes d’exécution à base de tâche. Afin de pouvoir utiliser ces travaux de manière efficace dans des codes parallèles de simulations, nous présentons également une interface distribuée, orientée éléments finis, permettant d’obtenir un assemblage optimisé de la matrice distribuée tout en masquant la complexité liée à la distribution des données à l’utilisateurThe ongoing hardware evolution exhibits an escalation in the number, as well as in the heterogeneity, of computing resources. The pressure to maintain reasonable levels of performance and portability forces application developers to leave the traditional programming paradigms and explore alternative solutions. PaStiX is a parallel sparse direct solver, based on a dynamic scheduler for modern hierarchical manycore architectures. In this thesis, we study the benefits and the limits of replacing the highly specialized internal scheduler of the PaStiX solver by two generic runtime systems: PaRSEC and StarPU. Thus, we have to describe the factorization algorithm as a tasks graph that we provide to the runtime system. Then it can decide how to process and optimize the graph traversal in order to maximize the algorithm efficiency for thetargeted hardware platform. A comparative study of the performance of the PaStiX solver on top of its original internal scheduler, PaRSEC, and StarPU frameworks is performed. The analysis highlights that these generic task-based runtimes achieve comparable results to the application-optimized embedded scheduler on homogeneous platforms. Furthermore, they are able to significantly speed up the solver on heterogeneous environments by taking advantage of the accelerators while hiding the complexity of their efficient manipulation from the programmer. In this thesis, we also study the possibilities to build a distributed sparse linear solver on top of task-based runtime systems to target heterogeneous clusters. To permit an efficient and easy usage of these developments in parallel simulations, we also present an optimized distributed interfaceaiming at hiding the complexity of the construction of a distributed matrix to the user
46
Junior, Michele Biagioni. "Modelo para programação de atividades e a alocação de técnicos para a instalação e assistência técnica de equipamentos." Universidade de São Paulo, 2008. http://www.teses.usp.br/teses/disponiveis/3/3135/tde-10112008-115513/.
Full textAbstract:
Este trabalho consiste na elaboração de um modelo para programação de atividades e alocação de técnicos que executam tarefas de instalação, manutenção preventiva e visita diagnóstica em equipamentos utilizados na produção de bens de consumo em escala industrial. O modelo utiliza técnicas de pesquisa operacional visando minimizar os custos envolvidos. O modelo em questão descreve as fases para a elaboração da programação das atividades e da alocação dos técnicos para executá-las, trazendo como contribuição ao tema restrições como acordo sindical de banco de horas celebrado com os empregados e nível de serviço prestado ao cliente. O presente modelo considera ainda eventuais penalidades existentes por atraso no início da instalação dos equipamentos comercializados. O modelo define as atividades que deverão ser atendidas prioritariamente e os impactos econômicos de tal decisão, distribuindo a carga de trabalho de forma mais uniforme possível entre os técnicos dentro do horizonte de planejamento.This paper presents a model to schedule the activities and allocation of technicians that perform tasks of installation, preventive maintenance and diagnostic visits in equipments used in the production of consuming goods in industrial scale. The model uses operation research techniques aiming at minimizing the costs involved in these activities. The model in question describes the phases of scheduling and allocation of technicians in order to perform their activities. It brings as contribution to this theme constrains such as union agreement on Accumulation of hours regime entered with the employees and the level of service rendered to the client. This model also considers the occasional existing penalties due to delays at the beginning of the installation of the sold equipments. This model defines which activities must be prioritized as well as their economic impacts, distributing the workload in the most even way among the technicians within the planning horizon.
47
Tampelini, Leonardo Garcia 1983. "Técnicas heurísticas de escalonamento paralelo em workflow." [s.n.], 2012. http://repositorio.unicamp.br/jspui/handle/REPOSIP/275702.
Full textAbstract:
Orientador: Jacques WainerDissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
Made available in DSpace on 2018-08-20T14:02:06Z (GMT). No. of bitstreams: 1 Tampelini_LeonardoGarcia_M.pdf: 834632 bytes, checksum: b0f1d3f3d777417870d8ddd0d317ab8e (MD5) Previous issue date: 2012
Resumo: Com a disseminação de tecnologias de gerenciamento empresarial, empresas procuram promover serviços mais ágeis e de maior qualidade. Neste contexto, áreas como gerenciamento de workflow vêm contribuindo para uma melhor organização na distribuição de tarefas. A aproximação da área de escalonamento com workflow demonstra um grande potencial para atender tais requisitos; porém, uma escassez de trabalhos voltados ao tratamento de estruturas de roteamento paralelas, comumente encontradas em modelos de workflow, é perceptível na literatura de escalonamento. Este trabalho tem por objetivo aproximar essas duas áreas apresentando três novas abordagens de escalonamento voltadas à ordenação de casos dentro de estruturas de roteamento paralelas (AND). Para alcançar tal objetivo, um conjunto de simuladores foi implementado representando o ambiente dinâmico de workflow, suas incertezas, bem como os diferentes cenários onde estruturas do tipo AND podem ocorrer. O desempenho de tais políticas foi comparado com regras amplamente utilizadas em sistemas de workflow, como FIFO (First In First Out), EDD (Earliest Due Date) e SPT (Shortest Processing Time). A análise dos resultados foi efetivada por meio de uma análise de variância (ANOVA) juntamente com o teste de Tukey. Os resultados mostram que é mais vantajoso utilizar técnicas específicas para estrutura de roteamento AND do que apenas aplicar as técnicas mais utilizadas
Abstract: With the dissemination of business management technologies, companies look for to promoting faster services with higher quality. In this context, areas such as workflow management have contributed to a better organization in the distribution of tasks. The approach between scheduling area and workflow area shows great potential to attend these requirements, but a lack of studies directed to the treatment of parallel routing structures, commonly found in workflow models, is apparent escalation in the literature about scheduling. This work aims to approximate these two areas, presenting three new scheduling approaches, directed to the raging of the cases within routing structures parallel (AND). To reach this objective a set of simulators was implemented, representing the dynamic workflow environment, their uncertainties, as well as the different scenarios where that structures such as AND may occur. The performance of these politics was compared with rules widely used in workflow systems, such as FIFO (First In First Out), EDD (Earliest Due Date) and SPT (Shortest Processing Time). The results show that it is more advantageous to use techniques focused on AND routing structure than only apply the most utilized ones
Mestrado
Ciência da Computação
Mestre em Ciência da Computação
48
Borro, Luiz César. "Escalonamento em grades móveis: uma abordagem ciente do consumo de energia." Universidade de São Paulo, 2014. http://www.teses.usp.br/teses/disponiveis/55/55134/tde-24032014-103603/.
Full textAbstract:
Considerando-se o contexto de gerenciamento energético em grades móveis, neste trabalho foram propostos dois algoritmos de escalonamento (Maximum Regret e Greedy) que, além de minimizar o consumo de energia, visam assegurar o cumprimento dos requisitos de qualidade de serviço das aplicações submetidas pelos usuários. Tais algoritmos foram projetados a partir de soluções heurísticas para o problema de escalonamento ciente de consumo de energia em grades móveis, que foi modelado como um problema de otimização envolvendo variáveis binárias. Por meio de experimentos, que consideraram tanto cenários estáticos quanto dinâmicos, foi demonstrada a viabilidade dos algoritmos de escalonamento propostos em relação à redução do consumo de energia. Em seu pior caso, o algoritmo Maximum Regret foi 12,18% pior que o referencial determinado pela melhor solução do solver Gurobi; já no pior caso do algoritmo Greedy, tal diferença foi de apenas 8,14%Considering the context of energy management in mobile grids, this work proposes two scheduling algorithms (Maximum Regret and Greedy) that aim not only to reduce the energy consumption of the mobile devices, but also to ensure the QoS (Quality of Service) requirements of the running applications. These algorithms were designed based on heuristics for the energy aware scheduling problem in mobile grids, which was modeled as an optimization problem with integer variables. The performances of the proposed scheduling algorithms were evaluated by an extensive set of experiments, which demonstrated the feasibility of the adopted approach regarding energy consumption minimization. In its worst case, the Maximum Regret algorithm was 12.18% worse than the best solution provided by the Gurobi solver. While in the Greedys worst case the performance difference was just 8.14%
49
Bountourelis, Theologos. "Efficient pac-learning for episodic tasks with acyclic state spaces and the optimal node visitation problem in acyclic stochastic digaphs." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/28144.
Full textAbstract:
Thesis (M. S.)--Industrial and Systems Engineering, Georgia Institute of Technology, 2009.Committee Chair: Reveliotis, Spyros; Committee Member: Ayhan, Hayriye; Committee Member: Goldsman, Dave; Committee Member: Shamma, Jeff; Committee Member: Zwart, Bert.
50
Angelin, Fernando. "Avaliação mista de aplicações do tipo Bag of Tasks sobre infraestruturas de nuvem física limitada e virtual escalada com a utilização do OpenStack e do CloudSim." Universidade Federal de Pelotas, 2017. http://repositorio.ufpel.edu.br:8080/handle/prefix/3844.
Full textAbstract:
Submitted by Aline Batista (alinehb.ufpel@gmail.com) on 2018-04-19T13:23:06Z
No. of bitstreams: 2
license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5)
Dissertacao_Fernando_Angelin.pdf: 1204993 bytes, checksum: 3cf6b9f14201e8e7168987d5dfd7354b (MD5)Approved for entry into archive by Aline Batista (alinehb.ufpel@gmail.com) on 2018-04-19T14:44:30Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_Fernando_Angelin.pdf: 1204993 bytes, checksum: 3cf6b9f14201e8e7168987d5dfd7354b (MD5)
Made available in DSpace on 2018-04-19T14:44:39Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Dissertacao_Fernando_Angelin.pdf: 1204993 bytes, checksum: 3cf6b9f14201e8e7168987d5dfd7354b (MD5) Previous issue date: 2017-08-30
Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES
A Computação em Nuvem vem apresentando um crescimento extraordinário nos últimos anos, em questão de quantidade e variedade de serviços oferecidos, estes, tomando uma forma onipresente no cotidiano. Com isso, usuários que necessitam, geralmente, de alta disponibilidade de processamento, buscam na Nuvem soluções que diminuam custos pontuais, como construção e manutenção de uma infraestrutura privada. A saída para tal é alugar infraestrutura em uma Nuvem ou até mesmo utilizar a Nuvem para dimensionar uma infraestrutura própria que supra sua demanda, sem sub ou superdimensionamento. Este trabalho apresenta um modelo de simulação mista, o qual busca comparar uma infraestrutura física limitada à uma infraestrutura virtual simulada com as mesmas características. Para isto, foram executados testes em uma infraestrutura física limitada e testes de simulação utilizando o CloudSim, escalando o tamanho das tarefas do tipo Bag of Tasks (BoT) e o número de hosts e núcleos computacionais. Para tais testes foram implementados algoritmos que realizam a transformação da entrada BoT para a execução na infraestrutura física e na simulada. Também, foram prototipadas classes para complementação do CloudSim, tanto para leitura dos BoTs transformados quanto para a criação da infraestrutura simulada.Com os testes realizados, notamos a estabilidade do sistema, quando simulados testes com BoT pequenos, médios e grandes em infraestruturas que, para nosso caso, foram classificadas como pequena, média e grande. Outra observação importante realizada foi a de que quando a infraestrutura oferece carga externa à execução desejada (utilização por outro usuário, por exemplo), o tempo final de execução dos BoTs aumenta proporcionalmente à quanto a infraestrutura está em utilização. Também percebemos que a granularidade das tarefas impacta na execução. Com relação à escalabilidade, foi percebido que BoTs classificados como grandes para infraestruturas categorizadas como pequenas foram agrupados como pequenos para infraestruturas identificadas como grandes.
Cloud Computing has been showing extraordinary growth in recent years, in terms of the quantity and variety of services offered, these, taking a ubiquitous form in everyday life. As a result, users who generally require high availability of processing, search on cloud solutions that reduce specific costs, such as building and maintaining a private infrastructure. The way out is to rent infrastructure in a Cloud or even use the Cloud to size an infrastructure that suits your demand, without sub or oversize. This dissertation presents a mixed simulation model, which seeks to compare a limited physical infrastructure to a simulated virtual infrastructure with the same characteristics. For this, tests were performed on a limited physical infrastructure and simulation tests using CloudSim, scaling the size of Bag of Tasks (BoT) tasks and the number of hosts and processing cores. For such tests, were implemented algorithms that perform the transformation of the BoT input for execution in real infrastructure and simulation. Also, classes to complement CloudSim were prototyped, both for reading the transformed BoTs and for creating the simulated infrastructure. With the tests carried out, we noticed the stability of the system when simulated small, medium and large BoT tests in infrastructures that, in our case, were classified as small, medium and large. Another important observation was that when the infrastructure offers external load to the desired execution (use by another user, for example), the final execution time of the BoTs increases proportionally to how much the infrastructure is in use. We also realize that the granularity of tasks impacts execution. With regard to scalability, it was noticed that BoTs classified as large for infrastructures categorized as small were grouped as small for infrastructures identified as large.