Better Implicit Parallelism; Improving ApplicativeDo Heuristics Through Weight Annotations
| dc.contributor.author | Hübinette, Edvard | |
| dc.contributor.author | Thune, Fredrik | |
| dc.contributor.department | Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers) | sv |
| dc.contributor.department | Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers) | en |
| dc.date.accessioned | 2019-07-03T14:55:48Z | |
| dc.date.available | 2019-07-03T14:55:48Z | |
| dc.date.issued | 2018 | |
| dc.description.abstract | ApplicativeDo tries to remove the monad binds where possible when desugaring Haskells’ do-notation. It does this by looking at inter-statement dependencies and connecting them with applicative operations when possible; this introduces implicit parallelism in the code. Deciding which structure to generate is tricky, since many different are usually possible. Currently, this is solved with simple minimum cost analysis with an unit cost model, assuming each statement takes the same amount of time to evaluate. By extending the cost model inside the ApplicativeDo algorithm for variable evaluation costs, we perform smarter generation of code by prioritising parallelisation of heavy statements. At Facebook, Marlow et al. developed Haxl, a data-fetching library that can use applicative structure in expressions for free parallelism. To our knowledge, it is the only library that can do automatic parallelism on applicative expressions. We observe significant wall-clock speedups in many cases when running benchmarks with Haxl, compared to the original ApplicativeDo-desugared programs, given relative costs of statements. The ApplicativeDo extension is agnostic to the source of costs, but one way of providing them is investigated as optional weight annotations on do-statements. This works well when the relative costs are known, but this kind of run-time estimation is notoriously difficult, particularly in Haskell. We suggest different directions for future work relating to sources of costs. | |
| dc.identifier.uri | https://hdl.handle.net/20.500.12380/256249 | |
| dc.language.iso | eng | |
| dc.setspec.uppsok | Technology | |
| dc.subject | Data- och informationsvetenskap | |
| dc.subject | Computer and Information Science | |
| dc.title | Better Implicit Parallelism; Improving ApplicativeDo Heuristics Through Weight Annotations | |
| dc.type.degree | Examensarbete för masterexamen | sv |
| dc.type.degree | Master Thesis | en |
| dc.type.uppsok | H | |
| local.programme | Computer science – algorithms, languages and logic (MPALG), MSc |
Ladda ner
Original bundle
1 - 1 av 1
Hämtar...
- Namn:
- 256249.pdf
- Storlek:
- 1022.11 KB
- Format:
- Adobe Portable Document Format
- Beskrivning:
- Fulltext