[SYSTEMDS-1782] Extend parfor block indexing analysis

• Type: Task
• Status: Open
• Priority: Major
• Resolution: Unresolved
• Assignee: Fei Hu
• Reporter: Matthias Boehm
• Created: 19/Jul/17 06:01
• Updated: 31/Aug/17 21:52

Description

This task aims to better support arbitrary block indexing in a parfor context, for expressions as this example from SYSTEMML-1774:

 parfor (j in 1:parallel_batches, log=DEBUG) {
        # Get a mini-batch in this group
        beg = ((j-1) * batch_size) %% nrow(X_group_batch) + 1
        end = min(nrow(X_group_batch), beg + batch_size - 1)
        X_batch = X_group_batch[beg:end,]
        y_batch = y_group_batch[beg:end,]

Currently, we're unable to determine a constant size for X_batch and y_batch. However, since the parfor body is anyway recompiled on parfor entry, we can improve upon this as follows:

• Leverage known constants and index ranges to perform a limit analysis for linear functions in indexing expressions. For example, the above expression for beg and end would simplify to (j-1) * 32 + 1 and beg + batch_size -1.
• Better handling of linear functions in right indexing HOPs - this would allow us to determine batch_size as the number of rows in the output.

Issue Links

• is depended upon by: SYSTEMDS-1774 Improve Parfor parallelism for deep learning