search

llvm / llvm-project

The LLVM Project is a collection of modular and reusable compiler and toolchain technologies.
http://llvm.org
Other
27.7k stars 11.4k forks source link

Implement strategy for loop ordering choice (true compiler starter) #51651

Open aartbik opened 2 years ago

aartbik commented 2 years ago
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

aartbik commented 2 years ago

assigned to @aartbik

Johan511 commented 1 year ago

Hi, has there been any progress made on this issue? Is there is scholarly work I could look into for a better strategy for picking loop order.

aartbik commented 1 year ago

Changes have been made to computeIterationGraph() to deal with some very obvious performance issues, but no foundational approach yet that picks the right order given the computation (parallel/reduction loops) and sparsity properties of the tensor operands (dense, sparse, what kind of sparse).

PeimingLiu commented 1 year ago

Also, see https://reviews.llvm.org/D144932 as a our recent attempt.

streichgeorg commented 1 year ago

I tried to improve this a bit in https://reviews.llvm.org/D150061

llvmbot commented 1 year ago

Hi!

This issue may be a good introductory issue for people new to working on LLVM. If you would like to work on this issue, your first steps are:

1) Assign the issue to you. 2) Fix the issue locally. 3) Run the test suite locally. 3.1) Remember that the subdirectories under test/ create fine-grained testing targets, so you can e.g. use make check-clang-ast to only run Clang's AST tests. 4) Create a git commit 5) Run git clang-format HEAD~1 to format your changes. 6) Submit the patch to Phabricator. 6.1) Detailed instructions can be found here

For more instructions on how to submit a patch to LLVM, see our documentation.

If you have any further questions about this issue, don't hesitate to ask via a comment on this Github issue.

@llvm/issue-subscribers-good-first-issue