include/twod/jagged_dp_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.hpp>
#include <twod/m_way_jag_2d.hpp>

template<typename T, typename Pr>
T twod::JagMOptHor<T,Pr>::part(int procCount, const Pr& prefixSumArray, util::RectList<T,Pr> &parts)
{
  return jagged_dp_internal ( procCount, prefixSumArray, parts);
}



template<typename T, typename Pr>
T twod::JagMOptHor<T,Pr>::jagged_dp_internal(int procCount, const Pr& prefixSumArray, util::RectList<T,Pr> & parts)
{
  using namespace oned;
  using namespace util;
  struct DP
  {
    const Pr& psa;
    util::Compact2D<T> dp_array;
    util::Compact3D<T> algo_1d_lazy;
    util::Compact2D<T> max_lazy;

    int nbproc;

    int nbfill;

    T best;
    int nb_ub_1d_cut_useful;
    int nb_ub_2d_cut_useful;

    DP(int procCount, const Pr& prefixSumArray)
      :psa(prefixSumArray),
       dp_array(prefixSumArray.prefixsizeX(), procCount+1),
       algo_1d_lazy(prefixSumArray.prefixsizeX(),prefixSumArray.prefixsizeX(),procCount+1),
       max_lazy(prefixSumArray.prefixsizeX(),prefixSumArray.prefixsizeX()),
       nbproc(procCount),
       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<procCount+1; j++)
          dp_array[i][j] = -1;


      for (int i=0; i<prefixSumArray.prefixsizeX(); i++)
        for (int j=0; j<prefixSumArray.prefixsizeX(); j++)
          for (int k=0; k<procCount+1; k++)
            {
              algo_1d_lazy(i,j,k)=-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];
    }

    void algo_1d_fill(int x, int n, int m, util::RectList<T,Pr> & parts)
    {
      assert (m>0);

      int *cuts = new int[m];

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

      util::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;
    }

    T algo_1d(int x, int n, int m)
    {
      if (algo_1d_lazy(x,n,m) < 0 )
        {

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

      return algo_1d_lazy(x,n,m);
    }

    T algo_1d_lb(int x, int n, int m)
    {
      if (algo_1d_lazy(x,n,m) < 0 )
        {
          util::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,m);
    }

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


      if (dp_array[n][m] < 0)
        {
          util::Aggreg2Dto1D<T, Pr, false> ps1dx_row(psa, 1, n, 1, psa.prefixsizeY() - 1); 
          return ps1dx_row[psa.prefixsizeY()-1]/m;
        }
      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)
        {
          util::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];
    }

    T algo_1d_ub(int x, int n, int m)
    {
      assert (m != 0);
      if (algo_1d_lazy(x,n,m) < 0 )
        {
          util::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,m);
    }


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

      T minimum = infinite();

      for (int x=1; x<= n; x++)//the subarray will be [1:x-1] and the stripe is [x:n]
        {

          for (int p=0; p<=m-1; p++) //There will be p proc on the subarray and thus m-p on the stripe
            {

              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,m-p) >= minimum)
                {
                 
                  break; //no need to compute
                }

              T e = 0;
              T a = 0;
              

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

              if (a > best)
                {

                  break; //next time there will be even less processors
                }

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


              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);
              
              assert (maximum >= algo_2d_lb(x-1,p));
              assert (maximum >= algo_1d_lb(x,n,m-p));
              assert (maximum >= e);
              assert (maximum >= a);

              if (minimum > maximum)
                {
                  minimum = maximum;
                }

              if (n == psa.prefixsizeX()-1 && m == nbproc)
                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<=nbproc; p++)
            fill(i,p);
        }
    }

    void backtrack(int n, int m, util::RectList<T,Pr> & parts)
    {

      if (n == 0) return;
      if (m == 0) { return;}

      T minimum = eval(n,m);                                    

      for (int x=1; x <= n; x++)
        {
          for (int p=0; p<=m-1; p++) // p is the number of processor in the remaining part
            {
              if (algo_2d_lb(x-1,p) > minimum)
                {
                  continue;
                }
              if (algo_1d_lb(x,n,m-p) > minimum)
                {
                  continue;
                }

              T a = algo_1d(x,n,m-p);
              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,m-p,parts);

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

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

    T opt()
    {
      T ret = eval(psa.prefixsizeX()-1, nbproc); 
      return ret;
    }
    
    void setBest(T b)
    {
      best = b;
    }
  };

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

    twod::JagMHeurHor<T, Pr > foo;
    data.setBest( foo.part(procCount, prefixSumArray, trash) );
  }


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

  return opt;
}


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