| 993 | } |
| 994 | |
| 995 | void grid_volume::find_best_split(int desired_chunks, bool fragment_cost, int &best_split_point, |
| 996 | direction &best_split_direction, |
| 997 | double &left_effort_fraction) const { |
| 998 | if (size_t(desired_chunks) > nowned_min()) { |
| 999 | meep::abort("Cannot split %zd grid points into %d parts\n", nowned_min(), desired_chunks); |
| 1000 | } |
| 1001 | |
| 1002 | left_effort_fraction = 0; |
| 1003 | best_split_point = 0; |
| 1004 | best_split_direction = NO_DIRECTION; |
| 1005 | if (desired_chunks == 1) return; |
| 1006 | |
| 1007 | direction longest_axis = NO_DIRECTION; |
| 1008 | int num_in_longest_axis = 0; |
| 1009 | LOOP_OVER_DIRECTIONS(dim, d) { |
| 1010 | if (num_direction(d) > num_in_longest_axis) { |
| 1011 | longest_axis = d; |
| 1012 | num_in_longest_axis = num_direction(d); |
| 1013 | } |
| 1014 | } |
| 1015 | |
| 1016 | double best_split_measure = 1e20; |
| 1017 | LOOP_OVER_DIRECTIONS(dim, d) { |
| 1018 | int first = 0, last = num_direction(d); |
| 1019 | while (first < last) { // bisection search for balanced splitting |
| 1020 | int mid = (first + last) / 2; |
| 1021 | double mid_diff = cost_diff(desired_chunks, get_split_costs(d, mid, fragment_cost)); |
| 1022 | if (mid_diff > 0) { |
| 1023 | if (first == mid) break; |
| 1024 | first = mid; |
| 1025 | } |
| 1026 | else if (mid_diff < 0) |
| 1027 | last = mid; |
| 1028 | else |
| 1029 | break; |
| 1030 | } |
| 1031 | int split_point = (first + last) / 2; |
| 1032 | std::complex<double> costs = get_split_costs(d, split_point, fragment_cost); |
| 1033 | double left_cost = real(costs), right_cost = imag(costs); |
| 1034 | double total_cost = left_cost + right_cost; |
| 1035 | double split_measure = std::max(left_cost / (desired_chunks / 2), |
| 1036 | right_cost / (desired_chunks - (desired_chunks / 2))); |
| 1037 | // Give a 30% preference to the longest axis, as a heuristic to prefer lower communication costs |
| 1038 | // when the split_measure is somewhat close. TODO: use a data-driven communication cost |
| 1039 | // function. |
| 1040 | if (d == longest_axis) split_measure *= 0.7; |
| 1041 | if (split_measure < best_split_measure) { |
| 1042 | best_split_measure = split_measure; |
| 1043 | best_split_point = split_point; |
| 1044 | best_split_direction = d; |
| 1045 | left_effort_fraction = left_cost / total_cost; |
| 1046 | } |
| 1047 | } |
| 1048 | } |
| 1049 | |
| 1050 | grid_volume grid_volume::split_at_fraction(bool side_high, int split_pt, int split_dir) const { |
| 1051 | if (dim == Dcyl) split_dir %= 3; |
no test coverage detected