Fixed a bug in get_hop_count
authorAmit Sharma <asharma6@uiuc.edu>
Mon, 23 May 2005 18:07:18 +0000 (18:07 +0000)
committerAmit Sharma <asharma6@uiuc.edu>
Mon, 23 May 2005 18:07:18 +0000 (18:07 +0000)
src/conv-ldb/topology.C
src/conv-ldb/topology.h

index c1a6a2746ae2a111598703b3ca74c19048716c3e..5375ff186d49580a9971fc3b47bc573c00ba8cfa 100644 (file)
@@ -31,30 +31,31 @@ int LBTopology::get_hop_count(int src,int dest)
        npe = max_neighbors();
        visited_srcs = new int[npes];
        
-       int count = rec_hop_count(src,dest,npe,1,visited_srcs); 
+       int count = rec_hop_count(src,dest,npe,1,visited_srcs,999999);
        delete [] visited_srcs;
 
        return count;
 }
 
-int LBTopology::rec_hop_count(int src,int dest,int max_neigh,int count,int *visited_srcs)
+int LBTopology::rec_hop_count(int src,int dest,int max_neigh,int count,int *visited_srcs,int min_hop_cnt)
 {
        int *pes = new int[max_neigh];
-       int min_hop_cnt=999999;
+       //int min_hop_cnt=999999;
        int ret_val=0;
        int skip_neigh=0;
+       int neigh_cnt=0;
        int i;
        
-       neighbors(src,pes,max_neigh);
+       neighbors(src,pes,neigh_cnt);
        
        visited_srcs[count-1]=src;
        
-       for(i=0;i<max_neigh;i++)
+       for(i=0;i<neigh_cnt;i++)
        {
                if(pes[i]==dest)
                        return count;
        }
-       for(i=0;i<max_neigh;i++)
+       for(i=0;i<neigh_cnt;i++)
        {
                for(int j=0;j<count;j++)
                        if(visited_srcs[j]==pes[i])
@@ -64,9 +65,11 @@ int LBTopology::rec_hop_count(int src,int dest,int max_neigh,int count,int *visi
                        }
                if(!skip_neigh)
                {
-                       ret_val=rec_hop_count(pes[i],dest,max_neigh,count+1,visited_srcs);
-                       if(ret_val < min_hop_cnt)
-                               min_hop_cnt = ret_val;
+                       if(min_hop_cnt > count+1){
+                               ret_val=rec_hop_count(pes[i],dest,max_neigh,count+1,visited_srcs,min_hop_cnt);
+                               if(ret_val < min_hop_cnt)
+                                       min_hop_cnt = ret_val;
+                       }
                }
                else
                        skip_neigh=0;
@@ -411,6 +414,7 @@ int LBTopo_torus3d::goodcoor(int x, int y, int z)
 
 void LBTopo_torus3d::neighbors(int mype, int* _n, int &nb)
 {
+
   int x = mype/(width*width);
   int k = mype%(width*width);
   int y = k/width;
@@ -450,6 +454,43 @@ void LBTopo_torus3d::neighbors(int mype, int* _n, int &nb)
   }
 }
 
+/*
+// Works only for perfect cube number of processor topologies
+int LBTopo_torus3d::get_hop_count(int src,int dest){
+       
+       int x_src = src/(width*width);
+  int k_src = src%(width*width);
+  int y_src = k_src/width;
+  int z_src = k_src%width;
+
+       int x_dest = dest/(width*width);
+  int k_dest = dest%(width*width);
+  int y_dest = k_dest/width;
+  int z_dest = k_dest%width;
+
+       int xdist=0,ydist=0,zdist=0;
+       
+       //CkPrintf("just a chk........\n");
+       xdist = x_dest-x_src;
+       if(xdist<0) xdist=-xdist;
+       if((width-xdist) < xdist)
+               xdist = width-xdist;
+
+       ydist = y_dest-y_src;
+       if(ydist<0) ydist=-ydist;
+       if((width-ydist) < ydist)
+               ydist = width-ydist;
+
+       zdist = z_dest-z_src;
+       if(zdist<0) zdist=-zdist;
+       if((width-zdist) < zdist)
+               zdist = width-zdist;
+
+       return (xdist+ydist+zdist);
+
+}
+*/
+
 //  TORUS ND 
 //  added by zshao1
 
index daeb2b07ecf7d803e3565b5b161000c36f81836c..b194a6e49268b0772b2f7ca3adb800660c7a2d1b 100644 (file)
@@ -34,7 +34,7 @@ public:
   virtual bool coordinate_difference(const int* my_coordinates, const int* target_coordinates, int* difference) { return false;}
   virtual bool coordinate_difference(int my_processor_id, int target_processor_id, int* difference) { return false; }
   virtual int get_hop_count(int src,int dest);
-  virtual int rec_hop_count(int src,int dest,int max_neigh,int count,int *visited_srcs);
+  virtual int rec_hop_count(int src,int dest,int max_neigh,int count,int *visited_srcs,int min_hop_cnt);
   virtual double per_hop_delay(int last_hop);
   virtual void get_pairwise_hop_count(double **dist);
 };