摘要:

The increasing interest in product networks (PNs) as a method of combining desirable properties of component networks, has prompted a need for the general study of the algorithmic issues related to this important class of interconnection networks. In this paper we present unified parallel algorithms for Gaussian elimination, with partial and complete pivoting, on product networks. A parallel algorithm for backward substitution is also presented. The proposed algorithms are network independent and are also independent of the matrix distribution methods employed. These algorithms can be used on a wide range of PNs including hypercube, mesh, and k-ary n-cube. Unified models for estimating computation time and interprocessor communication time are also presented. These models are then used to measure the performance of the proposed algorithms on several product networks

ISSN:1063-7192    

DOI:10.1080/10637199808947390

出版商:Taylor & Francis Group    

年代:2000

数据来源: Taylor

摘要:

In bulk-synchronous parallel (BSP) computation a superstep comprises a collection of concurrently executed processes with initial and terminal synchronisations. Data transfer between processes is realised through asynchronous communications. BSP programs can be organised either as explicit compositions of supersteps or as parallel compositions of threads (processes) which include synchronisation alignment operations. In this paper axiomatic semantics for the two approaches are proposed: in both cases the semantics are based on a new form of multiple substitution -predicate substitutionwhich generalises previous definitions of substitution.Predicate substitutiontogether with global synchronisation provide a means of linking state based and process semantics of BSP. Features of both models are illustrated through correctness proofs of matrix multiplication programs

ISSN:1063-7192    

DOI:10.1080/10637199808947391

出版商:Taylor & Francis Group    

年代:2000

数据来源: Taylor

摘要:

In this paper we analyze implementations of parallel Gram-Schmidt orthogonalization algorithms. One of the first parallel orthogonalization of Gram-Schmidt was the row-wise partitioning of O'Leary and Whitman. In this paper we describe a pipelined implementation which uses column-wise partitioning schemes. Timing models for the column-wise parallel algorithms are derived. We compare our column-wise partitionings against the row-wise partitioning and validate our study with computational results. The pipelined orthogonalization algorithm is important because the timing analysis is independent of the architecture model. Threshold values ofmmax, which is the number of rows where row partitioning becomes better than column partitioning are found theoretically and verified with our experiments

ISSN:1063-7192    

DOI:10.1080/10637199808947392

出版商:Taylor & Francis Group    

年代:2000

数据来源: Taylor

摘要:

Computation of maximal matching of a graph based on Depth First Search tree computation was introduced by Datta and Sen (Parallel Algorithms and Applications,5, 1995, 161-164). They showed that the approach gives efficient parallel algorithms for maximal matching for graphs for which DFS tree can be efficiently computed. They also presented a parallel scheme to compute a maximal matching in O(T(n) log n) time using O(P(n)) number of processors, where T(n) and P(n) are the time and the number of processors required to compute DFS tree of a graph in parallel. We present here, an improved technique to compute maximal matching in parallel based on DFS tree computation. The algorithm takes O(T(n)) time and O(P(n)) processors.

ISSN:1063-7192    

DOI:10.1080/10637199808947393

出版商:Taylor & Francis Group    

年代:2000

数据来源: Taylor

摘要:

This paper describes the development of a general Fortran 90 framework for the solution of composite laminate design problems using a genetic algorithm (GA). The initial Fortran 90 module and package of operators result in a standard genetic algorithm (sGA). The sGA is extended to operate on a parallel processor, and a migration algorithm is introduced. These extensions result in the distributed genetic algorithm with migration (dGA). The performance of the dGA in terms of cost and reliability is studied and compared to an sGA baseline, using two types of composite laminate design problems. The nondeterminism of GAs and the migration and dynamic load balancing algorithm used in this work result in a changed (diminished) workload, so conventional measures of parallelizability are not meaningful. Thus, a set of experiments is devised to characterize the run time performance of the dGA

ISSN:1063-7192    

DOI:10.1080/10637199808947394

出版商:Taylor & Francis Group    

年代:2000

数据来源: Taylor