# Changes between Version 1 and Version 2 of DataParallel/LiveFusion

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

Improve SF section.

### Legend:

Unmodified
 v1 = Live Fusion: An alternative runtime fusion system (WIP) = Although 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: 1. to justify the needs for the research by showing the limitations of the current system 1. to compare the designs of the new and old systems 1. to justify the needs for the research by showing the limitations of the current system, 1. to compare the designs of the new and the existing systems, 1. to give credit to the existing systems for the borrowed design decisions. === Programming Model === Stream Fusion framework introduces two data types: a ''stream'' and a ''stepper''. Stream 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 Stepper. {{{ }}} 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). Arrays or lists can be convected to and from streams. To save space we will only present a straight forward streaming function for lists. 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 Skips the current step does not contain an element (e.g. when a filter's precondition returns false). Arrays or lists can be converted to and from streams. To save space we will only present a straight forward streaming function for lists. {{{ }}} To see how a Skip step might be used it may be worthwhile to look at the definition of the filter function: To see how a Skip step might be used it might be worthwhile to look at the definition of the filter function: {{{ }}} The fusion opportunity such as (map f . filter p may now be exploited with the following rewrite rule: The fusion opportunity such as (map f . filter p) may now be exploited with the following rewrite rule:  forall stream (unstream s) +-> s (TODO: ppr from latex 1. \mathmf{(map\, f\cdot filter\, p)} === Generated Code === 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 {{{ 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: insert program code here can be desugared and inlined to give {{{ TODO: present the program in the desugared/inlined form }}} {{{ TODO: present the fully optimised program }}} enumFromStepLen :: Int -> Int -> Int -> Array Int {-# INLINE enumFromStepLen #-} enumFromStepLen start step len = Array loopH where loopH = LoopH mf start (ReplicateH len ())