Skip to content

Reduce branching in __brick_shift_left implementation in SYCL backend #2021

Open
@mmichel11

Description

@mmichel11

This issue is being filed based on the following review comment: #1976 (comment)

Potential Performance Issue
The current implementation of __brick_shift_left implementation in the SYCL backend performs strided accesses within a loop with a conditional check to ensure we are within bounds at each iteration:

const _DiffType __i = __idx - __n; //loop invariant
for (_DiffType __k = __n; __k < __size; __k += __n)
{
    if (__k + __idx < __size)
         __rng[__k + __i] = ::std::move(__rng[__k + __idx]);
}

The proposed vectorization path in https://github.com/uxlfoundation/oneDPL/pull/1976 more or less follows the same implementation with the same branching. This likely has some performance hit particularly on GPU architectures as they lack branch prediction. Instead, we should precompute the number of iterations outside the loop and hoist the last iteration after the loop with boundary checking as it may not be a full case.

This optimization should be a follow-up to the mentioned PR and should adjust both scalar and vector implementations.

Metadata

Metadata

Assignees

No one assigned

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions