Рассмотрение разреженности как свойства, а не (утомительной) детали реализации, позволяет разреженному коду 1 компилятора автоматически генерировать разреженный код. Эта концепция была впервые использована для линейной алгебры [Bik96] в MT1 и формализована для тензорной алгебры [Kjolstad17,Kjolstad20] в проекте Sparse Tensor Algebra Compiler (TACO) .
Диалект SparseTensor поддерживает все атрибуты, типы, операции и проходы, необходимые для того, чтобы сделать типы разреженных тензоров первоклассными гражданами в инфраструктуре компилятора MLIR. Диалект образует мост между операциями высокого уровня над типами разреженных тензоров и операциями более низкого уровня над реальными схемами разреженного хранения, состоящими из позиций, координат и значений. Поддержка нижнего уровня может состоять из полностью сгенерированного кода или может предоставляться посредством небольшой разреженной библиотеки поддержки времени выполнения.
Реализация MLIR [Biketal22] близко следует «теории разреженных итераций», которая составляет основу TACO. Компилятор имеет правило перезаписи для каждого тензорного выражения на диалекте Линалг (нотация индекса тензора MLIR): разреженность каждого уровня тензора указывается типами уровней (например, плотный, сжатый, одноэлементный) и спецификацией порядок на уровнях (см. [Chou18] для более подробного обсуждения и возможных расширений этих типов уровней). Для каждого тензорного выражения на входе компилятор сначала строит топологически отсортированный граф итераций, который отражает порядок координат относительно уровней каждого тензора; это гарантирует, что все тензоры посещаются в естественном порядке координат уровня. Далее для каждого индекса строятся итерационные решетки в топологическом порядке. Каждая точка итерационной решетки состоит из объединения тензорных координат и тензорного (под)выражения, которое необходимо вычислить для этого объединения. Внутри решетки точки итерации упорядочены в соответствии со способом исчерпания координат. По существу, эти решетки итераций управляют фактической генерацией разреженного кода, относительно простым и однозначным преобразованием решеток итераций в комбинации циклов for, циклов while и операторов if. Выходные данные разреженного тензора, которые материализуются неинициализированными, обрабатываются либо прямыми вставками, если все параллельные циклы являются крайними, либо вставками, которые косвенно проходят через одномерное расширение шаблона доступа (так называемое рабочее пространство), где это возможно [Gustavson72, Bik96, Kjolstad19].
[Bik96] Аарт Дж. С. Бик. Поддержка компилятора для вычислений с разреженной матрицей. Кандидатская диссертация, Лейденский университет, май 1996 г.
[Biketal22] Аарт Дж. К. Бик, Пенпорн Коанантакул, Татьяна Шпейсман, Николас Василаке, Биксия Чжэн и Фредрик Кьолстад. Поддержка компилятора для разреженных тензорных вычислений в MLIR. Транзакции ACM по оптимизации архитектуры и кода, июнь 2022 г. См.: https://dl.acm.org/doi/10.1145/3544559.
[Chou18] Стивен Чоу, Фредрик Берг Кьолстад и Саман Амарасингхе. Абстракция формата для компиляторов разреженной тензорной алгебры. Труды ACM по языкам программирования, октябрь 2018 г.
[Chou20] Стивен Чоу, Фредрик Берг Кьолстад и Саман Амарасингхе. Автоматическая генерация эффективных процедур преобразования разреженного тензорного формата. Материалы 41-й конференции ACM SIGPLAN по разработке и реализации языков программирования, июнь 2020 г.
[Gustavson72] Фред Г. Густавсон. Некоторые основные методы решения разреженных систем линейных уравнений. В книге «Разреженные матрицы и их приложения», страницы 41–52. Пленум Пресс, Нью-Йорк, 1972.
[Кьолстад17] Фредрик Берг Кьолстад, Шоаиб Ашраф Камил, Стивен Чоу, Дэвид Лугато и Саман Амарасингхе. Компилятор тензорной алгебры. Труды ACM по языкам программирования, октябрь 2017 г.
[Кьолстад19] Фредрик Берг Кьолстад, Питер Аренс, Шоаиб Ашраф Камил и Саман Амарасингхе. Компиляция тензорной алгебры с рабочими пространствами, Труды Международного симпозиума IEEE/ACM по генерации и оптимизации кода, 2019.
[Kjolstad20] Фредрик Берг Кьёлстад. Компиляция разреженной тензорной алгебры. Кандидатская диссертация, Массачусетский технологический институт, февраль 2020 г.
Хотите внести свой вклад? Вот несколько хороших первых выпусков .
Обратите внимание, что теперь мы предпочитаем термин «разрежитель» вместо часто используемой терминологии «разреженный компилятор» для обозначения такого прохода, чтобы прояснить, что проход разрежителя не является отдельным компилятором, а должен быть неотъемлемой частью любого компилятора. конвейер, построенный с использованием инфраструктуры компилятора MLIR. ↩