Fully dynamic biconnectivity in graphs

We present an algorithm for maintaining the biconnected components of a graph during a sequence of edge insertions and deletions. It requires linear storage and preprocessing time. The amortized running time for insertions and for deletions isO(m ^2/3 ), wherem is the number of edges in the graph. Any query of the form ‘Are the verticesu andv biconnected?’ can be answered in timeO(1). This is the first sublinear algorithm for this problem. We can also output all articulation points separating any two vertices efficiently. If the input is a plane graph, the amortized running time for insertions and deletions drops toO(√n logn) and the query time isO(log² n), wheren is the number of vertices in the graph. The best previously known solution takes timeO(n ^2/3 ) per update or query.     

Lock-free parallel dynamic programming

We show a method for parallelizing top down dynamic programs in a straightforward way by a careful choice of a lock-free shared hash table implementation and randomization of the order in which the dynamic program computes its subproblems. This generic approach is applied to dynamic programs for knapsack, shortest paths, and RNA structure alignment, as well as to a state-of-the-art solution for minimizing the maximum number of open stacks. Experimental results are provided on three different modern multicore architectures which show that this parallelization is effective and reasonably scalable. In particular, we obtain over 10 times speedup for 32 threads on the open stacks problem.     

Performing incremental dynamic analysis in parallel

Incremental dynamic analysis has recently emerged to offer comprehensive evaluation of the seismic performance of structures using multiple nonlinear dynamic analyses under scaled ground-motion records. Being computer-intensive, it can benefit from parallel processing to accelerate its application on realistic structural models. While the task-farming master–slave paradigm seems ideal, severe load imbalances arise due to analysis non-convergence at structural instability, prompting the examination of task partitioning at the level of single records or single dynamic runs. Combined with a multi-tier master–slave processor hierarchy employing dynamic task generation and self-scheduling we achieve a flexible and efficient parallel algorithm with excellent scalability.     

Fully parallel thinning with tolerance to boundary noise

A new fully parallel thinning algorithm is developed and evaluated in this paper to solve the noise spurs problem and preserve geometric properties efficiently. The algorithm not only prevents the excessive erosions but also lessens the creation of spurious end points for an image with boundary noise. When two input images are similar in shape but with boundary noise, our skeletons produced appear more consistent in topology as compared to those using other algorithms. Although a few additional neighbors other than 3 × 3 are considered in the deletability conditions, the smoothing procedure prior to thinning is avoided. The parallel thinning algorithm runs very fast and can be implemented in real time. Several English and Chinese characters and the difficult patterns often illustrated in the literature are also experimented to show the efficiency and consistency of our algorithm.     

Fully dynamic algorithms for permutation graph coloring

We introduce a dynamic model for maintaining permutation graph coloring. Our motivation comes from the strait type river routing problem in VLSI. This paper presents fully dynamic algorithms for the permutation graph coloring problem. These algorithms are designed to handle Insert and Delete operations and answer some queries. The aim is to provide for running times that are asymptotically more efficient than recomputation (off-line algorithms that run in 0(n logw) time, are known [5,6,10,3]). First, the algorithm A^ that runs in 0(n) uniform running time per Insert/Delete operation is presented. Second, a more sophisticated data structure leads to the algorithm A2 that runs in (9(m logw) uniform running time per Insert I Delete, where m denotes the number of chains in the decomposition. It follows from [7,4] that the running time of A2 when the points from the dynamically changing set are drawn independently from a uniform distribution on the unit square is G(yfn logn) per Insert/Delete in probability. Third, we sketch a composite algorithm A3 that switches between A± and A2 guarantees an amortized running time of (min{n,m logw)) per Insert/Delete. Finally, we outline a number of applications     

Asynchronous analysis of parallel dynamic programming algorithms

We examine a very simple asynchronous model of parallel computation that assumes the time to compute a task is random, following some probability distribution. The goal of this model is to capture the effects of unpredictable delays on processors, due to communication delays or cache misses, for example. Using techniques from queueing theory and occupancy problems, we use this model to analyze two parallel dynamic programming algorithms. We show that this model is simple to analyze and correctly predicts which algorithm will perform better in practice. The algorithms we consider are a pipeline algorithm, where each processor i computes in order the entries of rows i, i+p, and so on, where p is the number of processors; and a diagonal algorithm, where entries along each diagonal extending from the left to the top of the table are computed in turn. It is likely that the techniques used here can be useful in the analysis of other algorithms that use barriers or pipelining techniques     

Kinematic and dynamic identification of parallel mechanisms

In this paper, we provide a comprehensive method to perform the physical model identification of parallel mechanisms. This includes both the kinematic identification using vision and the identification of the dynamic parameters. A careful attention is given to the issues of identifiability and excitation. Experimental results obtained on a H4 parallel robot show that kinematic identification yields an improvement in the static positioning accuracy from some 1 cm down to 1 mm, and that dynamic parameters are globally estimated with less than 10% relative error yielding a similar error on the control torque estimation.     

Generalized core maintenance of dynamic bipartite graphs

Data Mining and Knowledge Discovery - k-core is important in many graph mining applications, such as community detection and clique finding. As one generalized concept of k-core,...     

Verifying parallel programs with dynamic communication structures

We address the verification problem of networks of communicating pushdown systems modeling communicating parallel programs with procedure calls. Processes in such networks can read the control state of the other processes according to a given communication structure (specifying the observability rights between processes). The reachability problem of such models is undecidable in general. First, we define a class of networks that effectively preserves recognizability (hence, its reachability problem is decidable). Then, we consider networks where the communication structure can change dynamically during the execution according to a phase graph. The reachability problem for these dynamic networks being undecidable in general, we define a subclass for which it becomes decidable. Then, we consider reachability when the switches in the communication structures are bounded. We show that this problem is undecidable even for one switch. We define a natural class of models for which this problem is decidable. This class can be used in the definition of an efficient semi-decision procedure for the analysis of the general model of dynamic networks. Our techniques allowed to find bugs in two versions of a Windows NT Bluetooth driver.     

一种有效的并行数据库动态负载平衡连接算法

在基于Shared-nothing结构的并行数据库中,负载平衡一直是影响查询处理性能的重要因素。在数据库中频繁使用的连接操作会因为各种因素导致的负载倾斜和额外的通讯开销而降低数据库的整体性能。提出了一种基于RCMD分布方法的动态负载平衡连接算法,能够在连接操作的执行过程中动态调整各个结点的负载。理论分析和实验结果证明提出的算法能够有效地平衡负载,提高并行数据库的执行效率。     

多路并行动态测试虚拟仪器的设计

动态测试仪器是大型复杂结构动态性能测试的必需仪器,它的功能较多,实现难度较大.本文重点论述应用虚拟仪器技术来设计多路并行动态测试虚拟仪器,然后对动态测试仪器的性能进行测试,并将测试分析的结果与动态信号分析仪HP35670的结果进行比较.结果表明,该仪器具有多通道、成本低、测试精度高等优点.     

Performance of parallel computations with dynamic processor allocation

In parallel adaptive mesh refinement (AMR) computations the problem size can vary significantly during a simulation. The goal here is to explore the performance implications of dynamically varying the number of processors proportional to the problem size during simulation. An emulator has been developed to assess the effects of this approach on parallel communication, parallel runtime and resource consumption. The computation and communication models used in the emulator are described in detail. Results using the emulator with different AMR strategies are described for a test case. Results show for the test case, varying the number of processors, on average, reduces the total parallel communications overhead from 16 to 19% and improves parallel runtime time from 4 to 8%. These results also show that on average resource utilization improves more than 37%.     

Fully dynamic metric access methods based on hyperplane partitioning

Metric access methods based on hyperplane partitioning have the advantage, compared to the ball partitioning-based ones, that regions do not overlap. The price is less flexibility for controlling the tree shape, especially in the dynamic scenario, that is, upon insertions and deletions of objects. In this paper we introduce a technique called ghost hyperplanes, which enables fully dynamic data structures based on hyperplane partitioning. We apply the technique to Brin's GNAT static index, obtaining a dynamic variant called EGNAT, which in addition we adapt to secondary memory. We show experimentally that the EGNAT is competitive with the M-tree, the baseline for this scenario. We also apply the ghost hyperplane technique to Voronoi trees, obtaining a competitive dynamic structure for main memory.     

Identification of dynamic comprehension processes during largescale maintenance

We present results of observing professional maintenance engineers working with industrial code at actual maintenance tasks. Protocol analysis is used to explore how code understanding might differ for small versus large scale code. The experiment confirms that cognition processes work at all levels of abstraction simultaneously as programmers build a mental model of the code. Analysis focused on dynamic properties and processes of code understanding. Cognition processes emerged at three levels of aggregation representing lower and higher level strategies of understanding. They show differences in what triggers them and how they achieve their goals. Results are useful for defining information which maintenance engineers need for their work and for documentation and development standards     

Degeneracy conditions of the dynamic model of parallel robots

Despite their well-known advantages in terms of higher intrinsic rigidity, larger payload-to-weight ratio, and higher velocity and acceleration capacities, parallel robots have drawbacks. Among them, the most important one is surely the presence of singularities in the workspace, which divide the workspace into different aspects (each aspect corresponding to one or more assembly modes) and near which the performance is considerably reduced.In order to increase the reachable workspace of parallel robots, a promising solution consists in the definition of optimal trajectories passing through the singularities to change either the leg working modes or the robot assembly modes. Previous works on the field have shown that it is possible to define optimal trajectories that allow the passing through the robot type 2 singularities. Such trajectories must respect a physical criterion that can be obtained through the analysis of the degeneracy conditions of the parallel robot inverse dynamic model.However, the mentioned works were not complete: they lacked a degeneracy condition of the parallel robot inverse dynamic model, which is not due to type 2 singularity anymore, but to a serial singularity. Crossing a serial singularity is appealing as in that case we can change the robot leg working mode and then potentially access to other workspace zones. This absence is due to the fact that the authors used a reduced dynamic model, which was not taking into account all link dynamic parameters.The present paper aims to fill this gap by providing a complete study of the degeneracy conditions of the parallel robot dynamic model and by demonstrating that it is possible to cross the type 2, but also serial singularity, by defining trajectories that respect some given criteria obtained from the analysis of the degeneracy of the robot dynamic model. It also aims to demonstrate that the serial singularities have impacts on the robot effort transmission, which is a point that is usually bypassed in the literature. All theoretical developments are validated through simulations and experiments.     

动态资源感知的并行化模糊测试框架

针对现有的并行模糊测试在测试效率、资源利用率以及异常处理上的局限性,本文围绕测试资源的生成、使用及容错三个方面提出了一种动态资源感知的系统化解决方案。针对测试环境在大规模和多场景两个维度快速搭建的需求,提出一种基于云平台的动态构建方法,加快测试环境部署,提高有效fuzz时间;针对并行模糊测试中资源利用率低的问题,提出一种多层次并行度动态调整的资源配置策略,优化整体测试资源配置并提高单机负载;针对大规模并行测试中节点易发生故障的问题,提出基于优先级调度的容错处理方法。最后,本文设计并实现了一个基于四级流水线并行处理结构的通用模糊测试框架。实验证明,该框架能够有效提高并行模糊测试的测试效率和资源利用率,实现系统的有效容错。     

并行计算在动态模式识别中的实现和应用*

研究一种针对最近提出的动态环境下的机器学习理论——确定学习理论的算法实现,提出一种采用并行计算实现确定学习理论中的动态模式识别的方法。利用并行计算中的OpenMP多核编程环境,采用曙光16核服务器为硬件平台,实现对动态模式识别算法的快速性。同时,以压气机Mansoux模型为应用背景,把确定学习理论的动态模式识别方法应用到压气机旋转失速/喘振的快速检测中,利用多核并行计算实现了从包含多种旋转失速/喘振模式的模式库中快速识别当前模式的方法,为文章中方法提供了一个有效的验证。     

Improving matrix-based dynamic programming on massively parallel accelerators

Dynamic programming techniques are well-established and employed by various practical algorithms, including the edit-distance algorithm or the dynamic time warping algorithm. These algorithms usually operate in an iteration-based manner where new values are computed from values of the previous iteration. The data dependencies enforce synchronization which limits possibilities for internal parallel processing. In this paper, we investigate parallel approaches to processing matrix-based dynamic programming algorithms on modern multicore CPUs, Intel Xeon Phi accelerators, and general purpose GPUs. We address both the problem of computing a single distance on large inputs and the problem of computing a number of distances of smaller inputs simultaneously (e.g., when a similarity query is being resolved). Our proposed solutions yielded significant improvements in performance and achieved speedup of two orders of magnitude when compared to the serial baseline.     

A virtual bus architecture for dynamic parallel processing

To support parallel processing of data-intensive applications, the interconnection network of a parallel/distributed machine must provide high end-to-end communication bandwidth and handle the bursty and concentrated communication patterns generated by dynamic load balancing and data collection operations. A large-scale interconnection network architecture called a virtual bus is proposed. The virtual bus can scale to terabits-per-second end-to-end communication bandwidth with low queuing delay for nonuniform traffic. A terabit virtual bus architecture can be efficiently implemented for less than 5% of the total cost of an eight-thousand-node system. In addition, the virtual bus has an open system parallel interface that is flexible enough to support up to gigabytes per second data transfer rates, different grades of services, and broadcast operation. Such flexibility makes the virtual bus a plausible open system communication backbone for a broad range of applications     

A parallel algorithm for the dynamic lot-sizing problem

The dynamic lot-sizing model (DLS) is one of the most frequently used models in production and inventory system because lot decisions can greatly affect the performance of the system. The practicality of DLS algorithms is hindered by the huge amount of computer resources required for solving these models, even for a modest problem. This study developed a parallel algorithm to solve the lot-sizing problem efficiently. Given that n is the size of the problem, the complexity of the proposed parallel algorithm is O(n²p) with p processors. Numerical experiments are provided to verify the complexity of the proposed algorithm. The empirical results demonstrate that the speedup of this parallel algorithm approaches linearity, which means that the proposed algorithm can take full advantage of the distributed computing power as the size of the problem increases.