1#include "BSprivate.h" 2 3/*+ BSido_color - Do a local IDO coloring 4 5 Input Parameters: 6. ido_queue - the nodes to color 7. n_queue - the length of the ido_queue 8. A - the sparse matrix 9. local_color - the local coloring 10. global_color - the colors of global nodes adjacent to each processor 11. local_ptr - array of pointers indicating which neighbors in 12. each row are local neighbors (on this processor) 13. global_ptr - array of pointers indicating which neighbors in 14. each row are global neighbors (not on this processor) 15. color_template - used to figure out what colors are around a node 16. ido_degree - the ido degree of each node 17. ido_queue_ptr - a work vector (should be 0's) 18. ido_deg_ptr - a work vector 19. procinfo - the usual processor info 20 21 Output Parameters: 22. ido_degree - the updated ido degree of nodes 23+*/ 24void BSido_color(int *ido_queue, int n_queue, BSspmat *A, int *local_color, 25 int **global_color, int *local_ptr, int *global_ptr, int *color_template, 26 int *ido_degree, int *ido_queue_ptr, int *ido_deg_ptr, BSprocinfo *procinfo) 27{ 28 BSsprow **local_col_array; 29 int *row_ptr; 30 BSsprow *t_node; 31 int i, j; 32 int max_ido_deg, deg, l_vtx, t_color; 33 int p1, p2, v1, v2; 34 35 local_col_array = A->rows; 36 37 /* Get ido_degrees and store as key in ido_queue_ptr */ 38 39 ido_queue_ptr[0] = 0; 40 for (i=0; i<n_queue; i++) 41 { 42 l_vtx = ido_queue[i]; 43 ido_queue_ptr[i] = ido_degree[l_vtx]; 44 } 45 46 /* Sort ido_queue by ido_degree; sorts both ido_queue_ptr & ido_queue */ 47 48 BSheap_sorthl1(n_queue,ido_queue_ptr,ido_queue); CHKERR(0); 49 50 /* Construct ido_deg_ptrs for ido_queue */ 51 52 max_ido_deg = ido_queue_ptr[0]; 53 ido_queue_ptr[0] = 0; 54 deg = max_ido_deg; 55 for (i=1; i<n_queue; i++) { 56 while (ido_queue_ptr[i] != deg) { 57 ido_deg_ptr[deg] = i-1; 58 deg--; 59 } 60 ido_queue_ptr[i] = 0; 61 } 62 ido_deg_ptr[deg] = n_queue - 1; 63 64 /* Construct ido_queue_ptrs */ 65 66 for (i=0; i<n_queue; i++) { 67 l_vtx = ido_queue[i]; 68 ido_queue_ptr[l_vtx] = i; 69 } 70 71 /* Main loop */ 72 73 for (i=0; i<n_queue; i++) { 74 l_vtx = ido_queue[i]; 75 t_node = local_col_array[l_vtx]; 76 row_ptr = t_node->col; 77 78 /* Check global adjacent nodes & mark unusable colors */ 79 80 for (j=0; j<global_ptr[l_vtx]; j++) { 81 t_color = global_color[l_vtx][j]; 82 color_template[t_color] = l_vtx; 83 } 84 85 /* Check local nodes and update their degree or mark unusable colors */ 86 87 for (j=local_ptr[l_vtx]; j<t_node->length; j++) { 88 (*A->map->fglobal2local) 89 (1,&(row_ptr[j]),&v1,procinfo,A->map);CHKERR(0); 90 if (v1 < 0) { 91 MY_SETERRC(COLOR_ERROR,"Bad global to local translation\n"); 92 } 93 t_color = local_color[v1]; 94 if (t_color == NO_COLOR) { 95 ido_degree[v1]++; 96 p1 = ido_queue_ptr[v1]; 97 if(p1 > i) { 98 if (ido_degree[v1] > max_ido_deg) { 99 max_ido_deg = ido_degree[v1]; 100 p2 = i+1; 101 ido_deg_ptr[max_ido_deg] = p2; 102 } 103 else { 104 ido_deg_ptr[ido_degree[v1]]++; 105 p2 = ido_deg_ptr[ido_degree[v1]]; 106 } 107 if (p1 != p2) { 108 v2 = ido_queue[p2]; 109 ido_queue[p1] = v2; 110 ido_queue[p2] = v1; 111 ido_queue_ptr[v1] = p2; 112 ido_queue_ptr[v2] = p1; 113 } 114 } 115 } 116 else 117 { 118 color_template[t_color] = l_vtx; 119 } 120 } 121 while ((ido_deg_ptr[max_ido_deg] == i) && (max_ido_deg > 0)) max_ido_deg--; 122 123 /* Choose t_color */ 124 125 t_color = 0; 126 while (color_template[t_color] == l_vtx) 127 t_color++; 128 local_color[l_vtx] = t_color; 129 } 130 131 /* Clean up ido_queue_ptr */ 132 133 for (i=0; i<n_queue; i++) 134 { 135 l_vtx = ido_queue[i]; 136 ido_queue_ptr[l_vtx] = 0; 137 } 138 139} 140