include/twod/jagged_dp_pq_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/jagged_dp_pq.hpp>

template<typename T, typename Pr>
T twod::JagPQOptHor<T,Pr>::part(int procCount, const Pr& prefixSumArray, util::RectList<T,Pr> &parts)
{
  using namespace util;
  int p;

  if (P == 0)
    p = intfactor(procCount);
  else
    p = P;

  int q = procCount / p;

  return jagged_dp_pq_internal ( p, q, prefixSumArray, parts);
}

template<typename T, typename Pr>
T twod::JagPQOptHor<T,Pr>::jagged_dp_pq_internal(int P, int Q, const Pr& prefixSumArray, util::RectList<T,Pr> & parts)
{
  using namespace oned;
  using namespace util;
  struct DP
  {
    const Pr& psa;
    Compact2D<T> dp_array;
    Compact2D<T> algo_1d_lazy;
    Compact2D<T> max_lazy;

    int nbprocX;
    int nbprocY;

    int nbfill;

    T best;
    int nb_ub_1d_cut_useful;
    int nb_ub_2d_cut_useful;

    DP(int P, int Q, const Pr& prefixSumArray)
      :psa(prefixSumArray),
       dp_array(prefixSumArray.prefixsizeX(), P+1),
       algo_1d_lazy(prefixSumArray.prefixsizeX(),prefixSumArray.prefixsizeX()),
       max_lazy(prefixSumArray.prefixsizeX(),prefixSumArray.prefixsizeX()),
       nbprocX(P),
       nbprocY(Q),
       nbfill(0),
       best(infinite()),
       nb_ub_1d_cut_useful(0),
       nb_ub_2d_cut_useful(0)
    {
      for (int i=0; i<prefixSumArray.prefixsizeX(); i++)
        for (int j=0; j<nbprocX+1; j++)
          dp_array[i][j] = -1;


      for (int i=0; i<prefixSumArray.prefixsizeX(); i++)
        for (int j=0; j<prefixSumArray.prefixsizeX(); j++)
            {
              algo_1d_lazy[i][j]=-1;
              max_lazy[i][j]=-1;
            }
              
    }

    T infinite() const
    {
      return psa[psa.prefixsizeX()-1][psa.prefixsizeY()-1]+1;
    }

    T eval(int n, int m)
    {
      assert (n >= 0);
      assert (m >= 0);
    
      assert (dp_array[n][m] <= infinite());

      if (dp_array[n][m] < 0 )
        fill(n,m);

      return dp_array[n][m];
    }


    //return the optimal of [x:n] jagged on nbprocY processors and fill the partitions
    void algo_1d_fill(int x, int n, RectList<T,Pr> & parts)
    {
      const int m = nbprocY;

      assert (m>0);

      int *cuts = new int[m];

      Aggreg2Dto1D<T, Pr, false> ps1dx_row(psa, x, n, 1, psa.prefixsizeY() - 1); 
      NicolPlus<T, Aggreg2Dto1D<T, Pr, false> >::nicol_plus (m, ps1dx_row, psa.prefixsizeY(), cuts, max_lazy[x][n]);

      rectangle r;

      r.x_top_l = x;
      r.x_bot_r = n;


      //if we are in the last row, then limit bottom rectangle height to prefixSumArray height
      r.y_top_l = 1;

      
      //Add partitions to the list
      for(int j = 0; j < m; j++)
        {
          r.y_bot_r = (j == m - 1) ? psa.prefixsizeY() - 1 :cuts[j];
          if(r.valid_bound(psa))
            {
              
              parts.add_rect(r);

              r.y_top_l = r.y_bot_r + 1;
            }
          else
            {
              break;
            }
        }
      


      delete[] cuts;
    }


    //return the optimal of [x:n] jagged on nbprocY processors
    T algo_1d(int x, int n)
    {
      const int m = nbprocY;

      if (algo_1d_lazy[x][n] < 0 )
        {
          Aggreg2Dto1D<T, Pr, false> ps1dx_row(psa, x, n, 1, psa.prefixsizeY() - 1); 
          algo_1d_lazy[x][n] = NicolPlus<T, Aggreg2Dto1D<T, Pr, false> >::nicol_plus (m, ps1dx_row, psa.prefixsizeY(), NULL, max_lazy[x][n]);
          assert (ps1dx_row[psa.prefixsizeY()-1 ] >= 0);
          assert (ps1dx_row[psa.prefixsizeY()-1 ] <= infinite());
          assert (algo_1d_lazy[x][n] >= 0);
          assert (algo_1d_lazy[x][n] <= infinite());
          
        }

      return algo_1d_lazy[x][n];
    }

    //return a lower bound on the best partitioning of [x:n] jagged on
    //nbprocY processors
    T algo_1d_lb(int x, int n)
    {
      const int m = nbprocY;
      if (algo_1d_lazy[x][n] < 0 )
        {
          Aggreg2Dto1D<T, Pr, false> ps1dx_row(psa, x, n, 1, psa.prefixsizeY() - 1); 
          return ps1dx_row[psa.prefixsizeY()-1]/m;
        }
      else
        return algo_1d_lazy[x][n];
    }

    //return a lower bound on the best partitioning of [1:n] on m 
    //columns of nbprocY processors
    T algo_2d_lb(int n, int m)
    {
      if (n == 0) return 0;
      if (m == 0) return infinite();


      if (dp_array[n][m] < 0)
        {
          Aggreg2Dto1D<T, Pr, false> ps1dx_row(psa, 1, n, 1, psa.prefixsizeY() - 1); 
          return ps1dx_row[psa.prefixsizeY()-1]/(m*nbprocY);
        }
      else
        return dp_array[n][m];
    }

    T algo_2d_ub(int n, int m)
    {
      if (n == 0) return 0;
      if (m == 0) return infinite();


      if (dp_array[n][m] < 0)
        {
          Aggreg2Dto1D<T, Pr, false> ps1dx_row(psa, 1, n, 1, psa.prefixsizeY() - 1); 
          return ps1dx_row[psa.prefixsizeY()-1];
        }
      else
        return dp_array[n][m];
    }


    //return an upper bound on the best partitioning of [x:n] jagged on
    // nbprocY processors
    T algo_1d_ub(int x, int n)
    {
      const int m = nbprocY;
      assert (m != 0);
      //if (m == 0) return infinite();

      if (algo_1d_lazy[x][n] < 0 )
        {
          //return ps1dx_row[psa.prefixsizeY()-1];

          Aggreg2Dto1D<T, Pr, false> ps1dx_row(psa, x, n, 1, psa.prefixsizeY() - 1); 
              
          if (max_lazy[x][n] < 0)
            {
              
              max_lazy[x][n] = 0;
              for (int i=1;i<psa.prefixsizeY();i++)
                max_lazy[x][n] = std::max(max_lazy[x][n], ps1dx_row[i]-ps1dx_row[i-1]);

            }
          
          return max_lazy[x][n] + ps1dx_row[psa.prefixsizeY()-1]/m;
        }
      else
        return algo_1d_lazy[x][n];
    }


    //the array is [1:n]
    //\f$f(n,m) = \min_{1 \leq x \leq n} \max (f (x-1, m-1), algo_1d ([x:n], Q))\f$
    T compute(int n, int m)
    {
      if (n == 0) return 0;
      if (m == 0) return infinite();
      if (m == 1) return algo_1d (1,n);


      T minimum = infinite();

      for (int x=1; x<= n; x++)
        {

          int p = m-1;
            {
              if (algo_2d_lb(x-1,p) > best)//the solution we will get won't be interesting
                {
                  continue;
                }

              if (algo_2d_lb(x-1,p) >= minimum)// not enough processor allocated to the first part to get good result anyway
                {
                  continue;
                }

              if (algo_1d_lb(x,n) >= minimum)
                {
                  //no need to compute
                  continue;
                }

              T e = 0;
              T a = 0;
              

              if (algo_1d_ub(x,n) <= e)
                {//seems pretty useless in the timings
                  a = e;
                }
              else
                a = algo_1d(x,n);

              if (a > best)
                {
                  //next time there will be even less processors
                  continue;
                }

              if (a >= minimum)
                {
                  //next time there will be even less processors
                  continue;
                }


              if (algo_2d_ub(x-1,p) < a)
                {
                  e = a;
                }
              else
                {
                  e = eval(x-1,p);
                }

              if (e > best) // the solution won't beat the best we have
                {                
                  continue;
                }
              if (e >= minimum)// not enough processor allocated to the first part to get good result anyway
                {
                  continue;
                }



              T maximum = std::max (e, a);
              minimum = std::min ( minimum, maximum );

              if (n == psa.prefixsizeX()-1 && m == nbprocX)
                if (minimum < best)
                  best = minimum;
            }
        }

      return minimum;
    }

    void fill (int n, int m)
    {
      dp_array[n][m] = compute(n,m);
    }

    void fill()
    {
      for (int i=0; i<=psa.prefixsizeX()-1; i++)
        {
          for (int p=0; p<=nbprocX; p++)
            fill(i,p);
        }
    }

    void backtrack(int n, int m, RectList<T,Pr> & parts)
    {
      if (m == 0) return;
      if (n == 0) return;

      T minimum = eval(n,m);

      for (int x=1; x<= n; x++)
        {
          //      for (int p=0; p<=m-1; p++)
          int p = m-1;
            {
              if (algo_2d_lb(x-1,p) > minimum)
                continue;
              if (algo_1d_lb(x,n) > minimum)
                continue;

              T a = algo_1d(x,n);
              if (a > minimum)
                break;

              T e = eval(x-1,p);
              if (e > minimum)
                continue;



              T maximum = std::max (e, a);

              if (maximum == minimum)
                {
                  algo_1d_fill(x,n,parts);

                  backtrack(x-1,p,parts);
                  return;
                }
            }
        }
    }

    void backtrack(RectList<T,Pr> & parts)
    {
      backtrack(psa.prefixsizeX()-1,nbprocX, parts);
    }

    T opt()
    {
      T ret = eval(psa.prefixsizeX()-1, nbprocX); 
      return ret;
    }
    
    //best should be a valid jagged partitioning
    void setBest(T b)
    {
      best = b;
    }
  };



  DP data (P, Q, prefixSumArray);
  //data.fill();




  {
    util::RectList<T,Pr> trash(prefixSumArray);

    twod::JagPQHeurHor<T, Pr > foo;
    foo.setP(P);
    data.setBest( foo.part(P*Q, prefixSumArray, trash) );
  }


  

  T opt = data.opt();
  data.backtrack(parts);

  return opt;
}


template <typename T, typename Pr>
T twod::JagPQOptVer<T, Pr>::part(int procCount, const Pr& prefixSumArray, util::RectList<T,Pr> &parts)
{
  JagPQOptHor <T, util::TransposePrefix2D<T, Pr > > 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::JagPQOptBest<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); 
  JagPQOptVer<T,Pr> foov;
  JagPQOptHor<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;
    }
}