Changes between Version 20 and Version 21 of DataParallel/WorkPlan

Mar 27, 2009 11:11:33 AM (8 years ago)



  • DataParallel/WorkPlan

    v20 v21  
    1919 ''Roman''::
    20    '''Code blow up''', '''Generate boilerplate with TH''' & '''Recycling for joinD'''
     20   '''Code blow up''', '''Generate boilerplate with TH''', '''Explicit shape information''' & '''Recycling for joinD'''
    2121   – status: partly implemented, but still needs serious work
    2222   * We still don't have the code blow up under control.
    4141 * #2984
    43 Category: ''Efficiency'' (improve scalability and/or baseline performance of generated code):
     43Category: ''Efficiency, short term'' (improve scalability and/or baseline performance of generated code):
    4545 * '''Recycling for joinD:''' Use Roman's recycling optimisation (PADL'09) to avoid copying in `joinD`.
    5151 * '''Regular multi-dimensional arrays:''' Representing regular arrays by nested arrays is generally not efficient, but due to the current lack of fusion for segmented arrays that produce multiple arrays of different length (e.g., `filterSU :: (a -> Bool) -> SUArr a -> SUArr a`), matters are worse than one might think (e.g., when using a hierarchical matrix representation).  Hence, we need direct support for regular, multi-dimensional arrays.
     53 * '''Explicit shape information:''' All library internal functions should get shape information (including the lengths of flat arrays) as extra arguments; in particular, lengths shouldn't be stored in every level of a flattened data structure.  This should simplify the use of rewrite rules that are shape sensitive.
     55 * '''Split/join fusion for segmented arrays:''' Needs to be redone completely, as it currently only works for very simple cases.
    5357 * '''Unlifted functions:''' For some scalar functions (especially numeric functions and functions operating on enumerations), it is easier to not lift them at all; rather than to lift them and then attempt to recover the original form with fusion and other optimisations.  An example is the `SumSq` benchmark, where we have `sumP (mapP (\x -> x * x) [:1..n:]`.  Here, we would rather not lift `\x -> x * x` at all.  Roman implemented a very simple form of this idea (which works for `SumSq`).  However, we would like this in a more general form, where named functions that remain unlifted are marked suitably, as clients of a function can only be unlifted if all functions it calls are already unlifted.  How much does that tie in with '''Selective vectorisation'''?
     59Category: ''Efficiency, long term'' (larger work items that will probably get more important with more complex applications):
     61 * '''Fusion for segmented arrays:''' Some segmented functions (e.g., `filterSU :: (a -> Bool) -> SUArr a -> SUArr a`) produce multiple arrays of varying lengths.  We currently have no good story for fusing such operations.
    5563 * '''Replicate:''' Implement an extended array representation that uses an optimised representation for arrays that are the result of common forms of replication (i.e., due to free variables in lifted expressions).  The optimised representation stores the data to be replicated and the replication count(s) instead of actually replicating the data.  This also requires all functions consuming arrays to be adapted.  ''Update:'' Since we have `INLINE CONLIKE`, we can handle `replicate` using rules as long as it gets close to its consumer during simplification.  This makes the use of an extended array representation less important.  We will delay it until we run into examples where its lack bites us significantly.