GCC Code Coverage Report

Directory: ./
File: Mapping/MultiGateReorder.cpp
Date: 2022-10-15 05:10:18
Warnings: 1 unchecked decisions!
Exec Total Coverage
Lines: 135 140 96.4%
Functions: 11 13 84.6%
Branches: 119 206 57.8%
Decisions: 23 26 88.5%
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/MultiGateReorder.hpp"
16
17 #include "Circuit/DAGDefs.hpp"
18 #include "Mapping/MappingFrontier.hpp"
19
20 namespace tket {
21
22 9 MultiGateReorder::MultiGateReorder(
23 const ArchitecturePtr &_architecture,
24 9 MappingFrontier_ptr &_mapping_frontier)
25 9 : architecture_(_architecture), mapping_frontier_(_mapping_frontier) {
26 // This needs to be updated every time the frontier changes
27 this->u_frontier_edges_ =
28
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 18 convert_u_frontier_to_edges(*frontier_convert_vertport_to_edge(
29
1/2
✓ Branch 3 taken 9 times.
✗ Branch 4 not taken.
 18 _mapping_frontier->circuit_, _mapping_frontier->linear_boundary));
30 9 }
31
32 // Traverse the DAG to the quantum frontier
33 // to find the UnitID associated with an VertPort
34 83 static UnitID get_unitid_from_vertex_port(
35 const MappingFrontier_ptr &frontier, const VertPort &vert_port) {
36 83 VertPort current_vert_port = vert_port;
37 while (true) {
38 auto it =
39
1/2
✓ Branch 4 taken 257 times.
✗ Branch 5 not taken.
 257 frontier->linear_boundary->get<TagValue>().find(current_vert_port);
40
3/4
✓ Branch 5 taken 257 times.
✗ Branch 6 not taken.
✓ Branch 7 taken 83 times.
✓ Branch 8 taken 174 times.
2/2
✓ Decision 'true' taken 83 times.
✓ Decision 'false' taken 174 times.
 257 if (it != frontier->linear_boundary->get<TagValue>().end()) {
41
1/2
✓ Branch 1 taken 83 times.
✗ Branch 2 not taken.
 83 return it->first;
42 }
43
1/2
✓ Branch 2 taken 174 times.
✗ Branch 3 not taken.
 174 Edge current_e = frontier->circuit_.get_nth_out_edge(
44 current_vert_port.first, current_vert_port.second);
45 Vertex prev_vert;
46
1/2
✓ Branch 1 taken 174 times.
✗ Branch 2 not taken.
 174 Edge prev_e;
47 174 std::tie(prev_vert, prev_e) =
48
1/2
✓ Branch 2 taken 174 times.
✗ Branch 3 not taken.
 348 frontier->circuit_.get_prev_pair(current_vert_port.first, current_e);
49
1/2
✓ Branch 2 taken 174 times.
✗ Branch 3 not taken.
 174 current_vert_port = {prev_vert, frontier->circuit_.get_source_port(prev_e)};
50 174 }
51 }
52
53 48 static bool is_multiq_quantum_gate(const Circuit &circ, const Vertex &vert) {
54
1/2
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
 48 Op_ptr op = circ.get_Op_ptr_from_Vertex(vert);
55 return (
56
4/8
✓ Branch 1 taken 48 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 48 times.
✗ Branch 5 not taken.
✓ Branch 6 taken 41 times.
✓ Branch 7 taken 7 times.
✗ Branch 9 not taken.
✗ Branch 10 not taken.
 144 op->get_desc().is_gate() && circ.n_in_edges(vert) > 1 &&
57
1/2
✓ Branch 1 taken 41 times.
✗ Branch 2 not taken.
 41 circ.n_in_edges_of_type(vert, EdgeType::Quantum) ==
58
4/8
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 48 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 41 times.
✗ Branch 8 not taken.
✓ Branch 9 taken 41 times.
✗ Branch 10 not taken.
 185 circ.n_in_edges(vert) &&
59
1/2
✓ Branch 1 taken 41 times.
✗ Branch 2 not taken.
 41 circ.n_out_edges_of_type(vert, EdgeType::Quantum) ==
60
3/6
✓ Branch 1 taken 41 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 41 times.
✗ Branch 4 not taken.
✓ Branch 5 taken 48 times.
✗ Branch 6 not taken.
 137 circ.n_out_edges(vert));
61 48 }
62
63 41 static bool is_physically_permitted(
64 const MappingFrontier_ptr &frontier, const ArchitecturePtr &arc_ptr,
65 const Vertex &vert) {
66 41 std::vector<Node> nodes;
67
3/4
✓ Branch 2 taken 124 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 83 times.
✓ Branch 5 taken 41 times.
0/1
? Decision couldn't be analyzed.
 124 for (port_t port = 0; port < frontier->circuit_.n_ports(vert); ++port) {
68
3/6
✓ Branch 2 taken 83 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 83 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 83 times.
✗ Branch 9 not taken.
 83 nodes.push_back(Node(get_unitid_from_vertex_port(frontier, {vert, port})));
69 }
70
1/2
✓ Branch 2 taken 41 times.
✗ Branch 3 not taken.
 82 return frontier->valid_boundary_operation(
71
1/2
✓ Branch 2 taken 41 times.
✗ Branch 3 not taken.
 123 arc_ptr, frontier->circuit_.get_Op_ptr_from_Vertex(vert), nodes);
72 41 }
73
74 // This method will try to commute a vertex to the quantum frontier
75 21 static std::optional<std::pair<EdgeVec, EdgeVec>> try_find_commute_edges(
76 const Circuit &circ, const EdgeVec &frontier_edges, const Vertex &vert) {
77 // Initialize to be the in_edges for the given vertex
78
1/2
✓ Branch 1 taken 21 times.
✗ Branch 2 not taken.
 21 EdgeVec current_edges = circ.get_in_edges(vert);
79
1/2
✓ Branch 4 taken 21 times.
✗ Branch 5 not taken.
 21 EdgeVec initial_edges(current_edges.begin(), current_edges.end());
80
81 // Record the colour of each port of the vertex.
82 21 std::vector<std::optional<Pauli>> colours;
83
2/2
✓ Branch 5 taken 43 times.
✓ Branch 6 taken 21 times.
2/2
✓ Decision 'true' taken 43 times.
✓ Decision 'false' taken 21 times.
 64 for (const Edge &edge : current_edges) {
84
1/2
✓ Branch 1 taken 43 times.
✗ Branch 2 not taken.
 43 port_t target_port = circ.get_target_port(edge);
85 std::optional<Pauli> colour =
86
1/2
✓ Branch 1 taken 43 times.
✗ Branch 2 not taken.
 43 circ.commuting_basis(vert, PortType::Target, target_port);
87
1/2
✓ Branch 1 taken 43 times.
✗ Branch 2 not taken.
 43 colours.push_back(colour);
88 }
89 // Stores all edges which the vertex can be commuted to
90 21 EdgeVec dest_edges;
91 while (true) {
92 // The vertex can be commuted to the front
93 55 bool success = true;
94
2/2
✓ Branch 1 taken 110 times.
✓ Branch 2 taken 53 times.
2/2
✓ Decision 'true' taken 110 times.
✓ Decision 'false' taken 53 times.
 163 for (unsigned i = 0; i < current_edges.size(); ++i) {
95 // Check if the edge is already in the quantum frontier
96
1/2
✓ Branch 3 taken 110 times.
✗ Branch 4 not taken.
2/2
✓ Decision 'true' taken 58 times.
✓ Decision 'false' taken 52 times.
 110 if (std::find(
97 110 frontier_edges.begin(), frontier_edges.end(), current_edges[i]) !=
98
2/2
✓ Branch 2 taken 58 times.
✓ Branch 3 taken 52 times.
 220 frontier_edges.end()) {
99
1/2
✓ Branch 2 taken 58 times.
✗ Branch 3 not taken.
 58 dest_edges.push_back(current_edges[i]);
100 58 continue;
101 }
102 // Check prev_op is a gate
103
1/2
✓ Branch 2 taken 52 times.
✗ Branch 3 not taken.
 52 Vertex prev_vert = circ.source(current_edges[i]);
104
1/2
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
 52 Op_ptr prev_op = circ.get_Op_ptr_from_Vertex(prev_vert);
105
3/6
✓ Branch 2 taken 52 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 52 times.
✗ Branch 6 not taken.
✗ Branch 8 not taken.
✓ Branch 9 taken 52 times.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 52 times.
 52 if (!prev_op->get_desc().is_gate()) {
106 // not commute
107 ✗ return std::nullopt;
108 }
109
110 // Check commute
111
1/2
✓ Branch 2 taken 52 times.
✗ Branch 3 not taken.
 52 port_t source_port = circ.get_source_port(current_edges[i]);
112
3/4
✓ Branch 1 taken 52 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 2 times.
✓ Branch 4 taken 50 times.
2/2
✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 50 times.
 52 if (!circ.commutes_with_basis(
113 52 prev_vert, colours[i], PortType::Source, source_port)) {
114 // not commute
115 2 return std::nullopt;
116 } else {
117 // Update dest_edges
118 Vertex prev_prev_v;
119
1/2
✓ Branch 1 taken 50 times.
✗ Branch 2 not taken.
 50 Edge prev_e;
120 50 std::tie(prev_prev_v, prev_e) =
121
1/2
✓ Branch 2 taken 50 times.
✗ Branch 3 not taken.
 100 circ.get_prev_pair(prev_vert, current_edges[i]);
122
1/2
✓ Branch 1 taken 50 times.
✗ Branch 2 not taken.
 50 dest_edges.push_back(prev_e);
123 }
124 // Only true if all edges are in frontier
125 50 success = false;
126
2/2
✓ Branch 1 taken 50 times.
✓ Branch 2 taken 2 times.
 52 }
127
2/2
✓ Branch 0 taken 19 times.
✓ Branch 1 taken 34 times.
2/2
✓ Decision 'true' taken 19 times.
✓ Decision 'false' taken 34 times.
 53 if (success) {
128
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 std::pair<EdgeVec, EdgeVec> p(initial_edges, dest_edges);
129 19 return p;
130 19 } else {
131
1/2
✓ Branch 1 taken 34 times.
✗ Branch 2 not taken.
 34 current_edges = dest_edges;
132
1/2
✓ Branch 1 taken 34 times.
✗ Branch 2 not taken.
 34 dest_edges = {};
133 }
134 34 }
135 21 }
136
137 19 static void partial_rewire(
138 const Vertex &vert, Circuit &circ, EdgeVec &src_edges,
139 EdgeVec &dest_edges) {
140 // move the vertex to the frontier
141 // Notice that if one of the vertex's in edge is already a destination
142 // edge then the circuit::remove_vertex will delete the destination edge
143 // hence circuit::rewire would result in an error due to the missing edge.
144 // We need a partial rewire for that reason.
145 // Example:
146 // Moving the second vertex (CX gate) to the front we only need to rewire
147 // the "x" part.
148 // --o-----
149 // |
150 // --x--x--
151 // |
152 // -----o--
153
154
2/2
✓ Branch 1 taken 39 times.
✓ Branch 2 taken 19 times.
2/2
✓ Decision 'true' taken 39 times.
✓ Decision 'false' taken 19 times.
 58 for (unsigned i = 0; i < dest_edges.size(); i++) {
155 39 Edge &dest_in_edge = dest_edges[i];
156 39 Edge &curr_in_edge = src_edges[i];
157 // If the vertex is already connected to an edge in the frontier, do
158 // nothing.
159
2/2
✓ Branch 1 taken 31 times.
✓ Branch 2 taken 8 times.
2/2
✓ Decision 'true' taken 31 times.
✓ Decision 'false' taken 8 times.
 39 if (dest_in_edge != curr_in_edge) {
160 // Add first edge
161
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 31 Vertex dest_prev_vert = circ.source(dest_in_edge);
162
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 31 circ.add_edge(
163
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 31 {dest_prev_vert, circ.get_source_port(dest_in_edge)},
164
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 31 {vert, circ.get_target_port(curr_in_edge)}, EdgeType::Quantum);
165 // Add second edge
166 Vertex curr_next_vert;
167
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 31 Edge curr_out_edge;
168
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 31 Vertex dest_next_vert = circ.target(dest_in_edge);
169 31 std::tie(curr_next_vert, curr_out_edge) =
170
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 62 circ.get_next_pair(vert, curr_in_edge);
171
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 31 circ.add_edge(
172
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 31 {vert, circ.get_source_port(curr_out_edge)},
173 31 {dest_next_vert, circ.get_target_port(dest_in_edge)},
174
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 31 EdgeType::Quantum);
175 // Add third edge
176
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 31 Vertex curr_prev_vert = circ.source(curr_in_edge);
177
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 31 circ.add_edge(
178
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 31 {curr_prev_vert, circ.get_source_port(curr_in_edge)},
179 31 {curr_next_vert, circ.get_target_port(curr_out_edge)},
180
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 31 EdgeType::Quantum);
181 // Remove edges
182
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 31 circ.remove_edge(dest_in_edge);
183
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 31 circ.remove_edge(curr_in_edge);
184
1/2
✓ Branch 1 taken 31 times.
✗ Branch 2 not taken.
 31 circ.remove_edge(curr_out_edge);
185 }
186 }
187 19 }
188
189 9 bool MultiGateReorder::solve(unsigned max_depth, unsigned max_size) {
190 // Assume the frontier has been advanced
191
192 // store a copy of the original this->mapping_frontier_->quantum_boundray
193 // this object will be updated and reset throughout the procedure
194 // so need to return it to original setting at end.
195
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 unit_vertport_frontier_t copy;
196 9 for (const std::pair<UnitID, VertPort> &pair :
197
4/6
✓ Branch 6 taken 38 times.
✗ Branch 7 not taken.
✓ Branch 9 taken 47 times.
✗ Branch 10 not taken.
✓ Branch 11 taken 38 times.
✓ Branch 12 taken 9 times.
 56 this->mapping_frontier_->linear_boundary->get<TagKey>()) {
198
2/4
✓ Branch 2 taken 38 times.
✗ Branch 3 not taken.
✓ Branch 6 taken 38 times.
✗ Branch 7 not taken.
 38 copy.insert({pair.first, pair.second});
199 }
200 // Get a subcircuit only for iterating vertices
201 Subcircuit circ =
202
1/2
✓ Branch 2 taken 9 times.
✗ Branch 3 not taken.
 9 this->mapping_frontier_->get_frontier_subcircuit(max_depth, max_size);
203
204 // for return value
205 9 bool modification_made = false;
206 // since we assume that the frontier has been advanced
207 // we are certain that any multi-q vert lies after the frontier
208
2/2
✓ Branch 5 taken 48 times.
✓ Branch 6 taken 9 times.
2/2
✓ Decision 'true' taken 48 times.
✓ Decision 'false' taken 9 times.
 57 for (const Vertex &vert : circ.verts) {
209 // Check if the vertex is:
210 // 1. physically permitted
211 // 2. is a multi qubit quantum operation without classical controls
212
5/6
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
✓ Branch 4 taken 41 times.
✓ Branch 5 taken 7 times.
✓ Branch 6 taken 21 times.
✓ Branch 7 taken 27 times.
2/2
✓ Decision 'true' taken 21 times.
✓ Decision 'false' taken 68 times.
 89 if (is_multiq_quantum_gate(this->mapping_frontier_->circuit_, vert) &&
213
2/2
✓ Branch 0 taken 21 times.
✓ Branch 1 taken 20 times.
 41 is_physically_permitted(
214
1/2
✓ Branch 1 taken 41 times.
✗ Branch 2 not taken.
 41 this->mapping_frontier_, this->architecture_, vert)) {
215 std::optional<std::pair<EdgeVec, EdgeVec>> commute_pairs =
216 try_find_commute_edges(
217
1/2
✓ Branch 2 taken 21 times.
✗ Branch 3 not taken.
 21 this->mapping_frontier_->circuit_, this->u_frontier_edges_, vert);
218
219
2/2
✓ Branch 1 taken 19 times.
✓ Branch 2 taken 2 times.
2/2
✓ Decision 'true' taken 19 times.
✓ Decision 'false' taken 2 times.
 21 if (commute_pairs != std::nullopt) {
220 19 modification_made = true;
221
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 partial_rewire(
222 19 vert, this->mapping_frontier_->circuit_, (*commute_pairs).first,
223 19 (*commute_pairs).second);
224 // Update the frontier
225
1/2
✓ Branch 2 taken 19 times.
✗ Branch 3 not taken.
 19 this->mapping_frontier_->advance_frontier_boundary(this->architecture_);
226 this->u_frontier_edges_ =
227
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 38 convert_u_frontier_to_edges(*frontier_convert_vertport_to_edge(
228
1/2
✓ Branch 1 taken 19 times.
✗ Branch 2 not taken.
 19 this->mapping_frontier_->circuit_,
229 57 this->mapping_frontier_->linear_boundary));
230 }
231 21 }
232 }
233 // Return the quantum boundary to its original setting
234
1/2
✓ Branch 2 taken 9 times.
✗ Branch 3 not taken.
 9 this->mapping_frontier_->set_linear_boundary(copy);
235 9 return modification_made;
236 9 }
237
238 8 MultiGateReorderRoutingMethod::MultiGateReorderRoutingMethod(
239 8 unsigned _max_depth, unsigned _max_size)
240 8 : max_depth_(_max_depth), max_size_(_max_size) {}
241
242 4 std::pair<bool, unit_map_t> MultiGateReorderRoutingMethod::routing_method(
243 MappingFrontier_ptr &mapping_frontier,
244 const ArchitecturePtr &architecture) const {
245
1/2
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
 4 MultiGateReorder mr(architecture, mapping_frontier);
246
2/4
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 4 times.
✗ Branch 6 not taken.
 8 return {mr.solve(this->max_depth_, this->max_size_), {}};
247 4 }
248
249 ✗ unsigned MultiGateReorderRoutingMethod::get_max_depth() const {
250 ✗ return this->max_depth_;
251 }
252
253 ✗ unsigned MultiGateReorderRoutingMethod::get_max_size() const {
254 ✗ return this->max_size_;
255 }
256
257 5 nlohmann::json MultiGateReorderRoutingMethod::serialize() const {
258 5 nlohmann::json j;
259
1/2
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 5 j["depth"] = this->max_depth_;
260
1/2
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
 5 j["size"] = this->max_size_;
261
2/4
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 5 times.
✗ Branch 5 not taken.
 5 j["name"] = "MultiGateReorderRoutingMethod";
262 5 return j;
263 }
264
265 4 MultiGateReorderRoutingMethod MultiGateReorderRoutingMethod::deserialize(
266 const nlohmann::json &j) {
267 return MultiGateReorderRoutingMethod(
268 4 j.at("depth").get<unsigned>(), j.at("size").get<unsigned>());
269 }
270
271 } // namespace tket
272