Optimization tracking issue

[tomwhite]

This is an umbrella issue for tracking the work on optimizations in Cubed.

Creation optimizations

Making creation operations more efficient, typically by not materializing unnecessary data.

• Add VirtualInMemoryArray that keeps small arrays in memory #336
• Handle the case where an array is created by calling map_blocks with no input arrays #343
• Use Dask's 'broadcast trick' to save memory for single-valued arrays #359

Fusion optimizations

Currenly we fuse map blocks operations with one input, but there are more types of fusion we could implement.

• Change the DAG to have separate nodes for operations and arrays #337
  • This should be done early on, so changes to fuse or other DAG manipulation tasks don't need to be done twice
• Introduce a class to model parts of an operation's memory usage #288
• Allow more control over optimizations applied #342
  • For example, allow users to switch on more aggressive optimizations
  • Introduce max_total_num_input_blocks as a heuristic to control fusion #376
• Fuse connected blockwise subgraphs #136
  • This change will fuse operations with multiple inputs
• Take allowed_mem into account when fusing primitive operations #366
• Support multiple outputs in blockwise #69
• Sibling fusion
  • This change will fuse operations that share the same inputs

Reduction optimizations

Reduction operations like sum and mean could be improved by minimising the amount of data transferred.

• Support arbitrary block index functions in blockwise #350
• Implement partial_reduce and tree_reduce using generalized blockwise #365
• Optimizing reduction #331
• Fuse pipelines with different numbers of tasks #284
• Find good defaults for reduction parameters #418

High-level query optimizations

Re-writing array expressions to an optimized form (before applying the optimizations above).

• Query optimization #333

Benchmarking and runtime

Testing the effect of the optimizations above.

• Benchmark optimizations #356
• Tune straggler mitigation algorithm #357

Documentation

• Document optimization changes #381

[TomNicholas]

Do any of the caveats on the Scaling docs page need updating after all these improvements? e.g. it currently says

In theory multiple blockwise operations can be fused together, enhancing the performance further. However this has not yet been implemented in Cubed.

[tomwhite]

Do any of the caveats on the Scaling docs page need updating after all these improvements? e.g. it currently says

In theory multiple blockwise operations can be fused together, enhancing the performance further. However this has not yet been implemented in Cubed.

Yes, thanks for raising this. I've opened #381 to track documentation changes.