include/twod/her_jag_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 <twod/her_jag_2d.hpp>
00038 
00039 template <typename T, typename Pr, 
00040           T (*onedalgoY) (int procCount, const util::Aggreg2Dto1D<T, Pr, false>& prefixSumArray, int length, int *cutIndexes, T),
00041           T (*onedalgoX)(int procCount, const util::Aggreg2Dto1D<T, Pr, true>& prefixSumArray, int length, int *cutIndexes, T) >
00042 T twod::JagPQHeurHor<T,Pr,onedalgoY, onedalgoX>::part(int procCount, const Pr& prefixSumArray, util::RectList<T,Pr> &parts)
00043 {
00044   using namespace util;
00045   assert(procCount > 0);
00046   //calculate processor number for dimensions X and Y
00047   int procX;
00048   int procY;
00049 
00050   assert (P>=0);
00051   assert (P<=procCount);
00052 
00053   if (P>0)
00054     {
00055       procX = P;
00056     }
00057   else
00058     {
00059       procX = intfactor(procCount);
00060     }  
00061   
00062   procY=procCount/procX;
00063   
00064   return her_jag_2d_internal(procX, procY, prefixSumArray, parts);
00065 
00066 }
00067 
00068 template <typename T, typename Pr, 
00069           T (*onedalgoY) (int procCount, const util::Aggreg2Dto1D<T, Pr, false>& prefixSumArray, int length, int *cutIndexes, T),
00070           T (*onedalgoX)(int procCount, const util::Aggreg2Dto1D<T, Pr, true>& prefixSumArray, int length, int *cutIndexes, T) >
00071 T twod::JagPQHeurHor<T,Pr,onedalgoY, onedalgoX>::her_jag_2d_internal(int procX, int procY, const Pr& prefixSumArray, util::RectList<T,Pr> &parts)
00072 
00073 {
00074   using namespace util;
00075   rectangle r;
00076   int *x_cuts;
00077   int *y_cuts;
00078   int i,j;
00079   T max_load = -1;
00080   x_cuts = new int[procX - 1];
00081   y_cuts = new int[procY - 1];
00082   //partition X dimension first (rows), fix it and then partition column-wise(Y)
00083    
00084   assert(prefixSumArray.prefixsizeY() > 0);
00085   assert(prefixSumArray.prefixsizeX() > 0);
00086   Aggreg2Dto1D<T, Pr, true> ps1dx(prefixSumArray, 1, prefixSumArray.prefixsizeX() - 1, 1, prefixSumArray.prefixsizeY() -1); 
00087   onedalgoX( procX, ps1dx, prefixSumArray.prefixsizeX(), x_cuts, -1);
00088   r.x_top_l = 1;
00089   //visit every fixed row
00090   for(i = 0; i < procX; i++)
00091     {
00092       //if we are in the last row, then limit bottom rectangle height to prefixSumArray height
00093       r.y_top_l = 1;
00094       r.y_bot_r = prefixSumArray.prefixsizeY() - 1;
00095       r.x_bot_r = (i == procX - 1) ? prefixSumArray.prefixsizeX() - 1 :x_cuts[i];
00096       if (r.x_top_l <= r.x_bot_r)
00097         {
00098           Aggreg2Dto1D<T, Pr, false> ps1dx_row(prefixSumArray, r.x_top_l, r.x_bot_r, 1, prefixSumArray.prefixsizeY() - 1); 
00099           onedalgoY(procY, ps1dx_row, prefixSumArray.prefixsizeY(), y_cuts, -1);
00100           //Add partitions to the list
00101           for(j = 0; j < procY; j++)
00102             {
00103               r.y_bot_r = (j == procY - 1) ? prefixSumArray.prefixsizeY() - 1 :y_cuts[j];
00104               if(r.valid_bound(prefixSumArray))
00105                 {
00106                   
00107                   parts.add_rect(r);
00108                   if(r.get_load<T,Pr>(prefixSumArray) > max_load)
00109                     max_load = r.get_load<T,Pr>(prefixSumArray);
00110                   r.y_top_l = r.y_bot_r + 1;
00111                 }
00112               else
00113                 break;
00114             }
00115         }
00116       r.x_top_l = r.x_bot_r + 1;
00117     }
00118     
00119   
00120   delete[] x_cuts;
00121   delete[] y_cuts;
00122   assert(max_load>=0);
00123   return max_load;
00124 }
00125 
00126 
00127 template <typename T, typename Pr,
00128           T (*onedalgoY) (int procCount, const util::Aggreg2Dto1D<T, util::TransposePrefix2D<T, Pr>, false>& prefixSumArray, int length, int *cutIndexes, T),
00129           T (*onedalgoX) (int procCount, const util::Aggreg2Dto1D<T, util::TransposePrefix2D<T, Pr>, true>& prefixSumArray, int length, int *cutIndexes, T)
00130 >
00131 T twod::JagPQHeurVer<T, Pr, onedalgoY, onedalgoX>::part(int procCount, const Pr& prefixSumArray, util::RectList<T,Pr> &parts)
00132 {
00133   JagPQHeurHor<T, util::TransposePrefix2D<T, Pr >, onedalgoY, onedalgoX> foo;
00134   foo.setP(P);
00135 
00136   util::TransposePrefix2D<T, Pr> tpr (prefixSumArray);
00137 
00138   util::RectList<T, util::TransposePrefix2D<T, Pr> > intermediate (tpr);
00139   
00140   T val = foo.part(procCount,tpr,intermediate);
00141 
00142   util::TransposePrefix2D<T, Pr>::convertRectList(intermediate, parts);
00143 
00144   return val;
00145 }  
00146 
00147 
00148 template <typename T, typename Pr>
00149 T twod::JagPQHeurBest<T,Pr>::part(int procCount, const Pr& prefixSumArray, util::RectList<T,Pr> &parts)
00150 {
00151   using namespace util;
00152   RectList<T,Pr > partsv(prefixSumArray);
00153   RectList<T,Pr > partsh(prefixSumArray); 
00154   JagPQHeurVer<T,Pr> foov;
00155   JagPQHeurHor<T,Pr> fooh;
00156   T ort1 = foov.part(procCount, prefixSumArray, partsv);
00157   T ort2 = fooh.part(procCount, prefixSumArray, partsh);
00158   if(ort1 > ort2)
00159     {
00160       parts.copy_into(partsh);
00161       return ort2;
00162     }
00163   else
00164     {
00165       parts.copy_into(partsv);
00166       return ort1;
00167     }
00168 }  
00169 
00170 template <typename T, typename Pr, 
00171           T (*onedalgoY) (int procCount, const util::Aggreg2Dto1D<T, Pr, false>& prefixSumArray, int length, int *cutIndexes, T),
00172           T (*onedalgoX)(int procCount, const util::Aggreg2Dto1D<T, Pr, true>& prefixSumArray, int length, int *cutIndexes, T) >
00173 twod::JagPQHeurHor<T,Pr,onedalgoY, onedalgoX>::~JagPQHeurHor(){}
00174 
00175 template <typename T, typename Pr,
00176             T (*onedalgoY) (int procCount, const util::Aggreg2Dto1D<T, util::TransposePrefix2D<T, Pr>, false>& prefixSumArray, int length, int *cutIndexes, T),
00177             T (*onedalgoX) (int procCount, const util::Aggreg2Dto1D<T, util::TransposePrefix2D<T, Pr>, true>& prefixSumArray, int length, int *cutIndexes, T) 
00178             >
00179 twod::JagPQHeurVer<T,Pr,onedalgoY, onedalgoX>::~JagPQHeurVer(){}
00180 
00181 
00182 template <typename T, typename Pr>
00183 twod::JagPQHeurBest<T,Pr>::~JagPQHeurBest(){}
00184 
00185 template <typename T, typename Pr, 
00186           T (*onedalgoY) (int procCount, const util::Aggreg2Dto1D<T, Pr, false>& prefixSumArray, int length, int *cutIndexes, T),
00187           T (*onedalgoX)(int procCount, const util::Aggreg2Dto1D<T, Pr, true>& prefixSumArray, int length, int *cutIndexes, T) >
00188 twod::JagPQHeurHor<T,Pr,onedalgoY, onedalgoX>::JagPQHeurHor()
00189   :P(0)
00190 {}
00191 
00192   template <typename T, typename Pr,
00193             T (*onedalgoY) (int procCount, const util::Aggreg2Dto1D<T, util::TransposePrefix2D<T, Pr>, false>& prefixSumArray, int length, int *cutIndexes, T),
00194             T (*onedalgoX) (int procCount, const util::Aggreg2Dto1D<T, util::TransposePrefix2D<T, Pr>, true>& prefixSumArray, int length, int *cutIndexes, T) 
00195             >
00196 twod::JagPQHeurVer<T,Pr,onedalgoY, onedalgoX>::JagPQHeurVer():P(0){}
00197 
00198 
00199 template <typename T, typename Pr, 
00200           T (*onedalgoY) (int procCount, const util::Aggreg2Dto1D<T, Pr, false>& prefixSumArray, int length, int *cutIndexes, T),
00201           T (*onedalgoX)(int procCount, const util::Aggreg2Dto1D<T, Pr, true>& prefixSumArray, int length, int *cutIndexes, T) >
00202 void twod::JagPQHeurHor<T,Pr,onedalgoY, onedalgoX>::setP(int P)
00203 {this->P=P;}
00204 
00205 
00206   template <typename T, typename Pr,
00207             T (*onedalgoY) (int procCount, const util::Aggreg2Dto1D<T, util::TransposePrefix2D<T, Pr>, false>& prefixSumArray, int length, int *cutIndexes, T),
00208             T (*onedalgoX) (int procCount, const util::Aggreg2Dto1D<T, util::TransposePrefix2D<T, Pr>, true>& prefixSumArray, int length, int *cutIndexes, T) 
00209             >
00210 void twod::JagPQHeurVer<T,Pr,onedalgoY, onedalgoX>::setP(int P)
00211 {this->P = P;}