Added SparseDenseMatMul Op.

Benchmarks:

$ .../tensorflow/python/sparse_tensor_dense_matmul_op_test --benchmarks

DenseDense MatMul (w/ Sparse Flag) vs. SparseDense MatMul
Matrix sizes:
  A sparse [m, k] with % nonzero values between 1% and 80%
  B dense [k, n]

% nonzero        n       gpu     m       k       dt(dense)       dt(sparse)      dt(sparse)/dt(dense)
0.01     1       True    100     100     0.000198262     9.8618e-05      0.497413
0.01     1       True    100     1000    0.000308075     9.71129e-05     0.315225
0.01     1       True    1000    100     0.000297211     9.97391e-05     0.335583
0.01     1       True    1000    1000    0.000749049     0.00011149      0.148842
0.01     1       False   100     100     0.000207866     9.79061e-05     0.471006
0.01     1       False   100     1000    0.000306979     9.8314e-05      0.320263
0.01     1       False   1000    100     0.000297263     9.7379e-05      0.327585
0.01     1       False   1000    1000    0.000858516     0.000112162     0.130647
0.01     10      True    100     100     0.000201347     9.71699e-05     0.482599
0.01     10      True    100     1000    0.00031786      0.000132792     0.417769
0.01     10      True    1000    100     0.000309127     0.000128658     0.416198
0.01     10      True    1000    1000    0.000779245     0.000133656     0.17152
0.01     10      False   100     100     0.000204979     9.80191e-05     0.478191
0.01     10      False   100     1000    0.000313234     0.000147974     0.472406
0.01     10      False   1000    100     0.00030785      0.000128056     0.415969
0.01     10      False   1000    1000    0.000797414     0.00013211      0.165673
0.01     25      True    100     100     0.000207293     0.000120325     0.580458
0.01     25      True    100     1000    0.000323452     0.000144444     0.44657
0.01     25      True    1000    100     0.000380279     0.000160515     0.422098
0.01     25      True    1000    1000    0.000859035     0.000211458     0.246158
0.01     25      False   100     100     0.000209623     0.000121898     0.58151
0.01     25      False   100     1000    0.000323748     0.000142495     0.440142
0.01     25      False   1000    100     0.000382699     0.000160281     0.418818
0.01     25      False   1000    1000    0.000840479     0.000211661     0.251834
0.2      1       True    100     100     0.000204974     9.70461e-05     0.473455
0.2      1       True    100     1000    0.000346863     0.000153119     0.441439
0.2      1       True    1000    100     0.000320219     0.000115405     0.360393
0.2      1       True    1000    1000    0.00100825      0.000204601     0.202927
0.2      1       False   100     100     0.000216355     9.8609e-05      0.455774
0.2      1       False   100     1000    0.000346128     0.000153136     0.442426
0.2      1       False   1000    100     0.000352324     0.00011737      0.333131
0.2      1       False   1000    1000    0.000990642     0.000205285     0.207224
0.2      10      True    100     100     0.000210795     0.000123959     0.588055
0.2      10      True    100     1000    0.000389961     0.000163421     0.41907
0.2      10      True    1000    100     0.000337358     0.000150689     0.446674
0.2      10      True    1000    1000    0.00108544      0.000857206     0.789729
0.2      10      False   100     100     0.000211931     0.000122924     0.580019
0.2      10      False   100     1000    0.00038925      0.000165562     0.425336
0.2      10      False   1000    100     0.000334816     0.000151162     0.451478
0.2      10      False   1000    1000    0.00109655      0.000843113     0.768877
0.2      25      True    100     100     0.000220397     0.000142263     0.645486
0.2      25      True    100     1000    0.000401368     0.000302446     0.753538
0.2      25      True    1000    100     0.000410934     0.000279523     0.680214
0.2      25      True    1000    1000    0.00127376      0.00244192      1.9171
0.2      25      False   100     100     0.000222309     0.000142203     0.639663
0.2      25      False   100     1000    0.000408741     0.000304749     0.745579
0.2      25      False   1000    100     0.000419264     0.000307255     0.732844
0.2      25      False   1000    1000    0.00126944      0.00249004      1.96152
0.5      1       True    100     100     0.00023428      0.000102918     0.439295
0.5      1       True    100     1000    0.000427166     0.000237494     0.555976
0.5      1       True    1000    100     0.000380724     0.00012818      0.336674
0.5      1       True    1000    1000    0.00160976      0.000481297     0.298987
0.5      1       False   100     100     0.000222527     0.000103388     0.464609
0.5      1       False   100     1000    0.000411102     0.000228725     0.556371
0.5      1       False   1000    100     0.000355794     0.000123535     0.347209
0.5      1       False   1000    1000    0.00141619      0.000490552     0.346388
0.5      10      True    100     100     0.000227675     0.000122795     0.539343
0.5      10      True    100     1000    0.000457623     0.000332977     0.727623
0.5      10      True    1000    100     0.000383134     0.000230231     0.600915
0.5      10      True    1000    1000    0.00156323      0.00226315      1.44774
0.5      10      False   100     100     0.000229292     0.000123618     0.539129
0.5      10      False   100     1000    0.000472363     0.000333602     0.706241
0.5      10      False   1000    100     0.000377634     0.000231078     0.61191
0.5      10      False   1000    1000    0.00157633      0.00225711      1.43188
0.5      25      True    100     100     0.000233055     0.00016205      0.695329
0.5      25      True    100     1000    0.000494024     0.000650206     1.31614
0.5      25      True    1000    100     0.00045893      0.000600457     1.30838
0.5      25      True    1000    1000    0.00186364      0.00606201      3.25278
0.5      25      False   100     100     0.000228475     0.00016268      0.712026
0.5      25      False   100     1000    0.000493242     0.000646534     1.31078
0.5      25      False   1000    100     0.000460567     0.000595119     1.29214
0.5      25      False   1000    1000    0.00167901      0.00613069      3.65137
0.8      1       True    100     100     0.000217078     0.000122763     0.565525
0.8      1       True    100     1000    0.000427521     0.000351477     0.822128
0.8      1       True    1000    100     0.0003469       0.000141773     0.408685
0.8      1       True    1000    1000    0.00148282      0.000691401     0.466273
0.8      1       False   100     100     0.000213548     0.000123152     0.576695
0.8      1       False   100     1000    0.000439499     0.000354205     0.805929
0.8      1       False   1000    100     0.000374365     0.000143963     0.384552
0.8      1       False   1000    1000    0.00138026      0.000737316     0.534186
0.8      10      True    100     100     0.000225083     0.00012419      0.551751
0.8      10      True    100     1000    0.000497607     0.000566593     1.13864
0.8      10      True    1000    100     0.000380098     0.000323333     0.850657
0.8      10      True    1000    1000    0.00164113      0.00375094      2.28558
0.8      10      False   100     100     0.00023011      0.0001231       0.534962
0.8      10      False   100     1000    0.000497115     0.000599468     1.20589
0.8      10      False   1000    100     0.000378207     0.000321302     0.849539
0.8      10      False   1000    1000    0.00163274      0.00371959      2.27813
0.8      25      True    100     100     0.000232235     0.000179456     0.772734
0.8      25      True    100     1000    0.000565002     0.00108429      1.91909
0.8      25      True    1000    100     0.000462347     0.000887741     1.92007
0.8      25      True    1000    1000    0.00187698      0.0105369       5.61375
0.8      25      False   100     100     0.00024654      0.000194484     0.788853
0.8      25      False   100     1000    0.000572626     0.00111752      1.95156
0.8      25      False   1000    100     0.000471096     0.000893812     1.8973
0.8      25      False   1000    1000    0.00188041      0.0104448       5.55452
Change: 114590991

1 files changed, 94 insertions, 0 deletions

diff --git a/tensorflow/core/kernels/sparse_tensor_dense_matmul_op.h b/tensorflow/core/kernels/sparse_tensor_dense_matmul_op.h
new file mode 100644
index 0000000000..aeb1f839a4
--- /dev/null
+++ b/tensorflow/core/kernels/sparse_tensor_dense_matmul_op.h
@@ -0,0 +1,94 @@
+/* Copyright 2015 Google Inc. All Rights Reserved.
+
+Licensed under the Apache License, Version 2.0 (the "License");
+you may not use this file except in compliance with the License.
+You may obtain a copy of the License at
+
+    http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing, software
+distributed under the License is distributed on an "AS IS" BASIS,
+WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+See the License for the specific language governing permissions and
+limitations under the License.
+==============================================================================*/
+
+#ifndef TENSORFLOW_KERNELS_SPARSE_TENSOR_DENSE_MATMUL_OP_H_
+#define TENSORFLOW_KERNELS_SPARSE_TENSOR_DENSE_MATMUL_OP_H_
+
+#include "third_party/eigen3/unsupported/Eigen/CXX11/Tensor"
+#include "tensorflow/core/framework/tensor_types.h"
+
+namespace tensorflow {
+
+namespace functor {
+
+template <typename Device, typename T, bool ADJ_A, bool ADJ_B>
+struct SparseTensorDenseMatMulFunctor {
+  static EIGEN_ALWAYS_INLINE void Compute(const Device& d,
+                                          typename TTypes<T>::Matrix out,
+                                          TTypes<int64>::ConstMatrix a_indices,
+                                          typename TTypes<T>::ConstVec a_values,
+                                          typename TTypes<T>::ConstMatrix b,
+                                          typename TTypes<T>::Vec scratch);
+};
+
+template <typename MATRIX, bool ADJ>
+class MaybeAdjoint;
+
+template <typename MATRIX>
+class MaybeAdjoint<MATRIX, false> {
+ public:
+  EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE MaybeAdjoint(MATRIX m) : m_(m) {}
+  EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE typename MATRIX::Scalar operator()(
+      const typename MATRIX::Index i, const typename MATRIX::Index j) const {
+    return m_(i, j);
+  }
+
+ private:
+  const MATRIX m_;
+};
+
+template <typename T>
+EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE T MaybeConj(T v) {
+  return v;
+}
+
+#ifdef __GCUDACC__
+// TODO(ebrevdo): remove this once a bugfix is in.
+#define MAYBE_CONJ(T)                                         \
+  template <>                                                 \
+  EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE T MaybeConj<T>(T v) { \
+    assert(false && "Conjugation not supported");             \
+  }
+#else
+#define MAYBE_CONJ(T)                                         \
+  template <>                                                 \
+  EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE T MaybeConj<T>(T v) { \
+    return std::conj(v);                                      \
+  }
+#endif
+
+MAYBE_CONJ(std::complex<float>);
+MAYBE_CONJ(std::complex<double>);
+MAYBE_CONJ(std::complex<long double>);
+
+#undef MAYBE_CONJ
+
+template <typename MATRIX>
+class MaybeAdjoint<MATRIX, true> {
+ public:
+  EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE MaybeAdjoint(MATRIX m) : m_(m) {}
+  EIGEN_DEVICE_FUNC EIGEN_STRONG_INLINE typename MATRIX::Scalar operator()(
+      const typename MATRIX::Index i, const typename MATRIX::Index j) const {
+    return MaybeConj(m_(j, i));
+  }
+
+ private:
+  const MATRIX m_;
+};
+
+}  // end namespace functor
+}  // end namespace tensorflow
+
+#endif  // TENSORFLOW_KERNELS_SPARSE_TENSOR_DENSE_MATMUL_OP_H_