跳转至

笔记

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

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

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

方差回归与回归分析

需要进一步的研究学习

暂无

遇到的问题

暂无

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

参考文献

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

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

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

参考文献