跳转至

2023

Localhost

环回地址

  • 环回地址,是指不离开主机的数据包(也就是说,这些数据包不会通过外部网络接口)。
  • 任何发往环回地址的数据包,其处理都在 TCP/IP 协议叠的链路层中实现的。这些数据包不会向下交由网卡(NIC)或者设备驱动程序处理,既不应在电脑系统以外出现,也不可经路由器转发。
  • 环回地址是主机用于向自身发送通信的一个特殊地址,帮助我们在同一台主机上实现client和server的功能。
  • 运用本地环回机制,便可在主机上运行网络服务,期间不须安装实体网络接口卡,也无须将该服务开放予主机所在网络。

localhost

  • localhost 是一个别名,用于指代为环回保留的 IP 地址(环回地址)。
  • IPv4使用 A 类地址的最后一个块(从 127.0.0.1 到 127.255.255)
    • 发送到这些地址(127.0.0.1 到 127.255.255.255)的所有数据包都会返回本机。
  • 而IPv6保留第一个(0:0:0:0:0:0:0:1 - 或 : :1)作为其环回地址。

0.0.0.0 任意ip

  • 0.0.0.0并不是一个真实的的IP地址,它表示本机中所有的IPV4地址。
  • 监听0.0.0.0的端口,就是监听本机中所有IP的端口。
  • 0.0.0.0是不能被ping通的。

localhost 与 127.0.0.1区别

  • localhost(本地主机)不是专门指 127.0.0.1,而是指为环回保留的整个 IP 地址范围。
    • 注意你不能总是使用127.0.0.1进行环回。
    • 仅限 IPv6 的系统不会响应此类请求,因为它们的 localhost 链接到地址::1。
    • 修改/etc/hosts文件即可修改环回的地址。但是十分不建议这样做,很可能导致本地服务崩溃
  • 请求的发送方式不同???
    • 127.0.0.1是通过网卡传输,依赖网卡,并受到网络防火墙和网卡相关的限制。
    • localhost不会解析成ip,也不会占用网卡、网络资源。一般设置程序时本地服务用localhost是最好的。

如何将环回地址某端口上的服务映射到外部网络接口

  • 可以使用ssh转发ssh -L 1313:localhost:8020 [email protected]将服务器localhost:1313上的内容转发到本地8020端口
  • hugo server -D -d ~/test/public默认会部署在localhost上
  • 解决办法hugo server --bind=202.38.72.23 --baseURL=http://202.38.72.23:1313 -D -d ~/test/public

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

https://blog.nnwk.net/article/107

UnimportantView: Game

关于偏好的循环

轮回与回旋镖:小别胜新婚

我发现我陷入了一种循环:

正向:

  1. 美术音乐和玩法的新鲜感:一开始游戏新鲜内容好奇,然后在新鲜内容耗尽时。
  2. 成就感
  3. 史诗故事感(真实代入感),和领悟
  4. 刺激感?(不适用我这里

反向:

  1. 日常的枯燥的刷任务积累,实在令人厌烦。
  2. PVP的队友的争吵和失败的挫败感也会大幅降低游玩意愿

关于PVP 和 PVE

如果在游玩的时候,如果没有对面是电脑的想法,任务的难度就是合适的,有趣的,或者有挑战的。

如果意识到了NPC反应的模板化,枯燥化,简单化的PVE就不行。 PVP可以避免这三点,但是组队的门槛、队内的矛盾、和失利会带来反向效果。

比如GTA5 online通关之后,上线之后所有东西都尝试过后,就没有留恋的意思了。除非将NPC接入AI并且动态调节难度,就可以避免这点。

如何筛选适合的游戏

现状:游玩时间少,时间碎片化,无规律

  • 游玩体验一定要舒适
    • 体验的主线内容:真实的幻想世界
      • 轻松快乐的主线剧情体验,(-20 ~ 35)
        • 一起提供代入感和沉浸式的游玩体验
        • 无剧情该项为0
        • 扣分:枯燥拖沓的演出(-10)
        • 加分:刺激有趣的剧情表演(+10)、诙谐的台本(+5),令人有所感悟的主线故事(+15)、动容的NPC故事(+5)
      • 有趣新颖的玩法(30)
        • 新鲜玩法(15)
        • 眼前一亮的细节(5)
        • 足够深的游戏内容,来随意探索;(10)
          • 或者足够精致宏大的单机主线内容(FF,大镖客2)
      • 精致华丽的美术(30)
        • 交互界面UI(3)
        • 开放世界风景(7) 震撼华丽的大场景可以弥补角色喜爱塑造的缺失
        • 令人喜爱的角色(15)
        • 动听的音乐(5)
    • 日常周常体验(40)
      • 耗时/门槛(20):
        • 无需投入大量前期时间才能正常体验
          • 经验训练技巧
          • 前置任务过多
        • 没有强制的任务指标来限制/延长在线时长
      • 收获感(10):投入有回报(货币)、提升(数值)
      • 新鲜感(10):有Rougelike元素,避免无聊
    • 手游根据逼氪程度减分
      • 200以上减5;1000以上减10

适合的类型:

  • 合家欢小游戏(主玩法,轻竞技):
    • 蛋仔、任系游戏(惊奇)
  • 主剧情的单机RPG游戏
    • 王国之泪,星际争霸(金手指)
  • 主美术的二次元轻度手游
    • 铁道
  • 网状叙事的电影史
    • 博德之门3

不适合的类型:

  • 有紧迫任务目标的游戏(大量限时任务的网游)
  • 快乐建立在胜负上的竞技类游戏(PVP游戏)

举例

231221 少女前线2 追放

首先,我没有玩过少前1,和战棋类游戏,和偏写实的剧情。

  1. 剧情与主线:
    1. 沉浸感低:谜语人,各种看不到的名词。我不知道是为了装逼还是少前1的基本概念。好的游戏,都不会在玩家理解上制造问题。
    2. 个人感觉写实的剧情立意不足,和目的性,意义行解释不清楚,导致游玩时,感觉动力不足。 由于本人并不喜欢打杀。我玩游戏也是认真玩的,如果剧情感觉不够恢弘,写实的枪战细节剧情感觉不是很动人。(可能是玄幻和幻想游戏玩多了,写实类剧情完全没接触过),需要平衡好真实感与现实的繁琐程度
  2. 美术
    1. UI简洁好看
    2. 好但可以更好,人物, 闪电姐的脸总感觉怪怪的胖胖的。黑丝等拟真质感确实不错。但是人物服饰什么的都是冷淡风,只能说之后的潜力很大。(比如像 尘白禁区泳装一样。
  3. 玩法
    1. 好但可以更好,利用地形杀,和道具之类的。(有潜力

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

Optimization Outline

Sun's 常见超线性加速的情况

http://www.cs.iit.edu/%7Esun/cs546.html#materials

https://annals-csis.org/Volume_8/pliks/498.pdf

Superlinear Speedup in HPC Systems: why and when?

  1. Cache size increased 多核的cache总size增加
  2. 在大多数的并行计算系统中,每个处理器都有少量的高速缓存,当某一问题执行在大量的处理器上,而所需要的数据都放在高速缓存中时,由于数据的复用,总的计算时间趋于减少,如果由于这种高速缓存效应补偿了由于通信造成的额外开销,就有可能造成超线性加速比。
  3. Overhead reduced 锁减少,粒度变小
  4. Latency hidden 数据预取更多了
  5. Randomized algorithms
  6. 在某些并行搜索算法中,允许不同的处理器在不同的分支方向上同时搜索,当某一处理器一旦迅速的找到了解,它就向其余的处理器发出中止搜索的信号,这就会提前取消那些在串行算法中所做的无谓的搜索分枝,从而出现超线性加速比现象
  7. Mathematical inefficiency of the serial algorithm 改并行算法
  8. Higher memory consumption access cost for in sequantial processing

应用优化前提

  1. 迭代进行 :分析程序最大热点(perf,vtune工具)->优化该热点—>分析程序最大热点->……
  2. 自顶向下分析优化程序热点的思路

    1. 全局算法的调研、理解、总体设计改进
    2. 程序任务划分,并行各部分模块
    3. 仔细分析热点的kernel循环
  3. 基本了解物理数学背景公式

  4. 阅读代码,明白实现
  5. 从main函数开始看的都是大撒比,没错,说的就是我
  6. 带着问题看,才能快速抓住重点
  7. 建议串行直接用vtune判断算法热点和时间
  8. 粗略判断热点
  9. 加入各部分热点的时间输出 (必需的:积极的正向反馈,会提高积极性和理清思路)
  10. 寻找合适的大例子
#include <omp.h>
itime = omp_get_wtime();
printf("\nTime taken is %f",omp_get_wtime()-itime);
  1. 运行n次求得平均值; 或者对不同大小的例子在不同参数下的效果拉图对比
  2. 单机不同数量多核,同机器的不同编译器,不同核心kernel/CPU
  3. warmup=10 loop=50 先热身10次,然后循环10次
./SLIC_0805_3 |tee 3.log && ./SLIC_0805_3 |tee 3.log && ./SLIC_0805_3 |tee 3.log

7. 每次优化基给予正确性的评价,并对负优化进行解释。

  1. 查看汇编
  2. 基本并行加速实现后,vtune检查访存,或者用Intel advisor的Roofline Model来分析。
  3. 新函数用 utils.cpputils.h

应用类型及其常见优化

  1. 计算密集
  2. 采用适合并行平台的算法
  3. CPU核数利用率
    1. 多进程
      1. 进程池动态调度
    2. 多线程(对于特别小的例子,一个cpu的核就够用了)
      1. 线程亲和性
      2. 线程动态调度
  4. 向量化率(提高单次计算量)SIMD
    1. 自动向量化提升有限吗?怎么写出好让编译器自动向量化的代码
      1. https://blog.csdn.net/zyl910/?type=blog SIMD测试比较
    2. pragma omp parallel for simd
    3. 循环展开,凑够无依赖计算,填满流水线avx512的宽度(8个float)
    4. intrins接口手动向量化
    5. 注意边界,不足8个单独计算
    6. 手动向量化avx2一般会快一些
  5. 降低计算量技巧
    1. 其他各种小技巧
    2. 使用掩码代替分支判断
      1. 增A:|A 删A:&(~A)判断:&A!=0
      2. https://blog.csdn.net/zyl910/article/details/7345655
    3. 替换if tmp[i][j] = (!(cnt^3))||((a[i][j]&1)&&(!(cnt^4)));
    4. 使用乘法代替除法
    5. 位运算实现整数绝对值
      1. 位运算实现浮点数绝对值
    6. 位运算实现整数MaxMin
    7. 位运算求二进制内1的个数
    8. 位运算代替乘除2运算
    9. 重新划分去除乘除,小代价是归约一下sigma
  6. 混合精度(降低部分精度,降低计算量)
  7. 数据重用(不重复计算,降低计算量)
  8. 访存密集
  9. vtune memory access分析,提高cpu访存带宽,优化2CPU通信
    1. store与load比stream慢很多
      1. 原因store是将要写的数据load到缓存里,然后修改。而stream是直接写内存。
  10. 计算分块
    1. 根据L1的大小设置块大小
      MiB = Mebibyte = 1024 KB,
      KiB = Kibibyte = 1024 Bytes,
      MB = Megabyte = 1,000 KB,
      KB = Kilobyte = 1,000 Bytes
      
    2. double 8 bytes
  11. 改变数据结构优化访存(提高cache命中率)
    1. 不合理的数据结构定义,导致数据存储不连续。通过改变数据结构,通过内存指针访问连续地址
  12. 强制使用静态链接库glibc
  13. 访存局部性原理(提高cache命中率)
    1. c语言先行后列
    2. 循环拆分、循环重组
  14. 根据cache空间,以及cache策略,进行cache数据预取,
  15. 计算融合(减少访存次数)
    1. 计算结果及时使用,去除中间结果的存储访问时间
    2. 将多个循环整合为一个
  16. 对于对同一个地址的连续读写依赖,采取pingpong-buffer来两个分治
  17. 申请空间
  18. 负载均衡(并行划分)
  19. 对不同的数据量进行不同的策略,比如数据特别少,单cpu反而最快。
  20. 二维的图,无脑按照y划分就行。
    1. 合并的时候,按照并查集(1.维护顺序 2.有代表性)
  21. 针对数据规模,是否要并行。
  22. IO密集
  23. 并行读取
  24. 内存硬盘化
  25. 通讯密集
  26. IB网通信
  27. 改变通信结构
  28. 打包发送
  29. 希尔伯特划分(一维二维)
  30. 编译选项
  31. O3优化,ipo过程优化,fp-model fast=2加速浮点计算
  32. 其他未分类

还没来得及看的优化

Software optimization resources :https://www.agner.org/optimize/

AMD 罗马米兰平台优化

https://www.bilibili.com/video/BV19q4y197uX?spm_id_from=333.999.0.0 https://www.bilibili.com/video/BV1vU4y1u7nL?spm_id_from=333.999.0.0

常见的参数

2 sockets cpu latency : 50/60

core memory bandwidth :20GB/s

样例图片

  1. 不合理数据结构,和合理的数据结构
  2. 编译选项

性能 功耗 与容错

陈子忠 教授( 美国加州大学河滨分校 ) 230616报告

  1. 多核的出现,单核能耗与频率三次方成正比,难以压住散热
  2. 在已知调度时间复杂度估计的情况下,降低频率DVFS延长执行能大幅度节约功耗。同理提升频率也行。
  3. 纠错:检查点机制,中间验证算法复杂度比计算算法复杂度低。

需要进一步的研究学习

https://johnysswlab.com/

遇到的问题

太糊了

开题缘由、总结、反思、吐槽~~

因为参加2021 IPCC,观看B站视频,学到很多特地总结一下

参考文献

https://www.bilibili.com/video/BV1Dv411p7ay

Probability Theory

常用离散分布

二项分布

二项分布(Binomial Distribution)是概率论中常见的离散概率分布,用于描述在n重伯努利实验中成功事件发生的次数。

n重伯努利实验是指进行了n次独立重复的伯努利试验。伯努利试验是一种只有两个可能结果的随机试验,通常称为成功(S)和失败(F)。每次试验成功的概率为p,失败的概率为1-p。特点是每次试验只有两种可能的结果,通常表示为成功和失败。

在二项分布中,我们关注的是在n次独立重复试验中成功事件发生的次数(记为X),其中每次试验成功的概率为p。二项分布的概率质量函数可以表示为:

\[P(X = k) = C(n, k) * p^k * (1-p)^{n-k}\]

P(X = k)表示在n次试验中成功事件发生k次的概率。

泊松分布

泊松分布(Poisson Distribution)是一种离散概率分布,用于描述在一段固定时间或空间内随机事件发生的次数。它的特点是事件发生的次数是离散的且无限可数,且事件发生的概率在整个时间或空间内是恒定的。

在泊松分布中,我们关注的是在给定的时间或空间内,事件发生的次数(记为X)。泊松分布的概率质量函数可以表示为:

\[P(X = k) = (λ^k * e^{-λ}) / k!\]

其中,P(X = k)表示在给定时间或空间内事件发生k次的概率。λ是事件发生的平均次数,即单位时间或空间内事件发生的平均频率。e是自然对数的底数,k!表示k的阶乘。

泊松分布常用于描述稀有事件的发生情况,例如单位时间内电话呼叫次数、单位面积内放射性粒子的撞击次数等。通过泊松分布,我们可以计算在给定平均发生率下,事件发生特定次数的概率,从而进行概率推断和预测。

超几何分布

超几何分布(Hypergeometric Distribution)是一种离散概率分布,用于描述从有限总体中进行抽样时,抽取的样本中具有某种特征的个数的分布。它与二项分布相似,但有一些关键区别。

在超几何分布中,我们考虑从总体中抽取固定大小的样本,总体中有M个具有某种特征的元素和N-M个没有该特征的元素。我们关注的是在抽样过程中,样本中具有该特征的元素的个数(记为X)。

超几何分布的概率质量函数可以表示为:

\[P(X = k) = (C(M, k) * C(N-M, n-k)) / C(N, n)\]

其中,P(X = k)表示样本中具有该特征的元素个数为k的概率。C(M, k)表示在M个具有该特征的元素中选择k个元素的组合数,C(N-M, n-k)表示在N-M个没有该特征的元素中选择n-k个元素的组合数,C(N, n)表示在总体中选择n个元素的组合数。

超几何分布常用于从有限总体中进行抽样,并研究样本中某种特征的出现情况。它的特点是,随着抽样数量的增加,成功事件的概率不再是恒定的,因为每次抽样都会影响总体中元素的可选性。通过超几何分布,我们可以计算在给定总体和抽样大小的情况下,样本中具有该特征的元素个数的概率分布。

几何分布

几何分布描述的是在独立重复试验中,第一次成功事件A发生所需的试验次数。每次试验都有成功(S)和失败(F)两种可能结果,且成功概率为p。几何分布的概率质量函数可以表示为:

\[P(X = k) = (1 - p)^{k-1} * p\]

其中,P(X = k)表示第一次成功事件发生在第k次试验的概率。

负二项分布(帕斯卡分布)

负二项分布描述的是在独立重复试验中,成功事件发生r次所需的试验次数。每次试验都有成功(S)和失败(F)两种可能结果,且成功概率为p。负二项分布的概率质量函数可以表示为:

\[P(X = k) = C(k-1, r-1) * (1 - p)^{k-r} * p^r\]

其中,P(X = k)表示成功事件发生r次在第k次试验的概率。C(k-1, r-1)表示组合数,表示在前k-1次试验中取r-1次成功的组合数。

常用连续分布

常用密度函数表示

正态分布(高斯分布)

正态分布,也称为高斯分布(Gaussian Distribution),是统计学中最重要且广泛应用的连续概率分布之一。

正态分布的概率密度函数(Probability Density Function, PDF)可以用以下公式表示:

\[f(x) = (1 / (σ * \sqrt{2π})) * exp(-(x-μ)^2 / (2σ^2))\]

其中,f(x)表示随机变量X的概率密度函数。μ表示分布的均值(期望值),σ表示标准差,π表示圆周率,exp表示自然对数的指数函数。

正态分布具有以下特点:

  • 对称性:正态分布的概率密度函数是关于均值对称的,呈现出钟形曲线的形状。
  • 唯一性:正态分布由其均值和标准差唯一确定。
  • 中心极限定理:许多随机现象的总体分布趋向于正态分布,尤其在样本量足够大时。
  • 68-95-99.7规则:在正态分布中,约有68%的数据落在均值的一个标准差范围内,约有95%的数据落在两个标准差范围内,约有99.7%的数据落在三个标准差范围内。

均匀分布

均匀分布(Uniform Distribution)是一种简单而常见的概率分布,它在指定的区间内的取值具有相等的概率。在均匀分布中,每个可能的取值都具有相同的概率密度。

均匀分布的概率密度函数(Probability Density Function, PDF)可以用以下公式表示:

f(x) = 1 / (b - a),如果 a ≤ x ≤ b f(x) = 0,其他情况

其中,f(x)表示随机变量X的概率密度函数。a和b分别表示分布的下限和上限。

指数分布

指数分布(Exponential Distribution)是一种连续概率分布,常用于描述事件发生的时间间隔。它是一种特殊的连续随机变量的分布,具有单峰、右偏的特点。

指数分布的概率密度函数(Probability Density Function, PDF)可以用以下公式表示:

f(x) = λ * exp(-λx),如果 x ≥ 0 f(x) = 0,其他情况

其中,f(x)表示随机变量X的概率密度函数,λ是分布的参数,被称为率参数。

指数分布具有以下特点:

  • 单峰性:指数分布的概率密度函数是单峰的,峰值出现在0点,随着时间的增长逐渐减小。
  • 无记忆性:指数分布具有无记忆性的特性,即给定已经等待了一段时间,再等待更多的时间的概率与刚开始等待的概率是相同的。这是指数分布与其他分布不同的重要特点。

指数分布在实际应用中具有广泛的应用。例如,它常用于描述随机事件的到达时间、服务时间、寿命等。在可靠性工程和排队论中,指数分布经常用于模拟和分析各种事件的发生和持续时间。

伽马分布

伽马分布(Gamma Distribution)是一种连续概率分布,它常用于描述正数随机变量的分布,如事件的等待时间、寿命等。伽马分布是指数分布的推广形式,它可以具有更灵活的形状。

伽马分布的概率密度函数(Probability Density Function, PDF)可以用以下公式表示:

$$ f(x) = (1 / (Γ(k) * θ^k)) * x^{k-1} * exp(-x/θ)$$,如果 x ≥ 0 0,其他情况

其中,f(x)表示随机变量X的概率密度函数,k和θ是分布的参数,k被称为形状参数,θ被称为尺度参数,Γ(k)表示伽马函数(Gamma function)。

伽马分布具有以下特点:

  • 随机变量为正数:伽马分布的取值范围为正数,不包括0及负数。
  • 形状灵活:通过调节形状参数k,可以改变伽马分布的形状。当k为整数时,伽马分布退化为Erlang分布。
  • 可以用于建模持续时间:伽马分布常用于建模持续时间,如等待时间、寿命等,特别是当事件的发生率不是恒定的情况下。

伽马分布在实际应用中具有广泛的应用。例如,在可靠性工程中,它常用于描述零部件的寿命和故障时间。在金融领域,伽马分布被用于模拟和分析资产价格的变动。

贝塔分布

贝塔分布(Beta Distribution)是一种连续概率分布,它定义在区间[0, 1]上,并且常用于描述概率分布、比例、概率参数等随机变量的分布。

贝塔分布的概率密度函数(Probability Density Function, PDF)可以用以下公式表示:

\(\(f(x) = (x^{α-1} * (1-x)^{β-1}) / B(α, β)\)\),如果 0 ≤ x ≤ 1 0,其他情况

其中,f(x)表示随机变量X的概率密度函数,α和β是分布的两个形状参数,B(α, β)表示贝塔函数(Beta function)。

贝塔分布具有以下特点:

  • 取值范围:贝塔分布的取值范围为区间[0, 1],对应于概率或比例的取值范围。
  • 形状灵活:通过调节形状参数α和β的值,可以改变贝塔分布的形状,使其适应不同的数据分布。
  • 可以用于建模随机概率:贝塔分布常用于建模随机概率、比例等,例如二项分布中的成功概率、伯努利分布中的参数等。

贝塔分布在实际应用中具有广泛的应用。它常被用于贝叶斯统计推断、可靠性分析、A/B测试、市场份额预测等领域。此外,贝塔分布还与其他概率分布有着密切的关联,例如伯努利分布、二项分布和贝叶斯推断中的共轭先验分布等。

三大抽样分布

  • 卡方分布(Chi-Square Distribution):卡方分布是一种连续概率分布,用于描述随机变量的平方和的分布。
  • F分布是一种连续概率分布,用于描述两个独立正态分布方差比的分布。
  • t分布(t-Distribution):t分布是一种连续概率分布,用于描述小样本情况下样本均值的分布。与正态分布相比,t分布的尖峰更高、尾部更厚,适用于样本容量较小或总体方差未知的情况。

随机过程

泊松过程

泊松过程(Poisson Process)是一种随机过程,用于描述在固定时间间隔内随机事件发生的模式。泊松过程的关键特征是事件在时间上的独立性和固定的平均发生率。它可以用于建模各种事件的发生,例如电话呼叫到达、事故发生、信号传输等。

马尔科夫

马尔可夫性质

当一个随机过程其未来状态的条件概率分布仅依赖于当前状态;换句话说,在给定现在状态时,它与过去状态(即该过程的历史路径)是条件独立的,那么此随机过程即具有马尔可夫性质。

马尔可夫链、过程

马尔可夫链(Markov Chain, MC)是概率论和数理统计中具有马尔可夫性质(Markov property)且存在于离散的指数集(index set)和状态空间(state space)内的随机过程(stochastic process)

适用于连续指数集的马尔可夫链被称为马尔可夫过程(Markov process)

马尔可夫决策过程

马尔可夫决策过程(Markov Decision Process, MDP)是序贯决策(sequential decision)的数学模型,用于在系统状态具有马尔可夫性质的环境中模拟智能体可实现的随机性策略与回报

平稳过程

平稳过程(Stationary Process)是一种随机过程,其统计特性在时间上保持不变。具体而言,一个平稳过程在不同时间段内具有相同的概率分布和统计特性,如均值、方差和自协方差。

布朗运动

布朗运动(Brownian Motion),也被称为维纳过程(Wiener Process),是一种随机过程,以英国生物学家罗伯特·布朗(Robert Brown)的名字命名。布朗运动是一种连续时间、连续空间的随机运动,它在各个时间点上的位置是随机的。

布朗运动的特点包括:

  • 随机性:布朗运动的运动路径是随机的,不可预测的。在每个时间点上,粒子的位置随机地变化。
  • 连续性:布朗运动在连续的时间和空间上进行。粒子在任意瞬时的位置是连续变化的。
  • 马尔可夫性:布朗运动满足马尔可夫性质,即未来的运动只与当前的位置有关,而与过去的运动路径无关。
  • 独立增量:布朗运动的位置变化是具有独立增量的,即在不同时间段上的位置变化是相互独立的。

布朗运动在物理学、金融学、生物学等领域具有广泛的应用。它可以用来描述微粒在流体中的扩散、金融市场中的价格变动、细胞内分子的运动等随机现象。布朗运动的数学描述采用随机微分方程,其中包括随机增量项,用来表示随机性和不确定性。

鞅过程

鞅过程(Martingale Process)是一种随机过程,它在概率论和数学金融领域中具有重要的应用。鞅过程是一种随机变量序列,它满足一定的条件,其中最重要的性质是条件期望的无偏性

具体而言,设{X(t), t ≥ 0}是一个随机过程,定义在一个概率空间上,关于时间t的随机变量。如果对于任意的s ≤ t,条件期望E[X(t) | X(s)]等于X(s),即 E[X(t) | X(s)] = X(s),那么这个随机过程被称为鞅过程。

换句话说,鞅过程在任意时刻的当前值的条件期望等于过去时刻的值,表明鞅过程在平均意义上不随时间变化而漂移。

一个典型的实际案例是赌博游戏中的赌徒之行。

假设有一个赌徒在每轮游戏中抛掷硬币,正面朝上赢得1单位的奖励,反面朝上输掉1单位的赌注。我们可以用一个鞅过程来描述赌徒的资金变化。假设赌徒的初始资金为0单位,并且在每轮游戏中抛硬币的结果是一个独立的随机事件。赌徒的资金变化可以表示为一个鞅过程{X(t), t ≥ 0},其中X(t)表示赌徒在时间t时的资金。

在这个例子中,条件期望的无偏性意味着在任意时刻t,赌徒的当前资金的条件期望等于过去时刻的资金,即 E[X(t) | X(s)] = X(s),其中s ≤ t。 这意味着赌徒在每轮游戏中没有系统性地赢或输。无论他之前的赢利或亏损情况如何,当前的资金预期值等于他之前的资金。

鞅过程在金融市场建模、随机控制理论、概率论等领域有广泛的应用。它在金融中可以用来描述资产价格的动态演化、期权定价、风险度量等。在概率论中,鞅过程是一类重要的随机过程,其具有丰富的性质和数学结构,被广泛研究和应用。

大数定理,中心极限定理

大数定理

大数定理(Law of Large Numbers)是概率论中的一条重要定理,描述了随机变量序列的均值的收敛性质。它指出,当随机变量的样本容量足够大时,样本均值将接近于随机变量的期望值。

中心极限定理

中心极限定理(Central Limit Theorem)是概率论和统计学中的重要结果之一。它描述了在一定条件下,当独立随机变量的数量足够大时,它们的平均值的分布将近似于正态分布。

中心极限定理的主要内容如下:

假设有n个独立随机变量X1, X2, ..., Xn,它们具有相同的分布和参数。这些随机变量的和S_n = X1 + X2 + ... + Xn的分布在n趋近于无穷大时,以及适当的标准化后,将近似于正态分布。

具体而言,当n足够大时,S_n的近似分布可以用正态分布来描述。

参数估计(概率分布模型)

在参数估计中,确实需要事先假设或确定一个概率分布模型(注意不是确定的模型,不然可以根据结果直接算出参数)。参数估计的前提是我们假设观测数据来自于某个特定的概率分布,而我们的目标是估计这个概率分布中的未知参数。

具体来说,参数估计的过程通常包括以下步骤:

  • 假设概率分布模型:我们需要根据问题的特点和领域知识,假设观测数据符合某个特定的概率分布模型,例如正态分布、泊松分布、伽马分布等。这个假设是基于对问题的理解和经验的。
  • 确定参数:在所假设的概率分布模型中,可能存在一个或多个未知参数,我们需要明确这些参数,并确定我们想要估计的参数。
  • 收集观测数据:根据实际情况,我们收集一组观测数据,作为对概率分布中参数的估计依据。
  • 构建估计方法:根据所选的概率分布模型和参数,我们构建相应的估计方法,例如最大似然估计、矩估计等。
  • 估计参数:利用观测数据和估计方法,计算出对未知参数的估计值。

需要注意的是,参数估计的准确性和可靠性依赖于所假设的概率分布模型的正确性和数据的充分性。如果所假设的概率分布模型与实际情况不符,或者观测数据过少或存在较大的噪声,估计结果可能会出现偏差或不准确的情况。

因此,在参数估计之前,我们需要对问题进行合理的假设和模型选择,并在数据收集和估计方法的过程中考虑到模型假设的合理性和数据的质量。

贝叶斯定理

贝叶斯定理是概率论中的一个基本定理,描述了在观测到新的证据(观测数据)后,如何更新对某个事件的概率估计。

假设有两个事件 A 和 B,其中事件 A 是我们要推断或估计的事件,而事件 B 是观测到的证据。贝叶斯定理表述如下:

P(A|B) = (P(B|A) * P(A)) / P(B)

其中:

  • P(A|B) 是在观测到事件 B 后事件 A 发生的条件概率,也称为后验概率。
  • P(B|A) 是在事件 A 发生的条件下观测到事件 B 的概率,也称为似然函数。
  • P(A) 是事件 A 的先验概率,即在观测到事件 B 之前对事件 A 发生的估计。
  • P(B) 是事件 B 的边际概率,即观测到事件 B 的概率。

贝叶斯定理的核心思想是通过观测到的证据(事件 B),更新对事件 A 的概率估计。它将先验概率和似然函数结合起来,得到后验概率。具体而言,贝叶斯定理可以用于根据已知信息更新模型参数、进行推断、进行分类等。

贝叶斯定理在贝叶斯统计学中具有重要的应用,它允许我们利用已有知识(先验)和新的证据(似然函数)来更新对未知事件的估计(后验)。通过不断地更新先验概率,我们可以根据新的观测数据获得更准确和可靠的后验概率估计。

先验分布 后验概率分布

在贝叶斯统计中,先验分布和后验概率分布是两个关键概念,用于描述我们对参数的初始信念和通过观测数据更新后的信念。

  • 先验分布(Prior Distribution):先验分布是在观测数据之前对参数的分布做出的假设或先验信念。它反映了我们在观测数据之前对参数可能取值的主观或客观的认识。先验分布通常用一个概率分布函数来表示,例如贝塔分布、高斯分布等。先验分布可以看作是参数的初始猜测,它对参数的可能取值进行了一定的限制或权重。
  • 后验概率分布(Posterior Probability Distribution):后验概率分布是在观测到数据后,通过贝叶斯定理将先验分布与似然函数结合起来得到的参数分布。它表示了在考虑观测数据之后,对参数取值的更新后的概率分布。后验概率分布结合了先验信息和观测数据的信息,提供了对参数的更准确估计,并反映了参数的不确定性程度。

先验分布和后验概率分布之间的关系可以用贝叶斯定理来表示:

后验概率分布 ∝ 先验分布 × 似然函数

其中,似然函数描述了观测数据出现的可能性。通过将先验分布与观测数据的似然函数相乘,并进行适当的归一化,可以得到后验概率分布。

贝叶斯统计的核心思想是通过不断地更新先验分布,利用观测数据提供的信息,得到后验概率分布,并在此基础上做出推断和决策。先验分布提供了先验知识和信念,而后验概率分布则是在考虑观测数据后对参数的更新和修正

点估计与无偏性

点估计(Point Estimation)是参数估计的一种方法,它通过使用样本数据来估计总体参数的具体值。点估计的目标是找到一个单一的估计值,作为对未知参数的最佳猜测。

无偏性是点估计的性质之一。一个无偏估计是指在重复抽样的情况下,估计值的期望等于被估计参数的真实值。换句话说,如果一个估计值的期望与真实参数值相等,则该估计值是无偏的。

矩估计

  • 使用使用样本矩来逼近/替代总体矩,从而得到参数的估计值。
  • 样本矩(Sample Moments):样本矩是根据从总体中抽取的样本数据计算得出的统计量。常见的样本矩包括样本均值、样本方差、样本偏度、样本峰度等。

最大似然估计与EM算法

  • 最大似然估计(maximum likelihood estimation,MLE),或者最大对数似然:
  • 简单来说:估计的是已知概率分布模型的参数值,输入是测试的结果/样本。简单来说,模型已定,参数未知下,用已知的样本结果信息,反推最具有可能(最大概率)导致这些样本结果出现的模型参数值!

最大似然估计的基本思想是,在给定观测数据的情况下,寻找使得观测数据的联合概率密度函数(或概率质量函数)最大化的参数值。具体步骤包括以下几个步骤:

  • 建立概率模型:首先需要确定一个适当的概率模型,假设观测数据满足某个概率分布,如正态分布、泊松分布等。
  • 构建似然函数:根据概率模型,将观测数据的联合概率密度函数(或概率质量函数)表示为参数的函数,即似然函数。似然函数描述了在给定参数值的情况下,观测数据出现的可能性。
  • 寻找最大似然估计:通过优化方法(如求导、迭代算法等),找到使得似然函数最大化的参数值。最大似然估计的目标是寻找最可能产生观测数据的参数值,使得观测数据的出现概率最大化。

最大似然估计具有一些良好的性质,例如在大样本下,最大似然估计的估计值具有渐近正态分布,且具有一致性和渐进有效性等特性。最大似然估计在统计学和机器学习等领域中广泛应用,用于估计参数、构建模型和进行推断。

  • EM算法(Expectation-Maximization Algorithm)是一种迭代优化算法,用于在存在隐变量或缺失数据的统计模型中进行参数估计。它通过交替进行两个步骤:E步(Expectation Step)和M步(Maximization Step),以最大化似然函数或完成参数的最大似然估计。

EM算法的基本思想是通过引入隐变量,将含有缺失数据的问题转化为完全数据的问题。具体步骤如下:

  • 初始化参数:首先需要对模型的参数进行初始化。
  • E步(Expectation Step):在E步中,根据当前参数的估计值,计算隐变量的后验概率(或期望),即给定观测数据下隐变量的分布。这一步利用当前参数的估计值进行"填补"缺失数据或估计隐变量的取值。
  • M步(Maximization Step):在M步中,根据E步得到的隐变量后验概率,重新估计模型的参数。这一步通过最大化完全数据的对数似然函数来更新参数的估计值。
  • 迭代更新:重复进行E步和M步,直到参数的估计值收敛或满足停止准则。

EM算法通过迭代的方式逐步优化参数的估计值,使得在每次迭代中似然函数都得到增大,从而逐渐逼近最优参数值。由于每次迭代中的E步和M步都可以分别求解,因此EM算法在理论上保证了在每一步都能得到似然函数的增加。然而,EM算法并不能保证收敛到全局最优解,可能陷入局部最优解。

EM算法在许多统计学和机器学习问题中都有广泛的应用,特别是在存在隐变量的概率模型、混合模型、高斯混合模型等领域中。它为解决这些问题提供了一种有效的参数估计方法。

最小方差无偏估计

  • 对于小样本, 无偏估计使用最小方差,对于有偏估计常使用均方误差
  • 有偏估计是指在统计学中,估计量的期望值不等于被估计参数的真实值。换句话说,有偏估计会在估计过程中引入一定的系统性偏差。
  • 我的理解, 你设计的模型,就不是真实的(也无法保证),自然就从根本上不完全准确,有系统性偏差,所以常用均方误差。

贝叶斯估计

频率学派和贝叶斯学派是统计学中两种不同的观点或方法论。

频率学派(Frequentist Approach)注重使用频率或概率的概念进行推断和估计。在频率学派中,参数被视为固定但未知的,通过基于样本数据的统计量来推断参数的值。频率学派强调利用大量的重复抽样来研究统计性质,并通过估计量的偏差、方差和置信区间等指标来评估估计的准确性和可靠性。

贝叶斯学派(Bayesian Approach)则采用贝叶斯定理和概率论的观点来进行推断和估计。在贝叶斯学派中,参数被视为随机变量,其先验分布和样本数据的条件下的后验分布共同决定了参数的估计。贝叶斯学派注重将先验知识或信念结合到推断过程中,并使用后验分布来提供关于参数的概率分布以及置信区间等信息。

贝叶斯估计是贝叶斯学派中一种参数估计的方法。它利用贝叶斯定理计算参数的后验分布,并将后验分布作为参数的估计。贝叶斯估计不仅考虑了样本数据的信息,还结合了先验知识或信念,因此可以提供更全面和灵活的估计结果。贝叶斯估计还可以通过调整先验分布的参数或选择不同的先验分布来灵活地处理不同的问题和背景。

需要注意的是,频率学派和贝叶斯学派并不是相互排斥的,它们是统计学中不同的方法论和观点,各自有其适用的领域和优势。在实际应用中,可以根据问题的特点、数据的性质以及研究目的来选择适合的学派和方法。

区间估计

区间估计是统计学中一种参数估计的方法,用于估计未知参数的范围或区间。与点估计不同,区间估计提供了一个范围,该范围内有一定的置信度(置信水平)包含了真实参数值。

区间估计的基本思想是通过样本数据来构建一个区间,该区间涵盖了真实参数值的可能范围。在频率学派中,常用的区间估计方法包括置信区间。置信区间是基于样本数据计算出来的一个区间,其具体形式为"估计值 ± 误差",其中误差由抽样误差和估计误差组成。

置信区间的置信水平表示该区间在重复抽样中包含真实参数值的概率。例如,95%的置信水平意味着在多次重复抽样中,有95%的置信区间会包含真实参数值。

区间估计的优势在于提供了对未知参数范围的估计,并提供了对估计结果的不确定性的量化。它能够更全面地反映估计的可靠性,并且可以与其他区间进行比较,进行统计推断和假设检验等。

需要注意的是,区间估计并不提供关于真实参数值的具体点估计,而是提供了一个范围。不同的置信水平会得到不同宽度的区间,较高的置信水平通常会导致较宽的区间。在应用中,选择适当的置信水平需要权衡估计的准确性和置信区间的宽度。

方差回归与回归分析

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

Pytorch

(本人是rookie,纯小白~

什么是 PyTorch?

PyTorch 是一个基于 Python 的科学计算包,主要定位两类人群:

  1. NumPy 的替代品,可以利用 GPU 的性能进行计算。
  2. 深度学习研究平台拥有足够的灵活性和速度

Pytorch简介

要介绍PyTorch之前,不得不说一下Torch。

Torch是一个有大量机器学习算法支持的科学计算框架,是一个与Numpy类似的张量(Tensor) 操作库,其特点是特别灵活,但因其采用了小众的编程语言是Lua,所以流行度不高,这也就有了PyTorch的出现。所以其实Torch是 PyTorch的前身,它们的底层语言相同,只是使用了不同的上层包装语言。

PyTorch是一个基于Torch的Python开源机器学习库,用于自然语言处理等应用程序。它主要由Facebookd的人工智能小组开发,不仅能够 实现强大的GPU加速,同时还支持动态神经网络,这一点是现在很多主流框架如TensorFlow都不支持的。 PyTorch提供了两个高级功能:

  • 具有强大的GPU加速的张量计算(如Numpy)
  • 包含自动求导系统的深度神经网络

TensorFlow和Caffe都是命令式的编程语言,而且是静态的,首先必须构建一个神经网络,然后一次又一次使用相同的结构,如果想要改变网络的结构,就必须从头开始。

但是对于PyTorch,通过反向求导技术,可以让你零延迟地任意改变神经网络的行为,而且其实现速度 快。正是这一灵活性是PyTorch对比TensorFlow的最大优势。

所以,总结一下PyTorch的优点:

  • 支持GPU
  • 灵活,支持动态神经网络
  • 底层代码易于理解
  • 命令式体验
  • 自定义扩展

当然,现今任何一个深度学习框架都有其缺点,PyTorch也不例外,对比TensorFlow,其全面性处于劣势,目前PyTorch

  • 还不支持快速傅里 叶、沿维翻转张量和检查无穷与非数值张量;
  • 针对移动端、嵌入式部署以及高性能服务器端的部署其性能表现有待提升;
  • 其次因为这个框 架较新,使得他的社区没有那么强大,在文档方面其C库大多数没有文档。

安装和使用

安装

https://pytorch.org/ 选择对应cuda版本下载即可

使用

from __future__ import print_function
import torch

数据类型和操作

Tensor(张量)

# 构造一个5x3矩阵,不初始化。基本是0,或者+-10^-4之类
x = torch.empty(5, 3)
# 构造一个随机初始化的矩阵:范围[0,1)
x = torch.rand(5, 3)
# 构造一个随机int初始化的矩阵:范围[3,10),大小2*2
torch.randint(3, 10, (2, 2))
tensor([[4, 5],
        [6, 7]])
# 构造一个矩阵全为 0,而且数据类型是 long.
x = torch.zeros(5, 3, dtype=torch.long)
# 直接使用数据 1*2维 
x = torch.tensor([5.5, 3])
# 裁取已有tensor 5*3的元素
x = x.new_ones(5, 3, dtype=torch.double)   
# 已有tensor元素全部随机化
x = torch.randn_like(x, dtype=torch.float) 
# 连接矩阵,不同维度 Concatenates 
>>> x = torch.randn(2, 3)
>>> x
tensor([[ 0.6580, -1.0969, -0.4614],
        [-0.1034, -0.5790,  0.1497]])
>>> torch.cat((x, x, x), 0)
# torch.cat([input]*100)
tensor([[ 0.6580, -1.0969, -0.4614],
        [-0.1034, -0.5790,  0.1497],
        [ 0.6580, -1.0969, -0.4614],
        [-0.1034, -0.5790,  0.1497],
        [ 0.6580, -1.0969, -0.4614],
        [-0.1034, -0.5790,  0.1497]])
# 相同大小对应位置相乘
x = torch.tensor([[5, 6], [1 / 5, 2]])
print(x)
print(torch.prod(x, 0))  # product along 0th axis
tensor([[5.0000, 6.0000],
        [0.2000, 2.0000]])
tensor([ 1., 12.])
# 转置 指定维度transpose() 和 permute()
x.t()   
# 横向纵向复制拓展
>>> x = torch.tensor([[1], [2], [3]])
>>> x.size()
torch.Size([3, 1])
>>> x.expand(3, 4)
tensor([[ 1,  1,  1,  1],
        [ 2,  2,  2,  2],
        [ 3,  3,  3,  3]])
>>> x.expand(-1, 4)   # -1 means not changing the size of that dimension
tensor([[ 1,  1,  1,  1],
        [ 2,  2,  2,  2],
        [ 3,  3,  3,  3]])
# 输出第二列的数据
print(x[:, 1])
# 维度信息 输出是一个元组,所以它支持左右的元组操作。
print(x.size())
# 改变一个 tensor 的大小或者形状
# reshape也行 https://blog.csdn.net/Flag_ing/article/details/109129752
x = torch.randn(4, 4)
y = x.view(16)
z = x.view(-1, 8)  # -1位置的取值是从其他维度推断出来的
print(x.size(), y.size(), z.size()) # torch.Size([4, 4]) torch.Size([16]) torch.Size([2, 8])
# 加法
z=x+y
z=torch.add(x, y)
y.add_(x)  # adds x to y

注意 任何使张量会发生变化的操作都有一个前缀 '_'。例如: x.copy_(y), x.t_(), 将会改变 x

PyTorch 自动微分

autograd 包是 PyTorch 中所有神经网络的核心。

autograd 软件包为 Tensors 上的所有操作提供自动微分。它是一个由运行定义的框架,这意味着以代码运行方式定义你的后向传播,并且每次迭代都可以不同。

TENSOR

torch.Tensor 是包的核心类。

如果将其属性 .requires_grad 设置为 True,则会开始跟踪针对 tensor 的所有操作。.requires_grad_( ... ) 会改变张量的 requires_grad 标记。输入的标记默认为 False ,如果没有提供相应的参数。

完成计算后,您可以调用 .backward() 来自动计算所有梯度。

该张量的梯度将累积到 .grad 属性中。要停止 tensor 历史记录的跟踪,您可以调用 .detach(),它将其与计算历史记录分离,并防止将来的计算被跟踪。要停止跟踪历史记录(和使用内存),您还可以将代码块使用 with torch.no_grad(): 包装起来。

在评估模型时,这是特别有用,因为模型在训练阶段具有 requires_grad = True 的可训练参数有利于调参,但在评估阶段我们不需要梯度。(???)

另一个重要的类是Function。Tensor 和 Function 互相连接并构建一个非循环图,它保存整个完整的计算过程的历史信息。

每个张量都有一个 .grad_fn 属性保存着创建了张量的 Function 的引用,(如果用户自己创建张量,则g rad_fn 是 None )。

计算导数

你可以调用 Tensor.backward()。如果 Tensor 是标量(即它包含一个元素数据),则不需要指定任何参数backward(),但是如果它有更多元素,则需要指定一个gradient 参数来指定张量的形状。

例子1

import torch
# 创建一个张量,设置 requires_grad=True 来跟踪与它相关的计算
x = torch.ones(2, 2, requires_grad=True)
# 操作张量
y = x + 2
z = y * y * 3
out = z.mean()
# 后向传播,因为输出包含了一个标量,out.backward() 等同于out.backward(torch.tensor(1.))。
out.backward()
# 打印梯度 d(out)/dx
print(x.grad)

# tensor([[4.5000, 4.5000],
#        [4.5000, 4.5000]])

原理: 最终Loss的值,网络结构(部分偏导数),当前训练的值。三者共同决定了梯度。这意味着在Batch使用时,假如将网络复制多遍(包括初始训练参数也一样),对于总的Loss来训练得到的参数是完全相同的。

例子2

y 不再是一个标量。torch.autograd 不能够直接计算整个雅可比,但是如果我们只想要雅可比向量积,只需要简单的传递向量给 backward 作为参数。(??? 雅可比向量积有什么用)

v = torch.tensor([0.1, 1.0, 0.0001], dtype=torch.float)
y.backward(v)

print(x.grad)
# tensor([1.0240e+02, 1.0240e+03, 1.0240e-01])

神经网络的训练

定义网络

一个简单的前馈神经网络,它接收输入,让输入一个接着一个的通过一些层,最后给出输出。 通过 torch.nn 包来构建。一个 nn.Module 包括层和一个方法 forward(input) 它会返回输出(output)。

import torch
import torch.nn as nn
import torch.nn.functional as F


class Net(nn.Module):

    def __init__(self):
        # 习惯上,将包含可训练参数的结构,声明在__init__里
        super(Net, self).__init__()
        # 1 input image channel, 6 output channels, 5x5 square convolution
        # kernel
        self.conv1 = nn.Conv2d(1, 6, 5)
        self.conv2 = nn.Conv2d(6, 16, 5)
        # an affine operation: y = Wx + b
        self.fc1 = nn.Linear(16 * 5 * 5, 120)
        self.fc2 = nn.Linear(120, 84)
        self.fc3 = nn.Linear(84, 10)

    def forward(self, x):
        # Max pooling over a (2, 2) window
        x = F.max_pool2d(F.relu(self.conv1(x)), (2, 2))
        # If the size is a square you can only specify a single number
        x = F.max_pool2d(F.relu(self.conv2(x)), 2)
        x = x.view(-1, self.num_flat_features(x))
        x = F.relu(self.fc1(x))
        x = F.relu(self.fc2(x))
        x = self.fc3(x)
        return x

    def num_flat_features(self, x):
        size = x.size()[1:]  # all dimensions except the batch dimension
        num_features = 1
        for s in size:
            num_features *= s
        return num_features


net = Net()
print(net)

一个模型可训练的参数可以通过调用 net.parameters() 返回:

params = list(net.parameters())
print(len(params))
print(params[0].size())  # conv1's .weight

运行一次网络

input = torch.randn(1, 1, 32, 32)
out = net(input)
print(out)

反向传播计算各个位置梯度

把所有参数梯度缓存器置零,用随机的梯度来反向传播

net.zero_grad()
out.backward(torch.randn(1, 10))

损失函数

一个损失函数需要一对输入:模型输出和目标,然后计算一个值来评估输出距离目标有多远。

有一些不同的损失函数在 nn 包中。一个简单的损失函数就是 nn.MSELoss ,这计算了均方误差。

可以调用包,也可以自己设计。

output = net(input)
target = torch.randn(10)  # 随便一个目标
target = target.view(1, -1)  # make it the same shape as output
criterion = nn.MSELoss()

loss = criterion(output, target)

使用loss反向传播更新梯度

查看梯度记录的地方

input -> conv2d -> relu -> maxpool2d -> conv2d -> relu -> maxpool2d
      -> view -> linear -> relu -> linear -> relu -> linear
      -> MSELoss
      -> loss

当我们调用 loss.backward(),整个图都会微分,而且所有的在图中的requires_grad=True 的张量将会让他们的 grad 张量累计梯度。

为了实现反向传播损失,我们所有需要做的事情仅仅是使用 loss.backward()。你需要清空现存的梯度,要不然将会和现存(上一轮)的梯度累计到一起。

net.zero_grad()     # zeroes the gradient buffers of all parameters
loss.backward()

查看某处梯度

print(net.conv1.bias.grad)

使用梯度和各种方法优化器更新参数

最简单的更新规则就是随机梯度下降。

weight = weight - learning_rate * gradient

我们可以使用 python 来实现这个规则:

learning_rate = 0.01
for f in net.parameters():
    f.data.sub_(f.grad.data * learning_rate)

尽管如此,如果你是用神经网络,你想使用不同的更新规则,类似于 SGD, Nesterov-SGD, Adam, RMSProp, 等。为了让这可行,我们建立了一个小包:torch.optim 实现了所有的方法。使用它非常的简单。

import torch.optim as optim

# create your optimizer
optimizer = optim.SGD(net.parameters(), lr=0.01)

# in your training loop:
optimizer.zero_grad()   # zero the gradient buffers
output = net(input)
loss = criterion(output, target)
loss.backward()
optimizer.step()    # Does the update

上面是一次训练

一般是按照一次多少batch训练,训练10次等.

或者考虑loss 稳定后结束,一般不使用loss小于某个值(因为不知道loss阈值是多少)

或许可以考虑K折交叉检验法(k-fold cross validation)

for epoch in range(2):  # loop over the dataset multiple times
    running_loss = 0.0
    for i, data in enumerate(trainloader, 0):
        # get the inputs
        inputs, labels = data

        # zero the parameter gradients
        optimizer.zero_grad()

        # forward + backward + optimize
        outputs = net(inputs)
        loss = criterion(outputs, labels)
        loss.backward()
        optimizer.step()

        # print statistics
        running_loss += loss.item()
        if i % 2000 == 1999:    # print every 2000 mini-batches
            print('[%d, %5d] loss: %.3f' %
                  (epoch + 1, i + 1, running_loss / 2000))
            running_loss = 0.0
print('Finished Training')

测试单个任务

分类任务,取最高的

outputs = net(images)
_, predicted = torch.max(outputs, 1)

测试总误差

correct = 0
total = 0
with torch.no_grad():
    for data in testloader:
        images, labels = data
        outputs = net(images)
        _, predicted = torch.max(outputs.data, 1)
        total += labels.size(0)
        correct += (predicted == labels).sum().item()

print('Accuracy of the network on the 10000 test images: %d %%' % (
    100 * correct / total))

各种初学者问题

In-place 正确性检查

所有的Variable都会记录用在他们身上的 in-place operations。如果pytorch检测到variable在一个Function中已经被保存用来backward,但是之后它又被in-place operations修改。当这种情况发生时,在backward的时候,pytorch就会报错。这种机制保证了,如果你用了in-place operations,但是在backward过程中没有报错,那么梯度的计算就是正确的。

对于不需要自动微分

=不需要计算梯度=手动计算值的

使用 someTensor.detach() 来更新

相关知识

欠拟合和过拟合判断

  1. 训练集和测试集都不好——欠拟合
  2. 训练集好,测试集不好——过拟合

多通道

一般是任务特征很多维度时,拓展描述参数用的。

比如:图像一般包含三个通道/三种原色(红色、绿色和蓝色)。 实际上,图像不是二维张量,而是一个由高度、宽度和颜色组成的三维张量。所以第三维通过通道表示。

https://zh.d2l.ai/chapter_convolutional-neural-networks/channels.html

多通道举例说明

self.conv1 = nn.Conv2d(1, 6, 5) # 输入通道1,输出通道6,卷积核 5*5
\[ 28=32-5+1 \]

初始1通道变6通道,意味着对初始的A数据,有6个初始值不同的5*5卷积核操作,产生6张图。需要参数6*5*5.

初始6通道变16通道,相当于将6通道变1通道,重复16次。6通道变1通道,通过6张图与由6个5*5卷积核组成的卷积核组作用,生成6张图,然后简单相加,变成1张。需要总参数16*6*5*5*5。相当于下图某些数据变成6和16:

BatchSize

https://blog.csdn.net/qq_34886403/article/details/82558399

  1. Batch Size定义:一次训练所选取的样本数。
  2. 由于矩阵操作,增加batch/行号。每行经过同一个网络,引起的就是输出行号增加。只需要对每行单独计算出来的误差进行sum或者mean得到一个误差值,就可以反向传播,训练参数。
  3. 简单来说就是平均了一个batch数据的影响,不会出现离谱的波动,方向比较准确。
  4. Batch Size的大小影响模型的优化程度和速度。同时其直接影响到GPU内存的使用情况,假如你GPU内存不大,该数值最好设置小一点。
  5. 没有Batch Size,梯度准确,只适用于小样本数据库
  6. Batch Size增大,梯度变准确。但是单个epoch的迭代次数减少了,参数的调整也慢了,假如要达到相同的识别精度,需要更多的epoch。
  7. Batch Size再增大,梯度已经非常准确,再增加Batch Size也没有用
  8. 虽然Batch Size增大,一遍的总次数变少,单步计算量增加。但是由于GPU并行操作,单步时间不会增加太多。

BatchNorm

Batch Normalization是将各层的输入进行归一化,使训练过程更快、更稳定的一种技术。在实践中,它是一个额外的层,我们通常添加在计算(卷积)层之后,在非线性(激活函数)之前。也有更先进的,比如layernorm。

BN层只是效果会变好,因为感受到了细节。不是有batch一定有BN层的意思。

各种不同的Loss

交叉熵和加权交叉熵

多用于多分类任务,预测值是每一类各自的概率。label为特定的类别 torch.nn.NLLLOSS通常不被独立当作损失函数,而需要和softmax、log等运算组合当作损失函数。

torch.nn.CrossEntropyLoss相当于softmax + log + nllloss。

预测的概率大于1明显不符合预期,可以使用softmax归一,取log后是交叉熵,取负号是为了符合loss越小,预测概率越大。

# 4类权重是 1, 10, 100, 100 一般是与样本占比成反比
criterion = nn.CrossEntropyLoss(weight=torch.from_numpy(np.array([1,10,100,100])).float() ,reduction='sum')
* size_average(该参数不建议使用,后续版本可能被废弃),该参数指定loss是否在一个Batch内平均,即是否除以N。默认为True * reduce (该参数不建议使用,后续版本可能会废弃),首先说明该参数与size_average冲突,当该参数指定为False时size_average不生效,该参数默认为True。reduce为False时,对batch内的每个样本单独计算loss,loss的返回值Shape为[N],每一个数对应一个样本的loss。reduce为True时,根据size_average决定对N个样本的loss进行求和还是平均,此时返回的loss是一个数。 * reduction 该参数在新版本中是为了取代size_average和reduce参数的。 * 它共有三种选项'mean','sum'和'none'。 * 'mean'为默认情况,表明对N个样本的loss进行求平均之后返回(相当于reduce=True,size_average=True); * 'sum'指对n个样本的loss求和(相当于reduce=True,size_average=False); * 'none'表示直接返回n分样本的loss(相当于reduce=False)

Focal Loss

相对于加权交叉熵不仅权重不需要计算,自动通过概率算,而且gamma=2按照平方缩小了,大样本的影响。

“蓝”线代表交叉熵损失。X轴即“预测为真实标签的概率”(为简单起见,将其称为pt)。举例来说,假设模型预测某物是自行车的概率为0.6,而它确实是自行车, 在这种情况下的pt为0.6。

Y轴是给定pt后Focal loss和CE的loss的值。

从图像中可以看出,当模型预测为真实标签的概率为0.6左右时,交叉熵损失仍在0.5左右。因此,为了在训练过程中减少损失,我们的模型将必须以更高的概率来预测到真实标签。换句话说,交叉熵损失要求模型对自己的预测非常有信心。但这也同样会给模型表现带来负面影响。

深度学习模型会变得过度自信, 因此模型的泛化能力会下降.

当使用γ> 1的Focal Loss可以减少“分类得好的样本”或者说“模型预测正确概率大”的样本的训练损失,而对于“难以分类的示例”,比如预测概率小于0.5的,则不会减小太多损失。因此,在数据类别不平衡的情况下,会让模型的注意力放在稀少的类别上,因为这些类别的样本见过的少,比较难分。

https://cloud.tencent.com/developer/article/1669261

https://blog.csdn.net/qq_34914551/article/details/105393989

https://ptorch.com/news/253.html

Pytorch.nn常用函数

torch.nn.Linear

\[ y=x*A^T+b \]

设置网络中的全连接层的,需要注意在二维图像处理的任务中,全连接层的输入与输出一般都设置为二维张量,形状通常为[batch_size, size],不同于卷积层要求输入输出是四维张量。

in_features指的是输入的二维张量的大小,即输入的[batch_size, size]中的size。

out_features指的是输出的二维张量的大小,即输出的二维张量的形状为[batch_size,output_size],当然,它也代表了该全连接层的神经元个数。

torch.nn.ReLU()

\[ ReLU(x)=(x)^+=max(0,x) \]

torch.nn.Sigmoid

\[ Sigmoid(x)=σ(x)= \frac{1}{1+exp(−x)} \]
  1. torch.nn.Sigmoid()
  2. 是一个类。在定义模型的初始化方法中使用,需要在_init__中定义,然后再使用。
  3. torch.nn.functional.sigmoid():
  4. 可以直接在forward()里使用。eg.A=F.sigmoid(x)

torch.cat

cat是concatnate的意思:拼接,联系在一起。

C = torch.cat( (A,B),0 )  #按维数0拼接(竖着拼)
C = torch.cat( (A,B),1 )  #按维数1拼接(横着拼)

torch.nn.BatchNorm2d

num_features – C from an expected input of size (N, C, H, W)

torch.nn.BatchNorm1d

Input: (N, C) or (N, C, L), where NN is the batch size, C is the number of features or channels, and L is the sequence length

Output: (N, C) or (N, C, L) (same shape as input)

Softmax函数和Sigmoid函数的区别

https://zhuanlan.zhihu.com/p/356976844

保存与读取

Save on GPU, Load on GPU Save:

torch.save(model.state_dict(), PATH)

Load:

device = torch.device("cuda")
model = TheModelClass(*args, **kwargs)
model.load_state_dict(torch.load(PATH))
model.to(device)
# Make sure to call input = input.to(device) on any input tensors that you feed to the model
model.eval()

Remember that you must call model.eval() to set dropout and batch normalization layers to evaluation mode before running inference. Failing to do this will yield inconsistent inference results.

误差的表示

训练参数怎么保存和读取

怎么表示数据

怎么反向梯度法训练

怎么使用GPU,怎么多GPU

在GPU上训练 就像你怎么把一个张量转移到GPU上一样,你要将神经网络转到GPU上。 如果CUDA可以用,让我们首先定义下我们的设备为第一个可见的cuda设备。

device = torch.device("cuda:0" if torch.cuda.is_available() else "cpu")

# Assume that we are on a CUDA machine, then this should print a CUDA device:

print(device) # cuda:0
net=Net()
net.to(device)
outputs = net(inputs)
input = torch.randn(1, 1, 32, 32)
inputs, labels = inputs.to(device), labels.to(device)
out = net(input)

多GPU

如果你想要来看到大规模加速,使用你的所有GPU,请查看:数据并行性(https://pytorch.org/tutorials/beginner/blitz/data_parallel_tutorial.html)。PyTorch 60 分钟入门教程:数据并行处理

http://pytorchchina.com/2018/12/11/optional-data-parallelism/

可视化

网络结构可视化

自动 https://stackoverflow.com/questions/52468956/how-do-i-visualize-a-net-in-pytorch

或者手动drawio

误差实时可视化TensorBoard

https://www.cnblogs.com/sddai/p/14516691.html

原理: 通过读取保存的log文件来可视化数据

标量可视化

记录数据,默认在当前目录下一个名为'runs/'的文件夹中。

from torch.utils.tensorboard import SummaryWriter

# 写log的东西
log_writer = SummaryWriter('./path/to/log')
# 第一个参数是名称,第二个参数是y值,第三个参数是x值。
log_writer.add_scalar('Loss/train', float(loss), epoch)

运行 tensorboard --logdir=runs/ --port 8123 在某端口打开,比如 https://127.0.0.1:6006

网络结构可视化

在tensorboard的基础上使用tensorboardX

from tensorboardX import SummaryWriter

with SummaryWriter(comment='LeNet') as w:
    w.add_graph(net, (net_input, ))

PR曲线

什么是PR曲线

log_writer.add_pr_curve("pr_curve", label_batch, predict, epoch)

x,y轴分别是recall和precision。应该有可能有矛盾的数据,或者网络分不开,对于不同的阈值,可以划分出PR图。

与ROC曲线左上凸不同的是,PR曲线是右上凸效果越好。

怎么分布式并行

需要进一步的研究学习

暂无

遇到的问题

  1. 矩阵或者向量的使用
  2. optimizer.step() # Does the update会自动循环吗?什么误差什么时候训练完毕呢?

开题缘由、总结、反思、吐槽~~

社会计算实验二,关于Meetup数据的预测性问题的解决

参考文献

https://pytorch-cn.readthedocs.io/zh/latest/

https://www.pytorch123.com/

https://zh.d2l.ai/chapter_convolutional-neural-networks/channels.html

Exploring the Impact of Dynamic Mutual Influence on Social Event Participation

Algorithm: leetcode

渐进符号

排序算法

* 排序算法的稳定性:排序前后相同元素的相对位置不变,则称排序算法是稳定的;否则排序算法是不稳定的。 * 计数排序 中 k是数据出现的范围 * 基数排序时间复杂度为O(N*M),其中N为数据个数,M为数据位数。

按照实现方法分类

  • 选择排序
  • 直接选择排序:N轮,每轮变小的范围内找到最小值,然后与第i个交换。
  • 堆排序:
    • 最大堆与数组的映射关系 大顶堆:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
    • 维护每轮范围变小的堆,每次将最大的堆顶移动到最后。每次维护堆需要O(logn)交换,把pop上来的小元素沉底到叶节点。
    • 初始建堆需要O(nlogn)
  • 插入排序
  • 直接插入:N轮,每轮从i开始向前插入(移动来交换),直到插入到合适的位置
  • 希尔排序: 希尔排序是插入排序改良的算法,
    • 希尔排序步长从大到小调整,第一次循环后面元素逐个和前面元素按间隔步长进行比较并交换,
    • 直至步长为1,步长选择是关键。
  • 交换排序
  • 冒泡排序:冒泡N轮,每轮变小的范围内确定最后一个。
  • 快速排序:在数组中随机选一个数(默认数组首个/末尾元素),数组中小于等于此数的放在左边部分(交换到前面的排列),大于此数的放在右边部分,这个操作确保了这个数是处于正确位置的,再对左边部分数组和右边部分数组递归调用快速排序,重复这个过程。

  • 分治合并

  • 归并排序: 首先让数组中的每一个数单独成为长度为1的区间,然后两两一组有序合并,得到长度为2的有序区间,依次合并进行得到长度为4、8、16的区间,直到合成整个区间。

  • 计数排序:数据出现的范围k << O(n)时,或者k=O(n)都可以采用该方法。

  • 基数排序:对数据的每一位(共M位)从低位到高位进行stableSort。大部分时候选择计数排序O(N+k)。总时间复杂度O(M*(N+k))
  • 桶排序:类似计数排序的思想,但是一般是对于区间等分为桶。桶内可以采用插入排序。n个元素n个桶,数学期望是O(n)

堆排序代码细节

void heapSort(int array[], int n)
{
    int i;
    //先建立堆
    for (i=n/2;i>0;i--)
    {
        HeapAdjust(array,i,n);//从下向上,从右向左调整
    }
    //交换最大堆顶,重复n次
    for( i=n;i>1;i--)
    {
        swap(array, 1, i);
        HeapAdjust(array, 1, i-1);//从上到下,从左向右调整
    }
}
void HeapAdjust(int array[], int s, int n )
{
    int i,temp;
    temp = array[s];
    for(i=2*s;i<=n;i*=2)
    {
        if(i<n&&array[i]<array[i+1])
        {
            //交换左右子树最大的那个
            i++;
        }
        if(temp>=array[i])
        {
            //找到了插入的合适的位置,子节点更小,父节点更大
            break;
        }
        // 将节点向上移动
        array[s]=array[i];
        s=i;
    }
    //将最顶部插入到合适的位置
    array[s]=temp;
}
void swap(int array[], int i, int j)
{
    int temp;
    temp=array[i];
    array[i]=array[j];
    array[j]=temp;
}

排序相关的问题

  • 既然时间复杂度堆排序、归并排序好于快排,为什么C++的qsort使用的是快排
  • 快速排序访存更友好,堆排序访问是跳跃的
  • 对于同样的数据,排序过程中,堆排序算法的数据交换次数多于快排
    • 堆排序建立堆,与堆顶的交换,很多时候都是无用功
  • 在数据量小的时候快速排序当属第一,堆排序最差,但随着数据的不断增大归并排序的性能会逐步赶上并超过快速排序,性能成为三种算法之首。
  • C++ 的 stable_sort 是基于归并排序的

LeetCode 常见算法

拓扑排序

拓扑排序常用来确定一个依赖关系集(图关系)中,事物发生的顺序。

带信号量判断的无依赖队列来实现,入队无依赖集合,出队的无依赖元素(add to result)去除后续元素的依赖信号量,信号量为0代表无依赖,可以入队。

无环图(树图)中最长距离

找到图中距离最远的两个节点与它们之间的路径:

以任意节点 pp 出现,利用广度优先搜索或者深度优先搜索找到以 pp 为起点的最长路径的终点 xx;

以节点 xx 出发,找到以 xx 为起点的最长路径的终点 yy;

xx 到 yy 之间的路径即为图中的最长路径,找到路径的中间节点即为根节点。

树状数组

https://leetcode-cn.com/circle/article/9ixykn/

https://leetcode-cn.com/problems/range-sum-query-mutable/

广度搜索确定图中各点对0点最近距离

//input [[0,1],[1,2]]
//维护
vector<vector<int>> adj(n); //先找出每个点的有关边
vector<bool> visit(n, false);   //维护已访问元素

queue<int> qu;

qu.emplace(0);
visit[0] = true;
int dist = 1;

while (!qu.empty()) {
    int sz = qu.size();
    for (int i = 0; i < sz; ++i) {
        int curr = qu.front();
        qu.pop();
        for (auto & v : adj[curr]) {
            if (visit[v]) {
                continue;
            }
            qu.emplace(v);
            //对应处理
            visit[v] = true;
        }
    }
    dist++;
}

2进制数表示子集合

对集合大小为n,可以用大于等于0小于1<<n2^n-1个数字来表示子集。

但是对每个子集都会单独计算,有重复。 不如用按每位是否存在回溯

#2044
class Solution {
public:
    int ans = 0;
    int countMaxOrSubsets(vector<int>& nums) {
        int maxOr = 0;
        for (auto n: nums){
            maxOr = n | maxOr;
        }
        dfs(nums, maxOr, 0 , 0);
        return ans;
    }
    void dfs(vector<int>& nums, int maxOr, int idx, int cur){
        if (cur == maxOr){
            ans += 1 << (nums.size()-idx);
            return;
        }

        if (idx == nums.size()){
            return;
        }

        dfs(nums, maxOr, idx+1, cur | nums[idx]);
        dfs(nums, maxOr, idx+1, cur);

    }
};

2进制表示使用状态true false

int 可以表示32个元素的使用情况

https://leetcode.cn/problems/can-i-win/

前缀和和差分

前缀和差分 是一组互逆的方法;他们的关系和积分求导 实质是一样的。前缀和可以帮我们通过预处理快速的求出区间的和;差分则可以快速帮助我们记录区间的修改。

将区间前一个加一,最后一个减一实现。

leetcode 798

预处理查询的数组

通过预处理记录信息来减少查询的时间

leetcode 2055

二分法

二分寻找满足条件的最小整数, 注意left + 1 < rights >= cars

while (left + 1 < right) { // 开区间
    long long mid = (left + right) / 2, s = 0;
    for (int r : ranks)
        s += sqrt(mid / r);
    (s >= cars ? right : left) = mid;
}
// 作者:灵茶山艾府
// 链接:https://leetcode.cn/problems/minimum-time-to-repair-cars/solutions/2177199/er-fen-da-an-pythonjavacgo-by-endlessche-keqf/
// 来源:力扣(LeetCode)
// 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

直接模拟

最常用的方法

哈希算法

根据设定的哈希函数H(key)和处理冲突方法将一组关键字映象到一个有限的地址区间上的算法。也称为散列算法、杂凑算法。

哈希冲突

一般有:开放定址法、链地址法(拉链法)、再哈希法、建立公共溢出区

LeetCode 代码优化加速

cin.tie与sync_with_stdio加速输入输出

std::ios::sync_with_stdio(); 是一个“是否兼容stdio”的开关,C++为了兼容C,保证程序在使用了std::printf和std::cout的时候不发生混乱,将输出流绑到了一起。也就是 C++标准streams(cin,cout,cerr…) 与相应的C标准程序库文件(stdin,stdout,stderr)同步,使用相同的 stream 缓冲区。 默认是同步的,但由于同步会带来某些不必要的负担,因此该函数作用是使得用户可以自行取消同步。

cin.tie(NULL) 取消 cin 和 cout 的绑定。

这对于输入数据个数在10^5以上的程序十分有效

static int x = []() {
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    return 0;
}();
// or
static const auto io_sync_off = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();

or

int init = []() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return 0;
}();

问题拆分循环调用

不如从底层动态规划合并,不要嵌套函数调用,还可以用二维数据,数据局部性较好。

https://leetcode-cn.com/problems/optimal-division/submissions/

不一定要执着数据只遍历一遍

可以将复杂的一次遍历,拆开成两次遍历,一次处理数据并存储,一次遍历统计。速度反而会快

简单递归循环

用while代替函数递归调用,eg二分法

减少if语句

可以保存分支的值来实现(1748)

//0ms
int sumOfUnique(vector<int>& nums) {
 int state[101]{}, ans = 0, d[101]{1,-1};
 for(int x: nums) ans += d[state[x]++] * x;
 return ans;
}

//4ms
int sumOfUnique(vector<int>& nums) {
 array<char,101> isshowed {};
 int sum=0;
 for(auto& num:nums){
  if(isshowed[num]==0){
   isshowed[num]=1;
   sum+=num;
  }else if(isshowed[num]==1){
   isshowed[num]=2;
   sum-=num;
  }
 }
 return sum;
}

通过判断筛选掉

无用的遍历计算(1219)

减少for循环

循环展开,只有一两种情况就不要写for循环了

注意的细节

计算防止溢出

int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2

转化成加减,而不用乘法

A < B/2
变成
A < B-A

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

https://oi-wiki.org/dp/basic/

https://github.com/azl397985856/leetcode/blob/master/thinkings/dynamic-programming.md

作者:AC_OIer 链接:https://leetcode-cn.com/problems/the-number-of-good-subsets/solution/gong-shui-san-xie-zhuang-ya-dp-yun-yong-gz4w5/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

Lock

互斥与同步的实现和使用

在进程/线程并发执行的过程中,进程/线程之间存在协作的关系,例如有互斥、同步的关系。

为了实现进程/线程间正确的协作,操作系统必须提供实现进程协作的措施和方法,主要的方法有两种:

  • 锁:加锁、解锁操作;
  • 自旋锁(spin lock, 忙等待锁),基于原子操作指令 —— 测试和置位(Test-and-Set)指令
  • 无等待锁:思想,把当前线程放入到锁的等待队列,然后执行调度程序

  • 信号量:P、V 操作;

这两个都可以方便地实现进程/线程互斥,而信号量比锁的功能更强一些,它还可以方便地实现进程/线程同步。

锁相关问题

  1. 共享内存加锁之后释放锁,别的进程是如何知道锁释放的
    1. 常用的方法是在共享内存中设置标志位或信号量等,并在共享内存中保证这个标志位或信号量只有在锁被释放时才会被更新。这样,其它进程可以通过轮询或者等待通知的方式来获取锁并开始修改共享内存,从而避免冲突。在共享内存中设置的标志位或信号量通常需要原子操作的支持,以确保并发修改时的正确性。
      1. 轮询:轮询是指线程反复检查某个条件是否成立,直到条件成立为止。在锁机制中,当一个线程持有锁时,其他线程会不断地轮询锁的状态,直到该锁被释放。这种方式的优点是实现简单,不需要额外的通知机制,缺点是占用CPU资源,效率较低。
      2. 等待通知:等待通知是指线程在某个条件不满足时挂起等待,当条件满足时由其他线程通知它继续执行。在锁机制中,当一个线程持有锁时,其他线程会进入等待状态,直到该锁被释放,此时其他线程会被通知并继续执行。这种方式的优点是占用CPU资源少,效率高,缺点是实现稍微复杂一些,需要额外的通知机制。
    2. 另外,也可以使用一个中央锁服务器或者等待队列来管理锁,当一个进程获取锁时,会向中央锁服务器或等待队列发出请求,直到锁被成功获取,并在共享内存中记录锁的状态。当锁被释放时,中央锁服务器或等待队列会通知其它进程,并让其它进程开始自由修改共享内存。
  2. 如何保证操作的原子性
    1. 操作系统提供的原子操作:一些操作系统会提供线程安全的原子操作接口,如Compare-And-Swap(CAS)等,它们能够确保指令的原子性,从而保证线程安全。
    2. 事务:事务是指一组操作被视为一个不可分割的操作序列,要么全部执行成功,要么全部失败,具有原子性和一致性保证。常用于数据库操作等场景。
    3. 锁机制:锁机制是一种常用的多线程同步机制,能够确保同一时刻只有一个线程(或进程)可以访问共享资源,从而保证原子性。
  3. 如何避免死锁
    1. 避免使用多把锁并且同时持有多个锁。当需要持有多个锁时,可以通过加锁的顺序来避免死锁。如果所有可能的锁按照固定的顺序加锁,那么可以避免死锁。
    2. 设置请求超时时间。当一个进程请求锁时,如果在超时时间内没有获得锁,可以释放之前持有的锁,并尝试重新获取。这样可以避免某一个进程一直持有锁而导致死锁。
    3. 引入随机性。在获取锁的时候加入一些随机因素,让不同的程序在不同的时间获取锁。这样可以防止程序之间在自己的重试过程中的饥饿状态导致的死锁。

RedStar (小红书) 笔试

图中有依赖的任务的,需要几个信号量来实现同步

CSDN,有一条依赖线,需要一个信号量

在使用信号量(Semaphore)进行线程同步时,P(proberen)和V(verhogen)操作是非常重要的概念。

  1. P操作(也称为Wait操作或Down操作):

  2. 表示获取或等待信号量。

  3. 如果信号量内部计数值大于0,获取信号量并将计数值减1。
  4. 如果计数值等于0,线程将等待,直到计数值大于0。如果信号量的值大于0,表示资源可用,进程可以继续执行。如果信号量的值为0,表示资源不可用,P操作将阻塞(即等待)进程,直到该信号量的值大于0为止。

伪代码表示为:

P(S):
  while S <= 0:
    // 等待,直到S大于0
  S = S - 1
  1. V操作(也称为Signal操作或Up操作):

  2. 表示释放或增加信号量。

  3. 将信号量内部计数值加1。
  4. 如果存在等待线程,唤醒其中一个线程继续执行。

伪代码表示为:

V(S):
  S = S + 1

P和V操作保证了对共享资源的互斥访问。

一个线程使用P操作等待获取信号量,V操作在使用完共享资源后释放信号量。

信号量的值通常用于控制共享资源的数量,它可以是非负整数。当信号量被初始化为1时,称为二进制信号量(Binary Semaphore),因为它只能取0或1的值,通常用于实现互斥访问临界区。如果信号量的值大于1,称为计数信号量,可用于限制对资源的并发访问数。

在实际编程中,P操作和V操作通常是原子操作,确保在多线程或多进程环境下的正确同步和竞争条件的安全处理。

TP-link笔试

设计的程序在多个CPU上运行时,不应使用哪个实现多个CPU间的数据访问同步?

  • 自旋锁(spinlock): 多线程同步的一种忙等待锁,线程反复检查锁变量是否可用。
  • 优点:避免了操作系统进程调度和线程切换,所以自旋锁通常适用在时间比较短的情况下。由于这个原因,操作系统的内核经常使用自旋锁。
  • 缺点:如果长时间上锁的话,自旋锁会非常耗费性能,它阻止了其他线程的运行和调度
    • 线程持有锁的时间越长,则持有该锁的线程将被 OS(Operating System) 调度程序中断的风险越大。
  • 解决办法: TicketLock 是采用排队叫号的机制。CLHLock和MCSLock通过链表的方式避免了减少了处理器缓存同步,极大的提高了性能,区别在于CLHLock是通过轮询其前驱节点的状态,而MCS则是查看当前节点的锁状态。
  • 互斥锁(mutex):把自己阻塞起来(内核态和用户态之间的切换进入阻塞状态,可能上下文切换),等待重新调度请求。
  • 互斥锁的实现
    1. 软件实现:软件互斥锁需要借助操作系统提供的原子操作(如Compare-And-Swap,CAS)来实现 优点是灵活性高 缺点是性能较低,
    2. CAS操作需要三个参数,内存地址A,期望值V,新值N。执行过程如下:
      • 读取内存地址A的原始值,保存在临时变量Value中
      • 比较Value和期待值V是否相等,如果相等则将内存地址A的值更新为新值N
      • 如果内存地址A的值已经被其他线程改变,则不进行更新操作
    3. TAS(test and set)
    4. 一个TAS指令包括两个子步骤,把给定的内存地址设置为1,然后返回之前的旧值。
    5. 硬件实现:硬件互斥锁使用计算机硬件提供的特殊指令(如锁总线指令)来实现。当线程要获取锁时,它会发出一个锁总线指令,这个指令会占用系统总线,使得其他CPU无法读写内存。
      1. 当lock前缀指令执行时,它将锁定处理器总线,确保其他处理器无法同时访问同一内存区域,
  • 读写锁(ReadWrite Lock)
  • 在读操作和写操作之间提供了更细粒度的同步控制。
  • 多个线程可以同时获取读锁,但只有一个线程能够获取写锁。
    • 读写锁有三种状态:读加锁状态、写加锁状态和不加锁状态
    • 规则
    • 当读写锁在写加锁模式下,任何试图对这个锁进行加锁的线程都会被阻塞,直到写进程对其解锁。
    • 当读写锁在读加锁模式先,任何线程都可以对其进行读加锁操作,但是所有试图进行写加锁操作的线程都会被阻塞,直到所有的读线程都解锁。
  • 缺点:当读者源源不断到来的时候,写者总是得不到读写锁,就会造成不公平的状态。
    • 避免方法: 当处于读模式的读写锁接收到一个试图对其进行写模式加锁操作时,便会阻塞后面对其进行读模式加锁操作的线程。这样等到已经加读模式的锁解锁后,写进程能够访问此锁保护的资源。
  • 优点:
    • 读写锁可以提高并发性,允许多个线程同时读取数据,而只有在需要修改数据时才会互斥。
    • 适合对数据结构读的次数远远大于写的情况。
  • RCU(Read-Copy-Update)
  • 对读写锁的一种改进。适用于读多写少场景的数据同步机制。
  • 具体内容

    • 并发读取数据不再需要加锁
    • 写数据时,RCU机制通过创建一个副本来实现读写分离,确保在更新过程中没有线程正在读取旧的数据。
    • 写者修改数据前首先拷贝一个被修改元素的副本,然后在副本上进行修改,修改完毕后它向垃圾回收器注册一个回调函数以便在适当的时机执行真正的修改操作。
    • 读者必须提供一个信号给写者以便写者能够确定数据可以被安全地释放或修改的时机。
    • 有一个专门的垃圾收集器来探测读者的信号,一旦所有的读者都已经发送信号告知它们都不在使用被RCU保护的数据结构,垃圾收集器就调用回调函数完成最后的数据释放或修改操作。
  • 悲观锁

    1. 写操作时,需要预先加锁,防止其他进程对资源的访问。
    2. 通过互斥锁(Mutex)和信号量(Semaphore)来实现。
  • 乐观锁

  • 在读取或修改共享资源时,并不先进行加锁操作,而是先读取资源,然后在对资源进行写操作时再进行一次比较,看看在这个时间间隔内是否发生了竞争。如果没有发生竞争,就可以将更新后的值写入共享资源,并结束操作;如果发生了竞争,则需要放弃本次更新,并进行重试
  • 通过版本号的方式来实现。在共享资源中记录该资源的版本号,当一个进程想要修改共享资源时,需要先获取当前资源的版本号。如果当前版本号与自己保存的版本号相符,说明没有其他进程在这段时间内修改该资源,则可以进行写操作;如果版本号已经发生变化,则说明有其他进程对该资源进行了修改,当前进程需要放弃本次写操作,更新版本号,重新获取新的资源,并重新执行操作。

下面回答部分来自ChatGPT-3.5,暂时没有校验其可靠性(看上去貌似说得通)。

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

https://www.cswiki.top/pages/f398f1/#blocking-i-o

原文链接:https://blog.csdn.net/qq_15437629/article/details/79116590

https://zhuanlan.zhihu.com/p/161936748

LLVM-MCA: docs

Introduction

LLVM Machine Code Analyzer 是一种性能分析工具,它使用llvm中可用的信息(如调度模型)静态测量特定CPU中机器代码的性能。

性能是根据吞吐量处理器资源消耗来衡量的。该工具目前适用于在后端中使用LLVM调度模型的处理器。

该工具的主要目标不仅是预测代码在目标上运行时的性能,还帮助诊断潜在的性能问题。

给定汇编代码,llvm-mca可以估计每个周期的指令数(IPC)以及硬件资源压力。分析和报告风格的灵感来自英特尔的IACA工具。

github

https://github.com/llvm/llvm-project/tree/main/llvm/tools/llvm-mca

docs

https://llvm.org/docs/CommandGuide/llvm-mca.html

options

architecture

-mtriple=<target triple>
    eg. -mtriple=x86_64-unknown-unknown
-march=<arch>
    Specify the architecture for which to analyze the code. It defaults to the host default target.
-march=<arch>
    Specify the architecture for which to analyze the code. It defaults to the host default target.
# 查看支持的arch
llc --version
# 查看具体支持的CPU Architecture
llc -march=x86 -mattr=help

output-report

-output-asm-variant=<variant id>
    为工具生成的报告指定输出程序集变量。???
-print-imm-hex
    优先16进制输出。
-json
    除了瓶颈分析,基本都支持json格式输出视图
-timeline
    打印指令流水线情况

runtime options

-dispatch=<width>
    为处理器指定不同的调度宽度。调度宽度默认为处理器调度模型中的“IssueWidth”字段。
-register-file-size=<size>
    指定寄存器文件的大小。指定时,该项会限制可用于寄存器重命名的物理寄存器的数量。此标志的值为零意味着“无限数量的物理寄存器”。
-iterations=<number of iterations>
    指定要运行的迭代次数。如果此标志设置为 0,则该工具会将迭代次数设置为默认值(即 100)。
-noalias=<bool>
    loads and stores don’t alias
-lqueue=<load queue size>
-squeue=<store queue size>
    在工具模拟的加载/存储单元中指定加载队列的大小。默认情况下,该工具假定加载队列中的条目数量不受限制。此标志的零值将被忽略,而是使用默认加载队列大小。
-disable-cb
    强制使用通用的 CustomBehaviour 和 InstrPostProcess 类,而不是使用目标特定的实现。通用类从不检测任何自定义危险或对指令进行任何后处理修改。

more values/Info

-resource-pressure
    Enable the resource pressure view. This is enabled by default.
-register-file-stats
    启用注册文件使用统计。
-dispatch-stats
-scheduler-stats
-retire-stats
-instruction-info
    启用额外的调度/发出/retire control unit统计。该视图收集和分析指令分派事件,以及静态/动态分派停顿事件。默认情况下禁用此视图。
-show-encoding
    打印指令16进制
-all-stats
-all-views
-instruction-tables
    这与资源压力视图不同,因为它不需要模拟代码。相反,它按顺序打印每个指令的资源压力的理论均匀分布。
-bottleneck-analysis
    打印有关影响吞吐量的瓶颈的信息。这种分析可能很昂贵,并且默认情况下是禁用的。瓶颈在摘要视图中突出显示。具有有序后端的处理器目前不支持瓶颈分析。???

实现逻辑

样例分析

quick overview of the performance throughput

Iterations:        300
Instructions:      900
Total Cycles:      610
Total uOps:        900

Dispatch Width:    2
uOps Per Cycle:    1.48
IPC:               1.48
Block RThroughput: 2.0
  1. IPC
  2. 理论最大值是\(\(\frac{OneLoopInstructions}{Block\_RThroughput}=(OneLoopInstructions)*(Block\_Throughput)\)\)
  3. uOps Per Cycle
  4. simulated micro opcodes (uOps)
  5. 每个周期的simulated micro opcodes数
  6. 在不考虑循环依赖的情况下,理论上最大值是\(\(\frac{OneLoopUOps}{Block\_RThroughput}=(OneLoopUOps)*(Block\_Throughput)\)\)
  7. A delta between Dispatch Width and this field is an indicator of a performance issue.
  8. The delta between the Dispatch Width (2.00), and the theoretical maximum uOp throughput (1.50) is an indicator of a performance bottleneck caused by the lack of hardware resources, and the Resource pressure view can help to identify the problematic resource usage.
  9. Dispatch Width
  10. 发射到乱序后端的最大微指令操作数(the maximum number of micro opcodes/uOps)?
  11. Block RThroughput (Block Reciprocal Throughput)
  12. 在不考虑循环依赖的情况下,理论上的每次循环的最大block或者iterations数
  13. 受限于dispatch rate和the availability of hardware resources.

Instruction info view

Instruction Info:
[1]: #uOps
[2]: Latency
[3]: RThroughput
[4]: MayLoad
[5]: MayStore
[6]: HasSideEffects (U)

[1]    [2]    [3]    [4]    [5]    [6]    Instructions:
 1      2     1.00                        vmulps      %xmm0, %xmm1, %xmm2
 1      3     1.00                        vhaddps     %xmm2, %xmm2, %xmm3
 1      3     1.00                        vhaddps     %xmm3, %xmm3, %xmm4
 ```

显示了指令里队列每条指令的**延迟**和**吞吐量的倒数**。

RThroughput是指令吞吐量的倒数。在不考虑循环依赖的情况下,吞吐量是**单周期能执行的同类型指令的最大数量**。

### Resource pressure view
Resources: [0] - JALU0 [1] - JALU1 [2] - JDiv [3] - JFPA [4] - JFPM [5] - JFPU0 [6] - JFPU1 [7] - JLAGU [8] - JMul [9] - JSAGU [10] - JSTC [11] - JVALU0 [12] - JVALU1 [13] - JVIMUL

Resource pressure per iteration: [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] - - - 2.00 1.00 2.00 1.00 - - - - - - -

Resource pressure by instruction: [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] Instructions: - - - - 1.00 - 1.00 - - - - - - - vmulps %xmm0, %xmm1, %xmm2 - - - 1.00 - 1.00 - - - - - - - - vhaddps %xmm2, %xmm2, %xmm3 - - - 1.00 - 1.00 - - - - - - - - vhaddps %xmm3, %xmm3, %xmm4 ```

每次循环或者每条指令执行,消耗的资源周期数。从而找到高资源占用的部分。

Timeline View

可打印流水线情况

Timeline view:
                    012345
Index     0123456789

[0,0]     DeeER.    .    .   vmulps   %xmm0, %xmm1, %xmm2
[0,1]     D==eeeER  .    .   vhaddps  %xmm2, %xmm2, %xmm3
[0,2]     .D====eeeER    .   vhaddps  %xmm3, %xmm3, %xmm4
[1,0]     .DeeE-----R    .   vmulps   %xmm0, %xmm1, %xmm2
[1,1]     . D=eeeE---R   .   vhaddps  %xmm2, %xmm2, %xmm3
[1,2]     . D====eeeER   .   vhaddps  %xmm3, %xmm3, %xmm4
[2,0]     .  DeeE-----R  .   vmulps   %xmm0, %xmm1, %xmm2
[2,1]     .  D====eeeER  .   vhaddps  %xmm2, %xmm2, %xmm3
[2,2]     .   D======eeeER   vhaddps  %xmm3, %xmm3, %xmm4


Average Wait times (based on the timeline view):
[0]: Executions
[1]: Average time spent waiting in a scheduler's queue
[2]: Average time spent waiting in a scheduler's queue while ready
[3]: Average time elapsed from WB until retire stage

      [0]    [1]    [2]    [3]
0.     3     1.0    1.0    3.3       vmulps   %xmm0, %xmm1, %xmm2
1.     3     3.3    0.7    1.0       vhaddps  %xmm2, %xmm2, %xmm3
2.     3     5.7    0.0    0.0       vhaddps  %xmm3, %xmm3, %xmm4
       3     3.3    0.5    1.4       <total>

影响因素包括:

  1. 数据冲突/依赖:读后写,写后读依赖 。无法指令级并行,也可以通过寄存器重命名解决
  2. 结构冲突:占用发射位 或者 同一硬件
  3. 控制冲突:分支?
  4. instructions must retire in program order, so [1,0] has to wait for [0,2] to be retired first

Bottleneck Analysis

  • 可以分析出数据冲突/依赖和结构冲突的影响大小
  • 准确性取决于模拟和是否有对应CPU模型。
  • 暂时不支持有序后端。
Cycles with backend pressure increase [ 91.52% ]
Throughput Bottlenecks:
  Resource Pressure       [ 0.01% ]
  - SBPort0  [ 0.01% ]
  - SBPort1  [ 0.01% ]
  - SBPort5  [ 0.01% ]
  Data Dependencies:      [ 91.51% ]
  - Register Dependencies [ 91.51% ]
  - Memory Dependencies   [ 10.76% ]
  • 端口信息来自TableGen llvm/lib/Target/X86/X86SchedSandyBridge.td
  • 鲲鹏920的来自 llvm/lib/Target/AArch64/AArch64SchedTSV110.td

额外信息

  1. Dynamic Dispatch Stall Cycles
  2. Dispatch Logic
  3. 可以看出流水线发射满带宽或几条指令的时间占比
  4. Schedulers
  5. 每个周期微指令发射数占比
  6. Scheduler's queue usage
  7. 执行时使用的平均或最大buffer entries (i.e., scheduler queue entries)
  8. AMD Jaguar

  9. JALU01 - A scheduler for ALU instructions. JFPU01 - A scheduler floating point operations. JLSAGU - A scheduler for address generation.

  10. Retire Control Unit

  11. 在一个周期里有多少指令retired的占比(好吧,感觉有语病)
  12. A re-order buffer (ROB) 的使用情况
  13. Register File statistics
  14. physical register file (PRF)
  15. floating-point registers (JFpuPRF)
  16. integer registers (JIntegerPRF)

Instruction Flow

llvm-mca 假设指令在模拟开始之前已经全部解码并放入队列中。因此,指令提取和解码阶段没有被计算。未考虑前端的性能瓶颈。此外,llvm-mca 不模拟分支预测。

Instruction Dispatch

处理器的默认 dispatch width值等于LLVM’s scheduling model里的IssueWidth值。

An instruction can be dispatched if:

  • The size of the dispatch group is smaller than processor’s dispatch width.
  • There are enough entries in the reorder buffer.
  • There are enough physical registers to do register renaming.
  • The schedulers are not full.

reorder buffer负责跟踪命令,使之按照程序顺序retired结束。其默认值为 MicroOpBufferSize 。

各种Buffered resources 被视作scheduler resources.

Instruction Issue

每个处理器调度器实现一个指令缓冲区。指令必须在调度程序的缓冲区中等待,直到输入寄存器操作数可用。只有在那个时候,指令才符合执行的条件,并且可能会被发出(可能是乱序的)以供执行。 llvm-mca 在调度模型的帮助下计算指令延迟。

llvm-mca 的调度器旨在模拟多处理器调度器。调度器负责跟踪数据依赖关系,并动态选择指令消耗哪些处理器资源。它将处理器资源单元和资源组的管理委托给资源管​​理器。资源管理器负责选择指令消耗的资源单元。例如,如果一条指令消耗了一个资源组的1cy,则资源管理器从该组中选择一个可用单元;默认情况下,资源管理器使用循环选择器来保证资源使用在组的所有单元之间均匀分配。

llvm-mca’s scheduler internally groups instructions into three sets:

  • WaitSet: a set of instructions whose operands are not ready.
  • ReadySet: a set of instructions ready to execute.
  • IssuedSet: a set of instructions executing.

Write-Back and Retire Stage

retire control unit

  1. When instructions are executed,the flags the instruction as “ready to retire.”
  2. Instructions are retired in program order
  3. free the physical registers

Load/Store Unit and Memory Consistency Model

load/store unit (LSUnit)用来模拟乱序memory操作

The rules are:

  1. A younger load is allowed to pass an older load only if there are no intervening stores or barriers between the two loads.
  2. A younger load is allowed to pass an older store provided that the load does not alias with the store.
  3. A younger store is not allowed to pass an older store.不能交换顺序的意思
  4. A younger store is not allowed to pass an older load.

假设 loads do not alias (-noalias=true) store operations.Under this assumption, younger loads are always allowed to pass older stores. ???

LSUnit不打算跑alias analysis来预测何时load与store不相互alias???

in the case of write-combining memory, rule 3 could be relaxed to allow reordering of non-aliasing store operations.???

LSUnit不管的其余三点:

  1. The LSUnit does not know when store-to-load forwarding may occur.
  2. The LSUnit does not know anything about cache hierarchy and memory types.
  3. The LSUnit does not know how to identify serializing operations and memory fences.
  4. The LSUnit does not attempt to predict if a load or store hits or misses the L1 cache(不考虑cache命中,默认是命中L1,产生the load-to-use latency的最乐观开销)

llvm-mca 不知道序列化操作或内存屏障之类的指令。 LSUnit 保守地假设同时具有“MayLoad”和未建模副作用的指令的行为类似于“软”load-barrier。这意味着,它在不强制刷新load队列的情况下序列化加载。类似地,“MayStore”和具有未建模副作用的指令被视为store障碍。完整的memory-barrier是具有未建模副作用的“MayLoad”和“MayStore”指令。LLVM的实现是不准确的,但这是我们目前使用 LLVM 中可用的当前信息所能做的最好的事情。

load/store barrier会占用在load/store 队列里占用一项。 当load/store barrier是其队列里oldest项时,其会被执行

In-order Issue and Execute

有序处理器被建模为单个 InOrderIssueStage 阶段。它绕过 Dispatch、Scheduler 和 Load/Store 单元。一旦它们的操作数寄存器可用并且满足资源要求,就会发出指令。根据LLVM的调度模型中IssueWidth参数的值,可以在一个周期内发出多条指令。一旦发出,指令就会被移到 IssuedInst 集,直到它准备好retire。 llvm-mca 确保按顺序提交写入。但是,如果 RetireOOO 属性for at least one of its writes为真,则允许指令提交写入并无序retire???

Custom Behaviour 自定义行为

某些指令在该模型中并不能被准确的模拟。为了几条指令而修改模型不是个好的选择,一般通过CustomBehaviour类对某些指令进行特殊建模:自定义数据依赖,以及规避、单独处理特殊情况。

为此,llvm-mca设置了一个通用的以及多个特殊的CustomBehaviour类。下面两种情况下会使用通用类:

  1. 开启了-disable-cb选项
  2. 不存在针对某目标的特殊类(通用类也做不了什么,我什么也做不到😥)

但是注意目前只有in-order流水线实现了CustomBehaviour类,out-order流水线将来也会支持。

该类主要通过checkCustomHazard()函数来实现,通过当前指令和真正流水线中执行的指令,来判断当前指令需要等待几个周期才能发射。

如果想对没有实现的目标添加CustomBehaviour类,可以参考已有的实现,比如在/llvm/lib/Target/AMDGPU/MCA/目录下。

Custom Views 自定义视图

关于自定义的视图的添加路径,如果没有输出从未在MC layer classes (MCSubtargetInfo, MCInstrInfo, etc.)里出现过的新后端值,请把实现加入/tools/llvm-mca/View/。相反,请加入/lib/Target/<TargetName>/MCA/目录。

关于Custom Views所需内容,需要写特殊的CustomBehaviour类来覆写CustomBehaviour::getViews()函数,根据位置的不同还有三种实现getStartViews(), getPostInstrInfoViews(),getEndViews()

影响准确性的因素

调度模型不仅用于计算指令延迟和吞吐量,还用于了解可用的处理器资源以及如何模拟它们。

llvm mca进行分析的质量不可避免地受到llvm中调度模型质量的影响。

功能(能估计的值

  1. IPC
  2. 硬件资源压力resource-pressure
  3. 一些额外Info? 1.

    register-file-stats
    -dispatch-stats
    -scheduler-stats
    -retire-stats
    -instruction-info
    instruction-tables
    
  4. 吞吐量瓶颈?

支持对特定代码块的分析

  1. 汇编代码,支持命名和嵌套

    # LLVM-MCA-BEGIN block-name
    add %eax, %eax
    # LLVM-MCA-END
    
  2. 高级语言,通过内联汇编实现

 int foo(int a, int b) {
     __asm volatile("# LLVM-MCA-BEGIN foo");
     a += 42;
     __asm volatile("# LLVM-MCA-END");
     a *= b;
     return a;
 }

但是,这会干扰循环矢量化等优化,并可能对生成的代码产生影响。具体影响请对比汇编代码。

相关论文

Google学术搜llvm-mca,一堆论文。但是不急着看,因为没有预备知识,没有问题的去看论文。效率和收获很低的,而且会看不懂。

相关项目

mc-ruler

mc-ruler是整合了llvm-mca的cmake,可以打印指定部分的代码分析信息。如果之后要测试可能用得上。

需要进一步的研究学习

  1. 具体功能
  2. llvm如何实现的,要看代码。

遇到的问题

  1. (llvm-mca detects Intel syntax by the presence of an .intel_syntax directive at the beginning of the input. By default its output syntax matches that of its input.)
  2. ???的地方
  3. 大概看了一下功能,但是性能怎么对比呢。准确值是多少呢?
  4. arm kunpeng pmu-tools 实现
  5. 每次的估计值会波动吗?

如何和大神交流呢+提问的艺术

开题缘由、总结、反思、吐槽~~

参考文献

llvm Backend

llvm 后端 概述

  • 后端(backend)由一套分析转换Pass组成,它们的任务是代码生成,即将LLVM中间表示(IR)变换为目标代码(或者汇编)。
  • LLVM支持广泛的目标:ARM,AArch64,Hexagon,MSP430,MIPS,Nvidia PTX,PowerPC,R600,SPARC,SystemZ,X86,和XCore。
  • 所有这些后端共享一套共用的接口,它是目标无关代码生成器的一部分,以通用API的方法抽象化后端任务。每个目标必须特殊化代码生成通用类,以实现目标特定的行为。

后端的基本流程

  • 下图给出了将LLVM IR转换为目标汇编代码必需的步骤

Backend

  • 浅灰色的中间框,也叫super pass,是必需的,它们是后端的核心部分。
  • 白色框所指示的,可以执行非必需的优化Pass以进一步改进翻译的质量。对于提高所生成的代码的效率更重要。
  • 比如-O3的优化,而且其顺序对结果也有影响。

详细解释各阶段:

  1. 指令选择(Instruction Selection):将三地址结构的LLVM IR变换为DAG(Directed Acyclic Graph)
  2. 每个DAG能够表示单一基本块的计算。DAG内节点表示机器指令,边表示数据依赖关系。
  3. 第1次指令调度(Instruction Scheduling),也称为前寄存器分配(RA)调度,对指令排序,同时尝试发现尽可能多的指令层次的并行。然后这些指令被变换为MachineInstr三地址表示。
  4. 寄存器分配(Register Allocation),它将无限的虚拟寄存器的引用转换为有限的目标特定的寄存器集,寄存器不够时挤出(spill)到内存。
  5. 第2次指令调度,也称为后寄存器分配(RA)调度。因为此时在这个点可获得真实的寄存器信息,某些类型寄存器存在额外的风险和延迟,它们可被用以改进指令顺序。
  6. 代码输出(Code Emission)阶段将指令从MachineInstr表示变换为MCInst实例。这种新的表示更适合汇编器和链接器,它有两种选择:输出汇编代码或者输出二进制块(blob)到一种特定的目标代码格式。

后端代码结构

后端的实现分散在LLVM源代码树的不同目录中。代码生成背后的主要程序库位于lib目录和它的子文件夹CodeGen、MC、TableGen、和Target中, 具体参考文档

Tablegen位置在类似 llvm/lib/Target/X86/X86.td的地方

llvm 编译优化

  • 通过llvm的分析和转换Pass相结合实现的。
  • 首先,通过分析Pass获取程序的一些特性和数据流等信息,例如控制流分析、数据流分析、依赖分析等。
  • 然后,根据所得到的分析信息,llvm会执行转换Pass,对程序进行一系列的重构、优化和变换,例如常量传播、死代码消除、内联函数、循环展开等。

举例:O3优化实现

程序优化选项 -O3 是通过启用 LLVM Pass Manager 并按照顺序执行包含多个具体优化 Pass 的过程实现的。包括:

  1. 函数内部优化 Pass,如内联、函数内联、无用函数清理、控制流扁平化;
  2. 函数间优化 Pass,如基于静态单走边分析的间接调用目标推导、函数每次调用的参数的重复计算消除、通过符号解析执行的函数简介化等。
  3. 模块优化 Pass,如死代码消除、全局优化、常量传播、数值宽化和窄化、整除优化等;
  4. 特定于架构的优化 Pass,包括指令调度和寄存器分配等。

这些 Pass 的执行范围涵盖 LLVM IR 与 LLVM 后端。

TableGen

  • LLVM的TableGen是一种表格驱动代码生成工具,主要用于生成汇编器、反汇编器、指令选择器、调度器等代码。
  • 它使用基于LLVM IR的DSL(Domain-Specific Language)来描述目标指令集的特性和规则,然后将这些信息转换为C++代码。
  • 使用TableGen可以将目标指令集的实现与源代码分离,从而提高代码的可读性和可维护性。

TableGen的输入文件使用扩展名“.td”(TableGen的缩写),它们可以描述如下内容:

  1. Instruction Set Architecture (ISA) - 描述目标机的指令集特性,例如指令集架构、寄存器、寄存器类、操作数类型、地址模型、端对齐性等。
  2. Selection DAG - 描述了如何将LLVM IR节点映射到目标机指令集的指令,例如指令的操作码、操作数、调用约定、指令延迟等。
  3. Pattern Matching - 对匹配到的指令模板做出生成想要的IR节点的选择。
  4. Instruction Scheduling - 描述调度器行为、指令之间的时间关系,以及如何将指令插入到调度图中的规则等。

  5. TableGen自动化了目标机指令集的大部分工作,同时也使得自定义目标机变得相对容易。

  6. 该工具支持针对多种平台和编译器的后端代码生成。
  7. 对于嵌入式系统和非标准指令集架构等领域,TableGen有着广泛的应用。

相关的概念

  • 目标描述语言(Target Description Language,TDL)来定义目标架构特定的指令和寄存器。其中,TDL可用于目标架构中指令定义和寄存器定义的映射关系和动态生成机器指令的规则。

实践:llvm IR 后端

实现一个简单的LLVM IR后端,将LLVM IR转换为x86汇编代码,能line by line的输出。

参考LLVM官方文档中的“Writing an LLVM Backend”以及“TableGen Backends”

需要进一步的研究学习

暂无

遇到的问题

暂无

开题缘由、总结、反思、吐槽~~

参考文献

https://getting-started-with-llvm-core-libraries-zh-cn.readthedocs.io/zh_CN/latest/ch06.html#id2