include/oned/direct_cut_impl.hpp Source File

Go to the documentation of this file.
00001 
00002 // This file is part of SPart, Spatially Located Workload Partitioner.
00003 
00004 // Copyright (C) 2011, The Ohio State University
00005 // SPart developed by Erdeniz O. Bas, Erik Saule and Umit V. Catalyurek 
00006 
00007 // For questions, comments, suggestions, bugs please send e-mail to: 
00008 // Umit V. Catalyurek   catalyurek.1@osu.edu
00009 
00010 // SPart is free software; you can redistribute it and/or modify it under
00011 // the terms of the GNU General Public License as published by the Free
00012 // Software Foundation; either version 2 or (at your option) any later
00013 // version.
00014 
00015 // SPart is distributed in the hope that it will be useful, but WITHOUT
00016 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
00017 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
00018 // for more details.
00019 
00020 // You should have received a copy of the GNU General Public License
00021 // along with SPart; if not, write to the Free Software Foundation, Inc.,
00022 // 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
00023 
00024 // As a special exception, if other files instantiate templates or use
00025 // macros or inline functions from this file, or you compile this file
00026 // and link it with other works to produce a work based on this file,
00027 // this file does not by itself cause the resulting work to be covered by
00028 // the GNU General Public License. However the source code for this file
00029 // must still be made available in accordance with section (3) of the GNU
00030 // General Public License.
00031 
00032 // This exception does not invalidate any other reasons why a work based
00033 // on this file might be covered by the GNU General Public License.
00034 
00035 // The full text of the GPL license version 2 is available in "gpl.txt".
00036 
00037 #include <oned/direct_cut.hpp>
00038 
00039 template <typename T, typename Pr>
00040 T oned::DirectCut<T,Pr>::direct_cut(int procCount, const Pr& prefixSumArray,
00041                               int length, int *cutIndexes, T )
00042 {
00043   T v = direct_cut_internal(procCount, prefixSumArray, length, cutIndexes);
00044   return v;
00045 }
00046 
00047 
00048 template <typename T, typename Pr>
00049 T oned::DirectCut<T,Pr>::direct_cut_internal(int procCount, const Pr& prefixSumArray,
00050                                        int length, int *cutIndexes)
00051 {
00052   using namespace util;
00053   T avg = prefixSumArray[length - 1] / procCount;
00054   int inc = length / procCount, p, lastcut = 0;
00055   int currentcut;
00056   int step = inc;
00057   T bottleneck = -1, val;
00058   for(p = 0; p < procCount - 1; p++)
00059     {
00060       val = (p + 1) * avg;
00061       while(prefixSumArray[step] <= val)
00062         {
00063           assert (inc >0);
00064           step+=inc;
00065           if(step > length-1)
00066             step = length-1;
00067         }
00068       assert (step>=0);
00069       assert (step<length);
00070       currentcut =  binarySearchLeft(prefixSumArray, step - inc, step, val);
00071 
00072       if (cutIndexes != NULL)
00073         cutIndexes[p] = currentcut;
00074 
00075       assert((prefixSumArray[currentcut] >=val) || (currentcut  == length - 1));
00076 
00077       assert(currentcut >= step - inc);
00078       assert(currentcut <= step);
00079       assert(currentcut >= 0);
00080       assert(lastcut <= currentcut);
00081       assert(-1 != currentcut);
00082 
00083       if((prefixSumArray[currentcut] - prefixSumArray[lastcut]) > bottleneck)
00084          bottleneck = prefixSumArray[currentcut] - prefixSumArray[lastcut] ;
00085       lastcut = currentcut;
00086     }
00087       if(prefixSumArray[length - 1] - prefixSumArray[lastcut] > bottleneck)
00088         return prefixSumArray[length - 1] - prefixSumArray[lastcut];
00089   else
00090     return bottleneck;
00091 }