1 /* Copyright 2007,2008,2011,2014 IPB, Universite de Bordeaux, INRIA & CNRS
2 **
3 ** This file is part of the Scotch software package for static mapping,
4 ** graph partitioning and sparse matrix ordering.
5 **
6 ** This software is governed by the CeCILL-C license under French law
7 ** and abiding by the rules of distribution of free software. You can
8 ** use, modify and/or redistribute the software under the terms of the
9 ** CeCILL-C license as circulated by CEA, CNRS and INRIA at the following
10 ** URL: "http://www.cecill.info".
11 **
12 ** As a counterpart to the access to the source code and rights to copy,
13 ** modify and redistribute granted by the license, users are provided
14 ** only with a limited warranty and the software's author, the holder of
15 ** the economic rights, and the successive licensors have only limited
16 ** liability.
17 **
18 ** In this respect, the user's attention is drawn to the risks associated
19 ** with loading, using, modifying and/or developing or reproducing the
20 ** software by the user in light of its specific status of free software,
21 ** that may mean that it is complicated to manipulate, and that also
22 ** therefore means that it is reserved for developers and experienced
23 ** professionals having in-depth computer knowledge. Users are therefore
24 ** encouraged to load and test the software's suitability as regards
25 ** their requirements in conditions enabling the security of their
26 ** systems and/or data to be ensured and, more generally, to use and
27 ** operate it in the same conditions as regards security.
28 **
29 ** The fact that you are presently reading this means that you have had
30 ** knowledge of the CeCILL-C license and that you accept its terms.
31 */
32 /************************************************************/
33 /** **/
34 /** NAME : bdgraph.c **/
35 /** **/
36 /** AUTHOR : Jun-Ho HER (v6.0) **/
37 /** Francois PELLEGRINI **/
38 /** **/
39 /** FUNCTION : This module contains the distributed **/
40 /** bipartitioning graph data structure **/
41 /** handling routines. **/
42 /** **/
43 /** DATES : # Version 5.1 : from : 10 sep 2007 **/
44 /** to 14 apr 2011 **/
45 /** # Version 6.0 : from : 11 sep 2011 **/
46 /** to 31 aug 2014 **/
47 /** **/
48 /************************************************************/
49
50 /*
51 ** The defines and includes.
52 */
53
54 #define BDGRAPH
55
56 #include "module.h"
57 #include "common.h"
58 #include "arch.h"
59 #include "dgraph.h"
60 #include "dmapping.h"
61 #include "bdgraph.h"
62
63 /*************************************/
64 /* */
65 /* These routines handle distributed */
66 /* bipartition graphs. */
67 /* */
68 /*************************************/
69
70 /* This routine builds the active graph
71 ** corresponding to the given bipartitioning
72 ** job parameters.
73 ** It returns:
74 ** - 0 : on success.
75 ** - !0 : on error.
76 */
77
78 int
bdgraphInit(Bdgraph * restrict const actgrafptr,const Dgraph * restrict const indgrafptr,const Dgraph * restrict const srcgrafptr,const Arch * restrict const archptr,const ArchDom domnsubtab[])79 bdgraphInit (
80 Bdgraph * restrict const actgrafptr, /* Active graph */
81 const Dgraph * restrict const indgrafptr, /* Induced source subdgraph */
82 const Dgraph * restrict const srcgrafptr, /* Original source graph */
83 const Arch * restrict const archptr, /* Current mapping of halo vertices */
84 const ArchDom domnsubtab[]) /* Subdomains */
85 {
86 Anum domndist; /* Distance between both subdomains */
87 Anum domnwght0; /* Processor workforce in each domain */
88 Anum domnwght1;
89
90 domndist = archDomDist (archptr, &domnsubtab[0], &domnsubtab[1]); /* Get distance between subdomains */
91 domnwght0 = archDomWght (archptr, &domnsubtab[0]); /* Get weights of subdomains */
92 domnwght1 = archDomWght (archptr, &domnsubtab[1]);
93 actgrafptr->s = *indgrafptr; /* Get source graph data */
94 actgrafptr->s.flagval &= ~DGRAPHFREEALL; /* Do not free contents of separation graph */
95 actgrafptr->s.vlblloctax = NULL; /* Never mind about vertex labels in the future */
96 actgrafptr->veexloctax = NULL; /* No external gain (yet) */
97 actgrafptr->veexglbsum = 0;
98 actgrafptr->partgsttax = NULL; /* Do not allocate frontier arrays yet */
99 actgrafptr->fronloctab = NULL;
100
101 bdgraphInit2 (actgrafptr, domndist, domnwght0, domnwght1);
102
103 /* TODO: Compute external gains */
104
105 #ifdef SCOTCH_DEBUG_BDGRAPH2
106 if (bdgraphCheck (actgrafptr) != 0) {
107 errorPrint ("bdgraphInit: inconsistent graph data");
108 return (1);
109 }
110 #endif /* SCOTCH_DEBUG_BDGRAPH2 */
111
112 return (0);
113 }
114
115 void
bdgraphInit2(Bdgraph * restrict const actgrafptr,const Anum domndist,const Anum domnwght0,const Anum domnwght1)116 bdgraphInit2 (
117 Bdgraph * restrict const actgrafptr, /* Active graph */
118 const Anum domndist, /* Distance between both subdomains */
119 const Anum domnwght0, /* Processor workforce in each domain */
120 const Anum domnwght1)
121 {
122 actgrafptr->fronlocnbr = /* No frontier vertices */
123 actgrafptr->fronglbnbr = 0;
124 actgrafptr->complocload0 = actgrafptr->s.velolocsum;
125 actgrafptr->compglbload0 = actgrafptr->s.veloglbsum;
126 actgrafptr->compglbload0min = 0; /* No external constraints on bipartition (yet) */
127 actgrafptr->compglbload0max = actgrafptr->s.veloglbsum;
128 actgrafptr->compglbload0avg = (Gnum) (((double) actgrafptr->s.veloglbsum * (double) domnwght0) / (double) (domnwght0 + domnwght1));
129 actgrafptr->compglbload0dlt = actgrafptr->s.veloglbsum - actgrafptr->compglbload0avg;
130 actgrafptr->complocsize0 = actgrafptr->s.vertlocnbr;
131 actgrafptr->compglbsize0 = actgrafptr->s.vertglbnbr;
132 actgrafptr->commglbload = 0;
133 actgrafptr->commglbloadextn0 = 0;
134 actgrafptr->commglbgainextn = 0;
135 actgrafptr->commglbgainextn0 = 0;
136 actgrafptr->bbalglbval = (double) actgrafptr->compglbload0dlt / (double) actgrafptr->compglbload0avg;
137 actgrafptr->domndist = domndist;
138 actgrafptr->domnwght[0] = domnwght0;
139 actgrafptr->domnwght[1] = domnwght1;
140 actgrafptr->levlnum = 0;
141 }
142
143 /* This routine frees the contents
144 ** of the given distributed active graph.
145 ** It returns:
146 ** - VOID : in all cases.
147 */
148
149 void
bdgraphExit(Bdgraph * const grafptr)150 bdgraphExit (
151 Bdgraph * const grafptr)
152 {
153 if (grafptr->partgsttax != NULL)
154 memFree (grafptr->partgsttax + grafptr->s.baseval);
155 if (grafptr->fronloctab != NULL)
156 memFree (grafptr->fronloctab);
157 if (grafptr->veexloctax != NULL)
158 memFree (grafptr->veexloctax + grafptr->s.baseval);
159
160 dgraphExit (&grafptr->s); /* Free distributed source graph and its private data (flagval may be corrupted afterwards) */
161
162 #ifdef SCOTCH_DEBUG_BDGRAPH2
163 memSet (grafptr, ~0, sizeof (Bdgraph));
164 #endif /* SCOTCH_DEBUG_BDGRAPH2 */
165 }
166
167 /* This routine moves all of the graph
168 ** vertices to the first part.
169 ** It returns:
170 ** - VOID : in all cases.
171 */
172
173 void
bdgraphZero(Bdgraph * const grafptr)174 bdgraphZero (
175 Bdgraph * const grafptr)
176 {
177 if (grafptr->partgsttax != NULL)
178 memSet (grafptr->partgsttax + grafptr->s.baseval, 0, grafptr->s.vertgstnbr * sizeof (GraphPart)); /* Set all local and ghost vertices to part 0 */
179
180 grafptr->fronlocnbr = /* No frontier vertices */
181 grafptr->fronglbnbr = 0;
182 grafptr->complocload0 = grafptr->s.velolocsum;
183 grafptr->compglbload0 = grafptr->s.veloglbsum;
184 grafptr->compglbload0dlt = grafptr->s.veloglbsum - grafptr->compglbload0avg;
185 grafptr->complocsize0 = grafptr->s.vertlocnbr;
186 grafptr->compglbsize0 = grafptr->s.vertglbnbr;
187 grafptr->commglbload = grafptr->commglbloadextn0;
188 grafptr->commglbgainextn = grafptr->commglbgainextn0;
189 }
190