Changes between Version 1 and Version 2 of DataParallel/LiveFusion


Ignore:
Timestamp:
Feb 6, 2012 6:45:28 PM (3 years ago)
Author:
roldugin
Comment:

Improve SF section.

Legend:

Unmodified
Added
Removed
Modified
  • DataParallel/LiveFusion

    v1 v2  
     1
    12= Live Fusion: An alternative runtime fusion system (WIP) =
    23
     
    1516
    1617Although only the section on the ''Live Fusion'' presents the new and unpublished material, two other fusion systems are described first. There are several reasons for this:
    17  1. to justify the needs for the research by showing the limitations of the current system
    18  1. to compare the designs of the new and old systems
     18 1. to justify the needs for the research by showing the limitations of the current system,
     19 1. to compare the designs of the new and the existing systems,
    1920 1. to give credit to the existing systems for the borrowed design decisions.
    2021
     
    2627=== Programming Model ===
    2728
    28 Stream Fusion framework introduces two data types: a ''stream'' and a ''stepper''.
     29Stream Fusion framework is useful for fusing collective operations that traverse data structures in some uniform fashion. Such data structures are viewed as a continuous stream of values of some type. Both lists and arrays can be presented in such manner, thus the framework is suitable for use in DPH. Stream Fusion introduces two data types: a `Stream` and a `Step`per.
    2930
    3031{{{
     
    4041}}}
    4142
    42 A `Done` would flag the end of the stream, while a `Yield` would contain an element and the next seed. If the stream `Skip`'s that would meant that the current step does not contain an element (e.g. when a `filter`'s precondition returned false).
    43 
    44 Arrays or lists can be convected to and from streams. To save space we will only present a straight forward streaming function for lists.
     43`Done` flags the end of the stream, while a `Yield` contains an element and the next seed. If the stream is converted back into the original form of a list of an array, the yielded element will appear in the appropriate position. On the other hand, if a stream `Skip`s the current step does not contain an element (e.g. when a `filter`'s precondition returns false).
     44
     45Arrays or lists can be converted to and from streams. To save space we will only present a straight forward streaming function for lists.
    4546
    4647{{{
     
    6768}}}
    6869
    69 To see how a `Skip` step might be used it may be worthwhile to look at the definition of the `filter` function:
     70To see how a `Skip` step might be used it might be worthwhile to look at the definition of the `filter` function:
    7071
    7172{{{
     
    8283}}}
    8384
    84 The fusion opportunity such as `(map f . filter p` may now be exploited with the following rewrite rule:
     85The fusion opportunity such as `(map f . filter p)` may now be exploited with the following rewrite rule:
    8586
    8687`<stream/unstream fusion> forall stream (unstream s) +-> s`
     88
    8789(TODO: ppr from latex
    88901. \mathmf{(map\, f\cdot filter\, p)}
     
    9294=== Generated Code ===
    9395
    94 In order to completely remove all traces of the helper data structures Stream Fusion relies on several general purpose compiler optimisations. They are discussed in the respective papers referenced at the beginning of this page. The program `TODO` can be desugared and inlned to give
    95 
    96 {{{
    97 
     96In order to completely remove all traces of the helper data structures Stream Fusion relies on several general purpose compiler optimisations. They are discussed in the respective papers referenced at the beginning of this page. The program `TODO: insert program code here` can be desugared and inlined to give
     97
     98{{{
     99TODO: present the program in the desugared/inlined form
    98100}}}
    99101
     
    101103
    102104{{{
    103 
     105TODO: present the fully optimised program
    104106}}}
    105107
     
    279281
    280282enumFromStepLen :: Int -> Int -> Int -> Array Int
    281 {-# INLINE enumFromStepLen #-}
    282283enumFromStepLen start step len = Array loopH
    283284  where loopH = LoopH mf start (ReplicateH len ())