1 /* Copyright 2004,2007,2010-2012,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 : kgraph.h **/ 35 /** **/ 36 /** AUTHOR : Francois PELLEGRINI **/ 37 /** Sebastien FOURESTIER (v6.0) **/ 38 /** **/ 39 /** FUNCTION : Part of a static mapper. **/ 40 /** These lines are the data declarations **/ 41 /** for the k-way graph mapping structures **/ 42 /** and routines. **/ 43 /** **/ 44 /** DATES : # Version 3.2 : from : 12 sep 1997 **/ 45 /** to 26 may 1998 **/ 46 /** # Version 3.3 : from : 19 oct 1998 **/ 47 /** to 12 mar 1999 **/ 48 /** # Version 4.0 : from : 11 dec 2001 **/ 49 /** to 16 feb 2005 **/ 50 /** # Version 5.0 : from : 17 jun 2008 **/ 51 /** to 17 jun 2008 **/ 52 /** # Version 5.1 : from : 13 jul 2010 **/ 53 /** to 31 aug 2011 **/ 54 /** # Version 6.0 : from : 03 mar 2011 **/ 55 /** to 23 aug 2014 **/ 56 /** **/ 57 /** NOTES : # The comploadavg and comploaddlt **/ 58 /** should always be allocated together, **/ 59 /** with comploaddlt just after **/ 60 /** comploadavg. **/ 61 /** **/ 62 /** # To date, the only k-way graph mapping **/ 63 /** method is recursive bipartitioning, **/ 64 /** which does not use the comploadavg, **/ 65 /** comploaddlt and frontab parameters. **/ 66 /** Consequently, although allocated, **/ 67 /** these parameters are not set by this **/ 68 /** method. However, when coupled with **/ 69 /** the kdgraphMapSq() parallel static **/ 70 /** mapping routine, these parameters **/ 71 /** have to be computed. This is why the **/ 72 /** kgraphCost() routine is called within **/ 73 /** kdgraphMapSq(). When other sequential **/ 74 /** mapping routines are proposed, it may **/ 75 /** be more interesting to move **/ 76 /** kgraphCost() to kgraphMapRb(). **/ 77 /** **/ 78 /** # When (pfixtax != NULL), we are **/ 79 /** handling fixed vertices. **/ 80 /** **/ 81 /** # When (r.m.parttax != NULL), we are **/ 82 /** doing repartitioning. **/ 83 /** **/ 84 /************************************************************/ 85 86 #define KGRAPH_H 87 88 /* 89 ** The defines. 90 */ 91 92 /*+ Graph option flags. +*/ 93 94 #define KGRAPHFREEFRON (GRAPHBITSNOTUSED) /*+ Free frontier array +*/ 95 #define KGRAPHFREECOMP (GRAPHBITSNOTUSED << 1) /*+ Free computational loads array +*/ 96 #define KGRAPHFREEPFIX (GRAPHBITSNOTUSED << 2) /*+ Free fixed vertex array +*/ 97 #define KGRAPHFREEVMLO (GRAPHBITSNOTUSED << 3) /*+ Free vertex migration cost array +*/ 98 #define KGRAPHHASANCHORS (GRAPHBITSNOTUSED << 4) /*+ The graph is a band graph +*/ 99 100 /* 101 ** The type and structure definitions. 102 */ 103 104 /*+ The graph structure. +*/ 105 106 typedef struct Kgraph_ { 107 Graph s; /*+ Current graph +*/ 108 Arch a; /*+ Current architecture +*/ 109 Mapping m; /*+ Current mapping of graph vertices +*/ 110 struct { /*+ Remapping structure +*/ 111 Mapping m; /*+ Old mapping +*/ 112 Gnum crloval; /*+ Coefficient load for regular edges +*/ 113 Gnum cmloval; /*+ Coefficient load for migration edges; may be zero +*/ 114 const Gnum * vmlotax; /*+ Vertex migration cost array +*/ 115 } r; 116 Gnum vfixnbr; /*+ Number of fixed vertices +*/ 117 const Anum * pfixtax; /*+ Fixed terminal part array +*/ 118 Gnum fronnbr; /*+ Number of frontier vertices +*/ 119 Gnum * frontab; /*+ Array of frontier vertex numbers +*/ 120 Gnum * comploadavg; /*+ Array of target average loads +*/ 121 Gnum * comploaddlt; /*+ Array of target imbalances +*/ 122 double comploadrat; /*+ Ideal load balance per weight unit +*/ 123 double kbalval; /*+ Last k-way imbalance ratio +*/ 124 Gnum commload; /*+ Communication load +*/ 125 Gnum levlnum; /*+ Graph coarsening level +*/ 126 } Kgraph; 127 128 /*+ The save graph structure. +*/ 129 130 typedef struct KgraphStore_ { 131 Gnum partnbr; /*+ Number of parts +*/ 132 int mflaval; /*+ Mapping properties +*/ 133 Anum * parttab; /*+ Mapping array [vertnbr] +*/ 134 ArchDom * domntab; /*+ Array of domains [termmax] +*/ 135 Anum domnnbr; /*+ Current number of domains +*/ 136 Gnum fronnbr; /*+ Number of frontier vertices +*/ 137 Gnum * frontab; /*+ Array of frontier vertex numbers +*/ 138 Gnum * comploadavg; /*+ Array of target average loads +*/ 139 Gnum * comploaddlt; /*+ Array of target imbalances +*/ 140 double kbalval; /*+ Last k-way imbalance ratio +*/ 141 Gnum commload; /*+ Communication load +*/ 142 } KgraphStore; 143 144 /* 145 ** The function prototypes. 146 */ 147 148 #ifndef KGRAPH 149 #define static 150 #endif 151 152 int kgraphInit (Kgraph * restrict const, const Graph * restrict const, const Arch * restrict const, const ArchDom * restrict const, const Gnum, const Anum * restrict const, const Anum * restrict const, const Gnum, const Gnum, const Gnum * restrict const); 153 void kgraphExit (Kgraph * const); 154 void kgraphFrst (Kgraph * const); 155 int kgraphCheck (const Kgraph * const); 156 void kgraphCost (Kgraph * const); 157 void kgraphFron (Kgraph * const); 158 int kgraphBand (Kgraph * restrict const, const Gnum, Kgraph * restrict const, Gnum * const, Gnum * restrict * restrict const); 159 160 int kgraphStoreInit (const Kgraph * const, KgraphStore * const); 161 void kgraphStoreExit (KgraphStore * const); 162 void kgraphStoreSave (const Kgraph * const, KgraphStore * const); 163 void kgraphStoreUpdt (Kgraph * const, const KgraphStore * const); 164 165 #undef static 166