/[escript]/trunk/paso/src/Pattern_reduceBandwidth.cpp
ViewVC logotype

Diff of /trunk/paso/src/Pattern_reduceBandwidth.cpp

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 4802 by jfenwick, Thu Feb 6 06:12:20 2014 UTC revision 4803 by caltinay, Wed Mar 26 06:52:28 2014 UTC
# Line 38  Line 38 
38  #include "Pattern.h"  #include "Pattern.h"
39  #include "Common.h"  #include "Common.h"
40    
41    namespace paso {
42    
43  /*   calculate initial bandwidth for a given labeling */  /*   calculate initial bandwidth for a given labeling */
44  dim_t Paso_Pattern_getBandwidth(Paso_Pattern* pattern, index_t* label) {  dim_t Pattern_getBandwidth(Pattern* pattern, index_t* label) {
45        register index_t k;        register index_t k;
46        index_t iptr;        index_t iptr;
47        dim_t bandwidth = 0, local_bandwidth=0,i ;        dim_t bandwidth = 0, local_bandwidth=0,i ;
# Line 83  int Paso_comparDegreeAndIdx(const void * Line 85  int Paso_comparDegreeAndIdx(const void *
85     }     }
86  }  }
87    
88  /*  Paso_Pattern_dropTree drops a tree in pattern from root */  /*  Pattern_dropTree drops a tree in pattern from root */
89    
90  /*  root - on input the starting point of the tree. */  /*  root - on input the starting point of the tree. */
91  /*  AssignedLevel- array of length pattern->numOutput indicating the level assigned to vertex */  /*  AssignedLevel- array of length pattern->numOutput indicating the level assigned to vertex */
# Line 93  int Paso_comparDegreeAndIdx(const void * Line 95  int Paso_comparDegreeAndIdx(const void *
95  /*                       firstVertexInLevel[i+1]-firstVertexInLevel[i] is the number of vertices in level i. */  /*                       firstVertexInLevel[i+1]-firstVertexInLevel[i] is the number of vertices in level i. */
96  /*                         (array of length pattern->numOutput+1) */  /*                         (array of length pattern->numOutput+1) */
97  /*  max_LevelWidth_abort-  input param which triggers early return if LevelWidth becomes >= max_LevelWidth_abort */  /*  max_LevelWidth_abort-  input param which triggers early return if LevelWidth becomes >= max_LevelWidth_abort */
98  bool Paso_Pattern_dropTree(index_t root,  bool Pattern_dropTree(index_t root,
99                               Paso_Pattern *pattern,                               Pattern *pattern,
100                               index_t *AssignedLevel,                               index_t *AssignedLevel,
101                               index_t *VerticesInTree,                               index_t *VerticesInTree,
102                               dim_t* numLevels,                               dim_t* numLevels,
103                               index_t* firstVertexInLevel,                               index_t* firstVertexInLevel,
104                               dim_t max_LevelWidth_abort,                               dim_t max_LevelWidth_abort,
105                   dim_t N)                               dim_t N)
106  {  {
107    dim_t nlvls,i;    dim_t nlvls,i;
108    index_t level_top,k ,itest,j;    index_t level_top,k ,itest,j;
# Line 123  bool Paso_Pattern_dropTree(index_t root, Line 125  bool Paso_Pattern_dropTree(index_t root,
125             itest = pattern->index[j];             itest = pattern->index[j];
126             if (AssignedLevel[itest]<0) {             if (AssignedLevel[itest]<0) {
127  #ifdef BOUNDS_CHECK  #ifdef BOUNDS_CHECK
128                 if (itest < 0 || itest >= N) { printf("BOUNDS_CHECK %s %d itest=%d\n", __FILE__, __LINE__, itest); exit(1); }                         if (itest < 0 || itest >= N) { printf("BOUNDS_CHECK %s %d itest=%d\n", __FILE__, __LINE__, itest); exit(1); }
129                 if (level_top < 0 || level_top >= N) { printf("BOUNDS_CHECK %s %d level_top=%d\n", __FILE__, __LINE__, level_top); exit(1); }                         if (level_top < 0 || level_top >= N) { printf("BOUNDS_CHECK %s %d level_top=%d\n", __FILE__, __LINE__, level_top); exit(1); }
130  #endif  #endif
131                AssignedLevel[itest] = nlvls;                AssignedLevel[itest] = nlvls;
132                VerticesInTree[level_top] = itest;                VerticesInTree[level_top] = itest;
# Line 138  bool Paso_Pattern_dropTree(index_t root, Line 140  bool Paso_Pattern_dropTree(index_t root,
140  }  }
141    
142  /* the driver */  /* the driver */
143  void Paso_Pattern_reduceBandwidth(Paso_Pattern* pattern,index_t* oldToNew) {  void Pattern_reduceBandwidth(Pattern* pattern,index_t* oldToNew) {
144     dim_t i, initial_bandwidth, N=pattern->numOutput, numLabledVertices, numLevels, max_LevelWidth, min_deg,deg, numVerticesInTree=0, bandwidth;     dim_t i, initial_bandwidth, N=pattern->numOutput, numLabledVertices, numLevels, max_LevelWidth, min_deg,deg, numVerticesInTree=0, bandwidth;
145     Paso_DegreeAndIdx* degAndIdx=NULL;     Paso_DegreeAndIdx* degAndIdx=NULL;
146     index_t root, *AssignedLevel=NULL, *VerticesInTree=NULL, *firstVertexInLevel=NULL,k, *oldLabel=NULL;     index_t root, *AssignedLevel=NULL, *VerticesInTree=NULL, *firstVertexInLevel=NULL,k, *oldLabel=NULL;
147     /* check input */     /* check input */
148     if (N != pattern->numInput) {     if (N != pattern->numInput) {
149        Esys_setError(VALUE_ERROR,"Paso_Pattern_reduceBandwidth: pattern needs to be for a square matrix.");        Esys_setError(VALUE_ERROR,"Pattern_reduceBandwidth: pattern needs to be for a square matrix.");
150     } else if (N > 0) {     } else if (N > 0) {
151  /* printf("relabeling of %d DOFs started.\n",N); */  /* printf("relabeling of %d DOFs started.\n",N); */
152        degAndIdx=new Paso_DegreeAndIdx[N];        degAndIdx=new Paso_DegreeAndIdx[N];
# Line 156  void Paso_Pattern_reduceBandwidth(Paso_P Line 158  void Paso_Pattern_reduceBandwidth(Paso_P
158           /* get the initial bandwidth */           /* get the initial bandwidth */
159           #pragma omp parallel for private(i)           #pragma omp parallel for private(i)
160           for (i=0;i<N;++i) oldToNew[i]=i;           for (i=0;i<N;++i) oldToNew[i]=i;
161           initial_bandwidth=Paso_Pattern_getBandwidth(pattern,oldToNew);           initial_bandwidth=Pattern_getBandwidth(pattern,oldToNew);
162  /* printf("initial bandwidth = %d\n",initial_bandwidth); */  /* printf("initial bandwidth = %d\n",initial_bandwidth); */
163           /* get the initial bandwidth */           /* get the initial bandwidth */
164           #pragma omp parallel for private(i)           #pragma omp parallel for private(i)
# Line 178  void Paso_Pattern_reduceBandwidth(Paso_P Line 180  void Paso_Pattern_reduceBandwidth(Paso_P
180           while (root>=0) {           while (root>=0) {
181               max_LevelWidth=N+1;               max_LevelWidth=N+1;
182                                    
183               while (Paso_Pattern_dropTree(root,pattern,AssignedLevel,VerticesInTree,               while (Pattern_dropTree(root,pattern,AssignedLevel,VerticesInTree,
184                                            &numLevels,firstVertexInLevel,max_LevelWidth,N) ) {                                            &numLevels,firstVertexInLevel,max_LevelWidth,N) ) {
185    
186                   /* find new maximum level width */                   /* find new maximum level width */
187                   max_LevelWidth=0;                   max_LevelWidth=0;
188                   for (i=0;i<numLevels;++i) {                   for (i=0;i<numLevels;++i) {
189  #ifdef BOUNDS_CHECK  #ifdef BOUNDS_CHECK
190                if (i < 0 || i >= N+1) { printf("BOUNDS_CHECK %s %d i=%d N=%d\n", __FILE__, __LINE__, i, N); exit(1); }                        if (i < 0 || i >= N+1) { printf("BOUNDS_CHECK %s %d i=%d N=%d\n", __FILE__, __LINE__, i, N); exit(1); }
191  #endif  #endif
192                        max_LevelWidth=MAX(max_LevelWidth,firstVertexInLevel[i+1]-firstVertexInLevel[i]);                        max_LevelWidth=MAX(max_LevelWidth,firstVertexInLevel[i+1]-firstVertexInLevel[i]);
193                   }                   }
# Line 204  void Paso_Pattern_reduceBandwidth(Paso_P Line 206  void Paso_Pattern_reduceBandwidth(Paso_P
206                   numVerticesInTree=firstVertexInLevel[numLevels];                   numVerticesInTree=firstVertexInLevel[numLevels];
207                   for (i=0;i<firstVertexInLevel[numLevels];++i) {                   for (i=0;i<firstVertexInLevel[numLevels];++i) {
208  #ifdef BOUNDS_CHECK  #ifdef BOUNDS_CHECK
209                 if (numLabledVertices+i < 0 || numLabledVertices+i >= N) { printf("BOUNDS_CHECK %s %d i=%d numLabeledVertices=%d root=%d N=%d firstVertexInLevel[numLevels]=%d\n", __FILE__, __LINE__, i, numLabledVertices, root, N, firstVertexInLevel[numLevels]); exit(1); }                         if (numLabledVertices+i < 0 || numLabledVertices+i >= N) { printf("BOUNDS_CHECK %s %d i=%d numLabeledVertices=%d root=%d N=%d firstVertexInLevel[numLevels]=%d\n", __FILE__, __LINE__, i, numLabledVertices, root, N, firstVertexInLevel[numLevels]); exit(1); }
210  #endif  #endif
211                         oldLabel[numLabledVertices+i]=VerticesInTree[i];                         oldLabel[numLabledVertices+i]=VerticesInTree[i];
212                   }                   }
# Line 212  void Paso_Pattern_reduceBandwidth(Paso_P Line 214  void Paso_Pattern_reduceBandwidth(Paso_P
214               /* now the vertices in the current tree */               /* now the vertices in the current tree */
215               for (i=0;i<numVerticesInTree;++i) {               for (i=0;i<numVerticesInTree;++i) {
216  #ifdef BOUNDS_CHECK  #ifdef BOUNDS_CHECK
217           if (numLabledVertices+i < 0 || numLabledVertices+i >= N) { printf("BOUNDS_CHECK %s %d i=%d numLabeledVertices=%d root=%d N=%d\n", __FILE__, __LINE__, i, numLabledVertices, root, N); exit(1); }                   if (numLabledVertices+i < 0 || numLabledVertices+i >= N) { printf("BOUNDS_CHECK %s %d i=%d numLabeledVertices=%d root=%d N=%d\n", __FILE__, __LINE__, i, numLabledVertices, root, N); exit(1); }
218  #endif  #endif
219                   oldToNew[oldLabel[numLabledVertices+i]]=numLabledVertices+i;                   oldToNew[oldLabel[numLabledVertices+i]]=numLabledVertices+i;
220               }               }
# Line 226  void Paso_Pattern_reduceBandwidth(Paso_P Line 228  void Paso_Pattern_reduceBandwidth(Paso_P
228                   }                   }
229               }               }
230          } /* end of while root loop */          } /* end of while root loop */
231          bandwidth=Paso_Pattern_getBandwidth(pattern,oldToNew);          bandwidth=Pattern_getBandwidth(pattern,oldToNew);
232  /* printf("bandwidth after DOF relabeling= %d\n",bandwidth); */  /* printf("bandwidth after DOF relabeling= %d\n",bandwidth); */
233          if (bandwidth>=initial_bandwidth) {          if (bandwidth>=initial_bandwidth) {
234  /* printf("initial labeling used.\n"); */  /* printf("initial labeling used.\n"); */
# Line 242  void Paso_Pattern_reduceBandwidth(Paso_P Line 244  void Paso_Pattern_reduceBandwidth(Paso_P
244     }     }
245  }  }
246    
247    } // namespace paso
248    

Legend:
Removed from v.4802  
changed lines
  Added in v.4803

  ViewVC Help
Powered by ViewVC 1.1.26