include/util/proportional.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 __PROPORTIONAL__
#define __PROPORTIONAL__


namespace util
{
  template <typename T, typename Pr>
  void distribute_processors(const Pr& psa, const util::RectList<T,Pr> & v, std::vector<int> & alloc, int m);
  template <typename T, typename Pr>
  void distribute_processors(const Pr& psa, const util::RectList<T,Pr> & v, std::vector<int> & alloc, int m)
  {
    bool debug = true;

    assert (alloc.empty());
    assert (m > 0);

    int nbrect = v.rectangles.size();

    assert (nbrect > 0);

    if (debug)
      {
        std::cerr<<"distributing "<<m<<" processors on "<<nbrect<<" rectangles"<<std::endl;
      }


    alloc.reserve(nbrect);
    std::vector<T> load;
    load.reserve(nbrect);

    int allocated = 0;

    typename util::RectList<T, Pr>::container::const_iterator it = v.rectangles.begin();

    for (int i=0; i<nbrect; i++)
      {
        const util::rectangle &r = *it;
        load[i] = r.get_load<T,Pr> (psa);

        alloc[i] = ((int) ceil((m - nbrect) * load[i]
                               /((double)psa[psa.prefixsizeX() - 1][psa.prefixsizeY() -1])));

        allocated += alloc[i];

        if (debug)
          std::cerr<<alloc[i]<<" processors for "<<i<<"="<<*it<<". "
                   <<"Expected bottleneck for that part :"<<((double)load[i])/alloc[i]
                   <<std::endl;

        it++;
        

      }

    assert (allocated <= m);

    if (debug)
      {
        std::cerr<<allocated<<" processors already allocated. "<<m-allocated<<" to come"<<std::endl;
      }

    while (allocated != m)
      {
        assert (allocated < m);
        int max_index = 0;

        for (int i=1; i<nbrect; i++)
          {
            if (load[i] / (double)alloc[i] > load[max_index] / (double)alloc[max_index])
              max_index = i;
                                 
          }

        alloc[max_index]++;

        if (debug)
          std::cerr<<"revising allocation of "<<max_index<<". now "<<alloc[max_index]<<" processors. "
                   <<"Expected bottleneck for that part: "<<((double)load[max_index])/alloc[max_index]<<std::endl;

        allocated ++;
      }

    assert (allocated == m);
    if (debug)
      {
        int max_index = 0;
        
        for (int i=1; i<nbrect; i++)
          {
            if (load[i] / (double)alloc[i] > load[max_index] / (double)alloc[max_index])
              max_index = i;
            
          }
        double exp_bot = (load[max_index] / (double)alloc[max_index]);
        double perfect_balance = ((double)(psa[psa.prefixsizeX()-1][psa.prefixsizeY()-1])/m);
        std::cerr<<"Allocation complete! "
                 <<"Expected bottleneck : "<<exp_bot<<". "
                 <<"Expected load imbalance : "<<(exp_bot/perfect_balance)-1
                 <<std::endl;

      }
  }
}
#endif