非精确计算中基于反馈的CPU在线调度算法

随着家庭网络中的多媒体服务器和实时数据库服务器这类应用对实时的灵活性的要求不断增加,传统实时基于最长执行时间(WCET)的调度算法已经不能满足它们对性能优化的要求.因此,产生了一些软实时的调度算法来解决这些问题.提出了一种由反馈环节控制的实时调度算法,该算法用于调度能使用不精确计算模型描述的进程.算法可以在各种负载条件下,通过在调度过程中引入的反馈控制,在计算精度和计算时间上直接取得折衷,将进程错过时限的比例控制在预定范围内.     

Efficient genetic algorithms using discretization scheduling

In many applications of genetic algorithms, there is a tradeoff between speed and accuracy in fitness evaluations when evaluations use numerical methods with varying discretization. In these types of applications, the cost and accuracy vary from discretization errors when implicit or explicit quadrature is used to estimate the function evaluations. This paper examines discretization scheduling, or how to vary the discretization within the genetic algorithm in order to use the least amount of computation time for a solution of a desired quality. The effectiveness of discretization scheduling can be determined by comparing its computation time to the computation time of a GA using a constant discretization. There are three ingredients for the discretization scheduling: population sizing, estimated time for each function evaluation and predicted convergence time analysis. Idealized one- and two-dimensional experiments and an inverse groundwater application illustrate the computational savings to be achieved from using discretization scheduling.     

基于集束搜索和银行家算法的柔性制造系统无死锁调度

本文提出了一种基于启发式规则的无死锁调度算法,该算法基于集束搜索方法,局部评价函数和全局评价函数,在无缓冲区的情况下,采用单步前瞻的银行家算法来避免死锁。该算法可以迅速解决复杂制造系统的死锁和调度问题,折衷了计算时间的消耗和调度结果的质量。     

Optimal Sequencing of Contract Algorithms

We address the problem of building an interruptible real-time system using non-interruptible components. Some artificial intelligence techniques offer a tradeoff between computation time and quality of results, but their run-time must be determined when they are activated. These techniques, called contract algorithms, introduce a complex scheduling problem when there is uncertainty about the amount of time available for problem-solving. We show how to optimally sequence contract algorithms to create the best possible interruptible system with or without stochastic information about the deadline. These results extend the foundation of real-time problem-solving and provide useful guidance for embedding contract algorithms in applications.     

Problem partitioning in parallel processor simulation systems

Problem partitioning to solve ordinary differential equations on a parallel processor system using classical numerical integration methods involves defining and ordering computation tasks and scheduling the tasks for execution, In defining tasks there is a tradeoff between decomposing a computation into a large number of primitive tasks to expose all potential parallelism and decomposing it into a smaller number of tasks to simplify scheduling. Scheduling is an intractable problem; heuristic scheduling algorithms reduce the effort required to schedule tasks but cannot guarantee that the parallel solution will execute in minimum time. An example illustrates difficulties encountered in scheduling tasks for parallel computation and use of a dependency graph as a tool in problem partitioning. The need for an efficient mechanism for asynchronous data exchanges among processors is demonstrated.     

基于不精确计算移动实时数据库服务质量管理

移动实时数据库服务应用逐渐广泛,但系统负载不可预测和有限资源常导致事务重启或夭折,给系统带来损失甚至灾难。传统的基于最长执行时间实时调度算法已不能满足性能要求,提出结合不精确计算和反馈控制的新算法。考虑更新数据对象间联系并结合时间和值域有效性,提出性能新参数标准去保证系统性能和服务质量。通过仿真实验表明：算法可从稳定性能和暂态性能保证系统预定的服务质量规范。     

实时人工智能系统的构成

实时人工智能系统是一种在动态的环境中，能够利用有限的资源来可靠地完成关键性任务的系统，Anytime算法能够折衷解的质量和计算时间，是构造实时人工智能系统的有效技术，本文阐述了构造方法和组织问题，并给出了关键性的时间分配算法。     

Nonmigratory Multiprocessor Scheduling for Response Time and Energy

Energy usage has been an important concern in recent research on online job scheduling, where processors are allowed to vary the speed dynamically so as to save energy whenever possible. Notice that providing good quality of service such as response time (flow time) and conserving energy are conflicting objectives. An interesting problem for scheduling is how to optimize an economic tradeoff of flow time and energy. To this end, the past two years have witnessed significant progress in the single-processor setting, and online algorithms with performance close to optimal have been obtained. In this paper we extend the study of optimizing the tradeoff between flow time and energy to the multi-processor setting. We derive and analyze a simple non-migratory online algorithm that makes use of the classified-round-robin (CRR) strategy to dispatch jobs. Even in the worst case, its performance is within O(log P) times of the optimal migratory offline algorithm, where P is the ratio of the maximum job size to the minimum job size. Technically speaking, this online result stems from a non-trivial solution to an offline problem of eliminating migration, which is also interesting by itself.     

Scheduling multiple task graphs with end-to-end deadlines in distributed real-time systems utilizing imprecise computations

In order to meet the inherent need of real-time applications for high quality results within strict timing constraints, the employment of effective scheduling techniques is crucial in distributed real-time systems. In this paper, we evaluate by simulation the performance of strategies for the dynamic scheduling of composite jobs in a homogeneous distributed real-time system. Each job that arrives in the system is a directed acyclic graph of component tasks and has an end-to-end deadline. For each scheduling policy, we provide an alternative version which allows imprecise computations, taking into account the effects of input error on the processing time of the component tasks of a job. The simulation results show that the alternative versions of the algorithms outperform their respective counterparts. To our knowledge, an imprecise computations approach for the dynamic scheduling of multiple task graphs with end-to-end deadlines and input error has never been discussed in the literature before.     

Hybrid solution algorithms for task scheduling problem with moving executors

Heuristic algorithms for solving the task scheduling problem with moving executors to minimize the sum of completion times are considered. The corresponding combinatorial optimization problem is formulated. Three hybrid solution algorithms are introduced. As a basis an evolutionary algorithm is assumed that is combined with the procedure that uses simulated annealing metaheuristics. The results of simulation experiments are given in which the influence of parameters of the solution algorithms as well as of the number of tasks on the quality of scheduling and on the time of computation is investigated.     

基于环网的多DSP系统的并行算法的设计

在基于环网的多ＤＳＰ系统上,应用并行块处理的策略讨论了并行算法设计的调度模型;对可１００％利用的ＤＳＰ数目及调度模型的２个关键参数：块处理的时间和ＤＳＰ间的延迟时间进行了具体的分析;将ＤＳ寂的处理过程和Ｉ／Ｏ设备上的处理过程分开,得到了更加接近真实计算环境的调度模型;给出了算法的性能评价准则;对ＦＩＲ滤波器的并行算法进行了具体的设计和实现,在模拟环境下的测试结果表明,应用以上确定工模型的关键参数的     

Algorithms for scheduling real-time tasks with input error andend-to-end deadlines

This paper describes algorithms for scheduling preemptive, imprecise, composite tasks in real-time. Each composite task consists of a chain of component tasks, and each component task is made up of a mandatory part and an optional part. Whenever a component task uses imprecise input, the processing times of its mandatory and optional parts may become larger. The composite tasks are scheduled by a two-level scheduler. At the high level, the composite tasks are scheduled preemptively on one processor, according to an existing algorithm for scheduling simple imprecise tasks. The low-level scheduler then distributes the time budgeted for each composite task across its component tasks so as to minimize the output error of the composite task     

A scheduling algorithm for applications in a cloud computing system with communication changes

This paper proposes a scheduling algorithm to solve the problem of task scheduling in a cloud computing system with time‐varying communication conditions. This algorithm converts the scheduling problem with communication changes into a directed acyclic graph (DAG) scheduling problem for existing fuzzy communication task nodes, that is, the scheduling problem for a communication‐change DAG (CC‐DAG). The CC‐DAG contains both computation task nodes and communication task nodes. First, this paper proposes a weighted time‐series network bandwidth model to solve the indefinite processing time (cost) problem for a fuzzy communication task node. This model can accurately predict the processing time of a fuzzy communication task node. Second, to address the scheduling order problem for the computation task nodes, a dynamic pre‐scheduling search strategy (DPSS) is proposed. This strategy computes the essential paths for the pre‐scheduling of the computation task nodes based on the actual computation costs (times) of the computation task nodes and the predicted processing costs (times) of the fuzzy communication task nodes during the scheduling process. The computation task node with the longest essential path is scheduled first because its completion time directly influences the completion time of the task graph. Finally, we demonstrate the proposed algorithm via simulation experiments. The experimental results show that the proposed DPSS produced remarkable performance improvement rate on the total execution time that ranges between 11.5% and 21.2%. In view of the experimental results, the proposed algorithm provides better quality scheduling solution that is suitable for scientific application task execution in the cloud computing environment than HEFT, PEFT, and CEFT algorithms.     

Resource-bounded sensing and planning in autonomous systems

This paper is concerned with the implications of limited computational resources and uncertainty on the design of autonomous systems. To address this problem, we redefine the principal role of sensor interpretation and planning processes. Following Agre and Chapman's plan-as-communication approach, sensing and planning are treated as computational processes that provide information to an execution architecture and thus improve the overall performance of the system. We argue that autonomous systems must be able to trade off the quality of this information with the computational resources required to produce it. Anytime algorithms, whose quality of results improves gradually as computation time increases, provide useful performance components for time-critical sensing and planning in robotic systems. In our earlier work, we introduced a compilation scheme for optimal composition of anytime algorithms. This paper demonstrates the applicability of the compilation technique to the construction of autonomous systems. The result is a flexible approach to construct systems that can operate robustly in real-time by exploiting the tradeoff between time and quality in planning, sensing and plan execution.     

通过内容自适应改善Web服务器服务质量

在近似计算算法基础上,提出了一个最高优先级优先（Highest-Priority-First,HPF）算法。在HPF算法基础上,设计了一个Web内容自适应的PIK机制来代替传统Web服务机制,并通过修改ApacheWeb服务器软件,实现了一个基于Web内容树结构的内容自适应PIK机制。通过对PIK机制仿真实验表明,PIK机制提高了Web服务器对请求的响应质量和响应率,它为研究Web服务器区分服务和服务质量问题提供了一种新技术思路。     

Multi-directional local search for a bi-objective dial-a-ride problem in patient transportation

This paper considers a generalization of a bi-objective dial-a-ride problem, incorporating real-life characteristics of patient transportation. It studies the impact of combination restrictions, preventing particular user combinations and limiting the set of drivers to which particular users can be assigned. The academic literature currently lacks insights into the effect of these restrictions on the cost structure of a service provider. A multi-directional local search algorithm is developed to solve this problem, taking into account the fundamental tradeoff between operational efficiency and service quality. Local search is integrated into a variable neighborhood descent framework that applies an intelligent candidate list principle to reduce computation time. Moreover, a new scheduling procedure is proposed, constructing time schedules that minimize total user ride time. It proves to be faster and more efficient than existing scheduling procedures. Overall, computational experiments on existing benchmark data extended with combination restrictions reveal a general pattern in the effect of the combination restrictions. Such insights are essential for service providers in order to support policy choices, e.g. related to service quality or medical education of drivers.     

异构并行平台的Caffe推理速度提升方法

随着计算机硬件性能的提高,目前在个人终端上也开始出现使用预训练机器学习模型进行推理的运用.Caffe是一款流行的深度学习框架,擅长图像分类等任务,但是在默认状态下只能单核运行,无法充分发挥异构并行计算设备的计算能力.深度学习对于计算性能的要求较高,如果能并行化以充分使用所有计算设备,就能提升计算速度和使用体验.由于CP...     

Heuristic algorithms for preemptive scheduling in a two-stage hybrid flowshop with additional renewable resources at each stage

This paper deals with the problem of preemptive scheduling in a two-stage flowshop with parallel unrelated machines and renewable resources at both the stages. The resource requirements are of a 0–1 type. The objective is the minimization of makespan. The problem is NP-hard. Four heuristic algorithms using linear programming are proposed for solving this problem. Performance of the algorithms is analyzed experimentally by comparing heuristic solutions with the lower bound on the optimal makespan. Statistical comparative analysis of the developed algorithms is carried out. The results of a computational experiment show that the proposed algorithms are able to produce good quality solutions in a small amount of computation time.     

An effective ant colony optimization algorithm for multi-objective job-shop scheduling with equal-size lot-splitting

This paper proposes several novel hybrid ant colony optimization (ACO)-based algorithms to resolve multi-objective job-shop scheduling problem with equal-size lot splitting. The main issue discussed in this paper is lot-splitting of jobs and tradeoff between lot-splitting costs and makespan. One of the disadvantages of ACO is its uncertainty on time of convergence. In order to enrich search patterns of ACO and improve its performance, five enhancements are made in the proposed algorithms including: A new type of pheromone and greedy heuristic function; Three new functions of state transition rules; A nimble local search algorithm for the improvements of solution quality; Mutation mechanism for divisive searching; A particle swarm optimization (PSO)-based algorithm for adaptive tuning of parameters. The objectives that are used to measure the quality of the generated schedules are weighted-sum of makespan, tardiness of jobs and lot-splitting cost. The developed algorithms are analyzed extensively on real-world data obtained from a printing company and simulated data. A mathematical programming model is developed and paired-samples t-tests are performed between obtained solutions of mathematical programming model and proposed algorithms in order to verify effectiveness of proposed algorithms.     

Fixed-priority sensitivity analysis for linear compute time models

Several formal results exist that allow an analytic determination of whether a particular scheduling discipline can feasibly schedule a given set of hard real-time periodic tasks. In most cases, these results provide little more than a `yes' or `no' answer. In practice, it is also useful to know how sensitive scheduling feasibility is to changes in the characteristics of the task set. This paper presents algorithms that allow a system developer to determine, for fixed-priority preemptive scheduling of hard real-time periodic tasks on a uniprocessor, how sensitive schedule feasibility is to changes in the computation times of various software components. The algorithms allow a system developer to determine what changes in task computation times can be made while preserving schedule feasibility (or what changes are needed to achieve feasibility). Both changes to the computation time of a single task and changes to the computation times of a specified subset of the tasks are analyzable. The algorithms also allow a decomposition of tasks into modules, where a module may be a component of multiple tasks