fredrikbk
fredrikbk on Hacker News
That is correct (and we appreciate the citation). The tensor compiler (taco) has focused on compiling expressions that contain one or more sparse tensors so far and, even though it can generate code for dense expressions just fine, does not optimize these like TC, TCE, and XLA does. We are working on a scheduling language for it so that it will perform well across all types of formats and on GPUs.
The story for sparse matrices is more complicated. Because of the dependencies imposes by sparse data structures (you don’t have random access and often have to traverse them) you cannot do loop ruling without adding if statements (I think you can probably get rid of these by preconputing, e.g. row halfway points). It may still make sense, but there’s a bigger cost. However, you can lay out data in a tiled way to get better cache blocking; taco lets you do this by storing a blocked matrix as a 4-tensor.
Because of the lack of random access, some algorithm like linear combination matrix-matrix multiplication benefits from adding a dense workspace that gives you a view into one row. Then you can scatter into it and when you’re done copy the nonzeroes to the sparse result matrix. This algorithm is sometimes called Gustavson’s algorithm after the person who published it first). We have worked out this optimization within the taco framework, it applies to other kernels too, and are now writing it up for publication.
We’ve tried to engineer it to emit clean code, but seems we left in some unused variables.
The C compilers dead code elimination should remove those though.
We currently compile to C code and use the system Compiler to compile it further. For dense loop nests it does a good job of auto-vectorizing, but we believe there’s good opportunities for doing something custom, knowing the high-level algebraic structure.
taco does not target GPUs yet, and we want to work on it this spring. It’s clearly needed, for example for neural networks
That is a good idea, but we are only so many. One student in the Julia group is developing Julia bindings though, and we hope to make C/python bindings. The inner workings are published in the paper “The Tensor Algebra Compiler”, so it can be implemented in other languages. We like the idea of bindings because then our future work can benefit more users.
Thanks, that is really nice of you :)
For sure, as you point out, many such kernels have been written, going at least as far back as 1967.
We believe our contribution is being able to generate kernels for all the expressions.
Thanks for the reference though! We’re trying to learn where sparsity may be important in neural networks.
I don't know of an explicit list like this, but some areas that we are particularly interested in are: data analytics (tensor factorization), machine learning (anything sparse including perhaps sparse neural networks), and scientific computing/graphics (general relativity, quantum mechanics such as QCD, finite element simulations, and apparently nuclear physics). It is particularly suited anywhere you have sparse matrices or tensors.
Thanks! I really like that conference!
Hi, that sounds very interesting and I hope someone works on it. We're only so many people though, and we have several things we want to do that will at least occupy us until next summer.
Larry chose to focus on the big data part, because it is intuitive. But I think you're absolutely correct, that it has applications in physics/chemistry (and machine learning too). We're actually talking to people in our theoretical physics department, who may want to use taco for their QCD computations. There's also a new issue on our tracker about adding complex number support for nuclear computations and quantum computing:
https://github.com/tensor-compiler/taco/issues/116.
The tensor contraction engine is great work, and focuses on dense tensor. We currently optimize for sparse tensors so TCE will do better than us for pure dense expressions. We want to bridge this gap next semester though.
The cyclops framework is also great. We discuss it in our related work, but we did not directly compare to it in our evaluation. The first version of it, like TCE, focused on dense tensors, and their main focus is on distributed computing, which we don't support yet (we do shared memory parallel execution at the moment). They have some followup work on sparse computations. The difference to our work is that they, if I read their paper correctly, transposes the data until they can call pre-existing matrix multiplication routines. This causes data movement overheads. Our work compiles expressions to work at the data at hand, without moving it.
Thanks! Yes, we have an `apps` directory in the source tree that we will add programs to. These programs are tested by our test suites, and will later be our performance regressions.
I'm actually working with some people at Adobe this summer to add Local-Global Solvers for ARAP energies (an optimization code) to the set of applications we provide there. We also have an implementation of PageRank.
Very valid concerns. If you use C++ it's easy to interoperate with Simit, since Simit is a C++ library with an online compiler that compile the time steppers. You build the graph using a C++ api and then you run a Simit program which updates the graph. It's similar to how you'd use OpenGL or DirectX (graphs instead of meshes and Simit programs instead of shaders). See
https://youtu.be/raPkxhHy5ro?t=19m32s, and
http://simit-lang.org/api for more information.
You're absolutely right that we could have provided all the functionality as C++ classes instead of compiling Simit programs through the Simit C++ API, and we might at some point. The reason why we didn't do this is that the language is complex enough that we felt it would be less user friendly. I definitely tried to design it as a library without a parser.
We needed new language constructs (the matrix assembly) and a new type system for matrices that ties back to the graph to make it simple and fast. It is also not limited to FEM codes. It can be used to write any application that computes on sparse systems using linear algebra. Some application areas are optimization, machine learning, data analytics, fluid dynamics, image processing, and robotics.
For more information about the language, why it is designed the way it is, why it is fast, and what applications it can be used for, see the talk I gave at Microsoft Research last Friday: https://youtu.be/raPkxhHy5ro?t=40m32s
It actually shares two authors (Jon and Saman). Their work on Halide was amazing!