1 /* 2 Copyright (c) 2005-2021 Intel Corporation 3 4 Licensed under the Apache License, Version 2.0 (the "License"); 5 you may not use this file except in compliance with the License. 6 You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10 Unless required by applicable law or agreed to in writing, software 11 distributed under the License is distributed on an "AS IS" BASIS, 12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 See the License for the specific language governing permissions and 14 limitations under the License. 15 */ 16 17 /* Bin-packing algorithm that attempts to use minimal number of bins B of 18 size desired_bin_capacity to contain elements_num items of varying sizes. */ 19 20 #include <cmath> 21 22 #include <string> 23 #include <iostream> 24 #include <tuple> 25 #include <vector> 26 #include <atomic> 27 #include <algorithm> 28 29 #include "oneapi/tbb/tick_count.h" 30 #include "oneapi/tbb/flow_graph.h" 31 #include "oneapi/tbb/global_control.h" 32 33 #include "common/utility/utility.hpp" 34 #include "common/utility/get_default_num_threads.hpp" 35 36 typedef std::size_t size_type; // to represent non-zero indices, capacities, etc. 37 typedef std::size_t value_type; // the type of items we are attempting to pack into bins 38 typedef std::vector<value_type> bin; // we use a simple vector to represent a bin 39 // Our bin packers will be function nodes in the graph that take value_type items and 40 // return a dummy value. They will also implicitly send packed bins to the bin_buffer 41 // node, and unused items back to the value_pool node: 42 typedef oneapi::tbb::flow:: 43 multifunction_node<value_type, std::tuple<value_type, bin>, oneapi::tbb::flow::rejecting> 44 bin_packer; 45 // Items are placed into a pool that all bin packers grab from, represent by a queue_node: 46 typedef oneapi::tbb::flow::queue_node<value_type> value_pool; 47 // Packed bins are placed in this buffer waiting to be serially printed and/or accounted for: 48 typedef oneapi::tbb::flow::buffer_node<bin> bin_buffer; 49 // Packed bins are taken from the_bin_buffer and processed by the_writer: 50 typedef oneapi::tbb::flow:: 51 function_node<bin, oneapi::tbb::flow::continue_msg, oneapi::tbb::flow::rejecting> 52 bin_writer; 53 // Items are injected into the graph when this node sends them to the_value_pool: 54 typedef oneapi::tbb::flow::input_node<value_type> value_source; 55 56 // User-specified globals with default values 57 size_type desired_bin_capacity = 42; 58 size_type elements_num = 1000; // number of elements to generate 59 bool verbose = false; // prints bin details and other diagnostics to screen 60 bool silent = false; // suppress all output except for time 61 int num_bin_packers = -1; // number of concurrent bin packers in operation; default is #threads; 62 // larger values can result in more bins at less than full capacity 63 size_type optimality = 64 1; // 1 (default) is highest the algorithm can obtain; larger numbers run faster 65 66 // Calculated globals 67 size_type bins_num_min; // lower bound on the optimal number of bins 68 size_type bins_num; // the answer, i.e. number of bins used by the algorithm 69 std::vector<size_type> input_array; // stores randomly generated input values 70 value_type item_sum; // sum of all randomly generated input values 71 std::atomic<value_type> packed_sum; // sum of all values currently packed into all bins 72 std::atomic<size_type> packed_items; // number of values currently packed into all bins 73 std::atomic<size_type> active_bins; // number of active bin_packers 74 std::vector<bin_packer*> bins; // the array of bin packers 75 76 // This class is the Body type for bin_packer 77 class bin_filler { 78 typedef bin_packer::output_ports_type ports_type; 79 bin my_bin; // the current bin that this bin_filler is packing 80 size_type 81 my_used; // capacity of bin used by current contents (not to be confused with my_bin.size()) 82 size_type relax, 83 relax_val; // relaxation counter for determining when to settle for a non-full bin 84 bin_packer* my_bin_packer; // ptr to the bin packer that this body object is associated with 85 size_type bin_index; // index of the encapsulating bin packer in the global bins array 86 value_type looking_for; // the minimum size of item this bin_packer will accept 87 value_pool* the_value_pool; // the queue of incoming values 88 bool done; // flag to indicate that this binpacker has been deactivated 89 public: 90 bin_filler(std::size_t bidx, value_pool* _q) 91 : my_used(0), 92 relax(0), 93 relax_val(0), 94 my_bin_packer(nullptr), 95 bin_index(bidx), 96 looking_for(desired_bin_capacity), 97 the_value_pool(_q), 98 done(false) {} 99 void operator()(const value_type& item, ports_type& p) { 100 if (!my_bin_packer) 101 my_bin_packer = bins[bin_index]; 102 if (done) 103 // this bin_packer is done packing items; put item back to pool 104 std::get<0>(p).try_put(item); 105 else if ( 106 item > 107 desired_bin_capacity) { // signal that packed_sum has reached item_sum at some point 108 size_type remaining = active_bins--; 109 if (remaining == 1 && 110 packed_sum == item_sum) { // this is the last bin and it has seen everything 111 // this bin_packer may not have seen everything, so stay active 112 if (my_used > 0) 113 std::get<1>(p).try_put(my_bin); 114 my_bin.clear(); 115 my_used = 0; 116 looking_for = desired_bin_capacity; 117 ++active_bins; 118 } 119 else if (remaining == 1) { // this is the last bin, but there are remaining items 120 std::get<0>(p).try_put(desired_bin_capacity + 1); // send out signal 121 ++active_bins; 122 } 123 else if (remaining > 1) { // this is not the last bin; deactivate 124 // this bin is ill-utilized; throw back items and deactivate 125 if (my_used < desired_bin_capacity / (1 + optimality * .1)) { 126 packed_sum -= my_used; 127 packed_items -= my_bin.size(); 128 for (size_type i = 0; i < my_bin.size(); ++i) 129 std::get<0>(p).try_put(my_bin[i]); 130 oneapi::tbb::flow::remove_edge(*the_value_pool, *my_bin_packer); // deactivate 131 done = true; 132 std::get<0>(p).try_put(desired_bin_capacity + 1); // send out signal 133 } 134 else { // this bin is well-utilized; send out bin and deactivate 135 oneapi::tbb::flow::remove_edge(*the_value_pool, 136 *my_bin_packer); // build no more bins 137 done = true; 138 if (my_used > 0) 139 std::get<1>(p).try_put(my_bin); 140 std::get<0>(p).try_put(desired_bin_capacity + 1); // send out signal 141 } 142 } 143 } 144 else if (item <= desired_bin_capacity - my_used && 145 item >= looking_for) { // this item can be packed 146 my_bin.push_back(item); 147 my_used += item; 148 packed_sum += item; 149 ++packed_items; 150 looking_for = desired_bin_capacity - my_used; 151 relax = 0; 152 if (packed_sum == item_sum) { 153 std::get<0>(p).try_put(desired_bin_capacity + 1); // send out signal 154 } 155 if (my_used == desired_bin_capacity) { 156 std::get<1>(p).try_put(my_bin); 157 my_bin.clear(); 158 my_used = 0; 159 looking_for = desired_bin_capacity; 160 } 161 } 162 else { // this item can't be packed; relax constraints 163 ++relax; 164 // this bin_packer has looked through enough items 165 if (relax >= (elements_num - packed_items) / optimality) { 166 relax = 0; 167 --looking_for; // accept a wider range of items 168 if (looking_for == 0 && my_used < desired_bin_capacity / (1 + optimality * .1) && 169 my_used > 0 && active_bins > 1) { 170 // this bin_packer is ill-utilized and can't find items; deactivate and throw back items 171 size_type remaining = active_bins--; 172 if (remaining > 1) { // not the last bin_packer 173 oneapi::tbb::flow::remove_edge(*the_value_pool, 174 *my_bin_packer); // deactivate 175 done = true; 176 } 177 else 178 active_bins++; // can't deactivate last bin_packer 179 packed_sum -= my_used; 180 packed_items -= my_bin.size(); 181 for (size_type i = 0; i < my_bin.size(); ++i) 182 std::get<0>(p).try_put(my_bin[i]); 183 my_bin.clear(); 184 my_used = 0; 185 } 186 else if (looking_for == 0 && 187 (my_used >= desired_bin_capacity / (1 + optimality * .1) || 188 active_bins == 1)) { 189 // this bin_packer can't find items but is well-utilized, so send it out and reset 190 std::get<1>(p).try_put(my_bin); 191 my_bin.clear(); 192 my_used = 0; 193 looking_for = desired_bin_capacity; 194 } 195 } 196 std::get<0>(p).try_put(item); // put unused item back to pool 197 } 198 } 199 }; 200 201 // input node uses this to send the values to the value_pool 202 class item_generator { 203 size_type counter; 204 205 public: 206 item_generator() : counter(0) {} 207 value_type operator()(oneapi::tbb::flow_control& fc) { 208 if (counter < elements_num) { 209 value_type result = input_array[counter]; 210 ++counter; 211 return result; 212 } 213 214 fc.stop(); 215 return value_type{}; 216 } 217 }; 218 219 // the terminal function_node uses this to gather stats and print bin information 220 class bin_printer { 221 value_type running_count; 222 size_type item_count; 223 value_type my_min, my_max; 224 double avg; 225 226 public: 227 bin_printer() 228 : running_count(0), 229 item_count(0), 230 my_min(desired_bin_capacity), 231 my_max(0), 232 avg(0) {} 233 oneapi::tbb::flow::continue_msg operator()(bin b) { 234 value_type sum = 0; 235 ++bins_num; 236 if (verbose) 237 std::cout << "[ "; 238 for (size_type i = 0; i < b.size(); ++i) { 239 if (verbose) 240 std::cout << b[i] << " "; 241 sum += b[i]; 242 ++item_count; 243 } 244 my_min = std::min(sum, my_min); 245 my_max = std::max(sum, my_max); 246 avg += sum; 247 running_count += sum; 248 if (verbose) { 249 std::cout << "]=" << sum << "; Done/Packed/Total cap: " << running_count << "/" 250 << packed_sum << "/" << item_sum << " items:" << item_count << "/" 251 << packed_items << "/" << elements_num << " bins_num=" << bins_num << "\n"; 252 } 253 if (item_count == elements_num) { // should be the last; print stats 254 avg = avg / (double)bins_num; 255 if (!silent) 256 std::cout << "SUMMARY: #Bins used: " << bins_num << "; Avg size: " << avg 257 << "; Max size: " << my_max << "; Min size: " << my_min << "\n" 258 << " Lower bound on optimal #bins: " << bins_num_min 259 << "; Start #bins: " << num_bin_packers << "\n"; 260 } 261 return oneapi::tbb::flow::continue_msg(); // need to return something 262 } 263 }; 264 265 int main(int argc, char* argv[]) { 266 utility::thread_number_range threads(utility::get_default_num_threads); 267 utility::parse_cli_arguments( 268 argc, 269 argv, 270 utility::cli_argument_pack() 271 //"-h" option for displaying help is present implicitly 272 .positional_arg(threads, "#threads", utility::thread_number_range_desc) 273 .arg(verbose, "verbose", " print diagnostic output to screen") 274 .arg(silent, "silent", " limits output to timing info; overrides verbose") 275 .arg(elements_num, "elements_num", " number of values to pack") 276 .arg(desired_bin_capacity, "bin_capacity", " capacity of each bin") 277 .arg(num_bin_packers, 278 "#packers", 279 " number of concurrent bin packers to use " 280 "(default=#threads)") 281 .arg(optimality, 282 "optimality", 283 "controls optimality of solution; 1 is highest, use\n" 284 " larger numbers for less optimal but faster solution")); 285 286 if (silent) 287 verbose = false; // make silent override verbose 288 // Generate random input data 289 srand(42); 290 input_array.resize(elements_num); 291 item_sum = 0; 292 for (auto& item : input_array) { 293 item = rand() % desired_bin_capacity + 1; // generate items that fit in a bin 294 item_sum += item; 295 } 296 bins_num_min = (item_sum % desired_bin_capacity) ? item_sum / desired_bin_capacity + 1 297 : item_sum / desired_bin_capacity; 298 299 oneapi::tbb::tick_count start = oneapi::tbb::tick_count::now(); 300 for (int p = threads.first; p <= threads.last; p = threads.step(p)) { 301 oneapi::tbb::global_control c(oneapi::tbb::global_control::max_allowed_parallelism, p); 302 packed_sum = 0; 303 packed_items = 0; 304 bins_num = 0; 305 if (num_bin_packers == -1) 306 num_bin_packers = p; 307 active_bins = num_bin_packers; 308 if (!silent) 309 std::cout << "binpack running with " << item_sum << " capacity over " << elements_num 310 << " items, optimality=" << optimality << ", " << num_bin_packers 311 << " bins of capacity=" << desired_bin_capacity << " on " << p << " threads." 312 << "\n"; 313 oneapi::tbb::flow::graph g; 314 value_source the_source(g, item_generator()); 315 value_pool the_value_pool(g); 316 oneapi::tbb::flow::make_edge(the_source, the_value_pool); 317 bin_buffer the_bin_buffer(g); 318 bins.resize(num_bin_packers); 319 for (int i = 0; i < num_bin_packers; ++i) { 320 bins[i] = new bin_packer(g, 1, bin_filler(i, &the_value_pool)); 321 oneapi::tbb::flow::make_edge(the_value_pool, *(bins[i])); 322 oneapi::tbb::flow::make_edge(oneapi::tbb::flow::output_port<0>(*(bins[i])), 323 the_value_pool); 324 oneapi::tbb::flow::make_edge(oneapi::tbb::flow::output_port<1>(*(bins[i])), 325 the_bin_buffer); 326 } 327 bin_writer the_writer(g, 1, bin_printer()); 328 make_edge(the_bin_buffer, the_writer); 329 the_source.activate(); 330 g.wait_for_all(); 331 for (int i = 0; i < num_bin_packers; ++i) { 332 delete bins[i]; 333 } 334 } 335 utility::report_elapsed_time((oneapi::tbb::tick_count::now() - start).seconds()); 336 return 0; 337 } 338