Generation of Efficient Nested Loops from Polyhedra

Quilleré, Fabien; Rajopadhye, Sanjay; Wilde, Doran
October 2000
International Journal of Parallel Programming;Oct2000, Vol. 28 Issue 5, p469
Academic Journal
Automatic parallelization in the polyhedral model is based on affine transformations from an original computation domain (iteration space) to a target space-time domain, often with a different transformation for each variable. Code generation is an often ignored step in this process that has a significant impact on the quality of the final code. It involves making a trade-off between code size and control code simplification/optimization. Previous methods of doing code generation are based on loop splitting, however they have nonoptimal behavior when working on parameterized programs. We present a general parameterized method for code generation based on dual representation of polyhedra. Our algorithm uses a simple recursion on the dimensions of the domains, and enables fine control over the tradeoff between code size and control overhead.


Related Articles

  • Improving Quicksort Performance with a Codeword Data Structure. Baer, Jean-Loup; Lin, Yi-Bing // IEEE Transactions on Software Engineering;May89, Vol. 15 Issue 5, p622 

    This paper investigates how the use of a new data structure, the codeword, can help improve the performance of quicksort when the records to be sorted are long and the keys are alphanumeric sequences of bytes. The codeword is a compact representation of a key with respect to some codeword...

  • INTEGRATING PROFILING INTO MDE COMPILERS. Aranega, Vincent; Rodrigues, A. Wendell O.; Etien, Anne; Guyomarch, Fréderic; Dekeyser, Jean-Luc // International Journal of Software Engineering & Applications;Jul2014, Vol. 5 Issue 4, p1 

    Scientific computation requires more and more performance in its algorithms. New massively parallel architectures suit well to these algorithms. They are known for offering high performance and power efficiency. Unfortunately, as parallel programming for these architectures requires a complex...

  • Code generation by model transformation: a case study in transformation modularity. Hemel, Zef; Kats, Lennart C. L.; Groenewegen, Danny M.; Visser, Eelco // Software & Systems Modeling;Jun2010, Vol. 9 Issue 3, p375 

    The realization of model-driven software development requires effective techniques for implementing code generators for domain-specific languages. This paper identifies techniques for improving separation of concerns in the implementation of generators. The core technique is code generation by...

  • Threshold Signature Scheme Based on TPM. Zhi-Hua Zhang; Si-Rong Zhang; Wen-Jin Yu; Jian-Jun Li; Bei Gong; Wei Jiang // International Journal of Communications, Network & System Scienc;Oct2011, Vol. 4 Issue 10, p622 

    For the traditional threshold signature mechanism does not considers whether the nodes which generate part signature are trusted and the traditional signature strategy doesn't do well in resisting internal attacks and external attacks and collusion attacks, so this paper presents a new threshold...

  • A New Method for Computing the Inverse Ideal in a Coordinate Ring. Basiri, `Abdolali // Proceedings of World Academy of Science: Engineering & Technolog;Dec2007, Vol. 36, p393 

    In this paper we present an efficient method for inverting an ideal in the ideal class group of a Cab curve by extending the method which is presented in [3]. More precisely we introduce a useful generator for the inverse ideal as a K[X]-module.

  • Using SCT Generator and Unity in Automatic Generation of 3D Scenes and Applications. Kvesić, Anton; Radošević, Danijel; Orehovački, Tihomir // Central European Conference on Information & Intelligent Systems;Sep2014, p312 

    This paper deals with the automatic generation of 3D scene and related source code using the SCT based generator. Compared to current ways of 3D modeling, the proposed approach is based on textual specification and code generation. Application built this way and its 3D scenes can still be edited...

  • Fast anomaly detection in hyperspectral images with RX method on heterogeneous clusters. Molero, J.; Paz, A.; Garzón, E.; Martínez, J.; Plaza, A.; García, I. // Journal of Supercomputing;Dec2011, Vol. 58 Issue 3, p411 

    Remotely sensed hyperspectral sensors provide image data containing rich information in both the spatial and the spectral domain, and this information can be used to address detection tasks in many applications. One of the most widely used and successful algorithms for anomaly detection in...

  • Adaptive parallel interval branch and bound algorithms based on their performance for multicore architectures. Sanjuan-Estrada, J.; Casado, L.; García, I. // Journal of Supercomputing;Dec2011, Vol. 58 Issue 3, p376 

    This work studies how to adapt the number of threads of a parallel Interval Branch and Bound algorithm to the available computational resources based on its current performance. Basically, a thread can create a new thread that will process part of the ancestor workload. In this way, load...

  • ALGORITHMS FOR RECOGNITION OF REGULAR PROPERTIES AND DECOMPOSITION OF RECURSIVE GRAPH FAMILIES. Borie, R.; Parker, R. Gary; Tovey, C. A. // Annals of Operations Research;1991, Vol. 33 Issue 1-4, p127 

    This paper focuses on two themes within the broad context of recursively definable graph classes. First, we generalize the series—parallel operations and establish exactly how far they can be extended subject to some consistency conditions. We show explicitly how Halin graphs are included...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics