刘芷溢
最近更新
README
CuTe FlashAttention-2 case-study benchmark This directory preserves the exact teaching kernel, benchmark harness, raw results, and figure generator used by the corresponding tom-jerr blog post.
CuTe 详解：以 FlashAttention-2 拆解 Layout、TiledCopy 与 TiledMMA
以一份可运行的 FlashAttention-2 前向 Kernel 为贯穿案例，从坐标函数和线程所有权出发，详解 CuTe 的 Layout algebra、Tensor、TiledCopy、TiledMMA、寄存器重解释与流水线，并用正确性和性能实验检查这些抽象最终生成了什么。
LLM 量化综述：数据格式、PTQ 与 QAT 的算法演进
从 INT8、FP8、INT4、MXFP4、NVFP4 的表示范围与舍入误差出发，按 8 bit、4 bit 和低于 4 bit 梳理 PTQ/QAT，解释各方法解决的问题、相对前作的创新、核心优化与数值稳定性，并对应到 llm-compressor 的工程实现。
从 EAGLE 到 DFlash 2：SGLang 与 SpecForge 的投机解码训练和推理
沿 EAGLE、EAGLE-2、EAGLE-3、DFlash、DSpark 和 DFlash 2 的演进，解释 draft 的训练目标、数据对齐、推理状态与验证预算，并对照 SpecForge 训练和 SGLang serving 源码串起完整流程。
SGLang HiCache：组件、工作流与 L1/L2/L3 读写时序
从 HiRadixCache、HiCacheController、Host KV Pool 与 Storage Backend 的职责出发，沿 Scheduler 主循环拆解 L3 query、hit、prefetch、L2 load、L2 write 和 L3 write 的准确时序。
从 Bank Conflict 到 CUTLASS Swizzle：推导 ldmatrix 的访存布局
从 shared memory 的 32 个 bank 出发，逐地址推导 ldmatrix 的行地址、寄存器分配与 bank conflict，再解释 CUTLASS 的 XOR permutation、CuTe Swizzle 参数和 producer/consumer 布局约束，附交互图与可运行验证程序。
CUDA 中的 ILP 与 MLP：从依赖链到延迟隐藏
从 warp scheduler、依赖链与 Little's Law 出发，区分 CUDA 中的指令级并行和内存级并行，并结合 GEMM、GEMV、FlashAttention、可对照的 Kernel 与 Nsight Compute 指标说明何时以及如何提升二者。
cuda basic
CUDA Basic Concept CUDA Async Copy & Pinned Memory 通常情况下，CPU 分配的内存是 Pageable（可分页） 的。操作系统为了节省物理内存，可能会把这些内存交换到磁盘上。 当你要把数据从 Pageable 内存拷贝到 GPU 时，CUDA 驱动其实做了一个幕后动作： 先在系统中申请一块临时存储区（即 Pinned Memory）。 将数据从 Pageable 内存拷贝到这块 Pinned Memory。 通过 DMA（直接内存访问） 将数据从 Pinned Memory 传给 GPU。 实际上多了一次 CPU 侧拷贝，所以性能会受到...
分类
187 篇文章
README
CuTe FlashAttention-2 case-study benchmark This directory preserves the exact teaching kernel, benchmark harness, raw results, and figure generator used by the corresponding tom-jerr blog post.
CuTe 详解：以 FlashAttention-2 拆解 Layout、TiledCopy 与 TiledMMA
以一份可运行的 FlashAttention-2 前向 Kernel 为贯穿案例，从坐标函数和线程所有权出发，详解 CuTe 的 Layout algebra、Tensor、TiledCopy、TiledMMA、寄存器重解释与流水线，并用正确性和性能实验检查这些抽象最终生成了什么。
LLM 量化综述：数据格式、PTQ 与 QAT 的算法演进
从 INT8、FP8、INT4、MXFP4、NVFP4 的表示范围与舍入误差出发，按 8 bit、4 bit 和低于 4 bit 梳理 PTQ/QAT，解释各方法解决的问题、相对前作的创新、核心优化与数值稳定性，并对应到 llm-compressor 的工程实现。
从 EAGLE 到 DFlash 2：SGLang 与 SpecForge 的投机解码训练和推理
沿 EAGLE、EAGLE-2、EAGLE-3、DFlash、DSpark 和 DFlash 2 的演进，解释 draft 的训练目标、数据对齐、推理状态与验证预算，并对照 SpecForge 训练和 SGLang serving 源码串起完整流程。
SGLang HiCache：组件、工作流与 L1/L2/L3 读写时序
从 HiRadixCache、HiCacheController、Host KV Pool 与 Storage Backend 的职责出发，沿 Scheduler 主循环拆解 L3 query、hit、prefetch、L2 load、L2 write 和 L3 write 的准确时序。
从 Bank Conflict 到 CUTLASS Swizzle：推导 ldmatrix 的访存布局
从 shared memory 的 32 个 bank 出发，逐地址推导 ldmatrix 的行地址、寄存器分配与 bank conflict，再解释 CUTLASS 的 XOR permutation、CuTe Swizzle 参数和 producer/consumer 布局约束，附交互图与可运行验证程序。
CUDA 中的 ILP 与 MLP：从依赖链到延迟隐藏
从 warp scheduler、依赖链与 Little's Law 出发，区分 CUDA 中的指令级并行和内存级并行，并结合 GEMM、GEMV、FlashAttention、可对照的 Kernel 与 Nsight Compute 指标说明何时以及如何提升二者。
cuda basic
CUDA Basic Concept CUDA Async Copy & Pinned Memory 通常情况下，CPU 分配的内存是 Pageable（可分页） 的。操作系统为了节省物理内存，可能会把这些内存交换到磁盘上。 当你要把数据从 Pageable 内存拷贝到 GPU 时，CUDA 驱动其实做了一个幕后动作： 先在系统中申请一块临时存储区（即 Pinned Memory）。 将数据从 Pageable 内存拷贝到这块 Pinned Memory。 通过 DMA（直接内存访问） 将数据从 Pinned Memory 传给 GPU。 实际上多了一次 CPU 侧拷贝，所以性能会受到...
cuda performance checklist
CUDA Performance Checklist DRAM vs SRAM DRAM由1个晶体管和1个电容器构成；SRAM: 由6个晶体管构成 SRAM 比 DRAM 更快，但也更贵；SRAM 占用更多空间且发热更多； 实际上SRAM就对应了GPU的Shared Memory，而DRAM对应的则是Shared Memory。 Performance Checklist 合并全局内存访问（Coalesced Global Memory Access） 最大化占用率（Maximize occupancy） 理解是内存受限还是计算受限（Understand if memory or comput...
quantization cuda
Quantization CUDA 动态量化流程 (Dynamic Quantization Flow): 权重和激活都从浮点开始 权重在预处理阶段量化 激活在运行时量化 使用Int8进行乘法运算 使用Int32进行累加 最后rescale回浮点数 未量化 (Not Quantized): 权重和激活都保持浮点格式 所有运算（乘法和累加）都使用浮点数进行 仅权重量化 (Weight Only Quantization): 权重在预处理阶段量化 随后立即反量化回浮点数 激活保持浮点格式 乘法和累加都使用浮点数进行 最后有一个rescale步骤 Dynamic Quantization 数学表达：...
server_profile
Nsys Profiler Load Model cudamemgetinfo 执行了 373 s，应该是 Orin 的内存探测有问题，可能是其他系统组件影响了这个函数的性能。 使用文件进行 mmap，所以会出现 cudamemasync 之后进行 cuda sync 的情况，导致性能下降。 Forward 也会出现大量的 H2D 拷贝 主要拷贝的不是模型权重，也不是大块 KV cache，而是这些每个 ubatch 都会变化的输入： tokens: 当前 prefill micro-batch 的 token id pos: 每个 token 的 position k_idxs / v_id...
deepep_architecture_notes
DeepEP 架构与实现笔记 本文整理 DeepEP 相关官方文档与源码，重点解释 V2 ElasticBuffer 架构，同时把 V1 legacy 的 NVSHMEM/IBGDA 路径作为对照。源码基于官方仓库 deepseek-ai/DeepEP 的 main 分支临时克隆版本，提交为 d4f41e4e93602a15e95f55f6ee8df8f1aaa0e4bb。 主要参考： DeepEP README DeepEP V1 legacy docs NVSHMEM install guide V1 Python legacy Buffer V1 C++ legacy runtime V...
deepseek
Deepseek Details MoE node-limited routing 每个 token 最多只发到有限个 node，这些 node 根据该 node 上专家的高 affinity 分数之和来选。目的非常直接，就是把跨节点 all-to-all 压下来，给 DualPipe + overlap 创造条件，最终接近计算通信重叠。再配合： 每 step 依据 batch 负载更新 expert bias，而不是靠大 aux loss 硬拉均衡。 再补一个很小的 sequence-wise aux loss，防单条序列极端失衡。 所以训练和推理都可以做到 no token droppin...
llm-compressor框架解析
LLM Compressor 量化原理、架构与算法执行流程 本文整理 llm-compressor 的量化体系：它如何把不同 PTQ / GPTQ / AWQ / SmoothQuant / AutoRound / FP8 / FP4 / KV cache quant 算法封装成 Modifier，如何通过 event 和 hook 在校准前向中收集统计量，如何逐层压缩模型，最后如何保存成 vLLM 可加载的 compressed-tensors checkpoint。 整体阅读顺序： 先理解量化的基础公式和粒度。 再看 llm-compressor 的整体架构、pipeline、event ...
longcontext
Long Context Attention 长上下文注意力（Long Context Attention）是指在处理长序列数据时，如何高效地计算注意力机制的一种方法。传统的注意力机制在处理长序列时会面临计算和内存的挑战，因为它需要计算所有位置之间的关系，导致计算复杂度为O(n^2)。为了克服这个问题，研究人员提出了多种优化策略，如Ring Attention和Striped Attention，以及后续的 Tree Attention等方法。 Motivation “挑战：我们耗尽了内存” 引用自Ring Attention（2023年，Hao Liu等人的研究）： “对于一个隐藏层大小为1...
optimization_tech
CUDA Graph 原理 CUDA Graph 将一段 GPU kernel 序列录制为静态 DAG，之后只需一次 CPU launch 即可重放整个计算流，以此消除逐个 kernel launch 的 CPU 开销。在此基础上，我们更进一步理解 CUDA Graph 的一些核心机制。 构造过程 Capture：捕获或者是录制 CUDA Graph。 调用 cudaStreamBeginCapture() 后，CUDA runtime 进入录制模式——后续所有提交到该 stream 的操作（kernel launch、memcpy、memset 等）都不会真正执行，而是被记录为 DAG 中的...
pip&uv
Pip & uv 使用 Pip 基础使用 pip install xxx 从 PyPI 下载合适的版本(一般是最新，如果没有 requirement) 优先使用 wheel 构建，如果没有本地编译 pip 会创建一个临时隔离环境 只安装 pyproject.toml 里声明的 build-system.requires 当前环境的 torch / numpy / cuda 都不可见 Pip 相关选项 —no-build-isolation：构建时直接用当前环境里的包 —no-use-pep517：不用 PEP 517 新构建系统，走 setup.py install —no-deps：...
python项目构建
Python 项目构建 现代 Python 项目基本围绕 PEP 517/518/621： PEP 518：构建工具写在哪里？构建前要先装什么？ PEP 517：pip / uv 应该如何“调用构建后端”？ PEP 621：项目元数据应该如何标准化地写？ 常见 python project 构建配置文件 pyproject.toml：项目元数据 + 构建配置的统一入口 build backend（构建后端）：真正构建项目二进制包的实现（setuptools / hatchling / flit / poetry-core…） build frontend（构建前端）：调用后端去构建 wheel...
Create Ann Index
Create Ann Index Ann Index Manager 在 Storage Daemon 中设计一个VectorIndexManager单例对整个 Storaged 中的 Ann Index 进行管理。 Ann Index 的生命周期： 创建：通过 CreateTagAnnIndex 请求创建 Ann Index。 除非删除，否则会一直在内存中维护，在退出时需要持久化到磁盘，同时重启系统后需要从磁盘中加载已经存在的 Ann Index。 使用：在查询时使用 Ann Index 进行加速。 删除：通过 DropTagAnnIndex 请求删除 Ann Index。 更新：通过 Up...
DDL for vector type
Implement DDL for Vector Type Implement CREATE TAG for Vector Type Thrift: Modify ColumnTypeDef Use type_lenght to indicate the dimension of the vector type.
DML for vector type
The Process of DML for Vector Type(Insert for example) Overview Graphd Process Insert 语句首先由 Graphd 从 client 接收，Graph Service 将 Query、Session、Storage 等打包成 Request Context，随后将 Request Context 打包成 Query Context，创建 Query Instance 随后开始执行 parse、validate、optimize、execute 整个流程。 经过 Graphd 的 validate，进入 Plann...
Match for vector property
Match for Vector Property Simplest match case MATCH (v) RETURN v LIMIT 3; Process MatchValidator 验证阶段 在验证阶段，节点 (v) 被识别为： 没有指定标签的节点模式 没有属性过滤条件 别名为 v，类型为 AliasType::kNode MatchPathPlanner 路径规划阶段 StartVidFinder 寻找起始点 在 MatchPathPlanner::findStarts() 中 // 遍历所有的 StartVidFinder for (auto& finder : sta...
wal for vector type
WAL for Vector Type WAL Scenarios 场景 1: 新节点加入集群 初始状态 集群状态： - Leader: Node1 (term=5, lastLogId=100) - Follower: Node2 (term=5, lastLogId=100) - Follower: Node3 (term=5, lastLogId=100) - 新节点: Node4 (term=0, lastLogId=0) 重放流程 步骤 1: 新节点启动 // Node4 启动 void RaftPart::start(std::vector<HostAddr>&...
summary
项目报告 项目名称：为 NebulaGraph 支持向量近似邻检索 项目导师：曹志鹏 申请人：刘芷溢 日期：2025.09.25 邮箱：lzy_CS_LN@163.com 项目信息 项目名称 为 NebulaGraph 支持向量近似邻检索 方案描述 在 NebulaGraph 分布式图数据库中原生集成向量数据存储与近似最近邻（Approximate Nearest Neighbor, ANN）检索能力。确保设计的语法兼容 NebulaGraph 现有的查询语言，查询语句兼容 OpenCypher 语法规范。 实现向量数据类型并支持其持久化。 实现新的数据类型 VECTOR 实现向量类型的存储，...
8.a kv life
A Vertex Life in Nebula Graph Storaged 在 Nebula Graph 中，一个 Vertex 的生命周期从创建到删除，涉及到多个组件和流程。本文将详细介绍一个 Vertex 的生命周期，由此来借鉴实现 VECTOR 类型属性的存储和处理流程。 Vertex Creation 在 Nebula Graph 中，Vertex 的创建通常通过 AddVerticesProcessor executor 来完成。它会将 Vertex 要插入的数据已经元数据打包成 raft-wal log，提交到 Raft Part 中，最后在 Part::commitLogs()...
1-Container
1 Container 1.1 std::vector 迭代器在vector插入超过容量后，自动扩容时失效 引用语义在使用 span 时必须谨慎。将一个新元素插入 vector 中,该 vector 中保存了跨度所引用的元素。由于 span 的引用语义,若 vector 分配新的内存，会使所有迭代器和指向其元素的指针无效,所以重新分配也会使引用 vector 元素的 span 失效。span 指向了不再存在的元素。 出于这个原因,需要在插入前后都要仔细检查容量 (分配内存的最大元素数量)。若容量发生变化,则重新初始化 span .
2-Algorithm
2 Algorithm 2.1 std::transform std::transform applies the given function to the elements of the given input range(s), and stores the result in an output range starting from d_first.
3-Iterator
3 Iterator 输入迭代器：只能用来读取指向的值；当该迭代器自加时，之前指向的值就不可访问。 std::istream_iterator 就是这样的迭代器。 前向迭代器：类似于输入迭代器，可以在指示范围迭代多次 std::forward_list 就是这样的迭代器。就像一个单向链表一样，只能向前遍历，不能向后遍历，但可以反复迭代。 双向迭代器：这个迭代器可以自增，也可以自减，迭代器可以向前或向后迭代。 std::list, std::set 和 std::map 都支持双向迭代器。 随机访问迭代器：与其他迭代器不同，随机访问迭代器一次可以跳转到任何容器中的元素上，而非之前的迭代器，一次只...
4-Filesystem
4 FileSystem 文件系统库提供对文件系统及其组件（例如路径、常规文件和目录）执行操作的工具。 文件系统库最初开发为boost.filesystem ，并作为技术规范 ISO/IEC TS 18822:2015发布，最终于 C++17 合并到 ISO C++ 中。目前，boost 实现在比 C++17 库更多的编译器和平台上可用。 如果对此库中的函数的调用引发文件系统竞争，即当多个线程、进程或计算机交错访问和修改文件系统中的同一对象时，则行为未定义。 4.1 定义 file：保存数据的文件系统对象，可以写入、读取或两者兼而有之。文件具有名称、属性，其中之一是文件类型： 目录：充当目录条...
5-View
5 View 通常若引用范围的元素修改,则视图的元素也会修改。 若视图的元素修改,则引用范围的元素也会修改。 视图通常用于在特定的基础上,处理基础范围的元素子集和/或经过一些可选转换后的值。例 如,可以使用一个视图来迭代一个范围的前五个元素 for (const auto& elem : std::views::take(coll, 5)) { ..
6-Span
6 Span 💀 这段代码会导致未定义的行为,因为基于范围的 for 循环中存在一个 bug,在对临时对象的引用上进行迭代时会使用已经销毁的值 // for the last 3 returned elements: for (auto s : std::span{arrayOfConst()}.last(3)) // fatal runtime ERROR.
C++-泛型算法
泛型算法 概述 不直接操作容器，遍历由两个迭代器指定的一个元素范围进行操作 迭代器令算法不依赖于容器 算法依赖于元素类型的操作 初识泛型算法 只读算法 find accumulate int sum = accumulate(vec.begin(),vec.end(), 0); // 第三个参数是和的初值 string sum = accumulate(v.cbegin(), v.cend(), string("")); // string定义了+运算符 count equal：确定两个序列是否保存相同的值，接受三个迭代器；假定每个元素在第二个序列中都有一个与之对应的元素（...
C++-关联容器
关联容器 关联容器支持高效的关键字查找和访问；主要的两个关联容器是map和set 使用关联容器 set和map的使用 map<string, size_t> word_cnt; set<string> exclude = {"The", "But"}; string word; while(cin >> word) // 只统计不在exclude中的单词 if(exclude.find(word) == exclude.end()) ++word_cnt[word]; 概述 关联容器不支持顺序容器的位置相关的操作，例如...
C++-动态内存
动态内存 静态内存保存局部static对象，类static数据成员以及任何定义在任何函数之外的变量 全局对象程序启动时分配，在程序结束时销毁 动态内存与智能指针 每个程序有一个内存池，叫做自由空间或堆 动态对象的生存期由程序来控制 智能指针负责自动释放所指向的对象 share_ptr允许多个指针指向同一个对象 unique_ptr则“独占”所指向的对象 weak_ptr是一种弱引用，指向shared_ptr所管理的对象 shared_ptr类 是一个模板，默认初始化的智能指针中保存着一个空指针 make_shared 最安全的分配和使用动态内存的方法 在动态内存中分配一个对象并初始化它；返回指...
C++-拷贝控制
拷贝控制 拷贝、赋值与销毁 拷贝构造函数 第一个参数是自身类类型的引用，所有其他参数均有默认值 逐个拷贝非static成员；内置类型成员直接内存拷贝；类类型成员，调用拷贝构造函数拷贝 string dots(10, '.'); // 直接初始化 string s(dots); // 直接初始化 string s2 = dots; // 拷贝初始化 string null_book = "99" // 拷贝初始化 拷贝初始化 “=” 一个对象作为实参传递给一个非引用类型的形参 从一个返回类型为非引用类型的函数返回一个对象 用花括号列表初始化一个数组中的元素...
C++-重载运算和类型转换
重载运算和类型转换 基本概念 重载的运算符是成员函数时，this绑定到左侧运算对象；成员运算符函数的显式参数数量比运算对象的数量少一个 对于一个运算符函数来说，它或者是类的成员或者至少含有一个类类型的参数 // 调用了非成员函数 data + data2; operator+(data, data2); // 调用了成员函数 data1 += data2; data1.operator+=(data2); 使用与内置类型一致的含义 IO类型保持一致 如果定义了operator==，应该定义operator!= 包含一个内在的单序比较，定义operator <, operator>…...
15_面向对象程序设计
OOP.
C++-变量和基本类型
变量和基本类型 1.基本内置类型 算数类型和空类型 bool, char, wchar_t, char16_t, char32_t, short, int, long, long long, fliat, double, long double w_char_t确保可以存放机器最大扩展字符集中的任意一个字符 char16_t，char32_t为Unicode字符集服务 一般float 32bit，double 64bit，long double 96/128bit 带符号类型和无符号类型 int, short, long, long long前直接加unsigned signed char和u...
C++-字符串、向量、数组
字符串、向量、数组 using声明 一般头文件不应该包含using声明 String 直接初始化和拷贝初始化 等性判断对字母的大小写敏感 如果表达式中使用size()（返回一个无符号整数），避免使用int 字面值和对象相加至少+号两边有一个是string对象 Vector 迭代器 begin()：表示第一个元素, end()：表示尾元素的下一个元素，指示的是根本不存在的尾后元素 ==, !=如果两个迭代器指向相同的元素或者都是同一个容器的尾后迭代器则相等 迭代器类型 iterator是可以操纵的类型 const_iterator能读取但不能修改该迭代器指向的元素值 任何改变vector容量的操...
C++-表达式
表达式 左值和右值 C++表达式要么为左值要么为右值 赋值运算符需要一个左值作为左侧运算对象，得到的结果仍然是一个左值 取地址符：得到的指针是一个右值 内置解引用符和下标运算符，迭代器解引用符，string & vector的下标运算符均是左值 内置类型和迭代器的递增递减运算符作用于左值运算对象 递增和递减运算符 作用于左值运算对象，前置版本将对象本身作为左值返回；后置版本作为右值返回 不建议使用后置版本 类型转换 算数转换 整型提升：把小整数类型转换成较大的整数类型 其他隐式类型转换 数组转换成指针 指针的转换转换成bool 转换成常量 类类型定义的转换 string s,t = &...
C++-语句
语句 switch 内部变量定义，使用花括号；只定义在该块内 try语句块和异常处理 throw表达式 try{…}catch(runtime_error e){…} 标准异常 excception：头文件中定义了通用的异常类exception。只报告异常的发生，不提供额外的信息 stdexcept：定义了集中常用的异常类 new头文件定义了bad_alloc type_info头文件定义了bad_cast异常类型 异常类型只有一个what成员函数，返回值是一个C风格字符串 Header guards(include guard) 避免一个头文件被多次引用 int getSquareSides...
C++-函数
函数 参数传递 传值参数 实参的值不变 初始值被拷贝给变量 传指针 拷贝的是指针，两个指针不同，但指向相同的对象 可以改变实参的值 传引用参数 绑定了初始化它的对象 避免拷贝 函数不需要改变引用形参的值，声明成常量引用 const形参和实参 实参初始化形参时会忽略掉顶层const 尽可能使用常量引用 数组形参 void print(const char *cp); void print(const int *beg, const int *end); // 传递指向数组首部和尾部的指针 void print(const int ia[], size_t size); void print(in...
C++-类
类 this指针 成员函数通过this指针访问调用它的那个对象 this形参是隐式定义的；this是一个常量指针 const成员函数 默认情况下，this的类型是指向类类型非常量版本的常量指针 需要将this声明为指向常量的指针 std::string isbn() const {return this->bookNo;} 构造函数 只有类没有声明任何构造函数时，编译器才会自动生成默认构造函数 =default含义 作用完全等同于之前使用的合成默认构造函数 class和struct 希望定义的类的所有成员是public时，使用struct 希望成员是private的，使用class 友元...
C++-IO库
IO库 IO class IO对象无拷贝，无赋值：不能作为参数和返回值 读写一个IO对象会改变其状态，传递和返回的引用不能是const 条件状态 管理输出缓冲 程序崩溃，输出缓冲区不会被刷新 每个输出流都管理一个缓冲区 缓冲刷新 程序正常结束，作为main函数的return操作一部分，缓冲被执行 缓冲区满时，需要刷新缓冲 endl等操纵符，显示刷新缓冲区 设置unitbuf来清空缓冲区 一个输出流可能被关联到另一个流。这种情况下，读写被关联的流时，关联到的流的缓冲区会被刷新 endl：输出换行符，刷新缓冲区 flush：刷新缓冲区，不附加任何额外字符 ends：输出一个空字符，刷新缓冲区 co...
C++-顺序容器
顺序容器 概述 vector, deque在内存中连续保存；list不支持<运算 通常，使用vector是最好的选择 随机访问元素，用vector或deque 容器中间插入或删除，用list或forward_list 头尾插入或删除，用deque 容器库 顺序容器几乎可以保存任意类型的元素；也可以保存容器的容器 // noDefault是一个没有默认构造函数的类型 vector<noDefault> v1(20, init); // 提供元素初始化器 vector<noDefault> v2(10); // 必须提供一个元素初始化器 容器操作 迭代器 迭代器范围由...
C++-Makefile语法学习
Makefile 使用条件判断 libs_for_gcc = -lgnu normal_libs = foo: $(objects) ifeq ($(CC),gcc) $(CC) -o foo $(objects) $(libs_for_gcc) else $(CC) -o foo $(objects) $(normal_libs) endif 使用函数 字符串处理函数 $(subst <from>,<to>,<text>) • 名称：字符串替换函数 • 功能：把字串 <text> 中的 <from> 字符串替换成 <to>...
C++-并发与多线程编程
并发与多线程编程 线程传值 使用 detach() 分离两个线程可能会导致主线程在子线程结束前就跑完了 char*变量在线程中地址相同；使用string类型引用来解决；创建 m_thread 对象的时候复制一份临时变量 隐式转换和显示转换 隐式转换，对象在子线程进行构造；如果detach后main线程先结束；直接失败 显示转换，对象的构建过程和拷贝过程都是在主线程中完成的，这就确保了子线程在使用该参数时是安全的 临时变量传参 如果传递int这种简单类型，推荐使用值传递，不要用引用； 如果传递类对象，要避免使用隐式类型转换，必须在代码中显式转换（相当于创建一个临时变量），然后在函数参数里，用引用...
1-grep
3.1 grep 全面搜索正则表达式并把行打印出来）是一种强大的文本搜索工具，它能使用正则表达式搜索文本，并把匹配的行打印出来。用于过滤/搜索的特定字符。 3.1.1 基本命令选项 -a --text # 不要忽略二进制数据。 -A <显示行数> --after-context=<显示行数> # 除了显示符合范本样式的那一行之外，并显示该行之后的内容。 -b --byte-offset # 在显示符合范本样式的那一行之外，并显示该行之前的内容。 -B<显示行数> --before-context=<显示行数> # 除了显示符合样式的那一行之外，并...
2-sed
3.2 sed 3.2.1 正则表达式 基本正则表达式 .，表示匹配任意一个字符，除了换行符，类似 Shell 通配符中的 ?； *，表示前边字符有 0 个或多个； .*，表示任意一个字符有 0 个或多个，也就是能匹配任意的字符； ^，表示行首，也就是每一行的开始位置，^abc 匹配以 abc 开头的字符串； ，表示行尾，也就是每一行的结尾位置，} 匹配以大括号结尾的字符串； {}，表示前边字符的数量范围，{2}，表示重复 2 次，{2,}重复至少 2 次，{2,4} 重复 2-4 次； []，括号中可以包含表示字符集的表达式 （二）扩展正则表达式 扩展正则表达式使用频率上没有基本表达式那么高...
3-awk
3.3 awk awk会根据空格和制表符，将每一行分成若干字段，依次用1、2、$3代表第一个字段、第二个字段、第三个字段等等 print命令里面，如果原样输出字符，要放在双引号里面。 3.3.1 基本用法 awk action filename awk '{print $0}' demo.txt 3.3.2 内置函数 变量NF表示当前行有多少个字段，因此$NF就代表最后一个字段 变量NR表示当前处理的是第几行 toupper()用于将字符转为大写 tolower()：字符转为小写。 length()：返回字符串长度。 substr()：返回子字符串。 sin()：正弦。 c...
4-find
3.4 find 从每个指定的起始点 (目录) 开始，搜索以该点为根的目录树，并按照运算符优先级规则从左至右评估给定的表达式，直到结果确定，此时find会继续处理下一个文件名。 3.4.1 语法 find [-H] [-L] [-P] [-D debugopts] [-Olevel] [起始点...] [表达式] -name pattern：按文件名查找，支持使用通配符 * 和 ?。 -type type：按文件类型查找，可以是 f（普通文件）、d（目录）、l（符号链接）等。 f 普通文件 l 符号连接 d 目录 c 字符设备 b 块设备 s 套接字 p Fifo -size [+-]size...
Asyncio
Python 中的Asyncio 使用单线程 + 事件循环 (Event Loop)。这是一种协作式多任务。 代码执行到 await（比如等待网络响应）时，主动交出控制权挂起自己，让事件循环去执行其他任务。等到网络响应回来了，再恢复执行。 优缺点 适用场景：高并发 I/O（特别是网络连接）。 比如：高性能 Web 服务器（FastAPI）、WebSocket 服务、同时处理数万个长连接。 优缺点： ✅ 极致轻量：没有线程切换的操作系统开销，内存占用极低，能处理 C10k（万级并发）问题。 ❌ 传染性：一旦用了 async，整个调用链都要变成异步。 ❌ 怕阻塞：因为是单线程，如果中间混入了一个耗...
Python 中的并行
Python 中的并行 基于线程的并行 threading 模块提供了一种在单个进程内部并发地运行多个 线程 (从进程分出的更小单位) 的方式。 它允许创建和管理线程，以便能够平行地执行多个任务，并共享内存空间。 线程特别适用于 I/O 密集型的任务，如文件操作或发送网络请求，在此类任务中大部分时间都会消耗于等待外部资源。 伪并行 在 CPython 中，由于存在 全局解释器锁(GIL)，同一时刻只有一个线程可以执行 Python 代码（虽然某些性能导向的库可能会去除此限制）。 如果你想让你的应用更好地利用多核心计算机的计算资源，推荐你使用 multiprocessing 或 concurre...
Python 中的装饰器
Python 中的装饰器 它是 Python 3.7 引入的一个标准库工具（from dataclasses import dataclass）。它的主要作用是 自动生成样板代码。 装饰器本质上就是一个 “接收一个函数/类，并返回一个新的函数/类”的高阶函数 工作流程 @dataclass 的核心工作流程是利用 Python 的 元编程 (Metaprogramming) 能力。具体步骤如下： 读取类型注解 (__annotations__)： Python 的类会把变量定义的类型保存在 __annotations__ 字典中。 dataclass 函数会去读取 Student 类中的 nam...
active slam
Active Slam Overview Active Slam 的工作流程: Perception: 传感器数据获取与预处理 SLAM(Localization + Mapping + Loop Closure) Candidate Generation: 生成候选观测点(frontiers/viewpoints) Evaluator: 对每个候选估算：预期信息增益（raycast / mutual information / belief propagation）、执行代价（路径长度、能耗）、定位风险（协方差增长）、碰撞风险。 Planner: 短期执行目标或控制序列（通常只执行第一步或首...
Prepacking
Prepacking: A Simple Method for Fast Prefilling and Increased Throughput in Large Language Models 阅读笔记.
deepseekv4
DeepseekV4 模型架构 Attention 这里所有的 Attention 实际上都是 MLA 的方式计算，只是 KV 的压缩程度不同以及是否有 DSA 参与 CSA(Compressed Sparse Attention) Compressed KV Entries：每 m 个 token 生成 1 个压缩 KV，但这个压缩 KV 实际会参考当前 block 的 m 个 token，以及前一个 block 的 m 个 token，一共 2m 个候选 token，然后用 learned softmax 权重加权求和(Overlap) DSA Strategy：对于每个 query，选择...
Chunked Prefill
Taming Throughput-Latency Tradeoff in LLM Inference with Sarathi-Serve Motivation Prefill 因为是长序列计算有高延迟，decode 是低延迟但是 GPU 利用率很低 现有的 batching 调度交错 prefill batch 和 decode batch，让高吞吐和低延迟变得困难 Batch 对 decode 吞吐量提升很大，对 prefill 影响小 Decode 阶段计算资源未被充分利用 SM 计算资源空闲：可以在解码批次中处理更多令牌，而不会显着增加其延迟。 线性层在预填充和解码阶段占据了大部分运...
PageAttention
Efficient Memory Management for Large Language Model Serving with PagedAttention Motivation 当时的大模型推理系统直接通过 pytorch 为每个 req 预分配一块连续的内存，会造成内部碎片（因为分配的会过多），外部碎片（因为需要分配连续的）；让整个系统的吞吐量骤降，无法高效利用和复用显存 Key Observation KV Cache 当模型生成新的 token 时，它会随着时间动态增长和收缩，并且它的生命周期和长度是未知的。 现有系统预分配 max_token 长度的显存，会导致内部碎片。因为实际...
SGLang
SGLang: Efficient Execution of Structured Language Model Programs.
distserve
DistServe: Disaggregating Prefill and Decoding for Goodput-optimized Large Language Model Serving Motivation 现有的 LLM 服务系统将 prefill 和 decode 两个阶段并置，并批量计算所有用户和请求的预填充和解码。我们发现这种策略不仅会导致强烈的预填充解码干扰，而且还会耦合两个阶段的资源分配和并行计划。 prefill 关注 TTFT decode 关注 TPOT 现有系统为了满足两种不同的延迟，过度配置计算资源或者牺牲其中一个来满足另一个；这会造成成本效益不足 因此，优化每...
DFLASH
DFlash : Block Diffusion for Flash Speculative Decoding 什么是 DLLM？ 在标准的自回归语言模型中，序列的联合概率分布被严格分解为条件概率的连乘：p(x_1,\dots,x_n)=\prod_{i=1}^n p(x_i\mid x_{<i})直观含义：第 i 个 Token 只能基于它前面的 i-1 个 Token 来预测。 dLLM 抛弃了上述的单向连乘约束，转而借鉴了 Diffusion 模型在图像生成领域的成功经验，定义了一个**加噪与去噪”**的过程： Forward Process (前向加噪)：在训练阶段，拿一段干净的...
SD in Llama
Efficient Speculative Decoding for Llama at Scale: Challenges and Solutions NOTE 在 8 个 NVIDIA H100 GPU 上以每个 token 约 4 ms（批量大小为 1）的速度进行解码，这比之前最知名的方法快了 10%。 对于基于 EAGLE 的推测解码，我们的优化使我们能够在生产规模上实现 1.4 倍到 2.0 倍之间的大规模部署上的加速 这篇文章从训练和推理两方面对现在 eagle-based 的 sd 方法如何在大规模生产环境下使用提出了一些方法。 暂时只看了推理部分 Inference 这里使用了 ...
eagle
(EAGLE 1)EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty Key Observation 特征（second-to-top-layer）级别的自回归比令牌级别更直接。 这一层的 feature 更有规律，在特征级别进行自回归处理，然后使用原始 LLM 的 LM 头导出标记比直接自回归预测标记更有效率。 采样过程中固有的不确定性极大地限制了预测下一个特征的性能。 对“am”或“always”等不同的 token 进行采样会产生不同的特征序列，从而在特征级自回归中引入歧义 EAGLE 将后一步的 tok...
eagle2
(EAGLE 2)EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees Key Observation Context-Dependent Acceptance Rates draft token 的接受率与位置相关，位置 P1 的接受率最高，位置 P6 的接受率最低 同一位置的接受率存在显着差异，这表明 draft token被接受的概率不仅取决于其位置，还取决于上下文。这表明上下文感知的动态草图树比静态草图树具有更大的潜力 Well-Calibrated Draft Model 为了应用动态草案树，我们需...
eagle3
(EAGLE 3)EAGLE-3: Scaling up Inference Acceleration of Large Language Models via Training-Time Test Motivation 当前的 EAGLE 范式在 scaling-up 上已经达到了瓶颈，无法通过更多的训练数据来提升 EAGLE 的性能，需要分析原因并改进 Key Observation EAGLE 在特征层面进行自回归预测，预测下一个特征，然后将特征输入到目标模型的 LM head 中以获得 token 分布。 EAGLE 的损失函数由两个部分组成：特征预测损失 l_{fea} 和 toke...
survey on parallel text gen
A Survey on Parallel Text Generation: From Parallel Decoding to Diffusion Language Models AR-Based 遵循 Draft-and-Verify 范式 [图片] 最大目标是最大化期望的吞吐率 A 是 accept tokens L(\mathcal{M})denote the latency of a single forward pass for model M.
batch-invariant kernel
Batch-Invariant Kernel 实际上是在硬件、软件栈以及 sampling temperature = 0 严格受控情况下的，输出确定性 Motivation 浮点结合律 浮点数加法不满足结合律，即：(a + b) + c \neq a + (b + c) 在 GPU 计算中，为了追求极致速度，成千上万个线程会并行计算。如果计算的顺序发生了哪怕一丁点改变，由于舍入误差（Rounding errors），最终的结果在比特位级别（Bit-level）就会产生微小差异。由于 LLM 是一个深度堆叠的非线性系统，这种微小的差异会随着层数增加被迅速放大，最终导致生成的下一个 Token ...
eplbopt
GRACE-MoE 优化 一种针对稀疏混合专家（SMoE, Sparse Mixture-of-Experts）模型在分布式多GPU集群上推理时的综合优化方案。SMoE模型的核心痛点在于：跨设备通信开销大与计算负载极度不均衡。 文中提出的三个核心Idea层层递进，形成了一个闭环：先通过分组减少通信（但加剧了负载不均衡），再通过复制缓解负载不均衡，最后通过路由在通信和计算之间找到最优的执行路径。 Core Idea 1.
2025-11-01
今天睡了大半天很爽 晚上开始给实验室做调研，搞一下红外摄像头的调研 纯纯zz工作，摄像头厂商都做完了，我们还做个球啊 .
2025-10-31
进行了 vllm 和 sglang scheduler 的分析 vllm 不再区分Req 的 prefill 和 decode 阶段，只是保存需要生成的 token 数；batcdh 中混合 prefill 和 decode，通过后端来进行区分处理 sglang 仍然区分 prefill 和 decode 阶段，prefill 请求优先调度，一个 batch 中只有 prefill 或者 decode 查看了下 sglang 的 pr，发现 speculative coding 现在很热门，接下来我的主要方向是向这个领域尽可能针对 Issue 合入 PR 晚上回来和师兄和同门聊到 llm i...
研一下总结
总结 先完成了 CMU15445 对应的 bustub 项目的实践，对数据库的各种基础知识又有了新的理解 又完成了 tidb 的小项目 tinykv，对 raft 有了一定的理解 感觉还是需要在生产中遇到问题，才能理解一些设计上的考量 但是越来越感觉分布式是一个脏活，处理层出不穷的 corner case 成功申请下了开源之夏，为 nebula graph 增加 ann search 能力 基本上整个暑假 + 9-10 月基本上在搞这个项目，简历上可以再来一笔 基本上 6 月开始看一些岗位的 job description，越发感觉数据库没什么增长点了，开始考虑和 AI 结合的一些数据库岗位，...
研二上总结
总结 在 9 月下旬，和室友半夜畅聊的时候，彻底下定决心，all in llm inference 💪 人生就是要 all in 一次的 看了 cse 234 的课程，补了补缺失的基础，里面老师提的三个期望非常戳我 Ability to identify the right problems Ability to understand “trends” Ability to “predict the future” (I hope so) 看了 GPU 和 CUDA 相关的基础知识(主要是博客和 cuda mode) 写了个小项目 tinyllm，暂时没有加上 page attention ...
从 Volta/Turing、Ampere、Ada 到 Hopper：硬件、PTX 与 Kernel 编程范式演进
沿着 Volta/Turing、Ampere、Ada、Hopper 的硬件、PTX 与 kernel 编程范式，连接白皮书峰值、微基准和真实算子，分析每代架构为什么变快，以及未达理论性能时如何区分硬件边界与优化问题。
Model Forward 瓶颈以及优化方法
Model Forward 瓶颈以及优化方法
Speculative Decoding
Speculative Decoding Draft 负责便宜地提一个多步候选树 Verify Target Model 在每一轮验证时的逻辑输入由两部分构成： 已验证的前缀 (Verified Prefix): 即截至上一轮已确认正确的 Token 序列，记为 x_{<n}。这部分通常已经存在于 KV Cache 中。 本轮候选 Token / Tree (Draft Proposals): 由 Draft Model 生成的 k 个候选 Token \{x_n, x_{n+1}, \dots, x_{n+k}\}，或者是树状结构的候选节点。 对于 Draft Model 提出的线性序...
Orca: A Distributed Serving System for Transformer-Based Generative Models (Yu 等, 2022, p. 520)
Orca: A Distributed Serving System for Transformer-Based Generative Models Motivation 当前的 serving system 调度方式是 request-level，对于当前自回归模型推理来说不够灵活 完成的请求无法立即退出 新来的请求无法在有空闲时加入 必须等待 batch 中最长的请求完成 在进行 iteration-level 调度时对操作进行 batching 操作时有困难 当时的 Attention 算子对输入长度和 position 有要求 Core Idea Iteration-level Sch...
Quantization in LLM Inference
Quantization in LLM Inference 对称量化：认为数值分布大致以 0 为中心 量化：q = round(\frac{x}{s}) 反量化：\hat{x} = q \cdot s 其中 s 是 scale，表示量化单位的大小，通常根据数值范围和量化位数 b 计算得到： s = \frac{\alpha}{2^b - 1} \alpha 是数值范围的绝对值上界，例如 \alpha = \max(|x_{min}|, |x_{max}|) 非对称量化：允许数值分布不以 0 为中心，因此需要额外的偏移量（zero-point）来表示 0 的位置 量化：q = round(\fr...
Attention & Transformers
首先从概率论角度介绍语言生成模型最终训练目标然后介绍注意力机制（Attention）及其在 Transformer 架构中的应用，并详细解析 Transformer 的结构和工作流程。
PD Disaggregation in SGLang
本文将从为什么需要 PD 分离开始讲起，通过几篇论文来讲述现在 PD 分离演进的路线，以 SGLang 中 PD 分离的实现作为 example 进行解析；由于笔者之前做过分布式相关的项目，将其中的状态机与 Raft 浅浅做了以下对比。
DIFFUSION LANGUAGE MODELS KNOW THE ANSWER BEFORE DECODING 论文精读
DIFFUSION LANGUAGE MODELS KNOW THE ANSWER BEFORE DECODING 香港理工大学、达特茅斯学院、Google DeepMind 等组织发表 Abstract 随着扩散语言模型（DLM）在各个领域的快速发展，其已成为自回归（AR）模型有力的替代方案。与 AR 模型相比，DLMs 的主要优势包括但不限于：高效的并行解码和灵活的生成顺序。 然而 DLMs 推理时需要双向注意力计算，而且为了高质量的 token 需要多步的 refine，这使得 DLMs 在推理速度上远远落后于 AR 模型，限制了其在实际应用中的使用。 本文，来自香港理工大学、达特茅斯学...
FlashAttention 原理 v1-v3
本文详细介绍 FlashAttention 的原理及其 v1-v3 版本的改进点，涵盖 Online Softmax、分块计算以及并行化优化等关键技术。
Parallelization in LLM Inference
本文介绍了在基于 Transformer 的大规模语言模型（LLM）中常用的并行化技术，包括数据并行（DP）、张量并行（TP）、流水线并行（PP）、专家并行（EP）以及序列并行（SP）和上下文并行（CP）。通过 deepseek-V3 来进行具体分析这些并行化技术在训练和推理中的应用。
Parallelization Concepts
本节主要介绍大模型训练中的并行化技术，涵盖数据并行、模型并行、流水线并行和张量并行等方法。我们将从 Transformer 的参数量、Flops 以及训练占用显存入手，分析为什么需要并行化技术，并介绍这些技术的基本原理。
研一上总结
当时研一上太忙，没来得及进行复盘；现在过去差不多一年来复盘一下当时的过程 进行了实验室 C++ 和网络编程的培训 对 C++ 17/20 比较熟悉了，对一些特性了解了 看了 STL 源码解析，对 STL 容器里面的设计有了了解 对 epoll 事件触发机制等网络库，特别是 muduo 有了细致的了解 当时和师兄，同门一块打了 ob 大赛，基本上整个研一上半年都是在搞这个 看了 CMU15445 的课程，对数据库有了比较成体系的了解，也是在这个时候考虑以后搞数据库 写了 miniob，实现了很多功能，尤其是 2024 年加入了向量搜索功能，让我想搞向量数据库，在向量索引方向发论文 在 ob 决赛...
从 GEMM 实践 CUDA 优化
本文将从最 naive 的 GEMM 实现开始，使用 nsight compute 工具进行性能分析寻找瓶颈并一步步进行优化。通过这种方式来实践 CUDA 中的各种优化技巧，包括 Tiling、Free Bank Conflict、Double Buffer、wmma 指令优化等。
DiT Generate Model in SGLang
DiT Generate Model in SGLang 常见 DiT Generate 模型 Stable Diffusion 3(Image Generate) NOTE 文本（Text）和图像（Image）是两种本质不同的模态，因此应该使用两套独立的权重来分别处理它们，但在注意力机制（Attention）阶段允许两者进行交互。 双流架构：文本流 c 与图像流 x 各自用独立权重处理，仅在注意力处交互，以更好保留各自模态特征。 全局调制：由时间步 t 与汇聚文本向量构成的 y 经 SiLU+Linear，为两流各自产生 6 组调制参数（\alpha,\beta,\gamma,\delta,...
Masked Diffusion Large Language Model
Masked Diffusion Large Language Model 📚 这里以 Ant Group 的 LLaDA 论文为例，介绍 Masked Diffusion LLM 的基本原理和实现方法；后面结合 SGLang 对该模型的推理实现进行说明。 Traing Details 基于掩码的扩散模型(Masked Diffusion Model) LLaDA 通过定义前向过程（Forward Process）和反向过程（Reverse Process）来建立模型分布 p_\theta(x_0)。 前向过程（破坏数据）：LLaDA 不像传统扩散模型那样添加高斯噪声，而是通过掩码（Mask...
MultiModel Generate in SGLang
MultiModel Generate in SGLang Overview SGLang Diffusion 采用了 Client-Server 架构，结合 多进程 (Multi-Process) 和 模块化流水线 (Modular Pipeline) 设计。 Client (DiffGenerator): 用户接口，负责发送请求和接收结果。 Server (Scheduler & Workers): 后端推理服务，由多个 GPU Worker 进程组成。 Rank 0 (Scheduler): 主节点，负责接收 Client 请求，并通过分布式广播将任务分发给所有 Worker。 ...
一条 Request 在 SGLang 的前世今生
本文将介绍在 SGLang 中，一条请求从到达系统到最终完成的全过程，涵盖请求的接收、调度、执行以及结果返回等关键环节。
RadixAttention 你需要知道的细节
本文深入探讨 SGLang 中 RadixAttention 的实现细节，涵盖 Radix Tree 结构、前缀匹配、内存管理与驱逐策略，以及 Cache-Aware Scheduling 的工作原理。
SGLang 中的 TP + PP 流程浅析(以 Qwen2 为例)
这里我们以 Qwen2 模型为例，开启 PP + TP 分析一下 SGLang 是如何实现模型推理的并行的
大模型推理服务中的 Batching
现在的大模型推理的框架基本都实现了 Continuous Batching，本文将从大模型推理服务为什么需要 Batching 开始，逐步讲解该领域的技术演进，包含调度层和计算层的相关优化技术。
下篇：向量索引与相似度搜索 —— Nebula Graph 的 ANN 实现之路
本篇主要介绍如何支持 Ann 索引和 Ann Search。
中篇：Vector 类型的 DDL & DML 适配
本篇主要介绍如何支持向量属性的 DDL 和 DML 语句，涵盖在 Nebula Graph 中添加 Vector 类型属性的实现细节。
GPU 内存系统演进：最大化带宽利用与延迟隐藏的技术路径
本文探讨了 GPU 内存系统的演进路径，重点介绍了如何通过提升带宽利用率和隐藏延迟来优化 GPU 性能。涵盖了 Little's Law、ILP/DLP 并行扩展、异步内存加载以及启动延迟优化等关键技术。
CUDA Optimization for LLM Inference
在大规模语言模型（LLM）推理中，优化 CUDA 代码对于提升性能和效率至关重要。本文档介绍了一些关键的 CUDA 优化技术，帮助开发者更好地利用 GPU 资源进行 LLM 推理。
从代码看 SGLang 的 KV Cache
本文将深入解析 SGLang 的 KV Cache 实现细节，介绍其组件结构、工作原理以及在模型推理中的应用。
Page Attention
本文深入探讨 Page Attention 的实现细节，涵盖 GPU Tiling、矢量化访问、分层计算结构以及注意力内核的具体实现过程，帮助读者理解其高效计算注意力机制的原理。
上篇：初识 Nebula Graph —— 向量类型支持
上篇：初识 Nebula Graph —— 向量类型支持 📚 本系列文章分为上中下三篇，记录了我在开源之夏项目中，开发 Nebula Graph 向量搜索功能的一些复盘和思考，希望可以给大家学习和开发类似系统时有一定的样本参考。希望大家多多关注和交流，大家一起进步 😊 欢迎订阅我的个人网站🚀 tom-jerr.github.io 上篇主要介绍 Nebula Graph 的整体执行流程，重点讲解向量类型的设计和向量存储的设计思路。 中篇主要介绍如何支持向量属性的 DDL 和 DML 语句(💀 走了很多设计的弯路)。 下篇主要介绍如何实现向量索引和向量搜索功能。 在真正开始对 Nebula...
上篇：初识 Nebula Graph —— 向量类型支持
本篇文章介绍了 Nebula Graph 向量类型的设计与实现，涵盖向量数据类型的定义、序列化与反序列化方法，以及向量属性的存储结构和存储引擎的改动。
SGLang Scheduler 技术变迁
本文将结合代码分析 SGLang Scheduler 的技术演进，介绍其核心数据结构和工作流程，帮助读者深入理解调度器的实现细节。
Data Parallelism in Attention in SGLang
本文介绍 SGLang 中 Attention 层的数据并行（DP Attention）机制，涵盖其设计理念、实现细节及执行流程，旨在提升模型推理的效率和性能。
一步步实现 CUDA Vector Add 优化
本文将通过一个简单的 CUDA Vector Add 例子，介绍如何使用 Nsight Compute 工具进行性能分析，并一步步进行优化。
Exploration with Global Consistency Using Real-Time Re-integration and Active Loop Closure 论文精读
Exploration with Global Consistency Using Real-Time Re-integration and Active Loop Closure ICRA 2022 作者信息：Yichen Zhang, 港科大 HDJI 团队，自主避障 Abstract 为了解决定位漂移问题，这篇文章之前的探索策略都是假设 localization 是 drift-free 的，这个假设在现实中往往不成立。 本文提出了一种实时重积分的帧剪枝建图算法以及一个考虑历史 viewpoints 的探索规划算法，并结合二者加上主动闭环检测构建了一个 framework 该方法主要解决...
Batching Inference & KV Cache
Batching Inference & KV Cache KV Cache Question without KV Cache Attention 计算实际上是与 seq_len 平方成正比的，所以 prompt 变长的话，我们的 FLOPs 会很快增长到超过 Single GPU 的计算能力(Compute-Bound) “Aha!”时刻： 当我们去预测第 9 个词时，我们需要： Q = 第 8 个 token 的 Query 向量。 K = ["The", ..., "and", "the"]（所有 8 个 token）...
3D Active Metric-Semantic SLAM 论文精读
3D Active Metric-Semantic SLAM 论文精读 RA-L 2024 作者信息：Yuezhan Tao, 宾西法尼亚大学的 GRASP 实验室，主要研究方向为机器人自主导航和 3D 重建以及将这些东西与 AI 和 LLM 融合 Abstract 主要解决了在 SWaP(Size Weight and Power)受限的平台上在无 GPS 的多层室内环境中自主探索和 metric-semantic mapping的问题 previous work: 假设 localization 是精确的，会导致不确定性的积累；同时减小不确定性的操作与探索未知环境的操作是冲突的 this ...
3D Active Metric-Semantic SLAM 论文精读
3D Active Metric-Semantic SLAM 论文精读 RA-L 2024 作者信息：Yuezhan Tao, 宾西法尼亚大学的 GRASP 实验室，主要研究方向为机器人自主导航和 3D 重建以及将这些东西与 AI 和 LLM 融合 Abstract Introduction 总体介绍 Background Method Experiments/Evaluation/Results Conclusion My Summary Reference.
Group Query Attention
GQA: Group Query Attention Group Query Attention 这是一种针对多头注意力机制的优化技术，可以降低与键 (K) 和值 (V) 投影相关的计算和内存成本。与多头注意力机制 (MHA) 中每个查询 (Q) 头都有自己的 K 头和 V 头不同，多个 Q 头共享相同的 K 头和 V 头。多查询注意力机制 (MQA) 是 GQA 的一个特例，其中所有 Q 头共享一个 K/V 头对。 实际上在应用时，我们还会再计算 q @ k 后进行 mask 叠加，这里一般有两种情况： 一种就是我们自己设计的 mask 形式 一种就是 causal mask(因果掩码)，用...
RMSNorm & MLP
RMSNorm & MLP RMSNorm RMSNorm1 的定义： y = \frac{x}{\sqrt{mean(x^2) + \epsilon}} \cdot weight x 是输入张量。 weight 是一个可学习的缩放参数。 epsilon(eps) 是为了数值稳定性而添加的一个小常数（例如，1e-5 或 1e-6）。 mean(x^2) 是平方和然后除以元素的数量 LayerNorm 成功的关键在于其 “重新缩放” (re-scaling) 的不变性，而 “重新中心化” (re-centering，即减去均值) 这一步可能不是必需的 归一化方法 方法归一化维度是否依赖批...
VINS 基础知识
VINS 基础知识 VINS 分类 VINS 可以分为 filter-based 和 optimization-based。 基于滤波器 (Filter-based) 的方法：将 VINS 看作一个在线的、递归的状态估计问题。它像一个流水线，新的传感器数据（测量值）源源不断地流入，滤波器利用这些新数据来更新对当前时刻状态的估计。它不回头修改过去的状态 基于优化 (Optimization-based) 的方法：将 VINS 看作一个批量处理的非线性最小二乘问题。它会收集一段时间内（一个“窗口”或全部历史）的所有传感器数据，然后寻找一条最优的轨迹（包含多个时刻的姿态、位置等），使得这条轨迹能够最...
Introduction
本文介绍了不同神经网络架构（如 MLP、CNN、RNN 和 Transformer）对计算模式的影响，探讨了这些模式如何映射到计算机系统资源，包括内存访问模式、计算特性、数据移动和资源利用。
Are You Sure You Want to Use MMAP in Your Database Management System
Are You Sure You Want to Use MMAP in Your Database Management System 论文阅读笔记 Abstract mmap = 💩 永远不要在 DBMS 中应用 mmap Intro 总体介绍 mmap work flow 用户用 mmap 请求读写 cidr.db 文件 mmap 系统调用将其映射到进程的虚拟内存空间中与文件关联，注意此时并没有将文件加载到真实物理内存 直到用户开始访问该文件数据，OS 发现虚拟内存没有对应的物理内存，触发 page fault，此时 OS 将文件的相应部分加载到物理内存中 同时向维护的页表以及 TLB...
PL-VINS: Real-Time Monocular Visual-Inertial SLAM with Point and Line Features 论文阅读笔记
PL-VINS: Real-Time Monocular Visual-Inertial SLAM with Point and Line Features. PL-VINS is the first real-time optimization-based monocular VINS method with point and line features. A modified LSD algorithm is presented for the pose estimation problem by studying a hidden parameter tuning and length rejection strategy.
PANNS: Enhancing Graph-based Approximate Nearest Neighbor Search through Recency-aware Construction and Parameterized Search
PANNS: Enhancing Graph-based Approximate Nearest Neighbor Search through Recency-aware Construction and Parameterized Search. It analyzes the graph-based ANNS workload, offers a parameterized search strategy for flexible speed-accuracy trade-offs, and incorporates hidden dimensions through a new proximity graph construction algorithm and graph memory layout optimization.
PDX: A Data Layout for Vector Similarity Search
PDX: A Data Layout for Vector Similarity Search. The design of PDX, a new data layout for vectors alongside PDXearch: a framework to perform pruned VSS dimension-by-dimension. The design and evaluation of PDX-BOND leverages the PDX layout to visit first the most relevant dimensions relative to the incoming query. To incorporate hidden dimensions not embedded into vectors, it proposes a new proximity graph construction algorithm and a graph memory layout optimization.
iQAN: Fast and Accurate Vector Search with Efficient Intra-Query Parallelism on Multi-Core Architectures 论文阅读笔记
iQAN: Fast and Accurate Vector Search with Efficient Intra-Query Parallelism on Multi-Core Architectures. It studies the root causes of poor scalability in vector search on multi-core architectures and introduces path-wise parallelism, staged expansion, and redundancy-aware synchronization.
A Large-Scale Disk-Based System for Dynamic Vector Search 论文阅读笔记
LSM-VEC uses a write-optimized LSM-tree for graph indexes, keeps only the bottom layer on disk, applies locality-aware graph reordering, and uses sampling-guided traversal with probabilistic routing.
From parser to executor, modifing nGQL statement
修改nGQL语句，从解析器一直到执行器
Bison Debug 指北
本文介绍如何在使用 Bison 进行语法分析时进行冲突查看和调试，帮助开发者更好地理解和解决语法规则中的问题。
Bustub 通关指北
Bustub 通关指北，带你快速了解 Bustub 的核心组件和实现细节，包括 Parser、Planner、Optimizer、Executor 以及 Storage 模块的工作原理。
The implement of Concurrent Component
并发组件的内部实现浅析
The history of C++ Asynchronous Solutions
C++ 的异步执行方案历史演进，从标准库的 Future 和 Promise，到 Folly 的扩展封装，再到 C++26 中的 std::execution 和协程的结合，详细介绍了各个方案的原理和使用方法。
std::thread & std::jthread
C++11 的线程和 C++20 的RAII线程
C++ 内存序
C++ 内存模型和基于原子类型的操作
Thread Shared Data Protection
C++ 中线程共享数据的保护方式
Synchronizing concurrent operation
C++ 中的同步并发操作
Non-blocking DataStructure
非阻塞的数据结构实现方式
MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Searcha Layout for Vector Similarity Search
MIRAGE-ANNS: Mixed Approach Graph-based Indexing for Approximate Nearest Neighbor Searcha Layout for Vector Similarity Search. It constructs the index as fast as refinement-based approaches while retaining search performance comparable to or better than increment-based ones.
Folly 异步编程框架
Folly 异步编程框架
一条nGQL语句的前世今生
一条nGQL语句的前世今生
Raft Wal
nebula中的Raft Wal
Visitor Pattern
观察者设计模式
Memory Management in nebula
nebula中的内存管理
Concurrent LRU Cache
并发的 LRU 缓存
MapReduce
MapReduce 论文笔记
SST
Sorted String Table 的基本介绍
Block
Block 的基本介绍
Merge Iterator
Merge Iterator 的基本介绍
Memtables
Memtable 的基本介绍
Transformer-based LLM
本章介绍基于 Transformer 架构的大规模语言模型（LLM），涵盖其核心组件如位置编码、注意力机制、归一化方法和前馈网络。
10-Join Algorithm
10-Join Algorithm 10.1 join algorithms 尽可能选择较小的表作为外围表 10.2 Join opetators Output data Cost Analysis Criteria Nested Loop Join Nested Loop Join 已知表非常小的情况下，可以使用 nested loop join，可以适配 L3 缓存 Index Nested Loop Join Block Nested loop join Nested Loop Join Summary Key Takeaways 选择更小的表作为 Outer table 尽可能在 bu...
12 Query Planning and Optimization
Query Planning and Optimization catalog 是一个记录元数据信息的文件 The Physical Plan Query Optimization(QO) Heuristics/Rules 重写查询来去除那些无效的条件 这些技巧需要访问 catalog，但是它们不需要访问数据 Predicate Pushdown Replace Cartesian Product Projection Pushdown Equivalence Architecture Overview Cost-based Search 使用一个模型来预测执行一个计划的成本 遍历多种计划，选...
13 Concurrency Control Theory
Concurrency Control Theory Transaction in sql ACID Mechanisms for ensuring atomicity Logging LSM tree 是针对单个表文件配置的；而 logging 是针对全局跨文件设置的 Shadow Paging 即使改变几字节，也会复制整个页 Consistency 很多系统采用最终一致性，但在过程中可能出现不一致的情况 Mechanisms for ensuring isolation Formal Properties of schedules Unreaptable Read 读写冲突的情况下，同一事...
14 Two Phase Lock
Two Phase Lock Concurrency Control Executing with locks 事务需要锁(upgrade) 锁管理器为请求申请锁 事务释放锁 锁管理器更新内部的 lock table lock table 跟踪每个事务持有什么锁，并正在等待什么锁 Locks vs.
15 Timestamp Ordering Concurrency Control
Timestamp Ordering Concurrency Control 2PL 和时间戳排序算法是悲观并发控制算法 还有乐观并发控制算法 T/O Concurrency Control 使用时间戳来确保事务执行的顺序 如果 TS(T_I) < TS(T_j)，DBMS 需要确保执行的调度必须和T_i发生在T_j前的串行化调度相同 Timestamp allocation System/Wall Clock Logical Counter Hybrid Basic T/O 事务读取和写入对象不需要锁 W-TS(X)：是最后成功写入的事务的时间戳 R-TS(X)：是最后成功读取的事务的...
16 Multi-Version Concurrency
Mutli-Version Concurrency DBMS 有多个物理版本和一个逻辑版本 一个事务写入时会创建一个新版本；读取时会读取该事务开始时最新的版本 MVCC 实际上是维护多个版本的机制；而版本之间的并发正确性仍然需要并发控制协议来维护 writers do not block readers and readers do not block writers 只读事务可以不获取锁读取一个一致性的快照 MVCC example Write Skew Anomaly 快照隔离并不能确保可串行性；可能出现这种写偏斜问题 Version Storage Append-Only Storage...
17 Database Logging
Database Logging Crash Recovery Actions during normal txn processing to ensure that the DBMS can recover from a failure Actions after a failure to recovver the database to a state that ensures atomicity, consistency, and durability Failure Classification Transaction Failures Logical Errors: 事务因为一些内部...
18 Database Recovery
Database Recovery ARIES Log Sequence Numbers MasterRecord 被硬编码到 DBMS，所以我们恢复时这个页面会先被拉到内存中 仅仅当 pageLSN <= flushLSN，才能将 log 刷入磁盘 所有的记录都有一个 LSN 每次一个事务修改一个页上的 record，pageLSN 会改变 每次 DBMS 将 WAL buffer 中的东西写入磁盘，flushedLSN 会更新 Normal Execution Transaction Commit 我们只需要保证在刷新 flushLSN 之前先将日志记录刷新到磁盘即可 TXN-END...
19 Introduction to distributed database
Introduction to distributed database.
7_B+Tree Indexes
7-B+Tree Indexes 7.1 B-Tree Family 7.1 Tree Indexes DBMS 在执行查询的时候，更多是查询索引而不是查询数据库中的表 索引问题 存储开销 维护索引开销 7.2 B+ Tree 是一个自平衡树。这是一种插入、删除均为 O(log n)的数据结构。可以支持线性遍历（哈希表不能做到） 相比 Hash Table，最好的性能是 O(1)，最差时退化到 O(n)。因为平衡，所以任意一个叶子结点到根结点的时间复杂度均为 O(log n) 对于读写磁盘上整页数据具有其他数据结构不具备的优势 7.2.1 B+ Tree Properties M阶搜索树 \\...
8_Index Concurrency
8-Index Concurrency 8.0 Concurrency control 8.1 Latch 8.1.0 LOCKS VS.
9-Sort && Aggregation Algorithm
9-Sort && Aggregation Algorithm 9.0 Query Plan 操作符可以处理比内存更多的数据 尽可能高效地利用 buffer pool 访问磁盘用尽可能多的顺序 IO 9.1 Sort 9.1.1 Why do we need to sort 通常情况下，基于哈希的方式比基于排序的方式更优；但是对于预先排序的数据基于排序的方式可能更优 9.1.2 IN-MEMORY SORTING 9.1.3 TOP-N HEAP SORT 如果出现相等的值，就扩展堆数组的大小 9.1.4 EXTERNAL MERGE SORT sorted run 行存储一般...
TimesharingOS
分时多任务OS
BatchOS
BatchOS介绍
LibOS
LibOS介绍
rustlings
rustlings中使用的rust技巧
6_Hash_Table
6 Hash Table 使用范围 Internal Meta-data Core Data Storage Temporary Data Structures (join 联表查询) Table Indexes 6.1 Design Decisions Data Organization Concurrency unrealistic assumptions Hash Function 计算速度和碰撞率的取舍 Hashing Scheme 静态哈希表 可扩展哈希表 6.2 hash functions 6.3 static Hashing Schemes Linear probe hashi...
csapp-7-链接
Chapter 7 链接 静态链接 符号解析 重定位 编译器和汇编器生成.text 和.data 链接器通过把每个符号定义和一个内存位置关联，对这些节进行重定位；修改引用，让符号指向这个内存位置 可重定位目标文件 .rel.*：不同节的重定位信息 .line：原始 C 程序和.text 节中机器指令的映射，“-g”得到 .bss：未初始化的静态变量，以及初始化为 0 的全局或静态变量 COMMON：未初始化的全局变量 解析多重定义符号 不允许有多个同名的强符号（定义并初始化） 强弱同在，选强符号 只有弱符号，随便选一个弱符号 重定位 重定位节和符号定义 将相同类型的节合并为同一类型的新的聚合节...
csapp-8-异常控制流
Chapter 8 异常控制流.
csapp-在系统上运行程序
在系统上运行程序 链接 gcc 编译链接程序：cpp 预处理器预处理源文件，cc1 编译器编译.i 文件为.S 文件，as 汇编器将.S 文件变为可重定位目标文件.o，最后运行 ld 链接器，创建一个可执行程序 执行./a.out，shell 调用加载器函数，将可执行文件的.text 和.data 复制到内存并跳转到该程序开头 解析多重定义的全局符号 规则 不允许多个同名的强符号 如果有一个强符号和多个弱符号同名，选择弱符号 如果有多个弱符号同名，选择其中任意一个 链接器不会表示检测到符号的多重定义 未初始化的全局变量交给 COMMON 段，将可能存在多重定义的变量交给链接器进行裁决 未初始化...
csapp-程序的结构和执行
程序的结构和执行 程序的机器级表示 使用基于条件的数据传送替代基于条件的控制转移 // 基于条件的数据传送 int ntest = x >= y; if (ntest) { .. } else { ..
8-Coordination
Coordination 1 进程切换过程 一个进程出于某种原因想要进入休眠状态，比如说出让 CPU 或者等待数据，它会先获取自己的锁； 之后进程将自己的状态从 RUNNING 设置为 RUNNABLE； 之后进程调用 switch 函数，其实是调用 sched 函数在 sched 函数中再调用的 switch 函数； switch 函数将当前的线程切换到调度器线程； 调度器线程之前也调用了 switch 函数，现在恢复执行会从自己的 switch 函数返回； 返回之后，调度器线程会释放刚刚出让了 CPU 的进程的锁 // 需要切换的进程 acquire(&p->lock); p...
5_Database_Storage
5 Buffer Pool 在磁盘中将文件切成一个个页 在内存中开辟一个缓存池；加快对页的访问 5.1 Buffer Pool Organization 是一个有着固定页数的数组；每个数组元素叫 frame (帧) 通过 page table 去索引内存池中的页 page table 可以 pin 某个页，也可以锁住某个索引 Mete-Data 页表跟踪现在在内存中的页 Dirty flag Pin/Reference Counter locks vs latches locks 保护事务中的内容 在事务期间持有锁 需要回滚 latches 保护临界区数据结构 在操作期间持有锁 不必回滚改变 ...
7-进程切换
进程切换 P1 进入内核，切换到调度器进程，调度器进程切换到 P2 核心函数为 swtch()函数；该函数保存并加载部分寄存器的值（RISC-V 中存在调用者保存并恢复的寄存器（caller-saved registers），不需要保存全部寄存器） 切换过程 yield 调用了 sched 函数 sched 函数进行合理性检查，最后调用 swtch 函数交换当前进程的上下文和 CPU 调度线程的上下文，返回地址为切换后上下文的 ra 寄存器存的值；实际上是 scheduler 函数 void sched(void) { int intena; struct proc *p = myproc()...
4_Database_Storage II
4 Database Storage II 数据库负责将非易失性存储中的数据和内存进行交互 4.1 problem with slotted page design Fragmentation (碎片) Useless Disk I/O Random Disk I/O (update 20 tuples on 20 pages) 4.2 Log-structed storage 更多使用 KV 数据库上，只有一个键一个值 不存数据，存放数据的操作（insert, delete, update） 直接在后面加上新操作，不检查前面的所有操作是否正确 读取一个记录，从后向前进行扫描记录；找到需要的数...
csapp-5-优化程序性能
Chapter 5 优化程序性能 编译器的能力和局限性 内存别名使用：两个指针可能指向同一个内存位置 可能出现这种问题，编译器必须进行检查和处理，这限制了可能的优化 restrict 关键字，可以告知编译器两个指针不能指向同一块内存，编译器可以进行进一步的优化 内联函数替换（inline substitution） 将函数调用替换成函数体；减轻调用的深度 消除循环中的低效率 比如将复杂的函数加入循环；此时考虑设置局部变量 消除循环中的过程调用；考虑返回值来优化 void combine3(vec_ptr v, data_t* dest) { long i; long length = vec_...
csapp-6-存储器层次结构
Chapter 6 存储器层次结构 RAM（随机访问存储器） SRAM：快但贵；作为高速缓存 DRAM：作为主存 分时复用地址线；减少引脚数量，增加访问时间 首先将一整行复制到一个内部行缓冲区；接着再从行缓冲区中复制出一个单元 非易失性存储器 主要是 ROM，但是 ROM 中有的类型实际上既可以读也可以写 固态硬盘 Solid State Disk (SSD)，是基于闪存的存储技术 闪存芯片替代传统旋转磁盘中的机械驱动器 闪存翻译层是一个硬件/固件设备，将对逻辑块的请求翻译成对底层物理设备的访问 SSD 以页为读写单位 将擦除平均分布到所有的块上 随机写很慢的原因 擦除块需要相对较长的时间 如...
1-OS的隔离性
OS 的隔离性 需要不同的应用程序之间有强隔离性 需要 OS 与应用程序间也有强隔离性 OS 隔离保证 multiplexing 和内存隔离 multiplexing（CPU 在多进程同分时复用）：不论应用程序在执行什么操作，multiplexing 都会迫使应用程序时不时的释放 CPU，这样其他的应用程序才能运行。 不同应用程序之间的内存是隔离的，应用程序之间不会相互覆盖 硬件支持强隔离 uer/kernel mode 在处理器里面有一个 flag。在处理器的一个 bit，当它为 1 的时候是 user mode，当它为 0 时是 kernel mode。当处理器在解析指令时，如果指令是特殊...
2-虚拟内存的实现
虚拟内存实现 页表 硬件通过处理器和 MMU（Memory Management Unit）实现 任何一条地址应该认为是虚拟内存地址；该地址会转到 MMU，MMU 翻译为物理地址，从物理地址加载 MMU 只是去查看 page table，page table 存在于内存中 虚拟内存地址只使用了低 39bit；低 12bit 作为页内地址偏移（offset），高 27bit 是索引页的 index，实际上是由 3 个 9bit 的数字组成（L2，L1，L0）。前 9 个 bit 被用来索引最高级的 page directory（注：通常 page directory 是用来索引 page tab...
3-系统调用和陷入
System calls and Trap 用户态和内核态的切换（trap） 程序执行系统调用（System call） 程序出现了类似 page fault、除 0 等异常（软件中断） 硬件中断（IO 设备） RISC-V 寄存器 32 个通用寄存器 PC（程序计数器） Mode（表明位于何种状态 user or supervisor） SATP（指向页表的物理地址） SEPC（指向 trap 指令的起始地址） STVEC （也就是处理 trap 的内核指令地址） SSRATCH（交换页表和 a0 地址） 内核态权限 读写控制寄存器：SATP、STVEC、SEPC 它可以使用 PTE_U 标...
4-缺页中断
Page Fault 通过 page fault 可以实现的一系列虚拟内存功能 lazy allocation copy-on-write fork demand paging memory mapped files 虚拟内存好处 isolation，隔离性；虚拟内存使得操作系统可以为每个应用程序提供属于它们自己的地址空间 level of indirection，提供了一层抽象，处理器和所有的指令都可以使用虚拟地址，内核会定义从虚拟地址到物理地址的映射关系 page fault 得到的信息 引起 page fault 的内存地址（STVAL 寄存器） 引起 page fault 的原因类型（...
5-硬件中断
Interrupts 中断与系统调用区别 asynchronous，异步，与当前运行在 CPU 的进程无关 concurrency，CPU 和产生中断的设备并行运行 program device，需要关注外部设备 中断处理——硬件 PLIC 会通知当前有一个待处理的中断 其中一个 CPU 核会 Claim 接收中断，这样 PLIC 就不会把中断发给其他的 CPU 处理 CPU 核处理完中断之后，CPU 会通知 PLIC PLIC 将不再保存中断的信息 中断处理——软件 使用驱动管理设备 bottom：通常是 Interrupt handler。当一个中断送到了 CPU，并且 CPU 设置接收这...
6-多核和锁
Multiprocessor and Lock 锁就是一个对象，就像其他在内核中的对象一样。有一个结构体叫做 lock，它包含了一些字段，这些字段中维护了锁的状态。锁有非常直观的 API： acquire，接收指向 lock 的指针作为参数。acquire 确保了在任何时间，只会有一个进程能够成功的获取锁。 release，也接收指向 lock 的指针作为参数。在同一时间尝试获取锁的其他进程需要等待，直到持有锁的进程对锁调用 release。 锁应该与操作而不是数据关联，所以自动加锁在某些场景下会出问题 想要程序简单点，可以通过 coarse-grain locking（注，也就是大锁），但是...
3_Database_Storage I
3-Database Storage I 1 DISK-BASED ARCHITECTURE 易失性存储和非易失性存储相结合 Volatile：Random Access Byte-Addressable （DRAM 之上） Non-Volatile：Sequential Access Block-Addressable（SSD 之下 ） SSD 以下只能按块来存取 顺序访问和随机访问 非易失性存储中顺序访问比随机访问快得多 一般数据存储在连续的块中，同时分配多个物理页叫区 2 DBMS 设计目标 允许管理比可用内存大的数据库 读写磁盘代价高昂，尽可能避免大的停顿和性能下降 DBMS 希望最大...
lecture10_Combinational_Logic
Combinational Logic CMOS Boolean algebra Arithmetic Logic Unit (ALU) .
lecture11_FSMs
FSMs, Synchronous Digital Systems FSM: Finite State Machine state transition diagram s0 初始状态；input/output；箭头指向是 next state clock and registers Flip-Flop 时钟上升沿；Q = D，其余时刻什么也不做 register delay clk-to-q delay Registers can’t transfer the D input to Q output instantly clk-to-q delay: Time it takes after ...
lecture14_DataPath_Hazards
Hazards Structural Hazards 两条或更多指令在流水线需要访问同一个物理单元 Solutions 指令轮流使用物理资源 增加额外的硬件资源 设计指令集避免结构冒险 Data Hazards Some regfiles support writing a new value to a register, then reading the new value, in the same cycle.
lecture15_Data_Level_Parallelism
Data-Level Parallelism SIMD single instruction, multiple data or vector instructions SIMD 实现矩阵乘法 common mistake 直接使用 32-bit 的 SIMD vector（寄存器与内存不同） 使用_mm_load or _mm_store 时采用未对齐的内存 忘记处理尾部特殊情况 使用太多的 vector .
lecture16_Thread_Level_Parallelism
Thread-Level Parallelism SISD：线性执行指令，没有并行 RISC-V 单周期 CPU SIMD：单指令流，多数据流 Intel instrinsics GPUS MISD：多指令流，单数据流 Deep learning acceleration chips MIMD：多指令流，多数据流 Modern processors 多核执行模型 独立资源 Datapath (PC, registers, ALU) Highest level caches (L1, L2 cache) 共享资源 Memory (DRAM) 3rd level cache 线程 一个进程可以可以...
lecture17_Process_Level_Parallelism
Process-Level Parallelism Multiprocess Framework 不同的核不分享内存，但是共享一个文件系统 在多线程程序运行时，一个线程 crash，整个程序可能 crash；但是多核程序，每个核之间是独立的，如果一个核 crash，其他的核可以继续运行 不同的核交流占用大量时间 将一个大问题分解成独立的小问题；以此来减少数据的传输时间损耗 .
lecture18_Caches
Caches Memory Hierarchy (层次化内存) 寄存器离 CPU 最近，使用也最快；但是很贵；每个 CPU 只有少量寄存器 DRAM 更适合存储大量数据，但是速度更慢 需要数据总线进行传输 加速方式 Hardware Multithreaing 在等待数据的过程中，切换到另一个进行去执行任务 每个物理核含有两个 PC 核寄存器组，所以上下文切换很快 Prefetching 每个周期预取指令和数据 Caching 利用空间局部性和时间局部性，减少和主存之间的数据传输 缓存中存放被主存使用的数据副本 主存中存放磁盘上的数据副本 层次化管理 Registers <--->...
lecture2_Intro_to_C
Intro to C Great idea in Computer Architecture 1. Abstraction (Layers of Representation/Interpretation) 2. Moore’s Law（摩尔定律） 3.
lecture21_Virtual_Memory
Virtual Memory 直接使用物理内存问题 没有足够空间；RISC-V 只提供 32bit 空间即 4GB 地址空间有空洞 不能保证其他程序不访问同一块内存 Benefits 允许运行自身大小比主存大得多的程序；只有工作的页放在主存，其他页放在磁盘；由 OS 进行页的请求和置换 OS 可以共享内存并实现程序的互相保护 隐藏机器级的不同 .
lecture4_C_Memory
C Memory memory alignment（内存对齐） Memory alignment: a system-dependent rule that tells us where data can be stored (usually not at every byte) Can be accomplished with the “aligned” attribute __attribute__((aligned(n))); Strings Example: The string “Hi” is stored in memory as an array of characters.
