GCC Code Coverage Report

Directory: ./
File: Placement/Placement.cpp
Date: 2022-10-15 05:10:18
Exec Total Coverage
Lines: 157 162 96.9%
Functions: 20 21 95.2%
Branches: 137 258 53.1%
Decisions: 14 16 87.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 "Placement.hpp"
16
17 #include "Utils/HelperFunctions.hpp"
18 #include "Utils/Json.hpp"
19
20 namespace tket {
21
22 // qubit_mapping_t -> std::map<Qubit, Node>
23 // qubit_map_t -> std::map<Qubit, Qubit>
24 // qubit_bimap_t -> boost::bimap<Qubit ArcVertex>
25
26 61 PlacementConfig::PlacementConfig(
27 unsigned _depth_limit, unsigned _max_interaction_edges,
28 unsigned _monomorphism_max_matches, unsigned _arc_contraction_ratio,
29 61 unsigned _timeout)
30 61 : depth_limit(_depth_limit),
31 61 max_interaction_edges(_max_interaction_edges),
32 61 monomorphism_max_matches(_monomorphism_max_matches),
33 61 arc_contraction_ratio(_arc_contraction_ratio),
34 61 timeout(_timeout) {}
35
36 1 bool PlacementConfig::operator==(const PlacementConfig &other) const {
37 2 return (this->depth_limit == other.depth_limit) &&
38
1/2
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
 1 (this->max_interaction_edges == other.max_interaction_edges) &&
39
1/2
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
 1 (this->monomorphism_max_matches == other.monomorphism_max_matches) &&
40
2/4
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 3 (this->arc_contraction_ratio == other.arc_contraction_ratio) &&
41
1/2
✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
 2 (this->timeout == other.timeout);
42 }
43
44 49 void to_json(nlohmann::json &j, const PlacementPtr &placement_ptr) {
45
1/2
✓ Branch 4 taken 49 times.
✗ Branch 5 not taken.
 49 j["architecture"] = placement_ptr->get_architecture_ref();
46
2/2
✓ Branch 0 taken 41 times.
✓ Branch 1 taken 8 times.
2/2
✓ Decision 'true' taken 41 times.
✓ Decision 'false' taken 8 times.
 49 if (std::shared_ptr<GraphPlacement> cast_placer =
47 49 std::dynamic_pointer_cast<GraphPlacement>(placement_ptr)) {
48
2/4
✓ Branch 1 taken 41 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 41 times.
✗ Branch 5 not taken.
 41 j["type"] = "GraphPlacement";
49
2/4
✓ Branch 3 taken 41 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 41 times.
✗ Branch 7 not taken.
 41 j["config"] = cast_placer->get_config();
50
2/2
✓ Branch 0 taken 5 times.
✓ Branch 1 taken 3 times.
2/2
✓ Decision 'true' taken 5 times.
✓ Decision 'false' taken 3 times.
 8 } else if (
51 std::shared_ptr<NoiseAwarePlacement> cast_placer =
52 8 std::dynamic_pointer_cast<NoiseAwarePlacement>(placement_ptr)) {
53
2/4
✓ Branch 1 taken 5 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 5 times.
✗ Branch 5 not taken.
 5 j["type"] = "NoiseAwarePlacement";
54
2/4
✓ Branch 3 taken 5 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 5 times.
✗ Branch 7 not taken.
 5 j["config"] = cast_placer->get_config();
55
2/4
✓ Branch 2 taken 5 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 5 times.
✗ Branch 6 not taken.
 5 j["characterisation"] = cast_placer->characterisation_;
56
2/2
✓ Branch 0 taken 2 times.
✓ Branch 1 taken 1 times.
2/2
✓ Decision 'true' taken 2 times.
✓ Decision 'false' taken 1 times.
 3 } else if (
57 std::shared_ptr<LinePlacement> cast_placer =
58 3 std::dynamic_pointer_cast<LinePlacement>(placement_ptr)) {
59
2/4
✓ Branch 1 taken 2 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 2 times.
✗ Branch 5 not taken.
 2 j["type"] = "LinePlacement";
60 } else {
61
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 1 j["type"] = "Placement";
62 60 }
63 49 }
64
65 4 void from_json(const nlohmann::json &j, PlacementPtr &placement_ptr) {
66
2/4
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
 4 std::string classname = j.at("type").get<std::string>();
67
2/4
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
 4 Architecture arc = j.at("architecture").get<Architecture>();
68
2/2
✓ Branch 1 taken 3 times.
✓ Branch 2 taken 1 times.
2/2
✓ Decision 'true' taken 3 times.
✓ Decision 'false' taken 1 times.
 4 if (classname == "GraphPlacement") {
69
2/4
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 3 times.
✗ Branch 5 not taken.
 3 PlacementConfig config = j.at("config").get<PlacementConfig>();
70
1/2
✓ Branch 1 taken 3 times.
✗ Branch 2 not taken.
 3 placement_ptr = std::make_shared<GraphPlacement>(arc, config);
71
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
1/2
✓ Decision 'true' taken 1 times.
✗ Decision 'false' not taken.
 1 } else if (classname == "NoiseAwarePlacement") {
72
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 1 PlacementConfig config = j.at("config").get<PlacementConfig>();
73 DeviceCharacterisation ch =
74
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 1 j.at("characterisation").get<DeviceCharacterisation>();
75 std::shared_ptr<NoiseAwarePlacement> nap =
76
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 std::make_shared<NoiseAwarePlacement>(arc, config);
77
1/2
✓ Branch 2 taken 1 times.
✗ Branch 3 not taken.
 1 nap->characterisation_ = ch;
78 1 placement_ptr = nap;
79
0/2
✗ Branch 3 not taken.
✗ Branch 4 not taken.
1/2
✗ Decision 'true' not taken.
✓ Decision 'false' taken 1 times.
 1 } else if (classname == "LinePlacement") {
80 ✗ placement_ptr = std::make_shared<LinePlacement>(arc);
81 } else {
82 ✗ placement_ptr = std::make_shared<Placement>(arc);
83 }
84 4 }
85
86 48 void to_json(nlohmann::json &j, const PlacementConfig &config) {
87
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 j["depth_limit"] = config.depth_limit;
88
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 j["max_interaction_edges"] = config.max_interaction_edges;
89
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 j["monomorphism_max_matches"] = config.monomorphism_max_matches;
90
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 j["arc_contraction_ratio"] = config.arc_contraction_ratio;
91
1/2
✓ Branch 2 taken 48 times.
✗ Branch 3 not taken.
 48 j["timeout"] = config.timeout;
92 48 }
93
94 5 void from_json(const nlohmann::json &j, PlacementConfig &config) {
95 5 config.depth_limit = j.at("depth_limit").get<unsigned>();
96 5 config.max_interaction_edges = j.at("max_interaction_edges").get<unsigned>();
97 5 config.monomorphism_max_matches =
98 5 j.at("monomorphism_max_matches").get<unsigned>();
99 5 config.arc_contraction_ratio = j.at("arc_contraction_ratio").get<unsigned>();
100 5 config.timeout = j.at("timeout").get<unsigned>();
101 5 }
102
103 972146 const std::string &Placement::unplaced_reg() {
104 static std::unique_ptr<const std::string> regname =
105
4/8
✓ Branch 0 taken 1 times.
✓ Branch 1 taken 972145 times.
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
✓ Branch 6 taken 1 times.
✗ Branch 7 not taken.
✗ Branch 10 not taken.
✗ Branch 11 not taken.
 972146 std::make_unique<const std::string>("unplaced");
106 972146 return *regname;
107 }
108
109 29565 void fill_partial_mapping(
110 const qubit_vector_t &current_qubits, qubit_mapping_t &partial_mapping) {
111 29565 unsigned up_nu = 0;
112
2/2
✓ Branch 6 taken 1179119 times.
✓ Branch 7 taken 29565 times.
2/2
✓ Decision 'true' taken 1179119 times.
✓ Decision 'false' taken 29565 times.
 1208684 for (Qubit q : current_qubits) {
113
3/4
✓ Branch 2 taken 1179119 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 972080 times.
✓ Branch 6 taken 207039 times.
2/2
✓ Decision 'true' taken 972080 times.
✓ Decision 'false' taken 207039 times.
 1179119 if (partial_mapping.find(q) == partial_mapping.end()) {
114
3/6
✓ Branch 1 taken 972080 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 972080 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 972080 times.
✗ Branch 9 not taken.
 972080 partial_mapping.insert({q, Node(Placement::unplaced_reg(), up_nu)});
115 972080 up_nu++;
116 }
117 1179119 }
118
119
1/2
✗ Branch 3 not taken.
✓ Branch 4 taken 29565 times.
 29565 if (std::any_of(
120 partial_mapping.begin(), partial_mapping.end(),
121 3537357 [&current_qubits](auto x) {
122
1/2
✓ Branch 2 taken 1179119 times.
✗ Branch 3 not taken.
 1179119 return std::find(
123 2358238 current_qubits.begin(), current_qubits.end(), x.first) ==
124 2358238 current_qubits.end();
125 })) {
126 ✗ tket_log()->warn("mapping contains qubits not present in circuit");
127 }
128 29565 }
129
130 // Default placement methods
131 68 bool Placement::place(
132 Circuit &circ_, std::shared_ptr<unit_bimaps_t> maps) const {
133
2/2
✓ Branch 1 taken 66 times.
✓ Branch 2 taken 2 times.
 68 qubit_mapping_t map_ = get_placement_map(circ_);
134
1/2
✓ Branch 2 taken 66 times.
✗ Branch 3 not taken.
 132 return place_with_map(circ_, map_, maps);
135 66 }
136
137 69 bool Placement::place_with_map(
138 Circuit &circ_, qubit_mapping_t &map_,
139 std::shared_ptr<unit_bimaps_t> maps) {
140
1/2
✓ Branch 1 taken 69 times.
✗ Branch 2 not taken.
 69 qubit_vector_t circ_qbs = circ_.all_qubits();
141
1/2
✓ Branch 1 taken 69 times.
✗ Branch 2 not taken.
 69 fill_partial_mapping(circ_qbs, map_);
142
1/2
✓ Branch 1 taken 69 times.
✗ Branch 2 not taken.
 69 bool changed = circ_.rename_units(map_);
143
1/2
✓ Branch 2 taken 69 times.
✗ Branch 3 not taken.
 69 changed |= update_maps(maps, map_, map_);
144 69 return changed;
145 69 }
146
147 4 qubit_mapping_t Placement::get_placement_map(const Circuit &circ_) const {
148 4 qubit_mapping_t out_map;
149
2/4
✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 4 times.
✗ Branch 5 not taken.
 4 fill_partial_mapping(circ_.all_qubits(), out_map);
150 4 return out_map;
151 }
152
153 ✗ std::vector<qubit_mapping_t> Placement::get_all_placement_maps(
154 const Circuit &circ_) const {
155 ✗ return {get_placement_map(circ_)};
156 }
157
158 26 qubit_mapping_t NaivePlacement::get_placement_map(const Circuit &circ_) const {
159
2/4
✓ Branch 2 taken 26 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 26 times.
✗ Branch 6 not taken.
 52 return get_all_placement_maps(circ_).at(0);
160 }
161
162 26 std::vector<qubit_mapping_t> NaivePlacement::get_all_placement_maps(
163 const Circuit &circ_) const {
164 26 qubit_mapping_t placement;
165 26 qubit_vector_t to_place;
166 26 std::vector<Node> placed;
167
168 // Find which/if any qubits need placing
169
3/4
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
✓ Branch 8 taken 127 times.
✓ Branch 9 taken 26 times.
 153 for (const Qubit &q : circ_.all_qubits()) {
170
1/2
✓ Branch 1 taken 127 times.
✗ Branch 2 not taken.
 127 Node n(q);
171
3/4
✓ Branch 1 taken 127 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 27 times.
✓ Branch 4 taken 100 times.
 127 if (!this->arc_.node_exists(n)) {
172
1/2
✓ Branch 1 taken 27 times.
✗ Branch 2 not taken.
 27 to_place.push_back(n);
173 } else {
174
1/2
✓ Branch 1 taken 100 times.
✗ Branch 2 not taken.
 100 placed.push_back(n);
175 // if already placed, make sure qubit retains placement
176
1/2
✓ Branch 2 taken 100 times.
✗ Branch 3 not taken.
 100 placement.insert({n, n});
177 }
178 153 }
179 // avoid doing std::set_difference unless qubits need to be placed
180 26 unsigned n_placed = to_place.size();
181
2/2
✓ Branch 0 taken 6 times.
✓ Branch 1 taken 20 times.
 26 if (n_placed > 0) {
182 6 std::vector<Node> difference,
183
1/2
✓ Branch 1 taken 6 times.
✗ Branch 2 not taken.
 6 architecture_nodes = this->arc_.get_all_nodes_vec();
184
2/4
✓ Branch 2 taken 6 times.
✗ Branch 3 not taken.
✓ Branch 9 taken 6 times.
✗ Branch 10 not taken.
 6 std::set_difference(
185 architecture_nodes.begin(), architecture_nodes.end(), placed.begin(),
186 placed.end(), std::inserter(difference, difference.begin()));
187 // should always be enough remaining qubits to assign unplaced qubits to
188 TKET_ASSERT(difference.size() >= n_placed);
189
2/2
✓ Branch 0 taken 27 times.
✓ Branch 1 taken 6 times.
 33 for (unsigned i = 0; i < n_placed; i++) {
190 // naively assign each qubit to some free node
191
1/2
✓ Branch 4 taken 27 times.
✗ Branch 5 not taken.
 27 placement.insert({to_place[i], difference[i]});
192 }
193 6 }
194
4/8
✓ Branch 1 taken 26 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 26 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 26 times.
✓ Branch 9 taken 26 times.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
 78 return {placement};
195 26 }
196
197 9 qubit_mapping_t LinePlacement::get_placement_map(const Circuit &circ_) const {
198
2/4
✓ Branch 2 taken 9 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 9 times.
✗ Branch 6 not taken.
 18 return get_all_placement_maps(circ_).at(0);
199 }
200
201 9 std::vector<qubit_mapping_t> LinePlacement::get_all_placement_maps(
202 const Circuit &circ_) const {
203 9 qubit_mapping_t partial_map;
204
1/2
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
 9 QubitLineList qb_lines = qubit_lines(circ_);
205
2/2
✓ Branch 1 taken 8 times.
✓ Branch 2 taken 1 times.
 9 if (!qb_lines.empty()) {
206
4/8
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 8 times.
✗ Branch 5 not taken.
✓ Branch 7 taken 8 times.
✗ Branch 8 not taken.
✓ Branch 10 taken 8 times.
✗ Branch 11 not taken.
 8 partial_map = lines_on_arc(arc_, qb_lines, circ_.n_qubits());
207 }
208
2/4
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 9 times.
✗ Branch 5 not taken.
 9 fill_partial_mapping(circ_.all_qubits(), partial_map);
209
4/8
✓ Branch 1 taken 9 times.
✗ Branch 2 not taken.
✓ Branch 5 taken 9 times.
✗ Branch 6 not taken.
✓ Branch 8 taken 9 times.
✓ Branch 9 taken 9 times.
✗ Branch 12 not taken.
✗ Branch 13 not taken.
 27 return {partial_map};
210 9 }
211
212 30 qubit_mapping_t GraphPlacement::get_placement_map(const Circuit &circ_) const {
213 QubitGraph q_graph = monomorph_interaction_graph(
214
2/4
✓ Branch 1 taken 30 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 30 times.
✗ Branch 5 not taken.
 30 circ_, arc_.n_connections(), config_.depth_limit);
215 std::vector<qubit_bimap_t> all_bimaps = monomorphism_edge_break(
216
2/2
✓ Branch 1 taken 29 times.
✓ Branch 2 taken 1 times.
 30 arc_, q_graph, config_.monomorphism_max_matches, config_.timeout);
217
1/2
✓ Branch 2 taken 29 times.
✗ Branch 3 not taken.
 29 qubit_mapping_t out_map = bimap_to_map(all_bimaps[0].left);
218
2/4
✓ Branch 1 taken 29 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 29 times.
✗ Branch 5 not taken.
 29 fill_partial_mapping(circ_.all_qubits(), out_map);
219 58 return out_map;
220 30 }
221
222 1 std::vector<qubit_mapping_t> GraphPlacement::get_all_placement_maps(
223 const Circuit &circ_) const {
224 QubitGraph q_graph = monomorph_interaction_graph(
225
2/4
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 1 times.
✗ Branch 5 not taken.
 1 circ_, arc_.n_connections(), config_.depth_limit);
226 std::vector<qubit_bimap_t> all_bimaps = monomorphism_edge_break(
227
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 arc_, q_graph, config_.monomorphism_max_matches, config_.timeout);
228 1 std::vector<qubit_mapping_t> all_qmaps;
229
1/2
✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
 1 qubit_vector_t all_qbs = circ_.all_qubits();
230
3/4
✓ Branch 4 taken 29388 times.
✗ Branch 5 not taken.
✓ Branch 8 taken 29388 times.
✓ Branch 9 taken 1 times.
 29389 for (qubit_bimap_t bm : all_bimaps) {
231
1/2
✓ Branch 1 taken 29388 times.
✗ Branch 2 not taken.
 29388 qubit_mapping_t qm = bimap_to_map(bm.left);
232
1/2
✓ Branch 1 taken 29388 times.
✗ Branch 2 not taken.
 29388 fill_partial_mapping(all_qbs, qm);
233
1/2
✓ Branch 1 taken 29388 times.
✗ Branch 2 not taken.
 29388 all_qmaps.push_back(qm);
234 29388 }
235 2 return all_qmaps;
236 1 }
237
238 8 qubit_mapping_t NoiseAwarePlacement::get_placement_map(
239 const Circuit &circ_) const {
240
1/2
✓ Branch 3 taken 7 times.
✗ Branch 4 not taken.
 15 return get_all_placement_maps(circ_)[0];
241 }
242
243 8 std::vector<qubit_mapping_t> NoiseAwarePlacement::get_all_placement_maps(
244 const Circuit &circ_) const {
245 // Set up default placements configuation
246 // Place according to configuration
247
1/2
✓ Branch 1 taken 8 times.
✗ Branch 2 not taken.
 8 Monomorpher placer(circ_, arc_, characterisation_, config_);
248
2/2
✓ Branch 1 taken 7 times.
✓ Branch 2 taken 1 times.
 8 std::vector<MapCost> results = placer.place(config_.depth_limit * 2);
249
1/2
✓ Branch 3 taken 7 times.
✗ Branch 4 not taken.
 7 std::sort(results.begin(), results.end());
250 7 std::vector<qubit_mapping_t> output;
251
1/2
✓ Branch 1 taken 7 times.
✗ Branch 2 not taken.
 7 qubit_vector_t all_qbs = circ_.all_qubits();
252
2/2
✓ Branch 5 taken 66 times.
✓ Branch 6 taken 7 times.
 73 for (const MapCost &map_c : results) {
253
1/2
✓ Branch 1 taken 66 times.
✗ Branch 2 not taken.
 66 qubit_mapping_t map_ = map_c.map;
254
1/2
✓ Branch 1 taken 66 times.
✗ Branch 2 not taken.
 66 fill_partial_mapping(all_qbs, map_);
255
1/2
✓ Branch 1 taken 66 times.
✗ Branch 2 not taken.
 66 output.push_back(map_c.map);
256 66 }
257 14 return output;
258 8 }
259
260 } // namespace tket
261