Paper Info
Title
Defining Asymptotic Parallel Time Complexity of Data-dependent Algorithms.
Abstract
The scientific research community has reached a stage of maturity where its strong need for high-performance computing has diffused into also everyday life of engineering and industry algorithms. In efforts to satisfy this need, parallel computers provide an efficient and economical way to solve large-scale and/or time-constrained problems. As a consequence, the end-users of these systems have a vested interest in defining the asymptotic time complexity of parallel algorithms to predict their performance on a particular parallel computer.The asymptotic parallel time complexity of data-dependent algorithms depends on the number of processors, data size, and other parameters. Discovering the main other parameters is a challenging problem and the clue in obtaining a good estimate of performance order. Great examples of these types of applications are sorting algorithms, searching algorithms and solvers of the traveling salesman problem ().This article encompasses all the knowledge discovery aspects to the problem of defining the asymptotic parallel time complexity of data-dependent algorithms. The knowledge discovery methodology begins by designing a considerable number of experiments and measuring their execution times. Then, an interactive and iterative process explores data in search of patterns and/or relationships detecting some parameters that affect performance. Knowing the key parameters which characterise time complexity, it becomes possible to hypothesise to restart the process and to produce a subsequent improved time complexity model. Finally, the methodology predicts the performance order for new data sets on a particular parallel computer by replacing a numerical identification.As a case of study, a global pruning traveling salesman problem implementation () has been chosen to analyze the influence of indeterminism in performance prediction of data-dependent parallel algorithms, and also to show the usefulness of the defined knowledge discovery methodology. The subsequent hypotheses generated to define the asymptotic parallel time complexity of the were corroborated one by one. The experimental results confirm the expected capability of the proposed methodology; the predictions of performance time order were rather good comparing with real execution time (in the order of 85%).
Year
DOI
Venue
2014
10.1007/s00354-014-0202-2
New Generation Comput.
Keywords
Field
DocType
Complexity,Data-Dependent Algorithms,Parallel Computing,Performance Order
Analysis of parallel algorithms,Asymptotic computational complexity,Computer science,Parallel algorithm,Embarrassingly parallel,Algorithm,Theoretical computer science,Probabilistic analysis of algorithms,Time complexity,Scientific method,Cost efficiency
Journal
Volume
Issue
ISSN
32
2
0288-3635
Citations 
PageRank 
References 
0
0.34
13
Authors
3
Name
Order
Citations
PageRank
Paula Cecilia Fritzsche1133.97
Dolores Rexachs219543.20
Emilio Luque31097176.18