The Library
Parallel longest increasing subsequences in scalable time and memory
Tools
Tools
Tools
Tiskin, Alexander and Krusche, Peter (2010) Parallel longest increasing subsequences in scalable time and memory. In: Wyrzykowski, Roman and Dongarra, Jack and Karczewski, Konrad and Wasniewski, Jerzy, (eds.) Parallel processing and applied mathematics. Lecture Notes in Computer Science (6067). Germany: Springer Verlag, pp. 176-185. ISBN 9783642143892
![[img]](http://wrap.warwick.ac.uk/style/images/fileicons/application_pdf.png) |
PDF
fulltext6.pdf - Published Version Restricted to Repository staff only - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (260Kb) |
Official URL: http://dx.doi.org/10.1007/978-3-642-14390-8_19
Abstract
The longest increasing subsequence (LIS) problem is a classical problem in theoretical computer science and mathematics. Most existing parallel algorithms for this problem have very restrictive slackness conditions which prevent scalability to large numbers of processors. Other algorithms are scalable, but not work-optimal w.r.t. the fastest sequential algorithm for the LIS problem, which runs in time O(n logn) for n numbers in the comparison-based model. In this paper, we propose a new parallel algorithm for the LIS problem. Our algorithm solves the more general problem of semi-local comparison of permutation strings of length n in time O(n 1.5 / p) on p processors, has scalable communication cost of $O(n/\sqrt{p})$ and is synchronisation-efficient. Furthermore, we achieve scalable memory cost, requiring $O(n/\sqrt{p})$ of storage on each processor. When applied to LIS computation, this algorithm is superior to previous approaches since computation, communication, and memory costs are all scalable.
| Item Type: | Book Item |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
| Divisions: | Faculty of Science > Computer Science |
| Series Name: | Lecture Notes in Computer Science |
| Publisher: | Springer Verlag |
| Place of Publication: | Germany |
| ISBN: | 9783642143892 |
| Book Title: | Parallel processing and applied mathematics |
| Editor: | Wyrzykowski, Roman and Dongarra, Jack and Karczewski, Konrad and Wasniewski, Jerzy |
| Date: | 2010 |
| Number: | 6067 |
| Page Range: | pp. 176-185 |
| Identification Number: | 10.1007/978-3-642-14390-8_19 |
| Status: | Not Peer Reviewed |
| Publication Status: | Published |
| Funder: | Engineering and Physical Sciences Research Council (EPSRC), University of Warwick. Centre for Discrete Mathematics and Its Applications (DIMAP) |
| Grant number: | EP/D063191/1 (EPSRC) |
| URI: | http://wrap.warwick.ac.uk/id/eprint/47482 |
Actions (login required)
 |
View Item |
