Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add a Scheduling Language #154

Open
wraith1995 opened this issue Mar 30, 2023 · 0 comments
Open

Add a Scheduling Language #154

wraith1995 opened this issue Mar 30, 2023 · 0 comments
Labels
discussion Request For Comment enhancement New feature or request

Comments

@wraith1995
Copy link
Collaborator

wraith1995 commented Mar 30, 2023

Precompute

Add a function with the following specification:
program = precompute(program, expressionPattern, computeAtIndex, storeAtIndex, storageType, storagePermutation)

This function finds all instances of expressionPattern below a loop level specified by the computeAtIndex. The expressionPattern should roughly be a pure function of the expressions it depends on. We the hoist the captured expressionPatterns and any intermediates used to compute them. If we go through wrapper arrays, we need to analyze them to deduce hoisted loop structure. However, we don't plan to do much bounds analysis beyond that - instead, we will lower the hoisted computation in a manner similar to which we would lower the original loop - we hope that the pre-existing infrastructure can simplify that to avoid too much over computing. We might need special storage types to avoid over-computing/allocating due needing to store something in the case of a dense array.

The storage for the hoisted computation is allocated right above storeAtIndex, which must be at or above the computeAtIndex. The storageType must have a dimension for every index below storeAtIndex. ThestoragePermutation, by default the identity, determines how hoisted indicies are mapped to the storage. The access pattern should be concordant with the storage - we don't want to introduce format conversions via this mechanism.

Fuse

(previously #155)

Introduce a transformation that fuses two loops where one is directly nested below the other. There are a few different strategies for how we could do this:

By enabling wrapper arrays for mod and div - this could be independently useful.
By adding reshape, stretch, and repeat wrapper arrays - reshape is independently useful. See 

#151
By using a symbolic tensor, F[i0, i1, f] which is True only when f would be the fused index of i0 and i1 - this is difficult due to the current lowering order.

Reorder

Loop reordering is very possible, but it's unclear if we want to similarly transpose corresponding inputs.

Split

Split a loop using a chunkmask

@willow-ahrens willow-ahrens added the enhancement New feature or request label May 8, 2024
@willow-ahrens willow-ahrens changed the title Add a precompute transform Add a Scheduling Language May 25, 2024
@willow-ahrens willow-ahrens added the discussion Request For Comment label May 25, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
discussion Request For Comment enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

2 participants