Charm++: Charm Source Code Documentation

00001 /*
00002  * Copyright 1997, Regents of the University of Minnesota
00003  *
00004  * selectq.c
00005  *
00006  * This file contains the driving routines for multilevel k-way refinement
00007  *
00008  * Started 7/28/97
00009  * George
00010  *
00011  * $Id$
00012  */
00013 
00014 #include <parmetislib.h>
00015 
00016 /*************************************************************************
00017 *  This stuff is hardcoded for up to four constraints
00018 **************************************************************************/
00019 void Moc_DynamicSelectQueue(int nqueues, int ncon, int subdomain1, int subdomain2,
00020      idxtype *currentq, floattype *flows, int *from, int *qnum, int minval, floattype avgvwgt,
00021      floattype maxdiff)
00022 {
00023   int i, j;
00024   int hash, index = -1, current;
00025   int cand[MAXNCON], rank[MAXNCON], dont_cares[MAXNCON];
00026   int nperms, perm[24][5];
00027   floattype sign = 0.0;
00028   KVType array[MAXNCON];
00029 int mype;
00030 MPI_Comm_rank(MPI_COMM_WORLD, &mype);
00031 
00032   *qnum = -1;
00033 
00034   if (*from == -1) {
00035     for (i=0; i<ncon; i++) {
00036       array[i].key = i;
00037       array[i].val = (fabs)(flows[i]);
00038     }
00039 
00040     qsort(array, ncon, sizeof(KVType), myvalkeycompare);
00041     ASSERTS(array[ncon-1].val - array[0].val <= maxdiff)
00042 
00043     if (flows[array[ncon-1].key]>avgvwgt*MOC_GD_GRANULARITY_FACTOR) {
00044       *from = subdomain1;
00045       sign = 1.0;
00046       index = 0;
00047     }
00048 
00049     if (flows[array[ncon-1].key]<-1.0*avgvwgt*MOC_GD_GRANULARITY_FACTOR) {
00050       *from = subdomain2;
00051       sign = -1.0;
00052       index = nqueues;
00053     }
00054 
00055     if (*from == -1) {
00056       return;
00057     }
00058   }
00059   else {
00060     ASSERTS(*from == subdomain1 || *from == subdomain2);
00061 
00062     if (*from == subdomain1) {
00063       sign = 1.0;
00064       index = 0;
00065     }
00066     else {
00067       sign = -1.0;
00068       index = nqueues;
00069     }
00070   }
00071 
00072   for (i=0; i<ncon; i++) {
00073     array[i].key = i;
00074     array[i].val = flows[i] * sign;
00075   }
00076 
00077   qsort(array, ncon, sizeof(KVType), myvalkeycompare);
00078 
00079   iset(ncon, 1, dont_cares);
00080 
00081   current = 0;
00082   for (i=0; i<ncon-1; i++) 
00083     if (array[i+1].val - array[i].val < maxdiff * MC_FLOW_BALANCE_THRESHOLD && dont_cares[current] < ncon-1) {
00084       dont_cares[current]++;
00085       dont_cares[i+1] = 0;
00086     }
00087     else
00088       current = i+1;
00089 
00090 
00091   switch (ncon) {
00092     /***********************/
00093     case 2:
00094       nperms = 1;
00095       perm[0][0] = 0;   perm[0][1] = 1;
00096 
00097       break;
00098     /***********************/
00099     case 3:
00100 
00101       /* if the first and second flows are close */
00102       if (dont_cares[0] == 2 && dont_cares[1] == 0 && dont_cares[2] == 1) {
00103         nperms = 4;
00104         perm[0][0] = 0;   perm[0][1] = 1;   perm[0][2] = 2;
00105         perm[1][0] = 1;   perm[1][1] = 0;   perm[1][2] = 2;
00106         perm[2][0] = 0;   perm[2][1] = 2;   perm[2][2] = 1;
00107         perm[3][0] = 1;   perm[3][1] = 2;   perm[3][2] = 0;
00108         break;
00109       }
00110 
00111       /* if the second and third flows are close */
00112       if (dont_cares[0] == 1 && dont_cares[1] == 2 && dont_cares[2] == 0) {
00113         nperms = 4;
00114         perm[0][0] = 0;   perm[0][1] = 1;   perm[0][2] = 2;
00115         perm[1][0] = 0;   perm[1][1] = 2;   perm[1][2] = 1;
00116         perm[2][0] = 1;   perm[2][1] = 0;   perm[2][2] = 2;
00117         perm[3][0] = 2;   perm[3][1] = 0;   perm[3][2] = 1;
00118         break;
00119       }
00120 
00121       /* all or none of the flows are close */
00122       nperms = 3;
00123       perm[0][0] = 0;   perm[0][1] = 1;   perm[0][2] = 2;
00124       perm[1][0] = 1;   perm[1][1] = 0;   perm[1][2] = 2;
00125       perm[2][0] = 0;   perm[2][1] = 2;   perm[2][2] = 1;
00126 
00127       break;
00128     /***********************/
00129     case 4:
00130 
00131       if (dont_cares[0] == 2 && dont_cares[1] == 0 &&
00132           dont_cares[2] == 1 && dont_cares[3] == 1) {
00133         nperms = 14;
00134         perm[0][0] =  0;   perm[0][1] =  1;   perm[0][2] =  2;   perm[0][3] =  3;
00135         perm[1][0] =  1;   perm[1][1] =  0;   perm[1][2] =  2;   perm[1][3] =  3;
00136         perm[2][0] =  0;   perm[2][1] =  2;   perm[2][2] =  1;   perm[2][3] =  3;
00137         perm[3][0] =  1;   perm[3][1] =  2;   perm[3][2] =  0;   perm[3][3] =  3;
00138         perm[4][0] =  0;   perm[4][1] =  1;   perm[4][2] =  3;   perm[4][3] =  2;
00139         perm[5][0] =  1;   perm[5][1] =  0;   perm[5][2] =  3;   perm[5][3] =  2;
00140         
00141         perm[6][0] =  0;   perm[6][1] =  3;   perm[6][2] =  1;   perm[6][3] =  2;
00142         perm[7][0] =  1;   perm[7][1] =  3;   perm[7][2] =  0;   perm[7][3] =  2;
00143 
00144         perm[8][0] =  0;   perm[8][1] =  2;   perm[8][2] =  3;   perm[8][3] =  1;
00145         perm[9][0] =  1;   perm[9][1] =  2;   perm[9][2] =  3;   perm[9][3] =  0;
00146 
00147         perm[10][0] = 2;   perm[10][1] = 0;   perm[10][2] = 1;   perm[10][3] = 3;
00148         perm[11][0] = 2;   perm[11][1] = 1;   perm[11][2] = 0;   perm[11][3] = 3;
00149         
00150         perm[12][0] = 0;   perm[12][1] = 3;   perm[12][2] = 2;   perm[12][3] = 1;
00151         perm[13][0] = 1;   perm[13][1] = 3;   perm[13][2] = 2;   perm[13][3] = 0;
00152         break;
00153       }
00154 
00155       if (dont_cares[0] == 1 && dont_cares[1] == 1 &&
00156           dont_cares[2] == 2 && dont_cares[3] == 0) {
00157         nperms = 14;
00158         perm[0][0] =  0;   perm[0][1] =  1;   perm[0][2] =  2;   perm[0][3] =  3;
00159         perm[1][0] =  0;   perm[1][1] =  1;   perm[1][2] =  3;   perm[1][3] =  2;
00160         perm[2][0] =  0;   perm[2][1] =  2;   perm[2][2] =  1;   perm[2][3] =  3;
00161         perm[3][0] =  0;   perm[3][1] =  3;   perm[3][2] =  1;   perm[3][3] =  2;
00162         perm[4][0] =  1;   perm[4][1] =  0;   perm[4][2] =  2;   perm[4][3] =  3;
00163         perm[5][0] =  1;   perm[5][1] =  0;   perm[5][2] =  3;   perm[5][3] =  2;
00164 
00165         perm[6][0] =  1;   perm[6][1] =  2;   perm[6][2] =  0;   perm[6][3] =  3;
00166         perm[7][0] =  1;   perm[7][1] =  3;   perm[7][2] =  0;   perm[7][3] =  2;
00167 
00168         perm[8][0] =  2;   perm[8][1] =  0;   perm[8][2] =  1;   perm[8][3] =  3;
00169         perm[9][0] =  3;   perm[9][1] =  0;   perm[9][2] =  1;   perm[9][3] =  2;
00170 
00171         perm[10][0] = 0;   perm[10][1] = 2;   perm[10][2] = 3;   perm[10][3] = 1;
00172         perm[11][0] = 0;   perm[11][1] = 3;   perm[11][2] = 2;   perm[11][3] = 1;
00173 
00174         perm[12][0] = 2;   perm[12][1] = 1;   perm[12][2] = 0;   perm[12][3] = 3;
00175         perm[13][0] = 3;   perm[13][1] = 1;   perm[13][2] = 0;   perm[13][3] = 2;
00176         break;
00177       }
00178 
00179       if (dont_cares[0] == 2 && dont_cares[1] == 0 &&
00180           dont_cares[2] == 2 && dont_cares[3] == 0) {
00181         nperms = 14;
00182         perm[0][0] =  0;   perm[0][1] =  1;   perm[0][2] =  2;   perm[0][3] =  3;
00183         perm[1][0] =  1;   perm[1][1] =  0;   perm[1][2] =  2;   perm[1][3] =  3;
00184         perm[2][0] =  0;   perm[2][1] =  1;   perm[2][2] =  3;   perm[2][3] =  2;
00185         perm[3][0] =  1;   perm[3][1] =  0;   perm[3][2] =  3;   perm[3][3] =  2;
00186 
00187         perm[4][0] =  0;   perm[4][1] =  2;   perm[4][2] =  1;   perm[4][3] =  3;
00188         perm[5][0] =  1;   perm[5][1] =  2;   perm[5][2] =  0;   perm[5][3] =  3;
00189         perm[6][0] =  0;   perm[6][1] =  3;   perm[6][2] =  1;   perm[6][3] =  2;
00190         perm[7][0] =  1;   perm[7][1] =  3;   perm[7][2] =  0;   perm[7][3] =  2;
00191 
00192         perm[8][0] = 2;    perm[8][1] = 0;    perm[8][2] = 1;    perm[8][3] = 3;
00193         perm[9][0] = 0;    perm[9][1] = 2;    perm[9][2] = 3;    perm[9][3] = 1;
00194         perm[10][0] = 2;   perm[10][1] = 1;   perm[10][2] = 0;   perm[10][3] = 3;
00195         perm[11][0] = 0;   perm[11][1] = 3;   perm[11][2] = 2;   perm[11][3] = 1;
00196         perm[12][0] = 3;   perm[12][1] = 0;   perm[12][2] = 1;   perm[12][3] = 2;
00197         perm[13][0] = 1;   perm[13][1] = 2;   perm[13][2] = 3;   perm[13][3] = 0;
00198         break;
00199       }
00200 
00201       if (dont_cares[0] == 3 && dont_cares[1] == 0 &&
00202           dont_cares[2] == 0 && dont_cares[3] == 1) {
00203         nperms = 14;
00204         perm[0][0] =  0;   perm[0][1] =  1;   perm[0][2] =  2;   perm[0][3] =  3;
00205         perm[1][0] =  0;   perm[1][1] =  2;   perm[1][2] =  1;   perm[1][3] =  3;
00206         perm[2][0] =  1;   perm[2][1] =  0;   perm[2][2] =  2;   perm[2][3] =  3;
00207         perm[3][0] =  2;   perm[3][1] =  0;   perm[3][2] =  1;   perm[3][3] =  3;
00208         perm[4][0] =  1;   perm[4][1] =  2;   perm[4][2] =  0;   perm[4][3] =  3;
00209         perm[5][0] =  2;   perm[5][1] =  1;   perm[5][2] =  0;   perm[5][3] =  3;
00210 
00211         perm[6][0] =  0;   perm[6][1] =  1;   perm[6][2] =  3;   perm[6][3] =  2;
00212         perm[7][0] =  1;   perm[7][1] =  0;   perm[7][2] =  3;   perm[7][3] =  2;
00213         perm[8][0] =  0;   perm[8][1] =  2;   perm[8][2] =  3;   perm[8][3] =  1;
00214         perm[9][0] =  2;   perm[9][1] =  0;   perm[9][2] =  3;   perm[9][3] =  1;
00215         perm[10][0] = 1;   perm[10][1] = 2;   perm[10][2] = 3;   perm[10][3] = 0;
00216         perm[11][0] = 2;   perm[11][1] = 1;   perm[11][2] = 3;   perm[11][3] = 0;
00217 
00218         perm[12][0] = 0;   perm[12][1] = 3;   perm[12][2] = 1;   perm[12][3] = 2;
00219         perm[13][0] = 0;   perm[13][1] = 3;   perm[13][2] = 2;   perm[13][3] = 1;
00220         break;
00221       }
00222 
00223       if (dont_cares[0] == 1 && dont_cares[1] == 3 &&
00224           dont_cares[2] == 0 && dont_cares[3] == 0) {
00225         nperms = 14;
00226         perm[0][0] =  0;   perm[0][1] =  1;   perm[0][2] =  2;   perm[0][3] =  3;
00227         perm[1][0] =  0;   perm[1][1] =  2;   perm[1][2] =  1;   perm[1][3] =  3;
00228         perm[2][0] =  0;   perm[2][1] =  1;   perm[2][2] =  3;   perm[2][3] =  2;
00229         perm[3][0] =  0;   perm[3][1] =  2;   perm[3][2] =  3;   perm[3][3] =  1;
00230         perm[4][0] =  0;   perm[4][1] =  3;   perm[4][2] =  1;   perm[4][3] =  2;
00231         perm[5][0] =  0;   perm[5][1] =  3;   perm[5][2] =  2;   perm[5][3] =  1;
00232 
00233         perm[6][0] =  1;   perm[6][1] =  0;   perm[6][2] =  2;   perm[6][3] =  3;
00234         perm[7][0] =  1;   perm[7][1] =  0;   perm[7][2] =  3;   perm[7][3] =  2;
00235         perm[8][0] =  2;   perm[8][1] =  0;   perm[8][2] =  1;   perm[8][3] =  3;
00236         perm[9][0] =  2;   perm[9][1] =  0;   perm[9][2] =  3;   perm[9][3] =  1;
00237         perm[10][0] = 3;   perm[10][1] = 0;   perm[10][2] = 1;   perm[10][3] = 2;
00238         perm[11][0] = 3;   perm[11][1] = 0;   perm[11][2] = 2;   perm[11][3] = 1;
00239 
00240         perm[12][0] = 1;   perm[12][1] = 2;   perm[12][2] = 0;   perm[12][3] = 3;
00241         perm[13][0] = 2;   perm[13][1] = 1;   perm[13][2] = 0;   perm[13][3] = 3;
00242 
00243         break;
00244       }
00245 
00246       nperms = 14;
00247       perm[0][0] =  0;   perm[0][1] =  1;   perm[0][2] =  2;   perm[0][3] =  3;
00248       perm[1][0] =  1;   perm[1][1] =  0;   perm[1][2] =  2;   perm[1][3] =  3;
00249       perm[2][0] =  0;   perm[2][1] =  2;   perm[2][2] =  1;   perm[2][3] =  3;
00250       perm[3][0] =  0;   perm[3][1] =  1;   perm[3][2] =  3;   perm[3][3] =  2;
00251       perm[4][0] =  1;   perm[4][1] =  0;   perm[4][2] =  3;   perm[4][3] =  2;
00252 
00253       perm[5][0] =  2;   perm[5][1] =  0;   perm[5][2] =  1;   perm[5][3] =  3;
00254       perm[6][0] =  0;   perm[6][1] =  2;   perm[6][2] =  3;   perm[6][3] =  1;
00255 
00256       perm[7][0] =  1;   perm[7][1] =  2;   perm[7][2] =  0;   perm[7][3] =  3;
00257       perm[8][0] =  0;   perm[8][1] =  3;   perm[8][2] =  1;   perm[8][3] =  2;
00258 
00259       perm[9][0] =  2;   perm[9][1] =  1;   perm[9][2] =  0;   perm[9][3] =  3;
00260       perm[10][0] = 0;   perm[10][1] = 3;   perm[10][2] = 2;   perm[10][3] = 1;
00261       perm[11][0] = 2;   perm[11][1] = 0;   perm[11][2] = 3;   perm[11][3] = 1;
00262 
00263       perm[12][0] = 3;   perm[12][1] = 0;   perm[12][2] = 1;   perm[12][3] = 2;
00264       perm[13][0] = 1;   perm[13][1] = 2;   perm[13][2] = 3;   perm[13][3] = 0;
00265       break;
00266     /***********************/
00267     default:
00268       return;
00269   }
00270 
00271   for (i=0; i<nperms; i++) {
00272     for (j=0; j<ncon; j++)
00273       cand[j] = array[perm[i][j]].key;
00274 
00275     for (j=0; j<ncon; j++)
00276       rank[cand[j]] = j;
00277 
00278 
00279     hash = Moc_HashVRank(ncon, rank) - minval;
00280     if (currentq[hash+index] > 0) {
00281       *qnum = hash;
00282       return;
00283     }
00284   }
00285 
00286   return;
00287 }
00288 
00289 
00290 /*************************************************************************
00291 *  This function sorts the nvwgts of a vertex and returns a hashed value
00292 **************************************************************************/
00293 int Moc_HashVwgts(int ncon, floattype *nvwgt)
00294 {
00295   int i;
00296   int multiplier, retval;
00297   int rank[MAXNCON];
00298   KVType array[MAXNCON];
00299 
00300 
00301   for (i=0; i<ncon; i++) {
00302     array[i].key = i;
00303     array[i].val = nvwgt[i];
00304   }
00305 
00306   qsort(array, ncon, sizeof(KVType), myvalkeycompare);
00307   for (i=0; i<ncon; i++)
00308     rank[array[i].key] = i;
00309 
00310   multiplier = 1;
00311 
00312   retval = 0;
00313   for (i=0; i<ncon; i++) {
00314     multiplier *= (i+1);
00315     retval += rank[ncon-i-1] * multiplier;
00316   }
00317 
00318   return retval;
00319 }
00320 
00321 
00322 /*************************************************************************
00323 *  This function sorts the vwgts of a vertex and returns a hashed value
00324 **************************************************************************/
00325 int Moc_HashVRank(int ncon, int *vwgt)
00326 {
00327   int i, multiplier, retval;
00328 
00329   multiplier = 1;
00330 
00331   retval = 0;
00332   for (i=0; i<ncon; i++) {
00333     multiplier *= (i+1);
00334     retval += vwgt[ncon-1-i] * multiplier;
00335   }
00336 
00337   return retval;
00338 }
00339 
00340
libs/ck-libs/parmetis/ParMETISLib/selectq.c
