include/oned/nicol_minus_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_minus.c
 *
 * This function is the implementation of the nicols algorithm as it is presented in PinarAykanat 2004 in JPDC in figure 5a
 *
 */

#include <oned/nicol_minus.hpp>

template <typename T, typename Pr>
T oned::NicolMinus<T,Pr>::nicol_minus_internal(const Pr& w, int n, int p)
{
  using namespace util;
  int *i_array = new int[p];
  T* Bb_array = new T[p];
  int b, ilow, ihigh, imid, i;
  T B, Bopt;
  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(ParametricSearch<T,Pr>::probe(B, p - 1, w, n))
            ihigh = imid;
          else
            ilow = imid + 1;
        }
      i_array[b] = ihigh;
      Bb_array[b-1] = w[i_array[b]] - w[i_array[b-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::NicolMinus<T,Pr>::nicol_minus (int procCount, const Pr& prefixSumArray,
                                 int length, int *cutIndexes, T )
{
  using namespace util;
  T b = nicol_minus_internal (prefixSumArray, length, procCount);
  if (cutIndexes != NULL)
    ParametricSearch<T,Pr>::probeCut (b, procCount-1, prefixSumArray,length,cutIndexes);
  return b;
}