三月过去了一半，整个二月，包括这已经过去的三月，都是颓颓的在宿舍度过的。这段时间每天做些什么呢？

十点多迷迷糊糊起床，玩手机到十二点，然后煮饭吃饭到了下午两点，稍微刷下虎扑知乎加写下代码，哦豁又要吃晚饭了。晚饭一过，就是各种娱乐活动了，913吃鸡，之前的剧本杀，现在的冬日计划，还有打了好几遍的三国志。。。

发现脑子这个东西还是得经常用经常转。之前划水的时候以到下午头晕的不行，但是有天强逼着自己学习写code，居然就不晕了。呵呵，我这叫做富贵病吗？

感觉不能这么浪费自己生命了，至少白天不能再手机综合征下去了。（其实颓的很大一个原因，是真的眼前这个OpenMPL的coding太过烦人，不过索性最终还是在今晚解决了，希望以后可以更有朝气的做接下来的许多许多事情。）

工作方面就是这样，说起来随着疫情的严重，intern的日期可能也需要变化，可能要推迟到下学期？不知道，但总之得尽快和老板确定。什么时候确定？等我openmpl搞定后才有底气说吧：毕竟确实划了太久水。

发现自己现在是个看得很开的人，不管是感情还是事业。有点命中有时终须有,命里无时莫强求的想法在三观里了，很多东西不太愿意投入太多的热情和希望，可能是害怕失败后的失望？不论好坏，但至少大部分事物不会让我捶胸顿足，喟然叹息，感觉也是成熟的一个小小标志吧。

最近唯一让我有点情绪的是妹妹的事。和妹妹视频，五岁的小孩子一句话不说，然后眼泪就流了出来。这么小就有了难以承受的心事，这么小就得寄人篱下 没有父母的照顾，这么小就眼泪憋不住的无声的流。看着真的揪心难受，既然选择了做父母，为什么就只管生不管养呢。不希望她重蹈我的覆辙，她这么可爱 ，这么漂亮，她值得拥有自己人生的幸福。

不过家家有本难念的经。我为我妹妹的人生叹息，我爸的人生也活得挺糟糕：生意上的不顺、女儿的身疾，都让这个中年人压着担子。哎，他的担子何尝不是我的担子呢。

今天忽然看到詹青云是12届的CU本科生，忽然惊了一下，想到自己14年入学的时候唯一报名的国辩队，没准当时她也在台上。然后觉得自己的青春这一点上挺可惜的，唯一报名的原因是确实当时只对这个有浓厚的兴趣，但是碍于懒惰，碍于一般家庭出生的短视，碍于自己的懦弱，最终还是没有去参加复试。也许参加了会有很多全新的体验、很多新的朋友、自己的思想也能系统化、逻辑化，对自己人生规划也会健全很多。

不过往者不可谏，来者犹可追。未来可能还会有这种辩论的机会（哈哈，不过就算有机会，也没有时间去准备、去充实自己了吧？），再不济，其他喜欢的东西一定要去追求一下。Follow your heart。

药效好像快到了，得睡了，晚安。Neway。前几天那个超大月亮确实很大，希望未来的某天你再看到月亮的时候，你找到了那个爱你的人。

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也肯定一样。

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