Standard

Parallel longest increasing subsequences in scalable time and memory. / Krusche, Peter; Tiskin, Alexander.

Parallel Processing and Applied Mathematics (PPAM 2009). Vol. PART 1 2010. p. 176-185 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6067).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Harvard

Krusche, P & Tiskin, A 2010, Parallel longest increasing subsequences in scalable time and memory. in Parallel Processing and Applied Mathematics (PPAM 2009). vol. PART 1, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6067, pp. 176-185. https://doi.org/10.1007/978-3-642-14390-8_19

APA

Krusche, P., & Tiskin, A. (2010). Parallel longest increasing subsequences in scalable time and memory. In Parallel Processing and Applied Mathematics (PPAM 2009) (Vol. PART 1, pp. 176-185). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6067). https://doi.org/10.1007/978-3-642-14390-8_19

Vancouver

Krusche P, Tiskin A. Parallel longest increasing subsequences in scalable time and memory. In Parallel Processing and Applied Mathematics (PPAM 2009). Vol. PART 1. 2010. p. 176-185. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-14390-8_19

Author

Krusche, Peter ; Tiskin, Alexander. / Parallel longest increasing subsequences in scalable time and memory. Parallel Processing and Applied Mathematics (PPAM 2009). Vol. PART 1 2010. pp. 176-185 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{4fb7db3d56e94e45b2bfac707046a3f4,
title = "Parallel longest increasing subsequences in scalable time and memory",
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 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/ √p) and is synchronisation- efficient. Furthermore, we achieve scalable memory cost, requiring O(n/ √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. {\textcopyright} 2010 Springer-Verlag Berlin Heidelberg.",
author = "Peter Krusche and Alexander Tiskin",
year = "2010",
month = aug,
day = "5",
doi = "10.1007/978-3-642-14390-8_19",
language = "English",
volume = "PART 1",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "176--185",
booktitle = "Parallel Processing and Applied Mathematics (PPAM 2009)",

}

RIS

TY - GEN

T1 - Parallel longest increasing subsequences in scalable time and memory

AU - Krusche, Peter

AU - Tiskin, Alexander

PY - 2010/8/5

Y1 - 2010/8/5

N2 - 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 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/ √p) and is synchronisation- efficient. Furthermore, we achieve scalable memory cost, requiring O(n/ √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. © 2010 Springer-Verlag Berlin Heidelberg.

AB - 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 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/ √p) and is synchronisation- efficient. Furthermore, we achieve scalable memory cost, requiring O(n/ √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. © 2010 Springer-Verlag Berlin Heidelberg.

UR - http://www.scopus.com/inward/record.url?scp=77955110445&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-14390-8_19

DO - 10.1007/978-3-642-14390-8_19

M3 - Conference contribution

AN - SCOPUS:77955110445

VL - PART 1

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 176

EP - 185

BT - Parallel Processing and Applied Mathematics (PPAM 2009)

ER -

ID: 127758167