Order Analysis for Translating NESL Programs into Efficient GPU Code

Ming Yi Yan*, Ming Hsiang Huang, Wuu Yang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


The language NESL aims to facilitate GPU programming. In order to utilize the computation power of GPUs, NESL programs must be translated into efficient low-level code for execution. We propose a new translation technique. In NESL, apply-to-each is the main construct to extract parallel computation capability of GPUs. The result of apply-to-each is a sequence of elements. In traditional translation, the order of the elements in a sequence is always preserved. However, sometimes, the order need not be preserved and hence a faster method (which may not preserve the order of elements) for calculating the sequence may be employed. We propose the order analysis to determine if the order of elements in a sequence needs to be preserved. Order analysis is based on the taint analysis. In our experiments, we obtained 8.76x speedup on average.

Original languageEnglish
Title of host publicationNew Trends in Computer Technologies and Applications - 23rd International Computer Symposium, ICS 2018, Revised Selected Papers
EditorsChuan-Yu Chang, Chien-Chou Lin, Horng-Horng Lin
PublisherSpringer Verlag
Number of pages8
ISBN (Print)9789811391897
StatePublished - 1 Jan 2019
Event23rd International Computer Symposium, ICS 2018 - Yunlin, Taiwan
Duration: 20 Dec 201822 Dec 2018

Publication series

NameCommunications in Computer and Information Science
ISSN (Print)1865-0929
ISSN (Electronic)1865-0937


Conference23rd International Computer Symposium, ICS 2018


  • GPU
  • NESL
  • Order analysis
  • Parallel computation
  • Taint analysis


Dive into the research topics of 'Order Analysis for Translating NESL Programs into Efficient GPU Code'. Together they form a unique fingerprint.

Cite this