Dynamic Tile Free Scheduling for Code with Acyclic Inter-Tile Dependence Graphs

Włodzimierz Bielecki; Piotr Adam Skotnicki

doi:10.7494/csci.2017.18.2.195

Authors

Włodzimierz Bielecki West Pomeranian University of Technology in Szczecin
Piotr Adam Skotnicki West Pomeranian University of Technology in Szczecin http://orcid.org/0000-0001-9105-911X

DOI:

https://doi.org/10.7494/csci.2017.18.2.195

Keywords:

optimizing compilers, tiling, task scheduling, parallel computing, dependence graph, data locality

Abstract

Free scheduling is a task ordering technique under which instructions are executed
as soon as their operands become available. Coarsening the grain of
computations under the free schedule, by means of using groups of loop nest
statement instances (tiles) in place of single statement instances, increases the
locality of data accesses and reduces the number of synchronization events, and
as a consequence improves program performance. The paper presents an approach
for code generation allowing for the free schedule for tiles of arbitrarily
nested affine loops at run-time. The scope of the applicability of the introduced
algorithms is limited to tiled loop nests whose inter-tile dependence graphs are
cycle-free. The approach is based on the Polyhedral Model. Results of experiments
with the PolyBench benchmark suite, demonstrating significant tiled
code speed-up, are discussed.

Downloads

Download data is not yet available.

References

Baskaran M.M., Vydyanathan N., Bondhugula U.K.R., Ramanujam J., Rountev A., Sadayappan P.: Compiler-assisted Dynamic Scheduling for Effective Par- allelization of Loop Nests on Multicore Processors. In: Proceedings of the 14th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’09, pp. 219–228. 2009. ISBN 978-1-60558-397-6.

Bielecki W., Pa lkowski M.: Perfectly Nested Loop Tiling Transformations Based on the Transitive Closure of the Program Dependence Graph. In: Soft Comput- ing in Computer and Information Science, Advances in Intelligent Systems and Computing, vol. 342, pp. 309–320. 2015.

Bielecki W., Pa lkowski M., Klimek T.: Free Scheduling for Statement Instances of Parameterized Arbitrarily Nested Affine Loops. In: Parallel Comput., vol. 38(9), pp. 518–532, 2012. ISSN 0167-8191.

Darte A., Robert Y., Vivien F.: Scheduling and Automatic Parallelization. Lec- ture Notes in Computer Science. Birkhauser, 2000.

Feautrier P.: Some Efficient Solutions to the Affine Scheduling Problem. Part I. One-dimensional Time. In: Int. J. Parallel Programming, vol. 21(5), pp. 313–348, 1992. ISSN 0885-7458.

Feautrier P.: Some Efficient Solutions to the Affine Scheduling Problem. Part II. Multidimensional Time. In: Int. J. Parallel Programming, vol. 21(6), pp. 389–420, 1992. ISSN 0885-7458.

Feautrier P., Lengauer C.: Encyclopedia of Parallel Computing, chap. Polyhedron Model, pp. 1581–1592. Springer US, 2011.

Hartono A., Baskaran M.M., Ramanujam J., Sadayappan P.: DynTile: Para- metric Tiled Loop Generation for Parallel Execution on Multicore Processors. In: Proceedings of the 24th IEEE International Symposium on Parallel and Dis- tributed Processing, pp. 1–12. 2010.

Irigoin F., Triolet R.: Supernode Partitioning. In: Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL ’88, pp. 319–329. 1988. ISBN 0-89791-252-7.

Kelly W., Pugh W., Rosser E., Shpeisman T.: Transitive closure of infinite graphs and its applications. In: Int. J. Parallel Programming, vol. 24(6), pp. 579–598, 1996. ISSN 0885-7458.

Mullapudi R.T., Bondhugula U.: Tiling for Dynamic Scheduling. In: Proceedings of the 4th International Workshop on Polyhedral Compilation Techniques. Vienna, Austria, 2014.

OpenMP Application Program Interface, Version 3.0, 2008. URL http://www. openmp.org/mp-documents/spec30.pdf. Accessed 01 February 2016.

Palkowski M., Klimek T., Bielecki W.: TRACO: An Automatic Loop Nest Par- allelizer for Numerical Applications. In: Computer Science and Information Sys- tems (FedCSIS), 2015 Federated Conference on Computer Science and Informa- tion Systems, pp. 681–686. 2015.

The Polyhedral Benchmark suite, 2015. URL http://web.cse.ohio-state. edu/~pouchet/software/polybench. Accessed 01 February 2016.

Strout M.M., Carter L., Ferrante J.: Rescheduling for Locality in Sparse Ma- trix Computations. In: Computational Science – ICCS 2001, Lecture Notes in Computer Science, vol. 2073, pp. 137–146. Springer Berlin Heidelberg, 2001.

Strout M.M., Carter L., Ferrante J., Kreaseck B.: Sparse Tiling for Stationary Iterative Methods. In: Int. J. High Perform. Comput. Appl., vol. 18(1), pp. 95–113, 2004.

Verdoolaege S.: isl: An Integer Set Library for the Polyhedral Model. In: Math- ematical Software – ICMS 2010, Lecture Notes in Computer Science, vol. 6327, pp. 299–302. Springer Berlin Heidelberg, 2010. ISBN 978-3-642-15581-9.

Verdoolaege S.: Integer Set Library: Manual, Version isl-0.16, 2016. URL http: //isl.gforge.inria.fr/manual.pdf. Accessed 01 February 2016.

Verdoolaege S.: Presburger Formulas and Polyhedral Compilation, v0.02. Polly Labs and KU Leuven, 2016.

Verdoolaege S., Grosser T.: Polyhedral Extraction Tool. In: Proceedings of the 2nd International Workshop on Polyhedral Compilation Techniques. Paris, France, 2012.