基于适应性的网格数据库中子查询的节点优化调度

网格数据库是数据库技术和网格技术相结合后新的研究领域,网格的动态变化特性对数据库查询优化技术提出了适应性的要求。本文提出了基于Petri网描述的子查询计划模型TNSN,通过扩展子查询及其节点的数据关联关系的描述,建立了子查询进行适应性优化调度的查询计划模型;进一步提出了考虑变化的参数在内的耗费估算模型,并在TNSN和耗费模型的基础上提出了适应性优化算法,保证了查询处理过程中可以根据网格参数的变化情况对查询进行适应性调整,最后给出了实验验证。     

基于Petri网的查询计划模型适应性进化的一致性保证

网格数据库是数据库技术和网格技术相结合后的新的研究领域,其适应性查询优化技术对传统的查询计划模型产生了新的要求.在分析了基于DAG(directed acylicgraph)的查询计划模型不足的基础上,提出了基于Petri网的查询计划描述模型QPPN(Query Plan Petn Net)网,丰富了查询计划模型中子查询与节点之间数据关系的描述能力,并在OPPN网的基础上,给出了适应性进化的查询计划一致性分析及定理,保证了进化的正确性.     

基于低耗费调度的网格数据库查询中间件的设计

网格数据库对其查询分解后的子查询的优化调度产生了新的要求,在分析了子查询与数据库节点的数据关联关系基础上,提出了一个基于低时间耗费评估模型的查询中间件（LCQM）,给出了低耗费的查询调度计划算法,并给出了实验验证,提高了网格数据库查询的效率。     

基于共享的MapReduce多查询优化技术

为解决MapReduce处理多个查询时效率低下的问题, 提出了一种基于查询共享的MapReduce查询优化方法——ShareOpt优化。通过分析所有查询的操作模式, 找出其中共享的子查询部分, 并根据子查询的执行顺序构造执行计划有向图（DAG）, 最终确定一组查询的整体执行计划。通过与Hive和Pig的对比, 验证了该方法能够在保证准确性的情况下有效地减少执行步数, 提高查询执行的效率。     

基于粒子群算法的多核处理器线程调度研究

为有效解决多核处理器的线程调度问题,提出了一种基于粒子群算法框架上的线程调度算法.该算法依据设计的调度模型,在线程DAG图上通过复制不在同一处理器上且存在相关性的线程,生成相互独立的子DAG图,并采用改进的粒子群优化算法对其进行合理调度,由此提高线程调度效率.仿真实现了该算法,并通过实验数据验证了该算法的优越性.     

基于信息网模型的分布并行多连接查询优化

在分布式集群系统中,数据根据划分算法存储在集群的各个节点,这为涉及大量连接操作的复杂查询带来了昂贵的网络开销。针对该问题,基于信息网模型INM(Information Network Mode),提出最小通信量查询划分算法和多目标查询优化算法。其中查询划分算法将复杂查询划分成多个PWOC(parallelizable without communication)子查询,所有子查询可近似无通信地并行执行。多目标优化算法将子查询作为查询计划的基本操作,并将并行性和通信代价同时作为驱动目标,以传统多目标加权算法结合贪心策略作为评估依据生成查询计划树。最后,系统基于TPC-H基准生成测试数据,将原始算法与优化算法进行了对比实验,结果表明优化算法可以极大提高复杂查询的效率。     

并行分布式无线生理传感器网络的任务调度模型研究

以智能服装为背景,研究基于无线生理传感器网络任务调度模型.首先对数据融合任务进行子任务划分,并通过基 于全局遗传模拟退火算法的任务调度算法对子任务进行优化调度,实现计算的并行化和分布化.由于各个传感器功能固定,导致子任务执行顺序也是固定的,因此任务调度优化算法可以事先运行.仿真结果表明,其加速比可以达到4倍以上,充分利用了网络中节点数量多的优势,有效地解决了单个节点有限的运算、存储资源与较高的整体计算性能需求之间的矛盾.     

图结构XML文档上子图查询的高效处理算法

研究了图结构XML数据上子图查询处理,给出了一系列高效的处理算法.基于可达编码,首先提出基于哈希的结构连接算法(HGJoin)来处理图结构XML数据上的可达查询.然后,该算法被扩展来处理特殊的二分图查询.基于这些算法和所给出的代价模型,提出了一般DAG子图查询的处理算法和查询优化策略.这些算法经过简单修改即可有效地处理一般的子图查询.理论分析和实验结果表明,算法具有较高的效率.     

基于图连通支配集的子图匹配优化算法

在子图匹配过程中,随着图规模不断增长,匹配时间呈现指数爆炸的趋势.对此,提出一种基于图连通支配集的子图匹配优化算法VF-SMDS.根据贪心算法构建查询图的最小连通支配子图;通过代价模型计算最小连通支配子图节点的匹配代价,构建最优k查询节点匹配序列;通过支配节点的结构特征缩小查询节点搜索空间范围,在数据图中遍历到满足要求的节点,得到最终答案集.实验将VF-SMDS与GADDI、SPath、VF2++、VF3和SubISO方法进行对比.实验结果表明,在处理较大规模子图匹配问题时,VF-SMDS查询效率更高.     

网格环境下基于QoS的协作型任务调度算法研究

在深入研究网格环境下任务调度算法的基础上,提出一种基于QoS的协作型任务调度遗传算法并通过引入协作型任务的形式化描述DAG图构造了QoS参数模型.该参数模型提出了任务完成时间、价格和可靠性三个QoS参数并将这些QoS参数引入遗传算法,实现了网格环境下协作型任务调度对服务质量的优化并保证了协作型任务之间的数据依赖.通过与DAG-MIN和DAG-GSA算法的对比实验表明,该算法能在保证较优调度性能的同时大幅度提高调度的服务质量.     

Data broadcasting for dependent information using multiple channels in wireless broadcast environments

Data broadcasting is an effective approach to disseminating information to mobile clients and has attracted much research attention in recent years. In many applications, the access pattern among the data can be represented by a weighted DAG. In this paper, we consider the problem of efficiently generating the broadcast schedules on multiple channels when the data set has a DAG access pattern. We show that it is NP-hard to find an optimal broadcast schedule which not only minimizes the latency but also satisfies the ancestor property that retains the data dependency. We further derive a condition for the input DAGs under which one can generate an optimal broadcast schedule in linear time and propose an algorithm to generate the schedule. Due to the NP-completeness, we provide three heuristics for general DAGs based on the level of a vertex in the input DAGs and each heuristic uses a different policy to place vertices into the broadcast channels. There are two categories for the policies. The first category mainly considers the probability for a process to stop at a considered vertex. The second category takes the vertices which are affected most when assigning a vertex into consideration. We analyze and discuss these heuristics. A short experimental simulation is given for supporting and validating the discussion. In particular, the experimental results indicate that roughly considering the whole posterior vertices of each vertex is not precise and may not lead to good results and considering the vertices affected most when assigning a vertex will help reducing the latency.     

Disseminating dependent data in wireless broadcast environments

In wireless mobile environments, data broadcasting is an effective approach to disseminate information to mobile clients. In some applications, the access pattern of all the data can be represented by a weighted DAG. In this paper, we explore how to efficiently generate the broadcast schedule in a wireless environment for the data set having a weighted DAG access pattern. Such a broadcast schedule not only minimizes the access latency but also is a topological ordering of the DAG. Minimized access latency ensures the quality of service (QoS). We prove that it is NP-hard to find an optimal broadcast schedule and provide some heuristics. After giving an analysis for these heuristics on the latency and complexity, we implement all the proposed heuristics to compare their performance. Recommended by: Sunil Prabhakar     

Advances in IC-Scheduling Theory: Scheduling Expansive and Reductive Dags and Scheduling Dags via Duality

Earlier work has developed the underpinnings of the IC-scheduling theory, a framework for scheduling computations having intertask dependencies - modeled via directed acyclic graphs (DAGs) - for Internet-based computing. The goal of the schedules produced is to render tasks eligible for execution at the maximum possible rate, with the dual aim of 1) utilizing remote clients' computational resources well by always having work to allocate to an available client and 2) lessening the likelihood of a computation's stalling for lack of eligible tasks. The DAGs handled by the theory thus far are those that can be decomposed into a given collection of bipartite building block DAGs via the operation of DAG decomposition. A basic tool in constructing schedules is a relation >, which allows one to "prioritize" the scheduling of a complex DAG's building blocks. The current paper extends the IC-scheduling theory in two ways: by expanding significantly the repertoire of DAGs that the theory can schedule optimally and by allowing one sometimes to shortcut the algorithmic process required to find optimal schedules. The expanded repertoire now allows the theory to schedule optimally, among other DAGs, a large range of DAGs that are either "expansive", in the sense that they grow outward from their sources, or "reductive", in the sense that they grow inward toward their sinks. The algorithmic shortcuts allow one to "read off" an optimal schedule for a DAG from a given optimal schedule for the DAG's dual, which is obtained by reversing all arcs (thereby exchanging the roles of sources and sinks).     

一种基于负载均衡性的网格任务调度算法

针对二分图匹配算法在任务之间存在时序关系时无法进行有效调度以及EFT算法没有充分考虑各处理机性能及网络通信状况的问题,提出基于二分图匹配的改进ETF算法。该算法综合考虑任务之间的时序关系、处理机的性能、处理机之间的通信情况及已处理任务的调度情况,利用二分图最佳匹配思想对局部任务进行调度。实验表明该算法具有较小的调度长度和较好的负载均衡性。     

Efficient local search far DAG scheduling

Scheduling DAGs to multiprocessors is one of the key issues in high-performance computing. Most realistic scheduling algorithms are heuristic and heuristic algorithms often have room for improvement. The quality of a scheduling algorithm can be effectively improved by a local search. In this paper, we present a fast local search algorithm based on topological ordering. This is a compaction algorithm that can effectively reduce the schedule length produced by any DAG Scheduling algorithm. Thus, it can improve the quality of existing DAG scheduling algorithms. This algorithm can quickly determine the optimal search direction. Thus, it is of low complexity and extremely fast     

可重定向C编译器中DAG及归约规则

以在嵌入式系统中建立C编译器的技术特点为主要内容,用设计实例论述了C编译器实现中前端、后端的主要工作内容。说明了在前、后端之间起桥梁作用的中间描述语言有向无环图(DAG)的设计原理及形成方法,同时还就如何将DAG与目标机系统之间形成映射关系进行描述,提出了在映射中规约规则制定的方法和原则,给出了一些有指导意义的经验性结论。     

主动接纳策略的Web集群多维QoS目标优化调度算法

针对以往的调度算法对服务器本身的研究较多，而结合网络流量特征采取相应调度策略研究较少的情况．提出了一种结合网络自相似访问特征的接纳控制策略，分析了一种综合考虑Web集群系统中多维调度因子的多目标函数．在此基础上提出了一种既适应网络访问特征，又支持QoS的Web集群调度算法．最后给出了其算法性能测试结果．     

基于网格资源预测的任务优先级调度算法

根据网格工作流中任务的依赖关系和截止时间,以及资源的有效度和MIPS（每秒百万条指令）,提出基于网格资源预测的任务优先级调度算法。把网格任务工作流抽象为有向无环图,找到该工作流的关键路径,计算每个任务的最迟开始执行时间,作为任务的优先级。在算法中考虑用户的要求和资源的类型,以及任务调度失败后重新分配的问题。实验验证了该算法的有效性。     

Run-Time Techniques for Exploiting Irregular Task Parallelism on Distributed Memory Architectures

Automatic scheduling for directed acyclic graphs (DAG) and its applications for coarse-grained irregular problems such as largen-body simulation have been studied in the literature. However, solving irregular problems with mixed granularities such as sparse matrix factorization is challenging since it requires efficient run-time support to execute a DAG schedule. In this paper, we investigate run-time optimization techniques for executing general asynchronous DAG schedules on distributed memory machines and discuss an approach for exploiting parallelism from commuting operations in the DAG model. Our solution tightly integrates the run-time scheme with a fast communication mechanism to eliminate unnecessary overhead in message buffering and copying. We present a consistency model incorporating the above optimizations, and take advantage of task dependence properties to ensure the correctness of execution. We demonstrate the applications of this scheme in sparse matrix factorizations and triangular equation solving for which actual speedups are difficult to obtain. We provide a detailed experimental study on Meiko CS-2 to show that the automatically scheduled code has achieved good performance for these difficult problems, and the run-time overhead is small compared to total execution times.     

Scheduling large-scale scientific workflow on virtual machines with different numbers of vCPUs

With the wide deployment of cloud computing in scientific computing, cost minimization is increasingly critical for large-scale scientific workflow. Unfortunately, due to the highly intricate directed acyclic graph (DAG)-based workflow and the flexible usage of virtual machines (VMs) in cloud platform, the existing workflow scheduling approaches are inefficient to strike a balance between the parallelism and the topology of the DAG-based workflow while using the VMs, which causes a low utilization of VMs and consumes more cost. To address these issues, this paper presents a novel task scheduling framework named cost minimization approach with the DAG splitting method (COMSE) for minimizing the cost of running a deadline-constrained large-scale scientific workflow. First, we provide comprehensive theoretical analyses on how to improve the utilization of a resource-balanced multi-vCPU VM for running multiple tasks simultaneously. Second, considering the balance between the parallelism and the topology of a workflow, we simplify the DAG-based workflow, and based on the simplified DAG, a DAG splitting method is devised to preprocess the workflow. Third, since the cloud is charged by hours, we also design an exact algorithm to find the optimal operation pattern for a given schedule to make the consumed instance hours minimum, and this algorithm is named as instance hours minimization by Dijkstra (TOID). Finally, by employing the DAG splitting method and the TOID, the COMSE schedules a deadline-constrained large-scale scientific workflow on the multi-vCPU VMs and incorporates two important objects: minimizing the computation cost and the communication cost. Our solution approach is evaluated through rigorous performance evaluation study using real-word workflows, and the results show that the proposed COMSE approach outperforms existing algorithms in terms of computation cost and communication cost.