include/twod/rec_bisect_2d_impl.hpp

Go to the documentation of this file.

// This file is part of SPart, Spatially Located Workload Partitioner.

// Copyright (C) 2011, The Ohio State University
// SPart developed by Erdeniz O. Bas, Erik Saule and Umit V. Catalyurek 

// For questions, comments, suggestions, bugs please send e-mail to: 
// Umit V. Catalyurek   catalyurek.1@osu.edu

// SPart is free software; you can redistribute it and/or modify it under
// the terms of the GNU General Public License as published by the Free
// Software Foundation; either version 2 or (at your option) any later
// version.

// SPart is distributed in the hope that it will be useful, but WITHOUT
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
// for more details.

// You should have received a copy of the GNU General Public License
// along with SPart; if not, write to the Free Software Foundation, Inc.,
// 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

// As a special exception, if other files instantiate templates or use
// macros or inline functions from this file, or you compile this file
// and link it with other works to produce a work based on this file,
// this file does not by itself cause the resulting work to be covered by
// the GNU General Public License. However the source code for this file
// must still be made available in accordance with section (3) of the GNU
// General Public License.

// This exception does not invalidate any other reasons why a work based
// on this file might be covered by the GNU General Public License.

// The full text of the GPL license version 2 is available in "gpl.txt".

#include <assert.h>
#include <twod/rec_bisect_2d.hpp>
#include <oned/rec_bisect.hpp>
#include <util/tools.hpp>

template<typename T, typename Pr, int type>
T twod::RecBisect2D<T,Pr,type>::part(int procCount, const Pr& prefixSumArray, util::RectList<T,Pr> &parts)
 {
   using namespace util;
   rectangle r;
   bool orient;
   if(type == HOR_ALT)
     orient = true;
   else
     orient = false;
   r.x_top_l = 1;
   r.y_top_l = 1;
   r.x_bot_r = prefixSumArray.prefixsizeX() - 1;
   r.y_bot_r = prefixSumArray.prefixsizeY() - 1;
   return rec_bisect_2d_internal(procCount, prefixSumArray, parts, r, orient);
 }

template<typename T, typename Pr,  int type>
T twod::RecBisect2D<T,Pr,type>::rec_bisect_2d_internal(int procCount, const Pr& prefixSumArray, util::RectList<T,Pr> &parts, util::rectangle r, bool orient)
{
  using namespace oned;
  using namespace util;
  //  std::cout<<r<<std::endl;
  if(procCount > 1)
    {
      bool can_vertical_cut;
      bool can_horizontal_cut;

      if (type == LOAD)
        {
          can_vertical_cut = true;
          can_horizontal_cut = true;
        }
      if((type == HOR_ALT) || (type == VERT_ALT))
        {
          if (orient)
            {
              can_vertical_cut = false;
              can_horizontal_cut = true;
            }
          
          else
            {
              can_vertical_cut = true;
              can_horizontal_cut = false;
            }
        }
      if (type == DIST)
        {
          if ((r.x_bot_r - r.x_top_l)
              <= (r.y_bot_r - r.y_top_l))
            {
              can_vertical_cut = true;
              can_horizontal_cut = false;
            }
          else
            {
              can_vertical_cut = false;
              can_horizontal_cut = true;
            }
        }


      double ver_max=-1, hor_max=-1;
      int cutIndex_ver=-1, cutIndex_ver1=-1,cutIndex_ver2=-1, cutIndex_hor=-1,cutIndex_hor1=-1,cutIndex_hor2=-1;
      rectangle subr1_ver = r, subr2_ver = r;
      rectangle subr1_hor = r, subr2_hor = r;
      int leftProc = (procCount >> 1);
      int rightProc = procCount - leftProc;
      //if vsvap is true then we allocate rightproc-leftproc --- for vertical cuts
      bool vswap=true;
      //if hsvap is true then we allocate rightproc-leftproc --- for horizontal cuts
      bool hswap=true;
   
      //vertical estimation
      if (can_vertical_cut)
        {
          Aggreg2Dto1D<T, Pr, false> ps1d_ver(prefixSumArray, (int)r.x_top_l, (int)r.x_bot_r, (int)r.y_top_l, (int)r.y_bot_r);
          
          cutIndex_ver1 = r.y_top_l-1 + RecursiveBisection<T, Aggreg2Dto1D<T,  Pr, false> >::findEvenCut(ps1d_ver, 1, r.y_bot_r-r.y_top_l+1, leftProc, rightProc);

          double candDiff1 = RecursiveBisection<T, Aggreg2Dto1D<T,  Pr, false> >::calculateDiff(ps1d_ver, 1, r.y_bot_r-r.y_top_l+1, leftProc, rightProc, cutIndex_ver1 - (r.y_top_l-1));


          //      std::cout<<"cut indexver1 "<<cutIndex_ver1<<" "<<candDiff1<<std::endl;

          double candDiff2;

          if (leftProc != rightProc)
            { 
              cutIndex_ver2 = r.y_top_l-1 + RecursiveBisection<T, Aggreg2Dto1D<T,  Pr, false> >::findEvenCut(ps1d_ver, 1, r.y_bot_r - r.y_top_l+1, rightProc, leftProc);
              candDiff2 = RecursiveBisection<T, Aggreg2Dto1D<T,  Pr, false> >::calculateDiff(ps1d_ver, 1, r.y_bot_r - r.y_top_l+1, rightProc, leftProc, cutIndex_ver2 - (r.y_top_l-1));
              //              std::cout<<"cut indexver2 "<<cutIndex_ver2<<" "<<candDiff2<<std::endl;
            }
          else 
            {
              cutIndex_ver2 = cutIndex_ver1;
              candDiff2 = candDiff1;
            }


          if(candDiff1 <= candDiff2)
            {
              cutIndex_ver = cutIndex_ver1;
              vswap = false;
              ver_max = candDiff1;
            }
          else
            { cutIndex_ver = cutIndex_ver2;
              vswap = true;
              ver_max = candDiff2;
            }
          assert (cutIndex_ver >= 0);
          
          assert (cutIndex_ver >= r.y_top_l);
          assert (cutIndex_ver <= r.y_bot_r);

          subr1_ver.y_bot_r = cutIndex_ver;
          subr2_ver.y_top_l = cutIndex_ver + 1;
        }

      //horizontal estimation
      if (can_horizontal_cut)
        {
          Aggreg2Dto1D<T, Pr, true> ps1d_hor(prefixSumArray, r.x_top_l, r.x_bot_r, r.y_top_l, r.y_bot_r);       

          cutIndex_hor1 = (r.x_top_l-1) + RecursiveBisection<T, Aggreg2Dto1D<T,  Pr, true> >::findEvenCut(ps1d_hor, 1, r.x_bot_r - r.x_top_l+1, leftProc, rightProc);
          
          double candDiff1 = RecursiveBisection<T, Aggreg2Dto1D<T,  Pr, true> >::calculateDiff(ps1d_hor, 1, r.x_bot_r - r.x_top_l+1, leftProc, rightProc, cutIndex_hor1 - (r.x_top_l-1));
          

          //      std::cout<<"cut indexhor1 "<<cutIndex_hor1<<" "<<candDiff1<<std::endl;

          double candDiff2;


          if (leftProc != rightProc)
            {
              cutIndex_hor2 = (r.x_top_l-1) + RecursiveBisection<T, Aggreg2Dto1D<T,  Pr, true> >::findEvenCut(ps1d_hor, 1, r.x_bot_r - r.x_top_l+1, rightProc, leftProc);
              candDiff2 = RecursiveBisection<T, Aggreg2Dto1D<T,  Pr, true> >::calculateDiff(ps1d_hor, 1, r.x_bot_r - r.x_top_l+1, rightProc, leftProc, cutIndex_hor2 - (r.x_top_l-1));
              //              std::cout<<"cut indexhor2 "<<cutIndex_hor2<<" "<<candDiff2<<std::endl;
            }
          else
            {
              cutIndex_hor2 = cutIndex_hor1;
              candDiff2 = candDiff1;
            }

          if(candDiff1 <= candDiff2)
            {
              cutIndex_hor = cutIndex_hor1;
              hswap = false;
              hor_max = candDiff1;
            }
          else
            {
              cutIndex_hor = cutIndex_hor2;
              hswap = true;
              hor_max = candDiff2;
            }

          assert(cutIndex_hor >= 0);
          
          assert (cutIndex_hor >= r.x_top_l);
          assert (cutIndex_hor <= r.x_bot_r);


          subr1_hor.x_bot_r = cutIndex_hor;
          subr2_hor.x_top_l = cutIndex_hor + 1;
        }

      //decision
      T load1, load2;
      if( can_vertical_cut && ((!can_horizontal_cut ) || ver_max<hor_max))
        {
          //vertical cutting

          load1 = RecBisect2D::rec_bisect_2d_internal((vswap?rightProc:leftProc), prefixSumArray, parts, subr1_ver, !orient);
          if(cutIndex_ver + 1 < prefixSumArray.prefixsizeY())
            load2 = RecBisect2D::rec_bisect_2d_internal((vswap?leftProc:rightProc), prefixSumArray, parts, subr2_ver, !orient);
          else
            load2 = load1;
        }
      else
        {
          //horizontal cutting

          load1 = RecBisect2D::rec_bisect_2d_internal((hswap?rightProc:leftProc), prefixSumArray, parts, subr1_hor, !orient);
          if(cutIndex_hor + 1 < prefixSumArray.prefixsizeX())
            load2 = RecBisect2D::rec_bisect_2d_internal((hswap?leftProc:rightProc), prefixSumArray, parts, subr2_hor, !orient);
          else
            load2 = load1;

        }
      if(load1 > load2)
        return load1;
      else
        return load2;
    }
  else
    {
      parts.add_rect(r);
      return r.get_load<T,Pr>(prefixSumArray);
    }
  
}