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 46
- Downloads 0
Design of Intelligent PD Controller for Water Supply in Healthcare Systems
The necessity of clean environment is the major aspect in this modern age. This maintains a healthy environment. Also several trials have made with multidisciplinary researchers for development of healthy environment. Ho...
Optimizing Maintenance in Project Management by Considering HSE and Resilience Engineering
One of the most important objectives of project management is to complete the project within the specified completion date of the project. Another important objective of project is to terminate the project by minimum rat...
A Contemplating approach for Hive and Map reduce for efficient Big Data Implementation
In the reference current scenario, data is incremented exponentially and speed of data accruing at the rate of petabytes. Big data defines the available amount of data over the different media or wide communication media...
An Adaptive Approach for image adaptive watermarking using Elliptical curve cryptography (ECC)
Elliptical curve cryptography (ecc) is a public key encryption approach based on elliptic curve idea that may be used to create quicker, smaller, and greater green cryptographic keys. Ecc generates keys through the house...
Reliability Modeling of OSS Systems based on Innovation-Diffusion Theory and Imperfect Debugging
Open Source Software (OSS) has obtained widespread popularity in last few decades due to the exceptional contribution of some well established ones like Apache, Android, MySQL, LibreOffice, Linux etc. not only in the fie...