include/oned/nicol_plus_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".

/*
 * (C) Ohio State University Biomedical Informatics - HPC Lab. http://www.bmi.osu.edu/hpc
 * 
 * 03/05/2010
 * nicol_plus.c
 *
 * this is the implementation of the nicols algorithm as it is provided in Pinar Aykanat 2004 in figure 10
 *
 */

#include <oned/nicol_plus.hpp>

template <typename T, typename Pr, bool DEBUG>
T oned::NicolPlus<T,Pr,DEBUG>::nicol_plus_internal(const Pr& wpre, int length,
                                             int numproc, T wmax, int *sl, int *sh)
{
  using namespace util;
  int ilast = 1, b;
  int ilow, ihigh, imid;
  T bottleneck, Bopt;
  T lb = wpre[length - 1] / numproc;
  T ub;
  if (wmax < 0)
    ub = wpre[length - 1];
  else
    ub = (wpre[length - 1] + wmax * (numproc - 1)) / numproc;
  int *s = new int[numproc];
  int *oris = s;

  //  T *Bb_array = new T[numproc];
  Bopt = ub;
  for(b=0; b < numproc - 1; b++)
    {

      ilow = (sl[b]<ilast?ilast-1:sl[b]);
      ihigh=length-1;
      //ihigh = sh[b]; //originaly in Pinar 04

      if (debug) std::cerr<<"b = " << b << ", ilow = " << ilow << ",ihigh = " << ihigh << std::endl;

      assert (ilow <= ihigh);

      while(ilow < ihigh)
        {
          imid = (ilow + ihigh) / 2;
          bottleneck = wpre[imid] - wpre[ilast - 1];

          assert (bottleneck >=0);
          if (debug) std::cerr<<"lb = " << lb << ", bottleneck = " << bottleneck <<  ", ub = "<< std::endl;
          if((lb <= bottleneck) && (bottleneck < ub))
            {
              if(ParametricSearch<T,Pr>::rprobe(wpre, length, bottleneck, numproc, s, sl, sh))
                {
                  int *tmp;
                  if (debug) std::cerr<<"rprobe ("<<bottleneck<<") is true"<<std::endl;
                  if (DEBUG)
                    assert ((ParametricSearch<T,Pr>::probe)(bottleneck, numproc-1, wpre, length));

                  tmp=s;
                  s=sh;
                  sh=tmp;
                  ub = bottleneck;
                  ihigh = imid;
                }
              else
                {
                  int *tmp;
                  if (debug) std::cerr<<"rprobe ("<<bottleneck<<") is false"<<std::endl;
                  if (DEBUG)
                    assert (!(ParametricSearch<T,Pr>::probe)(bottleneck, numproc-1, wpre, length));

                  tmp=s;
                  s=sl;
                  sl=tmp;
                  lb = bottleneck;
                  ilow = imid + 1;
                }
            }
          else if(bottleneck >= ub)
            {
              if (DEBUG)
                assert ((ParametricSearch<T,Pr>::probe)(bottleneck, numproc-1, wpre, length));
              ihigh = imid;
            }
          else
            {
              if (DEBUG)
                assert (! (ParametricSearch<T,Pr>::probe)(bottleneck, numproc-1, wpre, length));

              ilow = imid + 1;
            }
        }
      assert (ilow == ihigh);
      assert(b < numproc);

      Bopt = std::min(Bopt, wpre[ihigh] - wpre[ilast - 1]); //if b is the bottleneck, it executes [ilast-1:high]
      //      if (debug) std::cerr<<"ihigh = "<<ihigh<<", Bb_array["<<b<<"] = "<<Bb_array[b]<<std::endl;
      //assert ((ParametricSearch<T,Pr>::probe)(Bb_array[b], numproc-1, wpre, length) == 1);
      
      ilast = ihigh;
    }
  Bopt = std::min(wpre[length-1] - wpre[ilast - 1], Bopt);

  //computing the bottleneck value
//     Bopt = Bb_array[0];
//   for(p = 1; p < numproc; p++)
//     {
//       assert (Bopt >= 0);
//       if(Bopt > Bb_array[p])
//      {
//        Bopt = Bb_array[p];
//      }
//     }

  
//   delete[] Bb_array;
  delete[] oris;

  //return ub;
  return Bopt;
}


template <typename T, typename Pr, bool DEBUG>
T oned::NicolPlus<T,Pr, DEBUG>::nicol_plus(int procCount, const Pr & prefixSumArray,
                                     int length, int *cutIndexes, T max)
{
  using namespace util;
  int i;
  int *sl =  new int[procCount];
  int *sh =  new int[procCount];
  T b;
  for(i = 0; i < procCount; i++)
    {
      sl[i] = 1;
      sh[i] = length - 1;
    }

  b = nicol_plus_internal (prefixSumArray, length, procCount, max, sl, sh);
  if (cutIndexes != NULL)
    ParametricSearch<T,Pr>::probeCut (b, procCount-1, prefixSumArray,length, cutIndexes);
  delete[] sl;
  delete[] sh;
  return b;
}