llvm/llvm-project

Implement strategy for loop ordering choice (true compiler starter)

Open

#51.651 geöffnet am 25. Okt. 2021

Auf GitHub ansehen
 (10 Kommentare) (0 Reaktionen) (1 zugewiesene Person)C++ (10.782 Forks)batch import
bugzillagood first issuemlir:tensor

Repository-Metriken

Stars
 (26.378 Stars)
PR-Merge-Metriken
 (Durchschn. Merge 1T 2h) (1.000 gemergte PRs in 30 T)

Beschreibung
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

Contributor Guide

Research-Richtung
Untersuchen Sie die Methode computeIterationGraph() in mlir/lib/Dialect/SparseTensor/Transforms/Sparsification.cpp, um die aktuelle auf TopSort basierende Schleifenordnung zu verstehen. Ermitteln Sie, wie dichte Beschränkungen hinzugefügt werden, und identifizieren Sie Spielräume. Schlagen Sie eine Heuristik vor und implementieren Sie diese, um eine bessere Schleifenreihenfolge zu wählen.
Tech Stack
cpp
Domain
compilers
Issue Type
Funktion
SchwierigkeitGeschätzte Implementierungsschwierigkeit für neue Contributors, von 1 für sehr kleine Änderungen bis 5 für Expertenarbeit.
3
Geschätzte ZeitEin grober Zeitrahmen, um zu recherchieren, zu implementieren, zu testen und einen Pull Request vorzubereiten.
1-2 Tage
AktivitätsstatusWie verfügbar das Issue gerade wirkt: frisch, aktiv, stale, blockiert oder wartet auf Maintainer-Input.
Aktiv
KlarheitWie klar das Issue die erwartete Änderung, Akzeptanzkriterien und den nächsten Schritt erklärt.
Klar
Voraussetzungen
C++Git
EinsteigerfreundlichkeitEin Score von 1 bis 100, der schätzt, wie zugänglich dieses Issue für First-Time Contributors ist.
60