面向数据流离线分析的无共享并行查询中间件研究

通过分析网络监控离线分析处理的负载特征,给出了一种面向数据流离线分析处理的并行多策略查询中间件,并利用多策略及DBMS实现了局部结果的汇总,对需后处理查询的系统扩展性、不需后处理查询的系统扩展性分别进行了评价分析。评价分析结果表明:提出的基于面向数据流离线分析处理的并行多策略查询中间件,不但做到了中间件的轻量级,实现了查询内部的并行化;同时,能利用多策略及DBMS实现子节点间并行查询,能提高查询的响应时间,从而在多节点时保持较好的扩展比,避免了系统过载,提高了资源利用率。     

多核环境下AREM模式混合并行计算研究

使用多核处理器已成为构建高性能计算机系统的主流方式。结合多核高性能计算机系统集共享内存结构和分布式内存结构于一体的体系结构特点,对AREM模式开展MPI/OpenMP混合并行计算研究与实现。性能测试结果表明,使用MPI/OpenMP混合并行计算可以将并行应用扩展至更大处理机规模,缩短计算时间,不对原程序结构做大的改动、以增量方式和较小的并行化代价,取得比较好的并行计算效果。     

Frequency-based load shedding over a data stream of tuples

Usually the data generation rate of a data stream is unpredictable, and some data elements of the data stream cannot be processed in real time if the generation rate exceeds the capacity of a data stream processing algorithm. In order to overcome this situation gracefully, a load shedding technique is recommended. This paper proposes a frequency-based load shedding technique over a data stream of tuples. In many data stream processing applications, such as mining frequent patterns, data elements having high frequency can be considered more significant than others having low frequency. Based on this observation, in the proposed technique, only frequent elements of a data stream are processed in real time while the others are trimmed. The decision to shed a load from the data stream or not is controlled automatically by the data generation rate of a data stream. Consequently, an unnecessary load shedding operation is not allowed in the proposed technique.     

Asynchronous migration for parallel genetic programming on a computer cluster with multi-core processors

An island model is a typical implementation of genetic programming on parallel computers with distributed memory. The island model has a migration facility that sends/receives some individuals in an island to/from another island to maintain diversity. The island model requires synchronization to migrate same-generation individuals between islands, and this synchronization causes an increase in computation time. This article proposes a new parallel genetic programming implementation based on the island model with asynchronous migration. Most recent computers are equipped with one or more multi-core processors, and are suitable for multi-threading. Therefore we employ a communication thread for migration between islands. The communication thread on a processor communicates with the communication thread on another processor to migrate individuals at appropriate intervals. Since the migration and other genetic operations can be independently processed on each core, and since we allow the exchange of individuals of different generations, no synchronization is needed in our implementation. In addition, a fitness calculation is also executed in parallel by the remaining cores. Experimental results show that the proposed method can reduce the computation time to about 17% in serial GP by using 40 threads.     

A parallel programming assessment for stream processing applications on multi-core systems

Multi-core systems are any computing device nowadays and stream processing applications are becoming recurrent workloads, demanding parallelism to achieve the desired quality of service. As soon as data, tasks, or requests arrive, they must be computed, analyzed, or processed. Since building such applications is not a trivial task, the software industry must adopt parallel APIs (Application Programming Interfaces) that simplify the exploitation of parallelism in hardware for accelerating time-to-market. In the last years, research efforts in academia and industry provided a set of parallel APIs, increasing productivity to software developers. However, a few studies are seeking to prove the usability of these interfaces. In this work, we aim to present a parallel programming assessment regarding the usability of parallel API for expressing parallelism on the stream processing application domain and multi-core systems. To this end, we conducted an empirical study with beginners in parallel application development. The study covered three parallel APIs, reporting several quantitative and qualitative indicators involving developers. Our contribution also comprises a parallel programming assessment methodology, which can be replicated in future assessments. This study revealed important insights such as recurrent compile-time and programming logic errors performed by beginners in parallel programming, as well as the programming effort, challenges, and learning curve. Moreover, we collected the participants’ opinions about their experience in this study to understand deeply the results achieved.     

一种分布式数据流查询重用算法研究*

提出了一种基于查询树匹配的查询重用算法.首先,系统中原有查询树与新生成的查询树进行匹配并计算对新查询树的重用收益;然后根据重用收益来实现重叠的查询操作的重用.实验结果表明,该算法能够有效地减少连续查询的执行代价总量.     

XML数据流基于组着色的XPath查询模型

提出了一种新的XML数据流XPath查询模型GBRender,该模型通过组着色序列来直接处理元素,具有较高的处理效率与较强的适应性.     

Dynamic routing of real-time jobs among parallel EDF queues: A performance study

This paper introduces an analytical method for approximating the performance of a firm real-time system consisting of a number of parallel infinite-capacity single-server queues. The service discipline for the individual queues is earliest-deadline-first (EDF). Real-time jobs with exponentially distributed relative deadlines arrive according to a Poisson process. Jobs either all have deadlines until the beginning of service or deadlines until the end of service. Upon arrival, a job joins a queue according to a state-dependent stationary policy, where the state of the system is the number of jobs in each queue. Migration among the queues is not allowed. An important performance measure to consider is the overall loss probability of the system. The system is approximated by a Markovian model in the long run. The resulting model can then be solved analytically using standard Markovian solution techniques. Comparing numerical and simulation results for at least three different stationary policies, we find that the existing errors are relatively small.     

Packet routing on grids of processors

The problem of routing packets onn ₁×...×n _r mesh-connected arrays or grids of processors is studied. The focus of this paper is on permutation routing where each processor contains exactly one packet initially and finally. A slight modification of permutation routing called balanced routing is also discussed. For two-dimensional grids a determinisitc routing algorithm is given forn×n meshes where each processor has a buffer of size f(n) < n. It needs 2n + O(n/f(n)) steps on grids without wrap-arounds. Hence, it is asymptoticaliy nearly optimal, and as good as randomized algorithms routing data only with high probability. Furthermore, it is demonstrated that onr-dimensional cubes of processors permutation routing can be performed asymptotically by (2r–2)n steps, which is faster than the running times of so-far known randomized algorithms and of deterministic algorithms.Partially supported by Siemens AG, München.     

Attribute-based evaluation of multiple continuous queries for filtering incoming tuples of a data stream

The filtering of incoming tuples of a data stream should be completed quickly and continuously, which requires strict time and space constraints. In order to guarantee these constraints, the selection predicates of continuous queries are grouped or indexed in most data stream management systems (DSMS). This paper proposes a new scheme called attribute selection construct (ASC). Given a set of continuous queries, an ASC divides the domain of an attribute of a data stream into a set of disjoint regions based on the selection predicates that are imposed on the attribute. Each region maintains the pre-computed matching results of the selection predicates. Consequently, an ASC can collectively evaluate all of its selection predicates at the same time. Furthermore, it can also monitor the overall evaluation statistics, such as its selectivity and tuple dropping ratio, dynamically. For those attributes that are employed to express the selection predicates of the queries, the processing order of their ASC’s can significantly influence the overall performance of a multiple query evaluation. The evaluation sequence can be optimized by periodically capturing the run-time tuple dropping ratio of its current evaluation sequence. The performance of the proposed method is analyzed by a series of experiments to identify its various characteristics.     

基于结构化P2P的分布式数据流系统的查询处理模型

分析了基于结构化覆盖网的分布式查询处理模型,支持大量数据流的分布式存储,连续查询间、查询内的并行处理操作,能够在很大程度上消除资源约束问题（主要是内存）,提高了查询性能、服务质量,并且该查询模型具有很好的扩展性。     

基于下推自动机的XML数据流递归查询研究

针对具有子孙轴(//)和谓词([])结构特征的XPath对具有不同递归深度的XML数据流进行递归查询处理问题,提出了基于下推自动机技术的处理方法,通过将XPath各类置步转化成相对应的处理模块,由算法将各类处理模块组合起来,建立了自上而下的树状查询模型.由于查询过程中将会发生多重匹配,从而会产生大量的匹配模式,该模型通过有效的匹配策略和缓存操作,对匹配模式进行保存及检验,成功地实现XML数据流递归查询.实验结果表明,该算法在性能上要优于传统方法.     

基于多核并行的海量数据序列模式挖掘*

为了在多核处理器上充分利用多核资源以提升挖掘性能,提出了一种动态与静态任务分配机制相结合的基于多核的并行序列模式挖掘算法。该算法采用数据并行与任务并行相结合的策略,在各处理器核生成局部序列模式后,再与其他处理器核协同,以最终获得所有的全局序列模式。算法通过并行局部归约技术消除了局部序列的重复生成与计算,并可结合静态与动态任务分配机制解决处理器的负载不均衡问题。理论分析和实验都证实了该算法可有效利用多核计算平台及多核体系结构优势,具有较高的运行效率和加速比。     

基于查询的无线传感器网络多源单汇路由算法

针对定向扩散巨大的能量开销以及在路径加强时存在的链路冗余等问题,提出了一种基于查询的无线传感器网络多源单汇路由算法。该算法通过网络分簇来减少平面泛洪所带来的能量消耗,根据邻居节点的优先级来选择下一跳节点,建立多条源节点到Sink节点的路径,并在路径交叉处进行数据融合。仿真结果表明,该算法在节点能耗均衡性、能量有效性、数据包的传输量等方面具有明显的优势,有效地延长了网络生命周期。     

Energy efficient scheduling of real-time tasks on multi-core processors with voltage islands

This paper studies energy efficient scheduling of periodic real-time tasks on multi-core processors with voltage islands, in which cores are partitioned into multiple blocks (termed voltage islands) and each block has its own power source to supply voltage. Cores in the same block always operate at the same voltage level, but can be adjusted by using Dynamic Voltage and Frequency Scaling (DVFS). We propose a Voltage Island Largest Capacity First (VILCF) algorithm for energy efficient scheduling of periodic real-time tasks on multi-core processors. It achieves better energy efficiency by fully utilizing the remaining capacity of an island before turning on more islands or increasing the voltage level of the current active islands. We provide detailed theoretical analysis of the approximation ratio of the proposed VILCF algorithm in terms of energy efficiency. In addition, our experimental results show that VILCF significantly outperforms the existing algorithms when there are multiple cores in a voltage island.     

多核处理器并行编程模型的研究与设计

为了在多核处理器上充分利用多核资源以提升程序性能,研究了多核处理器的体系结构和多核环境下可能影响并行程序性能的因素,实现了基于任务的并行编程模型.该模型提供了单任务数据并行和多任务并行两种并行处理方式,其中单任务数据并行使用cache块技术划分数据集,多任务并行使用任务密取的任务调度策略.用该模型实现了计算斐波那契数列的递归算法,实验结果表明,使用该模型编写多核并行程序可以达到较高的相对于串行计算的加速比.     

Dynamic hierarchical triangulation of a clustered data stream

This paper presents a novel approach to handle large amounts of geometric data. A data stream clustering is used to reduce the amount of data and build a hierarchy of clusters. The data stream concept allows for the processing of very large data sets. The cluster hierarchy is then used in a dynamic triangulation to create a multiresolution model. It allows for the interactive selection of a different level of detail in various parts of the data.A method for removal multiple points from Delaunay triangulation is proposed. It is significantly faster than the traditional approach. The clustering and the triangulation are supplemented by an elliptical metric to handle data with anisotropic properties.Compared to the closest competitive method by Isenburg et al., the presented algorithm requires only a single pass over the data and offers a high flexibility. These advantages culminate in a long running time. The method was tested on several large digital elevation maps. The clustering phase can take up to a few hours. Once the cluster hierarchy is built, the terrains can be efficiently manipulated in real time.     

基于负载感知的数据流动态负载均衡策略

针对大数据流式计算平台中存在节点间负载不均衡、节点性能评估不全面的问题,提出基于负载感知算法的动态负载均衡策略,并将算法应用于Flink数据流计算平台中。首先通过有向无环图的深度优先搜索算法获取节点的计算延迟时间作为评估节点性能的依据,并制定负载均衡策略;然后基于数据分块管理策略实现流式数据的节点间负载迁移技术,通过反馈实现全局和局部的负载调优;最后通过实验评估时空代价论证算法的可行性,并讨论重要参数对算法执行效果的影响。经实验验证算法通过优化流式计算任务的负载分配提高了任务的执行效率,与采用Flink平台现有的负载均衡策略相比,任务执行时间平均缩短6.51%。