A Queuing-Theoretic Approach to Task Scheduling and Processor Selection for Video-Decoding Applications

We propose a cross-layer design for resource-constrained systems that simultaneously decode multiple video streams on multiple parallel processors, cores, or processing elements. Our proposed design explicitly considers the coder specific application characteristics such as the decoding dependencies, decoding deadlines, and distortion impacts of different video packets (e.g., frames, slices, groups of slices etc.). The key to the cross-layer design is the resource management control plane (RMCP) that coordinates the scheduling and processor selection across the active applications. The RMCP deploys a priority-queuing model that can evaluate the system congestion and predict the total expected video quality for the set of active decoding tasks. Using this model, we develop a robust distortion-and delay-aware scheduling algorithm for video packets. This algorithm aims to maximize the sum of achieved video qualities over all of the decoded video sequences. Additionally, we propose a processor selection scheme intended to minimize the delays experienced by the queued video packets. In this way, the number of missed decoding deadlines is reduced and the overall decoded video quality is increased. We compare queuing-theoretic based scheduling strategies to media agnostic scheduling strategies (i.e., earliest-deadline-first scheduling) that do not jointly consider the decoding deadlines and distortion impacts. Our results illustrate that by directly considering the video application's properties in the design of a video decoding system, significant system performance gains on the order of 4 dB peak-signal-to-noise ratio can be achieved.     

An Integrated Approach to Scheduling in Safety-Critical Embedded Control Systems

This paper describes an approach that has been developed over a number of years for the job of scheduling systems and providing evidence that timing requirements are met. The approach has been targeted at the safety-critical systems domain, and more specifically the development of control systems for jet engines. The work provides a usable computational model that supports the reuse of legacy systems. In addition, timing analysis has been developed that features low pessimism, low computational complexity and that is robust to change. The contributions of this paper are to show how standard timing analysis is often insufficient for real systems, presenting extensions to the standard analysis to give an integrated approach to verification, and providing a case study that demonstrates the appropriateness and benefits of the overall technique.     

An Integrated Approach to Designing and Evaluating Collaborative Applications and Infrastructures

Collaborative systems include both general infrastructures and specific applications for supporting collaboration. Because of the relative newness and complexity of these systems, it has been unclear what approach should be used to design and evaluate them. Based on the lessons learned from our work and that of others on collaborative systems, we have derived an integrated approach to researching collaborative applications and infrastructures. The approach can be described as a sequence of steps: We decompose the functionality of collaboration systems into smaller functions that can be researched more-or-less independently. For each of these functions, we adopt general (system-independent) principles regarding the design and implementation of the function, identify collaboration scenarios at multiple levels of abstraction, identify requirements based on the scenarios, adopt an interaction model to meet the requirements, realize the interaction model as a concrete user interface, develop a logical architecture of the system, identify a physical architecture for placing the logical components in a distributed system, develop infrastructure abstractions, use the abstractions to implement applications, and perform lab studies, field experiments, and simulations to evaluate the infrastructure and applications. As in other models with multiple phases, feedback from subsequent phases is used to modify the results from the previous phases. In this paper, we describe, illustrate and motivate this research plan.     

An Integrated Approach to the Design of Processor Arrays with Systolic Organization of Computations

An integrated approach is proposed to the design of economically efficient and high-performance processor arrays with systolic organization of computations. The approach includes the construction of VLSI-oriented versions of locally recursive algorithms and synthesis of new architectures of processor arrays for transforming algorithms that maximally take into account fundamental restrictions of VLSI technology. Within the framework of this approach, strategies are developed for obtaining the above-mentioned algorithms and architectures.     

An Efficient Processor Allocation Algorithm Using Two-Dimensional Packing

Mesh is one of the most widely used interconnection networks for multiprocessor systems. In this paper, we propose an approach to partition a given mesh intomsubmeshes which can be allocated tomtasks with grid structures. We adapt two-dimensional packing to solve the submesh allocation problem. Due to the intractability of the two-dimensional packing problem, finding an optimal solution is computationally infeasible. We develop an efficient heuristic packing algorithm called TP-heuristic. Allocating a submesh to each task is achieved using the results of packing. We propose two different methods called uniform scaling and nonuniform scaling. Experiments were carried out to test the accuracy of solutions provided by our allocation algorithm.     

DoubleP:一个有效的节点关键性能因素发现与聚类方法

随着处理器设计复杂性的提高,影响处理器节点性能的因素也越来越多.受资源(时间和空间)的限制,很难采集并分析所有影响性能因素的应用特征参数和机器性能轮廓参数.如何在众多的性能参数中提取影响性能的关键因素,成为并行系统节点性能评价中首先要解决的问题.提出了一个有效的DoubleP性能因素发现与聚类方法,该方法将众多复杂的性能因素聚焦到几个性能主成份上,明确了分析对象.通过DoubleP方法的分析,发现了14个影响处理器节点性能的关键因素和4个性能主成份.     

多机服务器任务调度的经济学方法q

本文针对多机服务器提出了一种任务调度的经济学方法以一般均衡理论为基础,依靠价格机制实现资源的优化分配;讨论了多机服务器的系统模型、任务的聚类和效用函数、经济学模型及均衡状态的最优性;最后通过模拟实验验证了经济学方法的有效性。     

关于建模与自适应控制的一体化途径

在文献自适应辨识预报和控制-多层递阶途经中,我们提出了非线性系统动态线性化的概念.这种动态线性化仅仅是形式上的,而不是真的线性化.但研究发现,在这种线性化过程中,包含了一种新的系统辨识思想,那就是在线实时建模一实时反馈控制校正的思想.这种辨识把建模与反馈控制结合成为一体,突破了参数自适应的框架.实现了控制系统的结构自适应性,并且避免了建立数学模型这一繁锁的步骤.本文就是对这种系统建模与控制一体化的途径进行介绍.     

An Integrated Method for Planning and Scheduling to Minimize Tardiness

We combine mixed integer linear programming (MILP) and constraint programming (CP) to minimize tardiness in planning and scheduling. Tasks are allocated to facilities using MILP and scheduled using CP, and the two are linked via logic-based Benders decomposition. We consider two objectives: minimizing the number of late tasks, and minimizing total tardiness. Our main theoretical contribution is a relaxation of the cumulative scheduling subproblem, which is critical to performance. We obtain substantial computational speedups relative to the state of the art in both MILP and CP. We also obtain much better solutions for problems that cannot be solved to optimality.     

共享存储多处理机系统在并行程序设计模式下的处理机分配法

该文在假定的系统结构和编程模型之上,分析了几种已有的基于共享存储的多处理机系统的处理机分配方法及其缺陷,提出了一种改进的方法,并对其实现进行了探讨。     

单向航道下连续泊位分配与船舶调度集成优化

为改善单向航道连续泊位港口的运营效率,研究泊位分配与船舶进出港调度集成优化.考虑潮汐、进出港时段交替与偏好泊位的影响,建立0-1整数线性规划模型,以船舶偏离偏好泊位成本和滞期成本为优化目标,确定各艘船舶的靠泊位置与进出港时刻.针对问题情境和其特有的约束条件,将原数学模型通过Dantzig-Wolfe分解方法分成主问题模...     

多机服务器任务调度的经济学方法

本文针对多机服务器提出了一种任务调度的经济学方法 :以一般均衡理论为基础 ,依靠价格机制实现资源的优化分配 ;讨论了多机服务器的系统模型、任务的聚类和效用函数、经济学模型及均衡状态的最优性 ;最后通过模拟实验验证了经济学方法的有效性     

An Evolutionary Squeaky Wheel Optimization Approach to Personnel Scheduling

The quest for robust heuristics that are able to solve more than one problem is ongoing. In this paper, we present, discuss and analyze a technique called Evolutionary Squeaky Wheel Optimization and apply it to two different personnel scheduling problems. Evolutionary Squeaky Wheel Optimization improves the original squeaky wheel optimization's effectiveness and execution speed by incorporating two additional steps (selection and mutation) for added evolution. In the evolutionary squeaky wheel optimization, a cycle of analysis-selection-mutation-prioritization-construction continues until stopping conditions are reached. The aim of the analysis step is to identify below average solution components by calculating a fitness value for all components. The selection step then chooses amongst these underperformers and discards some probabilistically based on fitness. The mutation step further discards a few components at random. Solutions can become incomplete and thus repairs may be required. The repair is carried out by using the prioritization step to first produce priorities that determine an order by which the following construction step then schedules the remaining components. Therefore, improvements in the evolutionary squeaky wheel optimization is achieved by selective solution disruption mixed with iterative improvement and constructive repair. Strong experimental results are reported on two different domains of personnel scheduling: bus and rail driver scheduling and hospital nurse scheduling.     

An Approach to Data Reduction and Integrated Machine Classification

The goal of the paper is to propose a novel approach to integrated machine classification and to investigate the effect of integration of the data reduction with data mining stage. The integration of both important steps of knowledge discovery in databases is recognized as a vital step towards improving effectiveness of the data mining effort. After having the introduced data reduction and integration schemes a solution to the integrated classification problem is proposed. The proposed algorithm allows for integrating data reduction through simultaneous instance and feature selection, with learning process using population-based and A-Team techniques. To validate the proposed approach and to investigate the effect of data reduction combined with different integration schemes, the computation experiment has been carried out. Experiment based on several benchmark datasets has shown that integrated data reduction and classifier learning outperform traditional approaches.     

An Integrated Approach to High Integrity Software Verification

Using automated reasoning techniques, we tackle the niche activity of proving that a program is free from run-time exceptions. Such a property is particularly valuable in high integrity software, for example, safety- or security-critical applications. The context for our work is the SPARK Approach for the development of high integrity software. The SPARK Approach provides a significant degree of automation in proving exception freedom. Where this automation fails, however, the programmer is burdened with the task of interactively constructing a proof and possibly also having to supply auxiliary program annotations. We minimize this burden by increasing the automation, through an integration of proof planning and a program analysis oracle. We advocate a ‘cooperative’ integration, where proof-failure analysis directly constrains the search for auxiliary program annotations. The approach has been successfully tested on industrial data.     

一种集成传感器故障诊断方法

针对传感器故障，提出了一种基于小波奇异性捡测和修正的Bayes算法(MB)的集成故障诊断方法，用RBF神经网络建立传感器故障模型，对系统的状态进行在线估计，进而得到残差，然后对残差进行小波分析，再用修正的Bayes算法进行传感器故障的在线检测、分离和估计对连续搅拌釜式反应器(CSTR)的仿真结果表明，该集成故障诊断方法能够对传感器故障进行快速准确的分离和估计，克服了传统小波分析方法大尺度下存在时延的缺点，并对传感器故障具有容错性。     

An Integrated Quay Crane Assignment and Scheduling Problem

As maritime container transport is developing rapidly, the need arises for efficient operations at container terminals. One of the most important determinants of container handling efficiency is the productivity of quay cranes, which are responsible for unloading and loading operations for container vessels. For this reason, the Quay Crane Assignment Problem (QCAP) and the Quay Crane Scheduling Problem (QCSP) have received increasing attention in the literature and the present paper deals with the integration of these interrelated problems. A formulation is developed for the Quay Crane Assignment and Scheduling Problem (QCASP), which accounts for crane positioning conditions and a Genetic Algorithm (GA) is developed to solve the QCASP. Both the model formulation and the solution methodology are presented in detail and computational analysis is conducted in order to evaluate the performance of the proposed GA. The results obtained from the GA are compared with the results from an exact technique, thus providing complete information about the performance of the heuristic in terms of solution quality.     

一种基于Web软件集成测试的建模方法

本文给出了一种Web软件集成测试的建模方法。该方法通过分析Web应用程序体系结构,对Web应用划分,用分层的有限状态机对Web应用进行行为建模,通过采用基于有限状态机的导航模型来指导测试人员进行Web集成测试;采用UML扩展的模型对Web应用组件间的交互建模,通过建立基于UML的组件依赖模型并提供相应的测试用例生成规则来提取Web应用的测试用例。     

多进程动态调度方法

文章对相关进程的典型关系进行了描述,并讨论了进程中有序和同步问题的实现方法。     

一种队列管理和队列调度结合的算法

队列的管理和调度是网络处理中非常重要的一个环节.针对传统的队列算法分离队列管理和队列调度的缺点,提出了一种两种机制结合的算法.该算法以排队延时和系统吞吐量综合性能折中最优为目标,使用最优化决策的方法,根据数据源端的发送速率和网络节点中的缓冲队列长度调整带宽资源的分配.在仿真平台NS2下对算法进行了大量的仿真实验,最终的实验结果表明:按照网络性能公式(Power公式)的标准,该算法比传统的算法在性能上提高了近20%.因此该队列算法更能够提升网络处理的性能.