(op: Operation)
| 255 | 时间复杂度: O(kd) k 为节点最大度数 d 为深度限制。建立所有Block所需时间 O(nkd) |
| 256 | """ |
| 257 | def _find_multi_input_ep(op: Operation): |
| 258 | # 如果当前节点后继节点存在多个，层序遍历寻找阻断节点 |
| 259 | least_first_queue = PriorityQueue() |
| 260 | least_first_queue.push(self.depth[op], op) |
| 261 | least_first_queue.pop() |
| 262 | |
| 263 | for down_op in self.graph.get_downstream_operations(op): |
| 264 | least_first_queue.push(self.depth[down_op], down_op) |
| 265 | |
| 266 | while not least_first_queue.empty(): |
| 267 | iter_operation = least_first_queue.pop()[-1] |
| 268 | if (least_first_queue.empty()): |
| 269 | upstream_ops = self.graph.get_upstream_operations(iter_operation) |
| 270 | if all([op in least_first_queue._ops for op in upstream_ops]) and len(upstream_ops) > 1: |
| 271 | return iter_operation |
| 272 | for down_op in self.graph.get_downstream_operations(iter_operation): |
| 273 | least_first_queue.push(self.depth[down_op], down_op) |
| 274 | |
| 275 | # if least_first_queue is empty, it means we can not find an blocking ep from given sp. |
| 276 | return None |
| 277 | |
| 278 | def _find_coherent_ep(op: Operation): |
| 279 | # 如果当前节点后继节点只有一个，向下寻找直系节点 |
nothing calls this directly
no test coverage detected