Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 3 of 3
Full-Text Articles in Physical Sciences and Mathematics
Optimal Parallel Lexicographic Sorting Using A Fine-Grained Decomposition, Ramachandran Vaidyanathan, Carlos R.P. Hartmann, Pramod Varshney
Optimal Parallel Lexicographic Sorting Using A Fine-Grained Decomposition, Ramachandran Vaidyanathan, Carlos R.P. Hartmann, Pramod Varshney
Electrical Engineering and Computer Science - Technical Reports
Though non-comparison based sorting techniques like radix sorting can be done with less "work" than conventional comparison-based methods, they are not used for long keys. This is because even though parallel radix sorting algorithms process the keys in parallel, the symbols in the keys are processed sequentially. In this report, we give an optimal algorithm for lexicographic sorting that can be used to sort n m-bit keys on an EREW model in Ө (log nlogm) time with Ө (mn) "work". This algorithm is not only as fast as any optimal non-comparison based algorithm, but can also be executed with less …
Optimal Parallel Solutions To The Neighbor Localization Problem And Integer Sorting: A Fine Grained Approach, Ramachandran Vaidyanathan, Carlos R.P. Hartmann, Pramod K. Varshney
Optimal Parallel Solutions To The Neighbor Localization Problem And Integer Sorting: A Fine Grained Approach, Ramachandran Vaidyanathan, Carlos R.P. Hartmann, Pramod K. Varshney
Electrical Engineering and Computer Science - Technical Reports
In this report, a fine-grained decomposition approach is used to obtain an optimal parallel solution to the Neighbor Localization Problem, which in turn is œ used to sort n θ(log n)-bit numbers optimally on an EREW model. The model of computation used is the EREW Reconfigurable PRAM (R-PRAM) that permits the use of “very small” processors. The main result of this report is a parallel EREW R-PRAM algorithm that sorts n θ(log n)-bit numbers in θ(log n) time with θ(n log n) “work”. The proposed algorithm is asymptotically optimal in time and efficiency. If a weaker variant of the R-PRAM …
Embedding Meshes On The Star Graph, Sanjay Ranka, Jhy-Chun Wang, Nangkang Yeh
Embedding Meshes On The Star Graph, Sanjay Ranka, Jhy-Chun Wang, Nangkang Yeh
Electrical Engineering and Computer Science - Technical Reports
We develop algorithms for mapping n-dimensional meshes on a star graph of degree n with expansion 1 and dilation 3. We show that an n degree star graph can efficiently simulate an n-dimensional mesh.