include/util/comm_cost_2d_impl.hpp Source File

Go to the documentation of this file.
00001 
00002 // This file is part of SPart, Spatially Located Workload Partitioner.
00003 
00004 // Copyright (C) 2011, The Ohio State University
00005 // SPart developed by Erdeniz O. Bas, Erik Saule and Umit V. Catalyurek 
00006 
00007 // For questions, comments, suggestions, bugs please send e-mail to: 
00008 // Umit V. Catalyurek   catalyurek.1@osu.edu
00009 
00010 // SPart is free software; you can redistribute it and/or modify it under
00011 // the terms of the GNU General Public License as published by the Free
00012 // Software Foundation; either version 2 or (at your option) any later
00013 // version.
00014 
00015 // SPart is distributed in the hope that it will be useful, but WITHOUT
00016 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
00017 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
00018 // for more details.
00019 
00020 // You should have received a copy of the GNU General Public License
00021 // along with SPart; if not, write to the Free Software Foundation, Inc.,
00022 // 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
00023 
00024 // As a special exception, if other files instantiate templates or use
00025 // macros or inline functions from this file, or you compile this file
00026 // and link it with other works to produce a work based on this file,
00027 // this file does not by itself cause the resulting work to be covered by
00028 // the GNU General Public License. However the source code for this file
00029 // must still be made available in accordance with section (3) of the GNU
00030 // General Public License.
00031 
00032 // This exception does not invalidate any other reasons why a work based
00033 // on this file might be covered by the GNU General Public License.
00034 
00035 // The full text of the GPL license version 2 is available in "gpl.txt".
00036 
00037 #include "comm_cost_2d.hpp"
00038 
00039 //for debugging purpose only!
00040 template <typename T, typename Pr>
00041 bool util::Comm_cost_2d<T,Pr>::check_neigh(rectangle r1, rectangle r2)
00042 {
00043   int i;
00044   //check r1's left
00045   if(r1.y_top_l!=1)
00046     if(r1.y_top_l-1 == r2.y_bot_r)
00047       for(i=r1.x_top_l; i<=r1.x_bot_r;i++)
00048         if((i<=r2.x_bot_r) && (i>=r2.x_top_l))
00049            return true; 
00050         
00051   //check r1's right
00052   if(r1.y_bot_r+1 == r2.y_top_l)
00053     for(i=r1.x_top_l; i<=r1.x_bot_r;i++)
00054       if((i<=r2.x_bot_r) && (i>=r2.x_top_l))
00055         return true;
00056            
00057   //check r1's top
00058   if(r1.x_top_l!=1)
00059     if(r1.x_top_l-1 == r2.x_bot_r)
00060       for(i=r1.y_top_l; i<=r1.y_bot_r;i++)
00061         if((i<=r2.y_bot_r) && (i>=r2.y_top_l))
00062           return true; 
00063   //check r1's bottom
00064   if(r1.x_bot_r+1 == r2.x_top_l)
00065     for(i=r1.y_top_l; i<=r1.y_bot_r;i++)
00066       if((i<=r2.y_bot_r) && (i>=r2.y_top_l))
00067         return true;
00068   return false;
00069 }
00070 
00071 template <typename T, typename Pr>
00072 bool util::Comm_cost_2d<T,Pr>::is_neighbor(rectangle r1, rectangle r2)
00073 {
00074   if(
00075      (((r1.x_top_l == r2.x_bot_r + 1) ||
00076        (r1.x_bot_r + 1 == r2.x_top_l)) && y_bounded(r1,r2)) ||
00077      (((r1.y_top_l == r2.y_bot_r + 1) ||
00078        (r1.y_bot_r + 1 == r2.y_top_l)) && x_bounded(r1,r2))
00079      )
00080     return true;
00081   else
00082     return false;
00083 }
00084 template <typename T, typename Pr>
00085 bool util::Comm_cost_2d<T,Pr>::x_bounded(rectangle r1, rectangle r2)
00086 {
00087   if((r1.x_top_l >= r2.x_top_l) && (r1.x_top_l <= r2.x_bot_r))
00088     return true;
00089   else if((r1.x_bot_r >= r2.x_top_l) && (r1.x_bot_r <= r2.x_bot_r))
00090     return true;
00091   else if((r2.x_top_l >= r1.x_top_l) && (r2.x_top_l <= r1.x_bot_r))
00092     return true;
00093   else if((r2.x_bot_r >= r1.x_top_l) && (r2.x_bot_r <= r1.x_bot_r))
00094     return true;
00095   else
00096     return false;
00097 }
00098 template <typename T, typename Pr>
00099 bool util::Comm_cost_2d<T,Pr>::y_bounded(rectangle r1, rectangle r2)
00100 {
00101   if((r1.y_top_l >= r2.y_top_l) && (r1.y_top_l <= r2.y_bot_r))
00102     return true;
00103   else if((r1.y_bot_r >= r2.y_top_l) && (r1.y_bot_r <= r2.y_bot_r))
00104     return true;
00105   else if((r2.y_top_l >= r1.y_top_l) && (r2.y_top_l <= r1.y_bot_r))
00106     return true;
00107   else if((r2.y_bot_r >= r1.y_top_l) && (r2.y_bot_r <= r1.y_bot_r))
00108     return true;
00109   else
00110     return false;
00111 }
00112 template <typename T, typename Pr>
00113 double util::Comm_cost_2d<T,Pr>::avg_neighbor(RectList<T, Pr>& rl, int procCount)
00114 {
00115   
00116   typename util::RectList<T,Pr>::container::const_iterator list_iter1;
00117   typename util::RectList<T,Pr>::container::const_iterator list_iter2;
00118   int total_neighbor=0;
00119   for (list_iter1 = rl.rectangles.begin(); list_iter1 != rl.rectangles.end(); list_iter1++)
00120     {
00121       const rectangle& r1 = *list_iter1;
00122           for (list_iter2 = rl.rectangles.begin(); list_iter2 != rl.rectangles.end(); list_iter2++)
00123             {
00124               const rectangle& r2 = *list_iter2;
00125               assert(is_neighbor(r1,r2) == check_neigh(r1,r2));
00126               if (list_iter2 == list_iter1)
00127                 continue;
00128               if(is_neighbor(r1,r2))
00129                 total_neighbor++;
00130             }
00131     }
00132   return ((double)total_neighbor)/procCount;
00133 }
00134 template <typename T, typename Pr>
00135 int util::Comm_cost_2d<T,Pr>::max_neighbor(RectList<T, Pr>& rl)
00136 {
00137   typename util::RectList<T,Pr>::container::const_iterator list_iter1;
00138   typename util::RectList<T,Pr>::container::const_iterator list_iter2;
00139   int maximum = 0;
00140   for (list_iter1 = rl.rectangles.begin(); list_iter1 != rl.rectangles.end(); list_iter1++)
00141     {
00142       int neighbor=0;
00143       const rectangle& r1 = *list_iter1;
00144           for (list_iter2 = rl.rectangles.begin(); list_iter2 != rl.rectangles.end(); list_iter2++)
00145             {
00146               const rectangle& r2 = *list_iter2;
00147               assert(is_neighbor(r1,r2) == check_neigh(r1,r2));
00148               if (list_iter2 == list_iter1)
00149                 continue;
00150               if(is_neighbor(r1,r2))
00151                 neighbor++;
00152             }
00153           maximum = std::max(maximum,neighbor);
00154     }
00155   return maximum;
00156 }
00157 
00158 
00159 
00160 
00161 template <typename T, typename Pr>
00162 int util::Comm_cost_2d<T,Pr>::tot_border(RectList<T, Pr>& rl, Pr& prefixSum)
00163 {
00164   
00165   typename util::RectList<T,Pr>::container::const_iterator list_iter1;
00166   typename util::RectList<T,Pr>::container::const_iterator list_iter2;
00167   int total_length = 0;
00168   for (list_iter1 = rl.rectangles.begin(); list_iter1 != rl.rectangles.end(); list_iter1++)
00169     {
00170       const rectangle& r1 = *list_iter1;
00171       int lnx=r1.x_bot_r - r1.x_top_l+1;
00172       if(r1.y_top_l != 1)
00173         total_length += lnx;
00174       if(r1.y_bot_r != (prefixSum.prefixsizeY() - 1))
00175         total_length += lnx; 
00176       int lny=r1.y_bot_r - r1.y_top_l+1;
00177       if(r1.x_top_l != 1)
00178         total_length += lny;
00179       if(r1.x_bot_r != (prefixSum.prefixsizeX() - 1))
00180         total_length += lny; 
00181     }
00182   return total_length;
00183 }
00184 
00185 template <typename T, typename Pr>
00186 int util::Comm_cost_2d<T,Pr>::max_border(RectList<T, Pr>& rl, Pr& prefixSum)
00187 {
00188   typename util::RectList<T,Pr>::container::const_iterator list_iter1;
00189   typename util::RectList<T,Pr>::container::const_iterator list_iter2;
00190   int max_length = 0;
00191   for (list_iter1 = rl.rectangles.begin(); list_iter1 != rl.rectangles.end(); list_iter1++)
00192     {
00193       int total_length = 0;
00194       const rectangle& r1 = *list_iter1;
00195       int lnx=r1.x_bot_r - r1.x_top_l+1;
00196       if(r1.y_top_l != 1)
00197         total_length += lnx;
00198       if(r1.y_bot_r != (prefixSum.prefixsizeY() - 1))
00199         total_length += lnx; 
00200       int lny=r1.y_bot_r - r1.y_top_l+1;
00201       if(r1.x_top_l != 1)
00202         total_length += lny;
00203       if(r1.x_bot_r != (prefixSum.prefixsizeX() - 1))
00204         total_length += lny;
00205       if(total_length > max_length)
00206         max_length = total_length;
00207     }
00208   return max_length;
00209 
00210 }