include/twod/jag_pq_opt_interval_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 <twod/jag_pq_opt_interval.hpp>

template <typename T, typename Pr>
T twod::JagPQOptIntervalHor<T,Pr>::internal(int procX, int procY, const Pr& prefixSumArray, util::RectList<T, Pr > &parts)
{
  util::Aggreg2Dto1Dpart<T, Pr> bar (prefixSumArray, procY);
  int * x_cuts = new int [procX+1];
  int * y_cuts = new int [procY+1];

  T res = oned::Nicol_plus_interval<T, util::Aggreg2Dto1Dpart<T, Pr> >::nicol_plus (procX, bar, prefixSumArray.prefixsizeX(), x_cuts, -1);
    
    
  {
    T max_load = 0;

    util::rectangle r;

    r.x_top_l = 1;
    //visit every fixed row
    for(int i = 0; i < procX; i++)
      {
        //if we are in the last row, then limit bottom rectangle height to prefixSumArray height
        r.y_top_l = 1;
        r.y_bot_r = prefixSumArray.prefixsizeY() - 1;
        r.x_bot_r = (i == procX - 1) ? prefixSumArray.prefixsizeX() - 1 :x_cuts[i];
        if (r.x_top_l <= r.x_bot_r)
          {
            util::Aggreg2Dto1D<T, Pr, false> ps1dx_row(prefixSumArray, r.x_top_l, r.x_bot_r, 1, prefixSumArray.prefixsizeY() - 1); 
            oned::NicolPlus<T, util::Aggreg2Dto1D<T, Pr, false> >::nicol_plus (procY, ps1dx_row, prefixSumArray.prefixsizeY(), y_cuts, -1);
            //Add partitions to the list
            for(int j = 0; j < procY; j++)
              {
                r.y_bot_r = (j == procY - 1) ? prefixSumArray.prefixsizeY() - 1 :y_cuts[j];
                if(r.valid_bound(prefixSumArray))
                  {
                      
                    parts.add_rect(r);
                    if(r.get_load<T,Pr>(prefixSumArray) > max_load)
                      max_load = r.get_load<T,Pr>(prefixSumArray);
                    r.y_top_l = r.y_bot_r + 1;
                  }
                else
                  break;
              }
          }
        r.x_top_l = r.x_bot_r + 1;
      }

    assert (res == max_load);
  }
  delete [] x_cuts;
  delete [] y_cuts;
  return res;
}

template <typename T, typename Pr>
twod::JagPQOptIntervalHor<T,Pr>::~JagPQOptIntervalHor(){}

template <typename T, typename Pr>
twod::JagPQOptIntervalHor<T,Pr>::JagPQOptIntervalHor():P(0){}

template <typename T, typename Pr>
void twod::JagPQOptIntervalHor<T,Pr>::setP(int P){this->P = P;}

template <typename T, typename Pr>
T twod::JagPQOptIntervalHor<T,Pr>::part (int procCount, const Pr& prefixSumArray, util::RectList<T, Pr > &parts)
{
      int procX;
      if (P == 0)
        procX = (int)sqrt(procCount);      
      else
        procX = P; 

      int procY = procCount/procX;

      return internal (procX, procY, prefixSumArray, parts);
}

template <typename T, typename Pr>
twod::JagPQOptIntervalVer<T,Pr>::JagPQOptIntervalVer():P(0){}

template <typename T, typename Pr>
void twod::JagPQOptIntervalVer<T,Pr>::setP(int P){this->P = P;}

template <typename T, typename Pr>
T twod::JagPQOptIntervalVer<T,Pr>::part(int procCount, const Pr& prefixSumArray, util::RectList<T,Pr> &parts)
{
  JagPQOptIntervalHor <T, util::TransposePrefix2D<T, Pr > > foo;
      
  util::TransposePrefix2D<T, Pr> tpr (prefixSumArray);
      
  util::RectList<T, util::TransposePrefix2D<T, Pr> > intermediate (tpr);
      
  T val = foo.part(procCount,tpr,intermediate);
      
  util::TransposePrefix2D<T, Pr>::convertRectList(intermediate, parts);
      
  return val;
}


template <typename T, typename Pr>
twod::JagPQOptIntervalVer<T,Pr>::~JagPQOptIntervalVer(){}

template <typename T, typename Pr>
T twod::JagPQOptIntervalBest<T,Pr>::part(int procCount, const Pr& prefixSumArray, util::RectList<T,Pr> &parts)
{
  util::RectList<T,Pr > partsv(prefixSumArray);
  util::RectList<T,Pr > partsh(prefixSumArray); 

  JagPQOptIntervalVer<T,Pr> foov;
  JagPQOptIntervalHor<T,Pr> fooh;

  T ort1 = foov.part(procCount, prefixSumArray, partsv);
  T ort2 = fooh.part(procCount, prefixSumArray, partsh);
  if(ort1 > ort2)
    {
      parts.copy_into(partsh);
      return ort2;
    }
  else
    {
      parts.copy_into(partsv);
      return ort1;
    }
}

template <typename T, typename Pr>
twod::JagPQOptIntervalBest<T,Pr>::~JagPQOptIntervalBest(){}