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 19
- Downloads 0
Developing keyword spotting method for the Polish language
The paper presents the application of unsupervised method to word detection in recorded speech for the spoken Polish language. The method utilizes similarity measure between analyzed speech and a pattern synthesized from...
Importance of Search Engine Marketing in the Digital World
Object tracking is one of the vital fields of computer vision that detects the moving object from a video sequence. Internet has changed the world to global village. Due to improved connectivity and increase in data usag...
Unintended effects of dependencies in source code on the flexibility of IT in organizations
This study links business requirements and adaptability of existing software systems. Organizations expect flexibility of IT with regard to business requirements. We hypothesize that the flexibility of business requireme...
Assertional Reasoning for Concurrent and Communicating BPEL-like Programs
This paper studies verification of programs similar to BPEL4WS (BPEL), the latter being a de facto standard for the web services composition and orchestration. Traditionally, in verification of concurrent and distributed...
Detection of Arrhythmia using Neural Network
There is an increase in cardio logical patients all over the world due to change in modern life style. It forces the medical researchers to search for smart devices that can diagnosis and predict the onset of cardiac pro...