清扫完成～这宿舍之前真的是狗窝
3 Likes
看看干净的宿舍（）
2 Likes
你们居然还是独立卫生间吗
是东区吗
3 Likes
2 Likes
其实我也拍了清洗前的宿舍，但是有碍国际观瞻，就不放出来了
4 Likes
看到这个 忽然也不羡慕东区独立卫浴了 这个设施看起来好旧啊
以及 lz 的清洁能力好强 （我也想要这样的室友）
2 Likes
不要羡慕，厕所地面高于宿舍，清洗起来很麻烦的 
2 Likes
这……让我想到了某些不好的画面
4 Likes
下午开会 + 开会 + 摸鱼 
2 Likes
2025 年 6 月 11 日 星期三 天气：阴/阵雨
今天除了上午刷了 leetcode，下午就是开组会 + 开专业毕业会 + 开夏令营宣讲会，合理摸鱼日～
今天的题目都稍微比较难，为了调超时都很难受 
这是一道前缀和 + 滑动窗口题目，アイラちゃん一直很不懂怎么很好地写双指针，因此每次都调试很久+cv 
C++
class Solution {
public:
int maxDifference(string s, int k) {
const int inf = INT_MAX / 2;
int ans = -inf;
for (int x = 0; x < 5; x++) {
for (int y = 0; y < 5; y++) {
if (y == x) {
continue;
}
int cur_s[5]{}, pre_s[5]{};
int min_s[2][2] = {{inf, inf}, {inf, inf}};
int left = 0;
for (int i = 0; i < s.size(); i++) {
cur_s[s[i] - '0']++;
int r = i + 1;
while (r - left >= k && cur_s[x] > pre_s[x] && cur_s[y] > pre_s[y]) {
int& p = min_s[pre_s[x] & 1][pre_s[y] & 1];
p = min(p, pre_s[x] - pre_s[y]);
pre_s[s[left] - '0']++;
left++;
}
ans = max(ans, cur_s[x] - cur_s[y] - min_s[cur_s[x] & 1 ^ 1][cur_s[y] & 1]);
}
}
}
return ans;
}
};
直接走 dijkstra+dfs 将会超时。因为可以构造一个长链连接到最后的全连接图上面，全连接图的 dfs 遍历将出现指数级复杂度，从而超时。
当然也可以用 dijkstra 算法，从 0 计算一次，再从 n-1 计算一次，最后判断 dist2[x]+dist2[y]+w(x,y)=dist1[n-1] 是否成立就可以了。
C++
using namespace std;
using pii = pair<int,int>;
using tiii = tuple<int,int,int>;
using Graph = vector<vector<tiii>>;
#define RELEASE
class Solution {
public:
vector<bool> findAnswer(int n, vector<vector<int>>& edges) {
// Build graph here.
Graph graph(n);
int ind = 0;
for(const auto & edge: edges) {
int u = edge[0], v = edge[1], w = edge[2];
graph[u].emplace_back(v,w,ind);
graph[v].emplace_back(u,w,ind);
ind++;
}
// iterate the graph now.
vector<int> distance(n, INT_MAX / 2);
vector<int> visited(n, 0);
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.emplace(0,0);
vector<vector<int>> pre(n); // Record the pre vertex of the graph.
distance[0] = 0;
while(!pq.empty()) {
const auto [dist, cur] = pq.top();
pq.pop();
if(visited[cur] == 1) continue;
visited[cur] = 1;
// Iterate over the adjacent vertices.
for(const auto & [adj, w, _]: graph[cur]) {
if(distance[adj] > dist + w) {
distance[adj] = distance[cur] + w;
pq.emplace(distance[adj], adj);
}
}
}
vector<char> visited2(n, 0);
vector<bool> ans(edges.size(), false);
auto dfs = [&](this auto && dfs, int from) -> void {
visited2[from] = 1;
for(const auto & [adj, w, index]: graph[from]) {
if(distance[adj] + w != distance[from]) {
continue;
}
ans[index] = true;
if(!visited2[adj]) {
dfs(adj);
}
}
};
if(distance[n-1] == INT_MAX / 2) return ans;
dfs(n-1);
return ans;
}
};
同样 dijkstra+dfs，稍微更改一下上面的就可以了。
要记得开 long long
C++
using plli = pair<long long,int>;
using Graph = vector<vector<pair<int,int>>>;
using ll = long long;
constexpr int MOD = 1e9+7;
#define RELEASE
class Solution {
public:
int countPaths(int n, vector<vector<int>>& roads) {
// Build graph here.
Graph graph(n);
for(const auto & edge: roads) {
int u = edge[0], v = edge[1], w = edge[2];
graph[u].emplace_back(v,w);
graph[v].emplace_back(u,w);
}
// iterate the graph now.
vector<ll> distance(n, LLONG_MAX);
vector<int> visited(n, 0);
priority_queue<plli, vector<plli>, greater<plli>> pq;
pq.emplace(0,0);
distance[0] = 0;
while(!pq.empty()) {
const auto [dist, cur] = pq.top();
pq.pop();
if(visited[cur] == 1) continue;
visited[cur] = 1;
// Iterate over the adjacent vertices.
for(const auto & [adj, w]: graph[cur]) {
if(distance[adj] > (ll)dist + w) {
distance[adj] = (ll)distance[cur] + w;
pq.emplace(distance[adj], adj);
}
}
}
#ifdef DEBUG
for(int i = 0; i < n; i++) {
const auto & adj = pre[i];
cout << i << ": ";
for(int i = 0; i < adj.size(); i++) {
cout << adj[i] << ' ';
}
cout << endl;
}
#endif
if(distance[n-1] == LLONG_MAX) return 0;
vector<int> counts(n, -1);
auto dfs = [&](this auto && dfs, int from) -> int {
if(from == 0) {
counts[from] = 1;
return 1;
} else if(counts[from] > -1) {
return counts[from];
}
counts[from] = 0;
for(const auto & [adj, w]: graph[from]) {
if(distance[adj] + w == distance[from]) {
counts[from] = (counts[from] + dfs(adj)) % MOD;
}
}
return counts[from];
};
return dfs(n-1);
}
};
明天要给学长画图，visio 从未用过，看来得学一学
3 Likes
明天不能再摆烂摸鱼了，要刷 leetcode+ 画图 + 复习高数，星期日去市区玩一玩 
3 Likes
抽象 
3 Likes
在アイラちゃん投简历后接近一个月，突然发来了面试通知，到底是什么问题啊 我还以为我初筛没过呢，突然跟我说初筛过了明天上午 10 点面试，我怎么抱佛脚啊 
JD:
对集群管理、机器学习平台、Kubernetes/Docker 有基本认识，熟悉 Linux 操作系统。乐于助人，耐心细致。计算机科学、软件工程等相关专业。熟练使用 Python/C++，掌握至少一种深度学习训练框架，具备 Megatron/DeepSpeed 框架研发经验者优先。
AI infra 实习
5 Likes
话说アイラちゃん是要保研考研还是就业哎（
4 Likes
保研>考研>就业 目前是这样
所以重心其实在前两者，所以刷 leetcode 防机考，目前一半复习数学 +408，剩下时间做 lab/忙实验室组里的东西
不太想卷，只想找个代码相关的工作最后，读硕士也是想攒实习经历 + 学习一些更多的技术
5 Likes
记录：对着 JD 抱 docker、k 哈基 s 的佛脚
不全面的面筋
Docker & k8s
Docker
-
运行于 OS 上的软件，用于创建，管理，编排容器。可以将开发的应用程序自动部署到容器。
-
与 VM 的区别
-
docker 应用层抽象，容器间通过网络命名空间进行隔离。多个容器共享一个 OS 内核。
-
VM 对物理硬件层抽象，包含独立操作系统。
-
前者为应用环境提供，后者为操作系统环境提供。
-
docker 组件
-
引擎（客户端，服务端），docker 镜像，容器，Registry（镜像仓库）
-
架构：Client（Application）-Server（OS）架构。
Docker 引擎
-
Docker 引擎主要有：docker 客户端，docker 守护进程 (daemon)，containerd 和 runc。
-
现在的 docker 引擎架构：
-
docker client(CLI) 与 docker daemon（API 与其它特性）进行交互。
-
docker daemon 与容器的监督者 (supervisor) 进行交互，有 start|stop|pause…等管理容器。
-
containerd 负责启动没有守护进程的容器 (shim)，每个 shim 运行时有 runc 作为内核源语接口，与运行容器进行交互。
-
Runc: OCI 容器的运行时规范的参考实现。用于创建容器。OCI：运行时标准、容器镜像标准。
-
containerd: 进行容器的生命周期管理——start|stop|pause|rm…。现在也可以用于管理镜像，例如拉取、推送，镜像数据/容器数据的存储。
-
根据镜像启动容器：
docker container run --name ctrl -it alpine:latest sh -
基于 alpine:latest 创建一个名为 ctrl 的容器，并进入 shell 环境。
-
cli 向 docker 守护进程接收指令，指示在 containerd 启动新的容器。
-
containerd 向 runc 传递 OCI 镜像并指示 runc 创建容器并启动 shell 环境。
-
创建容器
-
shim：与 daemon 守护解绑，实现没有 daemon 的容器。当创建新容器后，fork 出来的 runc 进程会退出。随后 containerd-shim 进程将成为容器的父进程。shim 将：
-
保持 stdin 和 stdout 开启。daemon 重启时容器不会因为管道关闭而终止。
-
退出状态反馈给 daemon。
Docker 镜像
-
镜像是一个只读的模板，独立的文件系统，（很像一个停止运行的容器），包括运行容器所需的数据，可以用来创建新的容器。
-
容器从镜像启动后，两者之间就变成了互相依赖的关系。在镜像上启动的容器全部停止之前，镜像是无法删除的。
-
镜像仓库：docker 镜像储存在镜像仓库服务中。一个仓库中可以拥有多个镜像。
-
镜像的命名和标签：采用
:分离。我们可以通过docker image pull <repo>:<tag>来拉取镜像。-a拉取仓库中所有的镜像。 -
一个镜像可以拥有多个标签。
-
filter可以用来过滤。 -
镜像由几个只读的平行层组成。通过
docker inspect可以了解这些层之间的关系。修改或创建新的内容时，将会在这些镜像层之上，创建新的镜像层。通过存储引擎（现在是快照）的方式实现堆栈，对外展示成一个统一的文件系统。 -
可以通过多架构镜像来适配当前运行环境。
--platform指定拉取对应架构镜像，也可以指定运行什么架构的容器。 -
docker image rm <ID>删除对应 ID 的镜像。同时，docker image rm $(docker image ls -q) -f删除所有本地系统内的镜像。
Docker 容器
-
镜像的运行时实例。通过
docker container run <image> <app>运行镜像中的某个应用。-it将当前终端连接到容器的对应终端上，也就是不在幕后运行镜像。 -
容器 vs 虚拟机
-
相同点：都依赖于宿主机，可以是 notebook，可以是物理服务器，也可以是公有云的一个实例。
-
虚拟机：启动后将全部物理资源通过 hypervisor 全部占有，hypervisor 通过将所有的物理资源划分成虚拟资源打包进入 VM 的软件结构中，这样用户可以使用这些虚拟机。虚拟化的是硬件资源。
-
容器：启动后会唤起所选择的操作系统。OS 占有全部的物理资源，在 OS 之上是 docker 引擎，获取 OS 的资源，例如进程树，文件系统和网络栈。接着将资源分割成相互隔离的结构，成为容器。因此虚拟化的是操作系统。
-
运行容器内的应用（例如运行 bash）后，一旦杀死该应用，容器也会退出、终止。因为这是这个容器的主进程。
-
退出容器但是并没有杀死主进程时，容器仍然在运行。此时不能通过 docker run，而是通过
docker exec -it <ID> <app>再次连接到进程。 -
docker container stop终止容器，docker container rm删除容器。数据在容器删除之前将不会被丢弃。
应用容器化
-
编写应用代码
-
dockerfile 创建，包含应用描述，依赖，以及如何运行应用。
-
对 dockerfile 进行
docker image build。 -
docker 将应用程序构建到 docker 镜像中。
对应的一些指令
-
from: 指定基础镜像作为基础镜像层。
-
label: 自定义的标签，是一组 KV 对。
-
run: 执行基础镜像层的应用，可能会安装新的应用，也是一个镜像层。
-
copy: 选取文件复制到当前镜像中，并且新建一个镜像层来存储。
-
EXPOSE: 暴露端口。
-
ENTRYPOINT: 指定入口程序。不新增镜像层。
-
docker image build -t <image>:<tag>. -
增加新的 tag 用于推送：需要
-
仓库服务，仓库，镜像标签。
-
docker image tag <image>:<tag> <repo>/<image>:<tag> -
docker image push推送到上游。
docker compose
-
单引擎进行多容器应用的部署与管理。
-
compose 文件可以使用 yaml 或者 json（前者是后者的子集）来编写。默认为
docker-compose.yml。 -
docker-compose up启动应用。 -
文件包括：version 版本，service 服务，networks 创建新的网络，volumes 创建新的卷。
docker swarm
-
集群管理。一个 swarm 由一个或多个 docker 节点构成。这些节点可以是服务器，虚拟机，树莓派或者云实例。要求通过可靠网络连接。
-
节点将会被配置成管理节点 (Manager) 或者工作节点 (worker)。
-
管理节点：负责控制平面，监控集群状态，分发工作任务，管理工作节点。
-
工作节点接受来自管理节点的任务并执行。
k8s(kubernetes)
-
开源的容器集群管理，提供集群的自动部署，扩缩容，维护等功能。分为管理节点和工作节点，类似于 docker swarm。
-
通过 CI/CD(持续集成/持续交付) 自动化流程，保证环境一致性 (CI)，并确保集群可以随时部署 (CD).
组件
-
etcd: 集群状态。
-
apiserver: 提供资源操作的唯一入口，提供认证，授权，访问控制，API 注册，发现等机制。
-
controller manager: 集群状态维护。
-
scheduler: 资源调度，根据预定调度策略将 pod 调度到相应的机器上。
-
kubelet: 负责维护容器的生命周期，同时也负责卷和网络的管理。
-
runtime: 镜像管理，pod 和容器的真正运行。
-
kube-proxy: service 提供 cluster 内部的服务发现和负载均衡。
一些概念
-
Pod：最小的可部署单元。包含一个或者多个紧密耦合的容器。Pod 的主要作用是提供一个环境，可以让容器共享网络和存储资源。并且提供了容器间通信、生命周期管理等功能。
-
Deployment：部署无状态应用程序。可以随时获知当前 Pod 的部署进度。
-
service: 定义了 Pod 的逻辑集合和访问该集合的策略，是真实服务的抽象。提供了一个统一的服务访问入口和代理服务发现机制，关联多个相同 label 的 pod。
-
volume: 卷宗，一个可以被多个容器共同访问的共享目录，定义在 pod 上，可以被一个或多个 pod 中的容器挂载到某个目录下。
-
namespace: Multi-tenant 多租户隔离，将集群内部资源对象分配到不同的 namespace 中，形成逻辑上不同的小项目，小组，用户组，便于共享集群资源的同时还能被分别管理，精细化管理的粒度。
-
1Ingress：通过定义规则来管理从外部访问集群内 Service 的流量。
5 Likes
已收藏 (?)
2 Likes
面试超级短（35min），之前抱得佛脚一点没用上，总结如下。（请大家不要随便传播谢谢）
总结
中国电信：AI infra 实习
没有手撕算法部分。（国企这么好的吗）
O、根据简历自我介绍
一、拷打项目：
- 操作系统项目的简单介绍？
- 页表是怎么配置的？（内核启动时配置高页表，随后配置低地址页表，随后启动用户态程序）
- 介绍一下 linux 如何管理内存。(伙伴系统和 slab 分配器)
3.1 两者的区别是什么？（slab 分配器将内存块作为对象进行管理，进行小内存的分配，较大内存的分配通过页表进行。管理对象的生命周期和分配，这样不会在使用完内存后真正释放内存，降低时延和开销。伙伴系统是真正进行内存管理的工具，减少外部内存碎片，通过 2^n 进行分配防止内存碎片。）
3.2 slab 分配器的管理数据结构？（红黑树）。 - IPC 通信方式你选择了什么？（共享内存，这样每个进程访问相同的物理内存，提高进程通信效率）
4.1 每个进程是怎样访问相同的物理内存的？（通过自身的虚拟地址空间，以及自身的页表通过 TLB 的方式来进行地址翻译成为物理内存进行访问）。
小结：操作系统问的不深。没有问到特别高深的技术（写时拷贝，锁，时钟中断 IRQ 等）
二、拷打项目：
- 介绍以下你的阵列是如何进行加速的？
（脉动阵列 (systolic array)，专门为矩阵运算进行翻译和加速。矩阵运算取的是两个矩阵的一行、一列进行乘累加操作，因此可以让矩阵的一行自左向右进入乘累加单元，让另一个数据自上而下流入乘累加单元，最后进行操作，中间值存储在寄存器之中。） - 对于大的矩阵乘法应该怎么做？（分块，计算出分块矩阵值后进行存储）
- 对于大型矩阵（分块矩阵）你的项目是否做到了 Cache 的优化？你提到了分块矩阵的存储（很遗憾没有，不过可以参考 flash attention 的方式，进行条块化和重计算后通过 HBM 优化）
建议：项目还要进行优化和深化。
三、深度学习、机器学习系统
- 你了解 Megatron 吗？（是一个大规模 LLM 训练系统，通过结合数据并行，张量并行，流水线并行的 PTP 混合并行方式来进行的系统。）
- 介绍一下 Megatron v1，v2 和 v3 是怎么进行优化的。
megatron v1 主要提出了张量并行的方式来优化 GPU 的内存不足问题。某些模型的权重 + 中间激活值太大无法储存在 GPU 中，因此将他们进行分割，分别储存在不同的节点当中。这样就可以减少不同节点之间的内存不足问题。
缺陷是没有考虑到 TP 所带来的大量通信开销问题。
2.1 向量并行一般有哪些方式？（行并行，列并行），为什么采取后者？（具有非线性激活，无法通过简单的线性防止进行分块矩阵计算，因此需要进行列并行处理）
megatron v2 采用了张量并行，数据并行和流水线并行的方式进行。
2.2 流水线并行进行了什么优化？（1F1B 交叠方式进行，这样显著减少了运算之间流水线的气泡占比）。
2.3 工作节点数目和数据并行，张量并行和流水线并行的关系？（右边三个东西的乘积就是所需的工作节点数）
2.4 microbatch 太大了有什么问题？太小了有什么问题？（microbatch 太大会导致单个节点计算缓慢，增加流水线周期。太小会导致频繁地通信，通信开销增大导致严重的通信开销）
megatron v3 采用激活重计算。因为我没有时间读完因此直接说了面试官也就没有拷打这一部分 QAQ
四、介绍以下目前的慢节点项目（组里）
- 检测到慢节点后如何恢复？（搬出了 Falcon 提出的解决办法，4 层级恢复：1.继续观察性能 2.数据重新划分 3.并行拓扑重新划分 4.检查点重启）
- 怎样才能够进行重新调度？你们有了具体方案吗？（诚实回答目前还在调研中，雏形的想法是通过 kv 的方式简化保存的内容，随后再从检查点中重新恢复。）
- 对于链路的检测和缓解，你认为应该采取什么方案？（对于拥塞，部署在网络层的全局拥塞感知已经在 Sigcomm14 上提出。通过 clos 两层架构，在叶子结点间传递相对应的拥塞指标进行。第一个是分布式架构才可以正确进行链路调度否则会出现问题（举例说明了 ECMP 性能降级），第二个是网络层可以避免绕开内核栈的问题，降低应用层复杂度）
- 目前你们将采用怎样的方式进行？（RDMA 传递，绕开内核直接写入内存）
五、有什么想问的问题？（公司目前的研发目标？有自研 teletron（感觉是 megatron 套皮没有什么新的技术在里面），也在多个层级上有进行研究）
六、评价一下自己？（目前自己的知识还比较碎片化，觉得系统的研究需要有完整的成体系的知识，以及更加深刻的了解，此外对于分布式的知识掌握仍然在入门，需要更加细致地了解相关知识）。
2 Likes
下午要把 leetcode 刷了，一日无 coding 则手生，两日无 coding 则手废矣，等到天晴了再出去玩一天
下周二二面，啊~~~~好累
4 Likes