WWW.ABSTRACT.DISLIB.INFO
FREE ELECTRONIC LIBRARY - Abstracts, online materials
 
<< HOME
CONTACTS



«PPAM 2009 What is in this talk? Some discussion of asymptotic scalability measures for parallel algorithms. A simple algorithmic problem that is hard ...»

Parallel Longest Increasing

Subsequences in Scalable Time and

Memory

Peter Krusche Alexander Tiskin

Department of Computer Science

University of Warwick, Coventry, CV4 7AL, UK

PPAM 2009

What is in this talk?

Some discussion of asymptotic scalability

measures for parallel algorithms.

A simple algorithmic problem that is

hard to parallelize scalably...

... and a scalable algorithm for it.

Outline

Parallel Algorithms

The BSP Model

Asymptotic Scalability Longest Increasing Subsequences The Problem Sequential LIS Permutation String Comparison Parallel LIS computation Previous Work Our Algorithm Summary and Outlook Machine Model Ingredients M A BSP computer with p processors/ cores/threads.

p External and per-processor memory.

t c1 c2 Superstep-style code execution. cp Machine Model Ingredients M A BSP computer with p processors/ cores/threads. m m m m External and per-processor memory.

t c1 c2 Superstep-style code execution. cp Machine Model Ingredients M A BSP computer with p processors/ cores/threads. m m m m External and per-processor memory.

t c1 c2 Superstep-style code execution. cp Algorithm Ingredients: Sequential Algorithms We have a problem of size n. We study... the total work W(n)... the memory requirement M(n)... the input/output size: I(n) We assume that the input and output are stored in the environment (e.g. external memory).

Algorithm Ingredients: Parallel Algorithms Across all supersteps of the algorithm, we look at... the computation time: W (n; p)... the communication cost: H(n; p)... the local memory cost: M(n; p) How to do these costs relate to scalability?

Algorithm Ingredients: Parallel Algorithms Across all supersteps of the algorithm, we look at... the computation time: W (n; p)... the communication cost: H(n; p)... the local memory cost: M(n; p) How to do these costs relate to scalability?

Classical Criterion: Work Optimality An algorithm is work-optimal (w.r.t. a sequential algorithm) if W(n) „ « W (n; p) = O

–  –  –

Example (Matrix Multiplication) Algorithms achieving W (n; p) = O(n3 =p) are work-optimal w.r.t. the sequential O(n3 ) method.

We have absolute work-optimality if ˙(W(n)) is a lower bound on the total work for the given problem, and the given model.

Classical Criterion: Work Optimality

–  –  –

Example (Matrix Multiplication) Algorithms achieving W (n; p) = O(n3 =p) are work-optimal w.r.t. the sequential O(n3 ) method.

We have absolute work-optimality if ˙(W(n)) is a lower bound on the total work for the given problem, and the given model.

Classical Criterion: Work Optimality

–  –  –

Example (Matrix Multiplication) Algorithms achieving W (n; p) = O(n3 =p) are work-optimal w.r.t. the sequential O(n3 ) method.

We have absolute work-optimality if ˙(W(n)) is a lower bound on the total work for the given problem, and the given model.

Scalable Communication and Memory

–  –  –

Scalable memory allows to increase number of virtual threads until subproblems fit into caches.

Scalable communication models algorithmic bus bandwidth sharing.

Algorithms with scalable memory and communication can be simulated efficiently on more complex parallel machine models.

Why Scalable Communication and Memory?

Scalable memory allows to increase number of virtual threads until subproblems fit into caches.

Scalable communication models algorithmic bus bandwidth sharing.

Algorithms with scalable memory and communication can be simulated efficiently on more complex parallel machine models.

Why Scalable Communication and Memory?

Scalable memory allows to increase number of virtual threads until subproblems fit into caches.

Scalable communication models algorithmic bus bandwidth sharing.

Algorithms with scalable memory and communication can be simulated efficiently on more complex parallel machine models.

Outline Parallel Algorithms The BSP Model Asymptotic Scalability Longest Increasing Subsequences The Problem Sequential LIS Permutation String Comparison Parallel LIS computation Previous Work Our Algorithm Summary and Outlook The Problem Given a sequence of n numbers, to find the longest subsequence that is increasing.

2, 9, 1, 3, 7, 5, 6, 4, 8 (alternate solution) Sequential Algorithms The LIS can be found by patience sorting.

(see [Knuth:73, Aldous/Diaconis:99, Schensted:61]).

Another approach: LIS via permutation string comparison.

(see [Hunt/Szymanski:77]).

For both algorithms, W(n) = O(n log n) in the comparison-based model.

Permutation String Comparison Definition (Input data) Let x = x1 x2 : : : xn and y = y1 y2 : : : yn be two permutation strings on an alphabet ˚.

Definition (Subsequences) A subsequence u of x: u can be obtained by deleting zero or more elements from x.

Definition (Longest Common Subsequences) An LCS (x, y) is any string which is subsequence of both x and y and has maximum possible length.

Length of these sequences: LLCS (x, y).

LIS via LCS How to compute comparison-based LIS using LCS computation?

1. Copy the sequence and sort it.





2. Compute the LCS of the sequence and its sorted copy.

LCS grid dags and highest-score matrices

–  –  –

Parallel Algorithms The BSP Model Asymptotic Scalability Longest Increasing Subsequences The Problem Sequential LIS Permutation String Comparison Parallel LIS computation Previous Work Our Algorithm Summary and Outlook Parallel LIS Algorithms Garcia,2001 LIS by parallel dynamic programming.

–  –  –

(... which, in fact, can solve a slightly more general problem than LIS) Our Tool: Semi-local Sequence Comparison Definition (Substrings) A substring of any string x can be obtained by removing zero or more characters from the beginning and/or the end of x.

Definition (Highest-score matrix) The element A(i; j) of the LCS highest-score matrix of two strings x and y gives the LLCS of yi : : : yj and x.

Definition (Semi-local LCS) Solutions to the semi-local LCS problem are given by a highest-score matrix A(i; j).

Critical points Definition (Critical Point) Odd half-integer point (i ` 1 ; j + 1 ) is critical iff.

A(i; j) + 1 = A(i ` 1; j) = A(i; j + 1) = A(i ` 1; j + 1).

Theorem

1. For permutation string inputs of length n, N = 2n such critical points are sufficient to implicitly represent the whole matrix [Schmidt:95/Alves+:06/Tiskin:05].

2. There is an algorithm to obtain these points in time O(n1:5 ) [Tiskin:06].

Critical points Definition (Critical Point) Odd half-integer point (i ` 1 ; j + 1 ) is critical iff.

A(i; j) + 1 = A(i ` 1; j) = A(i; j + 1) = A(i ` 1; j + 1).

Theorem

1. For permutation string inputs of length n, N = 2n such critical points are sufficient to implicitly represent the whole matrix [Schmidt:95/Alves+:06/Tiskin:05].

2. There is an algorithm to obtain these points in time O(n1:5 ) [Tiskin:06].

Highest-score matrices Example (Highest-score matrix for x =4312 and y =1234)

–  –  –

Given the implicit highest-score matrices DA and DB for two adjacent grid dag blocks, we compute the distribution matrix dC for the union of these blocks.

–  –  –

For each block in DC, only a subset of nonzeros in DA and DB are relevant.

Divide-and-conquer Multiplication The smaller the blocks, the less nonzeros are relevant!

All data for processing a block of size h can be stored in space O(h).

We can partition and compute the number of nonzeros in a block in time O(h).

) We get a divide-and-conquer algorithm for multiplying highest-score matrices of size N running in O(N 1:5 ).

Parallel Multiplication We first partition DC into p blocks and then finish the computation on these blocks independently [K,Tiskin:06].

–  –  –

To apply this algorithm to the LIS problem, we need to (min; +)-multiply work-optimally!

Work-optimal Multiplication Lemma We can locate a set of k nonzeros in a block of p size h in time O(h k).

Load-balancing Processors locate groups of maximally N=p nonzeros.

We have maximally p complete groups (N nonzeros overall).

We have maximally one incomplete group on each processor.

Work-optimal Multiplication Lemma We can locate a set of k nonzeros in a block of p size h in time O(h k).

Load-balancing Processors locate groups of maximally N=p nonzeros.

We have maximally p complete groups (N nonzeros overall).

We have maximally one incomplete group on each processor.

Work-optimal Multiplication Lemma We can locate all nonzeros using W (N; p) = O(N 1:5 =p).

–  –  –

Matches can be distributed in a scalable fashion using e.g. sorting by regular sampling.

Discussion of Practicality Speedup over the sequential algorithm is possible if input is distributed equally between processors.

This is interesting if we have big records to compare – in the comparison-based model, our sequence elements do not have to be numbers.

Speedup for large sequences is limited due to asymptotically very fast sequential algorithm.

Outline Parallel Algorithms The BSP Model Asymptotic Scalability Longest Increasing Subsequences The Problem Sequential LIS Permutation String Comparison Parallel LIS computation Previous Work Our Algorithm Summary and Outlook Summary and Outlook We have shown a scalable approach to computing longest increasing subsequences.

We are currently working on an improvement

to the parallel multiplication algorithm:

) We aim to reduce the work for multiplication to W (n; p) = O((n log n)=p).

This will bring us a step closer to achieving general work-optimality in a scalable fashion.

Thanks for listening!

Questions?

Parallel Algorithms The BSP Model Asymptotic Scalability Longest Increasing Subsequences The Problem Sequential LIS Permutation String Comparison Parallel LIS computation Previous Work Our Algorithm



Similar works:

«Chi Alpha Discipleship Tool Sacred Pathways Do you find yourself envious of the way that some other people connect with God? This resource helps you understand all the different ways that people can connect to God, and shows you the value of each and every path. Instead of trying to imitate another person’s walk with God, you should focus on bettering your own “sacred pathway.” This resource is based on the book, Sacred Pathways, written by Gary Thomas. Broken into two parts, the first...»

«Informatieblad Geloofsgemeenschap H. Pancratius Tubbergen -INFORMATIEBLAD VOOR DE GELOOFSGEMEENSCHAP VAN DE ST.-PANCRATIUSBASILIEK TUBBERGEN Jaargang 50 nr.23 26 november tot 10 december 2016 -ZOZEER HEEFT GOD DE WERELD LIEFGEHAD Terwijl het in de natuur grijzer, kouder en donkerder wordt, bereiden wij ons als christenen voor op de komst van het Licht. Het licht als begin voor een nieuwe tijd waarin wij weer ervaren hoe God ons dichterbij komt als de hoopgevende Messias, hoe God ons wil...»

«Microfluidics a Potent Route to Sample Delivery for Non-intrusive Sensors George Kyriacou, Hong Chang, Joseph Gargiuli, Ajay Agarwal and Pankaj Vadgama Abstract Biosensors offer wide opportunities for threat agent analysis, but practical analytical systems require these sensors to be integrated with preand post analytical steps to enable simplified, seamless operation. Perhaps the most important of these steps relates to sample handling and presentation. Advances in microfluidics now offer a...»

«CROSSROADS Evangelical Fellowship e-Newsletter February 2015 Dear Friends, Executive Committee Members The Covenant Presidents of the Council of Bishops, Bishop Rosemarie Wenner and Warner H. Brown, Jr., affirm Rev. H. O. “Tom” Thomas, President The Book of Discipline 2012 is the United Methodist Church’s ‘book of covenant’. This covenant they affirm ‘the most current statement of how United Methodists agree to live their lives together’. Rev. Burt Robinson, Vice President How do...»

«Leading Organizational Change Is Like Climbing a Mountain by Judith Zimmerman Abstract Leading organizational change is like climbing a mountain. Transformational leaders must prepare to lead change, understand the process and nature of change, and provide the essential gear so that those involved can be successful. The author draws on the literature and personal experiences as a hiker and change leader to provide a guide for leading organizational change. My husband Bill and I have had the...»

«BANNING THE SALE OF CATS, DOGS AND RABBITS IN OTTAWA PET STORES AND OTHER RETAIL AVENUES SUBMISSION TO CITY OF OTTAWA February 16, 2016 ` RECOMMENDATIONS RE BANNING THE SALE OF CATS, DOGS AND RABBITS IN OTTAWA PET STORES About PAWS Puppymill Awareness Working Solutions (PAWS) is a volunteer, non-profit organization in Ottawa, Ontario dedicated to raising public awareness and educating the public at large regarding the cruelty and abuse associated with puppy mills. This includes selling puppies...»

«RESTRICTED CONFERENCE ON STRENGTHENING SECTORAL POSITION AND FLOW DATA IN THE MACROECONOMIC ACCOUNTS Jointly organized by the IMF and OECD February 28–March 2, 2011 IMF Headquarters 2 (HQ2) Conference Hall 1 & 2 (lobby level) 1900 Pennsylvania Ave NW, Washington, DC, 20431 Non-Financial Balance Sheets for the Netherlands: Use, Compilation and Extensions To be presented in Session 5 by Bram (Abraham J.) de Boo The views expressed in this paper and web links to papers that will be considered at...»

«IN THE UNITED STATES DISTRICT COURT FOR THE EASTERN DISTRICT OF PENNSYLVANIA : UNITED STATES OF AMERICA : : CRIMINAL ACTION v. : : NO. 06-319 LEONARD P. LUCHKO : MARK C. EISTER : Memorandum and Order YOHN, J. October _, 2006 The United States brings the instant motion for a protective order over discovery materials, pursuant to Federal Rule of Criminal Procedure 16(d)(1). Since the initial filing of this motion, the government has significantly altered and narrowed the scope of the proposed...»

«REGLEMENT RELATIF AUX MODALITES D’ATTRIBUTION DES AIDES DE L’APPEL A PROJETS ENERGIES MARINES RENOUVELABLES INSTITUTS POUR LA TRANSITION ENERGETIQUE ANR | REGLEMENT RELATIF AUX MODALITES D’ATTRIBUTION DES AIDES DE L’ANR POUR AAP EMR /16 Sommaire PREAMBULE 1 OBJET 2 DEFINITIONS 3 CHAMP D’APPLICATION 3.1 Régime applicable 3.2 Etablissements coordinateurs 3.3 Activités de recherche 3.4 Exclusions – Entreprises en difficulté 4 MONTANT DE L’AIDE 4.1 Assiette de l’Aide 4.1.1...»

«PORTA LINGUARUM 14, junio 2010 pp. 45-58 Teachers’ Concerns and Uncertainties about the Introduction of CLIL Programmes VÍCTOR PAVÓN VÁZQUEZ University of Cordoba FERNANDO RUBIO University of Huelva Received: 6 June 2009 / Accepted: 20 November 2009 ISSN: 1697-7467 ABSTRACT: The implementation of content and language integrated learning (CLIL) means significant changes in the way in which teaching is planned, sequenced and carried out. The adoption of a new curriculum, which integrates...»

«Trading Markets With Canonical Momenta and Adaptive Simulated Annealing Lester Ingber ANALYSIS VERSUS INTUITION Too often the management of complex systems is ill-served by not utilizing the best tools available. For example, requirements set by decision-makers often are not formulated in the same language as constructs formulated by powerful mathematical formalisms, and so the products of analyses are not properly or maximally utilized, even if and when they come close to faithfully...»

«Traumatismo Grave de Cuello Gandini Luciano J. TSEM-Docente Fundación IDEM Rosario, Argentina www.reeme.arizona.edu Jornada Actualización Emergencias www.reeme.arizona.edu Venado Tuerto 2004 TRAUMATISMO DE CUELLO Pocas emergencias presentan el desafio que presentan los traumatismos de cuello Vía Aérea Lesiones Grandes Vasos Lesión espinal Jornada Actualización Emergencias www.reeme.arizona.edu Venado Tuerto 2004 VÍA AÉREA Jornada Actualización Emergencias www.reeme.arizona.edu Venado...»





 
<<  HOME   |    CONTACTS
2017 www.abstract.dislib.info - Abstracts, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.