If you prefer reading in English, there is a magical switch on the top-right corner.

本网站没有使用Python。

问题

给定一个棋盘格局，找出所有的威胁点。威胁点是指双方各自落子后能形成必胜局面的点，例如冲四的一端（必胜，落子后立刻形成五子连珠）、活三的两端（落子后形成活四，若对方此步不胜则下一回合必胜）。例如下面这个棋盘中标“x”的位置。

┌┬┬┬┬┬┬┬┬┬┬┬┬┬┐

├┼┼┼┼┼┼┼┼┼┼┼┼┼┤

├┼┼┼┼┼┼┼┼┼┼┼┼┼┤

├┼┼┼┼┼┼┼┼┼┼┼┼┼┤

├┼┼┼┼┼┼┼┼┼┼┼┼┼┤

├┼┼┼┼┼┼┼┼┼┼x┼┼┤

├┼┼┼┼┼┼┼┼┼●┼┼┼┤

├┼┼┼x○○○○●┼┼┼┼┤

├┼┼┼┼┼┼┼●┼┼┼┼┼┤

├┼┼┼┼┼┼x┼┼┼┼┼┼┤

├┼┼┼┼┼┼┼┼┼┼┼┼┼┤

├┼┼┼┼┼┼┼┼┼┼┼┼┼┤

├┼┼┼┼┼┼┼┼┼┼┼┼┼┤

├┼┼┼┼┼┼┼┼┼┼┼┼┼┤

└┴┴┴┴┴┴┴┴┴┴┴┴┴┘

在AI程序的搜索中，如果出现这些威胁点，必须快速找到，以便裁剪掉其他着法。 因为有威胁点时仍着于其他位置总会导致不利。

朴素方法

简单的解决方法是按照规则进行遍历。我相信大部分人初次上手编写程序都是这样解决的，我也一样，毕竟过早优化是万恶之源。 但是最终你会发现这一过程的速度对AI的表现而言是至关重要的。

首先容易想到的解决方案是向量化。 用位棋盘（bitboard）作格局表示，将棋盘分为黑、白两盘，每一盘都是225个比特，可以装在uint16_t [16]中，或一个YMM寄存器__m256i中。 通过_mm256_slli_epi16/_mm256_srli_epi16（VPSLLW/VPSRLW）等向量指令对整个棋盘进行移动、对齐，然后进行逻辑与，寻找活四、冲四、活三。 这样节省了遍历盘面的开销，但由于棋形复杂（冲四、活三都不一定是连续的，可能有眼），程序并不简单，仍然需要比较长时间。

三进制编码

2014年，我独立发现了一个解决方法，并运用于kalscope第二版“Dolanaar”起的评估函数中。 这个程序是我本科时练习调优的习作，但也在当时取得了不错的棋力。

我将棋盘的每条阳线（横向、纵向的线）分开看待。 一条阳线上有15格，我将一行上所有可能的格局都列出，提前计算威胁点，形成查找表。 但是以位棋盘表示的话，一条阳线的编码可达，对应查找表尺寸达到2 GB。 注意到位棋盘编码中有大量冗余，以2比特编码了3种情况：空“┼”0b00、白子“○”0b01、黑子“●”0b10，而0b11是非法的。 要实现紧凑编码，需要采用三进制计数，0表示空，1表示白子，2表示黑子，每个三进制位表示一个格子。

进制转换涉及大量除模运算，由二进制位棋盘转三进制开销大，是不现实的。 注意到棋盘格局并非突然出现，而是总由空棋盘逐步落子形成，三进制表示可以增量维护。 空棋盘编码为0；在第位落白子，即编码加；在第位落黑子，即编码加。搜索过程中进行回退，则将增加的编码重新减去。 要高效实现，只需另记一个三的各幂次查找表power3。

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

constexpr int power3[16] {
 1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049, 177147, 531441, 1594323, 4782969, 14348907
};
int triboard_h[15] {};
int triboard_v[15] {};
uint16_t threat_lut[14348907] { ... }; // pre-generated.

void make(int x, int y, int color) {
    triboard_h[y] += power3[x] << color;
    triboard_v[x] += power3[y] << color;
}
void unmake(int x, int y, int color) {
    triboard_h[y] -= power3[x] << color;
    triboard_v[x] -= power3[y] << color;
}
void find_threat() {
    for (int y = 0; y < 15; y++) {
        uint16_t threat = threat_lut[triboard_h[y]];
        while (threat) {
            int x = std::countr_zero(threat);

            // do something to the threat (x,y).

            threat &= threat - 1;
        }
    }
    // another loop for vertical lines.
    // TODO: how about diagonal / anti-diagonal lines?
}

查找表threat_lut紧密编码了15格阳线的所有可能格局，仅占据27.4 MB内存。

这个方法为标准15路棋盘设计，但彼时Gomocup规则是20路棋盘，导致这个方法无效，不然当时可能我也会去参赛。 我不确定是否有其他人率先发现了类似方法，不过我确实注意到最近赢下Gomocup大赛冠军的Rapfi也在程序的一些地方使用了这一技巧。

这个方法不完美。它只适用于固定15格的阳线，用在Gomocup的20格规则就会导致查找表过大。 另外，阴线（对角、反对角线）每一条都有不同长度，如果生硬套用15格阳线的查找表会导致误报。例如在总长度只有4格的阴线上，即使形成活三也不构成威胁，因为棋盘边界会自然堵截它。这该如何处理？

十年前的我没有给出答案，留下一个未解难题。

偏斜三进制编码

去年，我指导博士研究生郭泓锐完成了Cambricon-U，采用偏斜二进制编码实现了在SRAM中原位计数的功能。 偏斜记数法不仅可以用于二进制，也可用于三进制，解决上述三进制编码遗留的阴线表示问题。

偏斜三进制允许数位中暂时存在一个“3”而不向前进位。 计数时，如果各数位中不存在“3”，则将最低位递增1； 如果各数位中存在“3”，将“3”归零并向前进位。 在这样的计数规则下，容易发现偏斜三进制存在以下两项性质：

• 各数位上最多存在一个“3”；
• 如果存在“3”，在“3”的右侧各位（更低位）一定全都是“0”。

我们以“0”表示空格，“1”表示白子，“2”表示黑子，“3”表示棋盘边界，即可自然而紧凑地将各种长度的阴线编入到查找表中。 阴线的长度不满15格时，只使用高位，将边界置“3”，更低位置“0”。 查找表内各项按照偏斜三进制计数顺序编纂：

该查找表共21523359项，紧密地编码了15格阳线和1到15格的所有阴线的各种格局，占41.1 MB内存。 使用方法稍加改动即可，将三进制位权重power3改为偏斜三进制位权重basesk3，该数列为OEIS A261547。

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

constexpr int basesk3[16] {
    1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484, 7174453, 21523360
};
int sk3board_h[15] {};
int sk3board_v[15] {};
int sk3board_d[29] {};
int sk3board_a[29] {};
uint16_t threat_lut[21523359] { ... }; // pre-generated.
   
// set board bounds on init. 
void init() {
    for (int i = 0; i < 15; i++) {
        sk3board_d[i] = basesk3[13-i] * 3;
        sk3board_a[i] = basesk3[13-i] * 3;
    }
    for (int i = 15; i < 29; i++)
        sk3board_d[i] = basesk3[i-15] * 3;
        sk3board_a[i] = basesk3[i-15] * 3;
    }
}

void make(int x, int y, int color) {
    sk3board_h[y]      += basesk3[x]             << color;
    sk3board_v[x]      += basesk3[y]             << color;
    sk3board_d[14-x+y] += basesk3[x<y?y:x]       << color;
    sk3board_a[x+y]    += basesk3[x+y<15?14-y:x] << color;
}
void unmake(int x, int y, int color) {
    sk3board_h[y]      -= basesk3[x]             << color;
    sk3board_v[x]      -= basesk3[y]             << color;
    sk3board_d[14-x+y] -= basesk3[x<y?y:x]       << color;
    sk3board_a[x+y]    -= basesk3[x+y<15?14-y:x] << color;
}
void find_threat() {
    for (int y = 0; y < 15; y++) {
        uint16_t threat = threat_lut[sk3board_h[y]];
        while (threat) {
            int x = std::countr_zero(threat);

            // do something to the threat (x,y).

            threat &= threat - 1;
        }
    }
    // to process vertical, diagonal and anti-diagonal lines
}

这样，我们就将相当繁琐的威胁点检查问题完全转化成了增量维护四个方向的棋盘表示，然后进行表项查找。41 MB左右的查找表如今能够完全存放在L3缓存当中，可想而知速度是极快的。 上述示例中，find_threat还可以进一步向量化，乃至整个操作的开销可压缩至约百余个时钟周期。

同样的思路可以用于获胜检查、评价函数等。如果你准备使用类AlphaGo的架构，不妨尝试将神经网络第一层改为沿阴阳四线进行的一维卷积，用此方法可以直接以查找取代第一层卷积运算。

本文是续在Cambricon-U之后的短小随想。

RIM体现了我们作为并不研究存内计算的研究者，对于存内计算的新认识。 提到存内计算概念，人们直觉上首先与冯·诺依曼瓶颈联系起来，并认为存内计算当然是解决瓶颈的不二法门。 除了业余的计算机科学爱好者，也不乏专业的研究者以这种口径撰写各类材料。

这是错误的。

在RIM的心路历程中，我们展示了过去的存内计算缘何不能支持计数，而计数（后继运算）乃是皮亚诺算术系统中的公理元素，是算术之基础。 我们通过取巧的办法，利用了一种体系结构领域学者并不熟悉的记数法，才首次实现了存内计算的计数功能。 但是这种取巧只能取一次，无情的自然不会允许我们第二次取巧成功，因为想要在电路中同时高效实现加法和乘法的记数法已被证明不存在*。

计算需要信息的流动，而存内计算要求它们呆在原地，这天然是矛盾的。 结合姚先生的结论，我们恐怕无法真正在一个存储阵列中高效地原位完成冯·诺伊曼机所需的各类计算。 让我预测的话，存内计算永远不会和冯·诺依曼瓶颈真正产生关系。

* Andrew C. Yao. 1981. The entropic limitations on VLSI computations (Extended Abstract). STOC’81. [DOI]

在MICRO 2023大会上，我们展示发明了一种新型存内计算器件“随机自增存储器（RIM）”，并将其应用于随机计算（一进制计算）架构中。

在学术界，存内计算是当前火热的研究领域，常被研究者寄予突破冯·诺依曼瓶颈、实现计算机体系结构大变革的美好期望。 但目前，存内计算这一概念的涵义却逐渐收敛于特指采用忆阻器、阻变存储器（ReRAM）等新材料、新器件完成矩阵计算这种特定计算功能。 在2023年，在我们这些原来并不研究存内计算的外行研究者看来，存内计算发展到了一个很奇怪的境地：已经发展出的存内计算设备能够很好地处理神经网络、功能类比大脑，却仍然无法做诸如计数、加法这样最基础的运算。 在Cambricon-Q的研究中，我们留下了一个遗憾：我们设计了NDPO在近存端完成权重更新，却无法做到真正的存内累加，因此被评阅人批评“只能称为近存计算，而非存内计算”。 由此，我们开始了对于如何在存储器内完成原位累加的思考。

我们很快意识到，如果采用二进制记数，加法是很难在存储器内原位完成的。 这是因为加法虽然简单，但存在进位传播：即使是对存内数值加1，也有可能导致所有比特全部发生翻转。 因此，在集成电路中制作计数器，需要一个完整的加法器来完成数值自增操作（后继运算），存储器内完整的数据必须全部被激活备用。

好在自增操作在平均情况下只会导致两个比特的翻转。我们需要找到一种记数法，控制最差情况下可能发生翻转的比特数量。因此我们引入了偏斜二进制记数法来代替二进制。偏斜记数法最初提出时是用于数据结构设计，例如用于Brodal堆，控制堆发生归并时的最差情况时间复杂度，而这与控制加法的进位传播十分类似。

我们使用CMOS上的SRAM技术作为基础来设计RIM。我们将存储的数值（以偏斜记数法记录）按列向存储，并为每一列额外提供一列SRAM单元格用来存储每一数位的偏斜状态（即偏斜数中的数位“2”）。偏斜数的自增操作规则如下：

• 如果当前数中有数位为“2”，将“2”置“0”，将其下一位增1；
• 否则，将最低位增1.

虽然每一个数中的“2”所处的行可能不同（偏斜记数规则中要求一个偏斜数中最多只能有一位为“2”），导致要操作的单元格随机分布在存储器阵列里，不能按以往SRAM的行选方式来激活；但我们可以使用上一位的偏斜状态来激活本位和下一位的对应单元，实现在同一操作周期中激活出位于不同行的单元格！

最终，我们实现了24T的RIM单元格——没有使用新材料，而是完全由CMOS技术构建。RIM能够实现对所存数据的随机自增：在同一操作周期里，RIM所存储的一些数据可以按需自增，而其他数据可以保持不变。

我们将RIM应用于随机计算（一进制计算）中。 随机计算的一大痛点在于一进制数与二进制数之间的转化开销——二进制数转一进制数需要随机数发生器，一进制数转二进制数需要计数器。因为一进制数数位太长（可达上千比特），使用一进制数完成计算后，中间结果如需暂存，必须转换回二进制，使计数操作所消耗的能量甚至能达到整个计算架构的78%。 我们使用RIM替换了uSystolic中的计数器，构建了Cambricon-U架构，显著降低了计数操作的能耗。 这项工作解决了基于随机计算的深度学习处理器的一项关键痛点，使相关技术有望更快应用。

论文发表在MICRO 2023。[DOI]

整个五月都在帮人改文章当中度过。

在我们的教育体系里，学生写研究生学位论文之前，从来没有人教过他们怎么写。这导致了很多问题：学生不会写，老师改得痛苦；千叮咛万嘱咐，改了一版又一版，一两个月过去了，答辩完还是被逮捕。大部分文章出现的问题都是共性的，然而却需要我们每个人手把手地教，非常费时费力，效果也不好。我总结一部分共性问题，供有需要的同学自查自纠。

为了方便完全不懂写作的同学也能意识到问题，我给出的都是非常表面、浅显、刻板的现象，全部是写个寥寥几行的脚本就能计算出来的指标。请注意：不出现这些现象不意味着论文就能过关，出现了也不意味着一定就不是优秀的论文了。希望能引起读者自己的思考，考虑一下为什么问题论文浮现出的表面现象大多是这样的。

第一定律：“极”字出现的次数（）与文章质量负相关

“极”当然可以作为极限的意思在科学术语当中使用，但更多时候，论文里用“极”、“很”、“非常”等等词汇只是为了表达强调。 在语言中，这些词汇的作用是输出情绪，属于主观成分，而对客观地描绘事物几乎没有帮助。 论文作为科学的文字载体，必须保持客观。 写下这些主观描述程度的词汇的时候，同学们需要引起特别警惕，要着重检查自己是否已经脱离了保持客观这一基本要求。 一般同学一旦犯了这样的错误，会连续犯一大串，给评审专家留下的阅读体验可想而知会是多么的不专业。

类似地，建议同学检查论文里是否出现了其他形式的主观评判，例如“取得了广泛应用”“做出了突出贡献”，或者反过来的“效果有限”之类的词句。 这些是只有评审专家才能讲的，评审是要求专家发表主观意见的过程。论文作者要论述客观规律，没有资格讲自己；除非给出明确而客观的依据，论文作者也没有资格讲别人。

解决方法是提供客观的依据。 比如“效率极高”可以改成“在（某项测试）中效率达到了98.5%”；“应用广泛”可以改成“在情感分析[17]、对话系统[18]、摘要生成[19]等领域得到应用”。

第二定律：参考文献域数目的方差（）与文章质量负相关

你肯定懒得弄参考文献，从DBLP、ACM DL或者出版商网站上复制一份BiBTeX，粘在一起就用了，最后排版出来的参考文献部分长什么样完全交给不知道从哪拷来的bst文件控制。 最后做出来的效果就是，参考文献项目参差不齐：有的缺项，有的又多出很多意义不明的项目出来。所以，我说粗略数一下每一条参考文献里出现了多少个项目域，算算方差就能体现出论文质量来。 参考文献里的问题可真是五花八门了，花多少时间去整理都整不完，所以最能体现作者对论文的上心程度，区分度很高。 同一个会议名称，有的只写会议全称，有的前面加了主办方，有的后面加了缩写，有的用年份区分，有的用届区分； 明明有DOI，有些参考文献后面又给了个arXiv的URL；标题里大小写混乱，有时还连续出现NVIDIA的一百种写法。 所以写论文到底用没用心，用了多少时间打磨，看一眼参考文献就露馅了。学位会上评定论文的时候时间紧张，一定是先从这个弱点开始查起，想蒙混过关是不可能的。

解决方法只有下功夫自己捋一遍，需要不怕麻烦、多花时间。出版商网站上给出的项目只能参考，BiBTeX只是个排版工具，里面要填什么内容最后还是要靠作者来控制。

第三定律：下划线“_”出现的次数（）与文章质量负相关

汉语里是没有这个符号的，英语里也没有，我所知的人类语言都不用这个符号。 只有代码写多了，把论文当成代码文档来写，论文里夹带了代码碎片才会出现这个符号。 这一条定律是刻画得最准确的，几乎没有反例。

论文写作的目的是向其他人传播你的学术观点。要高效地向其他人传递知识，论文必须先对知识进行抽象和提炼。 总不能抛出一堆原始材料去要求读者自行理解，不然作者的贡献在哪里？ 抽象的过程就是抛弃掉与叙事无关的实现细节（代码就是其中最恼人的细节），保留令人眼前一亮的思路和诀窍。 因此，任何一篇好的文章里都不会出现代码碎片，好的作者也压根不会有想以含下划线的名字命名任何概念的想法。

解决方法是补完知识抽象和为抽象概念命名的过程。代码、数据、定理推演如要保留，也扔到附录里去，作为补充材料，不要把他们算作文章里的一份子。

第四定律：西文字符占比（）与文章质量负相关

学位论文要求是用汉语写作的，然而差劲的论文特别喜欢在汉语语境里夹杂其他东西。 上一条批判的是夹杂代码碎片（讲不好人话），这一条要批判夹杂所有非汉语的内容（讲不好中国话）。 AlphaGo（阿尔法围棋）不用汉语情有可原，Model-based RL（基于模型的强化学习）就没道理夹生了吧？ 今年有两个同学写出这样的话：“降低cache的miss率”，整篇论文变成了夹生饭。 研究生准备毕业了，却连母语都讲不好，显现出了论文的低质量。 论文里用到英文命名的概念一时不知道如何用汉语表达很正常。如果这个概念很重要，你当然应该花时间去寻找它的公允译名；如果是新概念就下点心思起一个专业、准确、可辨识的名字；如果你懒得寻找名字懒得起名，说明这些根本就是连自己也不看重的凑篇幅的废话罢了。

建议发现自己有类似习惯的同学，写作的时候给自己立个规矩：文章里每用到一个汉字、阿拉伯数字和汉语标点符号之外的字符，给红十字会捐一元钱。要让自己往汉语论文里写西文的时候，下意识地产生肉疼的感觉。西文不是不能写，至少不能滥用。

第五定律：数学符号平均长度（）与文章质量负相关

爱因斯坦是这样写公式的：

假如相对论是我们的同学创立的，这个公式可能就变成这样了：

至少也要把文字写在文字模式下吧！用\text或者\mathrm包裹起来，不要变成了 😅

不说啥了，体会一下大师的差距吧。为什么别人做出的工作是传世经典，我们的还在挣扎通过学位会审核呢？ 做工作的时候没有下心思去简化表述，文字也充满赘语，图片也纷繁复杂，竟然连小小的公式符号都缩短不下去。 复杂度越高，学术美感就越差。

第六定律：同一页出现的图表总数目最大值（）与文章质量负相关

当你凑不够篇幅的时候，堆砌图表总比绞尽脑汁多写点文字来得更快一些。 于是同学们写文章的时候，一写到了实验这一部分，拿起程序调优器（profiler）来一顿截图——连续七八张插图，满屏幕色块花花绿绿，感觉论文的分量霎时间就充足、饱满了起来。 结果评审专家拿到论文一筹莫展，这都是啥？啥？啥？ 一堆小色块堆砌在那里，与之配套的文字说明几乎没有，想参透背后的逻辑可比智商测试题有挑战得多啦！ 除了作者也就只有鬼能知道这图到底是什么意思了（实际上很可能连作者自己也不知道，只有鬼才知道）。 你的论文大体水准还行的时候，为了避免场面太尴尬，看破不说破，专家也就睁一只眼、闭一只眼，权当你这一段没写了。 论文水准若是不行，你堆砌的这些谜一样的配图怕是会成为让专家丧失信心的最后一根稻草。

我这个指标的计算方法如果算出较高的值，至少说明文章中某一部分图、文搭配的比例出了问题，很可能提示了存在有配图未在文字中予以说明、引用论证的情况。 文章的主体是文字，图、表只是方便直观理解文章内容的辅助工具。 使用图、表首先应注意它的辅助说明性质，是对文字的补充。不能本末倒置，绝不应该出现连续的图、表罗列。 其次，还要注意图、表的直观性。 它们要表达的意义应当明确，能够自述清楚（让专家看第一眼就能理解这份图表想要表达的意图）； 图、表较为复杂的时候，应当突出重点，引导读者的注意力。 或者，为复杂的图、表搭配详细的阅图（阅表）指引文字。

第七定律：屏幕截图的数量（）与文章质量负相关

承接上一条。写论文的时候，建议抠掉键盘上的PrintScreen——恶魔之键。 在这个键的诱惑下，同学们总是懒得画图，从VCS、NSight、VS Code甚至命令提示符终端之类的软件用户界面上直接截取一部分下来，就作为配图插入论文中了。 结果是几乎逃不脱字号过大或过小、字体不匹配、作图风格混乱、说明文字缺失、重点不突出、简单罗列堆砌原始材料等一系列问题。 虽然其中的问题不一定十分致命，但是给人的观感一定特别差。不论图本身的意义明确了没有，首先就给人留下一个懒散的印象。

从IDE截图的，截下来的内容肯定是代码吧！参见第三、第四定律。 而截取终端里程序执行打印出的调试日志作为配图的同学是最恶劣的，还不如截代码呢。 代码好歹还有语法语义，执行日志是纯纯的占用篇幅、浪费纸墨的内容。

第八定律：相关工作结束页的页码占全文页码的比例（）与文章质量负相关

我评价论文的时候，首先会检查这个指标，因为很容易：找到最后一页出现相关工作的位置，手指卡住，合上论文，观察书脊前后两部分的比例。 整个过程可能只需要五秒，却能直观地戳穿同学拿相关工作凑篇幅的现象。 如果论文在这个检查下头重脚轻，注定逃不脱是一篇烂文章。因为要写好相关工作，比写好自己的工作还要难得多！ 想象一下，答辩时专家们一边翻阅你的论文，一边努力分出一部分注意力来听你报告。 结果你却迟迟不进入自己的工作内容，浪费十几分钟在介绍一些或人尽皆知的、或陈词滥调的、或和本文工作几乎无关联的内容。 这次答辩的结果一定是非常糟糕的。

深入调研相关工作是需要大量精力和学术积累的。 首先需要对重要相关工作进行发现和筛选。 我们不去歧视科研机构和出版物，毕竟要评价具体工作的分量还是要坚持从客观的科学性评价出发。但引领性工作（在统计意义上）更经常由学术水平领先的机构发表在重要会议和刊物上。 而同学总是引用印度工程技术学院发表在Hindawi开放获取杂志上的文章，该领域开创性的重要工作却出现遗漏，足不足以说明对学科前沿还不够了解？ 能够罗列出大量的重要相关工作，同时又避免夹带低水平相关工作，本身就是需要长期学术积累才能做成的一件难事。同学们在学术道路上初出茅庐，功底不够深厚是正常的，此时贪图在相关工作上凑篇幅写得太多太长，总是难免露怯。

其次，对遴选出的相关工作进行综述，本就是一份科学性很强的工作。如果做好，其学术价值不亚于学位论文中某一项研究点。 同学们没有那么多时间精力去梳理，或者还没有掌握进行综述的方法，大多数时候只能对相关工作简单罗列。 其中，掌握得比较好的同学大概能写成这样：

这样的写法至少在一串工作的罗列前后做到了有头有尾，也集中呼应了自己的工作，已经难能可贵了。要知道还有很多同学写不成这个水平，只有其中罗列的部分，有甚者一列就是二三十条。 评审专家若成心想刁难作者让他下不了台，大可以一条一条地展开来问：“这项工作的诀窍是什么？”“这项和前面某一项工作的区别是什么？联系是什么？”“这项工作和你有什么关系？”二三十条问下来，人肯定是问傻了。 毕竟罗列这么多工作，有些工作在作者列上来之前可能根本连文章都没打开过，直接从谷歌学术上复制个BiBTeX项进来就草草了事了。 我列举的三个方面问题对应着相关工作的三个必备要素：关键科学思想或发现、分类学和主题相关性。 一个好的综述，应该做到对每一项相关工作的诀窍能够一句话解释清楚；相关工作从不同维度梳理成多个类别，分类合理、界限清楚；每一类工作之间逻辑关系明确、叙事线索清楚，与文章主题紧密相关。 这是非要作者具有很强的科学抽象、语言凝练能力不可的，需要一段反复的推敲和辩证过程才能成文。

学位论文的第一章只要把大约三个研究点归纳到一起，就已经难倒多数同学了。 所以我特别建议同学们，除非有特别的理解，不要轻易在第二章集中介绍相关工作。这样写特别考验写作能力。建议在各个研究点的论述过程中，在真正引用到相关工作的具体位置上，进行针对性的介绍。 否则同学未经科学写作训练，很容易将集中的相关工作章节写成意义不明的一段凑篇幅的内容。 既然是凑篇幅的内容，文章的正文工作越单薄，为了显得篇幅充足，这部分内容凑得自然也就越多。 这段内容占比越长，通常意味着论文质量越差，也就不难理解了。

第九定律：实验内容最长连续页数（）与文章质量负相关

另一个凑篇幅的重灾区在于实验部分。 毕竟相比于写文章的痛苦，动动手做实验显得舒适多了。 多设计几个无关紧要的指标，画个柱状图做对比，matplotlib脚本都是现成可复用的； 或者数据列成表格，一行可能都放不下，一下子又多占了许多页面。 还有相当多的同学，想凑三个研究点出来却凑不满，就把实验提取出来堆砌在一起，作为论文的第五章、第三个研究点来写。 作为单独的一章，连续的实验部分至少也是十几、二十多页打底，才不显得单薄。 实验罗列到一起，与相关工作罗列到一起，造成的危害是一样严重的。实验原本用来验证研究内容，现在一些研究内容失去了实验支持，而一堆缺乏组织逻辑的实验数据又堆砌到了一起，再一次构成了意义不明的凑篇幅内容。 第九定律提出的是特别为检查这一常见做法而设计的指标。

这种心态应该归结于两点。

其一，经验主义认识的盛行：只将实验看作科学研究的一等公民，从而忽略了建立和传播科学抽象的价值。 作为物理学前沿研究的重要基础设施，北京正负电子对撞机已经产生了超过10PB的实验数据。 很多重要科学发现最初都来源于这些原始数据。 将这些数据印刷编纂成册，一定会成为科学价值极高的著作，让物理学家人手一套吧？ 不然。 因为人类用符号语言传递信息的带宽只有约39bps，100年的寿命中一个人能接受上限为15GB的符号数据。 没有人能在有生之年阅读完这些数据，更别提从中发现些什么了。 真正有科学价值的不是用图、表展示的数据，而是由数据作为印证的、抽象的科学思想。 实验在其中只起到了验证的作用，可以说不仅不是一等公民，甚至很多时候只是第二性的——科学研究中常常是先提出抽象的科学思想，才有特别设计的实验去验证真伪。

其二，将论文误解为一种工作量证明（PoW）：实验是我攻读研究生期间写了代码干了活的直接证明材料，统统列上来作为我向老板、领导的工作汇报。 这样就是将自己在科学研究中的身份搞错了。 研究生不是力工。 科学探索不是出卖苦力，科学工作的一分耕耘大多数时候都不会有对应的一分收获产生（否则会被大家鄙称为“灌水”），对比工作量意义有限。 论文应该是创造性思想的载体，而不是对付雇主的打卡记录——前者将是富有科学价值的文献，后者除了付你工资的雇主之外再没有人会关心。 你的导师、评阅专家、答辩会成员、学位会成员，以及你论文未来潜在的读者，他们是不是你的雇主？他们关心的是什么，想看到的是什么？ 写论文之前，一定要首先搞清这一点。

当然同学也会问：你说这些有什么用，谁不知道要写出科学价值，可我的工作就是平凡到凑不齐三个研究点，怎么办？ 这里就得提醒还没临近毕业大限的同学，要有意识地避免落到这样的境地里来。 写学位论文一定要预先谋划，前期开展研究工作的时候就在同一领域内布局好三个研究点的大致内容，在导师的指导下开展一项工作，然后有针对性地开展另外一到两项的研究。 只要你完成了一项有价值的研究工作，就很容易延伸出三个研究点了，例如：以该工作本身作为第二点；查找该工作的缺陷，继续完善，是第三点；总结两项工作的思想，提出科学、凝练的形而上（模型、范式、原则、风格），是第一点。 其中形而上的部分完全可以在论文写作的过程中一同完成。

最差的情况下，也要保持实事求是。有几项工作就写几项，实验就原原本本地用来验证具体的工作内容，不要把实验提出来凑章节。

第十定律：标题间最小距离（）与文章质量正相关

与之前九项不同，最后一项是一条建议性的内容，因此提出了唯一一项正相关的指标。 将文章写得富有条理、线索明确并非一件容易的事。 但是我们有一种快速改进的方法：强迫自己将文章每一处的线索明确地列出来，写在各级标题的下方。 我们拿相关工作来举例：

采用这种写法，读者每读到一处，都可以从标题下方的文字获得局部内容的阅读指引，阅读体验将会显著改善。 而更重要的是，有意识地遵循这种固定写法，可以强迫你对文章的叙述脉络进行整理。 只要能写得出来，就能保证文章是有结构、有条理、有逻辑的。 这种写法带来的特点是各级标题下都有一段导引性文字，不会有任何两个标题直接相邻。因此，我用标题间最小距离来刻画这一特点。

总结

学位论文是同学们一生中独一无二的材料，论文代表了自己获取学位时的学术水平，在数据库中随时供人查阅参考。 虽然大家对我的博士论文给了比较高的评价，但我的论文里还是犯了以上一些错误； 学会将我的论文出版成册，再次校对的过程让我感到非常懊悔。 建议同学们还是应当将学位论文写作当作自己的一件人生大事去对待，用多少热情去仔细琢磨都不为过。

这一次我只是简单地从批判的角度来讨论论文写作，相对而言，建设性并不强。 希望同学们读到这些内容，经过思考后，能够体会到论文的基本要求，建立对论文基本的审美判断。 看到自己的不足之处是进步的基础；认识到论文写作需要遵循诸多限制、需要多下功夫，才能建立正确的心态。

上个月，我受教育处李丹老师邀请，面向毕业生做了一次学位论文写作和答辩心得报告，里面包含更多建设性的意见。 因为当时时间比较匆忙，其中很多内容还不完整或欠缺打磨。 学位论文写作是一项需要长远规划的重要工作，写好论文最重要的是要整理好自己的多项研究工作，而这些研究工作又需要从开展研究之初就进行谨慎的选题和谋划。 因此我认为类似的报告不应当放在五月、面向毕业生开展，而更应当放在九月、面向入学新生开展。 我计划争取在九月前将内容补充完整，然后再进行分享。

在科学计算任务中，既需要处理高精度（数百至数百万比特）数值数据，也需要处理低精度数据（科学智能算法中引入的深度神经网络）。我们判断支撑未来科学计算新范式，需要一种不同于深度学习处理器的新体系结构。

我们对高精度数值计算的应用特性进行分析，发现存在“反内存墙”现象：数据传输瓶颈总是出现在近端存储层次上。这是因为数值乘法的数据局部性极强，如果运算器件原生支持的字长不够长，就需要分解运算，产生巨额的中间结果访存请求。因此，新架构必须具有：1. 处理数值乘法的能力；2. 一次性处理更大字长的能力；3. 能够高效处理大量低精度数据。 针对这些需求，我们设计了Cambricon-P架构。

Cambricon-P架构具有以下特点：

• 采用逐位运算数据流，实现同时支持高精度数值乘法和低精度线性代数运算；
• 进位并行机制，一定程度上缓解乘法算法内的强数据依赖，实现充足的硬件并行性；
• 位索引内积计算算法，将计算过程分解至单比特向量，挖掘有限域线性代数中隐含的冗余计算，将计算逻辑降低至朴素方法的36.7%.

为实现更大规模架构支持更大字长，Cambricon-P整体架构采用分形方式设计，在核级、处理单元（PE）级、内积运算单元（IPU）级复用相同控制结构和相似的数据流。我们为Cambricon-P原型快速开发了配套运算库MPApca，实现了图姆-库克2/3/4/6快速乘法算法和颂哈吉-施特拉森快速乘法算法（SSA），以便与CPU+GMP、GPU+CGBN等现有高性能计算系统进行对比评估。

实验结果表明，Cambricon-P+MPApca在单个乘法运算时相比CPU+GMP最大加速达100.98倍，在四个典型应用上平均实现加速23.41倍、能效提升30.16倍。

论文发表在MICRO 2022。[DOI]

自1968年创办以来，55届MICRO会议总共收录论文1900余篇。Cambricon-P获评大会最佳论文Runner-up奖，这是中国大陆研究团队第四次提名MICRO最佳论文。

在上海交通大学李超老师的邀请下，我参加了第一届CCF Chips大会的“体系结构优秀青年学者论坛”，并作线上报告。 我分享了一篇在审（单盲）论文《Rescue to the Curse of Universality》的成果和延伸思考。 内容还未完成同行评议过程，仅供参考。

报告要点：

• 通用性的诅咒——用逻辑电路构建一台既通用又高效的计算机是不可能的；
• REnc体系结构——将数据局部性作为尺度不变约束是达成高效体系结构的充分条件；
• 结果提示现在DSA可能过于专用，有着保持高效的同时提升通用性的理论空间。

根据半导体周期规律，我们预测接下来深度学习处理器将向通用性、易用性、标准化、系统化方向发展。

在西宁，我碰见了季宇，他也是CCF优博。 他一见到我就提了很多问题：那么复杂的系统，怎么可能就用分形来刻画呢？你在寒武纪真的是这么做的？ 时间有限，我和他解释说，分形是并行计算里非常基础的本质特征，而不是我们刻意制造的概念。 在当日的新人脱口秀环节中，我也重新为分形做了一个新定义：分形（并行计算）是问题的一种基本性质，指能够用一段有限的程序控制任意规模的并行计算机、在有限时间内计算任意大的问题。

不止是季博士，很多同行也都有类似的疑惑。不能服人，是因为我的工作仍然还在非常初级的阶段。我必须承认，现在对一线开发者而言，分形计算系统的概念实践意义有限。 但是，我有一言（确信）：如果你的系统不是分形的，那你要小心了！

分形的基本要求是用同一套程序跑在任意大的机器上。不分形，对一个并行机各部分分别编程，会引来很奇怪的情况： 额外的程序会根本性地让计算过程变质。因为在计算理论中，它们可以作为建议串。理论计算机学家立刻就明白这是什么含义了，我将对工程师们再多解释一点。

以MPMD模型为例。 既然有个并行节点可以分别编程，我可以在每一个程序里硬编码一个比特的额外信息而不违反模型的任何约束（每个程序依然是有限的）。 开始计算时，我将这些比特搜集起来，组成一个比特的自然数，然后可以将这个数广播到全部计算节点上。 记这个数为。当然，能表达的最大值是。

是“夹带”到程序中的外部输入信息，而且和机器规模有关，机器规模又可以随着问题规模一同扩展，因此引入了非均一性。假如，我们让表示描述长度为的全部图灵机中，会在空纸带上停机的个数。 于是我们立刻就有这样一个算法：

0. 输入一个图灵机的描述串（比特长）.
1. 搜集并广播.
2. .
3. 并行循环，对每一个：
   1. 在空纸带上模拟执行，直到停机.
   2. 使用原子操作递增.
   3. 如果，终止整个并行循环.
4. 返回结果取决于第个循环的模拟是完成了还是被终止了.

这个算法在有限时间内判定停机问题。

如果你的系统不允许发生这种事情（判定非递归问题；你当然不应该允许发生这种事情），那么它就已经是分形的了，即使形式上可能和我在论文中描述的不一致。 根本问题在于，超额的程序是有害的——理论上它会导致能够计算不可计算问题，实践中导致的问题有多种形式：包括我们曾经在寒武纪遇到的每年一重构即是根源于此（Cambricon-F：一种具有分形冯·诺伊曼体系结构的机器学习计算机）。 分形计算系统是在反对这种错误实践。

希望这段论述能让分形的概念更清楚一些。

参考文献

• Pekka Orponen, Ker-i Ko, Uwe Schöning, and Osamu Watanabe. 1994. Instance complexity. J. ACM 41, 1 (Jan. 1994), 96–121.

去年在做 Cambricon-Q：量化训练架构 的工作时，我发现许多同学不会做误差估计，也没有意识到随机实验中需要进行误差估计。体系结构领域似乎并不重视这一点，同行做实验时常常在真实系统上测试跑一个几十毫秒的程序，然后直接用time命令截取用时，再汇报模拟实验结果的加速比。这样的测量是有误差的，结果常常在一个范围内波动；如果加速比达到上百倍，一点误差可能会导致最终报告出完全不同的数值。 小初高通识教育中，实验课会教我们“多次测量取平均值”，但“多次”应该是多少次？5次够吗？10次呢？100次呢？还是直到工作截稿之前，一直重复做下去呢？我们需要了解科学的实验方法：重复随机实验中的误差估计。我发现并非所有本科概率论课程都教授这些，但要从事科学研究工作，这却是一项必备技能。

我不是统计学家，本科时我也是全校挂科王，肯定算不上概率论专家。但我曾经作为业余爱好钻研过蒙特卡洛模拟，我来展示我自己是如何完成这个过程的。如果有误，还请概率论专家们不吝纠正。

高斯估计

我们有一组实验测量值，现在假设它们独立同分布，服从于高斯分布。

虽然分布参数中有，这是我们想得到的，但不会直接体现在测量值中。为了逼近，我们可以取测量值的算术平均值。我们首先先求和，得到，然后除以。这时算术平均值。注意一个高斯分布随机变量除以后，方差会相应缩减倍。

虽然以上推演过程首先假设了高斯分布，但是根据列维-林德伯格中心极限定理(Levy-Lindeberg CLT)，任意无限个随机变量叠加后，其和都趋近于服从高斯分布，只要这些随机变量满足以下两个条件：

• 方差是有限的；
• 独立。

这样，无论实验测量值实际服从的分布是什么，我们都可以直接从CLT导出最终的分布，结果是一样的。 只要实验次数足够多，就趋近于。

高斯分布告诉我们，我们有99.7%的把握说，与我们想要获取的真实值之间的差距不超过三倍的标准差，即。我们说，的99.7%置信度的置信区间是。 随着实验次数增多，的标准差还会持续缩小。原来我们只知道多次测量取平均值会奏效，现在我们还知道收敛速度了：每增加4倍样本，误差将缩小2倍。

我们用到的常数3和99.7%是查表得出的高斯分布累积分布函数(CDF)上的一个点，类似常用值还有1.96和95%。从确定的置信区间推算置信度，我们使用CDF：，但CDF只留了右边尾分布不计，但我们估计的区间是双边的，因此置信度还要扣除左边尾分布，即。如果要用目标置信度来推算置信区间，则需要使用CDF的逆函数ICDF，也叫PPF。

编程实现时，高斯分布的CDF可以比较直接地用数学库函数erf实现。它的逆函数erfinv并不常见，在C语言和C++的标准库里就不存在，不过因为CDF都是连续、单调、可导的，其导函数即概率密度函数(PDF)，因此用牛顿法、割线法、二分法等数值方法都可以比较高效地求逆。

然而，以上估计完全依赖于CLT，CLT毕竟只描述了一个极限情况。实际实验时我们取5次、10次实验结果，离无限次实验差得远，难道也强行应用CLT吗？这显然不科学。

“学生” t-分布估计

描述有限多次随机实验叠加值，有一个更专用的概率分布，即“学生” t-分布。除了以上高斯估计推算的过程，t-分布还额外考虑了和真实误差之间的差异。

t-分布与自由度直接相关，在重复随机实验里自由度可以理解为。自由度低时，t-分布的两端更长，可以导出一个更保守的误差估计；当自由度趋近于无穷时，t-分布也趋近于高斯分布。例如5次重复实验，自由度为4，如果用高斯估计99.7%置信度的误差结果为3倍标准差，用“学生” t-分布则估计为6.43倍，显著地扩大了。

当试验次数不多时，我们直接用t-分布代替高斯分布来描述。特别是在依靠误差估计来判定重复实验的提前结束时，使用高斯估计更容易发生过早的结束（特别是在前两、三个样本凑巧相差不大时）。

实现

在Python中，直接调包：高斯估计使用scipy.stats.norm.cdf和scipy.stats.norm.ppf；“学生” t-分布估计使用scipy.stats.t.cdf和scipy.stats.t.ppf。

C++里比较难做，STL库功能不全，而且引入外部库不方便。下面的代码给出了两种误差估计的C++实现。两条注释条之间的内容可以抽出组成一个头文件供直接使用，更下面的部分则展示了一个样例程序：从分布的随机变量中重复实验，直到误差估计认为有95%的把握将真实值囊括在估计值的正负10%的范围内。

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

/*
     error estimator for repeated randomized experiments.
     every scientists should know how to do this...
     requires c++17 or above.

     Copyright (c) 2021,2022 zhaoyongwei<zhaoyongwei@ict.ac.cn>
     IPRC, ICT CAS. Visit https://yongwei.site/error-estimator

     Permission is hereby granted, free of charge, to any person obtaining a copy
     of this software and associated documentation files (the "Software"), to deal
     in the Software without restriction, including without limitation the rights
     to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
     copies of the Software, and to permit persons to whom the Software is
     furnished to do so, subject to the following conditions:
     
     The above copyright notice and this permission notice shall be included in all
     copies or substantial portions of the Software.
     
     THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
     IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
     FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
     AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
     LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
     OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
     SOFTWARE.
*/

// ====================================================================
//           contents before the DEMO rule is a header.
// ====================================================================
// #pragma once // <-- don't forget opening this in a header.
                //     compilers don't like this in the main file.

#define __STDCPP_WANT_MATH_SPEC_FUNCS__ 1 // for std::beta
#include <cmath>
#include <iterator>
#include <tuple>

namespace errest {

// gaussian distribution. works as an approximation in most cases
// due to CLT, but is over-optimistic, especially when samples are
// few.
template<class RealType = double>
struct gaussian {
  static RealType critical_score(RealType cl, size_t df) {

    // due to CLT, mean of samples approaches a normal distribution.
    // `erf` is used to estimate confidence level.
    // now we set a confidence level and try obtain corresponding
    // confidence interval, thus we need the inverse of `erf`,
    // i.e. `erfinv`.
    using std::log; using std::sqrt; using std::erf; using std::exp;

    // solve erfinv by newton-raphson since c++stl lacks it.
    auto erfinv = [](RealType x) {
      constexpr RealType k = 0.88622692545275801; // 0.5 * sqrt(pi)
      RealType step, y = [](RealType x) { // a rough first approx.
           RealType sign = (x < 0) ? -1.0 : 1.0;
           x = (1 - x)*(1 + x);
           RealType lnx = log(x);
           RealType t1 = RealType(4.330746750799873)+lnx/2;
           RealType t2 = 1 / RealType(0.147) * lnx;
           return sign * sqrt(-t1 + sqrt(t1 * t1 - t2));
      }(x);
      do {
        step = k * (erf(y) - x) / exp(-y * y);
        y -= step;
      } while (step); // converge until zero step.
                      // this maybe too accurate for our usecase?
                      // add a threshold or cache if too slow.
      return y;
    };
    // we hope that the "truth" E[mean] lands in the interval
    // [mean-x*sigma, mean+x*sigma] with a probability of
    //                conf_level = erf( x/sqrt(2) )
    // conversely,
    //                x = sqrt(2) * erfinv(conf_level)
    return sqrt(RealType(2)) * erfinv(cl);
    // to get interval, mult this multiplier on the standard error of mean.
  }
};

// student's t-distribution. yields an accurate estimation even for few
// samples, but is more computational expensive.
template<class RealType = double>
struct student {
  static RealType critical_score(RealType cl, size_t df) {
    
    // similar to gaussian, we need to evaluate ppf for critical score.
    // ppf is the inverse function of cdf, and pdf is the derivative
    // function of cdf. we find the inverse of cdf by newton-raphson.
    using std::beta; using std::sqrt; using std::pow; using std::lgamma;
    using std::exp; using std::log; using std::nextafter;

    auto pdf = [](RealType x, RealType df) {
      return pow(df / (df + x * x), (df + 1)/2) /
        (sqrt(df) * beta(df/2, RealType(0.5)));
    };

    auto cdf = [](RealType x, RealType df) {
      // ibeta, derived from https://codeplea.com/incomplete-beta-function-c
      // original code is under zlib License,
      // Copyright (c) 2016, 2017 Lewis Van Winkle
      // i believe this snippet should be relicensed due to thorough rework.
      auto ibeta = [](RealType a, RealType b, RealType x){
        const RealType lbeta_ab = lgamma(a)+lgamma(b)-lgamma(a+b);
        const RealType first = exp(log(x)*a+log(1-x)*b-lbeta_ab) / a;
        RealType f = 2, c = 2, d = 1, step; int m = 0;
        do {
            RealType o = -((a+m)*(a+b+m)*x)/((a+2*m)*(a+2*m+1));
            m++; RealType e = (m*(b-m)*x)/((a+2*m-1)*(a+2*m));
            RealType dt = 1 + o/d; d = 1 + e/dt;
            RealType ct = 1 + o/c; c = 1 + e/ct;
            f *= (step = (ct+e)/(dt+e));
        } while(step - 1.);
        return first * (f - 1);
      };
      RealType root = sqrt(x*x+df);
      return ibeta(df/2, df/2, (x + root)/(2*root));
    };

    cl = 1 - (1 - cl) / 2;
    // solve the root of cdf(x) - cl = 0.
    // first use newton-raphson, generally starting at 0 since cdf is
    // monotonically increasing. disallow overshoot. when overshoot
    // is detected, an inclusive interval is also determined, then
    // switch to bisection for the accurate root.
    RealType l = 0, r = 0, step;
    while((step = (cdf(r, df) - cl) / pdf(r, df)) < 0) {
      l = r; r -= step;
    }
    while (r > nextafter(l, r)) {
      RealType m = (l + r) / 2;
      (cdf(m, df) - cl < 0 ? l : r) = m;
    }
    return nextafter(l, r); // let cdf(return val) >= 0 always holds.
  }
};

template<template<class> class Distribution = gaussian, class RealType = double>
struct estimator {

  // std::tie(mean, error) = estimator::test(first, last, cl)
  //
  // perform error estimation over the range [`first`, `last`). 
  // the ground truth should be included in the interval
  // [`mean-error`, `mean+error`] with a probability of `cl`.
  template<class InputIt>
  static std::tuple<RealType,RealType> test
          (InputIt first, InputIt last, RealType cl = 0.95) {

    // sampling has 1 less degrees of freedom.
    auto n = distance(first, last);
    auto df = n - 1;

    // pairwise sum to reduce rounding error.
    using std::distance; using std::next; using std::sqrt;
    auto sum = [](InputIt first, InputIt last,
                         auto&& trans, auto&& sum)->RealType {
      if (distance(first, last) == 1) {
        return trans(*first);
      } else {
        auto mid = first + distance(first, last) / 2;
        return sum(first, mid, trans, sum) + sum(mid, last, trans, sum);
      }
    };

    auto trans_mean = [n](RealType x)->RealType {
      return x/n;
    };
    auto mean = sum(first, last, trans_mean, sum);
    auto trans_var = [mean, df](RealType x)->RealType {
      return (x - mean) * (x - mean) / df;
    };
    auto var = sum(first, last, trans_var, sum);

    // assuming samples are i.i.d., we estimate `mean` as
    //
    //       samples[i] ~ N(mean, var)
    //              sum = Sum(samples)
    //                  ~ N(n*mean, n*var)
    //             mean = sum/n
    //                  ~ N(mean, var/n)
    // the standard error of mean, namely `sigma`,
    //            sigma = sqrt(var/n).
    //
    // due to Levy-Lindeberg CLT, above estimation to `mean`
    // approximately holds for any sequences of random variables when
    // `m_iterations`->inf, as long as:
    //
    //   * with finite variance
    //   * independently distributed
    
    auto sigma = sqrt(var/n);

    // finally, confidence interval is (+-) `critical_score*sigma`.
    // here critical_score is dependent on the assumed distribution.
    // we provide `gaussian` and `student` here.
    //
    //  - `gaussian` works well for many (>30) samples due to CLT,
    //    but are over-optimistic when samples are few;
    //  - `student` is more conservative, depends on number of
    //    samples, but is much more computational expensive.
    
    return { mean, Distribution<RealType>::critical_score(cl, df) * sigma };
  }
};

using gaussian_estimator = estimator<gaussian>;
using student_estimator = estimator<student>;

};

// ====================================================================
//      DEMO: experiment with RNG, try to obtain its expectation.
// ====================================================================
#include <random>
#include <vector>
#include <iostream>
#include <iomanip>

int main(int argc, char** argv) {

  // the "truth" hides behind a normal distribution N(5,2).
  // after this demo converged, we expect the mean very close to 5.
  // we use student's t-distribution here, which works better for
  // small sets.
  // if you change the distribution to gaussian, you will likely
  // see an increased chance to fail the challenge. 
  std::random_device rd;
  std::mt19937 gen(rd());
  std::normal_distribution<double> dist{5,2}; // <-- the "truth"

  // demo configuration.
  constexpr double confidence_level = 0.95; // 95% confidence to pass the challenge.
  constexpr double error_tolerance = 0.10;  // stop below +-10% error, ~[4.5, 5.5].

  double mean, error;
  size_t iteration = 5; // experiments per test.
  std::vector<double> samples;

  while (1) {
    // draw 5 more samples then test.
    std::cout << "Single Experiment Results: ";
    for (size_t i = 0; i < iteration; i++) {
      double sample = dist(gen); // <-- perform a single experiment.
      samples.push_back(sample);
      if (i < 10)
        std::cout << sample << " ";
      else if (i < 11)
        std::cout << "...";
    }
    std::cout << std::endl;

    // test the confidence interval with our estimator.
    std::tie(mean, error) = errest::student_estimator::test(samples.begin(), samples.end(), confidence_level);
    // or with structured binding declaration [c++17]:
    // auto [mean, error] = errest::student_estimator::test(samples.begin(), samples.end(), confidence_level);

    std::cout << " * Error Estimator Report: "
      "collected " << samples.size() << " results, "
      "mean: " << mean << ", error: " << error << std::endl
      << std::endl;

    // stop if error is below 10%,
    if (error < mean * error_tolerance) break;

  }

  std::cout << "demo converged with " << (confidence_level * 100) << " percent confidence "
    "within " << (error_tolerance * 100) << " percent error range. "
    "is the \"truth\" 5 within the interval "
    "[" << mean-error << ", " << mean+error << "]?" << std::endl;
  return 0;

}

由于现代深度学习技术的不断发展，深度学习任务具有控制逻辑复杂化、宿主-设备交互频繁化的发展趋势；而传统的以CPU为中心的加速器系统宿主-设备交互开销大，交互速度提升缓慢，最终形成“交互墙”问题：交互速度提升与设备计算速度提升之间形成剪刀差。根据阿姆达尔定律，这将严重限制加速器的应用。

针对这一问题，CPULESS加速器提出了融合流水线结构，将系统的控制中心移至深度学习处理器上来，省去独立的宿主CPU芯片；采用面向异常编程方式，能够将标量控制单元和向量运算单元之间的交互开销降至最低。

实验表明，在多种具有复杂控制逻辑的现代深度学习任务上，CPULESS系统相比传统以CPU为中心的GPU系统能够实现10.30倍性能提升，并节约92.99%的能耗。

论文发表在《IEEE Transactions on Computers》。[DOI] [实验源码]