好的 scc@sc'19 终于没有拿亚军 记个流水账 Benchmarking 好像没啥特别的. 一个新的发现是 HPL 的功耗飘可能是因为 GPU 功耗上升而不是计算 pattern? 回头仔细看看..? 内核的奇怪的锅 导致 idle 状态下 ssh 上一台机器就能跳 200w 的功耗 spike. 通过更新内核版本解决了该问题. IB 卡烧掉了??? benchmark 本来早晨很早就交了而且数也还行. 然而中午玩着玩着发现 ib 卡没了. 尝试 pci hot reenable 失败之后重启并重新跑了 benchmark. 后来发现是 ib 卡在 gpu 风道里, 而我们给没插卡的节点的 gpu 风扇拔了一半的线, 另一半还是最低速运转的, 于是把 ib 给热傻了… SST 人脑挖矿 + 无脑跑 SST 第一个部分是给定 cpu 核心数, l1/l2 cache 的不同搭配之类的总共乘起来 5760 种选择, 让用 SST 搞出一种性能最好且不超过5000块钱的配置. 人脑挖矿 vs 暴力. 测算发现暴力应该能跑完所有点, 于是就暴力了一下. 听说别的队有试图人脑的…...

获得一个生日礼物 raspberry pi 已将近一年, 然而因为它只有四个核所以被嫌弃地闲置了很久. 近期因为上了嵌入式的课, 所以又开始了一轮折腾. 把一些有趣的事记录一下. 网络连接配置 老师说让我们先插上显示器配wifi, 之前我也是这么干的, 于是照做了. 然后想拿回家用, 家里没显示器, wifi 密码输入错误, 失联 ovo 后来想起直接给有线网口配个静态ip 就完事了. 和电脑直接对插就能访问 ovo. 延迟测试 发了一个示波器很好玩, 然而只有 windows 的 pc 端驱动差评. GPIO 管脚控制居然是 python, 严重怀疑效率. 实验本身倒是很简单. 接下来是给 kernel 打实时性补丁. (中断响应优先级? 时间步大小? 感觉 很有趣) 视频流 网上看到一个例子是把 raspivid 的输出用 nc 接起来到 host 上用 mplayer / vlc 播放. 非常有趣就试了一下. cvlc 转发延迟略高. 直接 mplayer 放 h264 格式的视频非常流畅. Modius NN 计算棒 去 intel 上找到了 openvino 作为 myriad 计算棒的驱动....

GridGraph 师兄的文章. 主要 idea 是把邻接矩阵切成块 (p*p) 放到磁盘上顺序读来提升 io 性能. 单机. GraphChi disk-based, parallel sliding windows, single consumer-level computer. metis 不 work (???) 解决出入边都要考虑和写的问题. 按出边分块 shard. 入边按序存放, 在每个 shard 中为连续一段. 可加载进来. 解决了一些比较麻烦的问题比如数三角形.

因为在 LA 爬了俩月坡, 感觉自己功率有所长进, 所以这场比赛以为自己能站个台. 然而事实是刷出了 pw. 这个经历再次验证了 flag 学三大定理 lyzy, 2016. 起源和准备阶段 赛前两周才听说重庆有比赛. 本来下半年没有比赛计划的, 自己的公路车也还没组装好, 但考虑到可以中秋回趟成都过节, 就还是毅然决然地被报名了. 在成都老车迷租到了一台 Trek Emonda 的入门铝公路车, 是前段时间某个比赛的赞助车, 虽然套件轮组辣鸡, 但总之能骑, 而且比在 LA 骑的那台上古 Allez 强. 甚至感觉自己能刷 pb. 回北京第一周早晨倒时差起床跑步, 发现跑六分配速都喘. 三天跑了11km. 游泳训练是和洞pro约在陈明讨论学术顺便划了300米. 赛前 发现20-24被重邮移通铁人队占了绝大多数. 有点方. 听尘尘和红红说他们很菜. 我竟然信了. 去车店取了车准备骑回家, 一路在三环辅路上飙到40kph非常爽. 然而骑了 6km 胎就被扎了. 回家看了半天才发现胎里扎了个钉子. ovo 开自家车带着爹妈和自行车从成都开了四个半小时到长寿湖. 一路定速巡航还挺爽. 审体检报告的时候果然又被短pr间期的问题卡了. 不过这次赛会医疗组很人性化地带了心电图设备, 直接现场复查了. 赞. 看赛道的时候让我爹开车跟着, 体验了一把后援车跟拍. 发现有一段颠颠颠颠的下坡. 以及发现这车变速不太准. 当场调变速. 晚上去吃奇怪的水库鱼, 然后鱼一直没上, 饭都吃完了, 就把鱼退了. 游泳 第一次遇到水下出发. 第一圈还将就就是有点慢. 第二圈下水就游偏了, 被裁判船吹哨赶了回去. 上岸的时候发现岸边有石头甚至差点划破了脚. 到 T1 发现只有我和另一台自行车了....

看上去很复杂的一个题. 然而数据范围 ( n \leq 50 ) 基础知识0: python 里面 list 可以做 dict 的 key. 基础知识1: python 里面 list 可以直接比较大小, 比较方式就是元素的字典序. 做法是先按照 username 对记录进行归类 (dict of list). 然后把每个 username 对应的所有记录按 timestamp 进行排序. (sorted(…, key=lambda …)) 然后枚举每个用户的所有访问页面三元组并扔进 list 里面. 因为要求一个用户只算一次, 所以要去除 list 里面重复的元素. 所以把 list 转换成 set (集合) 就好了. 也可以直接用 set. 然后把 set 里面的元素都用一个 dict 做一下记数. 最后从记数的 dict 里面挑出次数最多且字典序最小的就可以了. 代码链接

首先弄清楚中序遍历是什么意思. 中序遍历是一个序列 (list). 不存在的节点的中序遍历是空序 ([]). 以 u 为根的二叉树的中序遍历 = u 的左儿子的中序遍历 + u + u 的右儿子的中序遍历 其中加号就是连接两个序列的意思. 题目里说只考虑叶子节点的中序遍历, 就是把所有非叶子从中序里扔掉就好了. 然后考虑从随便一个序列构造一个满足条件的二叉树. 其实这个二叉树上的任意一个点会对应原序列中的连续一段, 而这个点的值就是这一段的所有数的最大值. 我们考虑自底向上的建树. 也就是说最开始是 n 个单独的点, 然后每次建一个新点, 它的两个儿子分别是原来的两个点. 然后用这个新点代替原来的两个点. 重复 “挑选, 替代” 的过程直到只剩一个点, 就建成了一棵完整的树. 每次挑选的两个点一定代表原数组上相邻的两个区间. 合并后建成这棵树的 最小 代价为 左儿子的最小代价 + 右儿子的最小代价 + 左边最大值 * 右边最大值. 而我们的最小化目标是根的 最小 代价. 自然想到用 f[l][i] 代表以 i 为第一个数的长度为 l 的区间所代表的点为根的树 的 最小 代价. 首先 f[1][i] == a[i], 而我们的目标是 f[n][0]. 进一步想, 最小化 f[l][i] 就是在所有该点的左右儿子分配方式 (就是各有多长, 总之加起来是 l) 中挑一个最小的....

很基础的 BFS 题目. BFS 和 DFS 是相对应的两种算法. 其区别在于对于新发现的可能性, BFS 将其放入队列末尾, 稍后进行探索, 而 DFS 立即探索这种新情况, 等探索完之后再回到之前的状态继续枚举. 对于这道题目来说, 具体来讲, 状况可以用 (位置, 距离, 颜色) 这么一个 tuple 来表示. 最开始的时候, 有 (0, 0, blue) 和 (0, 0, red) 这两种情况. 假设 0到1 有一条蓝边, 0到2 有一条红边, 那么新的情况是 (1, 1, red) 和 (2, 1, blue). 如果我们使用 DFS, 那么当新发现 (1, 1, red) 这个状态的时候, 我会立即以 (1, 1, red) 为起点, 继续探索 1 号点的邻居, 比如找到了 (3, 2, blue) … 直到找完所有通过 (1, 1, red) 可以达到的状态之后, 再继续以 (2, 1, blue) 为基础进行枚举....

先预处理一下, 把 >8h 的变成 +1, <=8h 的变成 -1 现在问题就变成了: 找最长的连续一段使其和 >0 使用前缀和数组, 要求 i~j 的和, 公式是 sum[j] - sum[i - 1]. 枚举左端点 i. 对于某个确定的 i, 要找以 i 为左端点的最长一段符合要求的区间, 即找满足条件 sum[j] > sum[i - 1] 的最大的 j 注意到 sum 数组的取值为 [-n, n], 故使用值域数组 values. value[k] 表示 sum[j] == k 的最大的 j. 该数组可以在求 sum 数组时一并求出. 满足条件 sum[j] > sum[i - 1] 的最大 j 即求 values[sum[i - 1] + 1], values[sum[i - 1] + 2], values[sum[i - 1] + 3], …, values[正无穷] 中的最大值....

状压动态规划. dp[x] 表示 x 状态下的最少人数. 其中 x 是二进制数, 第 i 位表示第 i 项技能是否有人已经拥有. 例如 ( x = (10010)_2 ) 从右往左第 1, 4 位是 1, 表示技能 1, 4 已有人掌握, 而 0, 2, 3 无人掌握. 假设一个人的技巧是 p, 现在的状态是 x, 则加入后的状态是 x|p. 其中 | 即 python/cpp 中的 | 运算符, 意义是取二进制或. 运算过程为最初时只有 dp[0] = 0. 对于每个人的技能集合 p, 可以更新 dp 数组 dp[x | p] = min(dp[x | p], dp[x] + 1) 最后的答案是 dp[((111\dots 1)_2)] 即 dp[(1 « len(skills)) - 1]...

ISC'19. 一场大概是退役失败的超算比赛. 我负责的 part 是 AI, 还有万年大锅 HPL, 以及神秘应用. 还有就是订保险订酒店联系赞助商blabla. 本来想帮忙搞 HPCC 的但是没有精力搞不动 ovo AI AI 题是去年的 GB 论文 + 精调模型. 在解决了组委会提供的脚本里的一些性能上的 bug 之后顺利地训了起来. 而且按照原文里在上千个节点上并行训还能收敛来讲, 是可以在现有机器条件下随便数据并行的. (事实证明直接把整个训练集切成 10 个batch 也没有问题) 因为最终要求是精度, 所以请教了一些人, 得到的思路是 数据增强, ensemble. 数据增强不太写得动, 于是改脚本做了 ensemble 的 inference, 效果还不错. 比原文高了几个点. 但也没有特别闪亮的突破性进展. 唯一发现是 bn 用的是 training mode. (原因应该是 tf 的 bn 一直自带 bug, 如果用推理模式精度就是会炸掉) 于是推理的时候也应该 bs 越大越好. 于是就有了 dummy sample inference + unique 的一个脚本. 然后因为没有处理好 “//” 于是组委会还怀疑了半天为什么我的脚本有锅. 哭. 然后就是现场出了一个锅: unseen dataset 发下来一看居然是事前给出的 test set....