include/twod/nicol_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/nicol_2d.hpp>
#include <util/rect_list.hpp>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <util/tools.hpp>
#include <oned/nicol_plus.hpp>
#include <oned/nicol_plus_interval.hpp>

//Not algorithm pluggable, neither row or column fix selection provided. Need to implement after making sure the algorithm works correctly. For now, rows are fixed first.
template <typename T, typename Pr, bool DEBUG>
T twod::RectNicol<T,Pr,DEBUG>::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
    procX = P;

  int procY = procCount / procX;

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

template <typename T, typename Pr, bool DEBUG >
T twod::RectNicol<T,Pr,DEBUG>::nicol_2d_internal(int procX, int procY, const Pr& prefixSumArray, util::RectList<T,Pr> &parts)

{
  using namespace util;
  int *x_cuts;
  int *y_cuts;
  T max_load = -1;
  T min_max_load = -2;

  //if we are given too many processors on one dimension, we must waste them.
  //otherwise there will be an infinite loop down the code
  if (procX >= prefixSumArray.prefixsizeX())
    procX = prefixSumArray.prefixsizeX()-1;
  if (procY >= prefixSumArray.prefixsizeY())
    procY = prefixSumArray.prefixsizeY()-1;
  

//   x_cuts = (int*)malloc(sizeof(int)*(procX - 1));
//   y_cuts = (int*)malloc(sizeof(int)*(procY - 1));
  x_cuts = new int[procX - 1];
  y_cuts = new int[procY - 1];


  //  Aggreg2Dto1D<T,Pr,true> *lineSetX =(Aggreg2Dto1D<T,Pr,true>*) malloc(sizeof(Aggreg2Dto1D<T,Pr,true>) * procX);
  //  Aggreg2Dto1D<T,Pr,false> *lineSetY = (Aggreg2Dto1D<T,Pr,false>*)malloc(sizeof(Aggreg2Dto1D<T,Pr,false>) * procY);
  //partition X dimension first (rows), fix it and then partition column-wise(Y)
  Aggreg2Dto1D<T, Pr, true> ps1dx(prefixSumArray, 1, prefixSumArray.prefixsizeX() - 1, 1, prefixSumArray.prefixsizeY() -1);
  //Inital row partition. Fix x dimension first
  min_max_load = oned::Nicol_plus_interval<T,Aggreg2Dto1D<T, Pr, true> >::nicol_plus(procX, ps1dx, prefixSumArray.prefixsizeX(), x_cuts, -1);

  while(true)
    {
      //Prepare a new 1d array set (AggregMax2Dto1D) using fixed rows. It will be used to parition column-wise. The output set will be a row fixed set
      AggregMax2Dto1D<T,Pr,false> xMax (prefixSumArray, procX, x_cuts);

      //Do the column (y) partition
      max_load = fix_y_dimension(xMax, prefixSumArray.prefixsizeY(), procY, y_cuts);
      if (DEBUG)
        {
          std::cerr<<"previous bottleneck : "<<min_max_load<<std::endl;
          std::cerr<<"new bottleneck : "<<max_load<<std::endl;
          RectList<T,Pr> rl (prefixSumArray);
          convertToRectList(prefixSumArray.prefixsizeX(), prefixSumArray.prefixsizeY(), x_cuts, y_cuts, procX, procY, rl);
          std::cerr<<"computed bottleneck : "<<rl.get_maximum_load()<<std::endl;
          std::cerr<<rl<<std::endl;
          
          assert (rl.valid_part());
          assert (max_load == rl.get_maximum_load());
        }

      assert (max_load <= min_max_load); //according to nicol94 lemma 3
      //check if there is an improvement or not
      if(max_load == min_max_load)
        break;
      min_max_load = max_load;

      //prepare again for (x) dimension
      AggregMax2Dto1D<T,Pr,true> yMax (prefixSumArray, procY, y_cuts);
      //do the partition
      max_load = fix_x_dimension(yMax, prefixSumArray.prefixsizeX(), procX, x_cuts);

      if (DEBUG)
        {
          std::cerr<<"previous bottleneck : "<<min_max_load<<std::endl;
          std::cerr<<"new bottleneck : "<<max_load<<std::endl;
          RectList<T,Pr> rl (prefixSumArray);
          convertToRectList(prefixSumArray.prefixsizeX(), prefixSumArray.prefixsizeY(), x_cuts, y_cuts, procX, procY, rl);
          std::cerr<<"computed bottleneck : "<<rl.get_maximum_load()<<std::endl;
        }

      assert (max_load <= min_max_load); //according to nicol94 lemma 3
      if(max_load == min_max_load)
        break;
      min_max_load = max_load;


    }
  //create the rectangle list
  convertToRectList(prefixSumArray.prefixsizeX(), prefixSumArray.prefixsizeY(), x_cuts, y_cuts, procX, procY, parts);
  delete[] x_cuts;
  delete[] y_cuts;
  return max_load;

}

template <typename T, typename Pr, bool DEBUG >
T twod::RectNicol<T,Pr,DEBUG>::fix_x_dimension(util::AggregMax2Dto1D<T,Pr,true>& array, int length, int procX, int *x_cuts)
{
  using namespace util;
  if (DEBUG) std::cerr<<"fixing x dimension using "<<procX<<" processors" <<std::endl;

  if (DEBUG)
    {
      std::cerr<<"cuts before are : ";
      for (int i=0; i< procX; i++)
        std::cerr<<x_cuts[i]<<'\t';
      std::cerr<<std::endl;
    }

  T ret =  oned::Nicol_plus_interval<T,AggregMax2Dto1D<T,Pr,true> >::nicol_plus(procX, array, length, x_cuts, -1);

  if (DEBUG)
    {
      std::cerr<<"cuts after are : ";
      for (int i=0; i< procX-1; i++)
        std::cerr<<x_cuts[i]<<'\t';
      std::cerr<<std::endl;
    }

  return ret;
}

template <typename T, typename Pr, bool DEBUG >
T twod::RectNicol<T,Pr,DEBUG>::fix_y_dimension(util::AggregMax2Dto1D<T,Pr,false>& array, int length, int procY, int *y_cuts)
{
  using namespace util;
  if (DEBUG) std::cerr<<"fixing y dimension using "<<procY<<" processors"<<std::endl;

  if (DEBUG)
    {
      std::cerr<<"cuts before are : ";
      for (int i=0; i< procY; i++)
        std::cerr<<y_cuts[i]<<'\t';
      std::cerr<<std::endl;
    }

  T ret =  oned::Nicol_plus_interval<T,AggregMax2Dto1D<T,Pr,false> >::nicol_plus(procY, array, length, y_cuts, -1);

  if (DEBUG)
    {
      std::cerr<<"cuts after are : ";
      for (int i=0; i< procY-1; i++)
        std::cerr<<y_cuts[i]<<'\t';
      std::cerr<<std::endl;
    }


  return ret;
}

template <typename T, typename Pr, bool DEBUG >
void twod::RectNicol<T,Pr,DEBUG>::convertToRectList(int lengthX, int lengthY, int *x_cuts, int *y_cuts, int procX, int procY, util::RectList<T,Pr> &parts)
{
  using namespace util;
  //convert xcuts ycuts to rectList
  rectangle r;
  int i, j;
  int lastx = 1;
  int lasty = 1;
  for(i = 0; i < procX-1; i++){
    r.x_top_l = lastx;
    r.x_bot_r = x_cuts[i];
    for(j = 0; j < procY-1; j++){
        r.y_top_l = lasty;
        r.y_bot_r = y_cuts[j];
        parts.add_rect(r);
        lasty = y_cuts[j] + 1;
    }
    r.y_top_l = lasty;
    r.y_bot_r = lengthY - 1;
    parts.add_rect(r);
    lasty = 1;
    lastx = x_cuts[i] + 1;
  }
  r.x_top_l = lastx;
  r.x_bot_r = lengthX - 1;
  for(j = 0; j < procY-1; j++){
        r.y_top_l = lasty;
        r.y_bot_r = y_cuts[j];
        parts.add_rect(r);
        lasty = y_cuts[j] + 1;
    }
  r.y_top_l = lasty;
  r.y_bot_r = lengthY - 1;
  parts.add_rect(r);
}