GCC Code Coverage Report

Directory: ./
File: Mapping/MappingManager.cpp
Date: 2022-10-15 05:10:18
Warnings: 2 unchecked decisions!
Exec Total Coverage
Lines: 88 88 100.0%
Functions: 4 4 100.0%
Branches: 94 144 65.3%
Decisions: 26 30 86.7%
Line Branch Decision Exec Source
1 // Copyright 2019-2022 Cambridge Quantum Computing
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "Mapping/MappingManager.hpp"
16
17 #include "Architecture/BestTsaWithArch.hpp"
18
19 namespace tket {
20
21 71 MappingManager::MappingManager(const ArchitecturePtr& _architecture)
22 71 : architecture_(_architecture) {}
23
24 36 bool MappingManager::route_circuit(
25 Circuit& circuit, const std::vector<RoutingMethodPtr>& routing_methods,
26 bool label_isolated_qubits) const {
27
2/2
✓ Branch 1 taken 34 times.
✓ Branch 2 taken 2 times.
 36 return this->route_circuit_with_maps(
28 72 circuit, routing_methods, std::make_shared<unit_bimaps_t>(),
29 68 label_isolated_qubits);
30 }
31
32 71 bool MappingManager::route_circuit_with_maps(
33 Circuit& circuit, const std::vector<RoutingMethodPtr>& routing_methods,
34 std::shared_ptr<unit_bimaps_t> maps, bool label_isolated_qubits) const {
35
3/4
✓ Branch 1 taken 71 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 1 times.
✓ Branch 6 taken 70 times.
2/2
✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 69 times.
 71 if (circuit.n_qubits() > this->architecture_->n_nodes()) {
36 std::string error_string =
37
4/8
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 1 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 1 times.
✗ Branch 11 not taken.
 2 "Circuit has" + std::to_string(circuit.n_qubits()) +
38
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 2 " logical qubits. Architecture has " +
39
1/2
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
 1 std::to_string(this->architecture_->n_nodes()) +
40 " physical qubits. Circuit to be routed can not have more "
41
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 "qubits than the Architecture.";
42
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 1 throw MappingManagerError(error_string);
43 1 }
44
45 // mapping_frontier tracks boundary between routed & un-routed in circuit
46 // when initialised, boundary is over output edges of input vertices
47 70 MappingFrontier_ptr mapping_frontier;
48
7/10
✓ Branch 2 taken 70 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 35 times.
✓ Branch 5 taken 35 times.
✓ Branch 8 taken 35 times.
✗ Branch 9 not taken.
✓ Branch 10 taken 35 times.
✗ Branch 11 not taken.
✓ Branch 12 taken 35 times.
✓ Branch 13 taken 35 times.
2/2
✓ Decision 'true' taken 35 times.
✓ Decision 'false' taken 35 times.
 70 if (!maps->initial.empty() && !maps->final.empty()) {
49
1/2
✓ Branch 1 taken 35 times.
✗ Branch 2 not taken.
 35 mapping_frontier = std::make_shared<MappingFrontier>(circuit, maps);
50 } else {
51
1/2
✓ Branch 1 taken 35 times.
✗ Branch 2 not taken.
 35 mapping_frontier = std::make_shared<MappingFrontier>(circuit);
52 }
53 // updates routed/un-routed boundary
54
55
1/2
✓ Branch 2 taken 70 times.
✗ Branch 3 not taken.
 70 mapping_frontier->advance_frontier_boundary(this->architecture_);
56
57 28047 auto check_finish = [&mapping_frontier]() {
58 3108 for (const std::pair<UnitID, VertPort>& pair :
59
5/8
✓ Branch 6 taken 8313 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 5299 times.
✗ Branch 10 not taken.
✓ Branch 12 taken 8407 times.
✗ Branch 13 not taken.
✓ Branch 14 taken 8313 times.
✓ Branch 15 taken 94 times.
 11515 mapping_frontier->linear_boundary->get<TagKey>()) {
60 8313 Edge e = mapping_frontier->circuit_.get_nth_out_edge(
61
1/2
✓ Branch 1 taken 8313 times.
✗ Branch 2 not taken.
 8313 pair.second.first, pair.second.second);
62
1/2
✓ Branch 2 taken 8313 times.
✗ Branch 3 not taken.
 8313 Vertex v = mapping_frontier->circuit_.target(e);
63
1/2
✓ Branch 2 taken 8313 times.
✗ Branch 3 not taken.
 8313 OpType ot = mapping_frontier->circuit_.get_OpType_from_Vertex(v);
64
7/8
✓ Branch 1 taken 8313 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 4912 times.
✓ Branch 4 taken 3401 times.
✓ Branch 5 taken 3014 times.
✓ Branch 6 taken 1898 times.
✓ Branch 7 taken 3014 times.
✓ Branch 8 taken 5299 times.
2/2
✓ Decision 'true' taken 3014 times.
✓ Decision 'false' taken 5299 times.
 8313 if (!is_final_q_type(ot) && ot != OpType::ClOutput) {
65 3014 return false;
66 }
67 }
68 94 return true;
69 70 };
70
71
1/2
✓ Branch 1 taken 70 times.
✗ Branch 2 not taken.
 70 bool circuit_modified = !check_finish();
72
3/4
✓ Branch 1 taken 3038 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 2969 times.
✓ Branch 4 taken 69 times.
0/1
? Decision couldn't be analyzed.
 3038 while (!check_finish()) {
73 // The order methods are passed in std::vector<RoutingMethod> is
74 // the order they are run
75 // If a method performs better but only on specific subcircuits,
76 // rank it earlier in the passed vector
77 2969 bool valid_methods = false;
78
2/2
✓ Branch 5 taken 5891 times.
✓ Branch 6 taken 1 times.
2/2
✓ Decision 'true' taken 5891 times.
✓ Decision 'false' taken 1 times.
 5892 for (const auto& rm : routing_methods) {
79 // true => can use held routing method
80 std::pair<bool, unit_map_t> bool_map =
81
1/2
✓ Branch 2 taken 5891 times.
✗ Branch 3 not taken.
 5891 rm->routing_method(mapping_frontier, this->architecture_);
82
2/2
✓ Branch 0 taken 2968 times.
✓ Branch 1 taken 2923 times.
2/2
✓ Decision 'true' taken 2968 times.
✓ Decision 'false' taken 2923 times.
 5891 if (bool_map.first) {
83 2968 valid_methods = true;
84
2/2
✓ Branch 1 taken 1 times.
✓ Branch 2 taken 2967 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 2967 times.
 2968 if (bool_map.second.size() > 0) {
85 1 std::map<Node, Node> node_map;
86
2/2
✓ Branch 4 taken 3 times.
✓ Branch 5 taken 1 times.
2/2
✓ Decision 'true' taken 3 times.
✓ Decision 'false' taken 1 times.
 4 for (const auto& x : bool_map.second) {
87
3/6
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 3 times.
✗ Branch 9 not taken.
 3 node_map.insert({Node(x.first), Node(x.second)});
88 }
89 1 for (const std::pair<Node, Node>& swap :
90
3/4
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 9 taken 2 times.
✓ Branch 10 taken 1 times.
 4 BestTsaWithArch::get_swaps(*this->architecture_, node_map)) {
91
1/2
✓ Branch 2 taken 2 times.
✗ Branch 3 not taken.
 2 mapping_frontier->add_swap(swap.first, swap.second);
92 1 }
93 1 }
94 2968 break;
95 }
96
2/2
✓ Branch 1 taken 2923 times.
✓ Branch 2 taken 2968 times.
 5891 }
97
2/2
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 2968 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 2968 times.
 2969 if (!valid_methods) {
98
2/4
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 1 times.
✗ Branch 6 not taken.
 1 throw MappingManagerError(
99 2 "No RoutingMethod suitable to map given subcircuit.");
100 }
101 // find next routed/unrouted boundary given updates
102
1/2
✓ Branch 2 taken 2968 times.
✗ Branch 3 not taken.
 2968 mapping_frontier->advance_frontier_boundary(this->architecture_);
103 }
104 // there may still be some unlabelled qubits
105
2/2
✓ Branch 0 taken 63 times.
✓ Branch 1 taken 6 times.
2/2
✓ Decision 'true' taken 63 times.
✓ Decision 'false' taken 6 times.
 69 if (label_isolated_qubits) {
106 63 circuit_modified = true;
107
108 63 unit_map_t placement;
109 63 qubit_vector_t to_place;
110 63 std::vector<Node> placed;
111
112 // Find which/if any qubits need placing
113
3/4
✓ Branch 2 taken 63 times.
✗ Branch 3 not taken.
✓ Branch 9 taken 467 times.
✓ Branch 10 taken 63 times.
0/1
? Decision couldn't be analyzed.
 530 for (const Qubit& q : mapping_frontier->circuit_.all_qubits()) {
114
1/2
✓ Branch 1 taken 467 times.
✗ Branch 2 not taken.
 467 Node n(q);
115
3/4
✓ Branch 2 taken 467 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 9 times.
✓ Branch 5 taken 458 times.
2/2
✓ Decision 'true' taken 9 times.
✓ Decision 'false' taken 458 times.
 467 if (!this->architecture_->node_exists(n)) {
116 // Ancilla qubits can be assigned during routing
117 // If some qubits are unplaced then its possible the returned circuit
118 // has more qubits than the architecture has nodes, which is bad instead
119 // at least assign any unlabelled qubits to any ancilla nodes to prevent
120 // this
121
2/2
✓ Branch 2 taken 1 times.
✓ Branch 3 taken 8 times.
2/2
✓ Decision 'true' taken 1 times.
✓ Decision 'false' taken 8 times.
 9 if (mapping_frontier->ancilla_nodes_.size() > 0) {
122 1 circuit_modified = true;
123 1 Node ancilla = *mapping_frontier->ancilla_nodes_.begin();
124
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 1 mapping_frontier->merge_ancilla(q, ancilla);
125
1/2
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
 2 mapping_frontier->ancilla_nodes_.erase(
126 1 mapping_frontier->ancilla_nodes_.begin());
127
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 placed.push_back(n);
128 1 } else {
129
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 to_place.push_back(n);
130 }
131 } else {
132
1/2
✓ Branch 1 taken 458 times.
✗ Branch 2 not taken.
 458 placed.push_back(n);
133 // if already placed, make sure qubit retains placement
134
1/2
✓ Branch 2 taken 458 times.
✗ Branch 3 not taken.
 458 placement.insert({n, n});
135 }
136 530 }
137 // avoid doing std::set_difference unless qubits need to be placed
138 63 unsigned n_placed = to_place.size();
139
2/2
✓ Branch 0 taken 3 times.
✓ Branch 1 taken 60 times.
2/2
✓ Decision 'true' taken 3 times.
✓ Decision 'false' taken 60 times.
 63 if (n_placed > 0) {
140 3 std::vector<Node> difference,
141
1/2
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 3 architecture_nodes = this->architecture_->get_all_nodes_vec();
142
2/4
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
✓ Branch 9 taken 3 times.
✗ Branch 10 not taken.
 3 std::set_difference(
143 architecture_nodes.begin(), architecture_nodes.end(), placed.begin(),
144 placed.end(), std::inserter(difference, difference.begin()));
145 // should always be enough remaining qubits to assign unplaced qubits to
146 TKET_ASSERT(difference.size() >= n_placed);
147
2/2
✓ Branch 0 taken 8 times.
✓ Branch 1 taken 3 times.
2/2
✓ Decision 'true' taken 8 times.
✓ Decision 'false' taken 3 times.
 11 for (unsigned i = 0; i < n_placed; i++) {
148 // naively assign each qubit to some free node
149
1/2
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
 8 placement.insert({to_place[i], difference[i]});
150
1/2
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
 32 mapping_frontier->update_bimaps(
151
1/2
✓ Branch 3 taken 8 times.
✗ Branch 4 not taken.
 16 mapping_frontier->get_qubit_from_circuit_uid(to_place[i]),
152 8 difference[i]);
153 }
154
155
1/2
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 3 mapping_frontier->update_linear_boundary_uids(placement);
156
1/2
✓ Branch 2 taken 3 times.
✗ Branch 3 not taken.
 3 mapping_frontier->circuit_.rename_units(placement);
157 3 }
158 63 }
159
160 69 return circuit_modified;
161 70 }
162 } // namespace tket
163