Cell Mapping
TL;DR:
CellMapping
在构造一个等价关系表, 从而在对Layout
进行拷贝或对比时能够避免不必要的新Cell
的生成, 从而直接将src_layout
中的Cell
直接拷贝/比较dst_layout
中的Cell
.
为了缩减非重点代码, 以及简化写法, 文中涉及代码可能通过C++11以上的特性或直接进行简写, 与源代码不一致. 总之就是因为个人喜好, 有关 Klayout 的源码会有所变动.
简介
在 Klayout 中通常有如下三种情况来创建两 Layout
间的 CellMapping
:
create_single_mapping_full
: 只连接给定的两个Cell
,src_layout
的其余子Cell
会直接与dst_layout
中创建的新Cell
相连接create_from_names_full
: 连接给定的两个Cell
, 对于src_layout
的其余子Cell
会试图与dst_layout
中同名的Cell
相连接, 剩余Cell
同样与新创建的Cell
相连接create_from_geometry_full
: 连接给定的两个Cell
, 对于src_layout
的其余子Cell
会试图与dst_layout
同路径同累积变换的Cell
相连接, 剩余Cell
同样与新创建的Cell
相连接
create_single_mapping_full
真的很简单, 不信看下面源码
1
2
3
4
5
6
7
void
CellMapping::create_single_mapping (const db::Layout & /*layout_a*/, db::cell_index_type cell_index_a, const db::Layout & /*layout_b*/, db::cell_index_type cell_index_b)
{
clear ();
// 简单建立映射关系, 剩下的全都当 missing part 的处理
map (cell_index_b, cell_index_a);
}
create_from_names_full
此处逻辑也较为简单, 不过应该避免混淆 Cell::collect_called_cells
与 Cell::collect_caller_cells
. 前者 DFS 搜集所有的子 Cell(注意是 Cell 而非 instance), 后者向上收集所有父 Cell.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void
CellMapping::create_from_names (const db::Layout &layout_a, db::cell_index_type cell_index_a, const db::Layout &layout_b, db::cell_index_type cell_index_b)
{
clear ();
std::set<db::cell_index_type> called_b;
layout_b.cell (cell_index_b).collect_called_cells (called_b);
map (cell_index_b, cell_index_a);
// 遍历 cell_b 下所有子 Cell, 如果在 layout_a 中能找到同名 Cell 也进行映射
for (auto const &cell_b_index : called_b) {
std::pair<bool, db::cell_index_type> ac = layout_a.cell_by_name (layout_b.cell_name (cell_b_index));
if (ac.first) {
map (cell_b_index, ac.second);
}
}
}
create_from_geometry_full
逻辑异常复杂, 涉及到的机制也异常多, 需要非常熟悉 Klayout 基本 db, 包括各个类之间的存储关系等等, 因此需要先具备一些知识储备
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
void
CellMapping::create_from_geometry (const db::Layout &layout_a, db::cell_index_type cell_index_a, const db::Layout &layout_b, db::cell_index_type cell_index_b)
{
tl::SelfTimer timer (tl::verbosity () >= 31, tl::to_string (tr ("Cell mapping")));
if (tl::verbosity () >= 40) {
tl::info << "Cell mapping - first step: mapping instance count and instance identity";
}
clear ();
db::CellCounter cc_a (&layout_a, cell_index_a);
db::CellCounter cc_b (&layout_b, cell_index_b);
std::multimap<size_t, db::cell_index_type> cm_b;
for (auto const &cell_index : cc_b) {
cm_b.insert (std::make_pair (cell_index == cell_index_b ? 0 : cc_b.weight (cell_index), cell_index));
}
std::multimap<size_t, db::cell_index_type> cm_a;
for (auto const &cell_index : cc_a) {
cm_a.insert (std::make_pair (cell_index == cell_index_a ? 0 : cc_a.weight (cell_index), cell_index));
}
std::map <db::cell_index_type, std::vector<db::cell_index_type> > candidates; // key = index(a), value = indices(b)
InstanceSetCompareFunction cmp (layout_a, cell_index_a, layout_b, cell_index_b);
std::multimap<size_t, db::cell_index_type>::const_iterator a = cm_a.begin (), b = cm_b.begin ();
while (a != cm_a.end () && b != cm_b.end ()) { // mapping the same-weight cell, from layout_a to layout_b
size_t w = a->first;
while (b != cm_b.end () && b->first < w) { // 双指针快速找 instance 数量相同的 cell
++b;
}
if (b == cm_b.end ()) {
break;
} else if (b->first > w) { // 含义为 cell: a->second 对应的相同来自 b 的 cell 队列为空
candidates.insert (std::make_pair (a->second, std::vector<db::cell_index_type> ()));
++a;
} else { // weight(cell_a) == weight(cell_b)
if (tl::verbosity () >= 50) { // 正如 debug 信息,这是一个多对多的映射处理,处理内容为相同的 instance count
size_t na = 0, nb = 0;
for (auto aa = a; aa != cm_a.end () && aa->first == w; ++aa) {
++na;
}
for (auto bb = b; bb != cm_b.end () && bb->first == w; ++bb) {
++nb;
}
tl::info << "Multiplicity group (" << w << " instances) - " << na << " vs. " << nb << " cells";
}
unsigned int g = 0; // 可以视作每个处理区间内的 index ?
std::map <unsigned int, std::vector <db::cell_index_type> > b_group;
std::map <db::cell_index_type, unsigned int> b_group_of_cell; // 记录 cell_b 对应索引 g,类似 cache 作用
while (a != cm_a.end () && a->first == w) { // 确保没有步进 set_a,
candidates.insert (std::make_pair (a->second, std::vector <db::cell_index_type> ())); // a new entry
std::set <unsigned int> groups_taken;
std::multimap<size_t, db::cell_index_type>::const_iterator bb = b;
while (bb != cm_b.end () && bb->first == w) { // start do real calculation, current calculation interval
std::map <db::cell_index_type, unsigned int>::const_iterator bg = b_group_of_cell.find (bb->second);
if (bg != b_group_of_cell.end ()) { // already been calculated
if (groups_taken.find (bg->second) == groups_taken.end ()) { // if current groups has not been selected yet
if (cmp.compare (a->second, cc_a.selection (), bb->second, cc_b.selection ())) { // a->second equals bb->second
candidates [a->second] = b_group [bg->second]; // overwrite the candidates, 存在重复相同的应当覆盖
groups_taken.insert (bg->second);
}
}
} else { // list_a 与 list_b 进行匹配时,第一轮遍历 list_b 产生新 candidate
// 实质此处产生的对应关系如果在当前 weight 情况下不再经过上述 if 分支,则已经认为是一一映射
if (cmp.compare (a->second, cc_a.selection (), bb->second, cc_b.selection ())) { // a->second equals bb->second
candidates [a->second].push_back (bb->second); // add more candidates
b_group_of_cell.insert (std::make_pair (bb->second, g));
// 无语,b_group[g].push_back(bb->second) 不行吗
b_group.insert (std::make_pair (g, std::vector <db::cell_index_type> ())).first->second.push_back (bb->second);
}
}
++bb;
}
if (tl::verbosity () >= 60) {
tl::info << "Checked cell " << layout_a.cell_name (a->second) << ": " << candidates [a->second].size () << " candidates remaining.";
}
++a; // a 与 g 同步步进,意味着在每个处理区间内,可以视作 a 与 g 之间一一映射
++g; // 即,我们可以通过索引 g 来得知目前处理的是当前区间内的第几个 cell_a
}
while (b != cm_b.end () && b->second == w) { // 处理完当前 cell_b 步进 set_b
++b;
}
}
}
while (a != cm_a.end ()) { // collect remaining cell in set_a
candidates.insert (std::make_pair (a->second, std::vector<db::cell_index_type> ()));
++a;
}
if (tl::verbosity () >= 60) {
tl::info << "Mapping candidates:";
dump_mapping (candidates, layout_a, layout_b);
}
// extract one vs one mapping to m_b2a_mapping
for (std::map <db::cell_index_type, std::vector<db::cell_index_type> >::const_iterator cand = candidates.begin (); cand != candidates.end (); ++cand) {
extract_unique (cand, m_b2a_mapping, layout_a, layout_b);
}
int iteration = 0;
bool reduction = true;
while (reduction) {
reduction = false;
++iteration;
if (tl::verbosity () >= 40) {
tl::info << "Cell mapping - iteration " << iteration << ": cross-instance cone reduction";
}
// This map stores that layout_b cells with the corresponding layout_a cell for such cells which
// have their mapping reduced to a unique one
std::map <db::cell_index_type, std::pair<db::cell_index_type, int> > unique_candidates;
std::vector<db::cell_index_type> refined_cand;
for (std::map <db::cell_index_type, std::vector<db::cell_index_type> >::iterator cand = candidates.begin (); cand != candidates.end (); ++cand) {
if (cand->second.size () > 1) { // process the multiple mapping cases, since the 1 vs 1(unique) mapping cases have already processed
refined_cand.clear ();
refined_cand.insert (refined_cand.end (), cand->second.begin (), cand->second.end ());
if (tl::verbosity () >= 70) {
tl::info << "--- Cell: " << layout_a.cell_name (cand->first);
tl::info << "Before reduction: " << tl::noendl;
for (size_t i = 0; i < refined_cand.size (); ++i) {
tl::info << " " << layout_b.cell_name(refined_cand[i]) << tl::noendl;
}
tl::info << "";
}
std::set<db::cell_index_type> callers;
layout_a.cell (cand->first).collect_caller_cells (callers, cc_a.selection (), -1);
for (std::set<db::cell_index_type>::const_iterator c = callers.begin (); c != callers.end () && refined_cand.size () > 0; ++c) {
if (*c != cell_index_a) {
const std::vector<db::cell_index_type> &others = candidates.find (*c)->second;
if (others.size () == 1) {
std::set<db::cell_index_type> cross_cone_b;
layout_b.cell (others.front ()).collect_called_cells (cross_cone_b);
std::vector<db::cell_index_type>::iterator cout = refined_cand.begin ();
for (std::vector<db::cell_index_type>::const_iterator cc = refined_cand.begin (); cc != refined_cand.end (); ++cc) {
if (cross_cone_b.find (*cc) != cross_cone_b.end ()) {
*cout++ = *cc;
}
}
if (tl::verbosity () >= 70 && cout != refined_cand.end ()) {
tl::info << "Reduction because of caller mapping: " << layout_a.cell_name (*c) << " <-> " << layout_b.cell_name (others[0]);
tl::info << " -> " << tl::noendl;
for (size_t i = 0; i < size_t (cout - refined_cand.begin ()); ++i) {
tl::info << " " << layout_b.cell_name(refined_cand[i]) << tl::noendl;
}
tl::info << "";
}
refined_cand.erase (cout, refined_cand.end ());
}
}
}
if (refined_cand.size () > 0) {
std::set<db::cell_index_type> called;
layout_a.cell (cand->first).collect_called_cells (called);
for (std::set<db::cell_index_type>::const_iterator c = called.begin (); c != called.end () && refined_cand.size () > 0; ++c) {
const std::vector<db::cell_index_type> &others = candidates.find (*c)->second;
if (others.size () == 1) {
std::set<db::cell_index_type> cross_cone_b;
layout_b.cell (others.front ()).collect_caller_cells (cross_cone_b, cc_b.selection (), -1);
std::vector<db::cell_index_type>::iterator cout = refined_cand.begin ();
for (std::vector<db::cell_index_type>::const_iterator cc = refined_cand.begin (); cc != refined_cand.end (); ++cc) {
if (cross_cone_b.find (*cc) != cross_cone_b.end ()) {
*cout++ = *cc;
}
}
if (tl::verbosity () >= 70 && cout != refined_cand.end ()) {
tl::info << "Reduction because of callee mapping: " << layout_a.cell_name (*c) << " <-> " << layout_b.cell_name (others[0]);
tl::info << " -> " << tl::noendl;
for (size_t i = 0; i < size_t (cout - refined_cand.begin ()); ++i) {
tl::info << " " << layout_b.cell_name(refined_cand[i]) << tl::noendl;
}
tl::info << "";
}
refined_cand.erase (cout, refined_cand.end ());
}
}
if (refined_cand.size () == 1) {
// The remaining cell is a candidate for layout_b to layout_a mapping
db::cell_index_type cb = refined_cand[0];
db::cell_index_type ca = cand->first;
std::map <db::cell_index_type, std::pair<db::cell_index_type, int> >::iterator uc = unique_candidates.find (cb);
if (uc != unique_candidates.end ()) {
if (uc->second.first != ca) {
int ed = tl::edit_distance (layout_a.cell_name (ca), layout_b.cell_name (cb));
if (ed < uc->second.second) {
uc->second = std::make_pair (ca, ed);
if (tl::verbosity () >= 60) {
tl::info << "Choosing " << layout_b.cell_name (cb) << " (layout_b) as new unique mapping for " << layout_a.cell_name (ca) << " (layout_a)";
}
}
}
} else {
int ed = tl::edit_distance (layout_a.cell_name (ca), layout_b.cell_name (cb));
unique_candidates.insert (std::make_pair (cb, std::make_pair (ca, ed)));
if (tl::verbosity () >= 60) {
tl::info << "Choosing " << layout_b.cell_name (cb) << " (layout_b) as unique mapping for " << layout_a.cell_name (ca) << " (layout_a)";
}
}
}
}
}
}
// realize the proposed unique mapping
for (std::map <db::cell_index_type, std::pair<db::cell_index_type, int> >::const_iterator uc = unique_candidates.begin (); uc != unique_candidates.end (); ++uc) {
std::map <db::cell_index_type, std::vector<db::cell_index_type> >::iterator cand = candidates.find (uc->second.first);
tl_assert (cand != candidates.end ());
cand->second.clear ();
cand->second.push_back (uc->first);
reduction = true;
extract_unique (cand, m_b2a_mapping, layout_a, layout_b);
}
if (tl::verbosity () >= 60) {
tl::info << "Further refined candidates:";
dump_mapping (candidates, layout_a, layout_b);
}
if (tl::verbosity () >= 40) {
tl::info << "Cell mapping - iteration " << iteration << ": removal of uniquely mapped cells on B side";
}
for (std::map <db::cell_index_type, std::vector<db::cell_index_type> >::iterator cand = candidates.begin (); cand != candidates.end (); ++cand) {
if (cand->second.size () > 1) {
std::vector<db::cell_index_type> refined_cand;
for (std::vector<db::cell_index_type>::const_iterator c = cand->second.begin (); c != cand->second.end (); ++c) {
std::map<db::cell_index_type, db::cell_index_type>::const_iterator um = m_b2a_mapping.find (*c);
if (um == m_b2a_mapping.end () || um->second == cand->first) {
refined_cand.push_back (*c);
}
}
if (refined_cand.size () < cand->second.size ()) {
reduction = true;
cand->second.swap (refined_cand);
extract_unique (cand, m_b2a_mapping, layout_a, layout_b);
}
}
}
if (tl::verbosity () >= 60) {
tl::info << "After reduction of mapped cells on b side:";
dump_mapping (candidates, layout_a, layout_b);
}
}
if (tl::verbosity () >= 40) {
int total = 0;
int not_mapped = 0;
int unique = 0;
int non_unique = 0;
int alternatives = 0;
for (std::map <db::cell_index_type, std::vector<db::cell_index_type> >::iterator cand = candidates.begin (); cand != candidates.end (); ++cand) {
++total;
if (cand->second.size () == 0) {
++not_mapped;
} else if (cand->second.size () == 1) {
++unique;
} else {
++non_unique;
alternatives += (int) cand->second.size ();
}
}
tl::info << "Geometry mapping statistics:";
tl::info << " Total cells = " << total;
tl::info << " Not mapped = " << not_mapped;
tl::info << " Unique = " << unique;
tl::info << " Non unique = " << non_unique << " (total " << alternatives << " of alternatives)";
}
// Resolve mapping according to string match
if (tl::verbosity () >= 40) {
tl::info << "Cell mapping - string mapping as last resort";
}
for (std::map <db::cell_index_type, std::vector<db::cell_index_type> >::iterator cand = candidates.begin (); cand != candidates.end (); ++cand) {
if (cand->second.size () > 1) {
std::string cn_a (layout_a.cell_name (cand->first));
int min_ed = std::numeric_limits<int>::max ();
db::cell_index_type min_ed_ci;
for (std::vector<db::cell_index_type>::const_iterator c = cand->second.begin (); c != cand->second.end (); ++c) {
if (m_b2a_mapping.find (*c) == m_b2a_mapping.end ()) {
int ed = tl::edit_distance (cn_a, layout_b.cell_name (*c));
if (ed < min_ed) {
min_ed = ed;
min_ed_ci = *c;
}
}
}
cand->second.clear ();
if (min_ed < std::numeric_limits<int>::max ()) {
cand->second.push_back (min_ed_ci);
extract_unique (cand, m_b2a_mapping, layout_a, layout_b);
}
}
}
if (tl::verbosity () >= 40) {
int total = 0;
int not_mapped = 0;
int unique = 0;
int non_unique = 0;
int alternatives = 0;
for (std::map <db::cell_index_type, std::vector<db::cell_index_type> >::iterator cand = candidates.begin (); cand != candidates.end (); ++cand) {
++total;
if (cand->second.size () == 0) {
if (tl::verbosity () >= 50) {
tl::info << "Unmapped cell: " << layout_a.cell_name (cand->first);
}
++not_mapped;
} else if (cand->second.size () == 1) {
++unique;
} else {
++non_unique;
alternatives += (int) cand->second.size ();
}
}
tl::info << "Final mapping statistics:";
tl::info << " Total cells = " << total;
tl::info << " Not mapped = " << not_mapped;
tl::info << " Unique = " << unique;
tl::info << " Non unique = " << non_unique << " (total " << alternatives << " of alternatives)";
}
}
This post is licensed under CC BY 4.0 by the author.