12 |
|
|
13 |
/**************************************************************/ |
/**************************************************************/ |
14 |
|
|
15 |
/* Finley: Mesh : optimizes the labeling of nodes */ |
/* Finley: Mesh : optimizes the labeling of DOFs */ |
16 |
|
|
17 |
/**************************************************************/ |
/**************************************************************/ |
18 |
|
|
27 |
|
|
28 |
void Finley_Mesh_optimizeNodeLabeling(Finley_Mesh* mesh_p) { |
void Finley_Mesh_optimizeNodeLabeling(Finley_Mesh* mesh_p) { |
29 |
|
|
30 |
index_t *DOF_permutation=NULL, i; |
#if 0 |
31 |
/* |
|
32 |
|
|
33 |
|
index_t i, n, initial_bandwidth, first_available_DOF, first_available_level, max_level_size, num_levels; |
34 |
|
bool_t next_iteration, |
35 |
Paso_SystemMatrixPattern* pattern_p=NULL; |
Paso_SystemMatrixPattern* pattern_p=NULL; |
36 |
|
|
37 |
|
/* get access to the matrix pattern */ |
38 |
pattern_p=Finley_getPattern(mesh_p,FALSE,FALSE); |
pattern_p=Finley_getPattern(mesh_p,FALSE,FALSE); |
39 |
|
if (Finley_noError()) { |
40 |
if no error { |
if no error { |
41 |
XXX=pattern_p. ; |
n=pattern_p->n_ptr; |
42 |
DOF_permutation=MEMALLOC(XXX, index_t); |
old_to_new=MEMALLOC(n, index_t); |
43 |
availbale=MEMALLOC(XXX, index_t); |
availbale_DOF=MEMALLOC(n, bool_t); |
44 |
#pragma omp for private(i) |
#pragma omp for private(i) |
45 |
for (i=0;i< ;++i) { |
for (i=0;i<n;++i) { |
46 |
DOF_permutation[i]=i; |
old_to_new[i]=i; |
47 |
|
availbale_DOF=TRUE; |
48 |
} |
} |
49 |
first_available_node=0; |
/* get initial bandwidth */ |
50 |
while (first_available_node <= XXX) { |
initial_bandwidth=Finley_Mesh_getDegree(pattern_p,old_to_new); |
51 |
// get an available node with minimum number of naighbours |
printf("initial_bandwidth = %d\n",initial_bandwidth); |
52 |
max_level_size=XXX; |
/* make sure that all connection components are processed */ |
53 |
root=... |
first_available_DOF=0; |
54 |
// get the leveling string from root |
first_available_level=0; |
55 |
num_levels_tmp=1; |
while (root=Finley_Mesh_FindMinDegreeNode(pattern_p,availbale_DOF, TRUE) >-1) { |
56 |
num_nodes_in_level_tmp[0]=0; |
// get an available DOF with minimum number of naighbours |
57 |
levels_tmp[]; |
max_level_size=n; |
58 |
// get maximum level size |
next_iteration=TRUE; |
59 |
max_level_size_tmp=MAX(num_nodes_in_level_tmp[i+1]-num_nodes_in_level_tmp[i], max_level_size_tmp); |
num_levels=n; |
60 |
// use new leveling if |
#pragma omp parallel for private(i) |
61 |
if (max_level_size_tmp<max_level_size) { |
for (i=0;i<n;++i) { |
62 |
max_level_size=max_level_size_tmp; |
if (availbale_DOF[i]) |
63 |
num_levels=num_levels_tmp; |
level_mask[i]=num_levels-1; |
64 |
num_nodes_in_level=num_nodes_in_level_tmp; |
} else { |
65 |
|
level_mask[i]=-1; |
66 |
|
} |
67 |
|
} |
68 |
|
/* run through graph diameter and creates levels until the maximum level size cannot be improved anymore */ |
69 |
|
while (root>-1) { |
70 |
|
/* num_levels_new is the number of levels spanned from root. |
71 |
|
The DOFs ptr_DOFs_in_level_new[i] to ptr_DOFs_in_level_new[i+1]-1 in DOFs_in_level_new are |
72 |
|
maked for level i = 0,...,num_levels_new-1 */ |
73 |
|
Finley_Mesh_MarkLevels(root,pattern_p,level_mask,num_levels-1, |
74 |
|
&num_levels_new, ptr_DOFs_in_level_new, DOFs_in_level_new); |
75 |
|
/* now we calculate the maximum level size */ |
76 |
|
max_level_size_new=0; |
77 |
|
for (i=0;i<num_levels_new;++i) { |
78 |
|
max_level_size_new=MAX(ptr_DOFs_in_level_new[i+1]-ptr_DOFs_in_level_new[i], max_level_size_new); |
79 |
|
} |
80 |
|
/* if there is a reduction in the maximum level size the we accept this leveling */ |
81 |
|
/* otherwise we give up */ |
82 |
|
if (max_level_size_new < max_level_size) { |
83 |
|
max_level_size=max_level_size_new; |
84 |
|
num_levels=num_levels_new; |
85 |
|
for (i=0;i<num_levels_new+1;++i) { |
86 |
|
ptr_DOFs_in_level[i+first_available_level]=ptr_DOFs_in_level_new[i]; |
87 |
|
} |
88 |
|
for (i=0;i<ptr_DOFs_in_level_new[num_levels_new];++i) { |
89 |
|
DOFs_in_level[i+first_available_DOF]=DOFs_in_level_new[i]+first_available_level; |
90 |
|
} |
91 |
|
root=Finley_Mesh_FindMinDegreeNodeFromList(pattern_p, |
92 |
|
ptr_DOFs_in_level_new[num_levels_new]-ptr_DOFs_in_level_new[num_levels_new-1], |
93 |
|
DOFs_in_level_new[ptr_DOFs_in_level_new[num_levels_new-1]]); |
94 |
|
|
95 |
|
} else { |
96 |
|
root=-1; |
97 |
|
} |
98 |
|
} |
99 |
|
#pragma omp parallel for private(i) |
100 |
|
for (i=first_available_DOF;i<ptr_DOFs_in_level_new[num_levels];++i) { |
101 |
|
availbale_DOF[DOFs_in_level[i]]=FALSE; |
102 |
} |
} |
103 |
|
first_available_DOF+=ptr_DOFs_in_level_new[num_levels]; |
104 |
|
first_available_level+=num_levels; |
|
|
|
105 |
} |
} |
106 |
} |
/* create new_to_old labeling (we don't do anything here) */ |
107 |
*/ |
#pragma omp parallel for private(i) |
108 |
|
for (i=0;i<n;++i) new_to_old[i]=DOFs_in_level[i]; |
109 |
|
/* invert the new_to_old labeling */ |
110 |
|
#pragma omp parallel for private(i) |
111 |
|
for (i=0;i<n;++i) old_to_new[new_to_old[i]]=i; |
112 |
|
/* now we can start to assign new labels to DOFs */ |
113 |
|
new_bandwidth=Finley_Mesh_getDegree(pattern_p,old_to_new); |
114 |
|
if (new_bandwidth < initial_bandwidth) { |
115 |
|
|
116 |
|
|
117 |
|
} |
118 |
|
#endif |
119 |
|
} |
120 |
|
#if 0 |
121 |
|
dim_t Finley_Mesh_FindMinDegreeNode(Paso_SystemMatrixPattern* pattern_p,index_t* available,index_t indicator) { |
122 |
|
index_t min_deg_local, min_deg_node_local, min_deg, min_deg_node; |
123 |
|
register index_t deg; |
124 |
|
min_deg=pattern_p->n_ptr; |
125 |
|
min_deg_node=-1; |
126 |
|
#pragma omp parallel private(min_deg_local, min_deg_node_local) |
127 |
|
{ |
128 |
|
min_deg_local=pattern_p->n_ptr; |
129 |
|
min_deg_node=-1; |
130 |
|
#pragma omp for private(i,iptr,deg) |
131 |
|
for (i=0,i<pattern->n_ptr,++i) { |
132 |
|
if ( available[i] == indicator) { |
133 |
|
deg=0; |
134 |
|
for (iptr = pattern->ptr[i+1]; iptr<pattern->ptr[i+1]; ++iptr) { |
135 |
|
if (available[pattern->index[iptr]]==indicator) ++deg; |
136 |
|
} |
137 |
|
if (deg < min_deg_local) { |
138 |
|
min_deg_local=deg; |
139 |
|
min_deg_node_local=i; |
140 |
|
} |
141 |
|
} |
142 |
|
} |
143 |
|
#pragma omp critical |
144 |
|
{ |
145 |
|
if ((min_deg_local<min_deg) && (min_deg_local<min_deg)) { |
146 |
|
min_deg=min_deg_local; |
147 |
|
min_deg_node=min_deg_node_local; |
148 |
|
} |
149 |
|
} |
150 |
|
} |
151 |
|
return min_deg_node; |
152 |
|
} |
153 |
|
|
154 |
|
index_t Finley_Mesh_getDegree(Paso_SystemMatrixPattern* pattern_p, index_t *label) { |
155 |
|
index_t bandwidth, i, iptr, local_bandwidth; |
156 |
|
bandwidth = 0; |
157 |
|
#pragma omp parallel private(local_bandwidth) |
158 |
|
{ |
159 |
|
local_bandwidth=0; |
160 |
|
#pragma omp for private(i,i_ptr) |
161 |
|
for (i=0,i<pattern->n_ptr,++i) { |
162 |
|
for (iptr=pattern->ptr[i],iptr<pattern->ptr[i+1],++iptr) { |
163 |
|
local_bandwidth = MAX(local_bandwidth,ABS(label[i] - label(pattern->index[iptr]))); |
164 |
|
} |
165 |
|
} |
166 |
|
#pragma omp critical |
167 |
|
{ |
168 |
|
bandwidth=MAX(bandwidth,local_bandwidth); |
169 |
|
} |
170 |
|
} |
171 |
|
return bandwidth; |
172 |
|
} |
173 |
|
|
174 |
|
void Finley_Mesh_MarkLevels(index_t root, |
175 |
|
Paso_SystemMatrixPattern* pattern_p, |
176 |
|
dim_t *num_levels, dim_t *ptr_DOFs_in_level, index_t *DOFs_in_level) |
177 |
|
|
178 |
|
{ |
179 |
|
DOFs_in_level[0]=root; |
180 |
|
available[root]=FALSE; |
181 |
|
ptr_DOFs_in_level[0]=0; |
182 |
|
level_count=1; |
183 |
|
nn=1; |
184 |
|
while (ptr_DOFs_in_level[level_count-1] < nn ) { |
185 |
|
ptr_DOFs_in_level[level_count] = nn; |
186 |
|
++level_count; |
187 |
|
for (i = ptr_DOFs_in_level[level_count-1]; i < ptr_DOFs_in_level[level_count]; ++i) { |
188 |
|
dof=DOFs_in_level[i] |
189 |
|
for (iptr=pattern->ptr[dof],iptr<pattern->ptr[dof+1],++iptr) { |
190 |
|
itmp=pattern->index[iptr]; |
191 |
|
if (! available[itmp]) { |
192 |
|
available[itmp]=FALSE; |
193 |
|
DOFs_in_level[nn]=itmp; |
194 |
|
++nn; |
195 |
|
} |
196 |
|
|
197 |
|
|
198 |
|
|
199 |
|
} |
200 |
|
} |
201 |
|
*num_levels=level_count; |
202 |
|
ptr_DOFs_in_level[level_count]= ; |
203 |
} |
} |
204 |
|
#endif |