MizukiCry's Blog

也是 CS149 的准备内容，这次是 OpenMP 的初探。 1 OpenMP Introduction OpenMP：跨平台、多语言（C、C++、Fortran） 、可扩展的并行计算 API，使得开发者可以轻松利用多核 CPU 的并行计算能力，加速程序的运行。 只需要在编译时加上 -fopenmp 选项即可开启 OpenMP 支持。 在程序中插入 #pragma omp 指令，编译器就会根据指令自动生成多线程代码，例如一个简单例子： 1printf("Hello, World!\n"); 在前面加上一句： 12#pragma omp parallelprintf("Hello, World!\n"); 程序就会根据硬件情况，在多个线程中执行 printf 语句。 OpenMP 也可以用于循环并行化，例如： 12#pragma omp parallel forfor (int i = 0; i < 10; i++) { /* do something */ } 2 OpenMP Usage ...

Stanford CS149 (Fall 2023) Parallel Computing Optional Programming Assignment 5: Big Graph Processing in OpenMP Github repo Part 1: Parallel "Top Down" Breadth-First Search (20 points) 使用 OpenMP 加速从起点开始的 BFS 看了一下给出的代码，就是维护两层队列，一层是当前层，一层是下一层，那么能够加速的就是每一次向下一层扩展的过程。 这里选择对第一层 for 循环进行并行化，由于每个点的边数不一样，所以选择动态的调度方式，并且每个线程都有自己的 buffer，最后再合并。 提示中说到了部分情况可以避免 CAS 操作，也就是提前判断一下 1234567891011121314151617181920212223242526272829void top_down_step(Graph g, vertex_set *frontier, vertex_set *new_frontie ...

Stanford CS149 (Fall 2023) Parallel Computing Programming Assignment 4: Chat149 - A Flash Attention Transformer DNN Github repo 环境配置 妈的，外校学生又没有服务器，只能自己配环境，又不给 requirements.txt，装个 torch 因为版本问题整了半天，翻 issue 才知道要装 2.1.2 版本，至于其它 module 就一直编译靠报错找依赖（ Warm-Up: Accessing Tensors (3 Points) 简单来说就是实现 4D-Tensor（类似四维数组）和一维数组之间的转换，秒 （然而其实这个实现性能上还稍微有点问题，在 Part2 才查出来） 1234567891011inline float fourDimRead(std::vector<float> &tensor, int &x, int &y, int &z, int & ...

写 CS149 需要用到 CUDA，所以先简单学习一下 CUDA 的基础知识。 1 CUDA Introduction CUDA（Compute Unified Device Architecture）是 NVIDIA 推出的并行计算平台和编程模型，使得开发者可以利用 GPU 的并行计算能力，加速程序的运行。 要想写好 CUDA，首先要了解 CUDA 的编程模型。在 CUDA 中通常将 CPU 及内存称为主机（Host），GPU 和显存称为设备（Device），Host 通过调用函数（Kernel）将任务分配给 Device 执行。 从体系结构上看，CPU 和 GPU 的区别在于：CPU 有少量“大核”，适合串行任务，GPU 有大量“小核”，适合并行任务，下图展示了 CPU 和 GPU 的体系结构差异： The GPU Devotes More Transistors to Data Processing 接下来看看 GPU 的体系结构：每一次 Kernel 的调用都会启动大量的 CUDA Thread，一次 Kernel 调用中的所有 Thre ...

Stanford CS149 (Fall 2023) Parallel Computing Programming Assignment 3: A Simple Renderer in CUDA Github repo 环境配置 因为这次的 PA 要用到 CUDA，所以需要电脑有 NVIDIA 显卡，并且 Compute Capability >= 7.5（20 代及以上显卡） 我是用的 WSL，显卡驱动理论上只要外部环境装好了新版的 NVIDIA 驱动 WSL 就能直接用了，可以用 nvidia-smi 命令查看是否能识别到显卡。 123456789101112131415161718192021~ » nvidia-smi mizukicry@S-TerminalMon Apr 8 09:49:30 2024+----------------------------------------- ...

Stanford CS149 (Fall 2023) Parallel Computing Programming Assignment 2: Scheduling Task Graphs on a Multi-Core CPU Github repo Part A: Synchronous Bulk Task Launch 创建三种不同的 Task execution engine，难点在于看懂要求 Step 1: Move to a Parallel Task System 普通多线程版本，感觉动态分配任务的话有点浪费资源，不过静态分配如果任务运行时间不同就有可能效果不好 因为多线程之间有竞争，所以需要加锁或者原子操作 123456789101112131415161718192021222324252627282930313233343536373839class TaskSystemParallelSpawn : public ITaskSystem {private: int num_threads_; std::thread *threa ...

Stanford CS149 (Fall 2023) Parallel Computing Programming Assignment 1: Analyzing Parallel Program Performance on a Quad-Core CPU Github repo 环境配置 鉴于应该都不是 Stanford 的学生，只能本地配置环境了。我使用的是 WSL 虚拟环境，Windows 大概是不能直接用的 12345678910111213141516171819202122~ » neofetch mizukicry@S-Terminal .-/+oossssoo+/-. mizukicry@S-Terminal `:+ssssssssssssssssss+:` -------------------- ...

Stanford CS149 Parallel Computing: 斯坦福一门并行计算的课，最近不知道该做些什么，感觉要是继续颓下去就废了。打算学一学这门课，在这里记一下看 Slides 做的笔记 课程主页：Fall 2023 网上似乎没有 CS149 的视频，这门课前身是 CMU 的 15-418，可以看这门课的视频 Lecture 1: Why Parallelism? Why Efficiency? 2024/3/25 目标：并行处理加速程序计算 优化：减少线程之间通信 / 同步，线程过多将严重影响性能，平均分配任务 Fast != Efficient，考虑硬件消耗性价比 利用硬件中针对专门指令的处理单元 指令级并行 ILP 内存定义：一段连续的地址空间，通过地址定位其中的每一个字节，访问内存通常使得 CPU 等待影响性能 超标量 CPU：每个核心有多个逻辑单元（ALU），可以一个周期同时执行多条指令（若指令间相互独立） Cache：将部分内存缓存到 CPU 自带的高速缓存中，若缓存命中则不需要访问内存，通常已 Cache Li ...

Part 1: Make the tests compile 配置好之后尝试运行 cargo test，发现编译错误： 12345error[E0433]: failed to resolve: use of undeclared crate or module `assert_cmd` --> tests\tests.rs:1:5 |1 | use assert_cmd::prelude::*; | ^^^^^^^^^^ use of undeclared crate or module `assert_cmd` 显然是缺少相应的 crate，在 cargo.toml 里面加上。 123[dev-dependencies]assert_cmd = "0.11.0"predicates = "1.0.0" dev-dependencies 和 dependencies 的区别可以看官方文档 再次运行 cargo test，发现编译错误： 12345error[E0432]: unresolved import ...

Project #2 - B+Tree Task #1 - B+Tree Pages 这一部分没什么好说的，把他给的函数写出来就行，基本都是一两行的事 Task #2 - B+Tree Data Structure (Insertion, Deletion, Point Search) 逆天 Task 之一 B+Tree 这东西看着原理简单，在内存池上写起来怪恶心的 比较简单的是查找，直接顺着往下定位到叶子节点就行。关于每个节点上的定位可以直接遍历或者二分定位。我用的二分，不过估计效率差别不大，瓶颈不应该在这一块 至于插入，最好先画个图仔细想清楚再写，不然就会向我一样改了好几版，10 天才摸出来这个 Task，感觉 DSA 白学了（ 我在向上更新的时候用的递归，感觉比较好理解。需要注意 Split 时也要更新子节点的 parent_page_id 然后是删除。因为课件讲得不是很细致，有些细节也稍微卡了一会。在 Merge 时需要给右边节点的第一个子节点增加一个对应的 Key，这个 Key 可以直接取父节点对应的 Key，然后删除父节点中的内容。 ...