Parallel Algorithms for Dynamic Shortest Path Problems

The development of intelligent transportation systems (ITS) and the resulting need for the solution of a variety of dynamic traffic network models and management problems require faster‐than‐real‐time computation of shortest path problems in dynamic networks. Recently, a sequential algorithm was developed to compute shortest paths in discrete time dynamic networks from all nodes and all departure times to one destination node. The algorithm is known as algorithm DOT and has an optimal worst‐case running‐time complexity. This implies that no algorithm with a better worst‐case computational complexity can be discovered. Consequently, in order to derive algorithms to solve all‐to‐one shortest path problems in dynamic networks, one would need to explore avenues other than the design of sequential solution algorithms only. The use of commercially‐available high‐performance computing platforms to develop parallel implementations of sequential algorithms is an example of such avenue. This paper reports on the design, implementation, and computational testing of parallel dynamic shortest path algorithms. We develop two shared‐memory and two message‐passing dynamic shortest path algorithm implementations, which are derived from algorithm DOT using the following parallelization strategies: decomposition by destination and decomposition by transportation network topology. The algorithms are coded using two types of parallel computing environments: a message‐passing environment based on the parallel virtual machine (PVM) library and a multi‐threading environment based on the SUN Microsystems Multi‐Threads (MT) library. We also develop a time‐based parallel version of algorithm DOT for the case of minimum time paths in FIFO networks, and a theoretical parallelization of algorithm DOT on an ‘ideal’ theoretical parallel machine. Performances of the implementations are analyzed and evaluated using large transportation networks, and two types of parallel computing platforms: a distributed network of Unix workstations and a SUN shared‐memory machine containing eight processors. Satisfactory speed‐ups in the running time of sequential algorithms are achieved, in particular for shared‐memory machines. Numerical results indicate that shared‐memory computers constitute the most appropriate type of parallel computing platforms for the computation of dynamic shortest paths for real‐time ITS applications.     

Performance Comparison of Parallel Programming Environments for Implementing AIAC Algorithms

AIAC algorithms (Asynchronous Iterations Asynchronous Communications) are a particular class of parallel iterative algorithms. Their asynchronous nature makes them more efficient than their synchronous counterparts in numerous cases as has already been shown in previous works. The first goal of this article is to compare several parallel programming environments in order to see if there is one of them which is best suited to efficiently implement AIAC algorithms. The main criterion for this comparison consists in the performances achieved in a global context of grid computing for two classical scientific problems. Nevertheless, we also take into account two secondary criteria which are the ease of programming and the ease of deployment. The second goal of this study is to extract from this comparison the important features that a parallel programming environment must have in order to be suited for the implementation of AIAC algorithms.     

Parallel Algorithms for Series Parallel Graphs and Graphs with Treewidth Two 1

In this paper a parallel algorithm is given that, given a graph G=(V,E) , decides whether G is a series parallel graph, and, if so, builds a decomposition tree for G of series and parallel composition rules. The algorithm uses O(log \kern -1pt |E|log ^\ast \kern -1pt |E|) time and O(|E|) operations on an EREW PRAM, and O(log \kern -1pt |E|) time and O(|E|) operations on a CRCW PRAM. The results hold for undirected as well as for directed graphs. Algorithms with the same resource bounds are described for the recognition of graphs of treewidth two, and for constructing tree decompositions of treewidth two. Hence efficient parallel algorithms can be found for a large number of graph problems on series parallel graphs and graphs with treewidth two. These include many well-known problems like all problems that can be stated in monadic second-order logic. Received July 15, 1997; revised January 29, 1999, and June 23, 1999.     

Parallel Control for Optimal Tracking via Adaptive Dynamic Programming

This paper studies the problem of optimal parallel tracking control for continuous-time general nonlinear systems. Unlike existing optimal state feedback control, the control input of the optimal parallel control is introduced into the feedback system. However, due to the introduction of control input into the feedback system, the optimal state feedback control methods can not be applied directly. To address this problem, an augmented system and an augmented performance index function are proposed firstly. Thus, the general nonlinear system is transformed into an affine nonlinear system. The difference between the optimal parallel control and the optimal state feedback control is analyzed theoretically. It is proven that the optimal parallel control with the augmented performance index function can be seen as the suboptimal state feedback control with the traditional performance index function. Moreover, an adaptive dynamic programming (ADP) technique is utilized to implement the optimal parallel tracking control using a critic neural network (NN) to approximate the value function online. The stability analysis of the closed-loop system is performed using the Lyapunov theory, and the tracking error and NN weights errors are uniformly ultimately bounded (UUB). Also, the optimal parallel controller guarantees the continuity of the control input under the circumstance that there are finite jump discontinuities in the reference signals. Finally, the effectiveness of the developed optimal parallel control method is verified in two cases.      

Means for Organization of Parallel Computations and Programming for Multiprocessors with Dynamic Architecture

In the paper, techniques are explored that allow representing programs in the dynamic architecture multiprocessor environment as autotransforming networks of objects from various classes (data, operators, references, etc.). An object-oriented programming method is suggested for creating autotransforming network programs reflecting the structure of the problem being studied rather than the characteristics of the computing environment. Means for implementation of this approach are considered both at the hardware level and at the level of the operating system. A method for graphic design of parallel programs in network representation is discussed.     

A Parallel Deadlock Detection Algorithm with O(1) Overall Run-time Complexity

This article proposes a novel parallel, hardware-oriented deadlock detection algorithm for multiprocessor system-on-chips. The proposed algorithm takes full advantage of hardware parallelism in computation and maintains information needed by deadlock detection through classifying all resource allocation events and performing class specific operations, which together make the overall run-time complexity of the new method O(1). We implement the proposed algorithm in Verilog HDL and demonstrate in the simulation that each algorithm invocation takes at most four clock cycles in hardware.     

A Technique to Speed Up Parallel Fully Dynamic Algorithms for MST

We provide a new EREW PRAM algorithm to maintain the minimum spanning tree (MST) of an undirected weighted graph. Our approach combines the sparsification data structure with a novel parallel technique which efficiently treats single edge deletions. The proposed parallel algorithm requires O(log n) time and O(n^2/3 log(m/n)) work, where n and m are respectively the number of nodes and edges of the given graph.     

基于Visual C 的0-1背包问题的动态规划算法

0-1背包问题是经典的NP问题.本文对0-1背包问题的动态规划算法进行了分析,用Visual C 实现该算法.     

Serial and Parallel Algorithms for (k,2)-Partite Graphs

We introduce a class of layered graphs which we call (k,2)-partite and which we argue are an interesting class because of several important applications. We show that testing for (k,2)-partiteness can be done efficiently both on sequential and parallel machines, by showing that membership is in NSPACE(log n) and in NC². We show that (k,2)-partite graphs have bounded path width. We then show that a particular NP-complete problem, namely Maximum Independent Set, is solvable in linear time on bounded pathwidth graphs if the path decomposition is included in the input. Finally, we show that the Maximum Independent Set problem is in NC² for (k,2)-partite graphs. We note that linear time solutions for certain NP-complete problems have been shown for a wider class of graphs, namely partial k-trees. Our linear time algorithm is somewhat simpler in structure. We conjecture that our techniques can be used on many NP-complete problems to yield efficient algorithms for (k,2)-partite graphs.     

O(m~2)时间求解SAT问题的随机算法

传统的求解 SAT问题的随机算法主要是对满足解进行搜索 ,在找不到满足解的情况下 ,则无法正确判断问题的可满足性 .该文提出了两个时间复杂度为 O( m2 )求解 SAT问题的随机算法 Sat Test1和 Sat Test2 ,这里 m为CNF公式中的子句数 .这两个随机算法是通过对不满足解数的估计来判断 SAT问题的可满足性 ,不同于传统的随机算法 .其中第二个算法 Sat Test2在搜索满足解的同时又可以对不满足解数进行估计 ,是对传统随机算法的重要改进 .试验结果表明 ,文中提出的算法对相变区域的难 SAT实例有较好的求解能力 .     

面向非结构网格应用并行程序的编程工具

面向高性能数值模拟,分析了基于并行应用编程框架快速研发并行数值模拟软件存在的挑战。在此基础上,以JAUMIN(J adaptive unstructured mesh application infrastructure)框架的应用为例,设计并实现了一种面向非结构网格数值模拟应用并行程序的图形化编程工具。该编程工具采用基于结构化流程图的图形化编程方式,屏蔽JAUMIN框架的编程接口,帮助用户在不学习编程框架的基础上快速开发基于编程框架的并行应用程序。实际应用表明,该工具可以显著提升并行应用软件的研发效率,降低用户编写并行数值模拟程序的难度。由于编程工具生成的代码规范统一,系统的维护效率也得以大幅度提高。     

Algorithms for (0, 1, d)-graphs with d constrains

Let G be a graph with vertex set V(G). Let n, k, d be non-negative integers such that n+2k+d≤|V(G)|?2 and |V(G)|?n?d are even. A matching which saturates exactly |V(G)|?d vertices is called a defect-d matching of G. If when deleting any n vertices the remaining subgraph contains a matching of k edges and every k-matching can be extended to a defect-d matching, then G is said to be an (n, k, d)-graph. We present an algorithm to determine (0, 1, d)-graphs with d constraints. Moreover, we solve the problem of augmenting a bipartite graph G=(B, W) to be a (0, 1, d)-graph by adding fewest edges, where d=∥B|?|W∥. The latter problem is applicable to the job assignment problem, where the number of jobs does not equal the number of persons.     

A Paradigm for the Design of Parallel Algorithms with Applications

This paper proposes a model or paradigm for the development of parallel algorithms, gives an example of the proposed paradigm, and displays algorithms developed by application of the technique. The algorithm for the merge of two ordered lists developed through application of this technique is thought to be original. The paradigm proposed is to create composite unit operations which combine data movement between data structures with a conventional operation such as compare or add. The composite operation constructed for this study is based upon partitioning the data elements into two linear lists. Exchange of data between adjacent elements in each list are then combined with compares and adds to complete the composite operations. This composite operation can be implemented on at least the following computational architectures.     

Scheduling Functions for Spatiotemporal Mapping of d-Dimensional Algorithms with Homogeneous Dependences on (d-2)-Dimensional Parallel Architectures

A formalized method is proposed for construction of scheduling functions for spatiotemporal mapping of d-dimensional algorithms represented by systems of homogeneous recurrence equations on (d-2)-dimensional parallel architectures. Basic operations of the algorithms are scheduled separately by means of functions with rational coefficients.