Dynamic tile free scheduling for code with acyclic inter-tile dependence graphs

• Autorzy: Bielecki W. , Skotnicki P.

Identyfikatory

DOI

10.7494/csci.2017.18.2.195

• Języki publikacji: EN

Abstrakty

EN

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 that allows 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.

Słowa kluczowe

EN

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

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2017
• Tom: Vol. 18 (2)
• Strony: 195--216
• Opis fizyczny: Bibliogr. 22 poz., rys., wykr., tab.

Twórcy

autor

Bielecki W.

• West Pomeranian University of Technology, Faculty of Computer Science, Szczecin, Poland

autor

Skotnicki P.

• West Pomeranian University of Technology, Faculty of Computer Science, Szczecin, Poland

Bibliografia

• [1] Baskaran M.M., Vydyanathan N., Bondhugula U.K.R., Ramanujam J., Rountev A., Sadayappan P.: Compiler-Assisted Dynamic Scheduling for Effective Parallelization 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, ACM, 2009.
• [2] Bielecki W., Pa lkowski M.: Perfectly Nested Loop Tiling Transformations Based on the Transitive Closure of the Program Dependence Graph. In: Soft Computing in Computer and Information Science , Advances in Intelligent Systems and Computing , vol. 342, pp. 309–320, Springer International Publishing, 2015.
• [3] Bielecki W., Pa lkowski M., Klimek T.: Free Scheduling for Statement Instances of Parameterized Arbitrarily Nested Affine Loops, Parallel Computing , vol. 38(9), pp. 518–532, 2012. http://dx . doi . org/10 . 1016/j . parco . 2012 . 06 . 001 .
• [4] Darte A., Robert Y., Vivien F.: Scheduling and Automatic Parallelization , Lecture Notes in Computer Science, Birkhauser, Boston, 2000.
• [5] Feautrier P.: Some Efficient Solutions to the Affine Scheduling Problem. Part I. One-dimensional Time. In: International Journal of Parallel Programming , vol. 21(5), pp. 313–348, 1992. http://dx . doi . org/10 . 1007/BF01407835 .
• [6] Feautrier P.: Some Efficient Solutions to the Affine Scheduling Problem. Part II. Multidimensional Time. In: International Journal of Parallel Programming , vol. 21(6), pp. 389–420, 1992. http://dx . doi . org/10 . 1007/BF01379404 .
• [7] Feautrier P., Lengauer C.: Encyclopedia of Parallel Computing , chap. Polyhedron Model, pp. 1581–1592, Springer US, 2011. http://dx . doi . org/10 . 1007/978-0- 387-09766-4 502 .
• [8] Gusev M., Evans D.J.: A new matrix vector product systolic array, Journal of Parallel and Distributed Computing , vol. 22(2), pp. 346–349, 1994.
• [9] Hartono A., Baskaran M.M., Ramanujam J., Sadayappan P.: DynTile: Parametric Tiled Loop Generation for Parallel Execution on Multicore Processors. In: Proceedings of the 24th IEEE International Symposium on Parallel and Distributed Processing , pp. 1–12, 2010. http://dx . doi . org/10 . 1109/ IPDPS . 2010 . 5470459 .
• [10] 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, ACM, 1988. http://dx . doi . org/10 . 1145/73560 . 73588 .
• [11] Kelly W., Pugh W., Rosser E., Shpeisman T.: Transitive closure of infinite graphs and its applications, International Journal of Parallel Programming , vol. 24(6), pp. 579–598, 1996.
• [12] Mullapudi R.T., Bondhugula U.: Tiling for Dynamic Scheduling. In: Proceedings of the 4th International Workshop on Polyhedral Compilation Techniques , Vienna, Austria, 2014.
• [13] OpenMP Application Program Interface, Version 3.0, 2008. http:// www . openmp . org/mp-documents/spec30 . pdf [accessed 01 February 2016].
• [14] Pałkowski M., Klimek T., Bielecki W.: TRACO: An Automatic Loop Nest Parallelizer for Numerical Applications. In: Computer Science and Information Systems (FedCSIS), 2015 Federated Conference on Computer Science and Information Systems , pp. 681–686, 2015.
• [15] Pell O., Averbukh V.: Maximum performance computing with dataflow engines, Computing in Science & Engineering , vol. 14(4), pp. 98–103, 2012.
• [16] Strout M.M., Carter L., Ferrante J.: Rescheduling for Locality in Sparse Matrix Computations. In: Computational Science – ICCS 2001 , Lecture Notes in Computer Science , vol. 2073, pp. 137–146. Springer, Berlin–Heidelberg, 2001. http://dx . doi . org/10 . 1007/3-540-45545-0 \ 23 .
• [17] Strout M.M., Carter L., Ferrante J., Kreaseck B.: Sparse Tiling for Stationary Iterative Methods, International Journal of High Performance Computing Applications , vol. 18(1), pp. 95–113, 2004. http://dx . doi . org/10 . 1177/ 1094342004041294 .
• [18] The Polyhedral Benchmark suite, 2015. http://web.cse.ohio-state.edu/ ~ pouchet/software/polybench [accessed 01 February 2016].
• [19] Verdoolaege S.: isl: An Integer Set Library for the Polyhedral Model. In: Mathematical Software – ICMS 2010 , Lecture Notes in Computer Science , vol. 6327, pp. 299–302. Springer, Berlin–Heidelberg, 2010. http://dx . doi . org/10 . 1007/ 978-3-642-15582-6 \ 49 .
• [20] Verdoolaege S.: Integer Set Library: Manual, Version isl-0.16 , 2016. http://isl.gforge.inria.fr/manual.pdf [accessed 01 February 2016].
• [21] Verdoolaege S.: Presburger Formulas and Polyhedral Compilation, v0.02 . Polly Labs and KU Leuven, 2016.
• [22] Verdoolaege S., Grosser T.: Polyhedral Extraction Tool. In: Proceedings of the 2nd International Workshop on Polyhedral Compilation Techniques . Paris, France, 2012.