include/oned/nicol_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
 * 
 * 02/16/2010
 * nicol.c
 *
 * this is the implementation of the nicols algorithm as it is provided in Pinar Aykanat 2004 in figure 5b
 *
 */

#include <oned/nicol.hpp>

//Bopt is assumed to be less than upperbound. a negative value
//for upperbound will deactivate it.
template <typename T, typename Pr>
T  oned::Nicol<T,Pr>::nicol_internal(const Pr& w, int n, int p, T upperbound)
{
  using namespace util;
  T LB = w[n - 1] / p, UB = w[n - 1];
  int *i_array = new int[p];
  T *Bb_array = new T[p];
  int b, ilow, ihigh, imid, i;
  T B, Bopt;
  
  if (upperbound >= 0)
    UB=upperbound;

  i_array[0] = 1;
  for(b = 1; b <= p - 1; b++)
    {
      ilow = i_array[b - 1];
      ihigh = n - 1;
      while(ilow < ihigh)
        {
          imid = (ilow + ihigh) / 2;
          B = w[imid] - w[i_array[b - 1] - 1];
          if(LB <= B && B < UB)
            if(ParametricSearch<T,Pr>::probe(B, p - 1, w, n))
              {
                ihigh = imid;
                UB = B;
              }
            else
              {
                ilow = imid + 1;
                LB = B;
              }
          else if(B >= UB)
            ihigh = imid;
          else
            ilow = imid + 1;
        }
      i_array[b] = ihigh;
      Bb_array[b-1] = w[i_array[b]] - w[i_array[b-1]-1];
    }
  assert(i_array[p-1]-1 > -1);
  Bb_array[p-1] = w[n-1] - w[i_array[p-1]-1];
  Bopt = Bb_array[0];
  for(i = 1; i < p; i++)
    {
      if(Bopt > Bb_array[i])
        {
          Bopt = Bb_array[i];
        }
    }
  delete[] i_array;
  delete[] Bb_array;
  return Bopt;
}

template <typename T, typename Pr>
T oned::Nicol<T,Pr>::nicol(int procCount, const Pr& prefixSumArray,
                     int length, int *cutIndexes, T max)
{
  using namespace util;
  T ub = (prefixSumArray[length - 1] + max * (procCount - 1)) / procCount;
  if (max < 0)
    ub = -1;

  T b = nicol_internal (prefixSumArray, length, procCount, ub);
  if (cutIndexes != NULL)
    ParametricSearch<T,Pr>::probeCut (b, procCount-1, prefixSumArray,length,cutIndexes);
  return b;
}