소개

희소성을 (지루한) 구현 세부정보가 아닌 속성으로 취급하면 컴파일러의 희소화 도구1가 희소 코드를 자동으로 생성할 수 있습니다. 이 개념은 MT1에서 [Bik96] 에 의해 선형 대수학에 도입되었으며, 희소 텐서 대수학 컴파일러 (TACO) 프로젝트에서 [Kjolstad17, Kjolstad20]에 의해 텐서 대수학으로 공식화되었습니다.

SparseTensor 다이얼렉트는 MLIR 컴파일러 인프라 내에서 희소 텐서 유형을 일급 시민으로 만드는 데 필요한 모든 속성, 유형, 작업, 패스를 지원합니다. 방언은 희소 텐서 유형의 상위 수준 작업과 위치, 좌표, 값으로 구성된 실제 희소 스토리지 스키마의 하위 수준 작업 간의 브리지를 형성합니다. 하위 수준 지원은 완전히 생성된 코드로 구성되거나 작은 스파스 런타임 지원 라이브러리를 통해 제공될 수 있습니다.

MLIR 구현[Biketal22] 은 TACO의 기반을 형성하는 '스파스 반복 이론'을 따릅니다. 컴파일러에는 Linalg 다이얼로그 (MLIR의 텐서 색인 표기법)의 각 텐서 표현식에 대한 재작성 규칙이 있습니다. 텐서의 각 수준의 희소성은 수준 유형(예: dense, compressed, singleton)과 수준의 순서 사양으로 표시됩니다 (자세한 논의와 이러한 수준 유형의 가능한 확장 프로그램은 [Chou18] 참고). 입력의 각 텐서 표현식에 대해 컴파일러는 먼저 각 텐서의 수준과 관련된 좌표 순서를 반영하는 위상적으로 정렬된 반복 그래프를 구성합니다. 이렇게 하면 모든 텐서가 자연스러운 수준-좌표 순서로 방문됩니다. 다음으로, 토폴로지 순서로 모든 색인에 대해 반복 격자가 구성됩니다. 각 반복 격자 포인트는 텐서 좌표의 결합과 해당 결합에 대해 평가해야 하는 텐서 (하위)표현식으로 구성됩니다. 격자 내에서 반복 지점은 좌표가 소진되는 방식에 따라 정렬됩니다. 따라서 이러한 반복 격자는 실제 희소 코드 생성을 유도합니다. 이는 반복 격자에서 for 루프, while 루프, if 문 조합으로의 비교적 간단한 일대일 매핑입니다. 초기화되지 않은 희소 텐서 출력은 모든 병렬 루프가 가장 바깥쪽인 경우 직접 삽입을 사용하거나, 가능한 경우 1차원 액세스 패턴 확장 (즉, 작업 공간)을 통해 간접적으로 이동하는 삽입을 사용하여 처리됩니다[Gustavson72,Bik96,Kjolstad19].

  • [Bik96] Aart J.C. Bik. 희소 행렬 계산을 위한 컴파일러 지원 PhD thesis, Leiden University, May 1996.

  • [Biketal22] Aart J.C. Bik, Penporn Koanantakool, Tatiana Shpeisman, Nicolas Vasilache, Bixia Zheng, Fredrik Kjolstad. MLIR의 희소 텐서 계산을 위한 컴파일러 지원 ACM Transactions on Architecture and Code Optimization, 2022년 6월 참고: https://dl.acm.org/doi/10.1145/3544559

  • [Chou18] Stephen Chou, Fredrik Berg Kjolstad, Saman Amarasinghe. 스파스 텐서 대수 컴파일러의 형식 추상화 Proceedings of the ACM on Programming Languages, 2018년 10월.

  • [Chou20] Stephen Chou, Fredrik Berg Kjolstad, Saman Amarasinghe. 효율적인 희소 텐서 형식 변환 루틴의 자동 생성 Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation, June, 2020.

  • [Gustavson72] Fred G. Gustavson 희소 연립 일차 방정식을 푸는 몇 가지 기본 기법입니다. In Sparse Matrices and Their Applications, pages 41–52. Plenum Press, New York, 1972.

  • [Kjolstad17] Fredrik Berg Kjolstad, Shoaib Ashraf Kamil, Stephen Chou, David Lugato, Saman Amarasinghe. 텐서 대수 컴파일러입니다. Proceedings of the ACM on Programming Languages, 2017년 10월.

  • [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. 희소 텐서 대수 컴파일 박사 학위 논문, MIT, 2020년 2월.

참여하시겠어요? 다음은 몇 가지 좋은 첫 번째 문제입니다.

  1. 스파서티 패스가 별도의 컴파일러가 아니라 MLIR 컴파일러 인프라로 빌드된 모든 컴파일러 파이프라인의 필수 부분이어야 한다는 점을 명확히 하기 위해 이제는 일반적으로 사용되는 '스파스 컴파일러' 용어보다 '스파서티'라는 용어를 선호합니다. ↩