include/twod/m_way_probe_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_probe.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::JagMHeurProbeHor<T,Pr,onedalgoY,onedalgoX>::part(int procCount, const Pr& prefixSumArray, util::RectList<T,Pr> &parts)
{
  using namespace std;
  //Make an initial partition
  twod::PartBase<T, Pr >* pb = NULL;  
  T ub = (pb = new JagMHeurHor<T,Pr,onedalgoY,onedalgoX>())->part(procCount, prefixSumArray, parts);
  delete pb;

  int *firstDimCuts = new int[procCount+1];
  //Get the 1st dim cut points
  int procX=util::extractXDim<T,Pr>(parts, firstDimCuts);

  int *procs = new int[procX];//necessary to create rectList
  int **cuts = new int*[procX];//Cut points of each line
  int *lengths = new int[procX];//another unnecessary thing. Length of each row. This variable was put to MProbe if lines would be different size
  for(int i = 0; i < procX;i++)
    {
      cuts[i] = new int[procCount];//TODO: waste of memory
      lengths[i] = prefixSumArray.prefixsizeY();
      //initalize lower bound indexes to 1 and uppers to prefixsizeY()-1;

    }
  //I had to do this because the default constructor of Aggreg2Dto1D<T, Pr, false> is private
  util::Aggreg2Dto1D<T, Pr, false> **rows = new util::Aggreg2Dto1D<T, Pr, false>*[procX];
      
  //build the rows of row set
  int top = 1;

  for(int i=1;i<=procX;i++)
    {
          
      rows[i-1] = new util::Aggreg2Dto1D<T, Pr, false>(prefixSumArray, top,  firstDimCuts[i], 1, prefixSumArray.prefixsizeY()-1);

      top = firstDimCuts[i] + 1;
    }
#ifndef NDEBUG
  {
    T total=0;
    for(int i=0;i<procX;i++)
      {
        total += (*rows[i])[prefixSumArray.prefixsizeY()-1];
      }
    assert(total==prefixSumArray[prefixSumArray.prefixsizeX()-1][prefixSumArray.prefixsizeY()-1]);
  }
#endif
  util::Multiarrays<T,util::Aggreg2Dto1D<T, Pr, false> > arrs((const util::Aggreg2Dto1D<T, Pr, false>**)rows, lengths, procX);
  
  T lb = multiarraypart(procCount, arrs, ub, procs, cuts);

  //convert **cuts to parts

  parts.clear();
  top = 1;
  for(int i = 0; i< procX; i++)
    {
      int left = 1;
      for(int j = 0; j<procs[i]-1;j++)
        {

          util::rectangle r(top,firstDimCuts[i+1],left,cuts[i][j]);
          parts.add_rect(r);
          left = cuts[i][j] + 1;
        }
      util::rectangle r2(top,firstDimCuts[i+1],left,prefixSumArray.prefixsizeY()-1);
      parts.add_rect(r2);
      top = firstDimCuts[i+1] + 1;
    }
       
  //Free memory before exit
  delete [] firstDimCuts;
  delete [] lengths;
  delete [] procs;
  for(int i = 0; i < procX;i++)
    { 
      delete [] cuts[i]; 
      delete rows[i];
    }
  delete [] cuts;
  delete [] rows;
  return lb;
}


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::JagMHeurProbeHor<T,Pr,onedalgoY,onedalgoX>::multiarraypart(int procCount, const util::Multiarrays<T,util::Aggreg2Dto1D<T, Pr, false> > & arrs, T ub, int* procs, int** oricuts)
{
  const bool debug=false;

  T lb = 0;//can be refined
  int procX = arrs.arrayCount();

  int **lbar = new int*[procX];//lower bound index
  int **ubar = new int*[procX];//upper bound index
  int **cuts = new int*[procX];//cuts during the binary search. TODO: we probably don't need that array
  //  int **tmp; //for swapping operations

  for(int i = 0; i < procX;i++)
    {
      ubar[i] = new int[procCount];
      lbar[i] = new int[procCount];
      cuts[i] = new int[procCount];
      for(int j = 0; j < procCount; j++)
        {
          lbar[i][j] = 1;
          ubar[i][j] = arrs.getLength(i)-1;
        }
    }

  assert((util::MProbe<T,util::Aggreg2Dto1D<T, Pr, false>, util::Multiarrays<T,util::Aggreg2Dto1D<T, Pr, false> >  >::probe(ub, arrs, procCount, lbar, ubar, procs, cuts)) == true);

  int i=0;
  int startinterval = 1;

  while (i<procX)
    {
      if (debug)
        std::cerr<<"array : "<<i<<" startinterval: "<<startinterval<<std::endl;

      assert((util::MProbe<T,util::Aggreg2Dto1D<T, Pr, false>, util::Multiarrays<T,util::Aggreg2Dto1D<T, Pr, false> >  >::probe(ub, arrs, procCount, lbar, ubar, procs, cuts)) == true);

      
      int lowbound = startinterval;
      int highbound = arrs.getLength(i)-1;
      //decide if we are at the end of the array
      bool lastinterval;

      if (startinterval >= highbound)
        {
          lastinterval = true;
        }
      else
        {
          int middle = highbound;
          T bmid = arrs[i][middle] - arrs[i][startinterval-1];
          bool ok;
          if (bmid <= lb)
            ok = false;
          else if (bmid >= ub)
            ok = true;
          else  
            {
              ok = util::MProbe<T,util::Aggreg2Dto1D<T, Pr, false>, util::Multiarrays<T,util::Aggreg2Dto1D<T, Pr, false> >  >::probe(bmid, arrs, procCount, lbar, ubar, procs, cuts);
              if(ok)
                {
                  ub = bmid;
                }
              else
                {
                  lb = bmid;
                }
            }
          lastinterval = !ok;
        }

      
      if (lastinterval)
        {
          if (debug)
            std::cerr<<"changing interval"<<std::endl;
          startinterval = 1;
          i++;
        }
      else
        {
          while (lowbound < highbound)//find the smallest interval rooted at startinterval which is infeasible
            {
              if (debug)
                std::cerr<<"searching for end of the interval : [ "<<lowbound<<" ; "<<highbound<<" ]"<<std::endl;
              int middle = (highbound+lowbound)/2;
              
              T bmid = arrs[i][middle] - arrs[i][startinterval-1];
              bool ok;
              if (bmid <= lb)
                ok = false;
              else if (bmid >= ub)
                ok = true;
              else      
                {
                  ok = util::MProbe<T,util::Aggreg2Dto1D<T, Pr, false>, util::Multiarrays<T,util::Aggreg2Dto1D<T, Pr, false> >  >::probe(bmid, arrs, procCount, lbar, ubar, procs, cuts);
                  if(ok)
                    {
                      ub = bmid;
                    }
                  else
                    {
                      lb = bmid;
                    }
                }
              //modify highbound accordingly
              if (ok)
                {
                  highbound = middle;
                }
              else
                {
                  lowbound = middle+1;
                }
            }
          //      assert (startinterval < highbound); //there must be progress
          if (startinterval == highbound)
            highbound++;
          startinterval = highbound;
        }

    }

  //Do the partitioning again with lower bound because the above iteration can terminate with an infeasible value
#ifndef NDEBUG
  bool ret = 
#endif
    util::MProbe<T,util::Aggreg2Dto1D<T, Pr, false>, util::Multiarrays<T,util::Aggreg2Dto1D<T, Pr, false> >  >::probe(ub, arrs, procCount, lbar, ubar, procs, oricuts);
  assert(ret);

    for(int i = 0; i < procX;i++)
    { 
      delete [] lbar[i];
      delete [] ubar[i];
      delete [] cuts[i];
    }
    delete[] lbar;
    delete[] ubar;
    delete[] cuts;

  return ub;
}

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::JagMHeurProbeVer<T,Pr,onedalgoY,onedalgoX>::part(int procCount, const Pr& prefixSumArray, util::RectList<T,Pr> &parts)
{
  JagMHeurProbeHor<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>
 T twod::JagMHeurProbeBest<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); 
   JagMHeurProbeVer<T,Pr> foov;
   JagMHeurProbeHor<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,
          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)>
twod::JagMHeurProbeHor<T,Pr,onedalgoY,onedalgoX>::~JagMHeurProbeHor(){}

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)  >

twod::JagMHeurProbeVer<T,Pr,onedalgoY,onedalgoX>::~JagMHeurProbeVer(){}

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