The aim of the paper is to introduce general techniques in order to optimize the parallel execution time of sorting on a distributed architectures with processors of various speeds. Such an application requires a part...
详细信息
ISBN:
(纸本)3540338098
The aim of the paper is to introduce general techniques in order to optimize the parallel execution time of sorting on a distributed architectures with processors of various speeds. Such an application requires a partitioning step. For uniformly related processors (processors speeds are related by a constant factor), we develop a constant time technique for mastering processor load and execution time in an heterogeneous environment and also a technique to deal with unknown cost functions. For non uniformly related processors, we use a technique based on dynamic programming. Most of the time, the solutions are in O(p) (p is the number of processors), independent of the problem size n. Consequently, there is a small overhead regarding the problem we deal with but it is inherently limited by the knowing of time complexity of the portion of code following the partitioning.
We study the complexity of the parallel Givens factorization of a square matrix of size n on a shared memory architecture composed with p identical processors (coarse grained EREW PRAM). We show how to construct an as...
详细信息
We study the complexity of the parallel Givens factorization of a square matrix of size n on a shared memory architecture composed with p identical processors (coarse grained EREW PRAM). We show how to construct an asymptotically optimal algorithm. We deduce that the time complexity is equal to: T(opt)(p) = n2/2p + p + o(n) for 1 less-than-or-equal-to p less-than-or-equal-to n/2 + square-root 2 + o(n) and that the minimum number of processors in order to compute the Givens factorization in asymptotically optimal time (2n + o(n)) is equal to p(opt) = n/(2 + square-root 2) + o(n). These results complete previous analysis presented in the case where the number of processors is unlimited.
暂无评论