Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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] PDF
fulltext6.pdf - Published Version
Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer.

Download (260Kb)
Official URL: http://dx.doi.org/10.1007/978-3-642-14390-8_19

Request Changes to record.

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
Official Date: 2010
Dates:
DateEvent
2010Published
Number: 6067
Page Range: pp. 176-185
DOI: 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)

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us