include/util/m_probe.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".

#ifndef __M_PROBE_H__
#define __M_PROBE_H__

#include "prefix_sum_tools.hpp"
#include "multiarrays.hpp"

namespace util
{
  template <typename T, typename SubMa, typename Ma>
  class MProbe
  {
  public:
    static bool probe(T b, const Ma& arrs, int m, int **lb, int **ub, int *procs, int **cuts)
    {
      using namespace util;
      int i;
      
      //iterate 1st dimension
      for(i = 0; i < arrs.arrayCount(); i++)
        {
          if(m<0)
            return false;
          //try an array
          procs[i] = rprobe(arrs[i], arrs.getLength(i), b, m, cuts[i], lb[i], ub[i]);
          if(procs[i] == -1)
            return false;
          m-=procs[i];
        }
      assert (m>=0);
      return true;
    }
  private:
    static int rprobe(const SubMa& wpre, int length, const T& bottleneck,
                                             int numproc, int *s, int *sl, int *sh)
    {
      T bsum = bottleneck;
      int p;
      
      for(p = 0; p < numproc - 1 ; p++)
        {
          assert(sl[p] <= sh[p]);
          assert(p < numproc);
          s[p] = binarySearch(wpre, sl[p], sh[p], bsum);
          //if cutting from the rightmost, search is over
          if (p > 0)
            {
              assert (s[p]>=s[p-1]);
              assert (wpre[s[p]] - wpre[s[p-1]] <= bottleneck);
            }
          bsum = wpre[s[p]] + bottleneck;
          if(s[p] >= length - 2)
            {
              if(s[p] != length - 1)
                p++;
              break;
            }

        }
      if(bsum >= wpre[length - 1])
        return p+1;
      else
        return -1;
    }
    
  };
}

#endif