Xinhecuican's Blog

基础概念 集合： 一群无序对象 序列(sequence): 以某种顺序排布的有序列表 元组(tuple): 有限序列称为元组 字母表： 字母表是任何非空有限集合，例如{a, b, c} 字符串： 字符串是在字母表中的字符组成成的有限序列,如abcac 语言： 字典序的一组字符串。例如{0, 1}组成的一个语言为{0, 1, 01, 10, 11, 000}.也就是说1比0更大，先比较长度，长度相同从高位向低位比较 语言的拼接： 定义两个语言L1, L2， 他们的拼接L1L2 = {xy | $x \in L_1, y \in L_2$}。类似于分配率 设L1 = {ab, ba, bb} L2 = {00, 11}, L1L2 = {ab00, ab11, ba00, ba11, bb00, bb11} 语言的闭包： $L^* = L^+ \cup {\xi}$ 例如， $\sum = {0, 1}$ L = {01, 10} $L^0 = {\xi}, L^1 = L = {01, 10}, L^2 = L * L = {0101, 0110, 1001, 1010} ...

本篇是《通用图形处理器设计-GPGPU编程模型与架构原理》的阅读笔记 gpu处理器架构 gpu存储结构简介 gpu存储和cpu截然不同，呈现倒三角的结构。gpu使用如此多的寄存器文件主要是为了线程束的零开销切换。因为每个线程束都有它自己的寄存器，因此每次切换线程束时就不需要像cpu线程切换时那样将寄存器存入内存再读取了。 大容量寄存器带来的一个负面影响是L1和L2缓存的容量被大量挤压，在Pascal架构中超过60%的片上存储容量被分配给了寄存器。在NVIDIA V100架构中每个核最多128kb的l1数据缓存容量，而每个核中最多有2048个线程，也就是说每个线程只能分配到64b的空间。而l2缓存的容量有6mb，远小于l1数据缓存共10mb的容量。 寄存器gpu处理器的高并行导致每个核需要大量的寄存器端口。例如如果同时执行32个线程，每次需要读取3个操作数，那么要求寄存器文件每周期需要提供96个32bit的读端口和32个写端口。而寄存器在存储中占了绝大部分比重，大量的资源消耗导致寄存器无法使用激进的多端口设计。gpu中往往使用多bank的单端口来模拟多端口的设计。 如图所示为多板块寄存 ...

本篇是《通用图形处理器设计-GPGPU编程模型与架构原理》的阅读笔记 基础gpu基础结构可以参照 在上面已经提到线程块调度器会将线程块发送给对应的处理器，而处理器将执行线程块中所有线程。但是线程网格和线程块都是用户指定的，而硬件资源是有限的，例如寄存器端口，执行单元数量等。如果线程块的数量过大，那么执行一条指令就需要很多周期的时间，而且不好调度。因此处理器中真正的调度单位是线程束，线程束的大小是根据硬件资源决定的，线程块传递给处理器时会自动将线程块划分成若干线程束。 线程束中所有线程的pc相同，即执行的指令相同，不同的是他们有不同的线程id，读寄存器时会根据线程id和寄存器id来获得寄存器值。如果将它看成向量处理器，那么线程束就是单个指令流，每个线程只是一个分量。 每一个处理器中都会同时存在大量线程束，通过快速切换线程束执行来隐藏访存等耗时操作的延迟。 GPU指令流水线 gpu流水线和cpu类似，分为取指，译码，调度，读寄存器，执行，写回等阶段。 取指和译码在gpu中由于同时存在多个线程束且每个线程束的执行进度不一致，因此取指单元中需要保存多个pc值，然后调度单元根据线程束的状态选 ...

介绍tage分支预测器论文 tage-sc-l分支预测器 tage分支预测器是现代高性能处理器中常用的预测器，他使用pc和全局历史作为输入，通过哈希得到index和tag进行查表，并且谨慎的只更新少数表来减少表项的占用。在一些测试集中可以达到95%以上的准确率且低于5MKPI 预测tage分支预测器由一个base表和多个tage表组成。 base表是一个类gshare预测器，使用pc的哈希作为index。 tage表由三个部分组成，tag，u和ctr。其中ctr为饱和计数器。使用pc和不同长度的全局历史查表 tage表的查表方式为将pc和n位的全局历史使用不同的哈希函数分别获得index和tag，然后使用index获得表中的某一项表项，再使用tag进行匹配表项中的tag，如果匹配成功则使用表项中的饱和计数器作为最终结果。 如果有多个表成功匹配，则将最长历史的表的结果作为最终结果，如果全部没有匹配，则使用基础预测器作为最终结果 在实现时，如果历史长度较短，则可以直接将历史异或，进行折叠来获得index和tag。如果历史长度较长，则可以选择历史中的某几位和上一步计算结果进行逻辑操作来生成 ...

简介简截是一款截图软件。它的主要功能是图片透明化。 透明化前 透明化后 此外他还支持多种截图模式并且可以图片上编辑 下载及代码 所有版本 最新版本（密码8nq4） 文档 github地址页 欢迎拿走源码自己修改。也可以在评论区提意见（我设置了邮箱提醒）。 功能介绍 支持开机自启，自动更新，历史记录保存，自动复制到剪切板等功能 多区域截图 ​ 滚动截图 使用opencv库的图像拼接实现，并且加上了多线程，位置在Capture_window/…/Scroll_handle。 此外滚动截图可以调整滚动速度。滚动速度较快时可以利用所有cpu。  绘制 当前仅支持笔，荧光笔和文本绘制，并且支持撤销、恢复和擦除。 透明 目前仅可以做到对某一个色素透明，对于渐变和拍屏无效。并且由于文字都是由不同种类像素组成因此无法做到选取文字（正好下学期有图像处理，看看通过反锯齿可以直接把文字的范围弄出来）。 oc ...

自动操作是一款基于无障碍服务的安卓软件，可以提供自动点击，滚动，条件跳转等操作。 启用 首先点击设置按钮开启无障碍服务及关闭电源优化，然后开启服务，只有在开启服务后才能进行后面的设置。 悬浮球用于需要手动启动的配置，可以在配置页选择配置，然后点击悬浮球开始自动操作 配置添加配置 如图所示点击右下角的+号可以新建配置。点击配置右侧的三个点可以进入配置页面，长按进行删除和置换位置。点击可以选择下次触发的配置 修改配置 页面可以简单理解为应用，当切换应用时会同时检测当前页面的配置，如果发现有自启动的配置将会自动运行配置 配置是由一个个的操作组成的，进行完上一个操作之后会自动进行下一个操作，在配置页面中运行操作的顺序是从上到下。 点击步骤右侧的加号可以添加操作，共有如下五种操作。添加后点击图标可以进行操作的配置页面 所有配置都有重复次数和延迟两个属性。延迟表示在上一个操作结束之后需要等待多长时间才进行该操作。其中每一个操作图标下面的数字表示延迟 点击操作 点击操作可以根据屏幕的绝对坐标，控件，文本进行点击。 控件点击： 如下图所示，控件是无障碍服务可以操作的部分。使用控件进行点击的优点 ...

理解遗传算法思路来源于基因进化。即基因会随机突变，复制（生出新个体），最终适应的种群将会繁衍（找到最优解）。本质上是一种并行的搜索算法，可以自适应的得到最优解。 因此遗传算法的几个关键点是定义突变，复制过程，定义搜索空间和如何选择优良个体（定义适应度） 过程 随机的创建种群（例如二维搜索中随机的创建搜索点） 定义适应函数（二维搜索中和终点的距离） 选择出适应的个体作为父母进行繁衍 通过交叉和复制产生后代：从父亲和母亲中抽取一部分特征作为子集并合并，另一部分直接复制优秀的父亲和母亲 对一些个体进行变异 def nextGeneration(currentGen, eliteSize, mutationRate): popRanked = rankRoutes(currentGen) selectionResults = selection(popRanked, eliteSize) matingpool = matingPool(currentGen, selectionResults) children = breedPopulation(matingpool ...

简介recast navigation是基于三角形网格的寻路系统，他相比四边形网格可以减少网格数量从而提高网格速度。它具体可以分为两部分，recast和detour。recast是构建寻路网格的过程，detour是利用网格寻路的过程 recast过程划分参考 具体构建过程是根据Sample_SoloMesh.cpp中的handleBuild 体素化在体素化阶段，mesh将被转化成体素（一个个小的长方体）。 体素化的目的是填充heightfield的span区域，span是一个二维数组，长和宽是包围盒内体素的长和宽。而每一个span是rcSpan*类型，他是一个链表，链接竖直方向的体素 构建过程： rcAllocHeightfield：new一个rcHeightfield实例 rcCreateHeightfield： 初始化rcHeightfield rcMarkWalkableTriangles： 根据传进来的mesh（顶点和三角形）计算出哪个三角形可以通过。具体方法为计算每个三角形的法线，如果法线角超过设定值则认为不可通过 rcRasterizeTriangles(rcCon ...

介绍后缀中的后缀是一个字符串的所有后缀。例如abcde的后缀有5个，分别是abcde,bcde,cde,de,e。 后缀树是一种字符串算法，它可以被用于字符串搜索，寻找最长公共子串，查找匹配次数等。常见的匹配算法如KMP算法都是在模式串上做文章，而后缀树确实在匹配串上构建的。 后缀树需要满足五条性质： 如果字符串长度为n，那么后缀树中有n个叶子 除了根节点，所有除叶结点外的节点都至少有两个儿子 每条边上都标有非空子串S 没有同一个点延伸出的两条边上标记的字符串首字母相同 从根节点拼接每条边的子串到叶结点便可以获得一个后缀 如图左边是BANANAS的后缀树，右边abcabx的后缀树。 是否存在abcab的后缀树呢？ 答案是不存在，因为现在ab的后缀是abcab的前缀，也就是说现在想要满足条件4那么原来连接叶子节点4的边中子串要由x变成空串，但是这又违反了规则3. 为了避免上述问题，可以在字符串后面加上一个不在字符集中的字符$ 应用 查询字符串是否是某一字符串的子串： 使用后缀树进行匹配，如果匹配串所有字符匹配成功则为子串 查询是否为后缀： 如果匹配到叶子节点正好匹配结束则为后缀 ...

深度优先和广度优先可以参考这篇文章 a*算法可以参考这篇文章 b*算法b*搜索相对于a*搜索速度快了几十倍，但是他不能够保证最优解，和贪心算法有些类似。 定义： 探索节点：起始探索节点为原点 自由探索节点： 还可以进行下一步的探索节点 绕爬探索节点： 如果前方有阻挡，探索节点将试图绕过阻挡，绕行中的探索节点称为绕爬节点 算法过程： 起始，探索节点为原点，向目标进发 自由节点在前进过程中判断前方是否有障碍 有障碍，则分出左右两个分支试图绕过障碍，绕过障碍后节点将变成自由节点 无障碍，向目标前进一步 bool map[boundary.height()][boundary.width()];// 初始化map为0// 第二个参数为父节点Node* begin_node = new Node(point, null);map[point.x][point.y] = 1;begin_node->direction = getDirection(begin_node, end_node);free_nodes.push(begin_node); // 自由节点while(!fr ...