Trang 1
Studies in Computational Intelligence 607 Yacine Laalaoui Nizar Bouguila Editors Artificial Intelligence Applications in Information and Communication Technologies
Nội dung tài liệu
Trang 2
Studies in Computational Intelligence Volume 607 Series editor Janusz Kacprzyk, Polish Academy of Sciences, Warsaw, Poland e-mail: kacprzyk@ibspan.waw.pl
Trang 3
About this Series The series “Studies in Computational Intelligence” (SCI) publishes new develop- ments and advances in the various areas of computational intelligence—quickly and with a high quality. The intent is to cover the theory, applications, and design methods of computational intelligence, as embedded in the fields of engineering, computer science, physics and life sciences, as well as the methodologies behind them. The series contains monographs, lecture notes and edited volumes in computational intelligence spanning the areas of neural networks, connectionist systems, genetic algorithms, evolutionary computation, artificial intelligence, cellular automata, self-organizing systems, soft computing, fuzzy systems, and hybrid intelligent systems. Of particular value to both the contributors and the readership are the short publication timeframe and the worldwide distribution, which enable both wide and rapid dissemination of research output. More information about this series at http://www.springer.com/series/7092
Trang 4
Yacine Laalaoui • Nizar Bouguila Editors Artificial Intelligence Applications in Information and Communication Technologies 123
Trang 5
Editors Yacine Laalaoui Nizar Bouguila Taif University Faculty of Engineering and Computer Taif Science Saudi Arabia Concordia Institute for Information Systems Engineering, Concordia University Montreal, QC Canada ISSN 1860-949X ISSN 1860-9503 (electronic) Studies in Computational Intelligence ISBN 978-3-319-19832-3 ISBN 978-3-319-19833-0 (eBook) DOI 10.1007/978-3-319-19833-0 Library of Congress Control Number: 2015942218 Springer Cham Heidelberg New York Dordrecht London © Springer International Publishing Switzerland 2015 This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. The use of general descriptive names, registered names, trademarks, service marks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. The publisher, the authors and the editors are safe to assume that the advice and information in this book are believed to be true and accurate at the date of publication. Neither the publisher nor the authors or the editors give a warranty, express or implied, with respect to the material contained herein or for any errors or omissions that may have been made. Printed on acid-free paper Springer International Publishing AG Switzerland is part of Springer Science+Business Media (www.springer.com)
Trang 6
Contents Part I Search and Optimization A Metaheuristic for Optimizing the Performance and the Fairness in Job Scheduling Systems . . . . . . . . . . . . . . . . . . . . 3 Dalibor Klusáček and Hana Rudová Hybrid ACO and Tabu Search for Large Scale Information Retrieval . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 Yassine Drias and Samir Kechid Hosting Clients in Clustered and Virtualized Environment: A Combinatorial Optimization Approach . . . . . . . . . . . . . . . . . . . . . . 51 Yacine Laalaoui, Jehad Al-Omari and Hedi Mhalla Part II Machine Learning On the Application of Artificial Intelligence Techniques to Create Network Intelligence. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 Artur Arsenio A Statistical Framework for Mental Targets Search Using Mixture Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99 Taoufik Bdiri, Nizar Bouguila and Djemel Ziou Variational Learning of Finite Inverted Dirichlet Mixture Models and Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 Parisa Tirdad, Nizar Bouguila and Djemel Ziou A Fully Bayesian Framework for Positive Data Clustering . . . . . . . . . 147 Mohamed Al Mashrgy and Nizar Bouguila v
Trang 7
vi Contents Part III Ontologies and Multi-agents Applying Information Extraction for Abstracting and Automating CLI-Based Configuration of Network Devices in Heterogeneous Environments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 A. Martinez, M. Yannuzzi, J. López, R. Serral-Gracià and W. Ramirez MKMSIS: A Multi-agent Knowledge Management System for Industrial Sustainability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 Virgilio López-Morales, Yacine Ouzrout, Thitiya Manakitsirisuthi and Abdelaziz Bouras
Trang 8
Contributors Jehad Al-Omari Department of Information Technology, College of Computers and Information Technology, Taif University, Taif, Saudi Arabia Artur Arsenio YDreams Robotics, Universidade da Beira Interior, Covilhã, Portugal Taoufik Bdiri Department of Electrical and Computer Engineering, Concordia University, Montreal, QC, Canada Nizar Bouguila Concordia Institute for Information Systems Engineering, Concordia University, Montreal, QC, Canada Abdelaziz Bouras Computer Science and Engineering Department, College of Engineering, Qatar University, Doha, Qatar Yassine Drias USTHB, Algeria, Africa Samir Kechid USTHB, Algeria, Africa Dalibor Klusáček Faculty of Informatics, Masaryk University, Brno, Czech Republic Yacine Laalaoui Department of Information Technology, College of Computers and Information Technology, Taif University, Taif, Saudi Arabia Virgilio López-Morales CITIS, Universidad Autónoma del Estado de Hidalgo, Pachuca, Mexico J. López Department of Electronics and Communications Technologies, Autonomous University of Madrid (UAM), Madrid, Spain Thitiya Manakitsirisuthi DISP-Laboratory, Université Lumière Lyon 2, Bron, France A. Martinez Networking and Information Technology Lab (NetIT Lab), Technical University of Catalonia (UPC), Barcelona, Spain vii
Trang 9
viii Contributors Mohamed Al Mashrgy Department of Electrical and Computer Engineering, Concordia University, Montreal, QC, Canada Hedi Mhalla Department of Mathematics and Statistics, The American University of the Middle East, Eqaila, Kuwait Yacine Ouzrout DISP-Laboratory, Université Lumière Lyon 2, Bron, France W. Ramirez Advanced Network Architectures Lab (CRAAX), Technical University of Catalonia (UPC), Barcelona, Spain Hana Rudová Faculty of Informatics, Masaryk University, Brno, Czech Republic R. Serral-Gracià Networking and Information Technology Lab (NetIT Lab), Technical University of Catalonia (UPC), Barcelona, Spain Parisa Tirdad Concordia Institute for Information Systems Engineering, Concordia University, Montreal, QC, Canada M. Yannuzzi Networking and Information Technology Lab (NetIT Lab), Technical University of Catalonia (UPC), Barcelona, Spain Djemel Ziou DI, Faculté des Sciences, Université de Sherbrooke, Sherbrooke, QC, Canada
Trang 10
Introduction Information and Communication Technologies (ICT) is one of the important and climbing sectors in industry. It is part of the computing area and includes the human factor. Humans act as ICT managers, system administrators, network administrators and security experts. ICT challenges include user satisfaction, good performance insurance, security issues handling, etc. Great challenges are yet to come with increase of the Internet and mobile access devices. Often, ICT practitioners do not have sufficient Artificial Intelligence (AI) background to deal with real-life prob- lems. The main aim of this book is to help ICT practitioners in managing efficiently their platforms using AI tools and methods, and to bring up what can AI provides to the ICT sector. This book includes many AI topics namely: search and optimization methods, machine learning, data representation and Ontologies, and multi-agent systems. In “A Metaheuristic for Optimizing the Performance and the Fairness in Job Scheduling Systems”, Klusacek and Rudova present a meta-heuristic-based approach to periodically optimize job scheduling plan in large computational sys- tems such as HPC clusters and Grids. The proposed approach is time efficient extension of Conservative backfilling. In fact, this approach aims at minimizing the bad effects of inaccurate run time estimates while improving performance and guaranteeing good fairness with respect to different users of the system. In “Hybrid ACO and Tabu Search for Large Scale Information Retrieval”, Drias and Kechid use meta-heuristics to tackle the problem of information retrieval (IR) on large-scale web data sets. The authors use a hybridization of two meta-heuristics, namely Ant Colony Optimization and Tabu Search. In “Hosting Clients in Clustered and Virtualized environment: A Combinatorial Optimization Approach”, Laalaoui et al. propose an approach to address the problem of hosting clients (operations systems and applications) on clustered and virtualized environments. The authors describe an integer mathematical model of the problem and use Branch-and-Bound Search to solve the problem. In “On the Application of Artificial Intelligence Techniques to Create Network Intelligence”, Arsenio describes the application of AI and machine learning techniques in several areas related to ICT, namely epidemic detection and control, intelligent buildings monitoring, middleware and cloud robotics (inter ix
Trang 11
x Introduction process communication), Client profiling and Alarm predication in telecommuni- cation networks. In “A Statistical Framework for Mental Targets Search Using Mixture Models”, Bdiri et al. utilize machine learning techniques to search specific target based on visual features. The authors’ main objective is to improve the human–machine interaction. In “Variational Learning of Finite Inverted Dirichlet Mixture Models and Applications”, Tirdad et al. use statistics and machine learning to solve the problem of data modeling. The proposed framework has been applied to the challenging tasks of natural scene categorization and human activity classi- fication. In “A Fully Bayesian Framework for Positive Data Clustering”, Al Mashrgy and Bouguila propose a Bayesian framework for data modeling. The main objective is to enhance the clustering process of positive data. The applicability of the proposed model is shown in the real-life problem of object detection. In “Applying Information Extraction for Abstracting and Automating CLI-Based Configuration of Network Devices in Heterogeneous Environments”, Martinez et al. present a tool to automate/simplify the administration of network devices in heterogeneous environments. The proposed tool uses the Information Extraction and knowledge representation, from a designed ontology, and natural language processing of provided Command Line Interfaces. Finally, “MKMSIS: A Multi- agent Knowledge Management System for Industrial Sustainability” by Lopez et al. describes a framework for collaborative development to comply with environmental sustainability using multi-agent technology.
Trang 13
A Metaheuristic for Optimizing the Performance and the Fairness in Job Scheduling Systems Dalibor Klusáˇcek and Hana Rudová Abstract Many studies in the past two decades focused on the problem of efficient resource management and job scheduling in large computational systems such as HPC clusters and Grids. For this purpose, the application of Artificial Intelligence- based methods such as metaheuristics has been proposed in many works. This chapter provides an overview of such works that involve metaheuristics and discusses why mainstream resource management and scheduling systems are instead using only a limited set of rather simple scheduling policies. We identify several reasons that are causing this situation, e.g., a common use of overly simplified problem definitions with rather naive job and machine models or an application of unrealistic optimization criteria. In order to solve aforementioned issues, this chapter proposes new complex and well designed approaches that involve the use of metaheuristic which periodically optimizes job scheduling plan using several real life based optimization criteria. Importantly, approaches described in this chapter are successfully used in practice, i.e., within a production job scheduler which manages the computing infrastructure of the Czech Centre for Education, Research and Innovation in ICT (CERIT Scientific Cloud). Keywords Job scheduling ·Metaheuristic ·Optimization ·Fairness 1 Introduction The job scheduling problem is known to be very demanding, especially when large and heterogeneous computer environments such as computer clusters and Grids are considered. Here, both users and resource owners should be satisfied simultaneously. Typically, resource owners prefer to keep the overall resource usage reasonably high D. Klusáˇcek (B) · H. Rudová Faculty of Informatics, Masaryk University, Brno, Czech Republic e-mail: xklusac@fi.muni.cz H. Rudová e-mail: hanka@fi.muni.cz © Springer International Publishing Switzerland 2015 3 Y. Laalaoui and N. Bouguila (eds.), Artificial Intelligence Applications in Information and Communication Technologies, Studies in Computational Intelligence 607, DOI 10.1007/978-3-319-19833-0_1
Trang 14
4 D. Klusáˇcek and H. Rudová while users request short wait times. At the same time, fairness has shown to be one of the most important factors to keep users satisfied [1, 2]. Therefore the users should be treated in a fair fashion, such that the available computing power is fairly distributed among them [1]. Last but not least, the predictability, i.e., planning func- tionality [3, 4] is very useful as it allows users to better understand when and where their jobs will be executed. In fact, even experienced users often do not understand the scheduling decisions as delivered by existing scheduler that does not use planning functionality [2]. In order to meet these goals sophisticated and automated schedul- ing techniques should be applied, allowing to handle all requirements in an efficient manner. On the other hand, these techniques must remain robust and time-efficient as the system is typically highly dynamic. Then, reactions of the scheduler must remain fast in order to properly reflect continuously changing state of the system. In order to solve this problem efficiently, many studies considered the application of Artificial Intelligence-based methods such as metaheuristics [5]. Despite this large effort, mainstream resource management and scheduling systems are still using only a limited set of scheduling policies [6]. A typical scheduling system relies on job queues with priorities, while backfilling—a simple optimization of (priority) First Come First Served (FCFS) policy developed in 1995 in order to increase resource utilization—is typically the most advanced option available [7]. Obviously, there must be some good reason why Artificial Intelligence (AI) based methods are not usually used in practice. Therefore, this chapter provides an overview of existing works that involve metaheuristics. We identify several reasons why mainstream systems still rely on rather simple scheduling policies. As we show, existing works using AI methods often use simplified problem definitions with rather naive job and machine models. For example, authors often assume that (exact) job processing times are known in advance, which allow for the construction of accurate job schedules. However, such an assumption is far from reality since only highly inaccurate estimates are usually available, and an actual processing time is only known when a job actually completes its execution [4]. Moreover, although the real system should be represented as a multi-criteria optimization problem, many works use simplified approaches involving single criterion. Also, metaheuristics are frequently considered as “slow” and “static” in contrast to the widely used queue-based approaches that allow for fast and dynamic decisions that are required in real systems. This chapter—building upon and extending the results of the Ph.D. thesis [8]— demonstrates that aforementioned issues can be successfully addressed by using complex and well designed approaches. In the second part of the chapter, we apply a metaheuristic algorithm to optimize the initial job schedule which is created by the well known Conservative backfilling [4] scheduling algorithm. Unlike many existing works that often focus only on the performance-related criteria, we simultaneously optimize several real life based optimization criteria. Notably, we emphasize the fairness with respect to different users of the system, as this is a very important real life based requirement. The application of a metaheuristic largely improves the performance and fairness of Conservative backfilling while also outperforming
Trang 15
A Metaheuristic for Optimizing the Performance and the Fairness … 5 other classical techniques. Moreover, our solution outperforms those widely used scheduling techniques even when realistic (very inaccurate) job processing time estimates are used. At the same time, it does not introduce any major overhead thanks to the application of properly designed execution model and efficient data structures [9]. Last but not least, algorithms and approaches described in this chapter were reimplemented within a production job scheduler that manages the computing infrastructure of the Czech Centre for Education, Research and Innovation in ICT (CERIT Scientific Cloud), already demonstrating their usefulness in practice. This chapter is organized as follows. First, we define the studied problem. Next, an overview of existing scheduling techniques is presented. Especially, the fair- ness and the problems related to the inaccurate job processing times estimates are emphasized. Also, several existing works that use advanced scheduling methods like metaheuristics are presented. Section 4 describes the proposed complex extension of Conservative backfilling including the metaheuristic. Section 5 presents experi- mental evaluation of the proposed solution demonstrating good performance of our approach. Finally, we conclude with a short description of the production scheduler that uses the proposed solution in practice and we discuss the future work. 2 Problem Description In this section we describe the investigated job scheduling problem. In general, the goal of the scheduler is to allocate users’ jobs on available machines in time. During this process, jobs requirements concerning corresponding machines parameters must be satisfied. Also, one or more optimization criteria are followed by the scheduler. Therefore, we will further describe characteristics of considered machines and jobs and we will also define a set of optimization criteria that are used when evaluating the quality of generated solutions. 2.1 Machines A considered system is composed of one or more computer clusters and each cluster is composed of several machines. So far, we expect that all machines within one cluster have the same parameters, e.g., the number of CPUs and the CPU speed. All machines within a cluster use the Space Slicing processor allocation policy [10] which allows parallel execution of several jobs at the cluster when the total amount of requested CPUs is less than or equal to the number of CPUs of the cluster. Therefore, several machines within the same cluster can be co-allocated to process a given parallel job. On the contrary, co-allocation of machines belonging to different clusters is not supported.
Trang 16
6 D. Klusáˇcek and H. Rudová 2.2 Jobs A job represents a user’s application. In total, there are n jobs in the system which arrive over the time. Therefore the arrival timerj of each job is specified. There are no precedence constraints among jobs. Job may require one (sequential) or more CPUs (parallel), denoted as usagej. Job runtime is denoted as pj (processing time). Let Sj and Cj represent the start time and the completion time of the job j respectively. Since we do not consider job preemptions Cj = Sj + pj holds for every job j. An actual runtime (processing time) is typically unknown to a scheduling algorithm until a job completes. Instead of that, only an estimate is usually known in advance. Such an estimate is denoted as epj (estimated processing time). Let us briefly describe the assumptions that can be made concerning job runtime estimates. In a real system, these estimates are usually provided by users and are very inaccurate [4, 11]. Also, users may not specify these estimates at all. Although runtime estimates may not be strictly required, most scheduling systems favor those users who are able to provide such information. Their jobs can be used for backfilling (see Sect. 3.1) which increases utilization and decreases wait times. If no user estimate is provided, the default queue time limit can be used instead, since nowadays systems typically use more queues that specify the maximum allowed runtime of a job [12]. A runtime estimate or a queue time limit is the maximum time limit that a job can execute. In case that a job exceeds its available runtime it is killed immediately [4, 11]. As a result, an actual job runtime pj is always bounded by its estimate, i.e., pj ≤ epj. 2.3 Optimization Criteria There are plenty of optimization criteria that are used both in theory and prac- tice. In this chapter, the quality of generated solutions is measured using several performance-related as well as fairness-related criteria. 2.3.1 Performance-Related Criteria The avg. response time [10] represents the average time a job spends in a system, i.e., the time from its submission to its termination (Eq. 1). The avg. bounded slow- down [10] is the mean value of all jobs’ bounded slowdowns. Bounded slowdown is the ratio of the actual response time of the job to the response time if executed without any waiting1 (Eq. 2). Avg. wait time [13] is the mean time that jobs spend waiting before their executions start (Eq. 3). 1To avoid huge slowdowns of extremely short jobs, the minimal job runtime is bounded by some predefined time constant (e.g., 10 s), sometimes called a “threshold of interactivity” [10].
Trang 17
A Metaheuristic for Optimizing the Performance and the Fairness … 7 1 ∑n RT = (Cj − rj) (1) n j=1 ∑n ( ) 1 Cj − rj BSD = (2) n max(10, pj) j=1 1 ∑n WT = (Sj − rj) (3) n j=1 As pointed out by Feitelson et al. [10], the use of response time places more weight on long jobs and basically ignores if a short job waits few minutes, so it may not reflect users’ notion of responsiveness. Slowdown reflects this situation, measuring the responsiveness of a system with respect to a job length, i.e., jobs are completed within the time proportional to a job length. Wait time criterion supplies the slowdown and the response time. Short wait times prevent the users from feeling that the scheduler “forgot about their jobs”. Of course, also the time complexity of considered scheduling algorithms is of interest. For this purpose we measure the avg. runtime of a scheduling algorithm per job. It measures the mean CPU time needed by a scheduling algorithm to develop a scheduling decision for one job (see Eq. 4 where ARj is the CPU time that a given scheduling algorithm utilizes to develop a scheduling decision(s) for a given job j). 1 ∑n AR = ARj (4) n j=1 2.3.2 Fairness-Related Criteria Previous criteria mostly focused on an overall job performance. Still, good perfor- mance is not the only aspect that makes the scheduler acceptable. The scheduler must also be fair, i.e., it must guarantee that the available computing power is fairly distrib- uted among the users of the system. Currently, there is no widely accepted standard- ized metric to measure fairness and different authors use different metrics [14–16]. An overview of existing techniques including discussion of their suitability can be found in [2]. Very often, the fairness is understood and represented as a job-related metric, meaning that every job should be served in a fair fashion with respect to other jobs [14–16]. Such requirements are already partially covered by the common per- formance criteria like the slowdown and the wait time that were both discussed earlier. However, we aim to guarantee fair performance to different users of the sys- tem as well. Therefore, we use a different metric which is inspired by the well known fair-share principle [1, 17] that is commonly used in production systems [17] (see Sect. 3.3). Just like fair-share, we try to minimize the differences among (normalized)
Trang 18
8 D. Klusáˇcek and H. Rudová mean wait times of all users. Let o be a given user (job owner) in the system and J OBSo be the set containing jobs of user o. Then the normalized user wait time (NUWTo) for each user (job owner) o is calculated as shown by Eq. 5. TUWTo NUWTo = (5) TUSAo ∑ ( ) TUWTo = Sj − rj (6) j∈J OBSo ∑ ( ) TUSAo = pj · usagej (7) j∈J OBSo NUWTo is the total user wait time (see TUWTo in Eq. 6) divided (normalized) by the so called total user squashed area (see TUSAo in Eq. 7), which can be described as the sum of products of a job runtime (pj) and the number of requested processors (usagej). The normalization is used to prioritize less active users over those who utilize the system resources very frequently [1]. Since users wait times are considered as well, a higher priority is given to users with large wait times. The normalized user wait time (NUWTo) metric can be used “on the fly” by the scheduling algorithm to dynamically prioritize users. Also, it can be used in graphs with experimental results (see Fig. 3) to reflect the resulting (un)fairness of an applied scheduling algorithm. In this case, the interpretation is following. The closer the resulting NUWTo values of all users are to each other, the higher is the fairness. If the NUWTo value is less than 1.0, it means that the user spent more time by computing than by waiting, which is advantageous. Similarly, values greater than 1.0 indicate that the total user wait time is larger than the computational time of his or her jobs. 3 Overview of Existing Scheduling Approaches In this section we describe existing approaches in the area of (parallel) job scheduling in computing clusters and Grids. First, we describe several widely used scheduling algorithms, discussing their overall suitability. Next, we explain the crucial role of (inaccurate) job runtime estimates on the performance of existing solutions. Then, methods to reflect fairness are explained. Finally, we show how advanced AI-based methods such as metaheuristics can be used to optimize job schedules with respect to applied optimization criteria.
Trang 19
A Metaheuristic for Optimizing the Performance and the Fairness … 9 3.1 Standard Scheduling Algorithms All major production systems such as PBS Pro [12], TORQUE [18], LSF are so called queuing systems. It means that these systems follow the queue-based scheduling approach, using one or more incoming queues where jobs are stored until they are scheduled for execution. Job ordering (queue prioritization) and job selection is done using some scheduling policy. Often, these policies are based either on (priority)First Come First Served (FCFS)[12, 19] or on thebackfillingalgorithm [19]. FCFS always schedules the first job in the queue, checking the availability of the resources required by such job. If all the resources required by the first job in the queue are available, it is immediately scheduled for the execution, otherwise FCFS waits until all required resources become available. While the first job is waiting for the execution none of the remaining jobs can be scheduled, even if required resources are available. Despite its simplicity, FCFS approach presents several advantages. It does not require an estimated processing time of the job and it guarantees that the response time of a job that arrived earlier does not depend on the execution times of jobs that arrived later. On the other hand, if parallel jobs are scheduled the strict FCFS ordering of job selection often implies a low utilization of the system resources, that cannot be used by some “less demanding” job(s) from a queue [14, 19]. To solve this problem algorithms based on backfilling are frequently used [4]. Algorithms usingbackfillingrepresent an optimization of the FCFS algorithm that try to maximize resource utilization [19]. There are several variants of backfilling algorithms. The most popular one is the aggressive EASY backfilling [4]. It works as FCFS but when the first job in the queue cannot be scheduled immediately, EASY backfilling calculates the earliest possible starting time for the first job using the processing time estimates of running jobs. Then, it makes a reservation to run the job at this pre-computed time. Next, it scans the queue of waiting jobs and schedules immediately every job not interfering with the reservation of the first job [19]. This helps to increase the resource utilization, since idle resources are backfilled with suitable jobs, while decreasing the average job wait time. EASY backfilling takes an aggressive approach that allows short jobs to skip ahead provided they do not delay the job at the head of the queue. The price for improved utilization of EASY backfilling is that execution guarantees cannot be made because it is hard to predict the size of delays of jobs in the queue. Since only the first job gets a reservation, the delays of other queued jobs may be, in general, unbounded [4].2 Therefore, without further control, EASY does not guarantee fairness and may cause a huge job starvation. In order to prevent such situation, several approaches can be taken. First, the number of reservations can be increased. In case of slack-based [20] and selective backfilling [16] the number of jobs with a reservation is related to their current wait time and slowdown respectively. Conservative backfilling [16, 21, 22] makes 2If a job is not the first in the queue, new jobs that arrive later may skip it in the queue. While such jobs do not delay the first job in the queue, they may delay all other jobs and the system cannot predict when a queued job will eventually run [4].
Trang 20
10 D. Klusáˇcek and H. Rudová reservation for every queued job which cannot be executed at a given moment. It means that backfilling is performed only when it does not delay any previous job in the queue. Clearly, this reduces the core problem of EASY backfilling where jobs close to but not yet at the head of the queue can be significantly delayed. The price paid is that the number of jobs that can utilize existing gaps is reduced, implying that more gaps are left unused in Conservative backfilling than in EASY backfilling [23]. Still, both approaches lead to significant performance improvements compared to FCFS [24]. As the scheduling decisions are made upon job submittal, it can be predicted when each job will run, giving the users execution guarantees. Users can then plan ahead based on these guaranteed response times. Obviously, there is no danger of starvation as a reservation is made for every job that cannot be executed immediately. Apparently, such approach places a greater emphasis on predictability [4, 21] and it is a good compromise between “fair” but inefficient FCFS and “unfair” but efficient EASY backfilling. 3.2 Scheduling with Job Runtime Estimates The use of reservations in, e.g., the backfilling algorithms brings one major problem. In order to create accurate schedules and reservations, reasonably precise job runtime estimates are required to allow efficient and accurate predictions. The more precise these estimates are, the better results can be expected from these techniques [25, 26]. In current systems, estimates are usually specified either by a user or by a predefined time limit associated with a queue. Sadly, such estimates are typically very inaccurate and overestimated [4, 25, 27] as we have discussed in Sect. 2.2. 3.2.1 Existing Approaches Surprisingly, many works ignore this problem [28–30] and expect that precise run- time estimates are available. However, this represents rather unrealistic problem. As far as we know, those solutions that use inaccurate runtime estimates often follow similar approach, i.e., they re-compute the schedule from scratch when an inaccurate runtime estimate is detected due to an early job completion [3, 4, 31]. Let us have a look at the procedure applied in Conservative backfilling. Here— as a result of the overestimated runtime—jobs can usually start earlier [4, 21] than their reservations allow. The first solution is to leave existing reservations intact, disregarding that earlier time slots are appearing. Sadly, such a solution is very inef- ficient. Another solution is to cancel all existing reservations and re-backfill all jobs according to a new situation and establish new reservations [4]. However, this may violate the system’s execution guarantees that were provided by the previous—now canceled—reservations [4]. Backfilling allows later jobs to skip over jobs that arrived earlier, provided a suitable gap is found in the reservations’ schedule. This can only happen when the available gap is smaller than the size of some earlier job, but large
Hiển thị 20 trang đầu. Tải tài liệu để xem đầy đủ.
Bình luận (0)
Chưa có bình luận nào. Hãy là người đầu tiên!