#include <vector>
#include <map>
#include <algorithm>
+#include <string>
#define NUM_DISTRO 5
#define SWITCHES_PER_ROW 6
};
int distro_placements[NUM_DISTRO] = {
5, 12, 19, 26, 33
+ // 3, 7, 12, 19, 26, 31, 35
};
unsigned horiz_cost[SWITCHES_PER_ROW] = {
- 346, 250, 154, 104, 200, 296
+ // one seat is 80cm wide. first switch is after 6 seats, then 18, then
+ // 30. gap is 5m extra (the distribution switches are on the eastern
+ // side).
+ 290, 194, 98, 48, 144, 240
};
// memoization table
};
struct value {
unsigned char distro;
- unsigned cost, this_cost;
+ unsigned cost, this_cost, this_distance;
};
std::map<key, value> cache;
unsigned cache_hits = 0;
std::vector<sw> switches;
+std::map<unsigned, unsigned> num_ports_used;
-unsigned distance(sw from_where, unsigned distro)
+unsigned find_distance(sw from_where, unsigned distro)
{
- // FIXME: calculate gaps as well
- unsigned base_cost = 41 * abs(from_where.row - distro_placements[distro]) + horiz_cost[from_where.num];
+ // 3.7m from row to row (2.5m gap + 1.2m boards)
+ unsigned base_cost = 37 * abs(from_where.row - distro_placements[distro]) + horiz_cost[from_where.num];
+ // 4m, 5m, 4m gaps (1.5m, 2.5m, 1.5m extra)
if ((from_where.row <= 9) == (distro_placements[distro] >= 10))
- base_cost += 25;
+ base_cost += 15;
if ((from_where.row <= 17) == (distro_placements[distro] >= 18))
base_cost += 25;
if ((from_where.row <= 25) == (distro_placements[distro] >= 26))
- base_cost += 25;
- if ((from_where.row <= 34) == (distro_placements[distro] >= 35))
- base_cost += 25;
+ base_cost += 15;
-#if TRUNCATE_METRIC
- if (base_cost > 600)
+ // add 5.6m slack.
+ return base_cost + 56;
+}
+
+unsigned cable_select(unsigned distance)
+{
+
+ if (distance > 600)
return 1000;
- if (base_cost > 500)
+ if (distance > 500)
return FIFTYPLUSTEN;
- if (base_cost > 400)
+ if (distance > 400)
return 500;
- if (base_cost > 300)
+ if (distance > 300)
return THIRTYPLUSTEN;
- if (base_cost > 200)
+ if (distance > 200)
return 300;
- if (base_cost > 100)
+ if (distance > 100)
return TENPLUSTEN;
return 100;
+}
+
+unsigned find_slack(unsigned distance)
+{
+ switch (cable_select(distance)) {
+ case 1000:
+ return 1000 - distance;
+ case FIFTYPLUSTEN:
+ return 600 - distance;
+ case 500:
+ return 500 - distance;
+ case THIRTYPLUSTEN:
+ return 400 - distance;
+ case 300:
+ return 300 - distance;
+ case TENPLUSTEN:
+ return 200 - distance;
+ case 100:
+ return 100 - distance;
+ }
+}
+
+unsigned find_cost(unsigned distance)
+{
+ //return find_slack(distance);
+
+#if TRUNCATE_METRIC
+ return cable_select(distance);
#else
- return base_cost;
-// return ((base_cost + 90) / 100) * 100;
+ return distance;
+// return ((distance + 90) / 100) * 100;
#endif
}
unsigned find_optimal_cost(key &k)
{
- unsigned best_cost = 999999990, best_this_cost = 0;
+ unsigned best_cost = 999999990, best_this_cost = 0, best_this_distance = 0;
int best = -1;
unsigned char db = k.distro_bound;
unsigned char dbh = k.distro_bound_hard;
if (k.ports_left[i] == 0)
continue;
- unsigned cost = distance(switches[k.sw_ind], i);
+ unsigned distance = find_distance(switches[k.sw_ind], i);
+ unsigned cost = find_cost(distance);
--(k.ports_left[i]);
++(k.sw_ind);
if (best == -1 || cost < best_cost) {
best = i;
best_cost = cost;
- best_this_cost = distance(switches[k.sw_ind], i);
+ best_this_distance = distance;
+ best_this_cost = find_cost(distance);
}
}
k.distro_bound = db;
k.distro_bound_hard = dbh;
- value v = { best, best_cost, best_this_cost };
+ value v = { best, best_cost, best_this_cost, best_this_distance };
cache[k] = v;
return best_cost;
}
+
+std::string port_name(unsigned distro, unsigned portnum)
+{
+ char buf[16];
+
+ if (distro == 0) {
+ if (portnum < 23) {
+ sprintf(buf, "d01-1 g0/%u", portnum);
+ } else {
+ sprintf(buf, "d01-2 g0/%u", portnum - 22);
+ }
+ } else if (distro == 1) {
+ sprintf(buf, "d02 g1/0/%u", portnum);
+ } else if (distro == 2) {
+ sprintf(buf, "d03 g1/%u", portnum);
+ } else if (distro == 3) {
+ sprintf(buf, "d04 g1/0/%u", portnum);
+ } else if (distro == 4) {
+ if (portnum < 23) {
+ sprintf(buf, "d05-1 g0/%u", portnum);
+ } else {
+ sprintf(buf, "d05-2 g0/%u", portnum - 22);
+ }
+ } else {
+ sprintf(buf, "d%02u 1/0/%u", distro + 1, portnum);
+ }
+
+ return buf;
+}
-int main()
+int main(int argc, char **argv)
{
struct key start;
+ FILE *patchlist = fopen("patchlist.txt", "w");
+ FILE *switchlist = fopen("switches.txt", "w");
#if TRUNCATE_METRIC
std::map<unsigned, unsigned> cable_count;
#endif
+ unsigned total_slack = 0;
+
+#if 0
+ // used for placement optimization
+ distro_placements[0] = atoi(argv[1]);
+ distro_placements[1] = atoi(argv[2]);
+ distro_placements[2] = atoi(argv[3]);
+ distro_placements[3] = atoi(argv[4]);
+ distro_placements[4] = atoi(argv[5]);
+ distro_placements[5] = atoi(argv[6]);
+ distro_placements[6] = atoi(argv[7]);
+#endif
switches.push_back(sw(1, 3));
switches.push_back(sw(1, 4));
switches.push_back(sw(2, 4));
switches.push_back(sw(2, 5));
- for (unsigned i = 3; i < 35; ++i)
+ for (unsigned i = 3; i <= 15; ++i)
+ for (unsigned j = 0; j < SWITCHES_PER_ROW; ++j)
+ switches.push_back(sw(i, j));
+
+ switches.push_back(sw(16, 0));
+ switches.push_back(sw(16, 1));
+ switches.push_back(sw(16, 2));
+ switches.push_back(sw(16, 4));
+ switches.push_back(sw(16, 5));
+
+ switches.push_back(sw(17, 0));
+ switches.push_back(sw(17, 1));
+ switches.push_back(sw(17, 2));
+ switches.push_back(sw(17, 4));
+ switches.push_back(sw(17, 5));
+
+ for (unsigned i = 18; i <= 34; ++i)
for (unsigned j = 0; j < SWITCHES_PER_ROW; ++j)
switches.push_back(sw(i, j));
- switches.push_back(sw(35, 1));
- switches.push_back(sw(35, 2));
switches.push_back(sw(35, 3));
switches.push_back(sw(35, 4));
+ switches.push_back(sw(35, 5));
- switches.push_back(sw(36, 1));
- switches.push_back(sw(36, 2));
switches.push_back(sw(36, 3));
switches.push_back(sw(36, 4));
-
- switches.push_back(sw(37, 1));
- switches.push_back(sw(37, 2));
- switches.push_back(sw(37, 3));
- switches.push_back(sw(37, 4));
+ switches.push_back(sw(36, 5));
start.sw_ind = 0;
start.distro_bound = 0;
start.distro_bound_hard = 0;
- start.ports_left[0] = 40;
- start.ports_left[1] = 40;
- start.ports_left[2] = 50;
- start.ports_left[3] = 40;
- start.ports_left[4] = 40;
+ start.ports_left[0] = 44;
+ start.ports_left[1] = 42;
+ start.ports_left[2] = 37;
+ start.ports_left[3] = 42;
+ start.ports_left[4] = 44;
+#if 0
+ // split distro
+ start.ports_left[0] = 22;
+ start.ports_left[1] = 22;
+ start.ports_left[2] = 42;
+ start.ports_left[3] = 37;
+ start.ports_left[4] = 42;
+ start.ports_left[5] = 22;
+ start.ports_left[6] = 22;
+#endif
+
printf("Finding optimal layout for %u switches\n", switches.size());
find_optimal_cost(start);
printf("%u cache nodes, %u cache hits.\n", cache.size(), cache_hits);
k.distro_bound_hard = k.distro_bound;
if (last_row != switches[k.sw_ind].row) {
- printf("\n");
+ printf("\n%2u-%2u ", switches[k.sw_ind].row * 2 - 1, switches[k.sw_ind].row * 2 + 0 );
last_num = -1;
}
for (int j = last_num; j + 1 < switches[k.sw_ind].num; ++j) {
printf("\e[%um%u ", v.distro + 33, v.distro);
#if TRUNCATE_METRIC
- if (v.this_cost == FIFTYPLUSTEN)
+ if (cable_select(v.this_distance) == FIFTYPLUSTEN)
printf("(50+10) ");
- else if (v.this_cost == THIRTYPLUSTEN)
+ else if (cable_select(v.this_distance) == THIRTYPLUSTEN)
printf("(30+10) ");
- else if (v.this_cost == TENPLUSTEN)
+ else if (cable_select(v.this_distance) == TENPLUSTEN)
printf("(10+10) ");
else
- printf("(%-3u ) ", v.this_cost / 10);
- cable_count[v.this_cost]++;
+ printf("(%-3u ) ", cable_select(v.this_distance) / 10);
+ total_slack += find_slack(v.this_distance);
+ cable_count[cable_select(v.this_distance)]++;
#else
+ total_slack += find_slack(v.this_distance);
printf("(%3.1f) ", v.this_cost / 10.0);
#endif
++(k.sw_ind);
--k.ports_left[v.distro];
+
+ fprintf(patchlist, "e%u-%u %s\n", last_row * 2 - 1, last_num + 1,
+ port_name(v.distro, ++num_ports_used[v.distro]).c_str());
+ fprintf(switchlist, "87.76.%u.%u 26 e%u-%u\n",
+ i / 4, (i % 4) * 64, last_row * 2 - 1, last_num + 1);
}
printf("\n");
- for (std::map<unsigned,unsigned>::iterator i = cable_count.begin(); i != cable_count.end(); ++i)
- printf("%u => %u\n", i->first, i->second);
+#if TRUNCATE_METRIC
+ cable_count[100] += cable_count[TENPLUSTEN];
+ cable_count[100] += cable_count[TENPLUSTEN];
+
+ cable_count[100] += cable_count[THIRTYPLUSTEN];
+ cable_count[300] += cable_count[THIRTYPLUSTEN];
+
+ cable_count[100] += cable_count[FIFTYPLUSTEN];
+ cable_count[500] += cable_count[FIFTYPLUSTEN];
+
+ printf("\n");
+ printf("10m: %3u\n", cable_count[100]);
+ printf("30m: %3u\n", cable_count[300]);
+ printf("50m: %3u\n", cable_count[500]);
+ printf("Extensions: %u\n", cable_count[TENPLUSTEN] + cable_count[THIRTYPLUSTEN] + cable_count[FIFTYPLUSTEN]);
+ printf("\n");
+
+ unsigned total_cable = 100 * cable_count[100] + 300 * cable_count[300] + 500 * cable_count[500];
+ printf("Total cable: %.1fm\n", total_cable / 10.0);
+ printf("Total slack: %.1fm (%.2f%%)\n", total_slack / 10.0, 100.0 * double(total_slack) / double(total_cable));
+#endif
}
projects / nms / commitdiff