Changes between Version 1 and Version 2 of DataParallel/LiveFusion


Ignore:
Timestamp:
Feb 6, 2012 6:45:28 PM (2 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 ())