Garbage collection abstractions for high-level GPU languages

Jonathan Van der Cruysse
Persbericht

Nieuw onderzoek belooft efficiënter computergebruik

De computers, tablets, telefoons en devices die onze dag kleuren, bevatten doorgaans twee belangrijke chips. De eerste echte chip, die we vandaag nog altijd gebruiken, was de CPU (Central Processing Unit), die door zijn architectuur heel specifiek geschikt is voor het razendsnel uitvoeren van verschillende berekeningen na elkaar. De vele miljoenen verschillende computerprogramma’s die de wereld kent, zijn bijna uitsluitend geschreven op maat van deze CPU, die sinds de jaren ‘50 en ‘60 steeds gesofisticeerder werd en waarvoor we ook de lat van onze programmeertechnieken telkens weer hoger wisten te leggen.

In de jaren ‘70 en ‘80, toen de eerste games op het toneel verschenen, ontstond de behoefte om de kwaliteit van onze beeldweergave te verbeteren. Het inkleuren van de haast ontelbare pixels op een modern beeldscherm – het scherm van de nieuwe iPhone heeft er meer dan drie miljoen – voor toepassingen zoals games waarbij elke pixel tot zestig keer per seconde verandert, vergt een geheel andere rekenwijze dan wat die CPU ons kan bieden. De jaren ‘80 zagen de geboorte van de GPU (Graphics Processing Unit) die het inkleuren van de vele pixels niet hoeft na elkaar te berekenen, maar allemaal tegelijk en aan duizelingwekkende snelheden.

Van deze twee geheel verschillende chips verwachten we dus een totaal verschillende taak, waarvoor we ze ook een totaal verschillende architectuur meegeven. De evolutie van het programmeren en het uitvoeren van computerprogramma’s richt zich sinds vele decennia op de CPU, waarvoor een opbod van steeds betere en meer spitsvondige technieken ons elke dag opnieuw blijft verbazen.

Diezelfde evolutie zagen we tot enkele jaren geleden niet of amper bij de GPU, die eigenlijk maar één ware opdracht heeft: een blitse en levensechte weergave van beeldmateriaal op het scherm. Verbeteringen aan de GPU richtten zich dan ook voornamelijk op scherpere, meer kleurechte en snellere grafische beleving van wat onze computers en smartphones voor ons uitvoeren.

Toch zou een aantal specifieke computertoepassingen zeker gebaat zijn met GPUs als we die op dezelfde elegante manier zouden kunnen programmeren als een CPU. Daarbij denken we bijvoorbeeld aan weersvoorspelling, artificiële intelligentie, de interpretatie van medische scans en andere toepassingen waar tegelijkertijd gigantische hoeveelheden data worden verrekend. Die kerngedachte noemen we general-purpose GPU programming.

Een van de belangrijkste uitdagingen bij het programmeren van een CPU, is het geheugenbeheer. De hoeveelheid beschikbaar geheugen van elk device is immers begrensd. Bij het uitvoeren van een computerprogramma gaat onze chip telkens pakketjes geheugen lenen om daar bewerkingen op uit te voeren. Wanneer deze klaar zijn, wordt dat geheugen opnieuw ter beschikking gesteld voor volgende berekeningen. Het spreekt voor zich dat we het geleende geheugen niet langer dan strikt noodzakelijk bijhouden voor we het weer loslaten.

Bij het schrijven van een goed computerprogramma is het memory management soms zo complex dat het menselijk brein van de programmeur amper zelf nog kan inschatten op welk moment welke pakketjes geheugen moeten worden terugbezorgd. Om ons bij die complexe taak te ondersteunen ontwikkelden we doorheen de jaren een aantal programmeertools die deze berekening overnamen van de programmeur. De meest gebruikte en in het algemeen meest efficiënte daarvan is de zogenaamde garbage collector.

Hetzelfde concept werd tot dusver niet toegepast bij het programmeren van GPUs. Aangezien de miljoenen berekeningen door de aard van het GPU-beestje zelf gelijktijdig gebeuren, is het gereserveerde geheugen snel terug beschikbaar voor volgende bewerkingen. Dat ligt natuurlijk anders wanneer we de eerder primitieve GPU willen gaan gebruiken voor het uitvoeren van “echte” computerprogramma’s, zeker voor complexe berekeningen zoals in de voorbeelden die we net aanhaalden.

Zou het niet mooi zijn als we ook voor de GPU een garbage collector konden ontwikkelen? Het was nog nooit eerder geprobeerd en daarom een prachtige challenge voor een masterproef.

Bijkomende uitdaging: de GPU is er niet voor uitgerust om zijn eigen geheugen te managen. Heel kort door de bocht zou je kunnen stellen dat onze GPU een kleuter is die razendsnel kan rekenen, maar hij leerde nog niet zelf lezen. Daarom bestaat de oplossing (bij de huidige generatie van GPUs) hierin dat we hem een beroep laten doen op zijn grote CPU-broer om zijn geheugen te beheren. Alleen door een complexe interactie tussen de twee chips en de beschikbare geheugenbronnen, kunnen we ervoor zorgen dat het ontlenen van stukjes geheugen aan de GPU en het terugbezorgen van gebruikt geheugen kan verlopen terwijl de GPU zijn rekenwerk verricht, en niet langer uitsluitend daarvoor of daarna. Dat betekent dat we bij ruimere toepassing van dit principe geavanceerde programma’s zouden kunnen draaien op een grafische chip, die tot vandaag slechts zeer rudimentair programmeerwerk toelaat.

Hiervoor stelden we aan de GPU en de CPU onder meer een gedeeld communicatiekanaal ter beschikking waarmee de GPU kan signaleren wanneer de garbage collector moet worden ingezet. Metingen tonen aan dat hierdoor niet alleen gemakkelijker complex kan worden geprogrammeerd op GPU-niveau, maar dat de berekeningen ook op zijn minst even snel verlopen.

Deze nieuwe techniek toont aan dat het perfect mogelijk is om onderdelen van zowat alle moderne computerprogramma’s die vandaag uitsluitend lopen op CPUs, toe te vertrouwen aan de GPU. Daardoor worden ze als tandem een stuk productiever, wat de rekenkracht van toekomstige devices ten goede kan komen. De bevindingen van dit onderzoek verdienen zeker aandacht bij het uittekenen van nieuwe GPU-ontwerpen. Vrij eenvoudige ingrepen op dat niveau zouden immers toelaten de garbage collection aan boord te nemen van de GPU zelf, zonder de complexe interactie die we hier nodig hadden om het principe aan te tonen.

Zullen deze bevindingen onze wereld veranderen? Niet rechtstreeks, maar voor de eerste keer werd hier aangetoond dat we veelgebruikte programmeertalen zoals Java of C# gewoon kunnen laten draaien op GPUs. Dit kan ons toelaten om zelfs met bestaande hardwaretechnologie efficiënter en dus energieefficiëntier en milieuvriendelijker te werken. Studies voorspellen dat datacenters (denk maar aan Google, Facebook, etc.) tegen 2025 een vijfde van het energiegebruik in de hele wereld zullen vertegenwoordigen. Wat op een computer slechts enkele percenten verschil maakt betekent daarom op wereldschaal een gigantische energiewinst.

Bibliografie

[1] Abadi, M., Barham, P., Chen, J., Chen, Z., Davis, A., Dean, J., Devin, M., Ghemawat, S., Irving, G., Isard, M., et al. Tensorflow: A system for large-scale machine learning. In 12th USENIX Symposium on Operating Systems Design and Implementation (OSDI 16) (2016), pp. 265–283.
[2] Abhinav, and Nasre, R. FastCollect: offloading generational garbage collection to integrated GPUs. In International Conference on Compilers, Architectures, and Sythesis of Embedded Systems (CASES) (2016), IEEE, pp. 1–10.
[3] Adinets, A. Parallelism. Adaptive Parallel Computation with CUDA. Dynamic NVIDIA Developer Blog, https://devblogs.nvidia.com/introduction-cuda-dynamic-parallelism/ (May 2014). Accessed on June 5, 2019.
[4] Adinets, A. CUDA Dynamic Parallelism API and Principles. NVIDIA Developer Blog, https://devblogs.nvidia.com/cuda-dynamic-parallelism-api-principles/ (May 2014). Accessed on June 5, 2019.
[5] Adinetz, A. V., and Pleiter, D. Halloc: a high-throughput dynamic memory allocator for GPGPU architectures. In GPU Technology Conference (GTC) (2014), vol. 152.
[6] Agesen, O. GC points in a threaded environment.
[7] Appel, A. W. Garbage collection can be faster than stack allocation. Information Processing Letters 25, 4 (1987), 275–279.
[8] Appel, A. W. Simple generational garbage collection and fast allocation. Software: Practice and Experience 19, 2 (1989), 171–183.
[9] Attanasio, C. R., Bacon, D. F., Cocchi, A., and Smith, S. A comparative evaluation of parallel garbage collector implementations. In International Workshop on Languages and Compilers for Parallel Computing (2001), Springer, pp. 177–192.
[10] Baker, J., Cunei, A., Kalibera, T., Pizlo, F., and Vitek, J. Accurate garbage collection in uncooperative environments revisited. Concurrency and Computation: Practice and Experience 21, 12 (2009), 1572–1606.
[11] Baker Jr, H. G. List processing in real time on a serial computer. Communications of the ACM 21, 4 (1978), 280–294.
[12] Besard, T. Dynamic parallelism. https://github.com/JuliaGPU/CUDAnative.jl/pull/362, May 2019. Accessed on June 5, 2019.
[13] Besard, T., Churavy, V., Edelman, A., and De Sutter, B. Rapid software prototyping for heterogeneous and distributed platforms. Advances in Software Engineering (2019).
[14] Besard, T., and Foket, C. Benchmark suite for heterogeneous computing infrastructures. https://github.com/JuliaParallel/rodinia. Accessed on May 8, 2019.
[15] Besard, T., Foket, C., and De Sutter, B. Effective extensible programming: unleashing Julia on GPUs. IEEE Transactions on Parallel and Distributed Systems 30, 4 (2019), 827–841.
[16] Bezanson, J., Edelman, A., Karpinski, S., and Shah, V. B. Julia: A fresh approach to numerical computing. SIAM review 59, 1 (2017), 65–98.
[17] Bezanson, J., Karpinski, S., Shah, V. B., and Edelman, A. Julia: A fast dynamic language for technical computing. arXiv preprint arXiv:1209.5145 (2012).
[18] Blackburn, S. M., and McKinley, K. S. Ulterior reference counting: Fast garbage collection without a long wait. In ACM SIGPLAN Notices (2003), vol. 38, ACM, pp. 344–358.
[19] Boehm, H.-J., and Weiser, M. Garbage collection in an uncooperative environment. Software: Practice and Experience 18, 9 (1988), 807–820.
[20] Catanzaro, B., Garland, M., and Keutzer, K. Copperhead: compiling an embedded data parallel language. In Symposium on Principles and practice of parallel programming (PPoPP’11) (2011), pp. 47–56.
[21] Che, S., Boyer, M., Meng, J., Tarjan, D., Sheaffer, J. W., Lee, S.-H., and Skadron, K. Rodinia: A benchmark suite for heterogeneous computing. In 2009 IEEE international symposium on workload characterization (IISWC) (2009), IEEE, pp. 44–54.
[22] Chen, J., and Revels, J. Robust benchmarking in noisy environments. arXiv preprint arXiv:1608.04295 (2016).
[23] Churavy, V., Wilcox, L. C., Kozdon, J. E., and Ramadhan, A. GPUifyLoops.jl: Support for writing loop-based code that executes both on CPU and GPU. https://juliagpu.gitlab.io/GPUifyLoops.jl/, March 2019. Accessed on May 31, 2019.
[24] Colburn, T., and Shute, G. Abstraction in computer science. Minds and Machines 17, 2 (2007), 169–184.
[25] Corporation, I. Intel® CoreTM i7-6700K Processor. https://ark.intel.com/content/www/us/en/ark/products/88195/intel-core-i…, 2015. Accessed on June 12, 2019.
[26] Cytron, R., Ferrante, J., Rosen, B. K., Wegman, M. N., and Zadeck, F. K. Efficiently computing static single assignment form and the control dependence graph. ACM Transactions on Programming Languages and Systems (TOPLAS) 13, 4 (1991), 451–490.
[27] Dawson, J. L. Improved effectiveness from a real time lisp garbage collector. In Proceedings of the 1982 ACM symposium on LISP and functional programming (1982), ACM, pp. 159–167.
[28] Durant, L., Giroux, O., Harris, M., and Stam, N. Inside Volta: The world’s most advanced data center GPU. NVIDIA Developer Blog, https://devblogs.nvidia.com/inside-volta (May 2017). Accessed on May 24, 2019.
[29] Ecma International. Common Language Infrastructure (CLI). June 2012.
[30] Edelman, A. Julia: A fresh approach to parallel programming. In 2015 IEEE International Parallel and Distributed Processing Symposium (2015), IEEE, pp. 517–517.
[31] Fischer, K., Churavy, V., Hatherly, M., Hildebrand, M., Zhou, M., Karpinski, S., Besard, T., Yu, Y., and Arslan, A. Working with LLVM. https://github.com/JuliaLang/julia/blob/master/doc/src/devdocs/llvm.md, August 2018. Accessed on June 2, 2019.
[32] Fischer, K., Yu, Y., Besard, T., Nash, J., Arslan, A., Vettorel, D., Churavy, V., and Zhou, M. LLVM late GC lowering. https://github.com/JuliaLang/julia/blob/master/src/llvm-late-gc-lowerin…, May 2019. Accessed on June 2, 2019.
[33] Fumero, J. J., Remmelg, T., Steuwer, M., and Dubach, C. Runtime Code Generation and Data Management for Heterogeneous Computing in Java. In Proceedings of the Principles and Practices of Programming on The Java Platform - PPPJ ’15 (New York, New York, USA, 2015), ACM Press, pp. 16–26.
[34] Fumero, J. J., Steuwer, M., and Dubach, C. A Composable Array Function Interface for Heterogeneous Computing in Java. In Proceedings of ACM SIGPLAN International Workshop on Libraries, Languages, and Compilers for Array Programming - ARRAY’14 (2014), pp. 44–49.
[35] Fung, W. W., and Aamodt, T. M. Thread block compaction for efficient SIMT control flow. In 2011 IEEE 17th International Symposium on High Performance Computer Architecture (2011), IEEE, pp. 25–36.
[36] Garcı́a, C. G., Espada, J. P., Bustelo, B. C. P. G., and Lovelle, J. M. C. Swift vs. Objective-C: A new programming language. IJIMAI 3, 3 (2015), 74–81.
[37] GCC developers. Using the GNU Compiler Collection (GCC): Labels as Values. https://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html. Accessed on June 4, 2019.
[38] Govett, M. W., Middlecoff, J., and Henderson, T. Running the NIM next-generation weather model on GPUs. In Proceedings of the 2010 10th IEEE/ACM International Conference on Cluster, Cloud and Grid Computing (2010), IEEE Computer Society, pp. 792–796.
[39] Griffith, A. GCC: the complete reference. McGraw-Hill, Inc., 2002.
[40] Harris, M. Unified Memory for CUDA Beginners. NVIDIA Developer Blog, https://devblogs.nvidia.com/unified-memory-cuda-beginners/ (June 2017). Accessed on June 4, 2019.
[41] Henderson, F. Accurate garbage collection in an uncooperative environment. In ACM SIGPLAN Notices (2002), vol. 38, ACM, pp. 150–156.
[42] Homm, F., Kaempchen, N., Ota, J., and Burschka, D. Efficient occupancy grid computation on the gpu with lidar and radar for road boundary detection. In 2010 IEEE Intelligent Vehicles Symposium (2010), IEEE, pp. 1006–1013.
[43] Huang, X., Rodrigues, C. I., Jones, S., Buck, I., and Hwu, W.-m. Xmalloc: A scalable lock-free dynamic memory allocator for many-core machines. In Proceedings of the 2010 10th IEEE International Conference on Computer and Information
Technology (2010), IEEE, pp. 1134–1139.
[44] Introducing Julia contributors. Introducing Julia: Arrays and tuples. https://en.wikibooks.org/wiki/Introducing_Julia/Arrays_and_tuples, February 2019. Accessed on June 11, 2019.
[45] Julia contributors. Julia micro-benchmarks. https://julialang.org/benchmarks/. Accessed on April 23, 2019.
[46] Julia contributors. Working with LLVM. https://docs.julialang.org/en/v1/devdocs/llvm/index.html#Representation…, August 2018. Accessed on November 2, 2018.
[47] Kiczales, G. Towards a new model of abstraction in software engineering. In Proceedings of the 1991 International Workshop on Object Orientation in Operating Systems (1991), IEEE, pp. 127–128.
[48] Kramer, J. Is abstraction the key to computing? Communications of the ACM 50, 4 (2007), 36–42.
[49] Köplinger, A., Turaev, M., and Hasitzka, A. Generational GC. https://www.mono-project.com/docs/advanced/garbage-collector/sgen/, February 2019. Accessed on June 1, 2019.
[50] Lattner, C., and Adve, V. LLVM: a compilation framework for lifelong program analysis & transformation. In Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization (2004), IEEE
Computer Society, p. 75.
[51] LDC Developers. LLVM-based D Compiler.
https://github.com/ldc-developers/ldc. Accessed on May 8, 2019.
[52] Lee, V. W., Kim, C., Chhugani, J., Deisher, M., Kim, D., Nguyen, A. D., Satish, N., Smelyanskiy, M., Chennupaty, S., Hammarlund, P., et al. Debunking the 100× GPU vs. CPU myth: an evaluation of throughput computing on CPU and GPU. ACM SIGARCH computer architecture news 38, 3 (2010), 451–460.
[53] LLVM project. LLVM language reference manual. http://llvm.org/docs/LangRef.html, April 2019. Accessed on May 1, 2019.
[54] Maas, M., Reames, P., Morlan, J., Asanović, K., Joseph, A. D., and Kubiatowicz, J. GPUs as an opportunity for offloading garbage collection. In ACM SIGPLAN Notices (2012), vol. 47, ACM, pp. 25–36.
[55] Nickolls, J., Buck, I., and Garland, M. Scalable parallel programming. In 2008 IEEE Hot Chips 20 Symposium (HCS) (2008), IEEE, pp. 40–53.
[56] Nuseibeh, B., and Easterbrook, S. Requirements engineering: a roadmap. In Proceedings of the Conference on the Future of Software Engineering (2000), ACM, pp. 35–46.
[57] Nvidia. CUDA C programming guide v10.1. Nvidia Corporation, March 2019.
[58] Nvidia. Parallel Thread Execution ISA v6.4. Nvidia Corporation, March 2019.
[59] NVIDIA Corporation. GeForce GTX 970: Specifications. https://www.geforce.com/hardware/desktop-gpus/geforce-gtx-970/specifica…, 2014. Accessed on June 12, 2019.
[60] Owens, J. D., Houston, M., Luebke, D., Green, S., Stone, J. E., and Phillips, J. C. GPU computing. Proceedings of the IEEE 96, 5 (2008).
[61] Pohl, K. Requirements engineering: fundamentals, principles, and techniques. Springer Publishing Company, Incorporated, 2010.
[62] Pratt-Szeliga, P. C., Fawcett, J. W., and Welch, R. D. Rootbeer: Seamlessly using GPUs from Java. In High Performance Computing and Communication & 2012 IEEE 9th International Conference on Embedded Software and Systems (HPCC-ICESS), 2012 IEEE 14th International Conference on (2012), IEEE, pp. 375–380.
[63] Pratx, G., and Xing, L. GPU computing in medical physics: a review. Medical physics 38, 5 (2011), 2685–2697.
[64] Reames, P. Status of Garbage Collection with Statepoints in LLVM. http://lists.llvm.org/pipermail/llvm-dev/2016-March/096360.html, March 2016. Accessed on November 2, 2018.
[65] Revels, J., Arslan, A., Ahrens, P., Adams, L., Herriman, J., Goerz, M., Johnson, S. G., and Mauro. BenchmarkTools manual. https://github.com/JuliaCI/BenchmarkTools.jl/blob/master/doc/manual.md, November 2018. Accessed on June 10, 2019.
[66] Rhodin, H. A PTX code generator for LLVM. Bachelor’s thesis, Saarland University, Saarbrücken, Germany, October 2010.
[67] Romero, M., and Urra, R. CUDA Overview. http://cuda.ce.rit.edu/cuda_overview/cuda_overview.htm. Accessed on May 27, 2019.
[68] Sanders, J., and Kandrot, E. CUDA by Example: An Introduction to General-Purpose GPU Programming. Addison-Wesley Professional, 2010.
[69] Sobalvarro, P. A Lifetime-Based Garbage Collector for LISP Systems on General-Purpose Computers. Tech. rep., Massachusetts Institute of Technology, Cambridge Artificial Intelligence Lab, 1988.
[70] Steinberger, M., Kenzel, M., Kainz, B., and Schmalstieg, D. ScatterAlloc: Massively parallel dynamic memory allocation for the GPU. In 2012 Innovative Parallel Computing (InPar) (2012), IEEE, pp. 1–10.
[71] Stuart, J. A., Cox, M., and Owens, J. D. GPU-to-CPU callbacks. In European Conference on Parallel Processing (2010), Springer, pp. 365–372.
[72] TachyonicClock42, and Besard, T. CUDA debugger API. https:
//devtalk.nvidia.com/default/topic/1030648/cuda-programming-and-performance/cuda-debugger-api/, March 2019. Accessed on June 5, 2019.
[73] Terei, D. A., and Chakravarty, M. M. An LLVM backend for GHC. In ACM Sigplan Notices (2010), vol. 45, ACM, pp. 109–120.
[74] Vallée-Rai, R., Co, P., Gagnon, E., Hendren, L., Lam, P., and Sundaresan, V. Soot: A Java bytecode optimization framework. In CASCON First Decade High Impact Papers (2010), IBM Corp., pp. 214–224.
[75] Van Lamsweerde, A. Goal-oriented requirements engineering: A guided tour. In Proceedings of the Fifth IEEE International Symposium on Requirements Engineering (2001), IEEE, pp. 249–262.
[76] Veldema, R., and Philippsen, M. Iterative data-parallel mark&sweep on a GPU. In ACM SIGPLAN Notices (2011), vol. 46, ACM, pp. 1–10.
[77] Verroken, H. Contextual language abstractions for low-level GPGPU programming in Julia. Master’s thesis, Ghent University, June 2018.
[78] Veselỳ, J., Basu, A., Bhattacharjee, A., Loh, G., Oskin, M., and Reinhardt, S. K. GPU System Calls. arXiv preprint arXiv:1705.06965 (2017).
[79] Vuduc, R., Chandramowlishwaran, A., Choi, J., Guney, M., and Shringarpure, A. On the limits of GPU acceleration. In Proceedings of the 2nd USENIX conference on Hot topics in parallelism (2010), vol. 13.
[80] Wajnerman, J. Garbage collector. https://crystal-lang.org/2013/12/05/garbage-collector.html, December 2013. Accessed on June 1, 2019.
[81] Wenzel, M., Turn, N., Schonning, N., Mabee, D., Petrusha, R., B, M., Kotas, J., A, A., xaviex, Jones, M., Ciechan, M., Alan, Latham, L., and tompratt AQ. Fundamentals of garbage collection. https://github.com/dotnet/docs/blob/master/docs/standard/garbage-collec…, May
2019. Accessed on June 1, 2019.
[82] Wilson, P. R. Uniprocessor garbage collection techniques. In International Workshop on Memory Management (1992), Springer, pp. 1–42.
[83] Wilson, P. R., Johnstone, M. S., Neely, M., and Boles, D. Dynamic storage allocation: A survey and critical review. In International Workshop on Memory Management (1995), Springer, pp. 1–116.
[84] Wu, X., Koslowski, A., and Thiel, W. Semiempirical quantum chemical calculations accelerated on a hybrid multicore CPU–GPU computing platform. Journal of chemical theory and computation 8, 7 (2012), 2272–2281.
[85] Zhang, J., You, S., and Gruenwald, L. Indexing large-scale raster geospatial data using massively parallel GPGPU computing. In Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems (2010), ACM, pp. 450–453.

Universiteit of Hogeschool
Master of Science in Computer Science Engineering
Publicatiejaar
2019
Promotor(en)
Bjorn De Sutter
Kernwoorden
Share this on: