This is optimal up to a multiplicative constant, since the number of sorting steps is bounded by the diameter of M(n,n), which is 2n-2. For example, N=n 2 numbers can be sorted on N-node 2-D mesh M(n,n) in time kn, where k is a constant between 2 and 3. There exist asymptotically optimal mesh-sorting algorithms.It sorts N numbers in EREW PRAM memory using N processors in time O(log N). The most fundamental is called Cole's Merge sort. there exist time- and cost-optimal PRAM parallel sorting algorithms.Several optimal sequential algorithms are known, such as QuickSort or HeapSort.Ī vast number of parallel sorting algorithms have been described in the literature and the state-of-the-art is briefly the following: The lower bound on the number of CE operations to sort N elements is \Omega(Nlog N). Sorting is one of fundamental problems in computer science. N will always denote the length of input data sequence. In Sections 15-18, we will discuss parallel deterministic sorting algorithms based on the compare-and-exchange (CE) operation.
Lower bound on 2-D mesh snakelike sortingīack to the beginning of the page Back to the CS838 class schedule Introduction to comparison-based sorting.Even-odd transposition sorting on 1-D meshes.Introduction to comparison-based sorting.Introduction to parallel sorting on mesh-based topologies Section#15: Introduction to parallel sorting on mesh-based topologies
0 kommentar(er)
