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

scheduling: bug in fuse transformation #355

Closed
rohany opened this issue Jan 11, 2021 · 1 comment · Fixed by #360 or #362 · May be fixed by #500
Closed

scheduling: bug in fuse transformation #355

rohany opened this issue Jan 11, 2021 · 1 comment · Fixed by #360 or #362 · May be fixed by #500

Comments

@rohany
Copy link
Contributor

rohany commented Jan 11, 2021

The following test fails due to undefined variables causing the compilation process to error:

TEST(scheduling, fuseBug) {
    Tensor<double> A("A", {4, 4}, {Dense, Dense});
    Tensor<double> B("B", {4, 4}, {Dense, Dense});
    Tensor<double> C("C", {4, 4}, {Dense, Dense});
    IndexVar i("i"), j("j"), f("f");
    C(i, j) = A(i, j) * B(i, j);
    auto stmt = C.getAssignment().concretize();
    C.compile(stmt.fuse(i, j, f));
}

The generated code looks like:

int compute(taco_tensor_t *A, taco_tensor_t *B, taco_tensor_t *C) {
  int A1_dimension = (int)(A->dimensions[0]);
  int A2_dimension = (int)(A->dimensions[1]);
  double* restrict A_vals = (double*)(A->vals);
  double* restrict B_vals = (double*)(B->vals);
  int C1_dimension = (int)(C->dimensions[0]);
  int C2_dimension = (int)(C->dimensions[1]);
  double* restrict C_vals = (double*)(C->vals);

  for (int32_t f = 0; f < (C1_dimension * C2_dimension); f++) {
    int32_t i = f / C2_dimension;
    if (i >= C1_dimension)
      continue;

    int32_t j = f % C2_dimension;
    if (j >= C2_dimension)
      continue;

    int32_t jA = i * A2_dimension + j;
    A_vals[jA] = B_vals[jB] * C_vals[jC];
  }
  return 0;
}

The jB and jC variables are undefined and probably should be replaced with i and j.

@Infinoid
Copy link
Contributor

You're right. It seems all of the current test cases for fuse are using sparse inputs, where the fused IndexVar is passed to pos immediately after. Maybe that hid this problem somehow.

rohany added a commit to rohany/taco that referenced this issue Jan 13, 2021
Fixes tensor-compiler#355.

This commit fixes a bug where the fuse transformation would not generate
necessary locator variables when applied to iteration over two dense
variables.
rohany added a commit to rohany/taco that referenced this issue Jan 13, 2021
Fixes tensor-compiler#355.

This commit fixes a bug where the fuse transformation would not generate
necessary locator variables when applied to iteration over two dense
variables.
rohany added a commit to rohany/taco that referenced this issue Jan 13, 2021
Fixes tensor-compiler#355.

This commit fixes a bug where the fuse transformation would not generate
necessary locator variables when applied to iteration over two dense
variables.
@stephenchouca stephenchouca reopened this Jan 14, 2021
rohany added a commit to rohany/taco that referenced this issue Jan 14, 2021
Fixes tensor-compiler#355.

This commit fixes a bug where the fuse transformation would not generate
necessary locator variables when applied to iteration over two dense
variables.

Additionally, this commit adds a test for when a dense iteration results
in a transposition of a tensor.
rohany added a commit to rohany/taco that referenced this issue Jan 14, 2021
Fixes tensor-compiler#355.

This commit fixes a bug where the fuse transformation would not generate
necessary locator variables when applied to iteration over two dense
variables.

Additionally, this commit adds a test for when a dense iteration results
in a transposition of a tensor.
rohany added a commit to rohany/taco that referenced this issue Jan 14, 2021
Fixes tensor-compiler#355.

This commit fixes a bug where the fuse transformation would not generate
necessary locator variables when applied to iteration over two dense
variables.

Additionally, this commit adds a test for when a dense iteration results
in a transposition of a tensor.
rohany added a commit to rohany/taco that referenced this issue Jan 14, 2021
Fixes tensor-compiler#355.

This commit fixes a bug where the fuse transformation would not generate
necessary locator variables when applied to iteration over two dense
variables.

Additionally, this commit adds a test for when a dense iteration results
in a transposition of a tensor.
stephenchouca added a commit to stephenchouca/taco that referenced this issue Apr 30, 2021
…#355. Also generate more optimized attribute query code for parallel sparse tensor addition
guilhermeleobas pushed a commit to Quansight-Labs/taco that referenced this issue May 27, 2021
* Reimplemented parts of attribute query lowering and some optimizations

* Add a test case for mixing sparse/dense formats in matrix multiply

The test case does A=BC, and tries all permutations of Dense, CSR, CSC, and COO.
It is disabled for now, enable it once sparse output works.

* Add in hoisted workspace reuse and remove guard for divisible bound and split

* Fix some workspaces tests

* Use CUDA_LIBRARIES instead of hardcoding the path to libcudart

Hardcoded paths don't work when using Debian's packaged version of cuda,
as the library paths don't match.  CMake's find_package(CUDA) sets
CUDA_LIBRARIES to the path of libcudart, so just use that instead.

* Add TACO_NVCC var to complement TACO_NVCCFLAGS

This is useful for passing specific arguments to nvcc.  In my case,
I wanted to force nvcc to use a specific version of g++.

* Updated automated test workflow

* Updated automated test workflow

* fix -s arg parser

* Prototypes automatically generating code to to have sparse iteration over a dense workspace

* don't run autoscheduling commands if manual schedule is provided in command line tool fixes tensor-compiler#336

* fix fuse bound calculation, which was unnecessarily enlarged. Fixes tensor-compiler#337

* Fixes bugs in check for accelerating workspace

* Fixes bug in concreteNotation check. All workspace tests pass.

* Removes print statements

* fix handling of operator precedence in CUDA backend. Fixes tensor-compiler#338

* Only hoists out malloc + free from where statement when possible. Emits loop to zero every element in a temporary when it is hoisted before the producer is called. Changes the codegens to keep pointer names constant

* Fix build failures on ubuntu 16.04

* Fix python bindings when building with clang++-10

Fix a few instances of this build error in pytaco:
.../python_bindings/src/pyTensor.cpp:406:53: error: unknown type name 'nullptr_t'; did you mean 'std::nullptr_t'?

* Use exceptions for error reporting in all cases

Previously, exceptions were used only when the Python bindings were
enabled.  This meant that C++ applications could only handle errors
gracefully when the Python bindings were enabled.

Change it to consistently use exceptions in all cases.

* Adds negation to pytaco tensor interface

* Removes initialization loop from before producer when accelerating a dense workspacE

* Places index list size above the producer loop when accelerating a dense workspace. This should make the transition to multithreading easier and fixes a bug in the original code

* Fixes workspace reset

* If underived variables are used to index a workspace, we allocate space for the workspace based on the size of the sizes of the input tensors

* Relaxes requirements for spmm transformation

* Checks if first mode of last tensor has locate for spmm transform

* Changes SPMM tranform requirement. Unsure about this

* Fix whitespace in tools/taco.cpp.  (No functional changes)

* Report an error properly in the taco CLI tool.

* Use the existing Lexer to parse scheduling directives

Add a schedule parser function.
Add test cases for the schedule parser function.
Use the function in the taco command-line tool.
Return usage messages when the user passes in the wrong number of parameters.

* Silence a warning about cmake policy CMP0054.

* lower,index_notation: fix compilation warnings

Fix a few compilation warnings caused by taking copies of loop variables
instead of references.

* index_notation,error: deduplicate dimension checking routines

Currently, there are two dimension checking methods in TACO. The first
returned a boolean, and the second returned a user readable string
detailing the error. Both methods had nearly identical code. Therefore,
this commit merges them into a single function that returns a boolean
and the error, if it exists.

* lower: fix a bug causing undefined variables when applying fuse

Fixes tensor-compiler#355.

This commit fixes a bug where the fuse transformation would not generate
necessary locator variables when applied to iteration over two dense
variables.

* Revert "lower: fix a bug causing undefined variables when applying fuse"

* Add -help and -help=schedule parameters to CLI

* lower: fix a bug causing undefined variables when applying fuse

Fixes tensor-compiler#355.

This commit fixes a bug where the fuse transformation would not generate
necessary locator variables when applied to iteration over two dense
variables.

Additionally, this commit adds a test for when a dense iteration results
in a transposition of a tensor.

* Emit unsequenced insertion code

* Zeroelss updates

* Emit code to use attribute query results during assembly

* include,src: introduce a true break statement, rename current to continue

The current `ir::Break` statement actually translates to a `continue`.
This commit renames this to `ir::Continue`, and adds a new `ir::Break`
node that actually translates to a `break`. This new node will be used
by upcoming windowing work.

* Don't emit append code if using ungrouped insertion

* Clear the needsCompile flag in tensor->compileSource()

Fixes tensor-compiler#366.

* Add an error message for invalid input tensor names.

* Fix warnings in python bindings

* tensor,codegen: fix a bug where kernel cache could be modified

This commit fixes a bug where upon recompilation of an index statement,
entries in the kernel cache could be inadvertently modified, leading to
confusing segfaults.

An example of the bug is included in the added test, where the second
call to `c(i, j) = a(i, j)` would hit the cache, but then find a module
that had code that corresponded to `c(i, j) = a(i, j) + b(i, j)`.

* Implemented assemble scheduling command + don't sort sparse accelerator if performing reduction

* Assume inputs are zeroless when computing attribute queries

* Replace workspaces in attribute queries

* Enable parallelization of forall statements with results assembled by ungrouped insertion

* Fixed various bugs

* Fixed various bugs

* Deleted redundant code

* Fix workspaces test on ubuntu 16.04

Fixes: tensor-compiler#380

* Add code coverage targets to cmake

* Fix warnings in Release builds

* Fixed attribute query compute code not being emitted + optimize computation of Boolean temporaries when always assigned true

* Emit init_edges code

* Added parallel SpGEMM test

* Fixed heuristic for inserting accelerators for workspaces indexed by derived index variables

* Removed debug print statements

* Updated CMake requirements

* Added correctness checks for ungrouped insertion

* Fix a bug in CLI parsing of bound()

This bug was introduced in tensor-compiler#352.

* Strengthened precondition for assemble command

* Remove pybind11

* Make pybind11 a submodule

* Modify cmake

* fix cmake

* Removes forcecast in function overload

* Add comment to python code explaining when conversion happen

* Don't emit atomic pragma for non-reduction assignments

* *: add support for windowing of tensors

This commit adds support for windowing of tensors in the existing index
notation DSL. For example:

```
A(i, j) = B(i(1, 4), j) * C(i, j(5, 10))
```

causes `B` to be windowed along its first mode, and `C` to be windowed
along its second mode. In this commit any mix of windowed and
non-windowed modes are supported, along with windowing the same tensor
in different ways in the same expression. The windowing expressions
correspond to the `:` operator to slice dimensions in `numpy`.

Currently, only windowing by integers is supported.

Windowing is achieved by tying windowing information to particular
`Iterator` objects, as these are created for each `Tensor`-`IndexVar`
pair. When iterating over an `Iterator` that may be windowed, extra
steps are taken to either generate an index into the windowed space, or
to recover an index from a point in the windowed space.

* Update Cmake to pull python binding during any build

* Add a SpTV+openmp+atomics test case for tensor-compiler#316

* Improve CI test coverage

Add a build step that covers the OpenMP and Python features.

Make it run `make test` to run all available test suites.

* Raise internal error if trying to generate code to assemble sparse accelerator in parallel

* *: add the ability to stride window access

This commit extends the windowing syntax to include an optional third
parameter to a window expression on an index variable:

```
a(i) = b(i(0, n, 5 /* stride */))
```

This stride parameters means that the window should be accessed along
the provided stride, which defaults to 1.

Striding is implemented with a similar idea as windowing, where
coordinates in the stride are mapped to a canonical index space of `[0,n)`.
For compressed modes, coordinates that don't match the stride are
skipped.

* Fixed various bugs

* Fixed removal of redundant loops

* lower: fix a bug when using OpenMP and windowing

Fixes tensor-compiler#409.

This commit fixes a bug where position loops parallelized with OpenMP
that operated over windowed tensor modes would fail to compile.

This commit also fixes some compilation errors compiling windowing tests
on Ubuntu.

* Unbreak cmake build of python bindings

* Remove redundant allocation

* *: add support for using arbitrary indexing sets to window tensors

This commit adds support for using vectors to index arbitrary dimensions
of tensors. It works by packing the vector into a sparse tensor, and
coiterating over the sparse tensor to efficiently filter the chosen
dimensions. The syntax of indexing sets look as follows:

```
A(i) = B(i({1, 3, 5}))
```

which means that only elements 1, 3, and 5 from `B` will be used in the
computation.

* index_notation: implement the `divide` transformation

The divide transformation divides a loop up into `n` equal components,
whereas split breaks a loop up into a components of size `n`.

It also enables support for the transformation in the TACO CLI.

* Enable CI tests for array_algebra branch

* Suppress GCC warnings

* Fixed heuristic for inserting sparse accelerator

* Revert "Fixed heuristic for inserting sparse accelerator"

This reverts commit 4e264ce.

* Fixed heuristic for inserting sparse accelerator

* Fix package version issue in CI tests

Run "apt-get update" to update the package list.

* cuda: fix windowing test with cuda

Fixes tensor-compiler#422.

This commit ensures that the allocation clearing logic is applied to
the CUDA backend as well. The windowing test caught this because TACO
was automatically parallelizing the loop onto the GPU.

* index_notation,tensor: small bugfixes for index sets

* Fixes a runtime error when using index sets on tensors not of integer types
* Fixes a compile error when using a vector typed variable as argument
  for an index set.

* Allow CLI precompute() to specify the workspace name

* Add tracking/reporting of build info

* CLI tool treats double hyphens as a single hyphen

* lowerer_impl: fix some striding bugs

Fixes some formulaic errors in generated striding code along with a test
that revealed them.

* Better error message for guarding unguardable loops

* Use full precision when IR printing float constants

The default precision when printing a floating point value is 6 digits.
This causes a lot of double values to get truncated. Print these with
full precision to avoid losing data.

* Don't emit redundant code to append edges when inserting into result

* index_notation: fix a bug where windows would be dropped through `+=`

Fixes tensor-compiler#451.

This commit fixes a bug where windows applied to index variables would
be dropped when assigned to via the `+=` operator.

* Fixed printing of scheduling commands in command-line tool output

* Fixed precompute transformation and attempt at fixing tensor-compiler#389. Also generate more optimized attribute query code for parallel sparse tensor addition

* Modified MTTKRP test to use schedule with precompute

* assemble command now no longer uses fresh index variables in inserted attribute query computations by default

* Fixed typo in command-line tool usage

* Fixed assemble command with dense arrays + improved heuristics for determining whether result needs to be explicitly zero-initialized

* Fixed how parallelize command checks for races

* Fixing merge issues

Co-authored-by: Stephen Chou <[email protected]>
Co-authored-by: Mark Glines <[email protected]>
Co-authored-by: Olivia Hsu <[email protected]>
Co-authored-by: Stephen Chou <[email protected]>
Co-authored-by: roastduck <[email protected]>
Co-authored-by: Rawn <[email protected]>
Co-authored-by: Ryan Senanayake <[email protected]>
Co-authored-by: Rohan Yadav <[email protected]>
Co-authored-by: Changwan Hong <[email protected]>
Co-authored-by: Rohan Yadav <[email protected]>
Co-authored-by: Sam Kaplan <[email protected]>
rohany added a commit that referenced this issue Jan 2, 2022
This commit properly fixes #355 by ensuring that duplicate locators are
not generated by different codepaths. This bug is masked by the
ir::simplify call which removes the extra locators in most situations.
rohany added a commit that referenced this issue Jan 2, 2022
This commit properly fixes #355 by ensuring that duplicate locators are
not generated by different codepaths. This bug is masked by the
ir::simplify call which removes the extra locators in most situations.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
3 participants