컴파일러의 다면체(폴리헤드럴) 최적화에서 널리 쓰이는 ISL의 핵심 개념을 소개한다. 정수 집합과 관계의 표현, 간단한 조작, C 코드 생성, ISL C API 사용 예제, 그리고 MLIR의 FPL과의 상호운용 방법까지 다룬다.
Polyhedral optimization은 컴파일러에서 중첩 루프를 최적화하는 데 쓰이는 도구다. 이를 사용하는 주요 컴파일러들은 자체적으로 다면체 최적화를 구현하지만,1 다면체 최적화에 쓰이는 핵심 알고리즘을 구현한 범용 오픈 소스 C 라이브러리인 Integer Set Library (ISL)도 있다.
이 글은 ISL의 일부 기능을 개관한다. 특히 집합과 관계의 표현, 그리고 그에 대한 기본 조작에 초점을 맞춘다. 필자의 ISL 사용 목적이 MLIR과 관련되어 있어, ISL의 MLIR 포트(FAST Presburger Library, FPL)와 필자가 작성한 ISL-FPL 상호운용 계층에 대해서도 간략히 적는다. 이 글은 ISL이 사용하는 알고리즘의 세부 내용은 다루지 않는다.
이 글을 위해 작성한 모든 코드는 GitHub에 있다.
ISL의 핵심 데이터 객체는 정수 격자 위의 점들의 집합이며, 다면체 최적화의 핵심은 이러한 집합을 분석하고 조작하는 것이다. 관심 대상인 정수 집합은 매우 크거나 무한할 수 있으므로, 점들을 직접 나열하지 않고, 특정한 형태로 제한된 등식/부등식 계를 만족하는 정수점의 집합으로 간접 표현한다. 이 제한된 형태를 _준-아핀(quasi-affine) 식_이라 하고(정의는 아래에서 제시), 이를 이용한다.
다면체 최적화의 한 가지 원리는 루프 중첩의 “반복 공간(iteration space)”에 해당하는 정수 집합을 구성하는 것이다. 즉, 루프 안의 어떤 문장이 실행될 때마다 그에 해당하는 정수 격자점 하나가 존재하도록 하는 것이다. 여기서는 가장 안쪽에 단일 문장 S만 있는 “완전 중첩(perfect nest)”의 단순화된 루프 예제를 보자.
for (int i = 0; i < 100; i++) {
for (int j = 0; j < 200; j++) {
S(i, j);
}
}
S(i, j)가 실행되는 모든 쌍 (i, j)를 포함하는 정수 집합을 만들고자 한다. 보다 일반적으로 루프 중첩은 서로 다른 시작점, 상한, 스텝 크기를 가질 수 있고, S의 실행을 가드하는 if 문이 있을 수도 있다.
for (int i = 3; i < 100; i += 5) {
for (int j = 100; j > 0; j -= 2) {
if ((i + j) % 2 == 0 {
S(i, j);
}
}
}
다면체 최적화의 관찰은, 실제 코드에서 등장하는 대부분의 for 루프와 if 문이 제한된 구조를 가진다는 점이다. 루프의 경계는 상수이고 스텝 크기도 정적이고 상수인 경우가 많다(예: 보통 j *= 2나 j += i*i 같은 업데이트는 잘 쓰지 않는다). if의 조건도 대개 선형 산술에 조금 더한 정도다. 특히 바닥/천장 나눗셈과 모듈로 연산은 타일된 메모리 레이아웃 등에서 자주 쓰인다.
이것이 정수 집합을 _준-아핀 식_으로 이뤄진 등식/부등식 계로 정의하도록 제한하게 된 배경이다.
정의: _준-아핀(quasi-affine) 식_은 다음 연산들로 구성된 다변수 식이다.
MLIR 웹사이트의 BNF를 빌려 정의하면 다음과 같다.
affine-expr ::= `(` affine-expr `)`
| affine-expr `+` affine-expr
| affine-expr `-` affine-expr
| `-`? integer-literal `*` affine-expr
| affine-expr `ceildiv` integer-literal
| affine-expr `floordiv` integer-literal
| affine-expr `mod` integer-literal
| `-`affine-expr
| bare-id
| `-`? integer-literal
_프레즈버거(Presburger) 식_은 준-아핀 식과 표준 이항 비교 연산자(=, !=, <, <=, >, >=)를 포함하는 1차 논리식이다. 특히 프레즈버거 식에는 존재/전칭 양화 변수가 포함될 수 있다.
프레즈버거 집합(이 글에서는 간단히 정수 집합)은 프레즈버거 식을 만족하는 점들의 부분집합이다.
isl_cat 예제먼저 ISL을 사용해 프레즈버거 집합의 예시를 몇 가지 살펴보자.
이 글의 코드 저장소는 bazel을 사용하며 ISL 의존성이 미리 구성되어 있다. bazel(또는 bazelisk)가 설치되어 있다면, 리포를 클론하고 아래처럼 ISL을 빌드할 수 있다.
git clone git@github.com:j2kun/isl-primer.git
cd isl-primer
bazel build @isl//:isl
examples.isl 파일에는 여기서 보여줄 프레즈버거 집합 예제들이 들어 있다. 집합을 시각화하려면 Polly Labs Playground의 UI를 사용할 수 있다.2 그렇지 않다면 bazel build @isl//:isl_cat로 ISL에 예제를 통과시켜 파싱, 검증/단순화, 재출력을 할 수 있다.
bazel run @isl//:isl_cat < examples.isl
# isl_cat은 표준 입력을 읽는다. 인자 없이 실행하고 터미널에 수식을 붙여넣어도 된다.
bazel run @isl//:isl_cat
{ [i, j, a, b] : i = a + 1 and (b + j) mod 2 = 0 }
ISL은 정의 가능한 집합의 종류를 몇 가지로 나눈다. 가장 단순한 것은 _basic set_으로, 하나의 볼록 정수 다면체인 프레즈버거 집합이다. 예를 들어 다음은 삼각형을 정의한다.
{ [i,j] : 0 < i < 10 and 0 < j < 10 and i < j }
문법은 수학의 집합 생성자 표기법과 비슷하다. 중괄호 {}는 집합을, 대괄호 [] 속의 i, j는 정수 격자의 두 차원을 이름 붙이는 두 변수를, 콜론 :은 변수 정의와 식을 구분한다.
이 “기저 정수 격자”는 ISL 용어로 _공간(space)_이라고 부른다. 공간은 차원의 수와 각 차원의 이름, 그리고 전체 공간의 이름(선택적)으로 정의된다. 위의 공간에 이름을 붙이려면 여는 대괄호 앞에 기호를 쓴다.
{ A[i,j] : 0 < i < 10 and 0 < j < 10 and i < j }
공간의 이름은 루프 중첩 내의 문장을 식별하는 데 사용할 수 있다.
다음으로, ISL의 set(basic set과 대비되는 일반 set)은 서로 분리된 볼록 성분을 여러 개 갖는 프레즈버거 집합이다. 이들은 동일한 기반 공간과 연계되어 있어야 한다. 아래의 프레즈버거 집합은 삼각형과 정사각형의 합집합을 정의한다.
{ [i, j] : 0 <= i <= 10 and 0 <= j <= 10 and j > i or (6 <= i <= 9 and 0 < j <= 4) }
그다음 _union set_은 유한 개의 프레즈버거 집합의 합집합이며, 서로 다른 차원의 서로 다른 공간을 사용할 수 있다. 세미콜론으로 공간 정의를 구분한다.
{
A[i, j] : 0 <= i <= 10 and 0 <= j <= 10;
B[i, j, k] : 6 <= i <= 9 and 0 < j <= 4 and 0 <= k < 2
}
내가 이해하기로 union set의 목적은 동일한 구조(예: 같은 상위 루프를 공유하여 함께 최적화되어야 하는 문장들) 안의 두 개의 코드 문장(A와 B)을 표현하는 것이다. 다만 필자도 이 부분을 깊게 다뤄보지는 않았다.
마지막으로 위의 집합형에 대응하는 _map_이 있다. _map_은 역시 프레즈버거 집합이지만, 변수 중 일부를 도메인 변수, 나머지를 코도메인(치역) 변수(ISL에서는 range 변수라고 부름)로 구분한다. ->가 도메인과 치역을 구분하며, 각각 위에서 본 공간 형태로 정의된다.
예컨대 _basic map_은 _basic set_의 변수를 분할한 것이다.
{
[i, j] -> [a, b] : i = a + 1 and (b + j) mod 2 = 0
and 0 <= i < 10 and 0 <= j < 10
and 0 <= a < 10 and 0 <= b < 10
}
_map_은 basic map과 같지만 분리된 성분을 여러 개 가질 수 있고, _union map_은 유한 개 map의 합집합이다.
수학적으로 보면, 다면체 분석의 map은 사실 “함수”가 아니라 이항 _관계(relation)_다. 한 도메인 점이 여러 치역 점으로 “매핑”되거나 그 반대여도 아무런 제약이 없다. 관계를 쓰는 것은 더 일반적이라는 점에서 장점이다. 다만 “relation” 대신 “map”을 쓰게 된 역사적 이유로, 약간의 인지적 오버헤드를 감수해야 한다.
마지막으로 다면체 분석(ISL 포함)은 심볼릭 상수를 지원한다. 프레즈버거 집합 앞에 대괄호로 심볼 목록을 두고 ->를 붙인다.
예를 들어 아래 프레즈버거 집합은 심볼릭 상수 N을 사용해 변수 i, j의 상한을 정의한다.
[N] -> { [i, j] : 0 < i < N and j > i and 0 < j < N }
또 다른 문법으로 존재적 로컬 변수를 나타낼 수 있다. 아래 예는 로컬 변수를 사용해 도메인과 치역이 짝수-다음수 쌍(첫 원소가 짝수)로 순차적으로 짝지어지도록 하는 프레즈버거 집합이다.
{
[i] -> [j] :
exists q :
0 <= i < N
and 0 <= j < N
and i = 2*q
and j = 2*q + 1
}
첫 번째로 해볼 유의미한 작업은, 프레즈버거 집합의 점들을 순회하며 각 점마다 어떤 문장을 실행하는 C 코드를 생성하는 것이다.
이를 위해 _반복 스케줄(iteration schedule)_을 지정해야 한다. 반복 스케줄은 꽤 복잡할 수 있고, “정답”을 체계적으로 구하는 방법은(내가 아는 한) 없다. 응용에 따라 다르다. 여기서는 수면만 살짝 긁고, 어떤 변수 부분집합을 어떤 순서로 반복할지를 지정하는 가장 단순한 경우에 집중하겠다.
이 사양은 프레즈버거 집합을 맵으로 변환해 정의한다. 즉, 공간의 모든 변수를 자신이 반복하고 싶은 변수 부분집합으로 대응시키는 맵을 만든다.
위에서 본 N으로 파라미터화된 삼각형 예제의 경우,
[N] -> { [i, j] : 0 < i < N and j > i and 0 < j < N }
[i,j] 공간을 A[i, j] -> [i, j]로 바꾸면 두 변수 i, j를 그 순서로 반복하라는 뜻이 된다.
[N] -> { A[i, j] -> [i, j] : 0 < i < N and j > i and 0 < j < N }
그리고 isl_codegen을 실행한다. (아래 입력의 마지막 두 줄은 생성 코드의 고급 제어를 위한 것으로 여기서는 무시해도 된다)
bazel run @isl//:isl_codegen << EOF
[N] -> { A[i, j] -> [i, j] : 0 < i < N and j > i and 0 < j < N }
{ : }
{}
EOF
for (int c0 = 1; c0 < N - 1; c0 += 1)
for (int c1 = c0 + 1; c1 < N; c1 += 1)
A(c0, c1);
또는 반복 순서를 바꾸고 싶다면 [i, j] 대신 [j, i]로 매핑한다.
bazel run @isl//:isl_codegen << EOF
[N] -> { A[i, j] -> [j, i] : 0 < i < N and j > i and 0 < j < N }
{ : }
{}
EOF
for (int c0 = 2; c0 < N; c0 += 1)
for (int c1 = 1; c1 < c0; c1 += 1)
A(c1, c0);
제약으로 인해, 생성된 코드는 j를 2부터, i를 1부터 시작해야 함을 알아낸다. 또한 반복 순서를 바꾸면 문장 A에 전달되는 유도 변수의 순서도 바뀌는 점에 주목하라.
하나 더 예를 들어 보자. 생성된 루프 중첩에는 if 문이 포함될 수도 있고, 문장에 전달되는 최종 인자에 산술식이 들어갈 수도 있다. 이를 보여주기 위해 이 블로그의 이전 글, 대각선 데이터 패킹에서 사용한 대각선 패킹을 설명하는 정수 관계를 사용해 보겠다.
bazel run @isl//:isl_codegen << EOF
{ [i0, i1] -> [ct, slot] : (i0 - i1 + ct) mod 16 = 0 and (-i0 + slot) mod 16 = 0 and 0 <= i0 <= 9 and 0 <= i1 <= 15 and 0 <= ct <= 15 and 0 <= slot <= 1023 }
{ : }
{}
EOF
for (int c0 = 0; c0 <= 15; c0 += 1)
for (int c1 = 0; c1 <= 1023; c1 += 1)
if ((c1 + 6) % 16 >= 6)
(c1 % 16, (c0 + c1) % 16);
이후에 ISL C API를 사용해 위와 같은 코드를 생성하는 법을 보여주겠다.
ISL C API는 방대하다. 필자가 세어 보니 선언된 함수가 2만 개가 넘고, 순수 C 라이브러리라서 모양은 대체로 다음과 같다.
__isl_give isl_set *isl_map_domain(__isl_take isl_map *bmap);
isl_basic_set, isl_set, isl_union_set, isl_basic_map, isl_map, isl_union_map 타입이 있다.3 함수 이름은 isl_로 시작하고, 그다음 첫 번째 주요 인자의 타입(예: map), 그리고 수행할 동작의 설명이 뒤따른다.
즉, isl_map_domain은 isl_map을 입력으로 받아(반환 전에 해제하고) 그 맵의 도메인에 속하는 정수점 부분집합을 나타내는 isl_set 포인터를 반환한다.
ISL은 내부적으로 참조 카운팅을 하고, 각 객체는 이를 처리하는 isl_ctx 컨텍스트 객체와 연관된다. 매크로 __isl_give, __isl_take, __isl_keep(필자가 보기에는 모두 no-op)은 호출자에게 소유권 규약을 알린다. 즉, 인자의 소유권을 함수가 가져가면 __isl_take, 호출자가 유지하면 __isl_keep, 반환 포인터를 호출자가 해제해야 하면 __isl_give를 쓴다. 이런 규약이 있어도 ISL을 쓰다 보면 메모리를 누수하기 쉬우니, bazel을 --config=asan과 함께 실행하는 것을 권한다.
Hello World 예제로, 컨텍스트를 만들고 문자열에서 basic map을 파싱한 뒤, 도메인을 추출해 출력하는 C++ 프로그램을 보자.
#include "include/isl/ctx.h"
#include "include/isl/map.h"
#include "include/isl/map_type.h"
#include "include/isl/set.h"
std::string parse_map_and_extract_domain_as_string(
isl_ctx *ctx, std::string islStr) {
isl_set *domainMap = isl_map_domain(
isl_map_read_from_str(ctx, islStr.c_str()));
char *result_str = isl_set_to_str(domainMap);
std::string result(result_str);
free(result_str);
isl_set_free(domainMap);
return result;
}
그리고 이를 실행하는 간단한 바이너리:
#include "isl_api_examples.h"
#include <iostream>
#include <string>
#include "include/isl/ctx.h"
int main() {
std::string islMap;
std::cout << "Enter an ISL map: ";
std::getline(std::cin, islMap);
isl_ctx *ctx = isl_ctx_alloc();
std::string result = parse_map_and_extract_domain_as_string(ctx, islMap);
std::cout << "Result: " << result << std::endl;
isl_ctx_free(ctx);
return 0;
}
빌드 파일
load("@rules_cc//cc:cc_binary.bzl", "cc_binary")
load("@rules_cc//cc:cc_library.bzl", "cc_library")
load("@rules_cc//cc:cc_test.bzl", "cc_test")
cc_library(
name = "isl_api_examples",
srcs = ["isl_api_examples.cpp"],
hdrs = ["isl_api_examples.h"],
deps = ["@isl"],
)
cc_binary(
name = "get_domain",
srcs = ["get_domain.cpp"],
deps = [":isl_api_examples"],
)
실행 예:
$ bazel run :get_domain
Enter an ISL map: { [i] -> [j] : (-i + j) mod 7 = 0 and 0 <= i <= 20 and 0 <= j <= 20 }
Result: { [i] : 0 <= i <= 20 }
# 다음 예제에서는 j의 상한을 3으로 바꾼다.
# 이렇게 하면 추출된 도메인이, 해당하는 j가 존재하는 i의 부분집합만 포함함을 볼 수 있다.
$ bazel run :get_domain
Enter an ISL map: { [i] -> [j] : (-i + j) mod 7 = 0 and 0 <= i <= 20 and 0 <= j <= 3 }
Result: { [i] : 0 <= i <= 20 and 7*floor((-1 - i)/7) <= -4 - i }
ISL API에는 집합/맵의 합집합, 교집합 같은 기초 연산이 여럿 있지만, 흥미로워지는 지점은 맵을 합성하기 시작할 때라고 생각한다. 일반적인 두 관계의 합성에는 존재적 양화 변수를 도입해야 하며, ISL은 이를 단순화·소거해 깔끔한 표현으로 도달하는 강력한 알고리즘을 갖추고 있다.
필자의 현재 사용 사례 대부분은 메모리 레이아웃 분석이라, 예제는 “텐서가 어떤 정수 관계에 따라 메모리에 배치되어 있을 때, 프로그램에서 텐서에 가하는 변형을 원래 레이아웃과 합성해 새로운 레이아웃 기술자(descriptor)를 얻는 법”을 보여준다.
예를 들어 3차원 텐서가 있고, 벡터 레지스터 크기 16인 열-우선(column-major) 레이아웃을 설명하는 프레즈버거 관계가 있다고 하자.
{
S[i, j, k] -> [reg, lane] :
0 <= i < 32
and 0 <= j < 64
and 0 <= k < 1024
and 0 <= lane < 16
and i + j * 32 + k * 32 * 64 = 16 * reg + lane
}
이제 프로그램이 축 i와 j를 맞바꾸는 전치를 수행한다고 하자. 그 이후의 분석은 이 연산을 새로운 레이아웃에 반영해야 한다. 이는 다음 관계로 원래 레이아웃을 사전 합성(precompose) 하면 된다.
{ S[i, j, k] -> [j, i, k] }
이는 다음의 축약 표현이다.
{ S[i0, j0, k0] -> [i1, j1, k1] : i0 = j1 and i1 = j0 and k0 = k1 }
이를 ISL로 수행하기 위해, 등식/부등식의 계수가 행렬로 조직되는 내부 표현을 조금 들여다보자.
선언: 문자열에서 레이아웃을 파싱하고, 지정된 두 도메인 차원을 맞바꾸는 관계로 사전 합성한다.
std::string precompose_transposition(isl_ctx* ctx, std::string starting_layout,
int dim1, int dim2);
전체 구현과, 행별 설명은 다음과 같다.
std::string precompose_transposition(isl_ctx* ctx, std::string starting_layout,
int dim1, int dim2) {
isl_map* layout = isl_map_read_from_str(ctx, starting_layout.c_str());
isl_set* domain = isl_map_domain(isl_map_copy(layout));
isl_map* domain_map =
isl_map_from_domain_and_range(isl_set_copy(domain), domain);
isl_space* transpose_space = isl_map_get_space(domain_map);
isl_map_free(domain_map);
unsigned num_domain_vars = isl_space_dim(transpose_space, isl_dim_in);
isl_mat* eq_mat =
create_empty_constraint_matrix(transpose_space, num_domain_vars);
isl_mat* ineq_mat = create_empty_constraint_matrix(transpose_space, 0);
// 열 순서는 [domain_vars, range_vars, div_vars, symbol_vars, constant]
// 따라서 도메인 변수와 그에 대응하는 레인지 변수 사이의 오프셋은 num_domain_vars
for (int domain_var = 0; domain_var < num_domain_vars; ++domain_var) {
// 첫 번째 제약: domain_var dim1 - range_var dim2 = 0
if (domain_var == dim1) {
isl_mat_set_element_si(eq_mat, /*row=*/dim1, /*col=*/dim1, 1);
isl_mat_set_element_si(eq_mat, /*row=*/dim1,
/*col=*/num_domain_vars + dim2, -1);
continue;
}
if (domain_var == dim2) {
// 두 번째 제약: domain_var dim2 - range_var dim1 = 0
isl_mat_set_element_si(eq_mat, /*row=*/dim2, /*col=*/dim2, 1);
isl_mat_set_element_si(eq_mat, /*row=*/dim2,
/*col=*/num_domain_vars + dim1, -1);
continue;
}
// 그 외: domain_var d - range_var d = 0
isl_mat_set_element_si(eq_mat, /*row=*/domain_var, /*col=*/domain_var, 1);
isl_mat_set_element_si(eq_mat, /*row=*/domain_var,
/*col=*/num_domain_vars + domain_var, -1);
}
isl_map* transpose =
isl_map_from_basic_map(isl_basic_map_from_constraint_matrices(
transpose_space, eq_mat, ineq_mat, isl_dim_in, isl_dim_out,
isl_dim_div, isl_dim_param, isl_dim_cst));
isl_map* composed = isl_map_apply_range(transpose, layout);
char* result_str = isl_map_to_str(composed);
std::string result(result_str);
free(result_str);
isl_map_free(composed);
return result;
}
레이아웃을 파싱한 뒤 첫 단계는, 입력 레이아웃과 정확히 같은 도메인 변수를 사용하는 새 프레즈버거 맵의 기반 공간을 만드는 것이다. 대부분은 ISL API 상의 형식 작업과 메모리 관리다.
isl_set* domain = isl_map_domain(isl_map_copy(layout));
isl_map* domain_map =
isl_map_from_domain_and_range(isl_set_copy(domain), domain);
isl_space* transpose_space = isl_map_get_space(domain_map);
isl_map_free(domain_map);
다음으로 전치를 표현할 제약 행렬을 비어 있는 상태로 만든다.
isl_mat* eq_mat = create_empty_constraint_matrix(transpose_space, num_domain_vars);
isl_mat* ineq_mat = create_empty_constraint_matrix(transpose_space, 0);
이는 모든 항목을 0으로 초기화하는 도우미 함수를 사용한다.
__isl_give isl_mat* create_empty_constraint_matrix(__isl_keep isl_space* space,
unsigned num_constraints) {
unsigned num_in = isl_space_dim(space, isl_dim_in);
unsigned num_out = isl_space_dim(space, isl_dim_out);
unsigned num_div = isl_space_dim(space, isl_dim_div);
unsigned num_param = isl_space_dim(space, isl_dim_param);
// 열의 배치는 [domain_vars, range_vars, div_vars, symbol_vars, constant]
unsigned num_cols = num_in + num_out + num_div + num_param + 1;
isl_mat* mat =
isl_mat_alloc(isl_space_get_ctx(space), num_constraints, num_cols);
for (int i = 0; i < isl_mat_rows(mat); ++i)
for (int j = 0; j < isl_mat_cols(mat); ++j)
isl_mat_set_element_si(mat, /*row=*/i, /*col=*/j, 0);
return mat;
}
이제 실제 제약을, 개별 계수를 설정해 정의한다. 목표하는 관계는 다음과 같다.
{ S[i0, j0, k0] -> [i1, j1, k1] : i0 = j1 and i1 = j0 and k0 = k1 }
따라서 (도메인, 치역) 변수쌍마다 하나의 제약이 필요하다. 모든 도메인 변수를 순회하면서, 전치되는 두 차원에 대해서는 다음과 같은 특별 제약을 둔다.
// 첫 제약: domain_var dim1 - range_var dim2 = 0
isl_mat_set_element_si(eq_mat, /*row=*/0, /*col=*/dim1, 1);
isl_mat_set_element_si(eq_mat, /*row=*/0, /*col=*/num_domain_vars + dim2, -1);
// 둘째 제약: domain_var dim2 - range_var dim1 = 0
isl_mat_set_element_si(eq_mat, /*row=*/1, /*col=*/dim2, 1);
isl_mat_set_element_si(eq_mat, /*row=*/1, /*col=*/num_domain_vars + dim1, -1);
그리고 기본적으로는 도메인 변수와 치역 변수를 서로 같게 묶는 제약을 둔다.
// 그 외: domain_var d - range_var d = 0
isl_mat_set_element_si(eq_mat, /*row=*/domain_var, /*col=*/domain_var, 1);
isl_mat_set_element_si(eq_mat, /*row=*/domain_var,
/*col=*/num_domain_vars + domain_var, -1);
제약 행렬은 행마다 하나의 제약, 열마다 하나의 변수에 대응하며, 각 행은 변수와 계수의 _선형 결합_이고 마지막 열이 상수항을 나타낸다.
마지막으로 제약 행렬에서 관계를 만들고, 그 결과에 대해 apply_range를 호출한다. 이때 열과 변수의 의도된 순서(예: isl_dim_in에 도메인 변수가 먼저, 다음 isl_dim_out에 치역 변수)가 무엇인지 지정할 수 있다.
isl_map* transpose =
isl_map_from_basic_map(isl_basic_map_from_constraint_matrices(
transpose_space, eq_mat, ineq_mat, isl_dim_in, isl_dim_out,
isl_dim_div, isl_dim_param, isl_dim_cst));
isl_map* composed = isl_map_apply_range(transpose, layout);
apply_range는 첫 번째 인자의 치역을 두 번째 인자의 도메인과 합성해 합성 관계를 만든다. 나머지 코드는 결과를 문자열로 변환하고 메모리를 해제하는 부분이다.
코드는 다소 지저분하지만, ISL이 내부적으로 어떻게 동작하는지 이해하는 데 핵심적인 질문을 드러낸다. “변수의 _선형 결합_으로 제약을 표현하는 방식이, 어떻게 모듈로 산술과 바닥/천장 나눗셈을 표현할 수 있는가?” 그 답은 div 차원에 있다. ISL에서 div 차원은 항상 존재적으로 양화되는 특수 변수이며, 나눗셈의 중간 계산 결과를 표현하는 데 사용된다.
예를 들어 { [i] : 5 <= i } 같은 단순한 집합의 제약 행렬을 출력해 보면(필자는 basic_set의 원시 제약 행렬을 덤프하는 바이너리와 API 예제를 포함했다), 다음과 같이 나온다.
bazel run dump_constraints << EOF
{ [i] : i = 5 }
EOF
Equality Matrix:
[[1,-5]]
유일한 등식은 i - 5 = 0을 의미한다. 첫 번째 열은 i의 계수, 마지막 열은 상수항을 나타낸다.
하지만 { [i] : (i % 2) = 1 }처럼 모듈로 산술이 있는 좀 더 복잡한 시스템을 덤프하면 다음과 같은 등식 제약을 얻는다.
bazel run dump_constraints << EOF
{ [i] : (i % 2) = 1 }
EOF
Equality Matrix:
[[-1,2,-1]]
마지막 열은 여전히 상수항, 끝에서 두 번째 열은 정수 나눗셈의 결과를 나타내는 새로운 “div” 변수다. 이 변수는 존재적으로 양화되므로, 식은 사실 다음과 같다.
∃q: -i + 2q - 1 = 0 (즉 i = 2q - 1).
이를 정리하고 양변을 2로 나눈 나머지를 취하면 원래 식을 복원할 수 있다. ISL은 바닥/천장 나눗셈에서도 유사한 요령을 쓴다. 모든 준-아핀 식은 이런 연산들을 순수 선형 등식/부등식의 계로 환원할 수 있고, 중간 나눗셈 결과는 존재적으로 양화된 변수로 표현된다.
수동으로 div/mod 변수를 제약 시스템에 추가하는 일은 다소 번거롭다. ISL에는 include/isl/aff.h에 준-아핀 식을 구성하는 도우미 API가 있지만, 지면 관계상 이 API 탐구는 다음 글로 미루겠다.4
다음으로 유용한 디버깅 도구를 보여주겠다. basic map이나 basic set의 모든 점을 열거하고 덤프하는 것이다.
핵심 API는 isl_set_foreach_point로, 콜백 함수 포인터를 받아 집합의 각 점마다 이를 호출한다. 예제에서는 콜백이 (도메인/치역 분해를 알고 있는) 구조체에 점을 추가하고, 하나의 점을 도메인 점과 치역 점으로 분리할 수 있게 한다.
struct PointPairCollector {
using Point = std::vector<int64_t>;
std::vector<std::pair<Point, Point>> points;
int domain_dims;
int range_dims;
PointPairCollector(int domain_dims, int range_dims)
: domain_dims(domain_dims), range_dims(range_dims) {}
};
그리고 이를 채우는 함수 포인터:
isl_stat pointPairCallback(__isl_take isl_point* pnt, void* user) {
PointPairCollector* collector = static_cast<PointPairCollector*>(user);
isl_space* space = isl_point_get_space(pnt);
isl_space_free(space);
std::vector<int64_t> domainPoint(collector->domain_dims);
std::vector<int64_t> rangePoint(collector->range_dims);
// 도메인 좌표 추출
for (int i = 0; i < collector->domain_dims; i++) {
isl_val* coord = isl_point_get_coordinate_val(pnt, isl_dim_set, i);
if (isl_val_is_int(coord)) {
domainPoint[i] = isl_val_get_num_si(coord);
}
isl_val_free(coord);
}
// 치역 좌표 추출
for (int i = 0; i < collector->range_dims; i++) {
isl_val* coord = isl_point_get_coordinate_val(pnt, isl_dim_set,
collector->domain_dims + i);
if (isl_val_is_int(coord)) {
rangePoint[i] = isl_val_get_num_si(coord);
}
isl_val_free(coord);
}
collector->points.emplace_back(domainPoint, rangePoint);
isl_point_free(pnt);
return isl_stat_ok;
}
이제 이를 결합하는 루틴:
void enumeratePoints(isl_basic_map *bmap,
PointPairCollector& collector) {
isl_set* set = isl_set_from_basic_set(isl_basic_map_wrap(bmap));
isl_set_foreach_point(set, &pointPairCallback, &collector);
isl_set_free(set);
}
이제 C 문자열 형태의 루프 중첩 코드를 생성하는 방법을 C API로 보여주겠다.5
std::string generate_loop_nest_as_c_str(isl_basic_map *bmap) {
auto *ctx = isl_basic_map_get_ctx(bmap);
isl_union_map *schedule =
isl_union_map_from_basic_map(isl_basic_map_copy(bmap));
// 컨텍스트와 옵션은 의도적으로 비워 둔다.
isl_set *context = isl_set_universe(isl_space_params_alloc(ctx, 0));
isl_union_map *options = isl_union_map_empty(isl_space_params_alloc(ctx, 0));
// AST 생성
isl_ast_build *build = isl_ast_build_from_context(context);
build = isl_ast_build_set_options(build, options);
isl_ast_node *tree = isl_ast_build_node_from_schedule_map(build, schedule);
isl_ast_build_free(build);
char *cStr = isl_ast_node_to_C_str(tree);
std::string actual = std::string(cStr);
free(cStr);
isl_ast_node_free(tree);
// 다중 행 문자열과 비교하기 쉽도록 맨 앞에 개행을 추가한다.
return actual.insert(0, "\n");
}
핵심 API는 isl_ast_build_node_from_schedule_map이다. 이 함수는 [domain] -> [range]가 앞서 언급한 반복 순서를 지정하는 맵을 입력으로 받아, isl_ast_node를 구성한다. isl_ast_node는 루프, if 문 등 전통적인 AST 노드들을 갖는 구조다. isl_ast_node_to_C_str는 AST를 C 문자열로 바꾸는 도우미이며, 원한다면 AST를 직접 순회해, 예를 들어 MLIR 루프 중첩을 생성할 수도 있다. HEIR 프로젝트에서 이를 어떻게 하는지 여기에서 볼 수 있다.
MLIR 컴파일러 프로젝트에는 ISL의 핵심 알고리즘 일부를 자체 구현한 Fast Presburger Library(FPL)가 있다. 하지만 아직 미완성이라, 코드 생성이나 고급 단순화 알고리즘 등 ISL의 몇몇 기능은 HEIR 프로젝트의 우리 팀이 필수적으로 사용하고 있다.
그래서 FPL이 ISL의 보다 완전한 포트가 될 때까지, 우리는 MLIR과 ISL 사이의 상호운용 계층을 추가했다.6 이 계층은 MLIR의 IntegerRelation과 ISL의 basic_map 사이를 변환하며, 두 형식의 내부 제약 행렬을 그대로 복사하는 방식으로 구현된다. 위에서 고수준 ISL API를 피한 이유 중 하나가 바로 이 변환 계층을 더 이해하기 쉽게 만들고자 했기 때문이다.
이 프로젝트 리포에 MLIR을 의존성으로 추가하면 빌드 시간이 크게 늘어나 이득이 적다. 대신 코드로 연결하고, 핵심 조각을 아래에 보인다.
두 라이브러리 모두 내부적으로 등식/부등식 제약 행렬을 같은 방식으로 표현하므로, 변환은 단순히 행렬을 서로 복사해 옮기면 된다.
basic_map을 IntegerRelation으로 변환하기:
presburger::IntegerRelation convertBasicMapToRelation(
isl_basic_map* bmap) {
// IntegerRelation의 변수 저장 순서는 다음과 같다.
// Domain, Range, Symbols, Locals, Constant
// ISL에서는 다음에 대응한다.
// In, Out, Param, Div, Cst
isl_mat* eqMat = isl_basic_map_equalities_matrix(
bmap, isl_dim_in, isl_dim_out, isl_dim_param, isl_dim_div, isl_dim_cst);
isl_mat* ineqMat = isl_basic_map_inequalities_matrix(
bmap, isl_dim_in, isl_dim_out, isl_dim_param, isl_dim_div, isl_dim_cst);
PresburgerSpace fplSpace = PresburgerSpace::getRelationSpace(
/*numDomain=*/isl_basic_map_dim(bmap, isl_dim_in),
/*numRange=*/isl_basic_map_dim(bmap, isl_dim_out),
/*numSymbols=*/isl_basic_map_dim(bmap, isl_dim_param),
/*numLocals=*/isl_basic_map_dim(bmap, isl_dim_div));
IntegerRelation result(
/*numReservedInequalities=*/isl_mat_rows(ineqMat),
/*numReservedEqualities=*/isl_mat_rows(eqMat),
/*numReservedCols=*/isl_mat_cols(eqMat), fplSpace);
populateConstraints(result, eqMat, /*eq=*/true);
populateConstraints(result, ineqMat, /*eq=*/false);
isl_mat_free(eqMat);
isl_mat_free(ineqMat);
return result;
}
이후 populateConstraints가 계수들을 하나하나 복사한다.
void populateConstraints(IntegerRelation& rel, __isl_keep isl_mat* mat,
bool eq) {
unsigned numRows = isl_mat_rows(mat);
unsigned numCols = isl_mat_cols(mat);
for (unsigned i = 0; i < numRows; i++) {
SmallVector<int64_t, 8> row;
for (unsigned j = 0; j < numCols; j++) {
isl_val* val = isl_mat_get_element_val(mat, i, j);
row.push_back(isl_val_get_num_si(val));
isl_val_free(val);
}
if (eq) {
rel.addEquality(row);
} else {
rel.addInequality(row);
}
}
}
반대 방향 변환도 유사하다.
__isl_give isl_mat* createConstraintRows(__isl_keep isl_ctx* ctx,
const IntegerRelation& rel,
bool isEq) {
unsigned numRows = isEq ? rel.getNumEqualities() : rel.getNumInequalities();
unsigned numDimVars = rel.getNumDimVars();
unsigned numLocalVars = rel.getNumLocalVars();
unsigned numSymbolVars = rel.getNumSymbolVars();
unsigned numCols = rel.getNumCols();
isl_mat* mat = isl_mat_alloc(ctx, numRows, numCols);
for (unsigned i = 0; i < numRows; i++) {
auto row = isEq ? rel.getEquality(i) : rel.getInequality(i);
// 차원 변수는 같은 위치에 둔다.
for (unsigned j = 0; j < numDimVars; j++)
mat = isl_mat_set_element_si(mat, i, j, (int64_t)row[j]);
// 로컬 변수를 심볼보다 앞에 둔다.
for (unsigned j = 0; j < numLocalVars; j++)
mat = isl_mat_set_element_si(
mat, i, j + numDimVars, (int64_t)row[j + numDimVars + numSymbolVars]);
// 심볼은 그 뒤에 둔다.
for (unsigned j = 0; j < numSymbolVars; j++)
mat = isl_mat_set_element_si(mat, i, j + numDimVars + numLocalVars,
(int64_t)row[j + numDimVars]);
// 마지막으로 상수항.
mat = isl_mat_set_element_si(
mat, i, numCols - 1, (int64_t)row[numCols - 1]);
}
return mat;
}
__isl_give isl_basic_map* convertRelationToBasicMap(const IntegerRelation& rel,
__isl_keep isl_ctx* ctx) {
isl_mat* eqMat = createConstraintRows(ctx, rel, /*isEq=*/true);
isl_mat* ineqMat = createConstraintRows(ctx, rel, /*isEq=*/false);
isl_space* space =
isl_space_alloc(ctx, rel.getNumSymbolVars(), rel.getNumDomainVars(),
rel.getNumRangeVars());
return isl_basic_map_from_constraint_matrices(
space, eqMat, ineqMat, isl_dim_in, isl_dim_out, isl_dim_div,
isl_dim_param, isl_dim_cst);
}
후속 글에서는 다면체 최적화, 특히 ISL의 기반이 되는 핵심 알고리즘 일부를 더 자세히 살펴보고자 한다. 이들 알고리즘의 상당수는 심플렉스 유사 기법, 고모리 컷, 푸리에-모츠킨 소거, 기저 축소 등 볼록 최적화의 심도 있는 이론을 활용한다. ISL 레퍼런스 문서의 2장은 그 단면을 엿볼 수 있게 해준다.
이 글 초안에 피드백을 주신 Asra Ali께 감사드린다.
사이트가 꽤 오래되어 로딩이 오래 걸리고(PyPy.js 사용), 렌더링에 몇 가지 작은 버그가 있는 듯하지만, 그래도 집합을 시각화하기에는 괜찮다.↩︎
이 라이브러리가 얼마나 난해한지 보여주는 또 다른 예로, 이 구조체들의 정의를 찾는 것조차 쉽지 않다. 필자가 보기에는 결국 모두 isl_union_map의 특수화로 정의된 듯하며, isl_union_map_private.h에 정의되어 있다.↩︎
MLIR의 FPL에도 고수준 구조와 아핀 식을 IntegerRelation으로 변환하는 AffineExpr API가 있고, 나눗셈/모듈로 제약을 위해 로컬 변수를 추가하는 도우미들도 있다.↩︎
프레즈버거 집합에서 코드를 생성하는 과정을 문헌에서는 가끔 “스캐닝(scanning)”이라고 부른다.↩︎
우리는 이를 Enzyme-JAX 프로젝트에서 차용해 적응시켰다.↩︎