Multicolor (independent set) reordering capability on reference executor by Slaedr · Pull Request #2006 · ginkgo-project/ginkgo

Slaedr · 2026-04-23T03:09:47Z

The aim is to have a parallel GPU-capable multicolor ordering using the JPL algorithm. This PR only has the sequential reference implementation and corresponding tests.

Currently, CSR and SparsityCSR inputs are supported.

Also adds a "cores per SM" entry for NVIDIA GB10 GPU.

pratikvn

some initial comments

pratikvn · 2026-04-26T21:16:18Z

+
+    multicolor_reorder(
+        matrix.get(), color_ptrs_, permutation_->get_permutation(),
+        inv_permutation_ ? inv_permutation_->get_permutation() : nullptr);


In the reference kernel atleast, you always seem to compute the inverse permutation, so this would not work.

I'll keep the public option, but throw NOT_IMPLEMENTED if the user requests construct_inverse_permutation to be false.

yhmtsai

you also need to modify test_install.cpp

Slaedr · 2026-04-29T15:53:19Z

@yhmtsai None of the other reorder classes are there in test_install.cpp. Should I still add a check for building a Multicolor object there?

pratikvn

some more comments. But mostly looks good. One general question from my side: Does this reorder setup suit your workflow ? Meaning can you make use of this in your Gauss-Seidel ?

pratikvn · 2026-05-05T08:11:08Z

+}
+
+
+TEST(MatrixGenerator, GeneratesLaplace3d27pointMatrixData)


This test is a little elaborate and hard to read. Maybe you can have a .mtx file generated from MATLAB/Python with the required input, and read it and just compare element by element ?

Are you sure would not rather have a function to generate a 3D stencil matrix of whatever size you want? If so, I guess I would keep mtx files for 4x4 and 4x4x4 grids.

There's another consideration: for the omp and cuda/hip tests, I'd rather use a larger matrix. For that reason, I would prefer to have programmatic generation. I could try to go over the code again to make it clearer.

pratikvn · 2026-05-05T08:17:25Z

+     * The first entry is always 0, since the first color always starts at 0.
+     * The last entry stores the total number of rows.
+     */
+    std::vector<index_type> get_color_pointers() const { return color_ptrs_; }


It might make sense to have this as a gko::array rather than a std::vector.

This makes it explicit that the color_ptrs is always on the host. Do you expect a situation in which someone needs this on the device instead?

@pratikvn I can change the std::vector to gko::array if you say that is preferable, even though I can't (currently) think of a use case where an application will want the color pointers on the device.

I think keeping all internal arrays as gko::array objects is better than having some as std::vector. But if you need some methods of std::vector, then it should be fine.

pratikvn · 2026-05-05T08:18:31Z

+    // assert(permutation.end() == permutation.begin() +
+    // color_ptrs[num_colors]);


Maybe do assert this ?

Looks like this was left over from where I initially implemented this a while back. Since permutation is a raw pointer here, it does not make sense. I'll just remove it.

yhmtsai · 2026-05-05T08:23:38Z

+    // assert(permutation.end() == permutation.begin() +
+    // color_ptrs[num_colors]);


I will uncomment this part for checking?

Looks like this was left over from where I initially implemented this a while back. Since permutation is a raw pointer here, it does not make sense. I'll just remove it.

yhmtsai · 2026-05-05T08:26:51Z

+private:
+    std::shared_ptr<PermutationMatrix> permutation_;
+    std::shared_ptr<PermutationMatrix> inv_permutation_;
+    std::vector<index_type> color_ptrs_;


should color_ptrs always on host? you use color_ptrs to set up permutation. how do you plan on device?

For using this in preconditioners etc., we will need it on the host (to control kernel launches and parameters). So even if the multicolor cuda/hip kernel computes this on the device, it will need to be copied to the host.

okay. then it makes sense to put it in std::vector

yhmtsai · 2026-05-05T08:43:53Z

+    ASSERT_EQ(this->mc_factory->get_executor(), this->exec);
+}
+
+TYPED_TEST(Multicolor, GeneratesCorrectOrderingWithCsrInput)


I think the followings should be in the reference test?

Since this testing a particular generate, I think it should be in core.

pratikvn · 2026-05-11T09:36:37Z

@Slaedr , does the approach of having Multicolor as a reordering work for the goal of having this within GaussSeidel ?

Slaedr · 2026-05-12T21:05:39Z

@pratikvn Yes. I'm not sure if it's best offered as an option within the Gauss-Seidel class(es), since the matrix needs to be modified to obey the ordering. The best workflow is probably to reorder the matrix and then generate GaussSeidel on the reordered matrix, passing in the color pointers. If the user does not supply the color pointers, I guess we could compute and store a reordered copy of the matrix in the generate step.

pratikvn · 2026-05-15T08:55:04Z

@Slaedr , can you please check that you can use reordering as a wrapper for Gauss-Seidel ? If so, then I dont have any other issues with this PR.

pratikvn · 2026-05-11T09:22:17Z

+    if (parameters_.construct_inverse_permutation) {
+        inv_permutation_ = PermutationMatrix::create(exec, size);
+    } else {
+        GKO_NOT_IMPLEMENTED;
+    }


If not constructing an inverse permutation is not allowed, then maybe just remove that factory parameter ?

pratikvn · 2026-05-11T09:33:35Z

+    const auto local_nrows = num_vertices;
+
+    std::vector<int> color(local_nrows, -1);


If we already know the size beforehand, then we should allocate the vector outside the kernel in core.

pratikvn · 2026-05-15T08:56:46Z

+     * The first entry is always 0, since the first color always starts at 0.
+     * The last entry stores the total number of rows.
+     */
+    std::vector<index_type> get_color_pointers() const { return color_ptrs_; }


I think keeping all internal arrays as gko::array objects is better than having some as std::vector. But if you need some methods of std::vector, then it should be fine.

pratikvn reviewed Apr 26, 2026

View reviewed changes

Slaedr added 3 commits April 27, 2026 13:45

added core, reference and tests for Multicolor reordering

dfd74b3

reintroduced accidentally deleted test

5a4db98

addressed unused factory parameter, added documentation

3cae640

Slaedr force-pushed the multicoloring branch from 397c5c7 to 3cae640 Compare April 27, 2026 21:01

yhmtsai reviewed Apr 28, 2026

View reviewed changes

Comment thread core/reorder/multicolor.cpp Outdated

Comment thread core/test/reorder/multicolor.cpp Outdated

Comment thread core/test/reorder/multicolor.cpp Outdated

incorporated review suggestions

d9a59cf

Slaedr added 2 commits April 30, 2026 10:05

added cores per SM for NVIDIA GB10

aa97fea

fixed build issue in cuda_hip

b51783d

Slaedr requested review from pratikvn and yhmtsai April 30, 2026 15:13

pratikvn requested changes May 5, 2026

View reviewed changes

yhmtsai reviewed May 5, 2026

View reviewed changes

review comments - minor

2356752

pratikvn requested changes May 15, 2026

View reviewed changes

		// assert(permutation.end() == permutation.begin() +
		// color_ptrs[num_colors]);

		const auto local_nrows = num_vertices;

		std::vector<int> color(local_nrows, -1);

		}


		TEST(MatrixGenerator, GeneratesLaplace3d27pointMatrixData)

Conversation

Slaedr commented Apr 23, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

pratikvn left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

yhmtsai left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Slaedr commented Apr 29, 2026

Uh oh!

pratikvn left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Slaedr May 12, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

pratikvn commented May 11, 2026

Uh oh!

Slaedr commented May 12, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

pratikvn commented May 15, 2026

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Slaedr commented Apr 23, 2026 •

edited

Loading

Slaedr May 12, 2026 •

edited

Loading

Slaedr commented May 12, 2026 •

edited

Loading