Chapter 0

md语法

2级标题

3级标题

4级标题

5级标题
6级标D

一级标题

二级标题

斜体字 >>就是在字的前后各添加一个星号
斜体字 >>也可以在字的前后各添加一个下划线
粗体字 >>就是在字的前后各添加两个星号
粗体字 >>也可以在字的前后各添加两个下划线
粗斜体字 >>就是在字的前后各添加三个星号
粗斜体字 >>也可以在字的前后各添加三个下划线
世界是平坦的。 我们现在知道世界是圆的。 这是测试脚注1。

这是数字脚注2。这是文字脚注3

1

标识符可以是数字或文本。但不能包含空格或制表符。
2:数字脚注测试说明。
3:文本脚注测试说明。 需要添加下划线的内容

  Markdown本身并没有该语法，这只是一种非常简单的替代方法；当然Markdown语法支持html语句，可以直接用html标签来实现，请自行搜索学习。 字体颜色、大小、字体类型
这是蓝色3号楷体子
这是红色字体，可单独配置一项
这是4号字体，可单独配置一项
不需要高亮，重点提示需要高亮显示，<mark> 是HTML5的新标签。

块引用
blockquote
嵌套主体

第一层嵌套

第二层嵌套

在块引用中添加标题

  1. 在块引用添加项目编号
  2. 在块引用添加项目编号
  • 在块引用添加项目符号
  • 在块引用添加项目符号
  • 在块引用添加项目符号
  • 粗体文本 和 斜体文本
  1. 第一项
  2. 第二项
  3. 第三项
  4. 第四项
  5. 第五项
  6. 第六项
    1. 缩进项（键入4个空格或制表符）
    2. 缩进项（键入4个空格或制表符）
  • 第一项
  • 第二项
  • 第三项
  • 第四项
  • 第五项
  • 第六项
    • 缩进项（键入4个空格或制表符）
    • 缩进项（键入4个空格或制表符） main()函数中调用printf()函数

for(i=0; i<8; i++) { printf("这是代码块测试代码"); delay_ms(1000); /* 延时1s */ }

for(i=0; i<8; i++) {
    printf("这是代码块测试代码");
    delay_ms(1000);                 /* 延时1s */
}

for(i=0; i<8; i++) {
    printf("这是代码块测试代码");
    delay_ms(1000);                 /* 延时1s */
}

我常用的搜索引擎是百度 我常用的搜索引擎是百度。 https://markdown.p2hp.com xxxx@email.com | 标题 | 标题 | | --- | -------------- | | 单元格 | 单元格 | | 单元格 | 单元格 |

标题标题
单元格单元格
单元格单元格

没有使用反斜杠，这是4级标题

#### 使用反斜杠，这就是4个#号

Week 1

TIME: 10.30 - 11.2

TASK:

  1. 介绍和理解ANNS(blog)
  2. 介绍和理解ANNS(paper)
  3. 跑个ANNS，从实践角度去认识一下ANNS，具体可以抽象成哪些步骤操作，输入输出

项目背景 :现在论文基于忆阻器的硬件架构主要围绕神经网络(CNN,MLP)加速展开

所以目前定的课题是：研究如何用ReRAM这种存算一体的忆阻器来加速ANNS应用

所以第一步理解ANNS的实现原理，以及上手跑一跑ANNS，同时把《基于忆阻器的近似计算方法》这篇论文看了，看一下如何推理整个过程 ANNS在算两个向量间距离公式有：Manhattan距离（L1范数），Euclidean距离（L2范数），Cosine距离（1-cosine相似度），角距离，Hamming距离，Dot Rroduct距离 目前思路：是否可以从这几个距离算法在RRAM上进行加速

介绍和理解ANNS(blog)

图

宏观认识ANNS：

brute-force搜索的方式是在全空间进行搜索，为了加快查找的速度，几乎所有的ANN方法都是通过对全空间分割，将其分割成很多小的子空间，在搜索的时候，通过某种方式，快速锁定在某一（几）子空间，然后在该（几个）子空间里做遍历。

ANNS实现方法：

树1、哈希方法2、矢量量化方法3

1.树

(1)KD树

1

K-D树

划分标准 ： 求每一个维度的方差，选择方差最大的那个维度开始划分。

缺点 ： kd-trees are not suitable for efficiently finding the nearest neighbour in high dimensional spaces. In very high dimensional spaces, the curse of dimensionality causes the algorithm to need to visit many more branches than in lower dimensional spaces. In particular, when the number of points is only slightly higher than the number of dimensions, the algorithm is only slightly better than a linear search of all of the points.

(2)Annoy(Spotify推荐系统)

核心：不断用选取的两个质心的法平面对空间进行分割，最终将每一个区分的子空间里面的样本数据限制在K以内。

struct ANNOY_NODE_ATTRIBUTE Node {
S n_descendants;
union {
  S children[2]; // Will possibly store more than 2
  T norm;
};
T dot_factor;
T v[1]; // We let this one overflow intentionally. Need to allocate at least 1 to make GCC happy保持原始特征
};

2.哈希方法（典例代表局部敏感哈希）

2

(1)一些名词

局部敏感 : 相近的样本点对比相远的样本点对更容易发生碰撞

哈希加速查找 ：首先找到查询样本落入哪个cell(桶)中， 如果空间的划分是在想要的相似性度量下进行分割的， 则查询样本的最近邻将极有可能落在查询样本的cell中 ，如此只需要在当前的cell中遍历比较。

多表哈希 ：对于单表哈希，当哈希函数数目K取得太大，查询样本与其对应的最近邻落入同一个桶中的可能性会变得很微弱，针对这个问题，我们可以重复这个过程L次，从而增加最近邻的召回率。这个重复L次的过程，可以转化为构建L个哈希表，这样在给定查询样本时，我们可以找到L个哈希桶（每个表找到一个哈希桶），然后我们在这L个哈希表中进行遍历。这个过程相当于构建了K*L个哈希函数

多表哈希中K,L如何选取 : 哈希函数数目K和哈希表数目L,哈希函数数目K如果设置得过小，会导致每一个哈希桶中容纳了太多的数据点，从而增加了查询响应的时间；而当K设置得过大时，会使得落入每个哈希桶中的数据点变小，而为了增加召回率，我们需要增加L以便构建更多的哈希表，但是哈希表数目的增加会导致更多的内存消耗，并且也使得我们需要计算更多的哈希函数，同样会增加查询相应时间。这听起来非常的不妙，但是在K过大或过小之间仍然可以找到一个比较合理的折中位置。通过选取合理的K和L，我们可以获得比线性扫描极大的性能提升。

Multiprobe : 对于构建的L个哈希表，我们在每一个哈希表中找到查询样本落入的哈希桶，然后再在这个哈希桶中做遍历，而Multiprobe指的是我们不止在查询样本所在的哈希桶中遍历，还会找到其他的一些哈希桶，然后这些找到的T个哈希桶中进行遍历。 如果不使用Multiprobe，需要的哈希表数目L在100到1000之间，在处理大数据集的时候，其空间的消耗会非常的高，因为有了上面的Multiprobe的策略，LSH在任意一个哈希表中查找到最近邻的概率变得更高，从而能减少哈希表的构建数目。

其他哈希桶的选取准则 ：跟查询样本所在的哈希桶邻近的哈希桶，“邻近”指的是汉明距离度量下的邻近。

LSH ：

  • K，每一个哈希表的哈希函数（空间划分）数目
  • L，哈希表（每一个哈希表有K个哈希函数）的数目
  • T，近邻哈希桶的数目，即the number of probes

根据可使用的内存大小选取L，然后在K和T之间做出折中：哈希函数数目K越大，相应地，近邻哈希桶的数目的数目T也应该设置得比较大，反之K越小，L也可以相应的减小。

获取K和L最优值的方式可以按照如下方式进行：对于每个固定的K，如果在查询样本集上获得了我们想要的精度，则此时T的值即为合理的值。在对T进行调参的时候，我们不需要重新构建哈希表，甚至我们还可以采用二分搜索的方式来加快T参数的选取过程。

(2)LSH开源工具包

LSHash

使用单哈希表，哈希函数的系数随机生成。

def _generate_uniform_planes(self):
    """ Generate uniformly distributed hyperplanes and return it as a 2D
    numpy array.
    """

    return np.random.randn(self.hash_size, self.input_dim)//hash_size为哈希函数的数目即K

FALCONN

暂时未读懂，略

3.矢量量化方法（vector quantization）

矢量量化方法 : 将一个向量空间中的点用其中的一个有限子集来进行编码的过程。

关键 ： 码本的建立和码字搜索算法

资料来源： ANN Search

介绍和理解ANNS(papers)

一、ANNS实现思路：

  • 基本思路： The ANNS methods usually first construct an index structure to organize data items and then perform a querying search algorithm based on this index to retrieve the nearest neighbour results for the given queries.

    通过牺牲一小部分的精度，换取几个量级检索速度提升。具体就是先将数据按某种形式安排，在后续查找可以加快查询效率。

  • 基本方案：

    • 缩短距离计算的时间 ：量化
    • 减少距离计算的次数 ：树、哈希、图

  • 根据 Indexing and Searching 的类型分类实现思路: Hashing-based、Parition-based、Graph-based、Compression-based

categoryHashing-basedParition-basedGraph-basedCompression-based1
LSH (locality sensitive hash-based)2KD-tree3KGraphFaiss
Annoy4Small World GraphScaNN
hierarchical k-means tree5Navigating Spreading-out Graph
random projection tree (heuristic-based)
  • advantage
    • Faster search
    • Don not necessarily have to exact neighbors
    • Trade off : runtime,accuracy,and memory-consumption
    • a sense of scale : billion-scale data on memory

二、树方法

  • 基本思路：将数据按平面分割，用二叉树来代表每一分割的部分，便于后续搜索

  • 建树过程：

    1. 沿着笛卡尔坐标，选择方差最大的维度进行划分
    2. 每个维度采用中位数作为划分点，划分并分配数据至叶子结点
    3. 每个叶子结点重复建树过程，直至叶子结点只有一个数据点 KD树

  • 搜索过程：

    1. 依据二叉树搜索算法找到搜索点所在的叶子节点空间，计算叶子节点上的数据点与搜索点之间的距离，记作当前最短距离
    2. 回溯父结点，判断搜索点当前最短距离构成的超球体与父结点的另一个结点构成的超矩形是否相交，如果没有相交，继续回溯直至根节点，否则递归搜索另一个结点

  • 优缺点： KD树因为有回溯的机制，它能够保证搜索回来的点是精确的，同时相比与线性查找，它计算距离的次数是减少了，但它只适合用于低维数据的检索，维度越高，搜索点当前最短距离构成的超球体与超矩形的相交概率越大，此时就趋近于线性的搜索。

  • 建树过程：

    1. 随机选择两个点，确定划分超平面，划分为两个子空间
    2. 每个子空间按相同方式递归迭代划分，直至子空间数据量少于K Annoy
    • 可能出现的问题：
      • 如果我们想要 Top K 的点，但是该区域的点集数量不足 K，该怎么办？
      • 如果真实的 Top K 中部分点不在这个区域，该怎么办？
    • 解决办法：
      • 使用优先队列（priority queue）：将多棵树放入优先队列，逐一处理；并且通过阈值设定的方式，如果查询的点与二叉树中某个节点比较相似，那么就同时走两个分支，而不是只走一个分支
      • 使用森林（forest of trees）：构建多棵树，采用多个树同时搜索的方式，得到候选集 Top M（M > K），然后对这 M 个候选集计算其相似度或者距离，最终进行排序就可以得到近似 Top K 的结果

  • 搜索过程：

    1. 将每一颗树的根节点插入优先队列
    2. 搜索优先队列中的每一颗二叉树，每一颗二叉树都可以得到最多 Top K 的候选集
    3. 删除重复的候选集
    4. 计算候选集与查询点的相似度或者距离
    5. 返回 Top K 的集合

三、哈希方法

2

LSH（Locality-Sensitive Hashing,局部敏感哈希）

  • 基本思路 : 通过一系列哈希函数将附近的点映射到同一个桶中，组成哈希表,构建多个独立的哈希表增加候选点数量，提升精度
    (哈希函数满足局部敏感：两个点距离越近，哈希值相同概率越高)

  • 搜索过程 :
    把搜索点通过同样的哈希函数映射到某个桶里，对桶里的所有数据点求距离得到最近的数据点，因为只对一个桶里的数据做计算，而不是对所有数据计算，所以大大减少了距离计算的次数，提高了效率，而且因为同一个桶都是哈希敏感的，桶里的点大概率是相近的点，因此这种计算方式对精度的影响也不会很大；同时它可以通过构建多个哈希表的形式，把每个哈希表碰撞到的桶的数据做一个并集，再线性计算距离即可，避免出现单个哈希表把相近的数据点划分到不同桶里影响精度。

  • 两种不同的LSH :

    • 使用Jaccard系数度量数据相似度时的min-hash
    • 使用欧氏距离度量数据相似度时的P-stable hash

    无论是哪种LSH，其实说白了，都是将高维数据降维到低维数据，同时，还能在一定程度上，保持原始数据的相似度不变。LSH不是确定性的，而是概率性的，也就是说有一定的概率导致原本很相似的数据映射成2个不同的hash值，或者原本不相似的数据映射成同一hash值。这是高维数据降维过程中所不能避免的（因为降维势必会造成某种程度上数据的失真），不过好在LSH的设计能够通过相应的参数控制出现这种错误的概率，这也是LSH被广泛应用的原因

  • 实例:
    k-shinging 和 one-hot编码将文本转换为稀疏向量，然后用最小哈希创建签名，签名被传递给LSH流程以剔除部分候选对
    1. Shingling：把文档转换成集合
    2. Minhashing：把大规模集合转换成短小签名，但是保留相关性
    3. LSH Query：计算可能相似的签名对,调节 M，b，r用相似的签名来得到所有的文档对，但是剔除那些并不相似的签名多数对，检查主要内存，候选对并没有相似签名。

资料来源： LSH的实现原理

代码实操： LSH Code

论文参考

[1]M. Slaney and M. Casey, "Locality-Sensitive Hashing for Finding Nearest Neighbors [Lecture Notes]," in IEEE Signal Processing Magazine, vol. 25, no. 2, pp. 128-131, March 2008, doi: 10.1109/MSP.2007.914237.

Pseudocode：

获取数据 n 个 m 维的数据
随机生成 K 个 m 维的点
while(t)
    for(int i=0;i < n;i++)
        for(int j=0;j < k;j++)
            计算点 i 到类 j 的距离
    for(int i=0;i < k;i++)
        1. 找出所有属于自己这一类的所有数据点
        2. 把自己的坐标修改为这些数据点的中心点坐标
end

四、矢量量化方法

五、图方法

NSW (Navigable Small World Graph)

  • 基本思路：

    1. 随机选择1个元素，放入到candidates当中
    2. 从candidates中选取最近邻节点c，将这些元素的邻居节点放置到q当中
    3. 从candidates中移除最近邻节点c
    4. 如果c的距离远大于result中的第k个节点，跳出循环
    5. 否则，对于c的每个邻居节点，遍历其邻居，如果没有在visited set里面。
    6. 将e加入到visited set， candidates， tempRes
    7. 遍历完成candidate中所有的节点后，把tempRes的结果传入到result
    8. 重复执行上述步骤m遍, 返回result中最优的k个近邻结果。
    K-NNSearch(object q,integer:m,k)
 TreeSet[object]tempRes, candidates, visitedSet, result
    for(i<-0; i< m; i++) do:
        put random entry point in candidates
        tempRes<-null
        repeat:
            get element c closest from candidates to q
            remove c from candidates
            #checks to p condition:
            if c is further than k-th element from result
                than break repeat
            #update list of candidates:
            for every element e from friends of c do:
                if e is not in visited Set than
                add e to visited Set, candidates, tempRes
        end repeat
        #aggregate the results:
        add objects from tempRes to result
    end for
 return best k elements from result

HNSW(Hierarchical Navigable Small World Graph)

资料来源:NSW & HNSW

Process：

  1. 在Layer = 0 层中，包含了连通图中所有的点。
  2. 随着层数的增加，每一层的点数逐渐减少并且遵循指数衰减定律
  3. 图节点的最大层数，由随机指数概率衰减函数决定。
  4. 从某个点所在的最高层往下的所有层中均存在该节点。
  5. 在对HNSW进行查询的时候，从最高层开始检索。

输入：

输出：插入节点q后的hnsw网络结构

Product Quantization

资料来源: Faiss PQ_BLOG

代码实战:PQ_TEST

process：

  1. Taking a big, high-dimensional vector,
  2. Splitting it into equally sized chunks — our subvectors,
  3. Assigning each of these subvectors to its nearest centroid (also called reproduction/reconstruction values),
  4. Replacing these centroid values with unique IDs — each ID represents a centroid

\( \int x dx = \frac{x^2}{2} + C \)

资料来源：

Deep Learning for Approximate Nearest Neighbour Search: A Survey and Future Directions

图片名称

anns practice

Week 2

学习ReRAM

目录

  • RRAM技术的简介1
  • RRAM设备的制备和性能2
  • RRAM的表征与建模3
  • RRAM阵列架构4

资料来源： Resistive Random Access Memory(RRAM): From Devices to Array Architectures

词汇总结

fabrication 制备

hierarchy 层次

stores the charge储存充能

cross-coupled inverters交叉耦合的反相器

cell capacitor 电容器单位

the floating gate of the transistor晶体管的浮栅

nanosacle纳米尺度

degradation 降低

  • 对传统存储器（SRAM、DRAM、FLASH）进行了简要的回顾。

  • 介绍了非易失性存储器（non-volatile memory, NVM）RRAM的基本原理。

  • 其基本原理是：

    • (1) 在未加电压时，由于电极间氧化层默认绝缘，RRAM两端为高阻抗状态（HRS）；
    • (2) 在两端加一电压，若该电压超过“形成电压”（forming voltage,\( V_{form} \) )时，则氧化层中间形成“导电纤维”（conductive filatment, CF），从而进入低阻抗状态（LRS）（比HRS约低三个数量级）；
    • (3)以双极型（bipolar）为例，若给处于LRS的RRAM两端加一反向的电压，器件将从LRS再次变为HRS。

  • 将RRAM与市面上常见的存储器以及同属于NVM的其他的STT-MRAM、PCRAM做对比，强调了RRAM具有面积小、存取速度快、功耗极低的特点。

  • RRAM基础

    RRAM
    • 氧化物材料：NiO、TiOx、HfOx等。
    • 电极材料：TaN或TiN。
    • 物理原理：基于氧空位（oxygen vacanciy，Vo）形成CF机理——另有一种基于金属原子形成CF机理的CBRAM。
    • 总结了可能用来充当氧化物介质和两端电极的材料（以一张元素周期表形式给出）。
    • 介绍了两种阻变模式：单极型 (unipolar)和双极型 (bipolar)——本书重点讲bipolar。
2

RRAM设备的制备和性能

  • 器件制备
    • 制备流程：PVD（physical vapor deposition）制备TiN电极->CMP（chemical mechanical planarization）->ALD（atomic layer deposition）制备HfOx氧化层->PVD制备TiN顶层电极和Hf capping layer->进行表面钝化。
    • 关键指标①——HfOx thickness，减小厚度可有效降低 \( V_{form} \)约为线性降低），但是厚度太小，容易造成短路，需要对表面粗糙度更好的控制（tradeoff-I）。关键指标②——Hf capping layer thickness，增加厚度可有效降低 \( V_{form} \) （线性降低）。无论是通过①还是②来控制，都会因为HRS更低的阻抗而牺牲On/Off ratio（tradeoff-II）。
    • 小于10nm的RRAM已被成功制造。
  • 器件性能
    • 编程速度。因为CF的形成时个动态过程，需要时间，提升“编程电压”（programming voltage，\( V_{prog} \) ）可以加快编程速度，典型值：每提升0.25V/0.5V，对 \( 1\mu m/10nm \) 的尺寸的RRAM编程速度提升一个数量级。但是注意：过高的 可能会带来器件击穿（永久性损坏）的问题。
    • 器件不一致（variability）的问题。RRAM的Variability问题主要表现在：(1) 时间上，在set/reset每个周期（cycle）表现不一致；(2) 空间上，器件与器件之间表现不一致。前者主要是由于HRS状态的较大变化（由于隧道电流的存在）。
    • MLC（multi-level cell）多态RRAM块，可以直接提高存储密度（memory density）。MLC原理可能是由于越大的 set compliance voltage ( \( V_{set} \) ) 会造成CF的直径越大，从而电阻越小，因此会导致多个电阻态的存在（而不是之前的LRS和HRS两个态）。实践上，需要使用纠错逻辑来稳固每个态的电阻值分布，使得态之间更分明（distinguishable），但是会牺牲大量速度（tradeoff-III）。
  • 器件可靠性
    • 循环持久性（cycling endurance）。接着之前的讨论，cycle可能会导致器件的变化。实验表明不同的 \( V_{set} \) 会导致不同的变化模式（HRS、LRS两态的电阻随cycle次数的变化图形）。较低的 \( V_{set} \) 会导致set失败（器件被锁定在HRS），而较高会导致reset失败（器件被锁定在LRS）。而适中的 \( V_{set} \) 则会相对平缓的变化，因此，需要根据实际器件来寻找一个合适的 \( V_{set} \)
    • 数据遗忘 （data retention）——典型值：85°C环境下维持10年。较低的 \( V_{set} \) 会导致更差的数据维持性，而较高的 \( V_{set} \) 又要考虑power的问题。接着，又讨论了工艺上对数据维持性的几种优化方法。

3:

RRAM的表征与建模

物理方面（略）

  • 1T1R阵列
RRAM
  • cross-poing(交叉点)阵列
RRAM