)]}' { "commit": "b1fe60330559371c9e985886412ae2d39b581fe3", "tree": "ef572ab94ee4f7215e75aa88245d150baf8927a4", "parents": [ "16668eedf34f1bba70649b381a60ad9d26972064" ], "author": { "name": "Dmitriy Korchemkin", "email": "dmitriy.korchemkin@gmail.com", "time": "Wed Sep 07 16:06:51 2022 +0300" }, "committer": { "name": "Dmitriy Korchemkin", "email": "dmitriy.korchemkin@gmail.com", "time": "Fri Sep 30 17:23:13 2022 +0300" }, "message": "Parallel right products for partitioned view\n\nParallel implementations for right-multiply by dense vector for:\n - Partitioned matrix view\n - Block-sparse matrix\n - CRS matrix (non-symmetric only)\n\nWhen coupled with non-interleaving indexes in parallel for, this\nsimple aproach provides a reasonable speedup.\nFor example, in CRS case difference with GPGPU approach reduces\ncloser to memory throughput ratio for high enough core count.\n\n./bin/spmv_benchmark\n-------------------------------------------------------------------\nBenchmark Time\n-------------------------------------------------------------------\nBM_BlockSparseRightMultiplyAndAccumulateBA/1 28.5 ms\nBM_BlockSparseRightMultiplyAndAccumulateBA/2 15.7 ms\nBM_BlockSparseRightMultiplyAndAccumulateBA/4 9.01 ms\nBM_BlockSparseRightMultiplyAndAccumulateBA/8 5.60 ms\nBM_BlockSparseRightMultiplyAndAccumulateBA/16 3.86 ms\nBM_BlockSparseRightMultiplyAndAccumulateBA/28 3.84 ms\nBM_BlockSparseRightMultiplyAndAccumulateUnstructured/1 23.8 ms\nBM_BlockSparseRightMultiplyAndAccumulateUnstructured/2 15.0 ms\nBM_BlockSparseRightMultiplyAndAccumulateUnstructured/4 8.01 ms\nBM_BlockSparseRightMultiplyAndAccumulateUnstructured/8 4.02 ms\nBM_BlockSparseRightMultiplyAndAccumulateUnstructured/16 2.39 ms\nBM_BlockSparseRightMultiplyAndAccumulateUnstructured/28 1.68 ms\nBM_BlockSparseLeftMultiplyAndAccumulateBA 30.7 ms\nBM_BlockSparseLeftMultiplyAndAccumulateUnstructured 41.5 ms\nBM_CRSRightMultiplyAndAccumulateBA/1 24.1 ms\nBM_CRSRightMultiplyAndAccumulateBA/2 13.6 ms\nBM_CRSRightMultiplyAndAccumulateBA/4 8.70 ms\nBM_CRSRightMultiplyAndAccumulateBA/8 5.34 ms\nBM_CRSRightMultiplyAndAccumulateBA/16 3.99 ms\nBM_CRSRightMultiplyAndAccumulateBA/28 4.00 ms\nBM_CRSRightMultiplyAndAccumulateUnstructured/1 21.1 ms\nBM_CRSRightMultiplyAndAccumulateUnstructured/2 10.83 ms\nBM_CRSRightMultiplyAndAccumulateUnstructured/4 5.88 ms\nBM_CRSRightMultiplyAndAccumulateUnstructured/8 3.68 ms\nBM_CRSRightMultiplyAndAccumulateUnstructured/16 2.21 ms\nBM_CRSRightMultiplyAndAccumulateUnstructured/28 1.71 ms\nBM_CRSLeftMultiplyAndAccumulateBA 23.6 ms\nBM_CRSLeftMultiplyAndAccumulateUnstructured 22.5 ms\nBM_CudaRightMultiplyAndAccumulateBA 0.679 ms\nBM_CudaRightMultiplyAndAccumulateUnstructured 0.480 ms\nBM_CudaLeftMultiplyAndAccumulateBA 0.774 ms\nBM_CudaLeftMultiplyAndAccumulateUnstructured 0.361 ms\n\n./bin/partitioned_matrix_view_benchmark\n-----------------------------------------------------------------\nBenchmark Time\n-----------------------------------------------------------------\nBM_PatitionedViewRightMultiplyAndAccumulateE_Static/1 18.5 ms\nBM_PatitionedViewRightMultiplyAndAccumulateE_Static/2 10.7 ms\nBM_PatitionedViewRightMultiplyAndAccumulateE_Static/4 6.34 ms\nBM_PatitionedViewRightMultiplyAndAccumulateE_Static/8 4.26 ms\nBM_PatitionedViewRightMultiplyAndAccumulateE_Static/16 3.86 ms\nBM_PatitionedViewRightMultiplyAndAccumulateE_Static/28 3.75 ms\nBM_PatitionedViewRightMultiplyAndAccumulateF_Static/1 18.8 ms\nBM_PatitionedViewRightMultiplyAndAccumulateF_Static/2 11.9 ms\nBM_PatitionedViewRightMultiplyAndAccumulateF_Static/4 6.94 ms\nBM_PatitionedViewRightMultiplyAndAccumulateF_Static/8 4.41 ms\nBM_PatitionedViewRightMultiplyAndAccumulateF_Static/16 3.63 ms\nBM_PatitionedViewRightMultiplyAndAccumulateF_Static/28 3.86 ms\n\nTimings correspond to intel 8176 cpu and 2080ti nvidia gpu,\nwith OpenMP threading backend.\n\nChange-Id: Idc07d0563103d057ca3c8412de81a7823fe232af\n", "tree_diff": [ { "type": "modify", "old_id": "fef1c2db117e9b2aacd5475208a3e8bbd7ac8612", "old_mode": 33188, "old_path": "internal/ceres/CMakeLists.txt", "new_id": "350b3b5754ed02118e3d830f6acd2f71177cb56e", "new_mode": 33188, "new_path": "internal/ceres/CMakeLists.txt" }, { "type": "modify", "old_id": "0401696cbff7cee14f04d0efe35c3601d36e3706", "old_mode": 33188, "old_path": "internal/ceres/block_sparse_matrix.cc", "new_id": "0dd3b204d9ca1ec38123209019eeb345c03f2848", "new_mode": 33188, "new_path": "internal/ceres/block_sparse_matrix.cc" }, { "type": "modify", "old_id": "b7ea1df9ab246a52abb503fbbc626bdb9ef7ec51", "old_mode": 33188, "old_path": "internal/ceres/block_sparse_matrix.h", "new_id": "3a8dac99353f22269b992091dbd30b25e5d98e0f", "new_mode": 33188, "new_path": "internal/ceres/block_sparse_matrix.h" }, { "type": "modify", "old_id": "7d7d4c9160b1540d79345e9512eb8586d71ee7b1", "old_mode": 33188, "old_path": "internal/ceres/block_sparse_matrix_test.cc", "new_id": "3f5c78a780557e46476f07bff07bd44b3574c38f", "new_mode": 33188, "new_path": "internal/ceres/block_sparse_matrix_test.cc" }, { "type": "modify", "old_id": "17a5f6215ad124f1b1a2167089a4418b1e444bf3", "old_mode": 33188, "old_path": "internal/ceres/cgnr_solver.cc", "new_id": "e1c571d683d58d7cdc2bb9d5d54b6616c9967590", "new_mode": 33188, "new_path": "internal/ceres/cgnr_solver.cc" }, { "type": "modify", "old_id": "057adfd01f231ac25b02332f41c6eae89a2a3d54", "old_mode": 33188, "old_path": "internal/ceres/compressed_row_sparse_matrix.cc", "new_id": "553dc21aab6b4790fe2b4dfb00780deaed7bbef5", "new_mode": 33188, "new_path": "internal/ceres/compressed_row_sparse_matrix.cc" }, { "type": "modify", "old_id": "8668d06b0640b067da6a1e16d9f96e9e7709eaae", "old_mode": 33188, "old_path": "internal/ceres/compressed_row_sparse_matrix.h", "new_id": "6fe730ecb0b3c9d6d40b034b7cda1b2a5cb188fd", "new_mode": 33188, "new_path": "internal/ceres/compressed_row_sparse_matrix.h" }, { "type": "modify", "old_id": "82c982bc26e9bbc02e16789a27ea2a9781827046", "old_mode": 33188, "old_path": "internal/ceres/compressed_row_sparse_matrix_test.cc", "new_id": "46136dbfa64874b70de67631266aaea892080691", "new_mode": 33188, "new_path": "internal/ceres/compressed_row_sparse_matrix_test.cc" }, { "type": "modify", "old_id": "9e7d82b3f5709ad767526889d431780570d656b7", "old_mode": 33188, "old_path": "internal/ceres/fake_bundle_adjustment_jacobian.cc", "new_id": "dd2aee8493b3a238211d250b488cc8bb2ba20eaa", "new_mode": 33188, "new_path": "internal/ceres/fake_bundle_adjustment_jacobian.cc" }, { "type": "modify", "old_id": "9492b52d984b5ee54f9a331fe9769f7695346825", "old_mode": 33188, "old_path": "internal/ceres/fake_bundle_adjustment_jacobian.h", "new_id": "41b55c8c667cd62d97daecd2fe1edffbf63fa36d", "new_mode": 33188, "new_path": "internal/ceres/fake_bundle_adjustment_jacobian.h" }, { "type": "modify", "old_id": "9b7ee47405d9a85af190fc48e54b247a02c9ab20", "old_mode": 33188, "old_path": "internal/ceres/implicit_schur_complement.cc", "new_id": "bbd5e4b3b461bf1ccedb8e9f7089d73884c26fdd", "new_mode": 33188, "new_path": "internal/ceres/implicit_schur_complement.cc" }, { "type": "modify", "old_id": "597a37e77a88be268586f64ff78093195e97e837", "old_mode": 33188, "old_path": "internal/ceres/linear_operator.cc", "new_id": "1b518a6163cea32d06bf6e8549d4edb10d98d3f1", "new_mode": 33188, "new_path": "internal/ceres/linear_operator.cc" }, { "type": "modify", "old_id": "8a1e902d23136538e592164292a4e9bd883af712", "old_mode": 33188, "old_path": "internal/ceres/linear_operator.h", "new_id": "76beb4064d954b60c0ed5c12d236e1ff2345d9aa", "new_mode": 33188, "new_path": "internal/ceres/linear_operator.h" }, { "type": "modify", "old_id": "7fb1a095d7789476108cfec8303659fbf11832a2", "old_mode": 33188, "old_path": "internal/ceres/partitioned_matrix_view.h", "new_id": "86106da8e5b62790d466d5e1a81150d9927afc92", "new_mode": 33188, "new_path": "internal/ceres/partitioned_matrix_view.h" }, { "type": "add", "old_id": "0000000000000000000000000000000000000000", "old_mode": 0, "old_path": "/dev/null", "new_id": "63d0e344e8d92c3622bf3321e4662c5af5ead307", "new_mode": 33188, "new_path": "internal/ceres/partitioned_matrix_view_benchmark.cc" }, { "type": "modify", "old_id": "2150660629326ad7209b9ed443068c8d6ab5842e", "old_mode": 33188, "old_path": "internal/ceres/partitioned_matrix_view_impl.h", "new_id": "fea0a7dfc0a18afd027a0755210cf48b0a065047", "new_mode": 33188, "new_path": "internal/ceres/partitioned_matrix_view_impl.h" }, { "type": "modify", "old_id": "e4484dd050cd94e3df0e2817f0c4d963a0031c3b", "old_mode": 33188, "old_path": "internal/ceres/partitioned_matrix_view_test.cc", "new_id": "b11ea8e19a293bf740196fc434327e41479f3433", "new_mode": 33188, "new_path": "internal/ceres/partitioned_matrix_view_test.cc" }, { "type": "modify", "old_id": "a291405a58af1bfd26d63a35e38f8dfca01bbf29", "old_mode": 33188, "old_path": "internal/ceres/power_series_expansion_preconditioner_test.cc", "new_id": "233d4f722ed2be891cf9c2698324c2d540ceafb9", "new_mode": 33188, "new_path": "internal/ceres/power_series_expansion_preconditioner_test.cc" }, { "type": "modify", "old_id": "da6af184e9525628fce825be8fc8620c4776662e", "old_mode": 33188, "old_path": "internal/ceres/sparse_matrix.h", "new_id": "e665c8ba682dcf4dc464fe98fd2671f319f52804", "new_mode": 33188, "new_path": "internal/ceres/sparse_matrix.h" }, { "type": "modify", "old_id": "0bd1e43243c8d98bb22d6ef37495253ff6684d64", "old_mode": 33188, "old_path": "internal/ceres/spmv_benchmark.cc", "new_id": "69df1ea2f8913344b19524019ed9e058e608d69a", "new_mode": 33188, "new_path": "internal/ceres/spmv_benchmark.cc" } ] }