might's room

第二次爱上脆莓，整张专辑都可以循环一整天

0.赛题分析 初始化和验证正确性用了一秒，核心函数用了63.5秒 通过分析，该程序为访存密集型，在GPU上可能访存成为瓶颈。 可能存在的优化方法： 编译器优化：感觉无计可施，只替换为dpcpp不变代码的话会变慢 拆分复数类，自己实现，将AOS转换为SOA 修改循环或者进行矩阵转置 GPU版本 多GPU并行 更换buffer为USM 使用MPI多进程来提高GPU利用率 负载均衡 CPUGPU协同计算 降低时间复杂度 1.重写复数库思路：将AOS换位SOA 将复数数据其完全拆分成double数组操作，除了将将AOS换位SOA，还简化了部分中间计算。 问题：拆分复数后显著变慢。 tips：某个方向的优化遇到瓶颈最好不要死钻牛角尖，心态会很受影响，最好换个方向进行优化 原因：因为没有先改变循环的顺序，导致有些数组还是列访问，当将复数数组拆分成两个数组后，cache miss会加倍，cache冲突率也会加倍，所以时间会变慢，在修改循环顺序后保证了所有的数组都是行访问，性能就不会下降了。但是由于在拆分前已经向量化了（vtune显示向量化100%），所以拆分后没有显著的性能提升。等放到GPU上试 ...

十、向量操作现代处理器基本都支持向量指令了，这种技术叫SIMD(single instruction multiple data)。向量大小从64位（MMX）、128位(XMM)、256位(YMM)、512位(ZMM) 向量操作适用于对多个数据执行相同的操作且运行并行，比如图像处理、声音处理、矩阵运算。 下面附上各个向量指令集支持的数据类型 Type of elements Size of each elements, bits Number of elements Total size of vector, bits Instruction set char 8 8 64 MMX short int 16 4 64 MMX int 32 2 64 MMX int64_t 64 1 64 MMX char 8 16 128 SSE2 short int 16 8 128 SSE2 int 32 4 128 SSE2 int64_t 64 2 128 SSE2 float 32 4 128 SSE double 64 2 12 ...

十一、具体优化策略 跳过了anger手册中关于cpu dispatch的一章，还是感觉太遥远了，等需要的时候再去了解吧 1.查找表（lookup tables）如果list在缓存中，从list中读值是非常快的，要快过函数计算，所以可以将函数计算替换成从查找表取值。 使用查找表的tips 查找表应该声明为const，以便启用常量传播和其他优化。 在函数内部声明查找表时不要声明为静态的static，因为静态数据可能分散在不同的内存地址，可能会导致缓存问题。可以声明为const，例如： 1234567891011121314151617// Example 14.1cvoid CriticalInnerFunction (){ // Table of factorials: const int FactorialTable[13] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600}; ... int i, a, ...

十二、元编程元编程：普通编程操纵数据，元编程操纵其他编程语言，元编程指生成其他程序的程序。 在讲元编程前，必须补充模板编程的知识，在讲模板编程前，我想先补充一下宏编程的基础知识，因为两者有许多相似之处（我太菜了，不会的太多了） 1.宏编程与预处理宏编程继承自c语言，在预处理时被替换。 预处理过程的第一步是进行一些翻译处理，包括讲源码中出现的字符映射到源字符集，会同时处理多字节序列和三字符序列（三字符序列的介绍三字符序列 - 逛博 - 博客园 (cnblogs.com)） 接着把物理行转换为逻辑行，示例如下： 然后，编译器讲文本划分为预处理记号序列、空白序列和注释序列，使用一个空格替换注释序列，使用一个空格替换所有的空白字符序列。 最后进入预处理阶段，预处理器查找一行中以#开头的预处理指令。 1.1#definedefine作用是定义常量，在预处理阶段将代码中的宏替换为替换体。 需要注意的是如果宏中还包含宏，会再次替换，字符串内的不会被替换。 宏分两种，类对象宏：宏代表值，类函数宏：宏代表函数 如果要在宏函数的字符串中包含宏参数怎么办？ 在字符串内使用#运算符： 如果要在宏函数中 ...

八、多线程有三种方法可以并行地执行任务： 使用多个 CPU 或 多 核 CPU，如本章所述。 使用现代 CPU 的乱序执行能力，如第9章所述。 使用现代 CPU 的向量操作，如第10章所述。 在决定并行处理是否有利时，区分粗粒度并行和细粒度并行非常重要。粗粒度并行是指一序列的操作可以独立于其他任务的情况（多个线程执行不同的任务）。细粒度并行是指任务被划分为许多小的子任务（多个线程共同执行一个任务），但是在与其他子任务进行必要的协调之前，不可能在特定的子任务上工作很长时间。 由于不同内核之间的通信和同步比较慢，因此粗粒度并行比使用细粒度并行效率更高。如果粒度太细，那么将任务拆分为多个线程是没有优势的。无序执行和向量操作是利用细粒度并行的更有用的方法。 在使用多线程时，需要关注缓存冲突和缓存一致性问题。 缓存冲突：多个 CPU 内核或逻辑处理器通常共享相同的缓存，至少在最后一级缓存中是这样，在某些情况下甚至共享相同的一级缓存。共享相同缓存的优点是线程之间的通信变得更快，并且线程可以共享相同的代码和只读数据。缺点是，如果线程使用不同的内存区域，缓存就会被填满，如果线程写入相同的内存区域， ...

九、乱序执行乱序执行的定义：现代cpu可以乱序执行指令或者同时执行多个操作，因为一个cpu上有多个计算核心可以同时计算。 乱序执行可以提高效率，但是当存在依赖关系链时（第三章第六节），cpu无法乱序执行，顺序结构中依赖关系链比如： 12float a, b, c, d, y;y = a + b + c + d; 这个表达式将会以((a+b)+c)+d形式计算，编译器不会优化，因为交换计算位置可能会导致溢出（可以回顾浮点数相关的知识（第六章第一节）），我们可以手动取消依赖关系链。 12float a, b, c, d, y;y = (a + b) + (c + d); 这样就可以同时计算(a+b)和(c+d)。 还有一种常见的依赖链是循环依赖链，例如： 1234const int size = 100;float list[size], sum = 0; int i;for (i = 0; i < size; i++) sum += list[i]; 这里每一次循环都必须依赖上一次循环的结果，优化这种循环可以可以采用展开循环将依赖链一分为二 12345678910// ...

七、内存访问优化1.缓存优化访存主要就是优化cahce的访问，因此先系统复习下关于cache的相关知识。 现代cpu大多拥有三级缓存L1L2L3。 L1缓存分成两种，一种是指令缓存，一种是数据缓存。L2缓存和L3缓存不分指令和数据。 L1和L2缓存在每一个CPU核中，L3则是所有CPU核心共享的内存。 L1、L2、L3的越离CPU近就越小，速度也越快，越离CPU远，速度也越慢。 三级缓存和RAM读取速度的对比： L1 的存取速度：4 个CPU时钟周期 L2 的存取速度： 11 个CPU时钟周期 L3 的存取速度：39 个CPU时钟周期 RAM内存的存取速度：107 个CPU时钟周期 cache与RAM的映射方式： 直接映射：一个cache块对应多个内存块，一个内存块只能对应一个cache块 全相联映射：任何一个内存块都能对应任何一个cache块，但是比较块号所需时间长 组相联映射：将前两者结合起来，cache分为多个每个组内有多个块，内存也分块，每一块对应一cahce组，可以占用组内的任意cache块 离cpu最近的可以直接相联，较近的可以组相联，最远的可以全相联，距离越远对 ...

linux查漏补缺 查漏补缺，打好基础 一、linux系统目录 /bin：binaries二进制文件的缩写，里面都是二进制文件，且都是普通用户可以使用的命令 /boot：引导程序，内核存放的目录 /sbin：与bin类似，但是里面存放的都是超级（root）用户可以使用的命令 /lib：根目录下所有程序所需的共享库 /dev：设备文件目录(Linux中设备以文件形式存在，实体设备以设备文件的形式被Linux得知，并通过设备驱动被linux使用) /home：此目录下存放所有普通用户的主目录，一般每个用户都在/home下有一个子目录，目录名为用户名 /root：root用户的主目录 /etc：全局的配置文件存放目录，当程序在用户主目录下时，会将配置文件在用户主目录下生成，系统也会优先去用户主目录下加载配置，若没有再去/etc下加载。 /opt：optional的简称，可以将自定义软件包或第三方软件安装在此目录下 /mnt：临时挂载目录，用于挂载存储设备的，比如磁盘光驱网络文件系统等，例如WSL2的目录/mnt/c就是我们Windows下的c盘。 /media：用于挂载 ...

六、编译器层次的优化1.编译器如何优化1.1内联函数编译器可以自动在调用函数时将函数名替换为函数体，即转为内联函数。 内联函数优点： 节约了调用、返回和参数传递的开销。 因为代码变得连续了，代码缓存的效率会更高。 如果只调用一次内联函数，那么代码就会变得更小。 函数内联可以使其他优化成为可能，下面会详细描述。 1.2常量折叠（constant folding）和常量传播(constant propagation)常量折叠是指只包含常量的表达式或子表达式将会被计算结果替换： 123// Example 8.2adouble a, b;a = b + 2.0 / 3.0; 编译器将会替换成下面的代码： 12// Example 8.2ba = b + 0.666666666666666666667; 常量传播指在依赖链上，若上游结果为常量，下游结果也为常量，则都会被替换成常量 123456789// Example 8.3afloat parabola (float x){ return x * x + 1.0f;}float a, b;a = parab ...