inclyc

echo 'compiler' | tee OS

收集一些不错的偷懒指令

回到 git 根目录:

1
cd `git rev-parse --show-toplevel`

开一个临时目录,cd 过去

1
cd `mktemp -d`

cd 到刚刚创建的目录

1
cd $_

推送当前分支

1
git push -u github `git branch --show-current`

并行化的需求

Moore 定律的终结

集成电路上可容纳的晶体管数目,约每隔两年便会增加一倍。曾经我们可以非常简单地提高单核的性能来提高计算机的运行效率,然而,现在这一美好的想法已经结束了。由于功耗墙的存在,如今,CPU单核性能已经很难提升,CPU频率已经早已脱离早期指数性发展曲线。

Moore's Law

并行化

提高计算机性能的方法,是并行化。让多个CPU,多个核心并行地处理问题,是提高性能的最佳方法。目前,几乎所有的超级计算机都以多核、并行、相关的方向入手,进行性能调优。

Dual Core Cache Design

并行的手段

GPGPU - 异构计算

显卡(GPU)包含大量的核心来支持高度并行化的计算,最开始的在显卡上的编程是很困难的,随着时代的发展显卡的计算能力越来越不容小觑。通用计算显卡(GPGPU)也开始包含在编译优化的领域。AI模型在大型服务器集群上完成训练,要想投入实践就必须要把他编译到真正的体系结构上运行。

Torch-MLIR

异构计算最复杂的问题在于,多个层面的IR包含可能的信息丢失,如何把IR紧密结合在一起,并完成相应的编译优化?

例如,你容易知道一个矩阵求两次转置恒等 \(\left(A^T\right)^T = A\) ,但如果矩阵转置已经被下降(lowering)到三地址码,甚至是更底层的指令,我们就丢失了矩阵实际上“求了两次转置”这么简单的优化条件。

MLIR的出现有助于解决这个问题,但不是这篇文章的重点,可能我会在后续的文章里写相关问题。

多核

为了实现并行化,我们可以给一个计算机加入多个核心。多核心的特点在于:

  • 他们拥有不同的寄存器

  • 有不同的中断处理请求

  • 一般由操作系统-对称多处理(SMP)调度

Symmetric multiprocessing

不同的寄存器代表每个核心具有不同的状态。例如,他们可能拥有不同的PC指针指向不同的代码区段,这样便可同时执行编写好的多段代码。

单核

乱序执行 (OoOE)

乱序执行(Out-of-Order Execution)是现代CPU最基本的一个并行手段。

1
2
3
4
5
6
7
8
int test(int &a,
int &b,
int &c,
int &d) {
a += b;
c += d;
return 0;
}

这段 C++ 代码被编译为如下所示的汇编。

1
2
3
4
5
6
7
8
lw      a1, 0(a1)
lw a4, 0(a0)
addw a1, a1, a4
sw a1, 0(a0)
lw a0, 0(a3)
lw a1, 0(a2)
addw a0, a0, a1
sw a0, 0(a2)

SIMD

OoOE在编程上由编译器全局指令调度器(Instruction Scheduler)优化。

单指令流多数据流(Single instruction, multiple data (SIMD)),提供了一种让我 们更好地进行向量计算的方式。

SIMD

SIMD 的好处

通常情况下我们很难将串行代码转化为并行,为了设计并行算法通常需要改变原有的逻辑。

RGBA

如图所示,在图形学中我们经常需要计算图像的颜色信息,而颜色在RGBA几个维度下的计算是可以向量化的。

SIMD 的缺陷

RISC-V Designers SIMD Instructions considered harmful. -- David Patterson

一开始,SIMD被认为是实现并行化简单有效的方法。我们将64位寄存器和ALU划分为许多8, 16, 32位的块,然后并行地计算它们。用每条指令的操作码(opcode)提供数据宽度和操作。

指令集膨胀

IA-32指令集已经从最开始的80多条指令增长到了现在的1400多条。SSE, AVX, 各种SIMD扩展和宽寄存器让指令集变得越来越复杂。

尾循环

SIMD 指令通常要求把数据完全加载到向量寄存器中,然后一次处理 \(n\) 个数据。但不是所有的应用场合,需要处理的数据都能被 \(n\) 整除,这就导致需要一个标量循环,完成向量循环的收尾工作,这个循环就被称为 尾循环

Vector vs SIMD

向量机与SIMD的真正区别在于,向量长度是否在机器码层面确定。

1
2
3
4
5
6
7
8
9
10
void *memcpy_vec(void *dst, void *src, size_t n) {
void *save = dst;
// 逐字节拷贝内存区域
for (size_t vl; n > 0; n -= vl, src += vl, dst += vl) {
vl = vsetvl_e8m8(n); // 需要计算 n 个元素,由 CPU 计算 vl
vuint8m8_t vec_src = vle8_v_u8m8(src, vl); // 从 src 中加载 vl 个元素
vse8_v_u8m8(dst, vec_src, vl); // 写入 vl 个元素到 dst
}
return save;
}

这个代码展示了 RISC-V 实现memcpy的矢量版本(“伪汇编”,用C表示)。 这个程序最关键的部分在于vl的设定,每次循环都加载vl个元素,而vl对于 RISC-V 而言是一个每次循环可变的量。

CPU可以自己适配要计算多少个元素,给出尽量多的一次计算的元素,然后再一起操作。

vl 对于这段代码而言,是 “长度无关的”。对于传统的 SIMD 指令,我们需要用不同的指令,代表不同的向量长度,例如 SSE 通常加载 128 位,而 AVX2 通常加载 256 位。

这样做可以带来很多好处。首先,二进制程序便在支持不同矢量长度的 CPU 之间可以直接执行,而不需要重新编译(二进制兼容)。其次,SIMD 指令集通常需要内存对齐,尾循环等等不能很好向量化的部分,而可变向量长度 vl 的存在使得可以消除尾循环。

自动向量化(Auto-Vectorization)

可行性与好处

标量代码可以被自动向量化成含向量计算的代码。

事实上,大量的标量循环都可以被向量化

1
2
3
4
5
void add(int * restrict A, int * restrict B, int n){
for(int i = 0;i < n;i++){
A[i] += B[i];
}
}

合法性

数据依赖 & Overlap (Alias Analysis)

1
2
3
4
for (int i = 0; i < N; i += 1) {
a[i+1] = b[i] + 1; // S1
b[i+1] = a[i] + 1; // S2
}

Example of pointer overlapping

1
2
3
4
5
for(int i = 1;i < n;i++)
A[i] = A[i - 1];

for(int i = 1;i < n;i++)
A[i + 1] = B[i]; // overlap?

收益

必然导致的程序大小增加 / 标量循环和向量循环的选择和跳转

数据对齐的代价,尾循环的代价,都是需要考虑的因素。

1
2
3
4
load i64;
load i64;
load i64;
load i64;
1
load <4 x i64>;

这个部分的代价计算在LLVM后端作为虚函数,由具体的Target给出估计。每个体系结构可能有不同的 SIMD 指令代价,但代价模型在优化层次是通用的

Transformation

下图展示了 LLVM Developer 2013 中,来自 Apple 的工程师给出的 LLVM 循环向量化工具。

LLVM Developer 2013 by Apple

Loop Vectorizer Enhancements

现代化向量指令集可以更好地完成向量长度选择。

1
2
3
4
5
6
7
8
9
10
11
memcpy:
mv a3, a0 # Copy destination
loop:
vsetvli t0, a2, e8, m8, ta, ma # Vectors of 8b
vle8.v v0, (a1) # Load bytes
add a1, a1, t0 # Bump pointer
sub a2, a2, t0 # Decrement count
vse8.v v0, (a3) # Store bytes
add a3, a3, t0 # Bump pointer
bnez a2, loop # Any more?
ret # Return

Mask & Predication

Predication (判定寄存器) 其实是来源于ARM SVE的一个东西

VP-based Loop Vectorizer 在 LLVM 中还没实现...

前言

每次开机或重启后,新开一个终端,总会有漫长的conda加载时间。

conda init 会在你的shell中写入 conda initialize 相关的内容,保证 conda 环境被初始化。

1
2
3
4
5
6
7
8
9
10
11
12
13
# >>> conda initialize >>>
__conda_setup="$("$__conda_prefix/bin/conda" 'shell.bash' 'hook' 2> /dev/null)"
if [ $? -eq 0 ]; then
eval "$__conda_setup"
else
if [ -f "$__conda_prefix/etc/profile.d/conda.sh" ]; then
. "$__conda_prefix/etc/profile.d/conda.sh"
else
export PATH="$__conda_prefix/bin:$PATH"
fi
fi
unset __conda_setup
# <<< conda initialize <<<

然而,不知道为什么,这个东西会严重拖慢第一次打开终端时进入正常交互式shell的速度。

解决方案

在这里我的解决方案是,添加一个延迟加载选项。我的日常环境中不是所有的终端都会用上conda,甚至大概率不用。所以按需要加载环境就非常重要。

或许可以设计一个load_conda的函数,然后需要用conda的时候加载它!

然而,这样好像太蠢了!有没有一个办法能够在我输入conda指令时,虽然引发了一个错误但自动加载conda环境,然后执行加载后的conda? (类似于虚拟内存与缺页中断)

我把激活conda相关的变量改成了这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# https://www.reddit.com/r/zsh/comments/qmd25q/lazy_loading_conda/
# Add any commands which depend on conda here
lazy_conda_aliases=('python' 'conda')

load_conda() {
for lazy_conda_alias in $lazy_conda_aliases; do
unalias $lazy_conda_alias
done

__conda_prefix="$HOME/anaconda3" # Set your conda Location

# >>> conda initialize >>>
__conda_setup="$("$__conda_prefix/bin/conda" 'shell.bash' 'hook' 2> /dev/null)"
if [ $? -eq 0 ]; then
eval "$__conda_setup"
else
if [ -f "$__conda_prefix/etc/profile.d/conda.sh" ]; then
. "$__conda_prefix/etc/profile.d/conda.sh"
else
export PATH="$__conda_prefix/bin:$PATH"
fi
fi
unset __conda_setup
# <<< conda initialize <<<

unset __conda_prefix
unfunction load_conda
}

for lazy_conda_alias in $lazy_conda_aliases; do
alias $lazy_conda_alias="load_conda && $lazy_conda_alias"
done

这个方案实在是太巧了!很符合我对未来的想象(

当你在shell输入conda时,没有加载conda时会触发load_conda,然后自动加载conda。之后又会被alias到conda指令本身,看起来就像无缝加载了一个变量一样!

syscall

系统调用简介

系统调用syscall可以看作一次特殊的函数调用。程序按照Calling Convention将参数放在寄存器、堆栈中,然后CPU硬件修改程序计数器,权限状态等信息,跳转到内核提前设定好的一个位置(stvec)。

之后,处理器开始执行内核代码。内核代码执行完后,恢复发生中断时的现场,继续运行程序。

syscall lab 概述

这个lab一共有两个实验,分别是tracesysinfo,前者要求我们在之后系统调用时,打印系统调用的情况,后者需要我们提供内存使用和进程的使用信息。

我的所有实验代码都可以在github找到。

trace

这个实验重点是对于每个proc结构体保存一个flag,表示他要不要进行trace。

然后,在系统调用返回时,设计成可以打印结果:

1
2
3
4
5
6
7
8
num = p->trapframe->a7;
if(num > 0 && num < NELEM(syscalls) && syscalls[num]) {
int ret = syscalls[num]();
p->trapframe->a0 = ret;
if (p->tsysflag & (1 << num)) printf("%d: %s -> %d\n", p->pid, syscallnames[num], ret);
} else {
printf("%d %s: unknown sys call %d\n",
p->pid, p->name, num);

tsysflag是需要新写到结构体里的一个成员。

syscallnames,每个系统调用的字符串名字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
static char *syscallnames[] = {
[SYS_fork] "fork",
[SYS_exit] "exit",
[SYS_wait] "wait",
[SYS_pipe] "pipe",
[SYS_read] "read",
[SYS_kill] "kill",
[SYS_exec] "exec",
[SYS_fstat] "fstat",
[SYS_chdir] "chdir",
[SYS_dup] "dup",
[SYS_getpid] "getpid",
[SYS_sbrk] "sbrk",
[SYS_sleep] "sleep",
[SYS_uptime] "uptime",
[SYS_open] "open",
[SYS_write] "write",
[SYS_mknod] "mknod",
[SYS_unlink] "unlink",
[SYS_link] "link",
[SYS_mkdir] "mkdir",
[SYS_close] "close",
[SYS_trace] "trace",
};

trace实验的所有代码参考这里

sysinfo

主要是实现两个模块,进程和内存。

内存方面,内核用一个kfreelist来保存现在空闲的内存信息,这是一个链表,统计时只需要遍历链表即可。内存都是按照页分配的,所以结果就是PGSIZE * free_num

1
2
3
4
5
6
7
8
// kernel/kalloc.c
int kfreepages_count(){
int n = 0;
struct run *current = kmem.freelist;

for(;current;current = current->next) ++n;
return n;
}

进程计数,直接遍历进程数组,看他们中哪些不是UNUSED

1
2
3
4
5
6
7
8
9
10
11
// kernel/proc.c
int nproc(){
struct proc *p;
int ret = 0;
for(p = proc;p < proc + NPROC; p++){
acquire(&p->lock);
if(p->state != UNUSED) ret++;
release(&p->lock);
}
return ret;
}

最后,整理出系统调用的结果,把他们拷贝到用户态去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// kernel/sysinfo.c
uint64 sys_sysinfo(void)
{
uint64 va_info;
if(argaddr(0, &va_info)){
return -1;
}
struct sysinfo info;
struct proc *p = myproc();
info.freemem = kfreepages_count() * PGSIZE;
info.nproc = nproc();
if(copyout(p->pagetable, va_info, (void*)&info, sizeof(info))){
return -1;
}
return 0;
}

Primes

这个实验要求设计一个素数发生器。基于管道实现埃氏筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include "user.h"
void produce(int backward_pipe_fd) {
int prime;
read(backward_pipe_fd, &prime, sizeof(int));
printf("prime %d\n", prime);
if (prime >= 31) {
return;
}
int pp[2];
pipe(pp);
int pid = fork();
if (pid == 0) {
// child
close(pp[1]);
produce(pp[0]);
close(pp[0]);
} else {
int n;
close(pp[0]); // close a ----- b ----read--- c
for (; read(backward_pipe_fd, &n, sizeof(int));) {
if (n % prime)
write(pp[1], &n, sizeof(int));
}
close(pp[1]); // close a ---------- b ---write-- c
close(backward_pipe_fd); // close a ---read--- b ---------- c
wait(0);
}
exit(0);
}

int main() {
printf("prime 2\n");
int pp[2];
pipe(pp);
int pid = fork();
if (pid == 0) {
// child
close(pp[1]);
produce(pp[0]);
} else {
close(pp[0]);
for (int i = 3; i < 32; i += 2) { // filter 2-factors
write(pp[1], &i, sizeof(int));
}
close(pp[1]);
wait(0);
}
exit(0);
}

最开始的实验版本我在fork之后才调用pipe,导致出现了逻辑上的问题。这个程序中如果不及时关闭pipe中不需要的那个fd,会导致阻塞/资源用尽。

Pingpong

继续Lab1的实验,这个程序要求我们用一个管道实现父子进程通信,即开一个pipe,然后父进程发一个ping,子进程表示自己收到了ping,然后再翻过来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include "user.h"

int main(int argc, char *argv[]) {
int pipes[2];
int n = pipe(pipes);
if (n < 0) {
printf("pipe error\n");
exit(1);
}
int pid = fork();
if (pid < 0) {
printf("fork error\n");
exit(1);
}
if (pid == 0) {
char rd;
read(pipes[0], &rd, sizeof(char));
printf("%d: received ping\n", getpid());
write(pipes[1], &rd, sizeof(char));
} else {
// parent process
char wr = 'p';
write(pipes[1], &wr, sizeof(char));
read(pipes[0], &wr, sizeof(char));
printf("%d: received pong\n", getpid());
}
exit(0);
}

启动xv6(easy)

前言

我的实验环境是一台PC, 运行在我的寝室,作为工作站运行。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
[I] lyc@lyc-workstation ~/w/学/C/c/MIT6.S081 (master)> neofetch
-/oyddmdhs+:. lyc@lyc-workstation
-odNMMMMMMMMNNmhy+-` -------------------
-yNMMMMMMMMMMMNNNmmdhy+- OS: Gentoo Base System release 2.8 x86_64
`omMMMMMMMMMMMMNmdmmmmddhhy/` Host: MS-7D42 1.0
omMMMMMMMMMMMNhhyyyohmdddhhhdo` Kernel: 5.18.5-gentoo-lyc
.ydMMMMMMMMMMdhs++so/smdddhhhhdm+` Uptime: 22 hours, 29 mins
oyhdmNMMMMMMMNdyooydmddddhhhhyhNd. Packages: 1473 (emerge)
:oyhhdNNMMMMMMMNNNmmdddhhhhhyymMh Shell: bash 5.1.16
.:+sydNMMMMMNNNmmmdddhhhhhhmMmy Resolution: 3840x2160
/mMMMMMMNNNmmmdddhhhhhmMNhs: DE: Plasma 5.24.5
`oNMMMMMMMNNNmmmddddhhdmMNhs+` WM: KWin
`sNMMMMMMMMNNNmmmdddddmNMmhs/. WM Theme: Breeze 微风
/NMMMMMMMMNNNNmmmdddmNMNdso:` Theme: Breeze Light [Plasma], Breeze [GTK2/3]
+MMMMMMMNNNNNmmmmdmNMNdso/- Icons: Fluent [Plasma], Fluent [GTK2/3]
yMMNNNNNNNmmmmmNNMmhs+/-` Terminal: Konsole
/hMMNNNNNNNNMNdhs++/-` CPU: 12th Gen Intel i7-12700 (20) @ 4.900GHz
`/ohdmmddhys+++/:.` GPU: Intel AlderLake-S GT1
`-//////:--. Memory: 36679MiB / 128619MiB




RISC-V 64运行和交叉编译环境

cross-compilers

要运行老师给的xv6操作系统代码,必须先有交叉编译工具。[1]

用gentoo的crossdev工具[2]安装跨指令集的编译工具,包括GNU binutils, gcc, g++

1
sudo crossdev --stable -t riscv64-unknown-linux-gnu

Emulator(QEMU)

安装打开了riscv64对应的编译开关的qemu,我的实验主机是Gentoo Linux操作系统,在Portage中加入USE

1
write-use app-emulation qemu qemu_user_targets_riscv64 qemu_softmmu_targets_riscv64

其中write-use是一个自己写的辅助脚本

1
2
3
4
5
lyc@lyc-workstation ~> cat $(which write-use)
#!/bin/fish

set portage_use_dir "/etc/portage/package.use"
echo "$argv[1]/$argv[2] $argv[3..]" | sudo tee -a "$portage_use_dir/$argv[1]"

然后,重新编译qemu

1
sudo emerge -av qemu

获取实验源代码

clone mit xv6仓库

1
git clone git://g.csail.mit.edu/xv6-labs-2021

选到util分支

1
cd xv6-labs-2021 && git checkout util

编译和进入xv6系统

1
2
3
4
5
6
7
8
9
10
[I] lyc@lyc-workstation ~/w/学/C/c/M/xv6-labs-2021 (util)> make qemu
qemu-system-riscv64 -machine virt -bios none -kernel kernel/kernel -m 128M -smp 3 -nographic -drive file=fs.img,if=none,format=raw,id=x0 -device virtio-blk-device,drive=x0,bus=virtio-mmio-bus.0

xv6 kernel is booting

hart 1 starting
hart 2 starting
init: starting sh
$

Ctrl-a x退出系统。

sleep

实现一个UNIXsleep程序,要求使用sleep系统调用。

  • xv6 book 第一章
  • user/下有不少可以参考的程序
  • 如果用户没有参数,则打印错误信息
  • 用系统调用
  • 系统调用源代码在kernel/sysproc.c中可见
  • main函数应该使用exit(0)来正常推出
  • 将程序写入到Makefile的UPROGS中。

构建系统添加sleep

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
UPROGS=\
$U/_cat\
$U/_echo\
$U/_forktest\
$U/_grep\
$U/_init\
$U/_kill\
$U/_ln\
$U/_ls\
$U/_mkdir\
$U/_rm\
$U/_sh\
$U/_stressfs\
$U/_usertests\
$U/_grind\
$U/_wc\
$U/_zombie\
$U/_sleep\

sleep syscall的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// kernel/sysproc.c

uint64
sys_sleep(void)
{
int n;
uint ticks0;

if(argint(0, &n) < 0)
return -1;
acquire(&tickslock);
ticks0 = ticks;
while(ticks - ticks0 < n){
if(myproc()->killed){
release(&tickslock);
return -1;
}
sleep(&ticks, &tickslock);
}
release(&tickslock);
return 0;
}

其中,这里的sleep函数是一个在proc.c中实现的函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
// kernel/proc.c

// Atomically release lock and sleep on chan.
// Reacquires lock when awakened.
void
sleep(void *chan, struct spinlock *lk)
{
struct proc *p = myproc();

// Must acquire p->lock in order to
// change p->state and then call sched.
// Once we hold p->lock, we can be
// guaranteed that we won't miss any wakeup
// (wakeup locks p->lock),
// so it's okay to release lk.

acquire(&p->lock); //DOC: sleeplock1
release(lk);

// Go to sleep.
p->chan = chan;
p->state = SLEEPING;

sched();

// Tidy up.
p->chan = 0;

// Reacquire original lock.
release(&p->lock);
acquire(lk);
}

调度器、状态转移,这些概念应该在之后的课程中会涉及到。

自己实现的sleep.c

1
2
3
4
5
6
7
8
9
10
11
12
// user/sleep.c
#include "user.h"

int main(int argc, char *argv[]) {
if (argc != 2) {
printf("Usage: sleep <seconds>\n");
exit(-1);
}
int ticks = atoi(argv[1]);
sleep(ticks);
exit(0);
}

其中,他这里的uint还会出现一些编译错误

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
In file included from user/sleep.c:1:
user/user.h:36:1: 错误:unknown type name ‘uint’; did you mean ‘int’?
36 | uint strlen(const char*);
| ^~~~
| int
user/user.h:37:26: 错误:unknown type name ‘uint’; did you mean ‘int’?
37 | void* memset(void*, int, uint);
| ^~~~
| int
user/user.h:38:1: 错误:函数声明中出现形参名却未指定类型 [-Werror]
38 | void* malloc(uint);
| ^~~~
user/user.h:41:40: 错误:unknown type name ‘uint’; did you mean ‘int’?
41 | int memcmp(const void *, const void *, uint);
| ^~~~
| int
user/user.h:42:36: 错误:unknown type name ‘uint’; did you mean ‘int’?
42 | void *memcpy(void *, const void *, uint);
| ^~~~
| int
cc1:所有的警告都被当作是错误

我在user/user.h中加了一个类型定义,来解决这个编译错误

然后再次make qemu就可以了。

0%