optimized (multi-stitch version) dancing link

Here, I list the pseudocode of this algorithm, I didn’t implement it since it wasn’t critical for my journal…

But If you are required to implement a DL with dynamic working stitches. Hope this piece of code helps you. :)

The basic requirement of “dynamic” is:

• Given a working stitch k in each polygon, the alg construct corresponding coloring rows in the dancing links.

  Note that we need exactly k working stitches instead of # <= k (Since the optimality of DL is constraint by the row order, for example, if one polygon $p$ contains three stitches, then the rows indicating $p$ at beginning should be the coloring solution without working stitch, following is the # of exactly one stitch… and so on

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

def insert_exactly_k_stitches(k):
    for p in parent_node:
        if (|stitches_p| >= k):
            recursive_insert(k,stitches_p,selected_stitches)

def recursive_insert(k,stitches_p,selected_stitches):
	if(k>0):
        for(stitch in stitches_p):
            if(stitch not in selected_stitches): #select the stitch edge which has not been selected (to ensure exactly k different stitches are selected(working))
                stitch = selected_stitches[k-1]  
            	recursive_insert(k-1,stitches_p,selected_stitches)
    else: #k = 0
        #For the layout, one working stitch increase exactly one subcomponnet, therefore, there are pow(3,k+1) rows if we didn't consider the same coloring constarint(such as 1-1-1 for 3 sub-components).
        # For example, given two working stitches, which divide the polygon into three subcomponents, the total possible coloring solution for TPLD should be:
        #0-1-0,0-1-2,0-2-0,0-2-1,1-0-1,1-0-2,1-2-0,1-2-0,2-0-1,2-0-2,2-1-0,2-1-2
        divide the polygon into |selected_stitches| features
        recursive_color(|selected_stitches|, coloring_results)
 
def recursive_color(h,coloring_results):
    if(h>0):
        for(color in possible_colors):
            coloring_results[h-1] = color
            recursive_color(h-1,coloring_results)
    else:
        if the coloring is illegal constraint by selected stitches:
            continue
        #NOTE: here we may not need to remove illegal coloring! Guess why? because it doesn't influence the optimality, only possible efficiency is influenced. Since we certainly call insert_exactly_k_stitches(0), insert_exactly_k_stitches(1), insert_exactly_k_stitches(2)... and so on. If we delete this part, it means that the alg not onlt inserts exactly k stitches, but also working stitches whose number less than k
       	else:
            insert row according to the coloring results

for 循环中新建structure

如果直接用 Structure a = Structure(args)， 这个loop里面的a都是一个address

解决方法：new

1

liwei* a = new liwei(i);

klayout中的那些事

因为openMPL 需要用Klayout处理一些gds的input 所以学了些klayout中的技巧，记录如下。

先吐槽下当代科技的gds有多大：

path to polygon

由Dr.CU 生成的layout 所有feature是以path形式存储的，感谢Haoyu提示klayout有直接转的方法，遂Google，方法如下

• Tools->DRC

• input(x).merged.output(y) 意思就是把x layer merge起来（猜测merge的这个operation就会把path及其相连的path merge成一个poly） 然后输出到 y layer。万幸Dr.CU生成的layer都是固定63，43，22可以用来decomposition（不然我一个一个点一个个放大看真的要吐）

可以看到右下角就是生成的100，101，102 layer了，这时候我们visualize三个layer (后面保存的时候可以选择只保存被visualize的layer)

Flatten cell

layout中的feature其实是以cell为单位分布的，而cell又取自某特定library中（比如加法器就是一种cell，一个layout里面需要多个加法器）Ps：只是我现在的理解。

因此有些gds文件存储cell是以一个指向library的指针存储的（这样不用存储所有poly的各个点坐标了，只要存library中所有cell的具体信息，以及layout中cell的相对位置就可以了）。

现在的OpenMPL暂时不支持这种gds文件，因此需要把所有cell flatten，即不存指针，而是直接存指向的cell本身。

左边 右键 选中flatten cell

选择性保存

gds里面有许多layer用不到，我们选择性保存我们需要的100，101，102

Floorplanning

Floorplanning is typically considered the first stage of VLSI physical design.

• Given a set of hard blocks (whose shapes cannot be changed) and/or soft blocks (whose shapes can be adjusted) and a netlist,
• floorplanning determines the shapes of soft blocks and assembles the blocks into a rectangle (chip)
• so a predefined cost metric (such as the chip area, wire length, wire congestion) is optimized

Placement

Placement is the process of assigning the circuit components into a chip region. (sounds similar with floorplanning?)

• Given a set of fixed cells/macros, a netlist, and a chip outline,
• placement assigns the predesigned cells/macros to positions on the chip
• so that no two cells/macros overlap with each other (i.e., legalization) and some cost functions (e.g., wire length, congestion, and timing) are optimized

Routing

After placement, routing defines the precise paths for conductors that carry electrical signals on the chip layout to interconnect all pins that are electrically equivalent.

Floorplanning

Floorplanning is typically considered the first stage of VLSI physical design.

• Given a set of hard blocks (whose shapes cannot be changed) and/or soft blocks (whose shapes can be adjusted) and a netlist,
• floorplanning determines the shapes of soft blocks and assembles the blocks into a rectangle (chip)
• so a predefined cost metric (such as the chip area, wire length, wire congestion) is optimized

Placement

Placement is the process of assigning the circuit components into a chip region. (sounds similar with floorplanning?)

• Given a set of fixed cells/macros, a netlist, and a chip outline,
• placement assigns the predesigned cells/macros to positions on the chip
• so that no two cells/macros overlap with each other (i.e., legalization) and some cost functions (e.g., wire length, congestion, and timing) are optimized

Routing

After placement, routing defines the precise paths for conductors that carry electrical signals on the chip layout to interconnect all pins that are electrically equivalent.

PyTorch implement Color-GCN中的挫折

Dropout & Long

用Pytorch Implement GCN的时候，有一个error卡了我一天，google也没相关的答案：

1

fused_dropout not implemented for 'long'

自己找了会才发现不是dropout这个value的问题，而是input feature是 long。。。原来torch.Tensor([integer])会默认给int64(Long)而不是int32.。。真是奇怪的feature呢。

Cuda device

1

RuntimeError: Expected object of device type cuda but got device type cpu for argument #2 'mat2' in call to _th_mm

data,features,model全部都cuda()了，结果还是有问题。一个小时后的思索后。本侦探再次破案：

model.cuda() 这个func应该是把所有model中的Tensor 调用一遍 cuda()，大概伪代码就是：

1
2

for Var in model:
	Var.cuda()

但是问题在于！

如果Var不是Tensor 而是一个list（别问为啥会是list，菜鸡最喜欢的就是list）

那么Var.cuda()就失效了，这样就需要在initilize的时候就遍历list里面所有的tensor，并调用tensor.to(‘device’)

Floating point exception (core dumped)

1

Floating point exception (core dumped)

网上查了下 这个就是某一步计算分母为0的error。

但是蛋疼的是 没有指示哪一行有错。而且python（或者说dgl还是pytorch）有个蛋疼的feature是这个exception在还没来得及print的时候就会直接跳出程序。（也就是说还不能用简单的print来定位）

最后用IPython embed()很蠢的一步一步。。发现问题是 如果dgl.Graph没有边(G.number_of_edges == 0)，那么dgl自己的GATConv （Graph Attention Convolution会有问题），因此加了个dirty code判断这个情况，如果属实就直接生成一个zero vector（其实按道理应该是一个input feature itself，但是在这个work里面（graph color)反正没有边的图就没有利用价值，所以直接变成0）

DGL: Trying to create tensor with negative dimension

一步一步抽丝剥茧发现：

当pytorch的unique函数为gpu版本时，最后结果居然是一个dim=-251的vec（但问题在哪并不知道）。

奇怪的是单独写一个py文件用gpu调用这个函数并没有问题，同样的input同样的设备只有放到这个project里面才会return负数dim的vec。

暂时解决方法，将调用这个函数的func(in /dgl/core.py)改到cpu上：

1
2

unique_val = F.asnumpy(F.unique(sorted_val))
unique_val = F.asnumpy(F.unique(sorted_val.cpu()))

最近读了钱穆先生的国史大纲。

其实是抱着拜读加兴趣的想法看的，但是却出乎我的意料：本来以为国史大纲是一本和三国志，史记类似的“史书”，谁知道，竟然真的是“大纲”，像是钱穆先生从文化、政治、经济、社会等各领域出发做的一篇篇演讲稿。又或者像是一篇涵盖computer science所有内容paper里面中的introduction板块。

内容不是很多，几晚上就读完了，恕我愚钝，对于这些领域的研究并不是很感冒，譬如。。。

（wait，刚刚意识到我下的国史大纲只有引论哈哈哈哈哈不行 我说怎么这么短呢哈哈哈哈哈哈哈哈 不行等我下个完整版看完再说）

Graph Isomorphism Network 从数学理论的角度证明了，在验证graph是否同构(isomorphism)上，aggregation based gcn的能力不可能超过WL test。并以此提出了一个简单的graph isomorphism network，实现了能力范围内的最大效果。

本文是对知乎大佬论文解析的补充。

WL test

• The initial label of each node also influences the isomorphism. For example, $G_1$ and $G_2$ are graphs with same structure while $v^i_1,v^i_2$ has different labels, then the two graphs should be determined as non-isomorphism.

Lemma 2

若aggregation based gcn将异构两图map到不同的embedding(即成功分辨为不同构)，则WL test也一定可以将该两图判定为不同构。

该定理为了证明aggregation based gcn的能力不可能超过WL test，其实还有一个是

若aggregation based gcn将同构两图map到相同的embedding(即成功分辨为同构)，则WL test也一定可以将该两图判定为同构。

但这个是obvious的。。。

大概证明思路。

想象存在这样的两个异构图，使得gcn的embedding不一样，而WL test最后也无法判定（即最后output node label multiset 也一样）。

那么我们可以从WL无法判定的方向证明:

证明若WL 第i层node label一样，则gcn 第i层 node feature也肯定一样。

这个证明通过归纳法推得。

和yuzhe讨论了下一个我看来奇怪的attention公式

$e_{ij}= a^T * [h_i||h_j]$

这里的$e_{ij}$ 代表the importance between meta-path based node pairs (即两点i对j的重要性), $||$是concat符号。$h_i$代表点i的feature，$a$即为 attention vector （trainable）

但是这样的e能代表的重要性关系其实为：

• $a_0 * h_i$ 越大，代表点i“重要性”越大，即不分相对关系，不管你是j1，j2还是j3，对于i1，i2，只要$a_0 * h_{i1}>a_0 * h_{i2}$,，则 $e_{i1j} > e_{i2j}$。不论j是哪个点。但这真的能代表某些网络间的attention关系吗？

后面又看了google的那篇 what you need is attention，明显可解释性就强多了。

UPDATE:

DAmn, 这个bug被比我聪明的人发paper了

HOW ATTENTIVE ARE GRAPH ATTENTION NETWORKS?

https://arxiv.org/pdf/2105.14491.pdf