Given a simple graph G with n vertices and m edges, the spanning tree problem is to find a spanning tree for a given graph G. This problem has many applications, such as electric power systems, computer network design...Given a simple graph G with n vertices and m edges, the spanning tree problem is to find a spanning tree for a given graph G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. For a simple graph, the spanning tree problem can be solved in O(log n) time with O(m+n) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. In this paper, we shall propose a parallel algorithm which runs O(log n) time with O(n/log n) processors on the EREW PRAM for constructing on proper circle trapezoid graphs.展开更多
The real problem in cluster of workstations is the changes in workstation power or number of workstations or dynmaic changes in the run time behavior of the application hamper the efficient use of resources. Dynamic l...The real problem in cluster of workstations is the changes in workstation power or number of workstations or dynmaic changes in the run time behavior of the application hamper the efficient use of resources. Dynamic load balancing is a technique for the parallel implementation of problems, which generate unpredictable workloads by migration work units from heavily loaded processor to lightly loaded processors at run time. This paper proposed an efficient load balancing method in which parallel tree computations depth first search (DFS) generates unpredictable, highly imbalance workloads and moves through different phases detectable at run time, where dynamic load balancing strategy is applicable in each phase running under the MPI(message passing interface) and Unix operating system on cluster of workstations parallel platform computing.展开更多
In this paper, we propose an efficient parallel algorithm for generating k spanning trees of a connected, weighted and undirected graph Q(V,E,W) in the order of increasingweight. It runs in O(Tmst(n)+klogn) time with...In this paper, we propose an efficient parallel algorithm for generating k spanning trees of a connected, weighted and undirected graph Q(V,E,W) in the order of increasingweight. It runs in O(Tmst(n)+klogn) time with O(n2/ logn) processors on a CREW PRAM,where n=|V|, m=|E| and Tmst(n), O(log n)＜Tmst(n)＜O(log2 n) is the run time of the fastest parallel algorithm for finding a minimum spanning tree (MST) of G on a CREW PRAM. SinceTmst(n)=O(log2 n) for the time being, our algorithm is of the same time bound with Tmst(n)when k＜O(log n).展开更多
The techniques and methods for implementing parallel B+ -tree are firstpresented. Then, the parallel algorithms for data maintenance of B+ -tree, parallelalgorithms for maintaining schemes of the relations with parall...The techniques and methods for implementing parallel B+ -tree are firstpresented. Then, the parallel algorithms for data maintenance of B+ -tree, parallelalgorithms for maintaining schemes of the relations with parallel B+ - tree indices, and theparallel data operation algorithms based on the B+ -trees are propised. The proposedparallel B+ -trees and related parallel algorithms have been used in a parallel relationaldatabase system designed and implemented by the author. It is shown in practicethat the proposed parallel B+ -tree and algorithms are very efficient and very effective.展开更多
In this paper, it is supposed that the B&B algorithm finds the first optimal solution after h nodes have been expanded and m active nodes have been created in the state-space tree. Then the lower bound Ω(m+h log ...In this paper, it is supposed that the B&B algorithm finds the first optimal solution after h nodes have been expanded and m active nodes have been created in the state-space tree. Then the lower bound Ω(m+h log h) of the running time for the general sequential B&B algorithm and the lower bound Ω(m/p+h log p) for the general parallel best-first B&B algorithm in PRAM-CREW are proposed, where p is the number of processors available. Moreover, the lower bound Ω(M/p+H+(H/p) log (H/p)) is presented for the parallel algorithms on distributed memory system, where M and H represent total number of the active nodes and that of the expanded nodes processed by p processors, respectively. In addition, a nearly fastest general parallel best-first B&B algorithm is put forward. The parallel algorithm is the fastest one as p = max{hε, r}, where ε = 1/ rootlogh, and r is the largest branch number of the nodes in the state-space tree.展开更多
The reconfigurable mesh consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns among the processors. Recent...The reconfigurable mesh consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns among the processors. Recently, this model has attracted a lot of attention. In this paper, two efficient algorithms are proposed for computing the minimum spanning tree of an n-vertex undirected graph. One runs on an n×n reconfigurable mesh with time complexity of O(log^2 n). The other runs with time complexity of O(log n) on an n^(1+E)×n reconfigurable mesh, where < E < 1 is a constant. All these improve the previously known results on the reconfigurable mesh.展开更多
Network reconfiguration is of theoretical and practical significance to guarantee safe and economical operation of distribution system.In this paper,based on all spanning trees of undirected graph,a novel genetic algo...Network reconfiguration is of theoretical and practical significance to guarantee safe and economical operation of distribution system.In this paper,based on all spanning trees of undirected graph,a novel genetic algorithm for electric distribution network reconfiguration is proposed.Above all,all spanning trees of simplified graph of distribution network are found.Tie branches are obtained with spanning tree subtracted from simplified graph.There is one and only one switch open on each tie branch.Decimal identity number of open switch on each tie branch is taken as the optimization variable.Therefore,the length of chromosome is very short.Each spanning tree corresponds to one subpopulation.Gene operations of each subpopulation are implemented with parallel computing method.Individuals of offspring after gene operation automatically meet with radial and connected constraints for distribution network operation.Disadvantages of conventional genetic algorithm for network reconfiguration that a large amount of unfeasible solutions are created after crossover and mutation,which result in very low searching efficiency,are completely overcome.High calculation speed and superior capability of the proposed method are validated by two test cases.展开更多
A contour-parallel offset （CPO） tool-path linking algorithm is derived without toolretractions and with the largest practicability. The concept of ＂tool-path loop tree＂ （TPL-tree） providing the information on th...A contour-parallel offset （CPO） tool-path linking algorithm is derived without toolretractions and with the largest practicability. The concept of ＂tool-path loop tree＂ （TPL-tree） providing the information on the parent/child relationships among the tool-path loops （TPLs） is presented. The direction, tool-path loop, leaf/branch, layer number, and the corresponding points of the TPL-tree are introduced. By defining TPL as a vector, and by traveling throughout the tree, a CPO tool-path without tool-retractions can be derived.展开更多
We present a parallel algorithm that computes the ask and bid prices of an American option when proportional transaction costs apply to trading in the underlying asset. The algorithm computes the prices on recombining...We present a parallel algorithm that computes the ask and bid prices of an American option when proportional transaction costs apply to trading in the underlying asset. The algorithm computes the prices on recombining binomial trees, and is designed for modern multi-core processors. Although parallel option pricing has been well studied, none of the existing approaches takes transaction costs into consideration. The algorithm that we propose partitions a binomial tree into blocks. In any round of computation a block is further partitioned into regions which are assigned to distinct processors. To minimise load imbalance the assignment of nodes to processors is dynamically adjusted before each new round starts. Synchronisation is required both within a round and between two successive rounds. The parallel speedup of the algorithm is proportional to the number of processors used. The parallel algorithm was implemented in C/C++ via POSIX Threads, and was tested on a machine with 8 processors. In the pricing of an American put option, the parallel speedup against an efficient sequential implementation was 5.26 using 8 processors and 1500 time steps, achieving a parallel efficiency of 65.75%.展开更多
文摘Given a simple graph G with n vertices and m edges, the spanning tree problem is to find a spanning tree for a given graph G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. For a simple graph, the spanning tree problem can be solved in O(log n) time with O(m+n) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. In this paper, we shall propose a parallel algorithm which runs O(log n) time with O(n/log n) processors on the EREW PRAM for constructing on proper circle trapezoid graphs.
基金Natural Science Foundation of China (No.60 173 0 3 1)
文摘The real problem in cluster of workstations is the changes in workstation power or number of workstations or dynmaic changes in the run time behavior of the application hamper the efficient use of resources. Dynamic load balancing is a technique for the parallel implementation of problems, which generate unpredictable workloads by migration work units from heavily loaded processor to lightly loaded processors at run time. This paper proposed an efficient load balancing method in which parallel tree computations depth first search (DFS) generates unpredictable, highly imbalance workloads and moves through different phases detectable at run time, where dynamic load balancing strategy is applicable in each phase running under the MPI(message passing interface) and Unix operating system on cluster of workstations parallel platform computing.
文摘In this paper, we propose an efficient parallel algorithm for generating k spanning trees of a connected, weighted and undirected graph Q(V,E,W) in the order of increasingweight. It runs in O(Tmst(n)+klogn) time with O(n2/ logn) processors on a CREW PRAM,where n=|V|, m=|E| and Tmst(n), O(log n)＜Tmst(n)＜O(log2 n) is the run time of the fastest parallel algorithm for finding a minimum spanning tree (MST) of G on a CREW PRAM. SinceTmst(n)=O(log2 n) for the time being, our algorithm is of the same time bound with Tmst(n)when k＜O(log n).
文摘The techniques and methods for implementing parallel B+ -tree are firstpresented. Then, the parallel algorithms for data maintenance of B+ -tree, parallelalgorithms for maintaining schemes of the relations with parallel B+ - tree indices, and theparallel data operation algorithms based on the B+ -trees are propised. The proposedparallel B+ -trees and related parallel algorithms have been used in a parallel relationaldatabase system designed and implemented by the author. It is shown in practicethat the proposed parallel B+ -tree and algorithms are very efficient and very effective.
基金This paper was supported by Ph. D. Foundation of State Education Commission of China.
文摘In this paper, it is supposed that the B&B algorithm finds the first optimal solution after h nodes have been expanded and m active nodes have been created in the state-space tree. Then the lower bound Ω(m+h log h) of the running time for the general sequential B&B algorithm and the lower bound Ω(m/p+h log p) for the general parallel best-first B&B algorithm in PRAM-CREW are proposed, where p is the number of processors available. Moreover, the lower bound Ω(M/p+H+(H/p) log (H/p)) is presented for the parallel algorithms on distributed memory system, where M and H represent total number of the active nodes and that of the expanded nodes processed by p processors, respectively. In addition, a nearly fastest general parallel best-first B&B algorithm is put forward. The parallel algorithm is the fastest one as p = max{hε, r}, where ε = 1/ rootlogh, and r is the largest branch number of the nodes in the state-space tree.
基金Ph.D.foundation of Sate Education Commission of China
文摘The reconfigurable mesh consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns among the processors. Recently, this model has attracted a lot of attention. In this paper, two efficient algorithms are proposed for computing the minimum spanning tree of an n-vertex undirected graph. One runs on an n×n reconfigurable mesh with time complexity of O(log^2 n). The other runs with time complexity of O(log n) on an n^(1+E)×n reconfigurable mesh, where < E < 1 is a constant. All these improve the previously known results on the reconfigurable mesh.
文摘Network reconfiguration is of theoretical and practical significance to guarantee safe and economical operation of distribution system.In this paper,based on all spanning trees of undirected graph,a novel genetic algorithm for electric distribution network reconfiguration is proposed.Above all,all spanning trees of simplified graph of distribution network are found.Tie branches are obtained with spanning tree subtracted from simplified graph.There is one and only one switch open on each tie branch.Decimal identity number of open switch on each tie branch is taken as the optimization variable.Therefore,the length of chromosome is very short.Each spanning tree corresponds to one subpopulation.Gene operations of each subpopulation are implemented with parallel computing method.Individuals of offspring after gene operation automatically meet with radial and connected constraints for distribution network operation.Disadvantages of conventional genetic algorithm for network reconfiguration that a large amount of unfeasible solutions are created after crossover and mutation,which result in very low searching efficiency,are completely overcome.High calculation speed and superior capability of the proposed method are validated by two test cases.
文摘A contour-parallel offset （CPO） tool-path linking algorithm is derived without toolretractions and with the largest practicability. The concept of ＂tool-path loop tree＂ （TPL-tree） providing the information on the parent/child relationships among the tool-path loops （TPLs） is presented. The direction, tool-path loop, leaf/branch, layer number, and the corresponding points of the TPL-tree are introduced. By defining TPL as a vector, and by traveling throughout the tree, a CPO tool-path without tool-retractions can be derived.
文摘We present a parallel algorithm that computes the ask and bid prices of an American option when proportional transaction costs apply to trading in the underlying asset. The algorithm computes the prices on recombining binomial trees, and is designed for modern multi-core processors. Although parallel option pricing has been well studied, none of the existing approaches takes transaction costs into consideration. The algorithm that we propose partitions a binomial tree into blocks. In any round of computation a block is further partitioned into regions which are assigned to distinct processors. To minimise load imbalance the assignment of nodes to processors is dynamically adjusted before each new round starts. Synchronisation is required both within a round and between two successive rounds. The parallel speedup of the algorithm is proportional to the number of processors used. The parallel algorithm was implemented in C/C++ via POSIX Threads, and was tested on a machine with 8 processors. In the pricing of an American put option, the parallel speedup against an efficient sequential implementation was 5.26 using 8 processors and 1500 time steps, achieving a parallel efficiency of 65.75%.
