Search

We provide new parameterized complexity results for Interval Scheduling on Eligible Machines. In this problem, a set of n jobs is given to be processed non-preemptively on a set of m machines. Each job has a processing time , a deadline , a weight , and a set of eligible machines that can process it. The goal is to find a maximum weight subset of jobs that can each be processed on one of its eligible machines such that it completes exactly at its deadline. We focus on two parameters: The number m of machines, and the largest processing time p max. Our main contribution is showing W[1] -hardness when parameterized by m. This answers Open Problem 8 of Mnich and van Bevern's list of 15 open problems in parameterized complexity of scheduling problems [Computers & Operations Research, 2018]. Furthermore, we show NP -hardness even when p max = O (1) and present an FPT -algorithm with for the combined parameter m + p max. [ABSTRACT FROM AUTHOR]

Resource scheduling plays a vital role in High-Performance Computing (HPC) systems. Most scheduling research in HPC has focused on only a single type of resource (e.g., computing cores or I/O resource). With the advancement in hardware architectures and the increase in data-intensive HPC applications, there is a need to simultaneously consider a diverse set of resources (e.g., computing cores, cache, memory, I/O, and network resources) in the design of runtime schedulers for improving the overall application performance. In this paper, we study multi-resource scheduling to minimize the makespan of computational workflows comprised of moldable parallel jobs. Moldable jobs allow the scheduler to flexibly select a variable set of resources before execution, thus can adapt to the available system resources (as compared to rigid jobs) while staying easy to design and implement (as compared to malleable jobs). We propose a Multi-Resource Scheduling Algorithm (MRSA), which combines a novel resource allocation strategy and an extended list scheduling scheme to schedule the jobs. We prove that, on a system with d types of schedulable resources, MRSA achieves an approximation ratio of 1.619 d + 2.545 d + 1 for any d ≥ 1 , and a ratio of d + 3 d 2 3 + O (d 3) when d is large (i.e., d ≥ 22). We also present improved approximation results for workflows comprised of jobs with special precedence constraints (e.g., series-parallel graphs, trees, and independent jobs). Further, we prove a lower bound of d on the approximation ratio of any list-based scheduling algorithm with local priority considerations. Finally, we conduct a comprehensive set of simulations to evaluate the performance of the algorithm using synthetic workflows of different structures and moldable jobs following different speedup models. The results show that MRSA fares better than the theoretical bound predicts, and that it consistently outperforms two baseline heuristics under a variety of parameter settings, illustrating its robust practical performance. • We consider a multi-resource scheduling problem for moldable jobs with precedence constraints. • We propose a multi-resource scheduling algorithm (MRSA) for the studied problem. • We prove several approximation results of MRSA for general graphs and some special graphs. • We conduct simulations to evaluate the performance of MRSA under variety of settings. [ABSTRACT FROM AUTHOR]

We analyze time and energy performance of distributed computations in heterogeneous systems with hierarchical memory. Different levels of memory hierarchy have different time and energy efficiency. Core memory may be too small to hold whole load to be processed, while computations using external storage are expensive in time and energy. In order to avoid the costs of processing the load in the external memory, it is allowed that the load is distributed to the worker processors in multiple installments. A minimum energy solution is found by use of mixed integer linear programming under a limit on schedule length. Two types of fast heuristics with several variants are also examined. The trade-off between the criteria of processing time and energy is studied. Key features of optimum solutions are analyzed. It is shown that holding machines in a diverse set of energy modes and limited use of the out-of-core memory can be beneficial for the time and energy performance. The proposed scheduling algorithms are evaluated in the terms of solution quality and runtimes. • Processing big volumes of data on heterogeneous systems with memory hierarchy considered. • Heuristics and MIP-based scheduling algorithms proposed. • Time–energy performance trade-off has local optima caused by idle machine power usage. • Holding machines in a diverse set of energy modes is advantageous. • Heuristic solutions approx. 3 times worse in quality, but in 4–5 orders of magnitude shorter time. [ABSTRACT FROM AUTHOR]

In recent years, large computational problems have beensolved by the distributed environment in which applications are executed in parallel. Also, lately, fog computing or edge computing as a new environment is applied to collect data from the devices and preprocessing is done before sending for main processing in cloud computing. Since one of the crucial issues in such systems is task scheduling, this issue is addressed by considering reducing energy consumption. In this study, an energy-aware method is introduced by using the Dynamic Voltage and Frequency Scaling (DVFS) technique to reduce energy consumption. In addition, in order to construct valid task sequences, a hybrid Invasive Weed Optimization and Culture (IWO-CA) evolutionary algorithm is applied. The experimental results revealed that the proposed algorithm improves some current algorithms in terms of energy consumption. • Proposing an energy-aware task scheduling approach to minimize energy consumption in fog computing. • Presenting a hybrid invasive weed optimization (IWO) along with the cultural evolution algorithm (CEA) for proposed task scheduling approach in fog computing. • Guaranteeing optimal solutions for proposed energy-aware task scheduling approach based on maximum level of QoS factors. [ABSTRACT FROM AUTHOR]

Scheduling plays an important role in improving the performance of big data-parallel processing. Spark is an in-memory parallel computing framework that uses a multi-threaded model in task scheduling. Most Spark task scheduling processes do not take the memory into account, but the number of concurrent task threads determined by the user. It emerges as a potential limitation for the performance. To overcome the limitations in the Spark-core source code, this paper proposes a dynamic Spark memory-aware task scheduler (DMATS), which not only treats memory and network I/O as a computational resource but also dynamically adjusts concurrency when scheduling tasks. Specifically, we first analyze the RDD based Spark execution engine to obtain the amount of task processing data and propose an algorithm for estimating the initial adaptive task concurrency, which is integrated with the known task input information and the executor memory. Then, a dynamic adjustment algorithm is proposed to change the concurrency dynamically through feedback information to optimally utilize the limited memory resources. We implement a dynamic memory-aware task scheduling (DMATS) in Spark 2.3.4 and evaluate performance with two typical benchmarks, shuffle-light and shuffle-heavy. The results show that the algorithm not only reduces the execution time by 43.64%, but also significantly improves resource utilization. Experiments also show that our proposed method has advantages compared with other similar works such as WASP. • Memory resources are considered in Spark task scheduling processes. • We propose dynamic and static scheduling adjustment methods based on memory-aware. • The entire implementation is embedded in the Spark-core process, light and effective. [ABSTRACT FROM AUTHOR]

Modern applications generally need a large volume of computation and communication to fulfill the goal. These applications are often implemented on multiprocessor systems to meet the requirements in computing capacity and communication bandwidth, whereas, how to obtain a good or even the optimal performance on such systems remains a challenge. When tasks of the application are mapped onto different processors for execution, inter-processor communications become inevitable, which delays some tasks' execution and deteriorates the schedule performance. To mitigate the overhead incurred by inter-processor communications and improve the schedule performance, task duplication strategy has been employed in the schedule. Most available techniques for the duplication-based scheduling problem utilize heuristic strategies to produce sub-optimal solutions, however, how to find the optimal duplication-based solution with the minimal schedule makespan remains an unsolved issue. To fill in this gap, this paper proposes a novel Mixed Integer Linear Programming (MILP) formulation for this problem, together with a set of key theorems which enable and simplify the MILP formulation. The proposed MILP formulation can optimize the duplication strategy, serialize the execution of task instances on each processor and determine data precedences among different task instances, thus producing the optimal solution. The proposed method is tested on a set of synthesized applications and platforms and compared with the well-known algorithm. The experimental results demonstrate the effectiveness of the proposed method. • A MILP formulation for the duplication-based scheduling problem is proposed. • A set of optimality theorems are proposed with proof. • The optimality of the proposed method is guaranteed without any premise. • Thorough performance evaluation has been carried out in the paper. [ABSTRACT FROM AUTHOR]

Approximation algorithms for scheduling parallel machines have been studied for decades, leading to significant progress in terms of their approximation guarantees. The algorithms that provide near optimal performance are not feasible to use in practice due to their huge execution time requirements, thus underscoring the importance of developing efficient parallel approximation algorithms with near-optimal performance guarantees that are suitable for execution on current parallel systems, such as multi-core systems. We present the design and analysis of a parallel approximation algorithm for the problem of scheduling jobs on parallel identical machines to minimize makespan. The design of the parallel approximation algorithm is based on the best existing polynomial-time approximation scheme (PTAS) for the problem. To the best of our knowledge, this is the first practical parallel approximation algorithm for the minimum makespan scheduling problem that maintains the approximation guarantees of the sequential PTAS and it is specifically designed for execution on shared-memory parallel machines. We implement and run the algorithm on a large multi-core system and perform an extensive experimental analysis on data generated from realistic probability distributions. The results show that our proposed parallel approximation algorithm achieves significant speedup with respect to both the sequential PTAS and the CPLEX-based solver that solves the mixed integer program formulation of the problem. • A parallel approximation algorithm for scheduling parallel identical machines is proposed. • The proposed algorithm has the same approximation guarantees as the sequential PTAS. • The proposed algorithm is suitable for implementation on multi-core systems. [ABSTRACT FROM AUTHOR]

We investigate the problem of non-clairvoyant scheduling of independent parallel tasks on single and multiple multicore processors. For a single multicore processor, we derive an asymptotic worst-case performance bound for a non-clairvoyant offline scheduling algorithm called largest task first (LTF). The result improves our previous result on a single parallel computing system. For multiple multicore processors, we derive an asymptotic worst-case performance bound for the LTF algorithm. To the best of our knowledge, there has been little result on scheduling parallel tasks on multiple parallel computing systems. For multiple multicore processors, we also derive an asymptotic average-case performance bound for a non-clairvoyant online scheduling algorithm called random task first (RTF). The result extends our earlier result on a single parallel computing system. Extensive simulation results are also demonstrated. • Worst-case performance bound for offline scheduling on a single multicore processor. • Worst-case performance bound for offline scheduling on multiple multicore processors. • Average-case performance bound for online scheduling on multiple multicore processors. [ABSTRACT FROM AUTHOR]

Large-scale interactive Web services break a user's request to many sub-requests and send them to a large number of independent servers so as to consult multi-terabyte datasets instantaneously. Service responsiveness hinges on the slowest server, making the tail of the latency distribution of individual servers a matter of great concern. A large number of latency-sensitive applications hosted on individual servers use thread-driven concurrency model wherein a thread is spawned for each user connection. Threaded applications rely on the operating system CPU scheduler for determining the order of thread execution. Our experiments show that the default Linux scheduler (CFS) idiosyncrasies result in LCFS (Last Come First Served) scheduling of threads belonging to the same application. On the other hand, studies have shown that FCFS (First Come First Served) scheduling yields the lowest response time variability and tail latency, making the default scheduler of Linux a source of long tail latency for multi-threaded applications. In this paper, we present CTS, an operating system CPU scheduler to trim the tail of the latency distribution for latency-sensitive multi-threaded applications while maintaining the key characteristics of the default Linux scheduler (e.g., fairness). By adding new data structures to the Linux kernel, CTS tracks threads belonging to an application in a timely manner and schedules them in FCFS manner, mitigating the tail latency. To keep the existing features of the default Linux scheduler intact, CTS keeps CFS responsible for system-wide load balancing and core level process scheduling; CTS merely schedules threads of the CFS chosen process in FCFS order, ensuring tail latency mitigation without sacrificing the default Linux scheduler properties. Experiments with a prototype implementation of CTS in the Linux kernel demonstrate that CTS significantly outperforms the Linux default scheduler. For example, CTS mitigates the tail latency of a Null RPC server by up to 96%, a Thrift server by up to 90% and an Apache Web server by up to 51% at 99.9th percentile. • It has been proven that FCFS scheduling of threads leads to lower tail latency. • Experiments show that CFS policies lead to LCFS scheduling, aggravating tail latency. • CTS policies ensure FCFS thread scheduling, which yields lower tail latency. • CTS enforces our policies while maintaining the key features of the Linux scheduler. • Experimental results show that CTS significantly outperforms the Linux scheduler. [ABSTRACT FROM AUTHOR]

The job scheduling problem is a classic operations research problem in which agents have jobs to be executed by machines in given time slots, with each machine being able to process only one job at a time. We study this problem using cooperative game theory, focusing on how to divide the minimum cost (of executing all jobs) between the agents. First, we characterize the set of stable allocations, which all charge only users whose jobs are executed in peak-demand time periods. Second, we introduce a number of natural properties that allow to split the cost in a fair and consistent way. Using these desirable properties, we offer axiomatizations for two cost sharing methods that stand out: the peak-demand rule and the peak-interval rule. [ABSTRACT FROM AUTHOR]

Abstract Asymmetric multi-cores (AMCs) are a successful architectural solution for both mobile devices and supercomputers. By maintaining two types of cores (fast and slow) AMCs are able to provide high performance under the facility power budget. This paper performs the first extensive evaluation of how portable are the current HPC applications for such supercomputing systems. Specifically we evaluate several execution models on an ARM big.LITTLE AMC using the PARSEC benchmark suite that includes representative highly parallel applications. We compare schedulers at the user, OS and runtime levels, using both static and dynamic options and multiple configurations, and assess the impact of these options on the well-known problem of balancing the load across AMCs. Our results demonstrate that scheduling is more effective when it takes place in the runtime system level as it improves the baseline by 23%, while the heterogeneous-aware OS scheduling solution improves the baseline by 10%. Highlights • Evaluation of high performance applications on asymmetric multi-core systems. • Comparison of three scheduling approaches taking place on different levels of the software stack. • Analysis of results in terms of: performance, energy consumption and power. • Investigation of different runtime scheduling approaches (e.g. loop vs task-based). [ABSTRACT FROM AUTHOR]

Abstract Modern systems become more vulnerable to soft errors with technology scaling. Providing fault tolerance strategies on all structures in a system may lead to high energy consumption. Our framework with asymmetrically reliable caches with at least one protected core and several unprotected cores dynamically assigns the software threads executing critical code fragments to the protected core(s) with the FCFS-based algorithm. The framework can provide good reliability, performance, and power consumption trade-offs compared with the fully protected and unprotected systems. However, FCFS-based scheduling algorithm may degrade the system performance and unfairly slow down applications for some workloads. In this paper, a set of scheduling algorithms is proposed to improve both the system performance and fairness perspectives. Various static priority techniques that require preliminary information about the applications (such as their execution order, cache usage, number of requests sent to the protected core(s), and total burst time spent on the protected core(s)) are implemented and evaluated. On the other hand, dynamic priority techniques that target to equalize the total time spent of applications on the protected core(s) or the progress of the applications' requests are presented. Extensive evaluations using multi-application workloads validate significant improvements of our static and dynamic priority scheduling techniques on system performance and fairness over the FCFS algorithm. Highlights • We propose static and dynamic scheduling techniques to map application threads. • An asymmetric multicore system with protected and unprotected cores is considered. • Function criticality and vulnerability metrics are utilized for critical code regions. • Application threads executing critical code regions are mapped to the protected cores. • Results of performance and fairness metrics validate proposed scheduling techniques. [ABSTRACT FROM AUTHOR]

We consider the classical scheduling problem on parallel identical machines to minimize the makespan. There is a long history of study on this problem, focusing on exact and approximation algorithms. It is thus natural to consider whether these algorithms can be further improved in terms of running times. We provide strong lower bounds on the running times of exact and approximation schemes for the classical scheduling problem based on Exponential Time Hypothesis, showing that the best known approximation and exact algorithms are almost the best possible in terms of the running time. [ABSTRACT FROM AUTHOR]

With large resource capacity, clouds have become a primary infrastructure for users to store big amount of data and perform large-scale computations. With the increasing demands and diversity of applications’ requirements, users are facing a fundamental problem of management of resources reserved from clouds. Particularly, the problem of load scheduling is the most important since it directly affects the performance of the system. Designing an efficient scheduling strategy for minimizing the total processing time of loads is challenging since it has to consider many intrinsic characteristics of the system such as the availability and heterogeneity of computing nodes, network topology and capacity. In this paper, we propose a novel architecture of a multi-cloud system that can satisfy complex requirements of users’ applications. Based on this architecture, we propose a dynamic scheduling strategy (DSS) that integrates the Divisible Load Theory and node availability prediction techniques to achieve high performance. We conduct intensive simulations to evaluate the performance of the proposed scheduling strategy. The results show that the proposed scheduling strategy outperforms the baseline schemes by reducing the total processing time of loads up to 44.60%. The results also provide useful insights on the applicability of the proposed approach in realistic scenarios. [ABSTRACT FROM AUTHOR]

Many workflow scheduling algorithms for heterogeneous systems have been developed to satisfy multiple requirements such as minimizing schedule length while maximizing throughput. In particular, in list-based scheduling approaches, the schedule length depends on the given nodes as well as the task allocation and ordering policies. This is because the scheduling priority is derived by averaging the execution time and communication time of the given nodes. If the set of nodes can be adjusted before the scheduling tasks, a small schedule length can be achieved. In this paper, we propose a prior node selection algorithm, called lower bound based candidate node selection (LBCNS) to select a subset of given nodes to minimize the schedule length while fairly scheduling each job. Our proposal has two approaches: (i) LBCNS_DEFAULT, which considers the job characteristics and each node’s performance, and (ii) priority-based LBCNS, which additionally takes each scheduling priority into account for a dedicated task scheduling algorithm. The experimental results of extensive simulations show that LBCNS_DEFAULT has the best fairness for scheduling multiple workflow jobs, while priority-based LBCNS achieves the minimum schedule length with the highest efficiency for a single workflow job and multiple workflow jobs. [ABSTRACT FROM AUTHOR]

In this paper, to analyze end-to-end timing behavior in heterogeneous processor and network environments accurately, we adopt and modify a heterogeneous selection value on communication contention (HSV_CC) algorithm, which can synchronize tasks and messages simultaneously, for stream processing distribution. In order to adapt the concepts of a static algorithm like HSV_CC to automotive data stream management system (DSMSs), one must first address three issues: (i) previous task and message schedules might lead to less efficient resource usages in this scenario; (ii) the conventional method to determine the task scheduling order may not be best suited to deal with stream processing graphs, and; (iii) there is a need to be able to schedule tasks with time-varying computational requirements efficiently. To address (i), we propose the heterogeneous value with load balancing and communication contention (HVLB_CC) (A) algorithm, which considers load balancing in addition to the parameters considered by the HSV_CC algorithm. We propose HVLB_CC (B) to address issue (ii). HVLB_CC (B) can deal with stream processing task graphs and more various directed acyclic graphs to prevent assigning a higher priority to successor tasks. In addition, to address issue (iii), we propose HVLB_CC_IC. To schedule tasks more efficiently with various computation times, HVLB_CC_IC utilizes schedule holes left in processors. These idle time slots can be used for the execution of an optional part to generate more precise data results by applying imprecise computation models. Experimental results demonstrate that the proposed algorithms improve minimum schedule length, accuracy, and load balancing significantly compared to the HSV_CC algorithm. In addition, the proposed HVLB_CC (B) algorithm can schedule more varied task graphs without reducing performance, and, using imprecise computation models, HVLB_CC_IC yields higher precision data than HVLB_CC without imprecise computation models. [ABSTRACT FROM AUTHOR]

As massive microprocessors with thousands of cores are on the horizon, using Radio Frequency (RF) or state-of-the-art nanophotonic on-chip interconnects appears as a solution to cope with current latency constraints. Due to their reliance on numerous static circuitry to generate communication channels, proposed architectures cannot rearbitrate the available bandwidth to on-chip nodes according to instantaneous traffic demands. In this paper, we present an Orthogonal Frequency Division Multiple Access (OFDMA) based wired on-chip RF interconnect as an effective reconfigurable and broadcast capable modulation. A hierarchical 2048-core CMP architecture is explained along with its hybrid cache coherency mechanism. Based on this novel architecture, we introduce an innovative bandwidth arbitration mechanism which allocates more bandwidth to cache-line carrying long packets without requiring extra signaling overhead. Exploiting broadcast capability and effective reconfigurability, we show that this bimodal packet aware communication infrastructure can provide up to 10 × less average latency compared to a static counterpart under certain circumstances. [ABSTRACT FROM AUTHOR]

Modern network processors increasingly deal with packets that require heterogeneous processing. We consider a bounded size input queue buffer where each packet requires several rounds of processing before transmission. Usually the transmission order of packets is induced by processing order, but processing order can have significant impact on the performance of buffer management policies even if the transmission order is fixed. We introduce the class of Semi-FIFO policies that decouple processing order from transmission order, restricting the latter to First-In-First-Out (FIFO). We build a taxonomy of Semi-FIFO policies and provide worst case guarantees for different processing orders. We consider various special cases and properties of Semi-FIFO policies: greedy, work-conserving, lazy, and push-out policies, and show how these properties affect performance. We generalize our results to additional constraints related to copying cost and conduct a comprehensive simulation study that validates our results. [ABSTRACT FROM AUTHOR]

We consider the Do-All problem, where p cooperating processors need to complete t similar and independent tasks in an adversarial setting. Here we deal with a synchronous message passing system with processors that are subject to crash failures. Efficiency of algorithms in this setting is measured in terms of work complexity and communication complexity. When work and communication are considered to be comparable resources, then the overall efficiency is meaningfully expressed in terms of effort defined as work + communication . We develop and analyze a constructive algorithm that has work O ( t + p log ⁡ p ( p log ⁡ p + t log ⁡ t ) ) and a nonconstructive algorithm that has work O ( t + p log 2 ⁡ p ) . The latter result is close to the lower bound Ω ( t + p log ⁡ p / log ⁡ log ⁡ p ) on work. The effort of each of these algorithms is proportional to its work when the number of crashes is bounded above by c p , for some positive constant c < 1 . We also present a nonconstructive algorithm that has effort O ( t + p 1.77 ) . [ABSTRACT FROM AUTHOR]

The main challenge for embedded real-time systems, especially for mobile devices, is the trade-off between system performance and energy efficiency. Previous works mainly focused on finding an optimal tasks assignment with the minimum energy under the constraints of time or architecture. In this paper, we propose an Accelerated Search (AS) algorithm based on Dynamic Programming (DP) to obtain a combination of various task schemes which can be completed in a given time with the minimum possible energy by introducing the guaranteed probability and data migration energy. We adopt a DAG (Directed Acyclic Graph) to represent the dependent relation between tasks and develop a Minimum-Energy Model to find the optimal tasks assignment. The heterogeneous multi-core architectures can execute tasks under different voltage levels with DVFS (Dynamic Voltage and Frequency Scaling) which leads to different execution times and different consumption energies. We first design a Minimum Energy Under Probability Constraints (MEUPC) algorithm to assign a proper core and proper voltage level to each task to satisfy the probability constraints with the minimum energy and then a Leaf-Partition (LP) algorithm is used to determine the execution sequence on each core according to the position of the task in DAG. Finally, a Trading Energy For Time (TEFT) algorithm is proposed to explore the opportunity the parallelism of the tasks to reduce the execution time. The experimental results demonstrate that our approach outperforms state-of-the-art algorithms in this field (maximum improvement of 30.7%). [ABSTRACT FROM AUTHOR]

This paper presents a high performance technique for virtualization-unaware scheduling of compute-intensive synchronized (i.e., tightly-coupled) jobs in virtualized high performance computing systems. Online tightly-coupled jobs are assigned/reassigned to clustered virtual machines based on synchronization costs. Virtual machines are in turn assigned/reassigned to clustered physical machines based on CPU load. Our analytical study shows that it is possible to minimize the performance and scalability degradation of high performance computing applications such as ExaScale and PetaScale systems and applications that are recommended to use virtualization technology to achieve higher degree of performability, namely higher utilization, energy efficiency, portability, flexibility and configurability. [ABSTRACT FROM AUTHOR]

Power management through dynamic core, cache and frequency adaptation is becoming a necessity in today’s power-constrained many-core environments. Unfortunately, as core count grows, the complexity of both the adaptation hardware and the power management algorithms increases exponentially. This calls for hierarchical solutions, such as on-chip voltage regulators per-tile rather than per-core, along with multi-level power management. As power-driven adaptation of shared resources affects multiple threads at once, the efficiency in a tile-organized many-core processor architecture hinges on the ability to co-schedule compatible threads to tiles in tandem with hardware adaptations per tile and per core. In this paper, we propose a two-tier hierarchical power management methodology to exploit per-tile voltage regulators and clustered last-level caches. In addition, we include a novel thread migration layer that (i) analyzes threads running on the tiled many-core processor for shared resource sensitivity in tandem with core, cache and frequency adaptation, and (ii) co-schedules threads per tile with compatible behavior. On a 256-core setup with 4 cores per tile, we show that adding sensitivity-based thread migration to a two-tier power manager improves system performance by 10% on average (and up to 20%) while using 4 × less on-chip voltage regulators. It also achieves a performance advantage of 4.2% on average (and up to 12%) over existing solutions that do not take DVFS sensitivity into account. [ABSTRACT FROM AUTHOR]

The minimum-latency broadcast problem in duty-cycled wireless sensor networks has received significant attention over the last few years. A common approach for the problem is to assign collision-free transmitting times to forwarding nodes for disseminating a message from one source node to all other nodes according to their given duty-cycle schedules and transmission ranges. However, preventing collision for all transmissions may increase latency in the broadcast schedules. This paper proposes a novel strategy of Collision-Tolerant Scheduling (CTS) that offers an opportunity to reduce broadcast latency by allowing collisions at non-critical nodes to speed up the broadcast process for critical ones. The completion of broadcast scheduling, i.e. all nodes receive a broadcast message, is ensured by additionally transmitting the message to non-critical nodes experiencing collision. We employ the scheduling strategy in two proposed broadcast schemes: Degree-based CTS (DCTS) and MIS-based CTS (MCTS), which select forwarding nodes based on the node degree and maximal independent set information, respectively. The results of both theoretical analysis and simulation reveal the remarkable advantages of CTS in minimizing broadcast latency in duty-cycled WSNs. DCTS and MCTS guarantee approximation ratios of ( Δ − 1 ) T and 12 T in terms of broadcast latency, where Δ and T denote the maximum node degree and the number of time slots in a working period, respectively. The two schemes reduce to at least 94 percent of the broadcast latency compared with existing schemes, while slightly increasing the number of transmissions due to the additional transmissions. Thanks to the latency reduction, the proposed schemes require 93 percent less energy than existing ones. [ABSTRACT FROM AUTHOR]

We consider the problem of energy-efficient contention-aware application mapping and scheduling on Network-on-Chip (NoC) based multiprocessors. For an application represented by a directed acyclic graph, we present a model where voltage scaling techniques for processors can be combined with frequency tuning techniques for NoC links to save overall system energy consumption. We employ a two-step approach to solve the overall mapping and scheduling problem. First, the application mapping problem is formulated as a quadratic binary programming problem, which aims to minimize the communication energy; we apply a relaxation-based iterative rounding algorithm to solve it. With the mapping achieved, we further consider the application scheduling problem, which aims to find the optimal voltage level for each task of the application and optimal frequency level for each communication of the application to minimize the overall system energy consumption, given the application deadline. To attack the second problem, we first design an algorithm based on the earliest time first scheduling to determine the application’s finish time if a voltage and frequency assignment is given; then, we develop a genetic algorithm to search the solution space for the voltage and frequency assignment that minimizes the overall system energy consumption and meets the application’s deadline. Through these two steps, we produce a mapping and scheduling that meets the application’s deadline, and significantly reduces the overall system energy consumption. Experiments are conducted for a number of randomly generated application graphs, as well as several real application graphs to verify the energy reduction and applicability of the proposed model and algorithms. [ABSTRACT FROM AUTHOR]

Traditional ad-hoc network packet scheduling schemes cannot fulfill the requirements of proximity-based ad-hoc social networks (ASNETs) and they do not behave properly in congested environments. To address this issue, we propose a user popularity-based packet scheduling scheme for congestion control in ASNETs called Pop-aware. The proposed algorithm exploits social popularity of sender nodes to prioritize all incoming flows. Pop-aware also provides fairness of service received by each flow. We evaluate the performance of Pop-aware through a series of simulations. In comparison with some existing scheduling algorithms, Pop-aware performs better in terms of control overhead, total overhead, average throughput, packet loss rate, packet delivery rate and average delay. [ABSTRACT FROM AUTHOR]

Workflow scheduling is a key component behind the process for an optimal workflow enactment. It is a well-known NP-hard problem and is more challenging in the heterogeneous computing environment. The increasing complexity of the workflow applications is forcing researchers to explore hybrid approaches to solve the workflow scheduling problem. The performance of genetic algorithms can be enhanced by the modification in genetic operators and involving an efficient heuristic. These features are incorporated in the proposed Hybrid Genetic Algorithm (HGA). A solution obtained from a heuristic is seeded in the initial population that provides a direction to reach an optimal (makespan)solution. The modified two fold genetic operators search rigorously and converge the algorithm at the best solution in less amount of time. This is proved to be the strength of the HGA in the optimization of fundamental objective (makespan) of scheduling. The proposed algorithm also optimizes the load balancing during the execution side to utilize resources at maximum. The performance of the proposed algorithm is analyzed by using synthesized datasets, and real-world application workflows. The HGA is evaluated by comparing the results with renowned and state of the art algorithms. The experimental results validate that the HGA outperforms these approaches and provides quality schedules with less makespans. [ABSTRACT FROM AUTHOR]

We illustrate and evaluate the potential impact of dynamic resizability on parallel job scheduling. Our ReSHAPE framework includes a job scheduler that supports dynamic resizing of malleable parallel applications. We propose and evaluate new scheduling policies and strategies enabled by the ReSHAPE framework. These strategies use both application performance and user-assigned priorities to inform decisions about expanding or contracting the set of processors assigned to a particular job. Experimental results show that the scheduling policies significantly improve individual job turn around time as well as overall cluster utilization. [ABSTRACT FROM AUTHOR]

Energy-efficient task scheduling is a fundamental issue in many application domains, such as energy conservation for mobile devices and the operation of green computing data centers. Modern processors support dynamic voltage and frequency scaling (DVFS) on a per-core basis, i.e., the CPU can adjust the voltage or frequency of each core. As a result, the core in a processor may have different computing power and energy consumption. To conserve energy in multi-core platforms, we propose task scheduling algorithms that leverage per-core DVFS and achieve a balance between performance and energy consumption. We consider two task execution modes: the batch mode, which runs jobs in batches; and the online mode in which jobs with different time constraints, arrival times, and computation workloads co-exist in the system. For tasks executed in the batch mode, we propose an algorithm that finds the optimal scheduling policy; and for the online mode, we present a heuristic algorithm that determines the execution order and processing speed of tasks in an online fashion. The heuristic ensures that the total cost is minimal for every time interval during a task’s execution. Furthermore, we analyze and derive algorithms with low time complexity for each mode. [ABSTRACT FROM AUTHOR]

To identify the tradeoffs between efficiency and fault-tolerance in dynamic cooperative computing, we initiate the study of a task performing problem under dynamic processes’ crashes/restarts and task injections. The system consists of n message-passing processes which, subject to dynamic crashes and restarts, cooperate in performing tasks that are continuously and dynamically injected to the system. Tasks are not known a priori to the processes. This problem abstracts todays Internet-based computations, such as Grid computing and cloud services, where tasks are generated dynamically and different tasks may become known to different processes. We measure performance in terms of the number of pending tasks, and as such it can be directly compared with the optimum number obtained under the same crash–restart–injection pattern by the best off-line algorithm. Hence, we view the problem as an online problem and we pursue competitive analysis. We propose several deterministic algorithmic solutions to the considered problem under different information models and correctness criteria, and we argue that their performance is close to the best possible offline solutions. We also prove negative results that open interesting research directions. [ABSTRACT FROM AUTHOR]

Scheduling for a directed acyclic graph (DAG) on networked embedded systems is to maximize concurrency and minimize inter-processor communication for minimum end-to-end worst-case response time (WCRT). Time accuracy and synchronization are critical for scheduling on heterogeneous networked embedded systems, where computing and networking are both heterogeneous and deeply jointed. Most algorithms use the upward rank value for task prioritization, and the earliest finish time for processor selection. In order to obtain accurate and efficient schedules in heterogeneous networked systems, the above approaches can be improved. Moreover, synchronization with tasks and messages is critical for end-to-end WCRT. However, task scheduling and message scheduling are isolated in most approaches in communication contention environments. In this paper, a heterogeneity-driven task scheduling algorithm called Heterogeneous Selection Value (HSV) based on the classic model, and a heterogeneity-driven end-to-end synchronized scheduling algorithm called Heterogeneous Selection Value on Communication Contention (HSV_CC) based on the communication contention model are proposed to address the above problems. Both benchmark and extensive experimental evaluation demonstrate significant performance improvement of the proposed algorithms. [ABSTRACT FROM AUTHOR]

Several distributed mutual exclusion algorithms define the order in which requests are satisfied based on the priorities assigned to requests. These algorithms are very useful for real-time applications ones or those where priority is associated to a quality of service requirement. However, priority based strategies may result in starvation problems where high priority requests forever prevent low priority ones to be satisfied. To overcome this problem, many priority-based algorithms propose to gradually increase the priority of pending requests. The drawback of such an approach is that it can violate priority-based order of requests leading to priority inversion. Therefore, aiming at minimizing the number of priority violations without introducing starvation, we have added some heuristics in Kanrar–Chaki priority-based token-oriented algorithm in order to slow down the frequency with which priority of pending requests is increased. Performance evaluation results confirm the effectiveness of our approach when compared to both the original Kanrar–Chaki and Chang’s priority-based algorithms. [ABSTRACT FROM AUTHOR]

This article presents a method of enhancing the efficiency of Grid scheduling algorithms by employing a job grouping method based on priorities and also grouping of Grid machines based on their configuration before implementing a suitable scheduling algorithm within paired groups. The Priority method is employed to group jobs into four groups, while two different methods, SimilarTogether and EvenlyDistributed, are employed to group machines into four groups before implementing the MinMin Grid scheduling algorithm simultaneously. Implementing the scheduling algorithms simultaneously within paired groups (multi-scheduling) ensures a high degree of parallelism, increases throughput and improves the overall performance of scheduling algorithms. Two sets of controlled experiments were carried out on an HPC system. Analysis of results shows that the Priority Grouping method improved the scheduling efficiency by very large margins over the non-grouping method. [ABSTRACT FROM AUTHOR]

Scheduling for energy conservation has become a major concern in the field of information technology because of the need to reduce energy use and carbon dioxide emissions. Previous work has focused on the assumption that a task can be assigned to any processor. In contrast, we initially study the problem of task scheduling on restricted parallel processors. The restriction takes account of affinities between tasks and processors; that is, a task has its own eligible set of processors. We adopt the Speed Scaling (SS) method to save energy under an execution time constraint (on the makespan C max ), and the processors can run at arbitrary speeds in [ s min , s max ] . Our objective is to minimize the overall energy consumption. The energy-efficient scheduling problem, involving task assignment and speed scaling, is inherently complex as it is proved to be NP-complete for general tasks. We formulate the problem as an Integer Programming (IP) problem. Specifically, we devise a polynomial-time optimal scheduling algorithm for the case in which tasks have a uniform size. Our algorithm runs in O ( m n 3 log n ) time, where m is the number of processors and n is the number of tasks. We then present a polynomial-time algorithm that achieves a bounded approximation factor when the tasks have arbitrary-size work. Numerical results demonstrate that our algorithm could provide an energy-efficient solution to the problem of task scheduling on restricted parallel processors. [ABSTRACT FROM AUTHOR]

Scientific problems that depend on processing large amounts of data require overcoming challenges in multiple areas: managing large-scale data distribution, controlling co-placement and scheduling of data with compute resources, and storing, transferring, and managing large volumes of data. Although there exist multiple approaches to address each of these challenges and the complexity of distributed environments, an integrative approach is missing; furthermore, extending existing functionality or enabling interoperable capabilities remains difficult at best. We propose the concept of Pilot-Data to address the fundamental challenges of co-placement and scheduling of data and compute in heterogeneous and distributed environments with interoperability and extensibility as first-order concerns. Pilot-Data is an extension of the Pilot-Job abstraction for supporting the management of data in conjunction with compute tasks. Pilot-Data separates logical data units from physical storage, thereby providing the basis for efficient compute/data placement and scheduling. In this paper, we discuss the design and implementation of the Pilot-Data prototype, demonstrate its use by data-intensive applications on multiple production distributed cyberinfrastructure and illustrate the advantages arising from flexible execution modes enabled by Pilot-Data. Our experiments utilize an implementation of Pilot-Data in conjunction with a scalable Pilot-Job (BigJob) to establish the application performance that can be enabled by the use of Pilot-Data. We demonstrate how the concept of Pilot-Data also provides the basis upon which to build tools and support capabilities like affinity which in turn can be used for advanced data–compute co-placement and scheduling. [ABSTRACT FROM AUTHOR]

Wireless Sensor Network (WSN) enables pervasive, ubiquitous, and seamless communication with the physical world. This paper investigates an optimal cross-layer optimization for WSN with periodic application. A joint energy efficient routing with minimum delay scheduling optimization model is proposed in this paper. The problem is formulated as an Integer Linear Program (ILP) model. The proposed ILP model has multi objectives cost function. The main objective of the proposed model is to maximize network lifetime and to minimize delay. The proposed ILP model represents the operation of Energy-Efficient Distributed Schedule-Based (EEDS) protocol. The ILP model is solved for different network configurations. The solution obtained by solving the proposed ILP model is compared with EEDS simulation results. Although the two solutions show similar behavior, the ILP solution outperforms the solution obtained by EEDS simulation by 28.3%. Moreover, the optimal solutions assuming different objectives are compared together. [ABSTRACT FROM AUTHOR]

The Resource Constrained Project Scheduling Problem, which is considered to be difficult to tackle even for small instances, is a well-known scheduling problem in the operations research domain. To solve the problem we have proposed a parallel Tabu Search algorithm to find high quality solutions in a reasonable time. We show that our parallel Tabu Search algorithm for graphics cards (GPUs) outperforms other existing Tabu Search approaches in terms of quality of solutions and the number of evaluated schedules per second. Moreover, the algorithm for graphics cards is about 10.5/42.7 times faster (J90 benchmark instances) than the optimized parallel/sequential algorithm for the Central Processing Unit (CPU). The same quality of solutions is achieved up to 5.4/22 times faster in comparison to the parallel/sequential CPU algorithm respectively. The advantages of the GPU version arise from the sophisticated data-structures and their suitable placement in the device memory, tailor-made methods, and last but not least the effective communication scheme. [ABSTRACT FROM AUTHOR]

Broadcast is a fundamental operation in Wireless Sensor Networks (WSNs) and plays an important role in a communication protocol design. In duty-cycled scenarios, a sensor node can receive a message only in its active time slot, which makes it more difficult to design collision-free scheduling for broadcast operations. Recent studies in this area have focused on minimizing broadcast latency and guaranteeing that all nodes receive a broadcast message. This paper investigates the problem of Minimum Latency Broadcast Scheduling in Duty-Cycled (MLBSDC) WSNs. By using special geometric properties of independent sets of a broadcast tree, we reduce the number of transmissions, consequently reducing the possibility of collision. Allowing multiple transmissions in one working period, our proposed Latency Aware Broadcast Scheduling (LABS) scheme provides a latency-efficient broadcast schedule. Theoretical analysis proves that the scheme has the same approximation ratio and complexity as the previous best algorithm for the MLBSDC problem. Moreover, simulation shows that the new scheme achieves up to 34%, 37%, and 21% performance improvement over previous schemes, in terms of latency, number of transmissions, and energy consumption, respectively. [ABSTRACT FROM AUTHOR]

Schedulability analysis of real-time multiprocessor systems is usually based on sufficient but not necessary tests that produce pessimistic results. One difficulty in evaluating the effectiveness of sufficient schedulability tests has been distinguishing the cause of a task set failing the test, i.e., finding out whether the task set is in fact not schedulable or it is actually schedulable but the test itself is too pessimistic. Necessary schedulability tests help to distinguish between these two situations, since if a task set fails in the test then it is guaranteed to be unschedulable. An adversary simulator is a scheduling simulator that uses the non-determinism of the task model to generate scenarios that will stress a specific scheduling algorithm, improving the odds of a deadline miss. In this paper we describe a new adversary simulator algorithm for sporadic task sets executed on multiprocessors scheduled by Global Earliest Deadline First (G-EDF). It is shown that this new adversary simulator is more effective as a necessary test than existing approaches. We also estimate the uncertainty regarding G-EDF by applying to the same task sets a well-known sufficient schedulability test from the literature and the necessary schedulability test based on the adversary simulator. [ABSTRACT FROM AUTHOR]

HPC industry demands more computing units on FPGAs, to enhance the performance by using task/data parallelism. FPGAs can provide its ultimate performance on certain kernels by customizing the hardware for the applications. However, applications are getting more complex, with multiple kernels and complex data arrangements, generating overhead while scheduling/managing system resources. Due to this reason all classes of multi threaded machines-minicomputer to supercomputer-require to have efficient hardware scheduler and memory manager that improves the effective bandwidth and latency of the DRAM main memory. This architecture could be a very competitive choice for supercomputing systems that meets the demand of parallelism for HPC benchmarks. In this article, we proposed a Programmable Memory System and Scheduler (PMSS), which provides high speed complex data access pattern to the multi threaded architecture. This proposed PMSS system is implemented and tested on a Xilinx ML505 evaluation FPGA board. The performance of the system is compared with a microprocessor based system that has been integrated with the Xilkernel operating system. Results show that the modified PMSS based multi-accelerator system consumes 50% less hardware resources, 32% less on-chip power and achieves approximately a 19x speedup compared to the MicroBlaze based system. [ABSTRACT FROM AUTHOR]

Abstract: In distributed computing such as grid computing, online users submit their tasks anytime and anywhere to dynamic resources. Task arrival and execution processes are stochastic. How to adapt to the consequent uncertainties, as well as scheduling overhead and response time, are the main concern in dynamic scheduling. Based on the decision theory, scheduling is formulated as a Markov decision process (MDP). To address this problem, an approach from machine learning is used to learn task arrival and execution patterns online. The proposed algorithm can automatically acquire such knowledge without any aforehand modeling, and proactively allocate tasks on account of the forthcoming tasks and their execution dynamics. Under comparison with four classic algorithms such as Min–Min, Min–Max, Suffrage, and ECT, the proposed algorithm has much less scheduling overhead. The experiments over both synthetic and practical environments reveal that the proposed algorithm outperforms other algorithms in terms of the average response time. The smaller variance of average response time further validates the robustness of our algorithm. [Copyright &y& Elsevier]

Highlights: [•] We propose time-aware software defined networking (TaSDN) architecture for OpenFlow-based intra-datacenter optical networks. [•] Time-aware service scheduling (TaSS) strategy is introduced to allocate the network and datacenter resources optimally. [•] The feasibility of architecture is experimentally verified on our testbed with OpenFlow-enabled tunable optical modules. [Copyright &y& Elsevier]

Highlights: [•] Model predictive control is applied to hormone therapy of prostate cancer. [•] Model predictive control tends to delay the relapse later than our previous study. [•] The proposed framework can be used for other diseases. [Copyright &y& Elsevier]

Abstract: As large parallel systems increase in size and complexity, failures are inevitable and exhibit complex space and time dynamics. Most often, in real systems, failure rates are increasing or decreasing over time. Considering non-memoryless failure distributions, we study a bi-objective scheduling problem of optimizing application makespan and reliability. In particular, we determine whether one can optimize both makespan and reliability simultaneously, or whether one metric must be degraded in order to improve the other. We also devise scheduling algorithms for achieving (approximately) optimal makespan or reliability. When failure rates decrease, we prove that makespan and reliability are opposing metrics. In contrast, when failure rates increase, we prove that one can optimize both makespan and reliability simultaneously. Moreover, we show that the largest processing time (LPT) list scheduling algorithm achieves good performance when processors are of uniform speed. The implications of our findings are the accelerated completion and improved reliability of parallel jobs executed across large distributed systems. Finally, we conduct simulations to investigate the impact of failures on the performance, which is done using an actual application of biological sequence comparison. [Copyright &y& Elsevier]

Abstract: Scheduling algorithms have an essential role in computational grids for managing jobs, and assigning them to appropriate resources. An efficient task scheduling algorithm can achieve minimum execution time and maximum resource utilization by providing the load balance between resources in the grid. The superiority of genetic algorithm in the scheduling of tasks has been proven in the literature. In this paper, we improve the famous multi-objective genetic algorithm known as NSGA-II using fuzzy operators to improve quality and performance of task scheduling in the market-based grid environment. Load balancing, Makespan and Price are three important objectives for multi-objective optimization in the task scheduling problem in the grid. Grid users do not attend load balancing in making decision, so it is desirable that all solutions have good load balancing. Thus to decrease computation and ease decision making through the users, we should consider and improve the load balancing problem in the task scheduling indirectly using the fuzzy system without implementing the third objective function. We have used fuzzy operators for this purpose and more quality and variety in Pareto-optimal solutions. Three functions are defined to generate inputs for fuzzy systems. Variance of costs, variance of frequency of involved resources in scheduling and variance of genes values are used to determine probabilities of crossover and mutation intelligently. Variance of frequency of involved resources with cooperation of Makespan objective satisfies load balancing objective indirectly. Variance of genes values and variance of costs are used in the mutation fuzzy system to improve diversity and quality of Pareto optimal front. Our method conducts the algorithm towards best and most appropriate solutions with load balancing in less iteration. The obtained results have proved that our innovative algorithm converges to Pareto-optimal solutions faster and with more quality. [Copyright &y& Elsevier]

Abstract: The selection of the right I/O scheduler for a given workload can significantly improve the I/O performance. However, this is not an easy task because several factors should be considered, and even the “best” scheduler can change over the time, specially if the workload’s characteristics change too. To address this problem, we present a Dynamic and Automatic Disk Scheduling framework (DADS) that simultaneously compares two different Linux I/O schedulers, and dynamically selects that which achieves the best I/O performance for any workload at any time. The comparison is made by running two instances of a disk simulator inside the Linux kernel. Results show that, by using DADS, the performance achieved is always close to that obtained by the best scheduler. Thus, system administrators are exempted from selecting a suboptimal scheduler which can provide a good performance for some workloads, but may downgrade the system throughput when the workloads change. [Copyright &y& Elsevier]

Highlights: [•] NUS is needed to exploit the power on modern instruments in 3D and 4D protein NMR. [•] Random sampling schedules with Poisson-distributed gap lengths minimize artifacts. [•] Enhanced reconstruction speed of hmsIST makes NUS suitable for routine protein NMR. [Copyright &y& Elsevier]

Abstract: We give a polynomial time reduction from the vector scheduling problem (VS) to the generalized load balancing problem (GLB). This reduction gives the first non-trivial online algorithm for VS where vectors come in an online fashion. The online algorithm is very simple in that each vector only needs to minimize the norm of the resulting load when it comes, where is the number of partitions and is the dimension of vectors. It has an approximation bound of , which is in , so it also improves the bound of the existing polynomial time algorithm for VS. Additionally, the reduction shows that GLB does not have constant approximation algorithms that run in polynomial time unless . [Copyright &y& Elsevier]

Abstract: Executing large-scale applications in distributed computing infrastructures (DCI), for example modern Cloud environments, involves optimization of several conflicting objectives such as makespan, reliability, energy, or economic cost. Despite this trend, scheduling in heterogeneous DCIs has been traditionally approached as a single or bi-criteria optimization problem. In this paper, we propose a generic multi-objective optimization framework supported by a list scheduling heuristic for scientific workflows in heterogeneous DCIs. The algorithm approximates the optimal solution by considering user-specified constraints on objectives in a dual strategy: maximizing the distance to the user’s constraints for dominant solutions and minimizing it otherwise. We instantiate the framework and algorithm for a four-objective case study comprising makespan, economic cost, energy consumption, and reliability as optimization goals. We implemented our method as part of the ASKALON environment (Fahringer et al., 2007) for Grid and Cloud computing and demonstrate through extensive real and synthetic simulation experiments that our algorithm outperforms related bi-criteria heuristics while meeting the user constraints most of the time. [Copyright &y& Elsevier]

Abstract: In this work, we study the propagation of influence and computation in dynamic distributed computing systems that are possibly disconnected at every instant. We focus on a synchronous message-passing communication model with broadcast and bidirectional links. Our network dynamicity assumption is a worst-case dynamicity controlled by an adversary scheduler, which has received much attention recently. We replace the usual (in worst-case dynamic networks) assumption that the network is connected at every instant by minimal temporal connectivity conditions. Our conditions only require that another causal influence occurs within every time window of some given length. Based on this basic idea, we define several novel metrics for capturing the speed of information spreading in a dynamic network. We present several results that correlate these metrics. Moreover, we investigate termination criteria in networks in which an upper bound on any of these metrics is known. We exploit our termination criteria to provide efficient (and optimal in some cases) protocols that solve the fundamental counting and all-to-all token dissemination (or gossip) problems. [Copyright &y& Elsevier]