/[escript]/trunk/paso/src/SystemMatrixPattern_reduceBandwidth.c.2
ViewVC logotype

Contents of /trunk/paso/src/SystemMatrixPattern_reduceBandwidth.c.2

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1055 - (show annotations)
Thu Mar 22 04:49:23 2007 UTC (12 years, 10 months ago) by gross
File size: 35072 byte(s)
a bit of work towards the bandwidth optimizer
1
2 /*
3 ********************************************************************************
4 * Copyright 2006 by ACcESS MNF *
5 * *
6 * http://www.access.edu.au *
7 * Primary Business: Queensland, Australia *
8 * Licensed under the Open Software License version 3.0 *
9 * http://www.opensource.org/licenses/osl-3.0.php *
10 ********************************************************************************
11 */
12
13 /* Finley_Reduce determines a row and column permutation which, when applied to a given sparse matrix, produces a permuted */
14 /* matrix with a smaller bandwidth and profile. the input array is a connection table which represents the */
15 /* indices of the nonzero elements of the matrix, a. the algorithm is described in terms of the adjacency graph which */
16 /* has the characteristic that there is an edge (connection) between nodes i and j if a(i,j) .ne. 0 and i .ne. j. */
17
18
19 /* pattern_p(N,D1) D1 IS >= MAXIMUM degree_p OF ALL NODES.
20 /* label_p(D2) D2 AND N ARE >= THE TOTAL NUMBER OF
21 /* new_label_p(D2+1) NODES IN THE GRAPH.
22 /* degree_p(D2) STORAGE REQUIREMENTS CAN BE SIGNifICANTLY
23
24 /* assigned_level_p(D2) DECREASED FOR IBM 360 AND 370 COMPUTERS
25 /* forward_levels_p(D2) BY REPLACING INTEGER pattern_p BY
26 /* backward_levels_p(D2) INTEGER*2 pattern_p IN SUBROUTINES Finley_Reduce,
27 /* ConnectedComponents_p(D2) Finley_Reduce_setCharacteristics, Finley_Reduce_findDiameter, Paso_BandwidthReduction_dropTree AND NUMBER.
28 /* COMMON INFORMATION--THE FOLLOWING COMMON BLOCK MUST BE IN THE
29 /* CALLING ROUTINE.
30 /* COMMON/GRA/N,num_levels,ndeg_max
31 /* EXPLANATION OF INPUT VARIABLES--
32 /* pattern_p- CONNECTION TABLE REPRESENTING GRAPH.
33 /* pattern_p->index[iptr]=NODE NUMBER OF JTH CONNECTION TO NODE
34 /* NUMBER I. A CONNECTION OF A NODE TO ITSELF IS NOT
35 /* LISTED. EXTRA POSITIONS MUST HAVE ZERO FILL.
36 /* N- ROW DIMENSION ASSIGNED pattern_p IN CALLING PROGRAM.
37 /* label_p[i]- NUMBERING OF ITH NODE UPON INPUT. if NO NUMBERING EXISTS THEN label_p[i]=I.
38 /* N- NUMBER OF NODES IN GRAPH (EQUAL TO ORDER OF MATRIX).
39 /* ndeg_max- MAXIMUM degree_p OF ANY NODE IN THE GRAPH.
40 /* degree_p[i]- THE degree_p OF THE ITH NODE.
41 /* EXPLANATION OF OUTPUT VARIABLES--
42 /* new_label_p[i]- THE NEW NUMBER FOR THE ITH NODE.
43 /* newBandwidth- THE BANDWIDTH AFTER numbering .
44 /* newProfile- THE PROFILE AFTER numbering .
45 /* num_levels - NUMBER OF LEVELS IN Finley_Reduce LEVEL STRUCTURE.
46 /* */
47 /* The following only have meaning if the graph was connected:
48
49 /* assigned_level_p[i]- INDEX INTO forward_levels_p TO THE FIRST NODE IN LEVEL I. assigned_level_p(I+1)-assigned_level_p[i]= number of nodes in ith leveL
50 /* forward_levels_p- node numbers listed by level
51 /* backward_levels_p[i]- the level assigned to node i by Finley_Reduce.
52
53 /* WORKING STORAGE VARIABLE--
54 /* ConnectedComponents_p
55 /* LOCAL STORAGE--
56 /* COMMON/CC/-SUBROUTINES Finley_Reduce, Paso_BandwidthReduction_sortConnectedComponentsInfos AND Paso_BandwidthReduction_chooseFinalLeveling ASSUME THAT
57 /* THE GRAPH HAS AT MOST 50 CONNECTED COMPONENTS.
58 /* SUBROUTINE Finley_Reduce_findDiameter ASSUMES THAT THERE ARE AT MOST
59 /* 100 NODES IN THE LAST LEVEL.
60 /* COMMON/assigned_level_pW/-SUBROUTINES Paso_BandwidthReduction_setup AND Paso_BandwidthReduction_chooseFinalLeveling ASSUME THAT THERE
61 /* ARE AT MOST 100 LEVELS.
62 SUBROUTINE Finley_Reduce(pattern_p, N, label_p, new_label_p, degree_p, assigned_level_p, forward_levels_p,backward_levels_p, ConnectedComponents_p, newBandwidth, newProfile, NIN, ndeg_maxIN)
63 /* USE INTEGER*2 pattern_p WITH AN IBM 360 OR 370.
64 integer NIN, ndeg_maxIN
65 INTEGER pattern_p
66 INTEGER start_node, end_node, new_label_p, connected_component_counter, Paso_BandwidthReduction_sortConnectedComponentsInfos, last_available_node_number, ConnectedComponents_p,
67 * connected_component_size_p, connected_component_ptr, first_available_node_number
68 COMMON /GRA/ N, num_levels, ndeg_max
69 /* IT IS ASSUMED THAT THE GRAPH HAS AT MOST 50 CONNECTED COMPONENTS.
70 COMMON /CC/ connected_component_counter, connected_component_size_p(50), connected_component_ptr(50)
71 COMMON /assigned_level_pW/ NHIGH(100), NLOW(100), num_nodes_in_level_p(100)
72 DIMENSION ConnectedComponents_p(1), label_p(1)
73 DIMENSION pattern_p(N,1), assigned_level_p(1), forward_levels_p(1), backward_levels_p(1), new_label_p(1),
74 * degree_p(1)
75 newBandwidth = 0
76 newProfile = 0
77 /* SET new_label_p[i]=0 FOR ALL I TO INDICATE NODE I IS UNNUMBERED
78 c
79 c N = N
80 c do i=0,i<N,++i)
81 c if(ndeg_max<degree_p[i]) then
82 c ndeg_max = degree_p[i]
83 c end if
84 c end do
85 c
86
87 set degree_p
88 N=NIN
89 ndeg_max = ndeg_maxIN
90 for (i=0,i<N,++i) {
91 degree_p[i]=ptr[i+1]-ptr[i];
92 new_label_p[i] = 0;
93 }
94
95 /* COMPUTE degree_p OF EACH NODE AND ORIGINAL BANDWIDTH AND PROFILE*/
96
97 ===============================
98 Paso_BandwidthReduction_p* pattern_p,
99
100
101 long initial_bandwidth, initial_profile
102 dim_t *degree_p=NULL;
103 dim_t N = pattern_p->n_ptr;
104 index_t *label_p_p=NULL;
105
106 degree_p=MEMALLOC(N,dim_t);
107 label_p_p=MEMALLOC(N,index_t);
108 new_label_p=MEMALLOC(N,index_t);
109
110 if (sdsadsad) {
111 /* get the initial bandwidth and profile */
112 for (i=0,i<N,++i) {
113 degree_p[i]=pattern_p->ptr[i+1]-pattern_p->ptr[i]-1;
114 label_p[i]=i;
115 new_label_p[i]=0;
116 }
117 Finley_Reduce_setCharacteristics(pattern_p, degree_p, label_p, *initial_bandwidth, *initial_profile)
118 printf("initial bandwidth and profile: %dl %dl\n",initial_bandwidth, initial_profile);
119
120 /* first_available_node_number = low end of available numbers for numbering */
121 /* last_available_node_number = high end of available numbers for numbering */
122 first_available_node_number = 0;
123 last_available_node_number = N;
124 /* number the nodes of degree_p zero are last: */
125 for (i=0,i<N,++i) {
126 if (degree_p[i]==0) {
127 new_label_p[i] = last_available_node_number;
128 last_available_node_number--;
129 }
130 }
131
132 }
133 }
134 /* find an unnumbered node of min degree to start on */
135 while (first_available_node_number<=last_available_node_number) {
136
137 reverse_diameter_tree = FALSE;
138 SDIR = 1;
139
140 /* find the node with smallest degree and use this one as start node */
141 smallest_degree = N + 1;
142 for (i=0,i<N,++i) {
143 if (degree_p[i]<smallest_degree && new_label_p[i]<=0) {
144 smallest_degree = degree_p[i];
145 start_node = i;
146 }
147 }
148 /* find pseudo-diameter and associated level structures marked assigned_level_p: */
149
150 /* start_node and end_node are the ends of the diameter and
151 forward_levels_p and backward_levels_p are the respective level structures. */
152
153 Finley_Reduce_findDiameter(*start_node,
154 end_node, pattern_p, degree_p,
155 assigned_level_p,
156 forward_levels_p,backward_levels_p,
157 ConnectedComponents_p,
158 IDFLT)
159 /* reverse_diameter_tree INDICATES THE END TO BEGIN NUMBERING ON */
160 if (degree_p(start_node)>degree_p(end_node)) {
161 reverse_diameter_tree = TRUE;
162 start_node = end_node;
163 } else {
164 reverse_diameter_tree = FALSE;
165 }
166
167 Paso_BandwidthReduction_setup(assigned_level_p, forward_levels_p, backward_levels_p)
168 /* find all the connected components */
169 connected_component_counter = 0;
170 LROOT = 1
171 first_available_in_list_of_tree_nodes = 1
172 for (i=0,i<N,++i) {
173 if (assigned_level_p[i]==0) {
174 connected_component_counter++;
175 connected_component_ptr[connected_component_counter] = LROOT
176 Paso_BandwidthReduction_dropTree(I, pattern_p
177
178 assigned_level_p,
179 index_t *list_of_tree_nodes_p,
180 &last_level_width,
181 &first_node_in_bottom_level,
182 &first_available_in_list_of_tree_nodes,
183 &num_levels,
184 &max_level_width, N)
185
186 connected_component_size_p[connected_component_counter] =
187 first_node_in_bottom_level + last_level_width - LROOT;
188 LROOT = first_node_in_bottom_level + last_level_width;
189 first_available_in_list_of_tree_nodes = LROOT;
190 }
191 }
192 /* on return from Paso_BandwidthReduction_chooseFinalLeveling, DirectionLargestComponent
193 indicates the direction the largest component fell.
194 DirectionLargestComponent is modIFied now to indicate the numbering direction.
195 num is set to the proper value for this direction. */
196 if (Paso_BandwidthReduction_sortConnectedComponentsInfos(connected_component_counter,
197 connected_component_size_p,
198 connected_component_ptr) {
199 Paso_BandwidthReduction_chooseFinalLeveling(forward_levels_p,
200 backward_levels_p,
201 ConnectedComponents_p,
202 IDFLT,
203 DirectionLargestComponent)
204 }
205 DirectionLargestComponent = DirectionLargestComponent*reverse_diameter_tree;
206 NUM= (DirectionLargestComponent<0) ? last_available_node_number :first_available_node_number;
207
208 CALL NUMBER(start_node, NUM, pattern_p, backward_levels_p, degree_p, new_label_p, forward_levels_p,
209 * assigned_level_p, N, reverse_diameter_tree, newBandwidth, newProfile, ConnectedComponents_p, DirectionLargestComponent)
210
211 /* update last_available_node_number or first_available_node_number after numbering */
212
213 if (DirectionLargestComponent<0) last_available_node_number = NUM;
214 if (DirectionLargestComponent>0) first_available_node_number = NUM;
215
216 }
217
218 /* if original numbering is better than new one, set up to return it */
219
220 if (newBandwidth > initial_bandwidth) {
221 for (i=0,i<N,++i) new_label_p[i] = label_p[i];
222 *newBandwidth = initial_bandwidth;
223 *newProfile = initial_profile;
224 }
225 return;
226 }
227 ===============================================
228 /* Finley_Reduce_setCharacteristics computes the degree_p of each node and stores it in the array degree_p. */
229 /* the bandwidth and profile for the original or input numbering of the graph is computed also. */
230
231 void Finley_Reduce_setCharacteristics(Paso_BandwidthReduction_p *pattern_p,
232 dim_t *degree_p,
233 dim_t* label_p,
234 long *bandwidth,long *initial_profile) {
235
236 long max_diff;
237 dim_t i;
238 *bandwidth = 0;
239 *profile = 0;
240 for (i=0,i<pattern_p->n_ptr,++i) {
241 max_diff = 0;
242 for (iptr=pattern_p->ptr[i],iptr<pattern_p->ptr[i+1],++i) {
243 diff = label_p[i] - label_p(pattern_p->index[iptr]);
244 max_diff = MAX(max_diff,diff);
245 }
246 *profile + = max_diff;
247 *bandwidth=MAX(*bandwidth,max_diff);
248 }
249 }
250 void Paso_BandwidthReduction_sortByDegree(index_t* node_index1,
251 index_t* node_index2,
252 dim_t* num_nodes1,
253 dim_t num_nodes2,
254 dim_t* degree_p)
255 {
256 /* Paso_BandwidthReduction_sortByDegree sorts node_index2 by degree_p of the NODE AND ADDS IT TO THE END
257 OF node_index1 IN ORDER OF LOWEST TO HIGHEST degree_p. num_nodes1 AND num_nodes2 ARE THE
258 NUMBER OF NODES IN node_index1 AND node_index2 RESPECTIVELY.
259 */
260 register bool_t swapped=TRUE;
261 register dim_t i, ipp;
262 register index_t node_index2_i, node_index2_ipp, temp;
263 register dim_t j=num_nodes2-1;
264 while (swapped && j>1) {
265 j--;
266 swapped = FALSE;
267 for (i=0; i<j; ++i) {
268 ipp=i+1
269 node_index2_i = node_index2[i]
270 node_index2_ipp = node_index2[ipp]
271 if (degree_p[node_index2_i]>degree_p[node_index2_ipp]) {
272 swapped= TRUE;
273 temp = node_index2[i];
274 node_index2[i] = node_index2[ipp];
275 node_index2[ipp] = temp;
276 }
277 }
278 }
279 for (i=0; i< num_nodes2; ++i) {
280 (*num_nodes1)++;
281 node_index1[num_nodes1] = node_index2[i]
282 }
283 return;
284 }
285
286
287 void Finley_Reduce_findDiameter(index_t *start_node,
288 index_t *end_node,
289 Paso_SystemMatrixPattern *pattern_p,
290 dim_t* degree_p,
291 index_t* forward_levels_p,
292 index_t* backward_levels_p,
293 *IDFLT,
294 index_t* work1_p,
295 index_t* work2_p,
296 index_t* node_list_p,
297 )
298 /*
299 Finley_Reduce_findDiameter is the control procedure for finding the pseudo-diameter of pattern
300 as well as the level structure from each end
301
302 start_node- on input this is the node number of the first attempt at finding a diameter.
303 on output it contains the actual number used.
304 end_node - on output contains other end of diameter
305 forward_levels_p- ARRAY CONTAINING LEVEL STRUCTURE WITH start_node AS ROOT
306 backward_levels_p- ARRAY CONTAINING LEVEL STRUCTURE WITH end_node AS ROOT
307 IDFLT- reverse_diameter_tree USED IN PICKING FINAL LEVEL STRUCTURE, SET
308 =1 if WIDTH OF forward_levels_p <= WIDTH OF backward_levels_p, OTHERWISE =2
309 assigned_level_p, list_of_tree_nodes_p- WORKING STORAGE
310
311 */
312
313
314 /* COMMON /GRA/ N, num_levels, ndeg_max
315 IT IS ASSUMED THAT THE LAST LEVEL HAS AT MOST 100 NODES.
316 COMMON /CC/ node_list(100)
317 DIMENSION pattern_p(N,1), degree_p(1), assigned_level_p(1), forward_levels_p(1), backward_levels_p(1),list_of_tree_nodes_p(1)
318 */
319 dim_t num_tree_nodes;
320 dim_t N= pattern->n_ptr;
321 bool_t find_new_starting_nodes=TRUE;
322
323 /* find initial set of nodes as the end points of the tree created by root */
324 while (find_new_starting_nodes) {
325 num_tree_nodes = 0;
326 /* zero assigned_level_p to indicate all nodes are available to Paso_BandwidthReduction_dropTree */
327 for (i=0,i<N,++i) forward_levels_p[i] = -1;
328
329 Paso_BandwidthReduction_dropTree(*(start_node),
330 pattern_p,
331 forward_levels_p,
332 work2_p,
333 degree_p,
334 num_tree_nodes, first_node_in_bottom_level,
335 first_available_in_list_of_tree_nodes,
336 num_levels, max_level_width_abort1, N)
337
338 node_list_len = 0;
339 /* sort last level by degree_p and store in node_list_p */
340 Paso_BandwidthReduction_sortByDegree(node_list_p, &(work2_p[first_node_in_bottom_level]),
341 *node_list_len, last_level_width, degree_p)
342
343 find_new_starting_nodes=FALSE;
344 /* now start searching from the ends points of the initial search */
345 NDXN=0;
346 while (NDXN < node_list_len) {
347 start_node2 = node_list[NDXN];
348
349 /* drop a tree from start_node2 */
350 for (i=0;i<N;++i) assigned_level_p[i] = -1;
351 num_tree_nodes = 0;
352 Paso_BandwidthReduction_dropTree(start_node2,
353 pattern_p,
354 work1_p,
355 work2_p,
356 degree_p, last_level_width, first_node_in_bottom_level,
357 num_tree_nodes,
358 num_levels2,
359 max_level_width, max_level_width_abort);
360 if (num_levels2<num_levels) {
361 start_node = start_node2
362 find_new_starting_nodes=TRUE;
363 break;
364 }
365 /* STORE NARROWEST REVERSE LEVEL STRUCTURE IN backward_levels_p */
366 if (max_level_width<max_level_width_abort) {
367 max_level_width_abort = max_level_width;
368 end_node = start_node2;
369 for (i=0;i<N;++i) backward_levels_p[i] = work1_p[i];
370 }
371 NDXN++;
372 }
373 if (max_level_width_abort2<=max_level_width_abort1)
374 *IDFLT = 2
375 } else {
376 *IDFLT=1
377 }
378 return
379 }
380
381 void Paso_BandwidthReduction_dropTree(index_t root,
382 Paso_SystemMatrixPattern *pattern_p,
383 index_t *assigned_level_p,
384 index_t *list_of_tree_nodes_p,
385 index_t *last_level_width,
386 index_t *first_node_in_bottom_level,
387 index_t *first_available_in_list_of_tree_nodes,
388 dim_t *num_levels,
389 dim_t *max_level_width, dim_t max_level_width_abort)
390
391 /*
392 Paso_BandwidthReduction_dropTree drops a tree in pattern_p from root
393
394 assigned_level_p- array of length length pattern_p->N indicating available nodes with -1 entries.
395 Paso_BandwidthReduction_dropTree enters level numbers .
396
397 list_of_tree_nodes_p - on output contains node numbers used in tree (array of length pattern_p->N)
398 sorted by levels where list_of_tree_nodes_p[first_available_in_list_of_tree_nodes]
399 contains root and list_of_tree_nodes_p[first_node_in_bottom_level+last_level_width-1]
400 contains last node entered)
401
402 last_level_width - on output contains width of last level
403 first_node_in_bottom_level - on output contains index into list_of_tree_nodes_p of first node in last level
404
405 first_available_in_list_of_tree_nodes-
406 on input the first available location in list_of_tree_nodes_p
407 usually zero but if list_of_tree_nodes_p is used to store previous
408 connected components, first_available_in_list_of_tree_nodes is
409 next available location. on output the
410
411 num_levels - number of levels
412
413 max_level_width - on output contains the maximum level width
414 max_level_width_abort- input param which triggers early return if max_level_width becomes >= max_level_width_abort
415
416 */
417
418 dim_t j;
419 index_t node_now;
420 index_t i_top = first_available_in_list_of_tree_nodes;
421 index_t i_now = first_available_in_list_of_tree_nodes;
422 *max_level_width = 0;
423 *first_node_in_bottom_level = first_available_in_list_of_tree_nodes;
424 *top_level = first_available_in_list_of_tree_nodes + 1;
425 *num_levels = 0
426
427 assigned_level_p[root] = *num_levels;
428 list_of_tree_nodes_p[i_top] = root;
429
430 while ( ( max_level_width<max_level_width_abort ) && ( i_top >=top_level ) ) {
431
432 num_levels++;
433
434 while (i_now>=top_level) {
435 node_now = list_of_tree_nodes_p[i_now];
436 for (j=pattern_p->iptr[node_now],j<pattern_p->iptr[node_now+1],++j) {
437 index = pattern_p->index[j];
438 if (assigned_level_p[index]<0) {
439 assigned_level_p[index] = (*num_levels);
440 i_top++;
441 list_of_tree_nodes_p[i_top] = index
442 }
443 }
444 i_now++;
445 }
446 *last_level_width = top_level - first_node_in_bottom_level;
447 *max_level_width = MAX(*max_level_width, last_level_width);
448 *first_node_in_bottom_level = i_now;
449 *top_level = i_top + 1;
450 }
451 }
452
453 void Paso_BandwidthReduction_setup(dim_t N, dim_t num_levels,
454 index_t* assigned_level_p,
455 index_t* forward_levels_p,
456 index_t* backward_levels_p,
457 dim_t* num_nodes_in_level_p)
458 {
459 /* Paso_BandwidthReduction_setup COMPUTES THE REVERSE LEVELING INFO FROM backward_levels_p AND STORES
460 IT INTO backward_levels_p. num_nodes_in_level_p[i] IS INITIALIZED TO NODES/ITH LEVEL FOR NODES
461 ON THE PSEUDO-diameter OF THE GRAPH. assigned_level_p IS INITIALIZED TO NON-
462 ZERO FOR NODES ON THE PSEUDO-diameter AND NODES IN A DifFERENT
463 COMPONENT OF THE GRAPH.
464 COMMON /GRA/ N, num_levels, ndeg_max
465 IT IS ASSUMED THAT THERE ARE AT MOST 100 LEVELS.
466 COMMON /assigned_level_pW/ NHIGH(100), NLOW(100), num_nodes_in_level_p(100)
467 DIMENSION assigned_level_p(1), forward_levels_p(1), backward_levels_p(1)
468 */
469 register dim_t i, Itemp;
470 for (i=0;i<num_levels;++i) num_nodes_in_level_p[i] = 0;
471 for (i=0;i<N;++i) {
472 assigned_level_p[i] = 1;
473 backward_levels_p[i] = num_levels - 1 - backward_levels_p[i];
474 Itemp = backward_levels_p[i]
475 if (Itemp < num_levels) {
476 if (Itemp==forward_levels_p[i]) {
477 num_nodes_in_level_p[Itemp]++;
478 } else {
479 assigned_level_p[i] = 0;
480 }
481 }
482 }
483 return;
484 }
485
486 bool_t Paso_BandwidthReduction_sortConnectedComponentsInfos( dim_t connected_component_counter,
487 dim_t *connected_component_size_p,
488 index_t *connected_component_ptr)
489
490 {
491 /*
492 Paso_BandwidthReduction_sortConnectedComponentsInfos sorts connected_component_size_p
493 and connected_component_ptr into descending order according to the values
494 of connected_component_size_p.
495
496 connected_component_counter=number of entries in each array
497
498 INTEGER temp, ConnectedComponents_p, connected_component_size_p, connected_component_ptr, connected_component_counter
499 IT IS ASSUMED THAT THE GRAPH HAS AT MOST 50 CONNECTED COMPONENTS.
500 COMMON /CC/ connected_component_counter, connected_component_size_p(50), connected_component_ptr(50)
501
502 */
503 bool_t swapped = TRUE;
504 bool_t out = FALSE;
505 if (connected_component_counter>0) {
506 out = TRUE;
507 j = connected_component_counter-1;
508 while (j>1 && swapped) {
509 swapped = FALSE;
510 j--;
511 for (i=0; i<j; i++) {
512 ipp= i + 1;
513 if (connected_component_size_p[i]<connected_component_size_p[ipp]) {
514 swapped = TRUE;
515 temp = connected_component_size_p[i];
516 connected_component_size_p[i] = connected_component_size_p[ipp];
517 connected_component_size_p[ipp] = temp;
518 temp = connected_component_ptr[i];
519 connected_component_ptr[i] = connected_component_ptr[ipp];
520 connected_component_ptr[ipp] = temp;
521 }
522 }
523 }
524 }
525 return out;
526 }
527 void Paso_BandwidthReduction_chooseFinalLeveling(
528 index_t *forward_levels_p,
529 index_t *backward_levels_p,
530 index_t *ConnectedComponents_p,
531 IDFLT,
532 DirectionLargestComponent
533 connected_component_counter
534 connected_component_size_p
535 connected_component_ptr)
536 /*
537
538 Paso_BandwidthReduction_chooseFinalLeveling chooses the level structure used in
539 numbering graph
540
541 forward_levels_p- on input contains forward leveling info
542 backward_levels_p- on input contains reverse leveling info
543 on output the final level structure chosen
544 ConnectedComponents_p - ON INPUT CONTAINS CONNECTED COMPONENT INFO
545 IDFLT- ON INPUT =1 if WDTH forward_levels_p<=WDTH backward_levels_p, =2 OTHERWISE
546 NHIGH KEEPS TRACK OF LEVEL WIDTHS FOR HIGH NUMBERING
547 NLOW- KEEPS TRACK OF LEVEL WIDTHS FOR LOW NUMBERING
548 num_nodes_in_level_p- KEEPS TRACK OF LEVEL WIDTHS FOR CHOSEN LEVEL STRUCTURE
549 connected_component_counter- NUMBER OF CONNECTED COMPONENTS
550 connected_component_size_p[i]- connected_component_size_p OF ITH CONNECTED COMPONENT
551 connected_component_ptr[i]- INDEX INTO ConnectedComponents_pE OF 1ST NODE IN ITH CON COMPT
552 DirectionLargestComponent- reverse_diameter_tree WHICH INDICATES WHICH WAY THE LARGEST CONNECTED COMPONENT FELL. =+1 if LOW AND -1 if HIGH
553
554 INTEGER ConnectedComponents_p, connected_component_size_p, connected_component_ptr, connected_component_counter, END
555 COMMON /GRA/ N, num_levels, ndeg_max
556 IT IS ASSUMED THAT THE GRAPH HAS AT MOST 50 COMPONENTS AND
557 THAT THERE ARE AT MOST 100 LEVELS.
558 COMMON /assigned_level_pW/ NHIGH(100), NLOW(100), num_nodes_in_level_p(100)
559 COMMON /CC/ connected_component_counter, connected_component_size_p(50), connected_component_ptr(50)
560 DIMENSION forward_levels_p(1), backward_levels_p(1), ConnectedComponents_p(1)
561
562 */
563 /* FOR EACH CONNECTED COMPONENT DO */
564 for (80 I=1,connected_component_counter
565 J = connected_component_ptr[i]
566 END = connected_component_size_p[i] + J - 1
567 /* SET NHIGH AND NLOW EQUAL TO num_nodes_in_level_p */
568 for (10 K=1,num_levels
569 NHIGH(K) = num_nodes_in_level_p(K)
570 NLOW(K) = num_nodes_in_level_p(K)
571 10 CONTINUE
572 /* UPDATE NHIGH AND NLOW FOR EACH NODE IN CONNECTED COMPONENT */
573 for (20 K=J,END
574 INODE = ConnectedComponents_p(K)
575 first_available_in_list_of_tree_nodesH = forward_levels_p(INODE)
576 NHIGH(first_available_in_list_of_tree_nodesH) = NHIGH(first_available_in_list_of_tree_nodesH) + 1
577 first_available_in_list_of_tree_nodesL = backward_levels_p(INODE)
578 NLOW(first_available_in_list_of_tree_nodesL) = NLOW(first_available_in_list_of_tree_nodesL) + 1
579 20 CONTINUE
580 MAnum_nodes1 = 0
581 MAnum_nodes2 = 0
582 /* SET MAnum_nodes1=LARGEST NEW NUMBER IN NHIGH */
583 /* SET MAnum_nodes2=LARGEST NEW NUMBER IN NLOW */
584 for (30 K=1,num_levels
585 if (2*num_nodes_in_level_p(K).EQ.NLOW(K)+NHIGH(K)) GO TO 30
586 if (NHIGH(K)>MAnum_nodes1) MAnum_nodes1 = NHIGH(K)
587 if (NLOW(K)>MAnum_nodes2) MAnum_nodes2 = NLOW(K)
588 30 CONTINUE
589 /* SET IT= NUMBER OF LEVEL STRUCTURE TO BE USED */
590 IT = 1
591 if (MAnum_nodes1>MAnum_nodes2) IT = 2
592 if (MAnum_nodes1.EQ.MAnum_nodes2) IT = IDFLT
593 if (IT.EQ.2) GO TO 60
594 if (I.EQ.1) DirectionLargestComponent = -1
595 /* COPY forward_levels_p INTO backward_levels_p FOR EACH NODE IN CONNECTED COMPONENT */
596 for (40 K=J,END
597 INODE = ConnectedComponents_p(K)
598 backward_levels_p(INODE) = forward_levels_p(INODE)
599 40 CONTINUE
600 /* UPDATE num_nodes_in_level_p TO BE THE SAME AS NHIGH */
601 for (50 K=1,num_levels
602 num_nodes_in_level_p(K) = NHIGH(K)
603 50 CONTINUE
604 GO TO 80
605 /* UPDATE num_nodes_in_level_p TO BE THE SAME AS NLOW */
606 60 for (70 K=1,num_levels
607 num_nodes_in_level_p(K) = NLOW(K)
608 70 CONTINUE
609 80 CONTINUE
610 return;
611 }
612
613 SUBROUTINE NUMBER(start_node2, NUM, pattern_p, backward_levels_p, degree_p, new_label_p, assigned_level_pST, NUM 10
614 * Lconnected_component_ptr, N, reverse_diameter_tree, newBandwidth, newProfile, IPFA, DirectionLargestComponent)
615 /* NUMBER PRODUCES THE NUMBERING OF THE GRAPH FOR MIN BANDWIDTH
616 /* start_node2- ON INPUT THE NODE TO BEGIN NUMBERING ON
617 /* NUM- ON INPUT AND OUTPUT, THE NEXT AVAILABLE NUMBER
618 /* backward_levels_p- THE LEVEL STRUCTURE TO BE USED IN NUMBERING
619 /* new_label_p- THE ARRAY USED TO STORE THE NEW NUMBERING
620 /* assigned_level_pST- ON OUTPUT CONTAINS LEVEL STRUCTURE
621 /* Lconnected_component_ptr[i]- ON OUTPUT, INDEX INTO assigned_level_pST TO FIRST NODE IN ITH assigned_level_p
622 /* Lconnected_component_ptr(I+1) - Lconnected_component_ptr[i] = NUMBER OF NODES IN ITH assigned_level_p
623 /* reverse_diameter_tree- =+1 if start_node2 IS FORWARD END OF PSEUDO-diameter
624 /* =-1 if start_node2 IS REVERSE END OF PSEUDO-diameter
625 /* newBandwidth- BANDWIDTH OF NEW NUMBERING COMPUTED BY NUMBER
626 /* newProfile- PROFILE OF NEW NUMBERING COMPUTED BY NUMBER
627 /* IPFA- WORKING STORAGE USED TO COMPUTE PROFILE AND BANDWIDTH
628 /* DirectionLargestComponent- INDICATES STEP DIRECTION USED IN NUMBERING(+1 OR -1)
629 /* USE INTEGER*2 pattern_p WITH AN IBM 360 OR 370.
630 INTEGER pattern_p
631 INTEGER start_node2, node_indexA, node_indexB, node_indexC, node_indexD, XA, XB, connected_component_counter, XD, CX, END,
632 * new_label_p, TEST
633 COMMON /GRA/ N, num_levels, ndeg_max
634 /* THE STORAGE IN COMMON BLOCKS CC AND assigned_level_pW IS NOW FREE AND CAN
635 /* BE USED FOR STACKS.
636 COMMON /assigned_level_pW/ node_indexA(100), node_indexB(100), node_indexC(100)
637 COMMON /CC/ node_indexD(100)
638 DIMENSION IPFA(1)
639 DIMENSION pattern_p(N,1), backward_levels_p(1), degree_p(1), new_label_p(1), assigned_level_pST(1),
640 * Lconnected_component_ptr(1)
641 /* SET UP assigned_level_pST AND Lconnected_component_ptr FROM backward_levels_p
642 for (10 i=0,i<N,++i)
643 IPFA[i] = 0
644 10 CONTINUE
645 Nconnected_component_ptr = 1
646 for (30 I=1,num_levels
647 Lconnected_component_ptr[i] = Nconnected_component_ptr
648 for (20 J=1,N
649 if (backward_levels_p(J)!=I) GO TO 20
650 assigned_level_pST(Nconnected_component_ptr) = J
651 Nconnected_component_ptr = Nconnected_component_ptr + 1
652 20 CONTINUE
653 30 CONTINUE
654 Lconnected_component_ptr(num_levels+1) = Nconnected_component_ptr
655 /* node_indexA, node_indexB, node_indexC AND node_indexD ARE STACKS WITH POINTERS
656 /* XA,XB,connected_component_counter, AND XD. CX IS A SPECIAL POINTER INTO node_indexC WHICH
657 /* INDICATES THE PARTICULAR NODE BEING PROCESSED.
658 /* first_available_in_list_of_tree_nodes KEEPS TRACK OF THE LEVEL WE ARE WORKING AT.
659 /* INITIALLY node_indexC CONTAINS ONLY THE INITIAL NODE, start_node2.
660 first_available_in_list_of_tree_nodes = 0
661 if (reverse_diameter_tree<0) first_available_in_list_of_tree_nodes = num_levels + 1
662 connected_component_counter = 1
663 node_indexC(connected_component_counter) = start_node2
664 40 CX = 1
665 XD = 0
666 first_available_in_list_of_tree_nodes = first_available_in_list_of_tree_nodes + reverse_diameter_tree
667 LST = Lconnected_component_ptr(first_available_in_list_of_tree_nodes)
668 LND = Lconnected_component_ptr(first_available_in_list_of_tree_nodes+1) - 1
669 /* BEGIN PROCESSING NODE node_indexC(CX)
670 50 IPRO = node_indexC(CX)
671 new_label_p(IPRO) = NUM
672 NUM = NUM + DirectionLargestComponent
673 END = degree_p(IPRO)
674 XA = 0
675 XB = 0
676 /* CHECK ALL ADJACENT NODES
677 for (80 I=1,END
678 TEST = pattern_p(IPRO,I)
679 INX = new_label_p(TEST)
680 /* ONLY NODES NOT NUMBERED OR ALREADY ON A STACK ARE ADDED
681 if (INX.EQ.0) GO TO 60
682 if (INX<0) GO TO 80
683 /* for (PRELIMINARY BANDWIDTH AND PROFILE CALCULATIONS
684 NBW = (new_label_p(IPRO)-INX)*DirectionLargestComponent
685 if (DirectionLargestComponent>0) INX = new_label_p(IPRO)
686 if (IPFA(INX)<NBW) IPFA(INX) = NBW
687 GO TO 80
688 60 new_label_p(TEST) = -1
689 /* PUT NODES ON SAME LEVEL ON node_indexA, ALL OTHERS ON node_indexB
690 if (backward_levels_p(TEST).EQ.backward_levels_p(IPRO)) GO TO 70
691 XB = XB + 1
692 node_indexB(XB) = TEST
693 GO TO 80
694 70 XA = XA + 1
695 node_indexA(XA) = TEST
696 80 CONTINUE
697 /* SORT node_indexA AND node_indexB INTO INCREASING degree_p AND ADD node_indexA TO node_indexC
698 /* AND node_indexB TO node_indexD
699 if (XA.EQ.0) GO TO 100
700 if (XA.EQ.1) GO TO 90
701 CALL Paso_BandwidthReduction_sortByDegree(node_indexC, node_indexA, connected_component_counter, XA, degree_p)
702 GO TO 100
703 90 connected_component_counter = connected_component_counter + 1
704 node_indexC(connected_component_counter) = node_indexA(XA)
705 100 if (XB.EQ.0) GO TO 120
706 if (XB.EQ.1) GO TO 110
707 CALL Paso_BandwidthReduction_sortByDegree(node_indexD, node_indexB, XD, XB, degree_p)
708 GO TO 120
709 110 XD = XD + 1
710 node_indexD(XD) = node_indexB(XB)
711 /* BE SURE TO PROCESS ALL NODES IN node_indexC
712 120 CX = CX + 1
713 if (connected_component_counter>=CX) GO TO 50
714 /* WHEN node_indexC IS EXHAUSTED LOOK FOR MIN degree_p NODE IN SAME LEVEL
715 /* WHICH HAS NOT BEEN PROCESSED
716 MAX = ndeg_max + 1
717 start_node2 = N + 1
718 for (130 I=LST,LND
719 TEST = assigned_level_pST[i]
720 if (new_label_p(TEST)!=0) GO TO 130
721 if (degree_p(TEST)>=MAX) GO TO 130
722 new_label_p(start_node2) = 0
723 new_label_p(TEST) = -1
724 MAX = degree_p(TEST)
725 start_node2 = TEST
726 130 CONTINUE
727 if (start_node2.EQ.N+1) GO TO 140
728 connected_component_counter = connected_component_counter + 1
729 node_indexC(connected_component_counter) = start_node2
730 GO TO 50
731 /* if node_indexD IS EMPTY WE ARE DONE, OTHERWISE COPY node_indexD ONTO node_indexC
732 /* AND BEGIN PROCESSING NEW node_indexC
733 140 if (XD.EQ.0) GO TO 160
734 for (150 I=1,XD
735 node_indexC[i] = node_indexD[i]
736 150 CONTINUE
737 connected_component_counter = XD
738 GO TO 40
739 /* for (FINAL BANDWIDTH AND PROFILE CALCULATIONS
740 160 for (170 i=0,i<N,++i)
741 if (IPFA[i]>newBandwidth) newBandwidth = IPFA[i]
742 newProfile = newProfile + IPFA[i]
743 170 CONTINUE
744 RETURN
745 END

  ViewVC Help
Powered by ViewVC 1.1.26