include/twod/m_way_jag_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 <twod/m_way_jag_2d.hpp>
#include <util/rect_list.hpp>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <util/tools.hpp>
#include <oned/direct_cut.hpp>

template <typename T, typename Pr, 
          T (*onedalgoY) (int procCount, const util::Aggreg2Dto1D<T, Pr, false>& prefixSumArray, int length, int *cutIndexes, T),
          T (*onedalgoX)(int procCount, const util::Aggreg2Dto1D<T, Pr, true>& prefixSumArray, int length, int *cutIndexes, T) >
T twod::JagMHeurHor<T,Pr,onedalgoY, onedalgoX>::part(int procCount, const Pr& prefixSumArray, util::RectList<T,Pr> &parts)
{
  using namespace util;
  assert(procCount > 0);
  //calculate processor number for dimensions X and Y
  int procX;
  if (P==0)
    procX = intfactor(procCount);
  else if (P == -1)
    {
      procX = (int)floor(sqrt(procCount*((double)prefixSumArray.prefixsizeX()-1)/(prefixSumArray.prefixsizeX()-1)));
      if (procX == 0)
        procX = 1;
    }
  else
    procX = P;
  return m_way_jag_2d_internal(procX, procCount, prefixSumArray, parts);
}

 


template <typename T, typename Pr, 
          T (*onedalgoY) (int procCount, const util::Aggreg2Dto1D<T, Pr, false>& prefixSumArray, int length, int *cutIndexes, T),
          T (*onedalgoX)(int procCount, const util::Aggreg2Dto1D<T, Pr, true>& prefixSumArray, int length, int *cutIndexes, T) >
T twod::JagMHeurHor<T,Pr,onedalgoY, onedalgoX>::m_way_jag_2d_internal(int procX, int m, const Pr& prefixSumArray, util::RectList<T,Pr> &parts)

{
  using namespace util;
  rectangle r;
  int *x_cuts;
  int *y_cuts;
  int i,j;
  T max_load = -1;
  x_cuts = new int[procX-1];
  y_cuts = new int[m-1];//wow that allocation is overkill
  //partition X dimension first (rows), fix it and then partition column-wise(Y)

  assert(prefixSumArray.prefixsizeY() > 0);
  assert(prefixSumArray.prefixsizeX() > 0);
  Aggreg2Dto1D<T, Pr, true> ps1dx(prefixSumArray, 1, prefixSumArray.prefixsizeX() - 1, 1, prefixSumArray.prefixsizeY() -1); 
  onedalgoX( procX, ps1dx, prefixSumArray.prefixsizeX(), x_cuts, -1);
 


  int allocated = 0;
  int *ln_alloc = new int[procX];
  T *row_weight = new T[procX];
  //Find out processor number for each row
  r.y_top_l = 1;
  r.y_bot_r = prefixSumArray.prefixsizeY() - 1;
  r.x_top_l = 1;
  for(i = 0; i < procX; i++)
    {      
      r.x_bot_r = (i == procX - 1) ? prefixSumArray.prefixsizeX() - 1 :x_cuts[i];

      row_weight[i] = r.get_load<T, Pr>(prefixSumArray);
      ln_alloc[i] = ((int) ceil((m - procX) *  row_weight[i] / ((double)prefixSumArray[prefixSumArray.prefixsizeX() - 1][prefixSumArray.prefixsizeY() -1])));
      //Don't exceed matrix size!
      if(ln_alloc[i] >= prefixSumArray.prefixsizeY())
        ln_alloc[i]=prefixSumArray.prefixsizeY()-1;
      allocated += ln_alloc[i];
      r.x_top_l = r.x_bot_r + 1;
          
    }


  //distrubute reminder processors

  int extra_left = m-allocated;
  
  assert (extra_left >= 0);
  while (extra_left != 0)
    {
      int max_index = 0;
      for (i=1; i<procX; i++)
        {
          if(((double)row_weight[max_index])/ln_alloc[max_index]
             < ((double)row_weight[i])/ln_alloc[i])
            max_index = i;
        }
      //Do not allocate more processor than matrix size. Throw exceeding processors away
      if(ln_alloc[max_index] < prefixSumArray.prefixsizeY()-1)
         ln_alloc[max_index]++;
      extra_left--;
    }
  assert(extra_left == 0);
  
  //visit every fixed row
  r.x_top_l = 1;

  for(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)
        {
          Aggreg2Dto1D<T, Pr, false> ps1dx_row(prefixSumArray, r.x_top_l, r.x_bot_r, 1, prefixSumArray.prefixsizeY() - 1); 

          onedalgoY(ln_alloc[i], ps1dx_row, prefixSumArray.prefixsizeY(), y_cuts, -1);
          //Add partitions to the list


          for(j = 0; j < ln_alloc[i]; j++)
            {
              r.y_bot_r = (j == ln_alloc[i] - 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;
    }

  delete[] ln_alloc;
  delete[] row_weight;



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


template <typename T, typename Pr,
          T (*onedalgoY) (int procCount, const util::Aggreg2Dto1D<T, util::TransposePrefix2D<T, Pr>, false>& prefixSumArray, int length, int *cutIndexes, T),
          T (*onedalgoX) (int procCount, const util::Aggreg2Dto1D<T, util::TransposePrefix2D<T, Pr>, true>& prefixSumArray, int length, int *cutIndexes, T)
>
T twod::JagMHeurVer<T, Pr, onedalgoY, onedalgoX>::part(int procCount, const Pr& prefixSumArray, util::RectList<T,Pr> &parts)
{
  JagMHeurHor<T, util::TransposePrefix2D<T, Pr >, onedalgoY, onedalgoX> foo;
  foo.setP(P);

  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>
T twod::JagMHeurBest<T,Pr>::part(int procCount, const Pr& prefixSumArray, util::RectList<T,Pr> &parts)
{
  using namespace util;
  RectList<T,Pr > partsv(prefixSumArray);
  RectList<T,Pr > partsh(prefixSumArray); 
  JagMHeurVer<T,Pr> foov;
  JagMHeurHor<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;
    }
}