llvm/llvm-project

Implement strategy for loop ordering choice (true compiler starter)

Open

#51.651 aberto em 25 de out. de 2021

Ver no GitHub
 (10 comments) (0 reactions) (1 assignee)C++ (10.782 forks)batch import
bugzillagood first issuemlir:tensor

Métricas do repositório

Stars
 (26.378 stars)
Métricas de merge de PR
 (Mesclagem média 1d 2h) (1.000 fundiu PRs em 30d)

Description
Bugzilla Link 52309
Version unspecified
OS Linux
CC @joker-eph

Extended Description

The sparse compiler uses a topsort to find a suitable loop ordering (following the sparse constraints always, and possibly adding in the dense constraints if this does not yield cycles). However, often we still have an ordering choice, and the way we currently go from conservative ordering to relaxed ordering can possibly be improved. The bug requests investigating and implementing a good strategy for picking a loop order.

Relevant code to start looking at:

Method computeIterationGraph() in https://github.com/llvm/llvm-project/blob/main/mlir/lib/Dialect/SparseTensor/Transforms/Sparsification.cpp

Guia do colaborador

Direção de pesquisa
Estude o método computeIterationGraph() em mlir/lib/Dialect/SparseTensor/Transforms/Sparsification.cpp para entender a ordenação atual de loops baseada em topsort. Investigue como as restrições densas são adicionadas e identifique onde há flexibilidade. Proponha e implemente uma heurística para escolher uma melhor ordem de loops.
Pilha de tecnologia
cpp
Domain
compilers
Tipo Issue
Funcionalidade
DifficultyDificuldade de implementação estimada para um novo contribuidor, de 1 para alterações muito pequenas a 5 para trabalho de nível especializado.
3
Tempo estimadoUm intervalo de tempo aproximado para um colaborador experiente investigar, implementar, testar e preparar um pull request.
1-2 dias
Status da atividadeQuão disponível o issue aparece agora: novo, ativo, obsoleto, bloqueado ou aguardando entrada do mantenedor.
Ativo
ClarityCom que clareza o issue explica a mudança esperada, os critérios de aceitação e a próxima etapa.
Claro
Prerequisites
C++Git
Simpatia para novatosUma pontuação de 1 a 100 que estima o quão acessível este issue é para colaboradores iniciantes.
60