Re: [petsc-dev] do all MIS algorithms require a symmetric structure?

[Mark Adams]

On Sun, Sep 18, 2022 at 7:04 PM Barry Smith  wrote:

>
>   Right, but I want to run with the old options MIS (instead of MIS-2) and
> get the same times as before. But instead I am getting much larger times.
>

Yea, the new MIS is noticeably slower

New:
petsc/src/ksp/ksp/tutorials$ mpiexec -n 4 ./ex55 -ne 511 -ksp_type cg
-pc_type gamg -log_view -pc_gamg_square_graph 0 -mat_coarsen_type misk
PCSetUp_GAMG+  1 1.0 6.8526e-01 1.0 2.14e+08 1.0 1.2e+03 6.3e+03
7.3e+02 44 21 28 38 88 100100100100100  1242
 GAMG Coarsen  5 1.0 5.7050e-02 1.0 0.00e+00 0.0 3.0e+02 7.1e+02
1.5e+02  4  0  7  1 18   8  0 26  3 20 0
  GAMG MIS/Agg 5 1.0 5.0056e-02 1.0 0.00e+00 0.0 3.0e+02 7.1e+02
1.5e+02  3  0  7  1 18   7  0 26  3 20 0

Old:
petsc/src/ksp/ksp/tutorials$ mpiexec -n 4 ./ex55 -ne 511 -ksp_type cg
-pc_type gamg -log_view -pc_gamg_square_graph 0 *-mat_coarsen_type mis*
...
PCSetUp_GAMG+  1 1.0 6.7866e-01 1.0 2.14e+08 1.0 1.1e+03 7.1e+03
5.9e+02 43 21 26 39 85 100100100100100  1254
 GAMG Coarsen  5 1.0 1.3564e-02 1.0 0.00e+00 0.0 1.6e+02 9.6e+02
1.5e+01  1  0  4  1  2   2  0 15  2  3 0
  GAMG MIS/Agg 5 1.0 7.5110e-03 1.0 0.00e+00 0.0 1.6e+02 9.6e+02
1.5e+01  0  0  4  1  2   1  0 15  2  3 0

Same in serial:

(conda_env) 05:15 adams/landau-ex13-fixes=
~/Codes/petsc/src/ksp/ksp/tutorials$ mpiexec -n 1 ./ex55 -ne 511 -ksp_type
cg -pc_type gamg -log_view -pc_gamg_square_graph 0 *-mat_coarsen_type mis*
| g MIS
  GAMG MIS/Agg 5 1.0 *3.7858e-02* 1.0 0.00e+00 0.0 0.0e+00 0.0e+00
0.0e+00  1  0  0  0  0   2  0  0  0  0 0
(conda_env) 05:16 adams/landau-ex13-fixes=
~/Codes/petsc/src/ksp/ksp/tutorials$ mpiexec -n 1 ./ex55 -ne 511 -ksp_type
cg -pc_type gamg -log_view -pc_gamg_square_graph 0 -mat_coarsen_type misk |
g MIS
  GAMG MIS/Agg 5 1.0 *8.5015e-02* 1.0 0.00e+00 0.0 0.0e+00 0.0e+00
0.0e+00  3  0  0  0  0   5  0  0  0  0 0

I did find that there is an unneeded MatDuplicate in MISk with just one MIS
(MIS-1), but it is still slower than the old:

(conda_env) 05:31 adams/landau-ex13-fixes *=
~/Codes/petsc/src/ksp/ksp/tutorials$ mpiexec -n 1 ./ex55 -ne 511 -ksp_type
cg -pc_type gamg -log_view -pc_gamg_square_graph 0 -mat_coarsen_type misk |
g MIS
  GAMG MIS/Agg 5 1.0 *5.9566e-02* 1.0 0.00e+00 0.0 0.0e+00 0.0e+00
0.0e+00  2  0  0  0  0   4  0  0  0  0 0

MISk is organized differently and goes through some hoops that the old MIS
does not do that are not as easy as the MatDuplicate to avoid.

Mark


>
> On Sep 18, 2022, at 6:58 PM, Mark Adams  wrote:
>
>
>
> On Sun, Sep 18, 2022 at 6:19 PM Barry Smith  wrote:
>
>>
>>   Mark,
>>
>> Some how your changes to GAMG in June slowed down the time to compute
>> the MIS dramatically. I cannot figure out what options to use to
>> get the exact same performance as an older branch. -mat_coarsen_type mis
>> -pc_gamg_threshold 0 result in longer times than the older code with its
>> default options.
>>
>
> The new MIS-2 folds in the square graph with the MIS. Before the square
> graph was in a separate method that created an squared graph explicitly.
> So don't use aggressive coarsening (you will see a PtAP if you use
> aggressive coarsening in the new code)
> And -pc_gamg_threshold 0 will filter (zeros only). Use < 0 for no
> filtering.
> The old code also had this optimization to not create a graph for bs==1
> and no filter,
>
> Mark
>
>
>>
>>
>>
>> On Sep 18, 2022, at 4:21 PM, Mark Adams  wrote:
>>
>>
>>
>> On Sun, Sep 18, 2022 at 4:02 PM Barry Smith  wrote:
>>
>>>
>>>   Mark,
>>>
>>>Do all MIS algorithms  in PETSc require a symmetric graph structure?
>>> And parallel ones can hang if not structurally symmetric?
>>>
>>
>> Yes,
>>
>>
>>>
>>>When used sequentially I guess it never hangs but it may not produce
>>> a "correct" MIS if the matrix structure is not symmetric?
>>
>>
>> It is fine in serial and it is not necessarily an MIS of the
>> symmetrized graph.
>> If there is a one way edge between two vertices and the order of the
>> greedy MIS process picks the root of the edge it is an MIS of the
>> symmetrized graph, otherwise both vertices could get selected.
>>
>>
>>> But like the MIS is fine for GAMG in this circumstance?
>>>
>>
>> It will be fine for GAMG. The MIS is just a heuristic.
>>
>>
>>>
>>>   Barry
>>>
>>>
>>
>

Re: [petsc-dev] do all MIS algorithms require a symmetric structure?

[Barry Smith]

  Right, but I want to run with the old options MIS (instead of MIS-2) and get 
the same times as before. But instead I am getting much larger times.

> On Sep 18, 2022, at 6:58 PM, Mark Adams  wrote:
> 
> 
> 
> On Sun, Sep 18, 2022 at 6:19 PM Barry Smith  > wrote:
> 
>   Mark,
> 
> Some how your changes to GAMG in June slowed down the time to compute the 
> MIS dramatically. I cannot figure out what options to use to 
> get the exact same performance as an older branch. -mat_coarsen_type mis 
> -pc_gamg_threshold 0 result in longer times than the older code with its 
> default options.
> 
> The new MIS-2 folds in the square graph with the MIS. Before the square graph 
> was in a separate method that created an squared graph explicitly.  So don't 
> use aggressive coarsening (you will see a PtAP if you use aggressive 
> coarsening in the new code)
> And -pc_gamg_threshold 0 will filter (zeros only). Use < 0 for no filtering.
> The old code also had this optimization to not create a graph for bs==1 and 
> no filter,
> 
> Mark
>  
> 
> 
> 
>> On Sep 18, 2022, at 4:21 PM, Mark Adams > > wrote:
>> 
>> 
>> 
>> On Sun, Sep 18, 2022 at 4:02 PM Barry Smith > > wrote:
>> 
>>   Mark,
>> 
>>Do all MIS algorithms  in PETSc require a symmetric graph structure? And 
>> parallel ones can hang if not structurally symmetric?
>> 
>> Yes,
>>  
>> 
>>When used sequentially I guess it never hangs but it may not produce a 
>> "correct" MIS if the matrix structure is not symmetric?
>> 
>> It is fine in serial and it is not necessarily an MIS of the symmetrized 
>> graph.
>> If there is a one way edge between two vertices and the order of the greedy 
>> MIS process picks the root of the edge it is an MIS of the symmetrized 
>> graph, otherwise both vertices could get selected.
>>  
>> But like the MIS is fine for GAMG in this circumstance?
>> 
>> It will be fine for GAMG. The MIS is just a heuristic.
>>  
>> 
>>   Barry
>> 
> 

Re: [petsc-dev] do all MIS algorithms require a symmetric structure?

[Mark Adams]

On Sun, Sep 18, 2022 at 6:19 PM Barry Smith  wrote:

>
>   Mark,
>
> Some how your changes to GAMG in June slowed down the time to compute
> the MIS dramatically. I cannot figure out what options to use to
> get the exact same performance as an older branch. -mat_coarsen_type mis
> -pc_gamg_threshold 0 result in longer times than the older code with its
> default options.
>

The new MIS-2 folds in the square graph with the MIS. Before the square
graph was in a separate method that created an squared graph explicitly.
So don't use aggressive coarsening (you will see a PtAP if you use
aggressive coarsening in the new code)
And -pc_gamg_threshold 0 will filter (zeros only). Use < 0 for no filtering.
The old code also had this optimization to not create a graph for bs==1 and
no filter,

Mark


>
>
>
> On Sep 18, 2022, at 4:21 PM, Mark Adams  wrote:
>
>
>
> On Sun, Sep 18, 2022 at 4:02 PM Barry Smith  wrote:
>
>>
>>   Mark,
>>
>>Do all MIS algorithms  in PETSc require a symmetric graph structure?
>> And parallel ones can hang if not structurally symmetric?
>>
>
> Yes,
>
>
>>
>>When used sequentially I guess it never hangs but it may not produce a
>> "correct" MIS if the matrix structure is not symmetric?
>
>
> It is fine in serial and it is not necessarily an MIS of the
> symmetrized graph.
> If there is a one way edge between two vertices and the order of the
> greedy MIS process picks the root of the edge it is an MIS of the
> symmetrized graph, otherwise both vertices could get selected.
>
>
>> But like the MIS is fine for GAMG in this circumstance?
>>
>
> It will be fine for GAMG. The MIS is just a heuristic.
>
>
>>
>>   Barry
>>
>>
>

Re: [petsc-dev] do all MIS algorithms require a symmetric structure?

[Mark Adams]

On Sun, Sep 18, 2022 at 5:11 PM Barry Smith  wrote:

>
>Does the MIS you use, use the numerical values in the matrix? Looking
> at the code it looks like not, while hem does seems to use them.
>

Yes. numerical values are used in the filtering.


>
>But MatCreateGraph() seems to always get the numerical values, makes
> them positive and then scales them by the diagonal even when no filtering
> will be done. Can this be optimized out for no filtering and not HEM (for
> scalar matrices it looks like even the MatDuplicate() is not needed since
> it just processes a copy of the original matrix?)
>

Yes, it used to do that. There was code like if (Gmat1 != GMat2)
Destroy(Gmat1)
etc,
It looks like that was lost in the refactoring.
Maybe at gamg.c:634 check for bs==1 and no filtering and set Gmat
= Aarr[level];
Then check for this when Gmat is destroyed later.


>
>I think the current parallel symmetrization could be optimized
> especially when one doe not need numerical values. Probably can be done
> faster than MatTranspose() followed by MatMAXPY()
>

OK. It seems to me that the values just piggyback on the column indices,
but maybe.


>
>The MIS also seems to slow down with multiple MPI ranks.
>

I have never profiled this code carefully, It just does a nearest neighbor
exchange a few times, once for each iteration of the MIS.
That code and data structure is very old.
It could well be improved.
I have noticed that for the aggressive coarsening, with the square
graph-like thing, 80% of the time is in the PtAP that I use to create an
intermediate level matrix.


>
>These combine to make the total time to solution much slower in
> parallel than sequential for GAMG, while all the rest of GAMG gets good
> speedup.
>

You could compare with hypre to get an idea of the relative speed and
scaling.
The code uses a Fortran style linked list to collect selected vertices and
the vertices that it "deleted".
Then sends all the processors that see the selected and deleted vertices
the new state.
This code is 25 years old.


>Is there a parallel coarse grid point selector that would be faster and
> not have the parallel bottle necks that could be coded up relatively easily?
>

I got a best student paper award at Copper '98.
https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.3040=8
This paper discusses the parallel algotithm.
The algorithm is fine, but I could see the implementations could be bad.
Its not that much code.

Mark


>
>  Barry
>
>
> On Sep 18, 2022, at 4:21 PM, Mark Adams  wrote:
>
>
>
> On Sun, Sep 18, 2022 at 4:02 PM Barry Smith  wrote:
>
>>
>>   Mark,
>>
>>Do all MIS algorithms  in PETSc require a symmetric graph structure?
>> And parallel ones can hang if not structurally symmetric?
>>
>
> Yes,
>
>
>>
>>When used sequentially I guess it never hangs but it may not produce a
>> "correct" MIS if the matrix structure is not symmetric?
>
>
> It is fine in serial and it is not necessarily an MIS of the
> symmetrized graph.
> If there is a one way edge between two vertices and the order of the
> greedy MIS process picks the root of the edge it is an MIS of the
> symmetrized graph, otherwise both vertices could get selected.
>
>
>> But like the MIS is fine for GAMG in this circumstance?
>>
>
> It will be fine for GAMG. The MIS is just a heuristic.
>
>
>>
>>   Barry
>>
>>
>

Re: [petsc-dev] do all MIS algorithms require a symmetric structure?

[Barry Smith]

  Mark,

Some how your changes to GAMG in June slowed down the time to compute the 
MIS dramatically. I cannot figure out what options to use to 
get the exact same performance as an older branch. -mat_coarsen_type mis 
-pc_gamg_threshold 0 result in longer times than the older code with its 
default options.



> On Sep 18, 2022, at 4:21 PM, Mark Adams  wrote:
> 
> 
> 
> On Sun, Sep 18, 2022 at 4:02 PM Barry Smith  > wrote:
> 
>   Mark,
> 
>Do all MIS algorithms  in PETSc require a symmetric graph structure? And 
> parallel ones can hang if not structurally symmetric?
> 
> Yes,
>  
> 
>When used sequentially I guess it never hangs but it may not produce a 
> "correct" MIS if the matrix structure is not symmetric?
> 
> It is fine in serial and it is not necessarily an MIS of the symmetrized 
> graph.
> If there is a one way edge between two vertices and the order of the greedy 
> MIS process picks the root of the edge it is an MIS of the symmetrized graph, 
> otherwise both vertices could get selected.
>  
> But like the MIS is fine for GAMG in this circumstance?
> 
> It will be fine for GAMG. The MIS is just a heuristic.
>  
> 
>   Barry
> 

Re: [petsc-dev] do all MIS algorithms require a symmetric structure?

[Barry Smith]

   Does the MIS you use, use the numerical values in the matrix? Looking at the 
code it looks like not, while hem does seems to use them.

   But MatCreateGraph() seems to always get the numerical values, makes them 
positive and then scales them by the diagonal even when no filtering will be 
done. Can this be optimized out for no filtering and not HEM (for scalar 
matrices it looks like even the MatDuplicate() is not needed since it just 
processes a copy of the original matrix?)

   I think the current parallel symmetrization could be optimized especially 
when one doe not need numerical values. Probably can be done faster than 
MatTranspose() followed by MatMAXPY()

   The MIS also seems to slow down with multiple MPI ranks.

   These combine to make the total time to solution much slower in parallel 
than sequential for GAMG, while all the rest of GAMG gets good speedup. 

   Is there a parallel coarse grid point selector that would be faster and not 
have the parallel bottle necks that could be coded up relatively easily?

 Barry


> On Sep 18, 2022, at 4:21 PM, Mark Adams  wrote:
> 
> 
> 
> On Sun, Sep 18, 2022 at 4:02 PM Barry Smith  > wrote:
> 
>   Mark,
> 
>Do all MIS algorithms  in PETSc require a symmetric graph structure? And 
> parallel ones can hang if not structurally symmetric?
> 
> Yes,
>  
> 
>When used sequentially I guess it never hangs but it may not produce a 
> "correct" MIS if the matrix structure is not symmetric?
> 
> It is fine in serial and it is not necessarily an MIS of the symmetrized 
> graph.
> If there is a one way edge between two vertices and the order of the greedy 
> MIS process picks the root of the edge it is an MIS of the symmetrized graph, 
> otherwise both vertices could get selected.
>  
> But like the MIS is fine for GAMG in this circumstance?
> 
> It will be fine for GAMG. The MIS is just a heuristic.
>  
> 
>   Barry
> 

Re: [petsc-dev] do all MIS algorithms require a symmetric structure?

[Mark Adams]

On Sun, Sep 18, 2022 at 4:02 PM Barry Smith  wrote:

>
>   Mark,
>
>Do all MIS algorithms  in PETSc require a symmetric graph structure?
> And parallel ones can hang if not structurally symmetric?
>

Yes,


>
>When used sequentially I guess it never hangs but it may not produce a
> "correct" MIS if the matrix structure is not symmetric?


It is fine in serial and it is not necessarily an MIS of the
symmetrized graph.
If there is a one way edge between two vertices and the order of the greedy
MIS process picks the root of the edge it is an MIS of the symmetrized
graph, otherwise both vertices could get selected.


> But like the MIS is fine for GAMG in this circumstance?
>

It will be fine for GAMG. The MIS is just a heuristic.


>
>   Barry
>
>