Hàm thuần trong C: Một từ khóa nhỏ cho tự động song song hóa

Tim Süß1, Lars Nagel2, Marc-André Vef3, André Brinkmann3, Dustin Feld4, Thomas Soddemann4
1Department of Applied Computer Science, Fulda University of Applied Sciences, Fulda, Germany
2Department of Computer Science, Loughborough University, Leicestershire, UK
3Zentrum für Datenverarbeitung, Johannes Gutenberg University Mainz, Mainz, Germany
4Department of High Performance Computing, Fraunhofer SCAI, Sankt Augustin, Germany

Tóm tắt

Nhu cầu thực thi tác vụ song song đã gia tăng đều đặn trong những năm gần đây do các nhà sản xuất chủ yếu cải thiện hiệu suất bộ vi xử lý bằng cách tăng số lõi được lắp đặt thay vì tăng tần số của bộ xử lý. Để tận dụng tiềm năng này, một kỹ thuật thiết yếu để tăng cường tính song song của một chương trình là song song hóa các vòng lặp. Một số công cụ tự động song song hóa vòng lặp đã được phát triển trong quá khứ như PluTo. giới hạn chính của những công cụ này là các vòng lặp phải có thể phân tích tĩnh, điều này cản trở việc gọi hàm bên trong các vòng lặp. Trong bài viết này, chúng tôi trình bày một mở rộng tưởng chừng đơn giản cho ngôn ngữ lập trình C, đánh dấu các hàm không có hiệu ứng phụ. Các hàm này sau đó có thể bị bỏ qua khi công cụ song song hóa tự động kiểm tra khả năng song song của các vòng lặp. Chúng tôi đã tích hợp phương pháp này vào chuỗi công cụ biên dịch GCC và đánh giá nó bằng cách chạy một số ứng dụng thực tế. Các thí nghiệm của chúng tôi cho thấy rằng mở rộng của C giúp xác định thêm cơ hội song song hóa và do đó, tăng cường đáng kể hiệu suất của các ứng dụng.

Từ khóa

#tự động song song hóa #hàm thuần #ngôn ngữ lập trình C #hiệu suất #vòng lặp

Tài liệu tham khảo

Hennessy, J.L., Patterson, D.A.: A new golden age for computer architecture. Commun. ACM 62(2), 48–60 (2019). https://doi.org/10.1145/3282307 Dagum, L., Menon, R.: Openmp: an industry-standard API for shared-memory programming. IEEE Comput. Sci. Eng. 5(1), 46–55 (1998) The OpenACC Application Program Interface. Version 2.5 (2012). http://www.openacc-standard.org/ Leiserson, C.E.: The cilk++ concurrency platform. In: Proceedings of the 46th Annual Design Automation Conference, DAC ’09, pp. 522–527 (2009) SILKAN: HPC project. Par4All automatic parallelization (2012). http://www.par4all.org Amini, M., Ancourt, C., Coelho, F., Creusillet, B., Guelton, S., Irigoin, F., Jouvelot, P., Keryell, R., Villalon, P.: PIPS is not (just) polyhedral software adding GPU code generation in PIPS. In: First Int. Workshop on Polyhedral Compilation Techniques (IMPACT 2011) in Conjonction with CGO 2011 (2011) Bondhugula, U., Ramanujam, J., Sadayappan, P.: Pluto: a practical and fully automatic polyhedral parallelizer and locality optimizer. Tech. Rep. OSU-CISRC-10/07-TR70, The Ohio State University (2007) Verdoolaege, S., Juega, J.C., Cohen, A., Gómez, J.I., Tenllado, C., Catthoor, F.: Polyhedral parallel code generation for CUDA. ACM Trans. Archit. Code Optim. 9(4), 1–23 (2013). https://doi.org/10.1145/2400682.2400713. (Selected for presentation at the HiPEAC 2013 Conf) Feld, D., Soddemann, T., Jünger, M., Mallach, S.: Facilitate SIMD-code-generation in the polyhedral model by hardware-aware automatic code-transformation. In: Größliger, A., Pouchet, L.N. (eds.) Proceedings of the 3rd International Workshop on Polyhedral Compilation Techniques, pp. 45–54 (2013) Feld, D., Soddemann, T., Jünger, M., Mallach, S.: Hardware-aware automatic code-transformation to support compilers in exploiting the multi-level parallel potential of modern cpus. In: Proceedings of the 2015 International Workshop on Code Optimisation for Multi and Many Cores, COSMIC ’15, San Francisco Bay Area, 8 Feb 2015, pp. 2:1–2:10 (2015). https://doi.org/10.1145/2723772.2723776 Strout, M.M., Georg, G., Olschanowsky, C.: Set and relation manipulation for the sparse polyhedral framework. In: Kasahara, H., Kimura, K. (eds.) Languages and Compilers for Parallel Computing: 25th International Workshop, LCPC 2012, pp. 61–75 (2013) Bastoul, C., Cohen, A., Girbal, S., Sharma, S., Temam, O.: Putting polyhedral loop transformations to work. In: 16th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2003, pp. 209–225 (2003) Petersen, L., Orchard, D., Glew, N.: Automatic simd vectorization for haskell. SIGPLAN Not. 48(9), 25–36 (2013) Marlow, S., Peyton Jones, S., Singh, S.: Runtime support for multicore haskell. SIGPLAN Not. 44(9), 65–78 (2009) Gill, A., Runciman, C.: Haskell program coverage. In: Proceedings of the ACM SIGPLAN Workshop on Haskell Workshop, Haskell ’07, pp. 1–12 (2007) Corporation, I.: Intel Fortran language reference. Document number: 253261-002 (2001) Numrich, R.W., Reid, J.: Co-arrays in the next fortran standard. SIGPLAN Fortran Forum 24(2), 4–17 (2005) Shterenlikht, A., Margetts, L., Cebamanos, L., Henty, D.: Fortran 2008 coarrays. SIGPLAN Fortran Forum 34(1), 10–30 (2015) ARM compiler toolchain compiler reference—compiler-specific features (2015). http://infocenter.arm.com/help/topic/com.arm.doc.dui0491c/CHDFIJAE.html Kennedy, K., Koelbel, C., Zima, H.: The rise and fall of high performance fortran. Commun. ACM 54(11), 74–82 (2011) Bondhugula, U., Hartono, A., Ramanujam, J., Sadayappan, P.: A practical automatic polyhedral parallelizer and locality optimizer. In: Proceedings of the ACM SIGPLAN 2008 Conference on Programming Language Design and Implementation (PLDI), pp. 101–113 (2008) Dave, C., Bae, H., Min, S.J., Lee, S., Eigenmann, R., Midkiff, S.: Cetus: a source-to-source compiler infrastructure for multicores. Computer 42(12), 36–42 (2009). https://doi.org/10.1109/MC.2009.385 Schordan, M., Quinlan, D.J.: A source-to-source architecture for user-defined optimizations. In: JMLC, pp. 214–223 (2003) Bastoul, C.: Extracting polyhedral representation from high level languages. LRI, Paris-Sud University, Tech. rep. (2008) Bastoul, C.: Openscop: a specification and a library for data exchange in polyhedral compilation tools. Paris-Sud University, France, Tech. rep. (2011) Bastoul, C.: Generating loops for scanning polyhedra. Tech. Rep. 2002/23, PRiSM, Versailles University (2002) Verdoolaege, S.: isl: an integer set library for the polyhedral model. In: Fukuda, K., van der Hoeven, J., Joswig, M., Takayama, N. (eds.) Lecture Notes in Computer Science, pp. 299–302 (2010). https://doi.org/10.1007/978-3-642-15582-6_49. https://lirias.kuleuven.be/handle/123456789/270231 Polylib–a library of polyhedral functions. (1012). http://www.irisa.fr/polylib/ Feautrier, P., Collard, J., Bastoul, C.: Solving systems of affine (in)equalities. PRiSM, Versailles University, Tech. rep. (2002) Grosser, T., Zheng, H., Aloor, R., Simbürger, A., Grösslinger, A., Pouchet, L.N.: Polly-polyhedral optimization in LLVM. In: First International Workshop on Polyhedral Compilation Techniques (IMPACT’11) (2011) Feautrier, P.: Some efficient solutions to the affine scheduling problem: I. One-dimensional time. Int. J. Parallel Program. 21, 313–348 (1992). https://doi.org/10.1007/BF01407835 Girbal, S., Vasilache, N., Bastoul, C., Cohen, A., Parello, D., Sigler, M., Temam, O.: Semi-automatic composition of loop transformations for deep parallelism and memory hierarchies. Int. J. Parallel Program. 34, 261–317 (2006) Griebl, M.: Automatic Parallelization of Loop Programs for Distributed Memory Architectures. University Passau, Habilitation (2004) Bondhugula, U., Hartono, A., Ramanujam, J., Sadayappan, P.: A practical automatic polyhedral parallelizer and locality optimizer. In: Proc. 2008 ACM SIGPLAN Conf. on Programming Language Design and Implementation, PLDI ’08, pp. 101–113. ACM (2008) Xue, J.: Loop Tiling for Parallelism. Kluwer Int. Series in Engineering and Computer Science. Kluwer Academic, New York (2000) Heintze, N., Tardieu, O.: Ultra-fast aliasing analysis using CLA: A million lines of c code in a second. In: Proceedings of the ACM SIGPLAN 2001 Conference on Programming Language Design and Implementation, PLDI ’01, pp. 254–263 (2001) Xu, Z., Kremenek, T., Zhang, J.: Leveraging Applications of Formal Methods, Verification, and Validation: 4th International Symposium on Leveraging Applications, ISoLA 2010, chap. A Memory Model for Static Analysis of C Programs, pp. 535–548 (2010) Gad, R., Süß, T., Brinkmann, A.: Compiler driven automatic kernel context migration for heterogeneous computing. In: 34th International Conference on Distributed Computing Systems (ICDCS) (2014) Kraus, J., Förster, M., Brandes, T., Soddemann, T.: Using lama for efficient amg on hybrid clusters. Comput. Sci. R&D 28(2–3), 211–220 (2013) Wang, Y., Xue, Y., Li, Y., Guang, J., Mei, L., Xu, H., Ai, J.: Prior knowledge-supported aerosol optical depth retrieval over land surfaces at 500 m spatial resolution with modis data. Int. J. Remote Sens. 33(3), 674–691 (2012). https://doi.org/10.1080/01431161.2011.577832 Liu, J., Feld, D., Xue, Y., Garcke, J., Soddemann, T.: Multicore processors and graphics processing unit accelerators for parallel retrieval of aerosol optical depth from satellite data: implementation, performance, and energy efficiency. IEEE J. Sel. Top. Appl. Earth Observ. Remote Sens. 8(5), 2306–2317 (2015). https://doi.org/10.1109/JSTARS.2015.2438893 Stallman, R.M., DeveloperCommunity, G.: Using the GNU Compiler Collection: A GNU Manual for GCC Version 4.4.7. CreateSpace, Paramount, CA (2009)