Krusche, Peter and Tiskin, Alexander (2010) Parallel longest increasing subsequences in scalable time and memory. In: 8th International Conference on Parallel Processing and Applied Mathematics, Wroclaw, Poland, September 13-16, 2009. Published in: Lecture Notes in Computer Science, Vol.6067 pp. 176-185.

Full text not available from this repository.

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 log n) for in numbers in the comparison-based model. In this paper, we propose a new parallel algorithm for the US problem. Our algorithm solves the more general problem of semi-local comparison of permutation strings of length it in time O(n(1.5)/p) on p processors, has scalable communication cost of O(n/ root p) and is synchronisation-efficient. Furthermore, we achieve scalable memory cost, requiring O(n/ root 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:	Conference Item (Paper)
Subjects:	Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Divisions:	Faculty of Science > Computer Science Faculty of Science > Centre for Systems Biology
Series Name:	Lecture Notes in Computer Science
Journal or Publication Title:	Lecture Notes in Computer Science
Publisher:	Springer
ISBN:	978-3-642-14389-2
ISSN:	0302-9743
Editor:	Wyrzykowski, R and Dongarra, J and Karczewski, K and Wasniewski, J
Date:	2010
Volume:	Vol.6067
Number of Pages:	10
Page Range:	pp. 176-185
Identification Number:	10.1007/978-3-642-14390-8_19
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Restricted or Subscription Access
Conference Paper Type:	Paper
Title of Event:	8th International Conference on Parallel Processing and Applied Mathematics
Type of Event:	Conference
Location of Event:	Wroclaw, Poland
Date(s) of Event:	September 13-16, 2009
URI:	http://wrap.warwick.ac.uk/id/eprint/5310

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item