跳转至

2023

Wireguard

简介

  • WireGuard 是由 Jason Donenfeld 等人用 C 语言编写的一个开源 VPN 协议,被视为下一代 VPN 协议,旨在解决许多困扰 IPSec/IKEv2、OpenVPN 或 L2TP 等其他 VPN 协议的问题。它与 Tinc 和 MeshBird 等现代 VPN 产品有一些相似之处,即加密技术先进、配置简单。
  • 从 2020 年 1 月开始,它已经并入了 Linux 内核的 5.6 版本,这意味着大多数 Linux 发行版的用户将拥有一个开箱即用的 WireGuard。
  • WireGuard 作为一个更先进、更现代的 VPN 协议,比起传统的 IPSec、OpenVPN 等实现,效率更高,配置更简单,并且已经合并入 Linux 内核,使用起来更加方便。

常见VPN方法比较

  • wireguard 精簡、速度極快:
  • 只有 4000 行程式碼,是最精簡的 VPN 協議。对比下 OpenVPN,大约有 10 万行代码。
  • WireGuard 利用内核空间处理来提升性能(更高吞吐和更低延迟),同时避免了不必要的内核和用户空间频繁上下文切换开销。

Wireguard客户端连接Debug

  • 首先,服务端的ip或者域名能ping通
  • 其次端口确定开放> nc -z -v -u 4.shaojiemike.top 51822,wg是udp
  • 修改wg客户端配置文件,限制ip为wg设置的内网段,AllowedIPs = 192.168.31.0/24,10.0.233.1/24.然后ping 192.168.31.1测试
  • 如果还不行,判断为wg的VPN包被中间网关识别并丢弃

配置文件

配置详解参考中文文档

PersistentKeepalive

  • 一端位于 NAT 后面,另一端直接通过公网暴露
  • 这种情况下,最简单的方案是:通过公网暴露的一端作为服务端,另一端指定服务端的公网地址和端口,然后通过 persistent-keepalive 选项维持长连接,让 NAT 记得对应的映射关系。
  • [peer]里设定字段 PersistentKeepalive = 25,表示每隔 25 秒发送一次 ping 来检查连接。

AllowedIPs

虽然AllowedIPs = 0.0.0.0/0AllowedIPs = 0.0.0.0/1, 128.0.0.0/1包含的都是全部的ip。

但是前者在iptable里为default dev wg1,后者为两条0.0.0.0/1 dev wg1128.0.0.0/1 dev wg1

由于路由的ip匹配遵循最长前缀匹配规则,如果路由表里原本有一条efault dev eth0。使用前者会导致混乱。但是使用后者,由于两条的优先级会更高,会屏蔽掉原本的default规则。

前者的iptable修改如下:(macbook上)

> ip route
default via link#18 dev utun3
default via 192.168.233.1 dev en0
10.0.233.5/32 via 10.0.233.5 dev utun3
224.0.0.0/4 dev utun3  scope link
224.0.0.0/4 dev en0  scope link
255.255.255.255/32 dev utun3  scope link
255.255.255.255/32 dev en0  scope link

后者的iptable修改如下

> ip route
0.0.0.0/1 dev utun3  scope link
default via 192.168.233.1 dev en0
default via link#18 dev utun3
10.0.233.5/32 via 10.0.233.5 dev utun3
128.0.0.0/1 dev utun3  scope link
224.0.0.0/4 dev en0  scope link
224.0.0.0/4 dev utun3  scope link
255.255.255.255/32 dev en0  scope link
255.255.255.255/32 dev utun3  scope link

原理

建议看WireGuard 教程:WireGuard 的工作原理WireGuard 基础教程:wg-quick 路由策略解读,详细解释了wg是如何修改路由表规则的。

wireguard 运行原理以及配置文件

默认会产生51840的路由table,ip rule优先级较高。可以通过配置文件中添加PostUp来修改最后一个default的路由规则。

root@snode6:/etc/wireguard# cat wg0.conf
[Interface]
Address = 192.168.253.5/32,fd00::aaaa:5/128
PrivateKey = eGj5skRAGJu8d………………1PVfu0lY=
# PublicKey = VWe0wBVztgX………………xd7/kZ2CVJlEvS51c=

#Table必须有,不然默认的还是会修改ip rule
Table = 51820
#DNS = 1.1.1.1 #指定DNS服务器

#启动时运行: %i 是指wg的路由, 默认修改default, metric 一般不用指定
PostUp   = /sbin/ip -4 route replace default dev %i table default metric 1
PostUp   = /sbin/ip -6 route replace default dev %i table default metric 1
#down后运行
PostDown = /sbin/ip -4 route delete  default dev %i table default metric 1
PostDown = /sbin/ip -6 route delete  default dev %i table default metric 1

PostUp会产生下面的规则

root@snode6:/staff/shaojiemike# ip ro show table default
default dev wg0 scope link metric 1

OpenVPN原理

OpenVPN原理通过在main添加all规则来实现

# shaojiemike @ node5 in ~ [22:29:05]
$ ip route show table main
0.0.0.0/1 via 192.168.255.5 dev tun1

clash TUN模式

Macbook上的应用上的ClashX Pro的增强模式类似, 会添加如下配置,将基本所有流量代理(除开0.0.0.0/8

> ip route
1.0.0.0/8 via 198.18.0.1 dev utun3
2.0.0.0/7 via 198.18.0.1 dev utun3
4.0.0.0/6 via 198.18.0.1 dev utun3
8.0.0.0/5 via 198.18.0.1 dev utun3
16.0.0.0/4 via 198.18.0.1 dev utun3
32.0.0.0/3 via 198.18.0.1 dev utun3
64.0.0.0/2 via 198.18.0.1 dev utun3
128.0.0.0/1 via 198.18.0.1 dev utun3 #前面接受所有的ip,然后转换成198.18.0.1
198.18.0.1/32 via 198.18.0.1 dev utun3 #接受转换后的198.18.0.1,由于最长前缀匹配

明显有代理死循环问题,如何解决???

shaojiemike@shaojiemikedeMacBook-Air ~/github/hugoMinos (main*) [10:59:32]
> ip route get 198.18.0.42
198.18.0.42 via 198.18.0.1 dev utun3  src 198.18.0.1
shaojiemike@shaojiemikedeMacBook-Air ~/github/hugoMinos (main*) [10:59:38]
> ip route get 198.18.0.1
198.18.0.1 dev utun3  src 198.18.0.1

Wireguard 环境配置

wireguard-go: 安装客户端 wg-quick up config wireguard-tools: 安装服务端 wg

Wireguard 常见命令

  • 启动wg-quick up wg1
  • 关闭wg-quick down wg1
  • 查看状态 wg显示全部,或者wg show wg1显示wg1

wireguard开机启动

systemctl enable wg-quick@wg1 --now

使用wireguard 代理ipv6请求

  • WireGuard 也支持 IPv6。OpenWRT 服务端,当然要allowed ip fd00::aaaa:5/128
  • 注意:这是伪需求,为什么ipv6的流量需要走ipv6,不走wg,每个机器可以获得独立的公网ipv6,对于PT做种是很好的。
brainiac1# cat wg-tsj.conf
[Interface]
PrivateKey = xxx
ListenPort = 51828
Address = 10.0.233.7/32, fd00::aaaa:5/128
Table = 51820
#DNS = 1.1.1.1

# 使用iptable修改ipv6的路由规则
PostUp   = /sbin/ip -4 route replace default dev %i table default metric 1
PostUp   = /sbin/ip -6 route replace default dev %i table default metric 1
PostDown = /sbin/ip -4 route delete  default dev %i table default metric 1
PostDown = /sbin/ip -6 route delete  default dev %i table default metric 1

[Peer]
#AllowedIPs = 0.0.0.0/0,::/0
PublicKey = xxx
AllowedIPs = 0.0.0.0/1, 128.0.0.0/1
Endpoint = 4.shaojiemike.top:51822
PersistentKeepalive = 30

两次wireguard上网

修改sysctl.conf文件的net.ipv4.ip_forward参数。其值为0,说明禁止进行IP转发;如果是1,则说明IP转发功能已经打开。

需要执行指令sysctl -p 后新的配置才会生效。

两台机器的wireguard配置

注意中间需要NAT转换, 相当于把kunpeng机器的请求,隐藏成snode6的请求。在后一次wireguard转发时,就不会被过滤掉。

PostUp   = iptables -t nat -A POSTROUTING -s 10.1.0.0/24 ! -o %i -j MASQUERADE
PostDown = iptables -t nat -D POSTROUTING -s 10.1.0.0/24 ! -o %i -j MASQUERADE || true

机器(Nas)使用Wireguard上网

问题场景

由于换了wg服务端,导致nas变成闭环的网络了。最后是通过群晖助手(Synology Assistant / Web Assistant)的设置静态ip才连接上机器,但是iptable被设置乱了。

Synology Assistant can not find nas

静态连接上机器,首先在网页管理页面切换成DHCP(静态ip的DNS解析有误),iptable变成如下

sh-4.4# ip ro
default via 222.195.90.254 dev eth0  src 222.195.90.2
10.0.233.0/24 dev wg1  proto kernel  scope link  src 10.0.233.3
222.195.90.0/24 dev eth0  proto kernel  scope link  src 222.195.90.2

sh-4.4# ip ro s t eth0-table
222.195.90.0/24 via 222.195.90.2 dev eth0

注意iptable的修改是实时生效的。

思路

为了让nas上网我们需要满足两点

  1. 本地ssh eth0的222.195.90.2能访问机器(优先级更高)
  2. 其余网络走wg
# 重要项如下
sh-4.4# ip rule
3:      from 222.195.90.2 lookup eth0-table (ping  ssh ip 222.195.90.2的会使用这个规则)
32766:  from all lookup main (ping  ssh 其余ip 比如wg的10.0.233.3的会使用这个规则)

# 1. 设置本地ssh eth0的222.195.90.2的高优先级,不至于开启wg断开ssh
# 使用命令添加: ip ro add default via 222.195.90.254 dev eth0 table eth0-table
sh-4.4# ip route show table eth0-table
default via 222.195.90.254 dev eth0
222.195.90.0/24 via 222.195.90.2 dev eth0

# 2. 为了使得除开本地ssh网络走wg,需要删除屏蔽default的wg的DHCP(如果提前删,导致机器ssh连接不上了,重新插拔网线,让DHCP重新配置):
# 使用命令添加:ip ro d default via 222.195.90.254 dev eth0  src 222.195.90.2 table main,
# 3. 防止服务端重启,Nas的wg客户端失联
# 使用命令添加:ip ro a 114.214.233.0/24 via 222.195.90.254 dev eth0  src 222.195.90.2 table main 
# 4. 测试: ping域名能正常运行

# 其余方法:为了使得除开本地ssh网络走wg,也可以不删除,在DHCP的前面添加wg的网络通路
# 使用命令添加: ip ro add default dev wg1  proto kernel  scope link  src 10.0.233.3 table main
sh-4.4# ip r s t main
default dev wg1  proto kernel  scope link  src 10.0.233.3

使用wg1配置如下:

sh-4.4# cat /etc/wireguard/wg1.conf
[Interface]
PrivateKey = xxx
ListenPort = xxx
Address = 10.0.xxx.xxx/24

Table = 51820
PostUp   = /sbin/ip -4 route replace default dev %i table default metric 1
PostDown = /sbin/ip -4 route delete  default dev %i table default metric 1

[Peer]
PublicKey = xxx
AllowedIPs = 0.0.0.0/1, 128.0.0.0/1
Endpoint = 114.xxx.xxx.xxx:xxx
PersistentKeepalive = 25

问题:服务端重启,Nas的wg客户端失联

要保留没有wg的时候访问服务端的eth0(114.214.233.xxx)的通路

sh-4.4# ip ro s t main
···
114.214.233.0/24 via 222.195.90.254 dev eth0  src 222.195.90.2
···

来自eth0的ssh与ping请求原路返回

源地址为自身IP的包走学校的路由器

目的:需要ssh和ping ipv4成功

修改netplan的配置文件

# shaojiemike @ node5 in ~ [22:29:11]
$ cat /etc/netplan/acsa.yaml
network:
  version: 2
  renderer: networkd
  ethernets:
    eno0:
      dhcp4: false
      dhcp6: false
      accept-ra: false
      addresses:
        - 202.38.73.217/24
        - 2001:da8:d800:730::217/64
      gateway4: 202.38.73.254
      gateway6: 2001:da8:d800:730::1
      nameservers:
        addresses:
          - 202.38.64.1
      routing-policy:
        - from: 202.38.73.217
          table: 1
          priority: 2
      routes:
        - to: 0.0.0.0/0
          via: 202.38.73.254
          table: 1

$netplan apply

routing-policy会产生

# shaojiemike @ node5 in ~ [22:30:33]
$ ip rule
0:      from all lookup local
2:      from 202.38.73.217 lookup 1
32766:  from all lookup main
32767:  from all lookup default
# 也可以手动添加
ip rule add from 202.38.73.217 table 1 pref 2
或者
ip rule add from 202.38.73.217 lookup 1 pref 2

由于2优先级高,使得ping和ssh的返回信包(源地址为自身机器IP的包)走table1 规则,而不是走

routes使得所有的table1都会走学校的路由器(202.38.73.254)

$ ip route show table 1
default via 202.38.73.254 dev eno0 proto static
# 也可以通过`ip route add`
$ ip route add default via 202.38.73.254 dev eno0 proto static table 1

衍生问题:网络请求的源地址不是自己吗?怎么确定的

开启wg后,网络请求源地址变成了10.0.33.2。不是202.38.73.217

root@node5:/home/shaojiemike# ip ro
10.0.33.0/24 dev wg2 proto kernel scope link src 10.0.33.2

但是外界ping的是202.38.73.217。返回包交换所以会产生源地址为202.38.73.217的包

wireguard 实现翻墙

  • WireGuard 在国内网络环境下会遇到一个致命的问题:UDP 封锁/限速。虽然通过 WireGuard 可以在隧道内传输任何基于 IP 的协议(TCP、UDP、ICMP、SCTP、IPIP、GRE 等),但 WireGuard 隧道本身是通过 UDP 协议进行通信的,而国内运营商根本没有能力和精力根据 TCP 和 UDP 的不同去深度定制不同的 QoS 策略,几乎全部采取一刀切的手段:对 UDP 进行限速甚至封锁。
  • 虽然对 UDP 不友好,但却无力深度检测 TCP 连接的真实性。
  • 将 UDP 连接伪装成 TCP 连接不就蒙混过关了。目前支持将 UDP 流量伪装成 TCP 流量的主流工具是 udp2raw,但是有一款更强大的新工具: Phantun

需要进一步的研究学习

暂无

遇到的问题

暂无

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

参考文献

WireGuard 基础教程:使用 Phantun 将 WireGuard 的 UDP 流量伪装成 TCP

https://nordvpn.com/zh-tw/blog/vpn-xieyi/

https://blog.mozcp.com/wireguard-usage/

Assembly X86

关于X86 与 arm的寄存器的区别写在了arm那篇下

IDA analysis

word/ dword/ qword

In x86 terminology/documentation, a "word" is 16 bits

x86 word = 2 bytes

x86 dword = 4 bytes (double word)

x86 qword = 8 bytes (quad word)

x86 double-quad or xmmword = 16 bytes, e.g. movdqa xmm0, [rdi].

常见X86汇编

https://en.wikipedia.org/wiki/X86_instruction_listings

https://www.felixcloutier.com/x86/

https://officedaytime.com/simd512e/

官方手册第一个4800页

SHR     # Shift right (unsigned shift right)
SAL       # Shift Arithmetically left (signed shift left)
lea       # Load Effective Address, like mov but not change Flags, can store in any register, three opts
imul      # Signed multiply
movslq    # Move doubleword to quadword with sign-extension.
movl $0x46dd0bfe, 0x804a1dc #将数值0x46dd0bfe放入0x804a1dc的地址中
movl 0x46dd0bfe, 0x804a1dc #将0x46dd0bfe地址里的内容放入0x804a1dc地址中

lea & leaq

lea    -0xc(%ebp),%eax
mov    %eax,0x8(%esp) #常见于scanf第三个参数,lea传结果写入地址
// x is %rdi, result is %rax 就是计算地址,没有寻址操作
lea    0x0(,%rdi,8),%rax //result = x * 8;
lea    0x4b(,%rdi),%rax //result = x + 0x4b;

call & ret

  • Call 地址:返回地址入栈(等价于“Push %eip,mov 地址,%eip”;注意eip指向下一条尚未执行的指令)
  • ret:从栈中弹出地址,并跳到那个地址(pop %eip

leave

leave:使栈做好返回准备,等价于

mov %ebp,%esp
pop %ebp

compare order

cmpl   $0x5,$0x1
jle    8048bc5 # Jump if Less or Equal 会触发,前面的 1<=5

X86 load store

X86 不像 ARM有专门的ldrstr指令。是通过mov实现的

movswl (%rdi), %eax sign-extending load from word (w) to dword (l). Intel movsx eax, word [rdi]

AVX

https://docs.oracle.com/cd/E36784_01/html/E36859/gntbd.html

vxorpd   XORPD
Bitwise Logical XOR for Double-Precision Floating-Point Values

vxorps   XORPS
Bitwise Logical XOR for Single-Precision Floating-Point Values

vmovaps  MOVAPS
Move Aligned Packed Single-Precision Floating-Point Values

test & jump

test    al, al
jne     0x1000bffcc

The test instruction performs a logical and of the two operands and sets the CPU flags register according to the result (which is not stored anywhere). If al is zero, the anded result is zero and that sets the Z flag. If al is nonzero, it clears the Z flag. (Other flags, such as Carry, oVerflow, Sign, Parity, etc. are affected too, but this code has no instruction testing them.)

The jne instruction alters EIP if the Z flag is not set. There is another mnemonic for the same operation called jnz.

test   %eax,%eax
jg     <phase_4+0x35> # eax & eax > 0 jump

注意 cmp不等于 test

The TEST operation sets the flags CF and OF to zero.

The SF is set to the MSB(most significant bit) of the result of the AND.

If the result of the AND is 0, the ZF is set to 1, otherwise set to 0.

kinds of jump

AT&T syntax jmpq *0x402390(,%rax,8) into INTEL-syntax: jmp [RAX*8 + 0x402390].

ja VS jg

JUMP IF ABOVE AND JUMP IF GREATER

ja jumps if CF = 0 and ZF = 0 (unsigned Above: no carry and not equal)

jg jumps if SF = OF and ZF = 0 (signed Greater, excluding equal)

FLAGS

cmp performs a sub (but does not keep the result).

cmp eax, ebx

Let's do the same by hand:

 reg     hex value   binary value  

 eax = 0xdeadc0de    ‭11011110101011011100000011011110‬
 ebx = 0x1337ca5e    ‭00010011001101111100101001011110‬
  -    ----------
 res   0xCB75F680    11001011011101011111011010000000 

The flags are set as follows:

OF (overflow) : did bit 31 change      -> no
SF (sign)     : is bit 31 set          -> yes
CF (carry)    : is abs(ebx) < abs(eax) -> no  
ZF (zero)     : is result zero         -> no
PF (parity)   : is parity of LSB even  -> no (archaic)
AF (Adjust)   : overflow in bits 0123  -> archaic, for BCD only.

Carry Flag

Carry Flag is a flag set when:

a) two unsigned numbers were added and the result is larger than "capacity" of register where it is saved.

Ex: we wanna add two 8 bit numbers and save result in 8 bit register. In your example: 255 + 9 = 264 which is more that 8 bit register can store. So the value "8" will be saved there (264 & 255 = 8) and CF flag will be set.

b) two unsigned numbers were subtracted and we subtracted the bigger one from the smaller one.

Ex: 1-2 will give you 255 in result and CF flag will be set.

Auxiliary Flag is used as CF but when working with BCD. So AF will be set when we have overflow or underflow on in BCD calculations. For example: considering 8 bit ALU unit, Auxiliary flag is set when there is carry from 3rd bit to 4th bit i.e. carry from lower nibble to higher nibble. (Wiki link)

Overflow Flag is used as CF but when we work on signed numbers.

Ex we wanna add two 8 bit signed numbers: 127 + 2. the result is 129 but it is too much for 8bit signed number, so OF will be set.

Similar when the result is too small like -128 - 1 = -129 which is out of scope for 8 bit signed numbers.

register signed & unsigned

Positive or negative The CPU does not know (or care) whether a number is positive or negative. The only person who knows is you. If you test SF and OF, then you treat the number as signed. If you only test CF then you treat the number as unsigned. In order to help you the processor keeps track of all flags at once. You decide which flags to test and by doing so, you decide how to interpret the numbers.

register multiply

The computer makes use of binary multiplication(AND), followed by bit shift (in the direction in which the multiplication proceeds), followed by binary addition(OR).

1100100
0110111
=======
0000000
-1100100
--1100100
---0000000
----1100100
-----1100100
------1100100
==============
1010101111100

100 = 1.1001 * 2^6
55  = 1.10111* 2^5
100 * 55 -> 1.1001 * 1.10111 * 2^(6+5)

for more:

How computer multiplies 2 numbers? And: Binary multiplier - Wikipedia

Memory and Addressing Modes

声明静态代码区域

DB, DW, and DD can be used to declare one, two, and four byte data locations,

# 基本例子
.DATA       
var DB 64   ; Declare a byte, referred to as location var, containing the value 64.
var2    DB ?    ; Declare an uninitialized byte, referred to as location var2.
DB 10   ; Declare a byte with no label, containing the value 10. Its location is var2 + 1.
X   DW ?    ; Declare a 2-byte uninitialized value, referred to as location X.
Y   DD 30000        ; Declare a 4-byte value, referred to as location Y, initialized to 30000.

数组的声明,The DUP directive tells the assembler to duplicate an expression a given number of times. For example, 4 DUP(2) is equivalent to 2, 2, 2, 2.

Z   DD 1, 2, 3  ; Declare three 4-byte values, initialized to 1, 2, and 3. The value of location Z + 8 will be 3.
bytes   DB 10 DUP(?)    ; Declare 10 uninitialized bytes starting at location bytes.
arr DD 100 DUP(0)       ; Declare 100 4-byte words starting at location arr, all initialized to 0
str DB 'hello',0    ; Declare 6 bytes starting at the address str, initialized to the ASCII character values for hello and the null (0) byte.

寻址

32位X86机器寻址支持

  1. 最多支持32位寄存器和32位有符号常数相加
  2. 其中一个寄存器可以再乘上 2,4,8
# right
mov eax, [ebx]  ; Move the 4 bytes in memory at the address contained in EBX into EAX
mov [var], ebx  ; Move the contents of EBX into the 4 bytes at memory address var. (Note, var is a 32-bit constant).
mov eax, [esi-4]    ; Move 4 bytes at memory address ESI + (-4) into EAX
mov [esi+eax], cl   ; Move the contents of CL into the byte at address ESI+EAX
mov edx, [esi+4*ebx]        ; Move the 4 bytes of data at address ESI+4*EBX into EDX

# wrong and reason
mov eax, [ebx-ecx]  ; Can only add register values
mov [eax+esi+edi], ebx      ; At most 2 registers in address computation

指定存储在地址的数据大小

mov BYTE PTR [ebx], 2   ; Move 2 into the single byte at the address stored in EBX.
mov WORD PTR [ebx], 2   ; Move the 16-bit integer representation of 2 into the 2 bytes starting at the address in EBX.
mov DWORD PTR [ebx], 2      ; Move the 32-bit integer representation of 2 into the 4 bytes starting at the address in EBX.

汇编寄存器顺序,作用方向

这和汇编器语法有关:

X86 instructions

For instructions with two operands, the first (lefthand) operand is the source operand, and the second (righthand) operand is the destination operand (that is, source->destination).

mov eax, ebx — copy the value in ebx into eax
add eax, 10 — EAX ← EAX + 10

AT&T syntax

AT&T Syntax is an assembly syntax used in UNIX environments, that originates from AT&T Bell Labs. It is descended from the MIPS assembly syntax. (AT&T, American Telephone & Telegraph)

AT&T Syntax is an assembly syntax used mostly in UNIX environments or by tools like gcc that originated in that environment.

语法特点:https://stackoverflow.com/tags/att/info

需要注意的:

  1. Operands are in destination-last order
  2. Register names are prefixed with %, and immediates are prefixed with $
  3. sub $24, %rsp reserves 24 bytes on the stack.
  4. Operand-size is indicated with a b/w/l/q suffix on the mnemonic
  5. addb $1, byte_table(%rdi) increment a byte in a static table.
  6. The mov suffix (b, w, l, or q) indicates how many bytes are being copied (1, 2, 4, or 8 respectively)
  7. imul $13, 16(%rdi, %rcx, 4), %eax 32-bit load from rdi + rcx<<2 + 16, multiply that by 13, put the result in %eax. Intel imul eax, [16 + rdi + rcx*4], 13.
  8. movswl (%rdi), %eax sign-extending load from word (w) to dword (l). Intel movsx eax, word [rdi].

Intel syntax (used in Intel/AMD manuals).

The Intel assembler(icc,icpc我猜) uses the opposite order (destination<-source) for operands.

语法特点: https://stackoverflow.com/tags/intel-syntax/info

RISC-V

beq rs1, rs2, Label #RISC-V
SW rs2, imm(rs1)  # Mem[rs1+imm]=rs2 ,汇编将访存放在最后
add rd, rs1, rs2  # rd = rs1 + rs2

反汇编器

但是这个语法不是很重要,因为decompiler有选项控制语法

objdump has -Mintel flag, gdb has set disassembly-flavor intel option.

gcc -masm=intel -S or objdump -drwC -Mintel.

需要进一步的研究学习

暂无

遇到的问题

暂无

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

参考文献

https://www.cs.virginia.edu/~evans/cs216/guides/x86.html

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%的置信区间会包含真实参数值。

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

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

方差回归与回归分析

需要进一步的研究学习

暂无

遇到的问题

暂无

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

参考文献

Lock & Synchronization

导言

  • 在PTA开发时,其中的多线程加速经常要用锁来隔离资源和逻辑。

互斥与同步

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

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

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

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

常见问题

共享内存加锁之后释放锁,别的进程是如何知道锁释放的

  1. 常用的方法是在共享内存中设置标志位或信号量等,并在共享内存中保证这个标志位或信号量只有在锁被释放时才会被更新。这样,其它进程可以通过轮询或者等待通知的方式来获取锁并开始修改共享内存,从而避免冲突。在共享内存中设置的标志位或信号量通常需要原子操作的支持,以确保并发修改时的正确性。
    1. 轮询:轮询是指线程反复检查某个条件是否成立,直到条件成立为止。在锁机制中,当一个线程持有锁时,其他线程会不断地轮询锁的状态,直到该锁被释放。这种方式的优点是实现简单,不需要额外的通知机制,缺点是占用CPU资源,效率较低。
    2. 等待通知:等待通知是指线程在某个条件不满足时挂起等待,当条件满足时由其他线程通知它继续执行。在锁机制中,当一个线程持有锁时,其他线程会进入等待状态,直到该锁被释放,此时其他线程会被通知并继续执行。这种方式的优点是占用CPU资源少,效率高,缺点是实现稍微复杂一些,需要额外的通知机制。
  2. 另外,也可以使用一个中央锁服务器或者等待队列来管理锁,当一个进程获取锁时,会向中央锁服务器或等待队列发出请求,直到锁被成功获取,并在共享内存中记录锁的状态。当锁被释放时,中央锁服务器或等待队列会通知其它进程,并让其它进程开始自由修改共享内存。

如何保证操作的原子性

  1. 操作系统提供的原子操作:一些操作系统会提供线程安全的原子操作接口,如Compare-And-Swap(CAS)等,它们能够确保指令的原子性,从而保证线程安全。
  2. 事务:事务是指一组操作被视为一个不可分割的操作序列,要么全部执行成功,要么全部失败,具有原子性和一致性保证。常用于数据库操作等场景。
  3. 锁机制:锁机制是一种常用的多线程同步机制,能够确保同一时刻只有一个线程(或进程)可以访问共享资源,从而保证原子性。

如何避免死锁

  1. 避免使用多把锁并且同时持有多个锁。当需要持有多个锁时,可以通过加锁的顺序来避免死锁。如果所有可能的锁按照固定的顺序加锁,那么可以避免死锁。
  2. 设置请求超时时间。当一个进程请求锁时,如果在超时时间内没有获得锁,可以释放之前持有的锁,并尝试重新获取。这样可以避免某一个进程一直持有锁而导致死锁。
  3. 引入随机性。在获取锁的时候加入一些随机因素,让不同的程序在不同的时间获取锁。这样可以防止程序之间在自己的重试过程中的饥饿状态导致的死锁。

悲观锁

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

乐观锁

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

原子操作

Test-and-SetCompare-and-Swap (CAS) 都是并发编程中的重要原子操作指令,通常用于同步和处理多线程或多进程环境中的竞争条件。它们的作用是确保某些操作在执行时不会被中断,以保持数据一致性和避免并发冲突。我们来详细了解这两个命令。

1. Test-and-Set (TAS) 指令

  • 通常用于控制锁定状态,通过设置标志位来获取锁,它返回原始值(通常是锁状态),用于判断锁是否已经被占用。
  • 它通常用于实现自旋锁、互斥锁(mutex)或锁标志位。

它的操作过程如下:

  • Test: 检查指定位置(通常是一个布尔标志位或整数)当前的值。
  • Set: 将这个位置的值设置为 1 或 "true"。

操作是原子的,即不会被中断或干扰,保证在并发环境下,多个线程或进程不能同时修改同一位置。

用途:

  • 实现自旋锁(Spinlock):线程反复检查一个共享变量,如果该变量表示未被锁定,线程会尝试获得锁。
  • 防止竞争条件:确保在并发操作时,只有一个线程能够设置锁标志,其他线程需要等待。
示例

假设有一个共享的锁标志 lock,初始化为 false

lock = false;

while (Test_and_Set(lock)) {
    // 如果 lock 已经被设置为 true,则继续自旋等待
}
// lock 成功设置为 true,获取锁

2. Compare-and-Swap (CAS) 指令

  • 通常用于无锁编程,它通过比较期望值与当前值来决定是否进行更新(检查指定的内存位置的值是否等于一个预期的值,如果相等,则将该位置的值替换为新的值),适用于复杂的数据结构操作。
  • 常用于无锁数据结构和其他更高效的并发操作。

它的操作步骤如下:

  • Compare: 比较目标内存位置的当前值是否与预期值相等。
  • Swap: 如果当前值等于预期值,就将目标位置的值替换为新的值。如果不相等,则什么也不做。

CAS 也具有原子性,这意味着它在操作期间不会被中断。CAS 是实现无锁编程和避免线程同步问题的常用工具,尤其在需要高性能的并发程序中。

用途:

  • 实现无锁数据结构(如无锁队列、栈、哈希表等)。
  • 实现线程安全的计数器或标志位操作。
  • 用于一些算法(如版本控制或并发计数器)中,确保多个线程不冲突地更新共享数据。
示例:

假设有一个变量 x,初始值为 10:

int expected = 10;
int new_value = 20;

if (Compare_and_Swap(&x, expected, new_value)) {
    // 如果 x 的值为 expected (10),就将 x 更新为 new_value (20)
} else {
    // 如果 x 的值不为 expected,CAS 操作失败
}

3. TAS的汇编实现

  • Test-and-Set (TAS) 操作通常可以通过 XCHG 指令(交换)在 x86 汇编中实现。虽然 x86 没有直接的 Test-and-Set 指令,XCHG 被用作实现类似功能的原子操作。
例如,在 x86 中:
; x86 示例,使用 XCHG 实现 Test-and-Set
; 假设锁变量位于 memory_location
; eax 是存储旧值的寄存器
mov eax, 0          ; eax 设为 0,表示“未锁定”
xchg eax, [lock]    ; 将 eax 与锁变量交换,如果锁变量是 0,就设置为 1
                    ; 如果返回的 eax 仍为 0,说明锁成功设置

这个操作会交换 eax[lock] 位置的值,并将原值存储在 eax 中。如果 [lock] 最初是 0eax 将变为 1,并且 lock 会被设置为 1,表示锁已经被占用。

虽然 Test-and-Set 并不一定直接映射到汇编中的特定指令,但它可以通过交换指令来模拟。

4. CAS的汇编实现

  • Compare-and-Swap (CAS) 指令在 x86 中有专门的 CMPXCHG 指令,ARM 等其他架构也有类似的原子操作指令(如 LDREXSTREX)。
例如,在 x86 中:

x86 提供了 CMPXCHG(比较和交换)指令,它就是 CAS 操作的硬件实现。其语法如下:

CMPXCHG destination, source
  • destination:是要比较的内存位置。
  • source:是用于替换的值。
  • 如果 destination 中的值与 source 中的值相等,destination 将被更新为 source 的值,且 AX 寄存器的值将保存 destination 原先的值。
  • 如果不相等,destination 的值保持不变,并且 AX 寄存器将保存 destination 的原值。
; x86 示例,使用 CMPXCHG 实现 Compare-and-Swap
; 假设目标内存位置是 lock,期望值是 eax,新的值是 ebx

mov eax, expected_value    ; 将期望的值加载到 eax
mov ebx, new_value        ; 将新的值加载到 ebx
cmpxchg [lock], ebx        ; 比较 [lock] 的值与 eax(期望值),如果相等则将 [lock] 更新为 ebx(新值)
                        ; 如果不相等,eax 会保存 [lock] 的原值

这个 CMPXCHG 指令会首先将内存中的值与 eax 比较,如果两者相等,它会将 ebx 的值存储到内存中,并且 eax 会保存原来的值;如果两者不相等,内存中的值不会改变,而 eax 会保存当前内存值,指示操作失败。

在 ARM 架构中:

ARM 也提供了类似的原子操作指令,称为 LDREXSTREXLDREX 加载一个值并锁定它,STREX 则用于条件性地写回值。

; ARM 示例,使用 LDREX 和 STREX 实现 CAS
LDREX R0, [lock]    ; 加载锁的当前值到 R0
CMP R0, R1           ; 比较 R0(当前锁的值)与 R1(期望值)
BNE CAS_FAIL         ; 如果不相等,跳转到失败处理
STREX R2, R3, [lock] ; 如果相等,将 R3(新值)写入 [lock],并将成功标志存储在 R2

atomic 封装

std::atomic 是对 Test-and-SetCompare-and-Swap 等底层原子操作的高级封装,使得 C++ 开发者可以在多线程环境中更方便、更安全地使用这些原子操作。

原子操作(std::atomic)有如下特点:

  • 线程安全:原子操作保证了即使在多线程环境下也能正确地修改和读取共享变量。
  • 高效:没有加锁开销,适用于需要频繁检查和修改标志的场景。
  • 原子操作的限制std::atomic 只能用于一些简单的类型(如整数、指针和布尔类型),对于复杂的数据结构,仍然需要其他同步机制(如锁)。

示例:使用 std::atomic<bool> 控制初始化

在控制初始化只执行一次的场景中,你可以使用 std::atomic<bool> 来替代普通的 bool 类型,这样就能确保线程安全地检查和设置初始化标志。

#include <atomic>

std::atomic<bool> isInited(false);

void initFunction() {
    // 原子操作,检查并更新 isInited
    if (!isInited.exchange(true)) { // mutex  std::call_once 和std::once_flag 也可以实现类似功能。
        // 执行初始化逻辑
        // ...
    }
}
  1. std::atomic<bool> isInited(false);:声明一个原子类型的 bool 变量,初始值为 false
  2. isInited.exchange(true):调用 exchange 方法,该方法会将 isInited 的当前值返回,并将其更新为 true。如果当前值为 false,说明还没有初始化,此时会执行初始化逻辑。
  3. 如果 isInited 已经是 true,则 exchange 会返回 true,跳过初始化部分。

避免直接读取 std::atomic 对象, 使用load store

std::atomic<int> counter(0);
counter = 5;  // 这种赋值操作不是原子操作,可能导致线程不安全。
int value = counter;  // 直接读取可能没有同步, 导致缓存不一致问题,多个线程读取的值不一定是最新的。

原子操作是不会失败的

  • load、store 和 exchange 都不会失败,它们保证原子操作的顺序性和正确性。
  • compare_exchange_strong 和 compare_exchange_weak 是可能会“失败”的操作,它们只有在预期值和原子变量的值一致时才会成功执行,否则会返回 false,并更新预期值。

内存顺序:std::memory_order

对于一个线程里的同一个代码块内的无依赖关系的指令,处理器在运行时会重排序乱序执行。这对原子指令也是一样的。但实际生产中,多个原子操作之间,可能会有依赖关系,比如一个线程读取另一个线程写入的数据。为了确保这些依赖关系的正确性,需要使用内存顺序来控制处理器对指令的重排序。

std::atomic 的操作支持指定内存顺序,这控制了编译器和硬件对操作的优化和重排序。常见的内存顺序选项有:

  • std::memory_order_relaxed:没有限制,运行时会乱序。
  • std::memory_order_acquirestd::memory_order_release:分别用于“获取”和“释放”同步,确保操作顺序。
    • std::memory_order_acquire:保证在此操作之前的所有操作不会被重排序到它之后。
    • std::memory_order_release:保证在此操作之后的所有操作不会被重排序到它之前。
  • std::memory_order_seq_cst默认的内存顺序,保证在多线程程序中,所有原子操作按顺序执行,不允许重排序。但性能可能会略受影响。
memory_order_acquire

这两者提供了获取和释放同步的保证:

  • std::memory_order_acquire:保证在此操作之前的所有操作不会被重排序到它之后。
  • std::memory_order_release:保证在此操作之后的所有操作不会被重排序到它之前。
#include <atomic>
#include <iostream>
#include <thread>

std::atomic<int> counter(0);
std::atomic<bool> ready(false);

void producer() {
    counter.store(42, std::memory_order_release);  // 确保 counter 写入在 ready 之前
    ready.store(true, std::memory_order_release);  // 标记准备好
}

void consumer() {
    while (!ready.load(std::memory_order_acquire)) {}  // 等待 ready 为 true
    std::cout << "Counter: " << counter.load(std::memory_order_acquire) << std::endl;
}

int main() {
    std::thread t1(producer);
    std::thread t2(consumer);

    t1.join();
    t2.join();

    return 0;
}

解释

  • consumer 线程在 ready.load(std::memory_order_acquire) 后才能读取 counter,确保 ready 被设置为 true 后,counter 的写入才是可见的。
  • memory_order_release 确保 producer 线程的 counter 写操作不会被重排序到 ready.store 之前。
  • memory_order_acquire 确保 consumer 在读取 ready 后,才能正确地读取到 counter 的值。

1. 直接赋值:store

在原子操作中,store 用来将一个值存储到原子变量中。与普通赋值不同,store 会确保在多线程环境下,赋值操作是原子性的(即不会被打断)。

std::atomic<int> counter(0);
counter.store(5, std::memory_order_relaxed);  // 存储 5
- store 会保证在指定的内存顺序下将值存储到原子变量中,因此它是线程安全的。

2. 加载:load

load 用于从原子变量中读取值。它会确保在多线程环境中,读取操作是线程安全的,并且可以指定内存顺序。

int value = counter.load(std::memory_order_acquire);  // 从原子变量读取
  • load 会确保读取的是正确同步后的值,避免在多线程场景下出现读取错误。

3. 比较并交换:compare_exchange_strong

  • compare_exchange_strong(以及 compare_exchange_weak)广泛应用于实现锁和无锁算法。它会尝试将原子变量的值与一个预期值进行比较,如果相同,则将其更新为新值。如果比较失败,原子变量的值不会更改,并且返回 false
compare_exchange_strong 与compare_exchange_weak 的区别
  • compare_exchange_strong 是标准的、严格的 Compare-and-Swap 操作,失败时立即返回,并不会自动重试。
  • compare_exchange_weak 是一种可能会在某些实现中自动重试的版本,适用于高并发场景,特别是在竞争激烈时可以减少操作的开销。
  • 虽然它们有细微的区别,但两者的核心作用是相同的:原子地比较并更新共享变量。在选择使用哪种方法时,主要取决于你对性能的要求以及是否需要在失败时进行重试。
std::atomic<int> value(0);
int expected = 0;
int desired = 42;

if (value.compare_exchange_strong(expected, desired)) {
    std::cout << "CAS succeeded! Value updated to " << value.load() << "\n";
} else {
    std::cout << "CAS failed! Expected: " << expected << ", Actual: " << value.load() << "\n";
}

// 尝试比较并交换
while (!value.compare_exchange_weak(expected, desired)) {
    std::cout << "CAS failed, retrying...\n";
    // 可以执行一些其他的操作或稍微延迟再重试
}
std::cout << "CAS succeeded! Value updated to " << value.load() << "\n";

4. exchange

exchange 是一种常见的原子操作,类似于 store,但它会返回原子变量的先前值。

int oldValue = counter.exchange(5);  // 返回更新前的值,并将 counter 设置为 5
  • exchange 在多线程环境下是安全的,并且可以返回修改前的值,适用于某些需要获取旧值的场景。

常见锁的优缺点和实现

自旋锁(spinlock)

多线程同步的一种忙等待锁,线程反复检查锁变量是否可用。

  • 优点:避免了操作系统进程调度和线程切换,所以自旋锁通常适用在时间比较短的情况下。由于这个原因,操作系统的内核经常使用自旋锁。
  • 缺点:如果长时间上锁的话,自旋锁会非常耗费性能,它阻止了其他线程的运行和调度
    • 线程持有锁的时间越长,则持有该锁的线程将被 OS(Operating System) 调度程序中断的风险越大。
  • 解决办法:
    • TicketLock 是采用排队叫号的机制。
    • CLHLock和MCSLock通过链表的方式避免了减少了处理器缓存同步,极大的提高了性能,区别在于CLHLock是通过轮询其前驱节点的状态,而MCS则是查看当前节点的锁状态。
std::atomic_flag lock = ATOMIC_FLAG_INIT;

void spinlock() {
    while (lock.test_and_set(std::memory_order_acquire)) {
        // 自旋等待,直到锁被释放
    }
    // 临界区代码
    lock.clear(std::memory_order_release);  // 解锁
}

互斥锁(mutex)

把自己阻塞起来(内核态和用户态之间的切换进入阻塞状态,可能上下文切换),等待重新调度请求。

  • 互斥锁的实现
    1. 软件实现:软件互斥锁需要借助操作系统提供的原子操作(如Compare-And-Swap,CAS)来实现 优点是灵活性高 缺点是性能较低,
    2. CAS操作需要三个参数,内存地址A,期望值V,新值N。执行过程如下:
      • 读取内存地址A的原始值,保存在临时变量Value中
      • 比较Value和期待值V是否相等,如果相等则将内存地址A的值更新为新值N
      • 如果内存地址A的值已经被其他线程改变,则不进行更新操作
  • TAS(test and set)
    • 一个TAS指令包括两个子步骤,把给定的内存地址设置为1,然后返回之前的旧值。
    • 硬件实现:硬件互斥锁使用计算机硬件提供的特殊指令(如锁总线指令)来实现。当线程要获取锁时,它会发出一个锁总线指令,这个指令会占用系统总线,使得其他CPU无法读写内存。
      1. 当lock前缀指令执行时,它将锁定处理器总线,确保其他处理器无法同时访问同一内存区域,
代码实例:lock_guard

std::lock_guard<std::mutex> 是 C++ 标准库中的一个 RAII(Resource Acquisition Is Initialization)类,它用于在作用域内自动锁住一个 std::mutex,并在作用域结束时自动解锁。它可以帮助你避免手动管理锁,减少死锁和忘记解锁的风险。

用法

std::lock_guard 通过构造时自动锁住互斥量,并且在作用域结束时自动释放互斥量的锁。因此,你不需要手动调用 mutex.unlock()。只需要确保 lock_guard 的生命周期结束时,互斥量会被自动解锁。

示例代码

#include <iostream>
#include <mutex>
#include <thread>

std::mutex init_mutex_;  // 互斥量,防止多个线程同时初始化

void some_function() {
    // 创建一个 lock_guard 对象,自动锁住 init_mutex_
    std::lock_guard<std::mutex> lock(init_mutex_);

    // 在此作用域内,init_mutex_ 被锁定
    std::cout << "Doing some work inside the critical section...\n";

    // lock_guard 在作用域结束时会自动解锁 mutex
}

int main() {
    std::thread t1(some_function);
    std::thread t2(some_function);

    t1.join();
    t2.join();

    return 0;
}

解释

  1. std::lock_guard<std::mutex> lock(init_mutex_);
  2. 在这行代码中,lock_guard 对象被创建,并立即锁住 init_mutex_
  3. std::lock_guard 的构造函数会调用 mutex.lock() 来锁定互斥量。
  4. lock 变量在作用域结束时自动销毁,这会触发析构函数 lock_guard::~lock_guard(),并自动解锁互斥量(即调用 mutex.unlock())。

  5. some_function 中,互斥量在整个函数内都是被锁定的,因此其他线程无法进入这段代码,避免了并发冲突。

为什么使用 std::lock_guard

  • 避免死锁std::lock_guard 会自动解锁互斥量,减少了忘记解锁的风险。
  • 简洁易懂:它为你管理锁,减少了显式的锁管理代码,使代码更简洁。
  • 线程安全:当多个线程访问同一资源时,std::lock_guard 可以确保每次只有一个线程能够访问临界区,防止数据竞争。

适用场景

通常用于在函数、代码块中保护共享资源。它适合需要访问互斥量的代码块,但不想手动管理锁和解锁时。

代码实例:cv.wait 实现多线程的先后顺序
  1. 使用 std::thread 和 std::mutex + std::condition_variable

如果你希望在销毁环境的 Final 函数中等待某些子线程完成,可以使用 std::mutex 和 std::condition_variable 来同步子线程的完成状态。

示例代码: 假设你有一个主线程(执行 Final 函数)和一个子线程,主线程需要等待子线程完成后才能销毁环境。

#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <atomic>

std::mutex mtx;
std::condition_variable cv;
std::atomic<bool> thread_done{false};

void worker_thread() {
    std::this_thread::sleep_for(std::chrono::seconds(2)); // 模拟工作
    std::cout << "Worker thread finished." << std::endl;
    thread_done = true;  // 设置线程完成标志
    cv.notify_one();     // 通知主线程
}

void Final() {
    std::cout << "Final: Waiting for worker thread to finish..." << std::endl;

    // 等待子线程完成
    std::unique_lock<std::mutex> lock(mtx);
    cv.wait(lock, [] { return thread_done.load(); });
    // cv.wait(lock, [this] { return thread_done.load(); }); // in class

    std::cout << "Final: Worker thread finished. Proceeding with cleanup." << std::endl;
}

int main() {
    // 启动子线程
    std::thread t(worker_thread);

    // 在主线程中调用 Final
    Final();

    t.join();  // 等待子线程结束

    return 0;
}

关键点:

  • std::mutex mtx: 用于锁住条件变量,确保线程间的同步。
  • std::condition_variable cv: 用于实现主线程等待子线程的完成。
  • std::atomic<bool> thread_done: 用于标记子线程是否完成。
  • cv.wait(lock, condition): 主线程会等待子线程设置 thread_done 为 true,然后才会继续执行。

读写锁(ReadWrite Lock)

  • 在读操作和写操作之间提供了更细粒度的同步控制。
  • 多个线程可以同时获取读锁,但只有一个线程能够获取写锁。
    • 读写锁有三种状态:读加锁状态、写加锁状态和不加锁状态
    • 规则
    • 当读写锁在写加锁模式下,任何试图对这个锁进行加锁的线程都会被阻塞,直到写进程对其解锁。
    • 当读写锁在读加锁模式先,任何线程都可以对其进行读加锁操作,但是所有试图进行写加锁操作的线程都会被阻塞,直到所有的读线程都解锁。
  • 缺点:当读者源源不断到来的时候,写者总是得不到读写锁,就会造成不公平的状态。
    • 避免方法: 当处于读模式的读写锁接收到一个试图对其进行写模式加锁操作时,便会阻塞后面对其进行读模式加锁操作的线程。这样等到已经加读模式的锁解锁后,写进程能够访问此锁保护的资源。
  • 优点:
    • 读写锁可以提高并发性,允许多个线程同时读取数据,而只有在需要修改数据时才会互斥。
    • 适合对数据结构读的次数远远大于写的情况。

RCU(Read-Copy-Update)

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

通知与同步

适用于大段的修改和同步。

eventfd 事件通知

eventfd 是 Linux 提供的一种用于线程安全的事件通知机制,类似于文件描述符,可以通过读写操作来实现跨线程或跨进程的同步。通过 eventfd,线程或进程可以通过某些事件(例如计数器增减、通知等)来触发其他线程或进程的动作。

eventfd 可以通过两种方式工作:

  • 计数器模式:通过 eventfd_write 增加计数器,其他线程或进程可以通过 eventfd_read 来读取这些计数器的值。
  • 通知模式:使用 eventfd 进行事件通知,线程或进程通过 eventfd_read 来等待并响应这些事件。

eventfd_read 的功能 : eventfd_read 是一个用于从 eventfd 文件描述符读取事件的系统调用。它会从 eventfd 中读取一个 64 位无符号整数,并返回这个值。这个值通常表示某个事件的状态或计数器的值。

线程间同步

如果两个线程同时对同一个 eventfd 文件描述符进行读写操作:

  • eventfd_read 会阻塞直到 eventfd 中有事件(即计数器的值大于 0),并且在读取之后会减少计数器。
  • eventfd_write 会增加计数器的值,并通知正在等待的线程。

函数原型

#include <sys/eventfd.h>

ssize_t eventfd_read(int efd, uint64_t *value);
ssize_t eventfd_write(int efd, uint64_t value);
  • efdeventfd 文件描述符。
  • * value:指向一个 uint64_t 类型的变量,用于存储从 eventfd 读取的值。
  • value:要写入 eventfd 的值,通常是一个 64 位无符号整数 (uint64_t),表示事件计数器的增加量或特定事件的通知值。

返回值

  • 如果成功,eventfd_read 返回读取到的字节数,通常为 8(因为它读取一个 64 位的值)。
  • 如果失败,返回 -1,并将 errno 设置为合适的错误码。

错误码

  • EAGAINeventfd 中没有事件可读(即没有数据)。
  • EBADF:无效的文件描述符。
  • 其他常见的文件描述符错误。

代码示例

假设你使用 eventfd 来同步不同的线程:

#include <sys/eventfd.h>
#include <unistd.h>
#include <iostream>
#include <cstring>

int main() {
    // 创建 eventfd 文件描述符
    int efd = eventfd(0, EFD_NONBLOCK);
    if (efd == -1) {
        std::cerr << "Failed to create eventfd: " << strerror(errno) << std::endl;
        return -1;
    }

    // 写入事件
    uint64_t u = 1; // 写入一个事件值
    ssize_t s = write(efd, &u, sizeof(u));
    if (s == -1) {
        std::cerr << "Failed to write to eventfd: " << strerror(errno) << std::endl;
        close(efd);
        return -1;
    }

    // 读取事件
    uint64_t read_value;
    s = eventfd_read(efd, &read_value);
    if (s == -1) {
        std::cerr << "Failed to read from eventfd: " << strerror(errno) << std::endl;
    } else {
        std::cout << "Read value: " << read_value << std::endl;
    }

    close(efd);
    return 0;
}

概念题

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间的数据访问同步?

参考文献

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. 每次的估计值会波动吗?

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

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

参考文献