การถือว่าความกระจัดกระจายเป็นพร็อพเพอร์ตี้แทนที่จะเป็นการใช้งาน (ที่น่าเบื่อ) รายละเอียดช่วยให้ตัวทำให้กระจัดกระจายของคอมไพเลอร์1 สร้างโค้ดแบบกระจัดกระจาย โดยอัตโนมัติ แนวคิดนี้ได้รับการบุกเบิกสำหรับพีชคณิตเชิงเส้นโดย [Bik96] ใน MT1 และได้รับการกำหนดรูปแบบเป็นพีชคณิตเทนเซอร์โดย [Kjolstad17,Kjolstad20] ในโปรเจ็กต์คอมไพเลอร์พีชคณิตเทนเซอร์แบบกระจัดกระจาย (TACO)
ภาษา SparseTensor รองรับแอตทริบิวต์ ประเภท การดำเนินการ และการส่งผ่านทั้งหมดที่จำเป็นในการทำให้ประเภท SparseTensor เป็นพลเมืองชั้นหนึ่งภายในโครงสร้างพื้นฐานของคอมไพเลอร์ MLIR Dialect เป็นตัวเชื่อมระหว่างการดำเนินการระดับสูงในประเภท SparseTensor กับ การดำเนินการระดับล่างในรูปแบบการจัดเก็บแบบ Sparse จริง ซึ่งประกอบด้วยตำแหน่ง พิกัด และค่า การสนับสนุนระดับล่าง อาจประกอบด้วยโค้ดที่สร้างขึ้นอย่างสมบูรณ์หรืออาจมีให้ โดยใช้ไลบรารีการสนับสนุนรันไทม์แบบกระจัดกระจายขนาดเล็ก
การใช้งาน MLIR [Biketal22] เป็นไปตาม "ทฤษฎีการทำซ้ำแบบกระจัดกระจาย" อย่างใกล้ชิด ซึ่งเป็นพื้นฐานของ TACO คอมไพเลอร์มีกฎการเขียนใหม่สำหรับนิพจน์เทนเซอร์แต่ละรายการในภาษา Linalg (สัญกรณ์ดัชนีเทนเซอร์ของ MLIR): ความกระจัดกระจายของเทนเซอร์แต่ละระดับจะระบุโดยประเภทระดับ (เช่น หนาแน่น บีบอัด เดี่ยว) และข้อกำหนดของลำดับ ในระดับต่างๆ (ดู [Chou18] เพื่อดูการอภิปรายเชิงลึกและการขยายที่เป็นไปได้สำหรับประเภทระดับเหล่านี้) สำหรับนิพจน์เทนเซอร์แต่ละรายการในอินพุต คอมไพเลอร์จะสร้างกราฟการวนซ้ำที่จัดเรียงตามโทโพโลยีซึ่งแสดงถึงลำดับของพิกัดที่เกี่ยวข้องกับระดับของเทนเซอร์แต่ละรายการก่อน ซึ่งจะช่วยให้มั่นใจได้ว่าระบบจะเข้าชมเทนเซอร์ทั้งหมดตามลำดับระดับ-พิกัดตามธรรมชาติ จากนั้น จะสร้างแลตทิซการวนซ้ำสำหรับทุกดัชนีตามลำดับโทโพโลยี จุดแต่ละจุดใน Iteration-Lattice ประกอบด้วยการเชื่อมโยงพิกัดของเทนเซอร์และ นิพจน์ (ย่อย) ของเทนเซอร์ที่ต้องได้รับการประเมินสำหรับการเชื่อมโยงนั้น ภายในแลตทิซ จุดการวนซ้ำจะเรียงตามวิธี ที่ใช้พิกัดจนหมด ดังนั้น แลตทิซการวนซ้ำเหล่านี้จึงขับเคลื่อนการสร้างโค้ดแบบกระจัดกระจายจริง ซึ่งเป็นการแมปแบบหนึ่งต่อหนึ่งที่ค่อนข้างตรงไปตรงมาระหว่างแลตทิซการวนซ้ำกับชุดค่าผสมของลูป for, ลูป while และคำสั่ง if เอาต์พุต Sparse Tensor ที่สร้างขึ้น โดยไม่ได้เริ่มต้นจะได้รับการจัดการด้วยการแทรกโดยตรง หากลูปคู่ขนานทั้งหมด อยู่ด้านนอกสุด หรือการแทรกที่ผ่าน การขยายรูปแบบการเข้าถึงแบบ 1 มิติ (หรือที่เรียกว่าพื้นที่ทํางาน) โดยอ้อม หากเป็นไปได้ [Gustavson72,Bik96,Kjolstad19]
[Bik96] Aart J.C. Bik การรองรับคอมไพเลอร์สำหรับการคำนวณเมทริกซ์แบบกระจาย วิทยานิพนธ์ระดับปริญญาเอก มหาวิทยาลัยไลเดน พฤษภาคม 1996
[Biketal22] Aart J.C. Bik, Penporn Koanantakool, Tatiana Shpeisman, Nicolas Vasilache, Bixia Zheng และ Fredrik Kjolstad การรองรับคอมไพเลอร์สำหรับการคำนวณ Sparse Tensor ใน MLIR ACM Transactions on Architecture and Code Optimization, มิถุนายน 2022 ดูที่ https://dl.acm.org/doi/10.1145/3544559
[Chou18] Stephen Chou, Fredrik Berg Kjolstad และ Saman Amarasinghe การแยกรูปแบบสำหรับคอมไพเลอร์พีชคณิตเทนเซอร์แบบกระจัดกระจาย Proceedings of the ACM on Programming Languages, October 2018.
[Chou20] Stephen Chou, Fredrik Berg Kjolstad และ Saman Amarasinghe การสร้างกิจวัตรการแปลงรูปแบบ Sparse Tensor ที่มีประสิทธิภาพโดยอัตโนมัติ Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, June, 2020.
[Gustavson72] Fred G. Gustavson เทคนิคพื้นฐานบางอย่างสำหรับการแก้ระบบสมการเชิงเส้นแบบกระจัดกระจาย ใน Sparse Matrices and Their Applications หน้า 41–52 Plenum Press, New York, 1972.
[Kjolstad17] Fredrik Berg Kjolstad, Shoaib Ashraf Kamil, Stephen Chou, David Lugato และ Saman Amarasinghe Tensor Algebra Compiler Proceedings of the ACM on Programming Languages, October 2017.
[Kjolstad19] Fredrik Berg Kjolstad, Peter Ahrens, Shoaib Ashraf Kamil และ Saman Amarasinghe Tensor Algebra Compilation with Workspaces, Proceedings of the IEEE/ACM International Symposium on Code Generation and Optimization, 2019.
[Kjolstad20] Fredrik Berg Kjolstad การคอมไพล์พีชคณิตของ Sparse Tensor วิทยานิพนธ์ระดับปริญญาเอก, MIT, กุมภาพันธ์ 2020
หากต้องการร่วมให้ข้อมูล ต่อไปนี้คือปัญหาแรกที่ดี
-
โปรดทราบว่าตอนนี้เราชอบใช้คำว่า "sparsifier" มากกว่าคำว่า "sparse compiler" ซึ่งเป็นคำศัพท์ที่ใช้กันทั่วไปเช่นกัน เพื่ออ้างอิงถึงการส่งผ่านดังกล่าวเพื่อให้เห็นชัดเจนว่าการส่งผ่าน sparsifier ไม่ใช่คอมไพเลอร์แยกต่างหาก แต่ควรเป็นส่วนหนึ่งของไปป์ไลน์คอมไพเลอร์ที่สร้างขึ้นด้วยโครงสร้างพื้นฐานของคอมไพเลอร์ MLIR ↩