include/twod/rec_bisect_relaxed_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 <assert.h>
00038 #include <twod/rec_bisect_relaxed.hpp>
00039 #include <oned/rec_bisect_minmax.hpp>
00040 #include <util/tools.hpp>
00041 #include <iostream>
00042 
00043 template<typename T, typename Pr, int type, bool middle>
00044 T twod::HierRelaxed<T,Pr,type,middle>::part(int procCount, const Pr& prefixSumArray, util::RectList<T,Pr> &parts)
00045  {
00046    util::rectangle r;
00047    bool orient;
00048    if(type == HOR_ALT)
00049      orient = true;
00050    else
00051      orient = false;
00052    r.x_top_l = 1;
00053    r.y_top_l = 1;
00054    r.x_bot_r = prefixSumArray.prefixsizeX() - 1;
00055    r.y_bot_r = prefixSumArray.prefixsizeY() - 1;
00056    return rec_bisect_2d_internal(procCount, prefixSumArray, parts, r, orient);
00057  }
00058 
00059 template<typename T, typename Pr,  int type, bool middle>
00060 T twod::HierRelaxed<T,Pr,type,middle>::rec_bisect_2d_internal(int procCount, const Pr& prefixSumArray, util::RectList<T,Pr> &parts, util::rectangle r, bool orient)
00061 {
00062   using namespace oned;
00063   using namespace util;
00064   //there is a cut to perform (more than one cell and one processor)
00065 
00066   bool can_vertical_cut;
00067   bool can_horizontal_cut;
00068   
00069   if (type == LOAD)
00070     {
00071       can_vertical_cut = true;
00072       can_horizontal_cut = true;
00073 
00074     }
00075   if (type == DIST)
00076     {
00077       if ((r.x_bot_r - r.x_top_l)
00078           <= (r.y_bot_r - r.y_top_l))
00079         {
00080           can_vertical_cut = true;
00081           can_horizontal_cut = false;
00082         }
00083       else
00084         {
00085           can_vertical_cut = false;
00086           can_horizontal_cut = true;
00087         }
00088     }
00089 
00090   if((type == HOR_ALT) || (type == VERT_ALT))
00091     {
00092       if (orient)
00093         {
00094           can_vertical_cut = false;
00095           can_horizontal_cut = true;
00096           //if the dimension to cut is composed of a single cell, swap the dimensions
00097           if (r.x_top_l == r.x_bot_r) 
00098             {
00099               can_horizontal_cut = false;
00100               can_vertical_cut = true;
00101             }
00102         }
00103       
00104       else
00105         {
00106           can_vertical_cut = true;
00107           can_horizontal_cut = false;
00108           //if the dimension to cut is composed of a single cell, swap the dimensions
00109           if (r.y_top_l == r.y_bot_r)
00110             {
00111               can_vertical_cut = false;
00112               can_horizontal_cut = true;
00113           
00114             }
00115 
00116         }
00117     }
00118   
00119   if (r.y_top_l == r.y_bot_r)
00120     can_vertical_cut = false;
00121   
00122   if (r.x_top_l == r.x_bot_r)
00123     can_horizontal_cut = false; 
00124   
00125 
00126   if(procCount > 1 && (can_horizontal_cut || can_vertical_cut))
00127     {
00128       double ver_max=-1, hor_max=-1;
00129       int cutIndex_ver=-1, tmp_cutIndex_ver, cutIndex_hor=-1,tmp_cutIndex_hor;
00130       rectangle subr1_ver = r, subr2_ver = r;
00131       rectangle subr1_hor = r, subr2_hor = r;
00132       int leftProc = 1;
00133       int rightProc = procCount - leftProc;
00134       int tmpleft, tmpright, left_ver=-1, right_ver=-1, left_hor=-1, right_hor=-1;
00135       
00136 
00137       //vertical estimation
00138       if (can_vertical_cut)
00139         {
00140           Aggreg2Dto1D<T, Pr, false> ps1d_ver(prefixSumArray, r.x_top_l, r.x_bot_r, r.y_top_l, r.y_bot_r);
00141           if(middle)
00142             //if middle constraint is given cut from the middle
00143             tmp_cutIndex_ver = (r.y_bot_r - r.y_top_l)/2 + r.y_top_l;
00144           else
00145             tmp_cutIndex_ver = r.y_top_l-1 + RecursiveBisectionMinMax<T, Aggreg2Dto1D<T,  Pr, false>& >::findEvenCut(ps1d_ver, 1, r.y_bot_r-r.y_top_l+1, leftProc, rightProc);
00146 
00147           cutIndex_ver = tmp_cutIndex_ver;
00148           
00149 
00150           assert (tmp_cutIndex_ver >= r.y_top_l);
00151           assert (tmp_cutIndex_ver < r.y_bot_r);
00152 
00153 
00154           double tmp_candDiff = RecursiveBisectionMinMax<T, Aggreg2Dto1D<T,  Pr, false>& >::calculateDiff(ps1d_ver, 1, r.y_bot_r-r.y_top_l+1, leftProc, rightProc, cutIndex_ver - (r.y_top_l-1));
00155           double candDiff = tmp_candDiff;
00156 
00157           for(tmpleft = leftProc + 1; tmpleft < procCount; tmpleft++)
00158             {
00159               tmpright = procCount - tmpleft;
00160               if(!middle)
00161                 tmp_cutIndex_ver = r.y_top_l-1 + RecursiveBisectionMinMax<T, Aggreg2Dto1D<T,  Pr, false>& >::findEvenCut(ps1d_ver, 1, r.y_bot_r-r.y_top_l+1, tmpleft, tmpright); 
00162               tmp_candDiff = RecursiveBisectionMinMax<T, Aggreg2Dto1D<T,  Pr, false>& >::calculateDiff(ps1d_ver, 1, r.y_bot_r - r.y_top_l+1, tmpleft, tmpright, tmp_cutIndex_ver - (r.y_top_l-1));
00163 
00164               assert (tmp_cutIndex_ver >= r.y_top_l);
00165               assert (tmp_cutIndex_ver < r.y_bot_r);
00166 
00167               if(tmp_candDiff < candDiff)
00168                 {
00169                   leftProc = tmpleft;
00170                   candDiff = tmp_candDiff;
00171                   cutIndex_ver = tmp_cutIndex_ver;
00172                 }
00173             }
00174           rightProc = procCount - leftProc;
00175           ver_max = candDiff;
00176           
00177           left_ver = leftProc;
00178           right_ver = rightProc;
00179 
00180 
00181           assert (cutIndex_ver >= 0);
00182           
00183           assert (cutIndex_ver >= r.y_top_l);
00184           assert (cutIndex_ver < r.y_bot_r);
00185 
00186           //      assert (cutIndex_ver + 1 > r.y_top_l);
00187           //      assert (cutIndex_ver + 1 <= r.y_bot_r);
00188 
00189           subr1_ver.y_bot_r = cutIndex_ver;
00190           //      subr2_ver.y_top_l = (cutIndex_ver + 1 > r.y_top_l ? r.y_top_l : cutIndex_ver + 1);
00191           subr2_ver.y_top_l = cutIndex_ver + 1;
00192         }
00193       leftProc = 1;
00194       rightProc = procCount - leftProc;
00195       //horizontal estimation
00196       if (can_horizontal_cut)
00197         {
00198           Aggreg2Dto1D<T, Pr, true> ps1d_hor(prefixSumArray, r.x_top_l, r.x_bot_r, r.y_top_l, r.y_bot_r);       
00199           if(middle)
00200             tmp_cutIndex_hor = (r.x_bot_r - r.x_top_l)/2 + r.x_top_l;
00201           else
00202             tmp_cutIndex_hor = r.x_top_l-1 + RecursiveBisectionMinMax<T, Aggreg2Dto1D<T,  Pr, true>& >::findEvenCut(ps1d_hor, 1, r.x_bot_r-r.x_top_l+1, leftProc, rightProc);
00203           cutIndex_hor = tmp_cutIndex_hor;
00204 
00205           assert (tmp_cutIndex_hor >= r.x_top_l);
00206           assert (tmp_cutIndex_hor <  r.x_bot_r);
00207 
00208 
00209           double tmp_candDiff = RecursiveBisectionMinMax<T, Aggreg2Dto1D<T,  Pr, true>& >::calculateDiff(ps1d_hor, 1, r.x_bot_r-r.x_top_l+1, leftProc, rightProc, cutIndex_hor-(r.x_top_l-1));
00210           double candDiff = tmp_candDiff;
00211           for(tmpleft = leftProc + 1; tmpleft < procCount; tmpleft++)
00212             {
00213               tmpright = procCount - tmpleft;
00214               if(!middle)
00215                 tmp_cutIndex_hor = r.x_top_l-1 + RecursiveBisectionMinMax<T, Aggreg2Dto1D<T,  Pr, true>& >::findEvenCut(ps1d_hor, 1, r.x_bot_r-r.x_top_l+1, tmpleft, tmpright);
00216               tmp_candDiff = RecursiveBisectionMinMax<T, Aggreg2Dto1D<T,  Pr, true>& >::calculateDiff(ps1d_hor, 1, r.x_bot_r-r.x_top_l+1, tmpleft, tmpright, cutIndex_hor-(r.x_top_l-1));
00217 
00218               assert (tmp_cutIndex_hor >= r.x_top_l);
00219               assert (tmp_cutIndex_hor <  r.x_bot_r);
00220 
00221 
00222                if(tmp_candDiff < candDiff)
00223                 {
00224                   leftProc = tmpleft;
00225                   candDiff = tmp_candDiff;
00226                   cutIndex_hor = tmp_cutIndex_hor;
00227                 }
00228             }
00229           rightProc = procCount - leftProc;
00230           hor_max = candDiff;
00231 
00232           left_hor = leftProc;
00233           right_hor = rightProc;
00234 
00235           assert(cutIndex_hor >= 0);
00236           
00237           assert (cutIndex_hor >= r.x_top_l);
00238           assert (cutIndex_hor <  r.x_bot_r);
00239           //      assert (cutIndex_hor + 1 >= r.x_top_l);
00240           //      assert (cutIndex_hor + 1 <= r.x_bot_r);
00241 
00242           subr1_hor.x_bot_r = cutIndex_hor;
00243           //      subr2_hor.x_top_l = (cutIndex_hor + 1 > r.x_bot_r ? r.x_bot_r : cutIndex_hor + 1);
00244           subr2_hor.x_top_l = cutIndex_hor + 1;
00245         }
00246 
00247       //decision
00248       T load1, load2;
00249       if( can_vertical_cut && ((!can_horizontal_cut ) || ver_max<hor_max))
00250         {
00251 
00252           assert (leftProc + rightProc <= procCount);
00253           //vertical cutting
00254           
00255           load1 = HierRelaxed::rec_bisect_2d_internal(left_ver, prefixSumArray, parts, subr1_ver, !orient);
00256           if(cutIndex_ver + 1 < prefixSumArray.prefixsizeY())
00257             load2 = HierRelaxed::rec_bisect_2d_internal(right_ver, prefixSumArray, parts, subr2_ver, !orient);
00258           else
00259             load2 = load1;
00260         }
00261       else
00262         {
00263           //horizontal cutting
00264           assert (can_horizontal_cut);
00265           assert (leftProc + rightProc <= procCount);
00266 
00267           load1 = HierRelaxed::rec_bisect_2d_internal(left_hor, prefixSumArray, parts, subr1_hor, !orient);
00268           if(cutIndex_hor + 1 < prefixSumArray.prefixsizeX())
00269             load2 = HierRelaxed::rec_bisect_2d_internal(right_hor, prefixSumArray, parts, subr2_hor, !orient);
00270           else
00271             load2 = load1;
00272           
00273         }
00274 
00275       return  std::max(load1,load2);
00276     }
00277   else
00278     {
00279 
00280       parts.add_rect(r);
00281       return r.get_load<T,Pr>(prefixSumArray);
00282     }
00283   
00284 }