The Experts below are selected from a list of 4902 Experts worldwide ranked by ideXlab platform
Melih Ozlen - One of the best experts on this subject based on the ideXlab platform.
-
a Tree Traversal algorithm for decision problems in knot theory and 3 manifold topology
Algorithmica, 2013Co-Authors: Benjamin A Burton, Melih OzlenAbstract:In low-dimensional topology, many important decision algorithms are based on normal surface enumeration, which is a form of vertex enumeration over a high-dimensional and highly degenerate polytope. Because this enumeration is subject to extra combinatorial constraints, the only practical algorithms to date have been variants of the classical double description method. In this paper we present the first practical normal surface enumeration algorithm that breaks out of the double description paradigm. This new algorithm is based on a Tree Traversal with feasibility and domination tests, and it enjoys a number of advantages over the double description method: incremental output, significantly lower time and space complexity, and a natural suitability for parallelisation. Experimental comparisons of running times are included.
-
a Tree Traversal algorithm for decision problems in knot theory and 3 manifold topology
Algorithmica, 2013Co-Authors: Benjamin A Burton, Melih OzlenAbstract:In low-dimensional topology, many important decision algorithms are based on normal surface enumeration, which is a form of vertex enumeration over a high-dimensional and highly degenerate polytope. Because this enumeration is subject to extra combinatorial constraints, the only practical algorithms to date have been variants of the classical double description method. In this paper we present the first practical normal surface enumeration algorithm that breaks out of the double description paradigm. This new algorithm is based on a Tree Traversal with feasibility and domination tests, and it enjoys a number of advantages over the double description method: incremental output, significantly lower time and space complexity, and a natural suitability for parallelisation. Experimental comparisons of running times are included.
-
a Tree Traversal algorithm for decision problems in knot theory and 3 manifold topology
Symposium on Computational Geometry, 2011Co-Authors: Benjamin A Burton, Melih OzlenAbstract:In low-dimensional topology, many important decision algorithms are based on normal surface enumeration, which is a form of vertex enumeration over a high-dimensional and highly degenerate polytope. Because this enumeration is subject to extra combinatorial constraints, the only practical algorithms to date have been variants of the classical double description method. In this paper we present the first practical normal surface enumeration algorithm that breaks out of the double description paradigm. This new algorithm is based on a Tree Traversal with feasibility and domination tests, and it enjoys a number of advantages over the double description method: incremental output, significantly lower time and space complexity, and a natural suitability for parallelisation.
Michela Becchi - One of the best experts on this subject based on the ideXlab platform.
-
an analytical study of recursive Tree Traversal patterns on multi and many core platforms
International Conference on Parallel and Distributed Systems, 2017Co-Authors: Michela BecchiAbstract:Recursive Tree Traversals are found in many application domains, such as data mining, graphics, machine learning and scientific simulations. In the past few years there has been growing interest in the deployment of applications based on graph data structures on many-core devices. A couple of recent efforts have focused on optimizing the execution of multiple serial Tree Traversals on GPU, and have reported performance trends that vary across algorithms. In this work, we aim to understand how to select the implementation and platform that is most suited to a given Tree Traversal algorithm and dataset. To this end, we perform a systematic study of recursive Tree Traversal on CPU, GPU and the Intel Phi processor. We first identify four Tree Traversal patterns: three of them performing multiple serial Traversals concurrently, and the last one performing a single parallel level order Traversal. For each of these patterns, we consider different code variants including existing and new optimization methods, and we characterize their control-flow and memory access patterns. We implement these code variants and evaluate them on CPU, GPU and Intel Phi. Our analysis shows that there is not a single code variant and platform that achieves the best performance on all Tree Traversal patterns, and it provides guidelines on the selection of the implementation most suited to a given Tree Traversal pattern and input dataset.
Milind Kulkarni - One of the best experts on this subject based on the ideXlab platform.
-
Treelogy a benchmark suite for Tree Traversal applications
IEEE International Symposium on Workload Characterization, 2016Co-Authors: Nikhil Hegde, Jianqiao Liu, Milind KulkarniAbstract:An interesting class of irregular algorithms are Tree Traversal algorithms, which repeatedly traverse spatial Trees to perform efficient computations. Optimizing Tree Traversal algorithms requires understanding specific characteristics of these algorithms which affect their behavior and govern which types of optimizations are likely to perform well. In this work, we present a set of Tree Traversal applications, drawn from multiple domains, called Treelogy. This benchmark suite can be studied through the use of an ontology that characterizes Tree Traversal algorithms according to structural properties of the algorithm. We describe how each of these attributes constrains or allows different kinds of Traversal optimizations. We characterize the applications of Treelogy both according to our structural ontology as well as by various applicationand input-dependent metrics that measure the irregularity of these applications. We then show the scalability of these applications implemented using generic frameworks for GPU, shared memory, and distributed memory systems. We also find that for certain input distributions, Barnes-Hut and 2-point correlation yield better performance when implemented with Tree types other than the "standard" Tree.
-
automatically optimizing Tree Traversal algorithms
2013Co-Authors: Milind KulkarniAbstract:Many domains in computer science, from data-mining to graphics to computational astrophysics, focus heavily on irregular applications. In contrast to regular applications, which operate over dense matrices and arrays, irregular programs manipulate and traverse complex data structures like Trees and graphs. As irregular applications operate on ever larger datasets, their performance suffers from poor locality and parallelism. Programmers are burdened with the arduous task of manually tuning such applications for better performance. Generally applicable techniques to optimize irregular applications are highly desired, yet scarce. In this dissertation, we argue that, for an important subset of irregular programs which arises in many domains, namely, Tree Traversal algorithms like Barnes-Hut, nearest neighbor and ray tracing, there exist general techniques to enhance performance. We investigate two sources of performance improvement: locality enhancement and vectorization. Furthermore we demonstrate that these techniques can be automatically applied by an optimizing compiler, relieving programmers of manual, error-prone, application-specific effort. Achieving high performance in many applications requires achieving good locality of reference. We propose two novel transformations called point blocking and Traversal splicing, inspired by the classic tiling loop transformation, and show that it can substantially enhance temporal locality in Tree Traversals. We then present a transformation framework called Tree SPLICER, that automatically applies these transformations, and uses autotuning techniques to determine appropriate parameters for the transformations. For six benchmark algorithms, we show that a combination of point blocking and Traversal splicing can deliver single-thread speedups of up to 8.71 (geometric mean: 2.48), just from better locality. Modern commodity processors support SIMD instructions, and using these instructions to process multiple Traversals at once has the potential to provide substantial performance improvements. Unfortunately Tree algorithms often feature highly diverging Traversals which inhibit efficient SIMD utilization, to the point that other, less profitable sources of vectorization must be exploited instead. We propose a dynamic reordering of Traversals based on previous behavior, based on the insight that Traversals which have behaved similarly so far are likely to behave similarly in the future, and show that this reordering can dramatically improve the SIMD utilization of diverging Traversals, close to ideal utilization. We present a transformation framework, SIMTree, which facilitates vectorization of Tree algorithms, and demonstrate speedups of up to 6.59 (geometric mean: 2.78). Furthermore our techniques can effectively SIMDize algorithms that prior, manual vectorization attempts could not.
-
automatically enhancing locality for Tree Traversals with Traversal splicing
Conference on Object-Oriented Programming Systems Languages and Applications, 2012Co-Authors: Milind KulkarniAbstract:Generally applicable techniques for improving temporal locality in irregular programs, which operate over pointer-based data structures such as Trees and graphs, are scarce. Focusing on a subset of irregular programs, namely, Tree Traversal algorithms like Barnes-Hut and nearest neighbor, previous work has proposed point blocking, a technique analogous to loop tiling in regular programs, to improve locality. However point blocking is highly dependent on point sorting, a technique to reorder points so that consecutive points will have similar Traversals. Performing this a priori sort requires an understanding of the semantics of the algorithm and hence highly application specific techniques. In this work, we propose Traversal splicing, a new, general, automatic locality optimization for irregular Tree Traversal codes, that is less sensitive to point order, and hence can deliver substantially better performance, even in the absence of semantic information. For six benchmark algorithms, we show that Traversal splicing can deliver single-thread speedups of up to 9.147 (geometric mean: 3.095) over baseline implementations, and up to 4.752 (geometric mean: 2.079) over point-blocked implementations. Further, we show that in many cases, automatically applying Traversal splicing to a baseline implementation yields performance that is better than carefully hand-optimized implementations.
-
brief announcement locality enhancing loop transformations for Tree Traversal algorithms
ACM Symposium on Parallel Algorithms and Architectures, 2011Co-Authors: Milind KulkarniAbstract:In this paper, we discuss transformations that can be applied to irregular programs that perform Tree Traversals, which can be seen as analogs of the popular regular transformations of loop tiling. We demonstrate the utility of these transformations on two Tree Traversal algorithms, the Barnes-Hut algorithm and raytracing, achieving speedups of up to 237% over the baseline implementation.
-
locality enhancing loop transformations for parallel Tree Traversal algorithms
2011Co-Authors: Milind KulkarniAbstract:Exploiting locality is critical to achieving good performance. For regular programs, which operate on dense arrays and matrices, techniques such as loop interchange and tiling have long been known to improve locality and deliver improved performance. However, there has been relatively little work investigating similar locality-improving transformations for irregular programs that operate on Trees or graphs. Often, it is not even clear that such transformations are possible. In this paper, we discuss two transformations that can be applied to irregular programs that perform graph Traversals. We show that these transformations can be seen as analogs of the popular regular transformations of loop interchange and tiling. We demonstrate the utility of these transformations on two Tree Traversal algorithms, the Barnes-Hut algorithm and raytracing, achieving speedups of up to 251% over the baseline implementation.
Benjamin A Burton - One of the best experts on this subject based on the ideXlab platform.
-
a Tree Traversal algorithm for decision problems in knot theory and 3 manifold topology
Algorithmica, 2013Co-Authors: Benjamin A Burton, Melih OzlenAbstract:In low-dimensional topology, many important decision algorithms are based on normal surface enumeration, which is a form of vertex enumeration over a high-dimensional and highly degenerate polytope. Because this enumeration is subject to extra combinatorial constraints, the only practical algorithms to date have been variants of the classical double description method. In this paper we present the first practical normal surface enumeration algorithm that breaks out of the double description paradigm. This new algorithm is based on a Tree Traversal with feasibility and domination tests, and it enjoys a number of advantages over the double description method: incremental output, significantly lower time and space complexity, and a natural suitability for parallelisation. Experimental comparisons of running times are included.
-
a Tree Traversal algorithm for decision problems in knot theory and 3 manifold topology
Algorithmica, 2013Co-Authors: Benjamin A Burton, Melih OzlenAbstract:In low-dimensional topology, many important decision algorithms are based on normal surface enumeration, which is a form of vertex enumeration over a high-dimensional and highly degenerate polytope. Because this enumeration is subject to extra combinatorial constraints, the only practical algorithms to date have been variants of the classical double description method. In this paper we present the first practical normal surface enumeration algorithm that breaks out of the double description paradigm. This new algorithm is based on a Tree Traversal with feasibility and domination tests, and it enjoys a number of advantages over the double description method: incremental output, significantly lower time and space complexity, and a natural suitability for parallelisation. Experimental comparisons of running times are included.
-
a Tree Traversal algorithm for decision problems in knot theory and 3 manifold topology
Symposium on Computational Geometry, 2011Co-Authors: Benjamin A Burton, Melih OzlenAbstract:In low-dimensional topology, many important decision algorithms are based on normal surface enumeration, which is a form of vertex enumeration over a high-dimensional and highly degenerate polytope. Because this enumeration is subject to extra combinatorial constraints, the only practical algorithms to date have been variants of the classical double description method. In this paper we present the first practical normal surface enumeration algorithm that breaks out of the double description paradigm. This new algorithm is based on a Tree Traversal with feasibility and domination tests, and it enjoys a number of advantages over the double description method: incremental output, significantly lower time and space complexity, and a natural suitability for parallelisation.
Zhengkang Zuo - One of the best experts on this subject based on the ideXlab platform.
-
non recursive algorithm derivation and formal proof of binary Tree Traversal class problems
IEEE International Conference on Software Quality Reliability and Security Companion, 2020Co-Authors: Zhengkang Zuo, Yue Fang, Qing Huang, Yunyan Liao, Yuan Wang, Changjing WangAbstract:The development of loop invariants for recursive problems of nonlinear data structures is always difficult problem in formal development. The paper studies the derivation and formal proof of binary Tree Traversal class non-recursive algorithm. The non-recursive Apla (Abstract Programming Language) algorithms of binary Tree Traversal class problems and their exact and simple loop invariants are derived. Then, the correctness of the algorithm is proved by Dijkstra-Gries standard proving technique. Finally, the PAR platform is used to automatically generate C++ code, which realizes the complete refinement process from abstract specification to concrete executable program. The results of this study point out the direction for the exploration of the loop invariant of the nonrecursive algorithm for recursive problems and have guiding significance for the derivation and formal proof of the algorithm program of the nonlinear data structure.
-
unified formal derivation and automatic verification of three binary Tree Traversal non recursive algorithms
Cluster Computing, 2016Co-Authors: Zhen You, Jinyun Xue, Zhengkang ZuoAbstract:Binary Tree Traversal algorithm can be applied in many aspects, such as information encryption, Network, operating systems, cluster computing and so on. We have already proposed a useful method to verify the correctness of algorithmic programs based on Isabelle proof assistant and Dijkstra's weakness precondition theory, and have manually derived and verified binary Tree Traversal non-recursive algorithms in our previous work. In order to ensure the security of the non-recursive algorithms, the focus of this paper is to construct a unified recurrence-relations expression about preorder, in-order, and post-order binary Tree Traversal non-recursive algorithms. The recurrence-relations expression make it easier to derive the loop invariants of three algorithms. Meanwhile, we automatically verify the correctness of three kinds of non-recursive algorithms by using a generic proof assistant Isabelle. This work realizes mechanically automatic-verification and overcomes the intricacies and weakness of manual verification, improves the verification efficiency, and ensures the trustworthiness and reliability of the algorithm program.
