11 #define SWITCHES_PER_ROW 6
12 #define TRUNCATE_METRIC 1
13 #define TENPLUSTEN 250
14 #define THIRTYPLUSTEN 450
15 #define FIFTYPLUSTEN 650
18 unsigned char row, num;
20 sw(unsigned char row, unsigned char num) : row(row), num(num) {}
22 int distro_placements[NUM_DISTRO] = {
24 // 3, 7, 12, 19, 26, 31, 35
26 unsigned horiz_cost[SWITCHES_PER_ROW] = {
27 // one seat is 80cm wide. first switch is after 6 seats, then 18, then
28 // 30. gap is 5m extra (the distribution switches are on the eastern
30 290, 194, 98, 48, 144, 240
35 unsigned char sw_ind, distro_bound, distro_bound_hard;
36 unsigned char ports_left[NUM_DISTRO];
38 bool operator< (const key &other) const
40 if (sw_ind != other.sw_ind)
41 return (sw_ind < other.sw_ind);
42 if (distro_bound != other.distro_bound)
43 return (distro_bound < other.distro_bound);
44 if (distro_bound_hard != other.distro_bound_hard)
45 return (distro_bound_hard < other.distro_bound_hard);
46 for (unsigned i = distro_bound_hard; i < NUM_DISTRO - 1; ++i)
47 if (ports_left[i] != other.ports_left[i])
48 return (ports_left[i] < other.ports_left[i]);
49 return (ports_left[NUM_DISTRO - 1] < other.ports_left[NUM_DISTRO - 1]);
54 unsigned cost, this_cost, this_distance;
56 std::map<key, value> cache;
57 unsigned cache_hits = 0;
58 std::vector<sw> switches;
59 std::map<unsigned, unsigned> num_ports_used;
61 unsigned find_distance(sw from_where, unsigned distro)
63 // 3.7m from row to row (2.5m gap + 1.2m boards)
64 unsigned base_cost = 37 * abs(from_where.row - distro_placements[distro]) + horiz_cost[from_where.num];
66 // 4m, 5m, 4m gaps (1.5m, 2.5m, 1.5m extra)
67 if ((from_where.row <= 9) == (distro_placements[distro] >= 10))
69 if ((from_where.row <= 17) == (distro_placements[distro] >= 18))
71 if ((from_where.row <= 25) == (distro_placements[distro] >= 26))
75 return base_cost + 56;
78 unsigned cable_select(unsigned distance)
96 unsigned find_slack(unsigned distance)
98 switch (cable_select(distance)) {
100 return 1000 - distance;
102 return 600 - distance;
104 return 500 - distance;
106 return 400 - distance;
108 return 300 - distance;
110 return 200 - distance;
112 return 100 - distance;
116 unsigned find_cost(unsigned distance)
118 //return find_slack(distance);
121 return cable_select(distance);
124 // return ((distance + 90) / 100) * 100;
128 unsigned find_optimal_cost(key &k)
130 unsigned best_cost = 999999990, best_this_cost = 0, best_this_distance = 0;
132 unsigned char db = k.distro_bound;
133 unsigned char dbh = k.distro_bound_hard;
135 if (k.sw_ind == switches.size())
137 if (cache.count(k)) {
139 return cache[k].cost;
142 bool next_changes_row = (k.sw_ind + 1U < switches.size() && switches[k.sw_ind].row != switches[k.sw_ind + 1].row);
144 for (unsigned char i = dbh; i < dbh + 2 && i < NUM_DISTRO; ++i) {
145 if (k.ports_left[i] == 0)
148 unsigned distance = find_distance(switches[k.sw_ind], i);
149 unsigned cost = find_cost(distance);
154 k.distro_bound = std::max(i, db);
155 if (next_changes_row) {
156 k.distro_bound_hard = k.distro_bound;
159 cost += find_optimal_cost(k);
163 if (best == -1 || cost < best_cost) {
166 best_this_distance = distance;
167 best_this_cost = find_cost(distance);
171 k.distro_bound_hard = dbh;
173 value v = { best, best_cost, best_this_cost, best_this_distance };
179 std::string port_name(unsigned distro, unsigned portnum)
185 sprintf(buf, "d01-1 g0/%u", portnum);
187 sprintf(buf, "d01-2 g0/%u", portnum - 22);
189 } else if (distro == 1) {
190 sprintf(buf, "d02 g1/0/%u", portnum);
191 } else if (distro == 2) {
192 sprintf(buf, "d03 g1/%u", portnum);
193 } else if (distro == 3) {
194 sprintf(buf, "d04 g1/0/%u", portnum);
195 } else if (distro == 4) {
197 sprintf(buf, "d05-1 g0/%u", portnum);
199 sprintf(buf, "d05-2 g0/%u", portnum - 22);
202 sprintf(buf, "d%02u 1/0/%u", distro + 1, portnum);
208 int main(int argc, char **argv)
211 FILE *patchlist = fopen("patchlist.txt", "w");
212 FILE *switchlist = fopen("switches.txt", "w");
214 std::map<unsigned, unsigned> cable_count;
216 unsigned total_slack = 0;
219 // used for placement optimization
220 distro_placements[0] = atoi(argv[1]);
221 distro_placements[1] = atoi(argv[2]);
222 distro_placements[2] = atoi(argv[3]);
223 distro_placements[3] = atoi(argv[4]);
224 distro_placements[4] = atoi(argv[5]);
225 distro_placements[5] = atoi(argv[6]);
226 distro_placements[6] = atoi(argv[7]);
229 switches.push_back(sw(1, 3));
230 switches.push_back(sw(1, 4));
231 switches.push_back(sw(1, 5));
232 switches.push_back(sw(2, 3));
233 switches.push_back(sw(2, 4));
234 switches.push_back(sw(2, 5));
236 for (unsigned i = 3; i <= 15; ++i)
237 for (unsigned j = 0; j < SWITCHES_PER_ROW; ++j)
238 switches.push_back(sw(i, j));
240 switches.push_back(sw(16, 0));
241 switches.push_back(sw(16, 1));
242 switches.push_back(sw(16, 2));
243 switches.push_back(sw(16, 4));
244 switches.push_back(sw(16, 5));
246 switches.push_back(sw(17, 0));
247 switches.push_back(sw(17, 1));
248 switches.push_back(sw(17, 2));
249 switches.push_back(sw(17, 4));
250 switches.push_back(sw(17, 5));
252 for (unsigned i = 18; i <= 34; ++i)
253 for (unsigned j = 0; j < SWITCHES_PER_ROW; ++j)
254 switches.push_back(sw(i, j));
256 switches.push_back(sw(35, 3));
257 switches.push_back(sw(35, 4));
258 switches.push_back(sw(35, 5));
260 switches.push_back(sw(36, 3));
261 switches.push_back(sw(36, 4));
262 switches.push_back(sw(36, 5));
265 start.distro_bound = 0;
266 start.distro_bound_hard = 0;
267 start.ports_left[0] = 44;
268 start.ports_left[1] = 42;
269 start.ports_left[2] = 37;
270 start.ports_left[3] = 42;
271 start.ports_left[4] = 44;
275 start.ports_left[0] = 22;
276 start.ports_left[1] = 22;
277 start.ports_left[2] = 42;
278 start.ports_left[3] = 37;
279 start.ports_left[4] = 42;
280 start.ports_left[5] = 22;
281 start.ports_left[6] = 22;
284 printf("Finding optimal layout for %u switches\n", switches.size());
285 find_optimal_cost(start);
286 printf("%u cache nodes, %u cache hits.\n", cache.size(), cache_hits);
289 int last_row = 0, last_num = -1;
290 for (unsigned i = 0; i < switches.size(); ++i) {
292 bool next_changes_row = (k.sw_ind + 1U < switches.size() && switches[k.sw_ind].row != switches[k.sw_ind + 1].row);
294 if (cache.count(k) == 0) {
295 fprintf(stderr, "FATAL: no solutions!\n");
299 k.distro_bound = std::max(k.distro_bound, v.distro);
300 if (next_changes_row)
301 k.distro_bound_hard = k.distro_bound;
303 if (last_row != switches[k.sw_ind].row) {
304 printf("\n%2u-%2u ", switches[k.sw_ind].row * 2 - 1, switches[k.sw_ind].row * 2 + 0 );
307 for (int j = last_num; j + 1 < switches[k.sw_ind].num; ++j) {
312 printf("
\e[%um%u ", v.distro + 33, v.distro);
314 if (cable_select(v.this_distance) == FIFTYPLUSTEN)
316 else if (cable_select(v.this_distance) == THIRTYPLUSTEN)
318 else if (cable_select(v.this_distance) == TENPLUSTEN)
321 printf("(%-3u ) ", cable_select(v.this_distance) / 10);
322 total_slack += find_slack(v.this_distance);
323 cable_count[cable_select(v.this_distance)]++;
325 total_slack += find_slack(v.this_distance);
326 printf("(%3.1f) ", v.this_cost / 10.0);
329 last_row = switches[k.sw_ind].row;
330 last_num = switches[k.sw_ind].num;
333 --k.ports_left[v.distro];
335 fprintf(patchlist, "e%u-%u %s\n", last_row * 2 - 1, last_num + 1,
336 port_name(v.distro, ++num_ports_used[v.distro]).c_str());
337 fprintf(switchlist, "87.76.%u.%u 26 e%u-%u\n",
338 i / 4, (i % 4) * 64, last_row * 2 - 1, last_num + 1);
343 cable_count[100] += cable_count[TENPLUSTEN];
344 cable_count[100] += cable_count[TENPLUSTEN];
346 cable_count[100] += cable_count[THIRTYPLUSTEN];
347 cable_count[300] += cable_count[THIRTYPLUSTEN];
349 cable_count[100] += cable_count[FIFTYPLUSTEN];
350 cable_count[500] += cable_count[FIFTYPLUSTEN];
353 printf("10m: %3u\n", cable_count[100]);
354 printf("30m: %3u\n", cable_count[300]);
355 printf("50m: %3u\n", cable_count[500]);
356 printf("Extensions: %u\n", cable_count[TENPLUSTEN] + cable_count[THIRTYPLUSTEN] + cable_count[FIFTYPLUSTEN]);
359 unsigned total_cable = 100 * cable_count[100] + 300 * cable_count[300] + 500 * cable_count[500];
360 printf("Total cable: %.1fm\n", total_cable / 10.0);
361 printf("Total slack: %.1fm (%.2f%%)\n", total_slack / 10.0, 100.0 * double(total_slack) / double(total_cable));