Accelerating Minimum Cost Polygon Triangulation Code with the TRACO Compiler
Journal Title: Annals of Computer Science and Information Systems - Year 2018, Vol 17, Issue
Abstract
In this paper, we present automatic loop tiling and parallelization for the minimum cost polygon triangulation (MCPT) task. For this purpose, we use the authorial source-to-source TRACO compiler. MCPT is a recursive algorithm encountering each subproblem many times in different branches of its recursion tree. The most intensive computing part is a triple nested polyhedral program loop nest filling a cost table using the MCPT recursive. First, the code is tiled by means of the transitive closure of a dependence graph. TRACO allows for tiling of the innermost loop nest that is not possible by means of other closely related compilers. We tile only the two innermost loops and apply skewing to serialize the outermost one and parallelize the innermost ones. An experimental study carried out on multi-core computers demonstrates considerable speed-up of tiled code, which overcomes that obtained for code generated with the closely related PLuTo compiler based on the affine transformations framework.
Authors and Affiliations
Marek Pałkowski, Wlodzimierz Bielecki
Keywords
Related Articles
- EP ID EP568871
- DOI 10.15439/2018F8
- Views 15
- Downloads 0
The Use of Deep Learning in Speech Enhancement
Deep learning is an emerging area in current scenario. Mostly, Convolutional Neural Network (CNN) and Deep Belief Network (DBN) are used as the model in deep learning. It is termed as Deep Neural Network (DNN). The use o...
Static typing and dependency management for SOA
Several problems related to work reliability appear while building service-oriented systems. The first problem consists in lack of static typing and lack of inter-service data type checking. The second one consists in hi...
Business Process Management: Terms, Trends and Models
Business Process Management (BPM) is a subject that is becoming a growing trend in the fields of Business Administration, Engineering, Information Technology (IT), among others. Understanding the subject is a complex and...
Analysis of inter-channel dependencies in audio lossless block coding
In this paper the basics of data predictive modeling (using the method of minimization mean square error) for lossless audio compression are presented. The described research focuses on inter-channel analysis and setting...
Evolution of the BPM Lifecycle
The process lifecycle systematizes the method of implementing and managing business processes in the organization. Due to changes in the social culture and the availability of technologies, the process lifecycle are also...