[SYSTEMDS-1284] Code generation for operator fusion

• Type: Epic
• Status: Closed
• Priority: Major
• Resolution: Done
• Fix Version/s: SystemML 0.14, SystemML 1.0.0, SystemML 0.15
• Component/s: Compiler, Runtime
• Epic Name: Code generation for operator fusion
• Assignee: Matthias Boehm
• Reporter: Matthias Boehm
• Created: 19/Feb/17 06:23
• Updated: 12/Jan/18 00:32
• Resolved: 05/Jan/18 06:00

Description

This epic aims to introduce code generation capabilities for automatic operator fusion, which helps to reduce the number of materialized intermediates, reduce the number of input scans, exploit sparsity, and reduce compute, while significantly reducing the development effort compared to hand-coded fused operators.

For the 1.0 release, we will introduce code generation as an experimental feature, covering an extended version of SPOOF's code generator as described in the following paper:

T. Elgamal, S. Luo, M. Boehm, A. V. Evfimievski, S. Tatikonda, B. Reinwald, P. Sen: SPOOF: Sum-Product Optimization and Operator Fusion for Large-Scale Machine Learning, CIDR, 2017
http://cidrdb.org/cidr2017/papers/p3-elgamal-cidr17.pdf

Issue Links

• depends upon: SYSTEMDS-1594 Mlogit performance
• is duplicated by: SYSTEMDS-448 Source code generation for automatic operator fusion
• is related to: SYSTEMDS-1828 New simplification rewrite for merging sequences blocks
• is related to: SYSTEMDS-2065 Code generation for operator fusion v3
• is related to: SYSTEMDS-2019 Perftest multiple algorithms failing w/ codegen and intercept 2
• is related to: SYSTEMDS-2020 Perftest bivariate statistics w/ codegen causes unnecessary sparse-dense conversions
• is related to: SYSTEMDS-2021 Perftest stratstats w/ codegen getting stuck in optimization
• is related to: SYSTEMDS-2022 Perftest LinregCG and MLogreg failing w/ codegen due to dim mismatch
• is related to: SYSTEMDS-2024 Perftest Mlogreg multinomial, icp 1 failing w/ index-out-of-bounds
• is related to: SYSTEMDS-2026 Perftest OOM on genStratStatsData 80GB w/ codegen
• is related to: SYSTEMDS-2028 Perftest Mlogreg 10M x 1K, icpt 1 codegen failing w/ unsupported cbind in cell

Sub-Tasks

• Basic code generator: Closed
• Compiler integration codegen: Closed
• Runtime integration codegen: Closed
• Additional meta operator template: MultiAggregate: Closed
• Support compressed matrix blocks: Closed
• Hardening transfer of generated operators: Closed
• Size bounding plan cache: Closed
• Support spark codegen instructions w/ multiple RDD inputs: Closed
• Extended compiler: materialization decisions: Closed
• Disable counter-productive existing fused operators: Closed
• In-memory source code compilation: Closed
• Extended stats tool (code generation statistics): Closed
• Extended explain tool (for generated java/byte code): Closed
• Perftest benchmark codegen: Closed
• Removal unnecessary int-double casts: Closed
• Enable spoof instructions in parfor remote spark: Closed
• Codegen for existing cellwise fused operators: Closed
• Memory management temporary vector intermediates: Closed
• Rework codegen algorithm testcases (use current algorithms): Closed
• Hardening sparse-safe check cellwise operations: Closed
• Generalization cellwise template (from sideways vectors to matrices): Closed
• Generalization cellwise template (add mm as aggregation root): Closed
• Simplify cplan construction algorithm: Closed
• Support right indexing in cellwise and rowaggregate templates: Closed
• Support for different plan selection policies: Closed
• Sparsity-exploiting cellwise template: Closed
• Cost model for candidate selection: Closed
• Support min/max/sumsq in cell templates w/ aggregation: Closed
• Fuse row aggregate w/ colvector output into cell template: Closed
• Vector primitives for row comparisons: Closed
• Handling of plan selection constraints (e.g., memory/blocksize): Closed
• Multi-threaded compilation of fused operators: Closed
• Support 'replace' in row aggregate and cell templates: Closed
• Support rowMins/rowMaxs in row aggregate template: Closed
• Avoid dense allocation of empty sideway inputs: Closed
• Support cross-partition multi-aggregates with partial shared reads: Closed
• Additional meta operator template: SpoofRowwise: Closed
• Support log and exp row vector operations: Closed
• Extended compiler: leave hop dags unchanged during initial compilation: Closed
• Performance spark rowwise codegen instructions: Closed
• Create additional common unary and binary row vector operations: Closed
• Generalize cell template for sideways row vectors inputs: Closed
• Extend cost model for distributed operations and broadcasts: Closed
• Multi-aggregates w/ dot products as aggregation roots: Closed
• Support codegen for matrix-matrix multiplications: Closed
• Include multi-aggregate plans into cost estimation: Closed
• Improve efficiency sparse-unsafe cellwise operations: Closed
• Improve handling of sparse outputs and sideway inputs: Closed
• Codegen support for various patterns in nn dml library: Closed
• Improvements to row templates to capture missed opportunities: Closed
• Worst-case size estimates for codegen fused operators: Closed
• Generalized row-wise template (scalar-vector, vector indexing): Closed
• Determine minimal number of vector intermediates: Closed
• Common subexpression elimination for codegen plans: Closed
• Full aggregation support in rowwise templates: Closed
• Reduce garbage collection overhead of the codegen compiler: Closed
• Support for sparse-unsafe sparse vector primitives: Closed
• Rework codegen cost-based plan selector (opt V2): Closed
• Support rowwise cumsum operations: Closed
• Simplify algorithm dml scripts: Closed
• Column-range indexing in rowwise templates: Closed
• Column aggregation in cellwise templates: Closed
• Rework codegen candidate exporation algorithm: Closed
• Automatically determine max memory/compute bandwidth: Open
• Improve sparse-safe declaration of fused operators: Closed
• Extend outer template support for matrix-scalar ops on sparse driver: Closed
• Allow external codegen compiler configuration: Closed
• More aggressive dynamic recompilation w/ codegen: Closed
• Extended plan enumeration statistics: Closed
• Generalize row-wise cbind handling: Closed
• Column indexing on main input in row-wise ops: Closed
• Configurable codegen candidate selection policy: Closed
• Avoid dense conversion of sparse side inputs in row templates: Closed
• Support for complex sparse-unsafe binary expressions in codegen outer templates: Closed
• Improve cost-based optimizer for distributed operations: Closed
• Vector primitive for counting nnz: Closed
• New rewrite framework for code generation plans: Closed
• Linearize search space according to size of intermediates: Closed