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