New-pipeline: Performance of fusion analysis

Aperta
  • Qualcosa non va?
#585 0 commenti 0 reazioni 0 assegnatari Vedi su GitHub

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
5/5
Tempo stimato
Più di una settimana
Idoneità per principianti
25/100
Tipo di issue
Bug
Chiarezza
Abbastanza chiara
Stato di attività
Attiva
Stack tecnologico
haskell
Ambito
performance

Direzione di ricerca

Start by reading the new-pipeline fusion implementation and how it builds and solves the ILP with CBC; the issue does not name specific files or tests. Use the radixsort nofib test as the performance case, and compare solver options or approaches described here. Done means fusion performance is improved and the radixsort test is enabled again.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

In the new-pipeline, fusion uses an ILP (MIP) to find the best way to fuse the program. The ILP is solved using CBC. However, CBC is very slow on some programs. This includes the radixsort test in our nofib test suite. We should thus optimize fusion.

Possible solutions include:

  • Switch to HiGHS (if HiGHS is faster than CBC on our ILP instances)
  • Implement a custom constraint solver and optimize using domain knowledge (see https://github.com/ivogabe/accelerate/pull/31 for initial work in this direction)
  • Settle with approximations from CBC: give CBC a timeout and let it return the best-known solution it found so far. Downside: solution becomes non-deterministic, and this fails if no solution was found before the timeout.
  • Instruct CBC to use multiple cores. This does not give sufficient speedup, but would be a small quick win. CBC can run with multiple cores, but if I remember correctly, Haskell-MIP cannot parse the result as CBC prints a message that it is using multiple cores (should be easy to fix though).
  • Disable in-place updates. This is not a real solution, since we really want to have in-place updates, but the ILP got a lot more complex due to the addition of in-place updates.

The radixsort test is temporarily disabled until this issue is fixed (See c6e328906f77affe2d6e9d6d1a64ba2542ada7d8). We should enable the test again when this issue is resolved.

Lingua principale
Haskell
Stelle
1k
Fork
138
Nessuna PR unita negli ultimi 30g

Preparare l'ambiente

  • Nessun Dockerfile né file Docker Compose
  • Ha un modello di pull request
  • Nessuna guida per i contributori

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di AccelerateHS/accelerate

Tutte le issue di AccelerateHS/accelerate

Issue simili

Altre issue su Haskell

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.