include/twod/hybrid_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/hybrid.hpp"

template<typename T, typename Pr>
void  twod::Hybrid<T, Pr>::setLevel1(twod::PartBase<T,Pr> * l1)
{
  algoLevel1 = std::auto_ptr<twod::PartBase<T,Pr> > (l1);
}

template<typename T, typename Pr>
void twod::Hybrid<T, Pr>::setProcLevel1(int s1)
{
  this->s1=s1;
}

template<typename T, typename Pr>
void twod::Hybrid<T, Pr>::setLevel2(twod::PartBase<T, sPr  > * l2)
{
  algoLevel2 = std::auto_ptr<twod::PartBase<T, sPr > > (l2);
}

template<typename T, typename Pr>
void twod::Hybrid<T, Pr>::setLevel2Slow(twod::PartBase<T, sPr  > * l2)
{
  algoLevel2Slow = std::auto_ptr<twod::PartBase<T, sPr > > (l2);
}

template<typename T, typename Pr>
T twod::Hybrid<T, Pr>::part (int procCount, const Pr & prefixSumArray, util::RectList< T, Pr > & parts)
{
  util::RectList<T, Pr > l1(prefixSumArray);

  if (s1 >=0)
    phase1(procCount, prefixSumArray, l1);
  else
    probephase1(procCount, prefixSumArray, l1);

  phase2(procCount, prefixSumArray, parts, l1);

  return parts.get_maximum_load();
}


template<typename T, typename Pr>
void twod::Hybrid<T, Pr>::probephase1(int procCount,const Pr & prefixSumArray, util::RectList<T, Pr > & l1)
{
  int first_level = (int)(floor(sqrt(procCount)));
  first_level = better_guess(first_level, procCount);
  
  double expectedload = ((double)prefixSumArray[prefixSumArray.prefixsizeX()-1][prefixSumArray.prefixsizeY()-1]+1); //worse than no partition

  //try all first_level more than sqrt(m) and that are synchronized with the waves
  while (first_level <= procCount / 2)
    {
      assert (first_level>0);
      assert (first_level<procCount);
      
      util::RectList<T, Pr > temp(prefixSumArray);
      
      //build the a partition for phase 1
      algoLevel1->part (first_level, prefixSumArray, temp);
          
      assert (temp.valid_part());

      //compute the expected load 
      std::vector<int> alloc;
      util::distribute_processors(prefixSumArray, temp, alloc, procCount);

      double max_local_expected = 0.;
      int i=0;
      for(typename util::RectList<T,Pr>::container::const_iterator list_iter1 = temp.rectangles.begin();
          list_iter1 != temp.rectangles.end();
          list_iter1++, i++)
        {
          const util::rectangle &r =  *list_iter1;
          
          assert (alloc[i] > 0);
          
          double local_expected = (double)r.get_load<T,Pr>(prefixSumArray)/(double)alloc[i];
          
          assert (local_expected > 0);
          
          if (local_expected > max_local_expected)
            max_local_expected = local_expected;
        }


      //swap if better
      if (expectedload > max_local_expected)
        {
          expectedload = max_local_expected;
          l1.clear();
          l1.copy_into(temp);
        }

      //loop
      first_level = better_guess(first_level+1, procCount);
    }
}

template<typename T, typename Pr>
int twod::Hybrid<T, Pr>::better_guess(int p, int m)
{
  int pprime = p;
  assert (p>=0);
  while ((int)ceil((double)(m-pprime)/(double)pprime) == (int)ceil((double)(m-p)/(double)p))
    pprime++;

  assert (pprime>=p);
  return pprime;
}

template<typename T, typename Pr>
void twod::Hybrid<T, Pr>::phase1(int procCount,const Pr & prefixSumArray,
            util::RectList<T, Pr > & l1)
{
  int first_level;

  //Compute the right value for first_level
  {
    int log = (int)log2(procCount);

    if (s1 == 0)
      {

        int c = (int)ceil(sqrt(pow(2,log/2)));
        int f = (int)floor(sqrt(pow(2,log/2)));
            
        c=c*c;
        f=f*f;
            
        if (c >= procCount)
          first_level = f;
        else
          first_level = c;

        first_level = (int)sqrt(procCount);

        //          first_level = better_guess(first_level, procCount);
      }
    else
      first_level = s1;

  }

  assert (first_level>0);
  assert (first_level<procCount);
        

  //build the actual partition of phase 1
  algoLevel1->part (first_level, prefixSumArray, l1);

  assert (l1.valid_part());

}

template<typename T, typename Pr>
void twod::Hybrid<T, Pr>::phase2(int procCount,const Pr & prefixSumArray,
            util::RectList< T, Pr > & parts, const util::RectList<T, Pr > & l1)
{
  std::vector<int> alloc;
  util::distribute_processors(prefixSumArray, l1, alloc, procCount);

  std::vector< util::RectList< T, Pr >* > temp; //stores the solution inside each part generated by phase1

  std::vector< T> local_bottleneck;      
  std::vector< bool > exec_fast;


  //Compute solution in each block of phase1 using the fast phase2 algorithm
  unsigned int i=0;
  for(typename util::RectList<T,Pr>::container::const_iterator list_iter1 = l1.rectangles.begin();
      list_iter1 != l1.rectangles.end();
      list_iter1++)
    {
      const util::rectangle &r =  *list_iter1;
      sPr spsa (prefixSumArray, r);

      util::RectList<T, sPr > l2(spsa);

      algoLevel2->part(alloc[i], spsa, l2);
       
          
      util::RectList<T, Pr>* l1l = new util::RectList<T, Pr>(prefixSumArray);

      for(typename util::RectList<T,Pr>::container::iterator list_iter2 = l2.rectangles.begin();
          list_iter2 != l2.rectangles.end();
          list_iter2++)
        {
          const util::rectangle &r2 =  *list_iter2;
          l1l->add_rect(spsa.inOriginalSpace(r2));
        }

      temp.push_back(l1l);
      local_bottleneck.push_back(l2.get_maximum_load());
      exec_fast.push_back(false);

      assert (l2.valid_part());
      i++;
    }

  //trying to improve the most loaded part with a slower algorithm
  if (algoLevel2Slow.get() != NULL)
    {
      bool cont = true;
      while (cont)
        {
          int max_index = 0;
          for (i=0; i<local_bottleneck.size(); i++)
            {
              if (local_bottleneck[i] > local_bottleneck[max_index])
                max_index = i;
            }

          if (exec_fast[max_index])
            {
              cont = false;
            }
          else
            {
              exec_fast[max_index] = true;

              const util::rectangle &r = l1.rectangles[max_index];

              sPr spsa (prefixSumArray, r);

              util::RectList<T, sPr > l2(spsa);
                  
              algoLevel2Slow->part(alloc[max_index], spsa, l2);
                  
              //if the slow algorithm improved:
              if (l2.get_maximum_load() < local_bottleneck[max_index])
                {
                  //replace the local partition
                  local_bottleneck[max_index] = l2.get_maximum_load();
                      
                  temp[max_index]->clear();
                  for(typename util::RectList<T,Pr>::container::iterator list_iter2 = l2.rectangles.begin();
                      list_iter2 != l2.rectangles.end();
                      list_iter2++)
                    {
                      const util::rectangle &r2 =  *list_iter2;
                          
                      temp[max_index]->add_rect(spsa.inOriginalSpace(r2));
                    }
                }

            }         
        }
    }

  //copying the local partition to the master rectangle list
  {
    for (unsigned int j=0; j<temp.size(); j++)
      {
        parts.add_into(*temp[j]);
        delete temp[j];
      }
  }
}

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