# Contents of /trunk/paso/src/Pattern_reduceBandwidth.c

Revision 1388 - (show annotations)
Fri Jan 11 07:45:58 2008 UTC (12 years, 1 month ago) by trankine
File MIME type: text/plain
File size: 10044 byte(s)
```And get the *(&(*&(* name right
```
 1 2 /* \$Id\$ */ 3 4 /******************************************************* 5 * 6 * Copyright 2003-2007 by ACceSS MNRF 7 * Copyright 2007 by University of Queensland 8 * 9 * http://esscc.uq.edu.au 10 * Primary Business: Queensland, Australia 11 * Licensed under the Open Software License version 3.0 12 * http://www.opensource.org/licenses/osl-3.0.php 13 * 14 *******************************************************/ 15 16 /**************************************************************/ 17 18 /* Paso: pattern: a simple algorithm to create a new labeling */ 19 /* of input/output with a minimum bandwidth. The algorithm */ 20 /* starts from a vertex with a minumum number of naigbours (connections in the pattern). */ 21 /* From this root it searches recursively the naighbours. In the last level */ 22 /* a new root is picked (again the vertex with the minumum number of naigbours) and the */ 23 /* process is repeated. The algorithm is repeated until the maximum number of vertices */ 24 /* in a level cannot be reduced. */ 25 26 /**************************************************************/ 27 28 /* Copyrights by ACcESS Australia 2004,2005,2007 */ 29 /* Author: gross@access.edu.au */ 30 31 /**************************************************************/ 32 33 34 #include "Paso.h" 35 #include "Pattern.h" 36 #include "Common.h" 37 38 /* calculate initial badwdisth for a given labeling */ 39 dim_t Paso_Pattern_getBandwidth(Paso_Pattern* pattern, index_t* label) { 40 register index_t k; 41 index_t iptr; 42 dim_t bandwidth = 0, local_bandwidth=0,i ; 43 44 #pragma omp parallel private(local_bandwidth) 45 { 46 local_bandwidth=0; 47 #pragma omp for private(i,iptr,k) 48 for (i=0;inumOutput;++i) { 49 k=label[i]; 50 for (iptr=pattern->ptr[i];iptrptr[i+1];++iptr) { 51 local_bandwidth = MAX(local_bandwidth, ABS(k - label[pattern->index[iptr]])); 52 } 53 } 54 #pragma omp critical 55 { 56 bandwidth=MAX(local_bandwidth,bandwidth); 57 } 58 } 59 return bandwidth; 60 } 61 /* structures used to create an ordering by increasing degree */ 62 typedef struct Paso_DegreeAndIdx { 63 dim_t deg; 64 index_t idx; 65 } Paso_DegreeAndIdx; 66 67 int Paso_comparDegreeAndIdx(const void *arg1,const void *arg2){ 68 Paso_DegreeAndIdx a1=*(Paso_DegreeAndIdx*)arg1; 69 Paso_DegreeAndIdx a2=*(Paso_DegreeAndIdx*)arg2; 70 if (a1.dega2.deg) { 73 return 1; 74 } else if (a1.idxa2.idx) { 77 return 1; 78 } else { 79 return 0; 80 } 81 } 82 83 /* Paso_Pattern_dropTree drops a tree in pattern from root */ 84 85 /* root - on input the starting point of the tree. */ 86 /* AssignedLevel- array of length pattern->numOutput indicating the level assigned to vertex */ 87 /* VerticesInTree - on output contains the vertices used in tree (array of length pattern->numOutput) */ 88 /* numLevels- on output the number of level used. */ 89 /* firstVertexInLevel - on output firstVertexInLevel[i] points to the first vertex of level i in VerticesInTree. */ 90 /* firstVertexInLevel[i+1]-firstVertexInLevel[i] is the number of vertices in level i. */ 91 /* (array of length pattern->numOutput+1) */ 92 /* max_LevelWidth_abort- input param which triggers early return if LevelWidth becomes >= max_LevelWidth_abort */ 93 bool_t Paso_Pattern_dropTree(index_t root, 94 Paso_Pattern *pattern, 95 index_t *AssignedLevel, 96 index_t *VerticesInTree, 97 dim_t* numLevels, 98 index_t* firstVertexInLevel, 99 dim_t max_LevelWidth_abort, 100 dim_t N) 101 { 102 dim_t nlvls,i; 103 index_t level_top,k ,itest,j; 104 105 #pragma omp parallel for private(i) 106 for (i=0;inumInput;++i) AssignedLevel[i]=-1; 107 108 nlvls=0; 109 AssignedLevel[root] = 0; 110 VerticesInTree[0] = root; 111 firstVertexInLevel[0]=0; 112 level_top=firstVertexInLevel[0]+1; 113 while (firstVertexInLevel[nlvls]=max_LevelWidth_abort) return FALSE; 117 for (i=firstVertexInLevel[nlvls-1];iptr[k];jptr[k+1];++j) { 120 itest = pattern->index[j]; 121 if (AssignedLevel[itest]<0) { 122 #ifdef BOUNDS_CHECK 123 if (itest < 0 || itest >= N) { printf("BOUNDS_CHECK %s %d itest=%d\n", __FILE__, __LINE__, itest); exit(1); } 124 if (level_top < 0 || level_top >= N) { printf("BOUNDS_CHECK %s %d level_top=%d\n", __FILE__, __LINE__, level_top); exit(1); } 125 #endif 126 AssignedLevel[itest] = nlvls; 127 VerticesInTree[level_top] = itest; 128 level_top++; 129 } 130 } 131 } 132 } 133 *numLevels=nlvls; 134 return TRUE; 135 } 136 137 /* the driver */ 138 void Paso_Pattern_reduceBandwidth(Paso_Pattern* pattern,index_t* oldToNew) { 139 dim_t i, initial_bandwidth, N=pattern->numOutput, numLabledVertices, numLevels, max_LevelWidth, min_deg,deg, numVerticesInTree, bandwidth; 140 Paso_DegreeAndIdx* degAndIdx=NULL; 141 index_t root, *AssignedLevel=NULL, *VerticesInTree=NULL, *firstVertexInLevel=NULL,k, *oldLabel=NULL; 142 /* check input */ 143 if (N != pattern->numInput) { 144 Paso_setError(VALUE_ERROR,"Paso_Pattern_reduceBandwidth: pattern needs to be for a square matrix."); 145 } else { 146 printf("relabeling of %d DOFs started.\n",N); 147 degAndIdx=TMPMEMALLOC(N,Paso_DegreeAndIdx); 148 oldLabel=TMPMEMALLOC(N,bool_t); 149 AssignedLevel=TMPMEMALLOC(N,index_t); 150 VerticesInTree=TMPMEMALLOC(N,index_t); 151 firstVertexInLevel=TMPMEMALLOC(N+1,index_t); 152 if (! ( Paso_checkPtr(degAndIdx) || Paso_checkPtr(oldLabel) || Paso_checkPtr(AssignedLevel) || Paso_checkPtr(VerticesInTree) || Paso_checkPtr(firstVertexInLevel) ) ) { 153 /* get the initial bandwidth */ 154 #pragma omp parallel for private(i) 155 for (i=0;iptr[i+1]-pattern->ptr[i]; 164 } 165 /* create an ordering with increasing degree */ 166 #ifdef USE_QSORTG 167 qsortG(degAndIdx,(size_t)N,sizeof(Paso_DegreeAndIdx),Paso_comparDegreeAndIdx); 168 #else 169 qsort(degAndIdx,(size_t)N,sizeof(Paso_DegreeAndIdx),Paso_comparDegreeAndIdx); 170 #endif 171 172 root=degAndIdx[0].idx; 173 numLabledVertices=0; 174 175 while (root>=0) { 176 max_LevelWidth=N+1; 177 178 while (Paso_Pattern_dropTree(root,pattern,AssignedLevel,VerticesInTree, 179 &numLevels,firstVertexInLevel,max_LevelWidth,N) ) { 180 181 /* find new maximum level width */ 182 max_LevelWidth=0; 183 for (i=0;i= N+1) { printf("BOUNDS_CHECK %s %d i=%d N=%d\n", __FILE__, __LINE__, i, N); exit(1); } 186 #endif 187 max_LevelWidth=MAX(max_LevelWidth,firstVertexInLevel[i+1]-firstVertexInLevel[i]); 188 } 189 /* find a vertex in the last level which has minimum degree */ 190 min_deg=N+1; 191 root=-1; 192 for (i = firstVertexInLevel[numLevels-1]; iptr[k+1]-pattern->ptr[k]; 195 if (deg= N) { printf("BOUNDS_CHECK %s %d i=%d numLabledVertices=%d root=%d N=%d firstVertexInLevel[numLevels]=%d\n", __FILE__, __LINE__, i, numLabledVertices, root, N, firstVertexInLevel[numLevels]); exit(1); } 205 #endif 206 oldLabel[numLabledVertices+i]=VerticesInTree[i]; 207 } 208 } 209 /* now the vertices in the current tree */ 210 for (i=0;i= N) { printf("BOUNDS_CHECK %s %d i=%d numLabledVertices=%d root=%d N=%d\n", __FILE__, __LINE__, i, numLabledVertices, root, N); exit(1); } 213 #endif 214 oldToNew[oldLabel[numLabledVertices+i]]=numLabledVertices+i; 215 } 216 numLabledVertices+=numVerticesInTree; 217 /* new search for a vertex which is not labled yet */ 218 root=-1; 219 for (i=0;i=initial_bandwidth) { 229 printf("initial labeling used.\n"); 230 #pragma omp parallel for private(i) 231 for (i=0;i