首先利用brew进行安装：

1

brew install libomp

完成之后，采用如下的测试代码，存储为hello.c：

1
2
3
4
5
6

#include <omp.h>
#include <stdio.h> 
int main() { 
  #pragma omp parallel 
  printf("Hello from thread %d, nthreads %d\n", omp_get_thread_num(), omp_get_num_threads());
}

尝试利用gcc进行编译：

1

gcc hello.c -fopenmp -o hello && ./hello

诡异的事情出现了，会得到如下的结果，非常奇怪，gcc应该是支持这个选项的：

1

clang: error: unsupported option '-fopenmp'

从这个地方可以发现clang进行了报错，但是明明是使用gcc进行编译的，利用gcc -v查看可以看到如下发现：

1
2
3
4

Apple clang version 11.0.0 (clang-1100.0.33.17)
Target: x86_64-apple-darwin19.3.0
Thread model: posix
InstalledDir: /Library/Developer/CommandLineTools/usr/bin

这里名叫gcc的东西实际上是clang，所以正常使用gcc编译的时候实际上是用的clang？？？之后采用gcc-9来指定gcc进行编译，而不采用clang：

1

gcc-9 hello.c -fopenmp -o hello && ./hello 

可以正常的执行并得到如下的结果：

1
2
3
4
5
6
7
8

Hello from thread 1, nthreads 8
Hello from thread 4, nthreads 8
Hello from thread 3, nthreads 8
Hello from thread 6, nthreads 8
Hello from thread 5, nthreads 8
Hello from thread 0, nthreads 8
Hello from thread 2, nthreads 8
Hello from thread 7, nthreads 8

由于多线程并不能保证执行顺序，可以看到Hello的打印顺序是不一样的，到这里就可以愉快使用OpenMP了！

简介

文章提出了一种利用重复一个简单基本块从而聚集一系列有着相同拓扑结构的的转换，这种多分支的结构叫做ResNeXt，相对于ResNet的有着更好地性能。

就像VGG和ResNet一样，都是通过堆叠有着相同拓扑结构的模块这种简单策略，来实现更好的效果。而Inception model不同，是通过一种split-transform-merge的策略，首先split来得到一些低维的embedding，然后过一系列不同的filter来进行transform，最后直接拼接merge在一起，通过这种方式来用更小的算力企图获得更大更深的网络能够带来的表现。

这篇论文中提出了一个同样是重复模块的简单模型，从VGG/ResNet和Inception model都借鉴了策略，将一系列有着相同拓扑结构的transformation给聚集起来了。这种聚集的transformation的多少叫做cardinality。实验证明，当提高网络的深度和宽度得到减少的回报的时候，提升cardinality是一个更有效的提升准确率的方法。

网络结构

这种网络有着三种等价形式：

可以发现最上面一层每一条路径都能够看到全部的数据，最后面一层由于最后对于多条之路要汇总求和，所以也是可以直接做卷积，能够看到全部的数据的。事实上只有中间的卷积操作，对于每一条支路而言，只能看到上一层部分的数据。虽然三者相互等价，但是显然在实现上采用c中描述的形式要简便许多。

以上分析针对三层以上网络，那么对于小于三层的网络而言，两种实现是完全等价的。

那么这里采用新的形式从64变为32x4d的方法只是额外增加了网络宽度。

参数量

以上是几种参数规模差不多的设置，其中$C=1$的情况代表的就是普通的ResNet，实验结果最好的为$C=32$，即$32\times4d$的模型。对于每一层的参数计算如下：

$C \cdot(256*d+3*d*d+d*256)$

代码实现

其实基本和ResNet的实现相同，由于pyTorch的卷积层自身有group参数，采用之前提到的三种等价形式的最后一种，只需要在Bottleneck的模块中将中间的卷积层的group设置成32，重新设置Basicblock和Bottleneck的expansion为原来的二分之一，调整channel的大小为原来的两倍，就可以得到ResNeXt了，下面是ResNeXt(32x4D)的一个实现：

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

class BasicBlock(nn.Module):
    expansion = 0.5
    
    def __init__(self, input_channel, channel, stride):
        super(BasicBlock, self).__init__()
        
        output_channel = int(channel * self.expansion)
        self.downsample = lambda x: x
        if(input_channel != output_channel):
            self.downsample = nn.Sequential(
                nn.Conv2d(in_channels = input_channel, out_channels = output_channel, kernel_size = 1, stride = stride, bias = False),
                nn.BatchNorm2d(output_channel)
            )
        
        self.relu = nn.ReLU(inplace = True)
        
        self.convlayers = nn.Sequential(
            nn.Conv2d(in_channels = input_channel, out_channels = channel, kernel_size = 3, stride = stride, padding = 1, bias = False),
            nn.BatchNorm2d(channel),
            nn.ReLU(inplace = True),
            nn.Conv2d(in_channels = channel, out_channels = output_channel, kernel_size = 3, stride = 1, padding = 1, bias = False),
            nn.BatchNorm2d(output_channel)
        )
    def forward(self, x):
        out = self.downsample(x) + self.convlayers(x)
        out = self.relu(out)
        return out

class Bottleneck(nn.Module):
    expansion = 2
    
    def __init__(self, input_channel, channel, stride, expansion = 2, group_num = 32):
        super(Bottleneck, self).__init__()
        self.expansion = expansion
        output_channel = channel * expansion
        
        self.downsample = lambda x: x
        if(input_channel != output_channel):
            self.downsample = nn.Sequential(
                nn.Conv2d(in_channels = input_channel, out_channels = output_channel, kernel_size = 1, stride = stride, bias = False),
                nn.BatchNorm2d(output_channel)
            )
        
        self.relu = nn.ReLU(inplace = True)
        
        self.convlayers = nn.Sequential(
            nn.Conv2d(in_channels = input_channel, out_channels = channel, kernel_size = 1, stride = 1, bias = False),
            nn.BatchNorm2d(channel),
            nn.ReLU(inplace = True),
            nn.Conv2d(in_channels = channel, out_channels = channel, kernel_size = 3, stride = stride, padding = 1, groups = group_num, bias = False),
            nn.BatchNorm2d(channel),
            nn.ReLU(inplace = True),
            nn.Conv2d(in_channels = channel, out_channels = output_channel, kernel_size = 1, stride = 1, bias = False),
            nn.BatchNorm2d(output_channel)
        )
    def forward(self, x):
        out = self.downsample(x) + self.convlayers(x)
        out = self.relu(out)
        return out
    
class ResNet(nn.Module):
    def __init__(self, block, block_nums, input_channel, class_num = 1000):
        super(ResNet, self).__init__()
        
        self.stacklayers = nn.Sequential(
            nn.Conv2d(in_channels = input_channel, out_channels = 64, kernel_size = 7, stride = 2, padding = 3, bias = False),
            nn.BatchNorm2d(64),
            nn.ReLU(inplace = True),
            nn.MaxPool2d(kernel_size = 3, stride = 2, padding = 1),
            self.make_layers(block = block, input_channel = 64, channel = 128, stride = 1, block_num = block_nums[0]),
            self.make_layers(block = block, input_channel = int(128 * block.expansion), channel = 256, stride = 2, block_num = block_nums[1]),
            self.make_layers(block = block, input_channel = int(256 * block.expansion), channel = 512, stride = 2, block_num = block_nums[2]),
            self.make_layers(block = block, input_channel = int(512 * block.expansion), channel = 1024, stride = 2, block_num = block_nums[3]),
            nn.AdaptiveAvgPool2d(1),
            nn.Flatten(),
            nn.Linear(int(1024*block.expansion), class_num)
        )
    
    def make_layers(self, block, input_channel, channel, stride, block_num):
        layers = []
        layers.append(block(input_channel, channel, stride))
        input_channel = int(channel * block.expansion)
        for _ in range(1, block_num):
            layers.append(block(input_channel, channel, 1))
        return nn.Sequential(*layers)
    
    def forward(self, x):
        out = self.stacklayers(x)
        return out
    
def ResNeXt_18(input_channel, class_num):
    return ResNet(BasicBlock, [2,2,2,2], input_channel, class_num)

def ResNeXt_34(input_channel, class_num):
    return ResNet(BasicBlock, [3,4,6,3], input_channel, class_num)

def ResNeXt_50(input_channel, class_num):
    return ResNet(Bottleneck, [3,4,6,3], input_channel, class_num)

def ResNeXt_101(input_channel, class_num):
    return ResNet(Bottleneck, [3,4,23,3], input_channel, class_num)

def ResNeXt_152(input_channel, class_num):
    return ResNet(Bottleneck, [3,8,36,3], input_channel, class_num)

Environment Setting

在OS X下进行的环境搭建，配置如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

             ###                  User: pims
           ####                   Hostname: PimsdeMacBook-Pro
           ###                    Distro: OS X 10.15.3
   #######    #######             Kernel: Darwin
 ######################           Uptime:  7:32
#####################             Shell: /bin/zsh
####################              Terminal: xterm-256color iTerm.app
####################              CPU: Intel Core i5-8257U CPU @ 1.40GHz
#####################             Memory: 16 GB
 ######################           Disk: 26%
  ####################            Battery: 100%
    ################             
     ####     #####

由于官网提供的补丁版qemu在本地报错make不成功，所以用的是正常版的qemu，但是对于在完成exercise的过程中没有遇到很大的问题，对于lab文件的make结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

➜  lab git:(lab1) ✗ make
+ as kern/entry.S
+ cc kern/entrypgdir.c
+ cc kern/init.c
+ cc kern/console.c
+ cc kern/monitor.c
+ cc kern/printf.c
+ cc kern/kdebug.c
+ cc lib/printfmt.c
+ cc lib/readline.c
+ cc lib/string.c
+ ld obj/kern/kernel
i386-jos-elf-ld: warning: section `.bss' type changed to PROGBITS
+ as boot/boot.S
+ cc -Os boot/main.c
+ ld boot/boot
boot block is 382 bytes (max 510)
+ mk obj/kern/kernel.img

Exercise1

内容为阅读汇编的文档，进行了阅读，了解了内嵌汇编的语法格式。

Exercise2

逐步执行查看了运行过程，并且对于GDB指令进行了进一步的熟悉。

Exercise3

• At what point does the processor start executing 32-bit code? What exactly causes the switch from 16- to 32-bit mode?

1
2
3
4
5
6
7
8

lgdt    gdtdesc
movl    %cr0, %eax        
orl     $CR0_PE_ON, %eax  
movl    %eax, %cr0        

# Jump to next instruction, but in 32-bit code segment.
# Switches processor into 32-bit mode.
ljmp    $PROT_MODE_CSEG, $protcseg

在修改完了cr0的值之后，通过ljmp指令切换到32-bit模式

• What is the last instruction of the boot loader executed, and what is the first instruction of the kernel it just loaded?

在main.c文件中可以看到，bootmain结尾的最后是：

1

((void (*)(void)) (ELFHDR->e_entry))();

转到ELF头里面的入口，这个函数正常情况下不会返回，所以后面bad里面的死循环在正常情况下是永远不可能执行的代码。

在obj/boot/boot.asm里面可以看到对应的内容为：

1

7d63:	ff 15 18 00 01 00    	call   *0x10018

• Where is the first instruction of the kernel?

在gdb窗口中b *0x7d63在call语句前面打一个断点，之后执行si，可以看到kernel里面的第一条语句是

1

0x10000c:	movw   $0x1234,0x472

• How does the boot loader decide how many sectors it must read in order to fetch the entire kernel from disk? Where does it find this information?

在ELF头里面，保存了相关的信息，其中Elf数据类型的定义inc/elf.h头文件当中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

struct Elf {
	uint32_t e_magic;	// must equal ELF_MAGIC
	uint8_t e_elf[12];
	uint16_t e_type;
	uint16_t e_machine;
	uint32_t e_version;
	uint32_t e_entry;
	uint32_t e_phoff;
	uint32_t e_shoff;
	uint32_t e_flags;
	uint16_t e_ehsize;
	uint16_t e_phentsize;
	uint16_t e_phnum;
	uint16_t e_shentsize;
	uint16_t e_shnum;
	uint16_t e_shstrndx;
};

其中e_phoff表示Program header table在文件中的偏移量，e_phnum表示Program header table里面一共有多少个条目，在bootmain的主函数中从ELF头读入得到：

1
2

ph = (struct Proghdr *) ((uint8_t *) ELFHDR + ELFHDR->e_phoff);
eph = ph + ELFHDR->e_phnum;

Exercise4

pointers.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
34
35
36
37
38
39
40
41
42
43
44
45
46
47

#include <stdio.h>
#include <stdlib.h>

void
f(void)
{
    int a[4];
    int *b = malloc(16);
    int *c;
    int i;

    printf("1: a = %p, b = %p, c = %p\n", a, b, c);

    c = a;
    for (i = 0; i < 4; i++)
	a[i] = 100 + i;
    c[0] = 200;
    printf("2: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n",
	   a[0], a[1], a[2], a[3]);

    c[1] = 300;
    *(c + 2) = 301;
    3[c] = 302;
    printf("3: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n",
	   a[0], a[1], a[2], a[3]);

    c = c + 1;
    *c = 400;
    printf("4: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n",
	   a[0], a[1], a[2], a[3]);

    c = (int *) ((char *) c + 1);
    *c = 500;
    printf("5: a[0] = %d, a[1] = %d, a[2] = %d, a[3] = %d\n",
	   a[0], a[1], a[2], a[3]);

    b = (int *) a + 1;
    c = (int *) ((char *) a + 1);
    printf("6: a = %p, b = %p, c = %p\n", a, b, c);
}

int
main(int ac, char **av)
{
    f();
    return 0;
}

得到的输出结果为：

1
2
3
4
5
6

1: a = 0x7ffeef413940, b = 0x7ffe70c00060, c = 0x7ffeef4139a0
2: a[0] = 200, a[1] = 101, a[2] = 102, a[3] = 103
3: a[0] = 200, a[1] = 300, a[2] = 301, a[3] = 302
4: a[0] = 200, a[1] = 400, a[2] = 301, a[3] = 302
5: a[0] = 200, a[1] = 128144, a[2] = 256, a[3] = 302
6: a = 0x7ffeef413940, b = 0x7ffeef413944, c = 0x7ffeef413941

可以看到b指向的是在堆上面开辟的空间，而a、c都是在栈上面开辟的空间，所以地址存在一定差异。之后都是一些比较简单的地址索引以及指针加法。

Exercise5

这里将boot/Makefrag文件中的0x7C00修改成了0x7D00：

1
2
3
4
5
6

$(OBJDIR)/boot/boot: $(BOOT_OBJS)
	@echo + ld boot/boot
	$(V)$(LD) $(LDFLAGS) -N -e start -Ttext 0x7D00 -o $@.out $^
	$(V)$(OBJDUMP) -S $@.out >$@.asm
	$(V)$(OBJCOPY) -S -O binary -j .text $@.out $@
	$(V)perl boot/sign.pl $(OBJDIR)/boot/boot

重新make之后，查看obj/boot/boot.asm可以发现链接地址已经发生了改变：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

.globl start
start:
  .code16                     # Assemble for 16-bit mode
  cli                         # Disable interrupts
    7d00:	fa                   	cli    
  cld                         # String operations increment
    7d01:	fc                   	cld    

  # Set up the important data segment registers (DS, ES, SS).
  xorw    %ax,%ax             # Segment number zero
    7d02:	31 c0                	xor    %eax,%eax
  movw    %ax,%ds             # -> Data Segment
    7d04:	8e d8                	mov    %eax,%ds
  movw    %ax,%es             # -> Extra Segment
    7d06:	8e c0                	mov    %eax,%es
  movw    %ax,%ss             # -> Stack Segment
    7d08:	8e d0                	mov    %eax,%ss

但是执行GDB可以看到，事实上BIOS依然将boot loader加载到了0x7c00的位置，也就是说程序在执行到这里的时候，前面依然有一部分是可以正常执行的：

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

Breakpoint 1, 0x00007c00 in ?? ()
(gdb) x/40i
   0x7c01:	cld
   0x7c02:	xor    %eax,%eax
   0x7c04:	mov    %eax,%ds
   0x7c06:	mov    %eax,%es
   0x7c08:	mov    %eax,%ss
   0x7c0a:	in     $0x64,%al
   0x7c0c:	test   $0x2,%al
   0x7c0e:	jne    0x7c0a
   0x7c10:	mov    $0xd1,%al
   0x7c12:	out    %al,$0x64
   0x7c14:	in     $0x64,%al
   0x7c16:	test   $0x2,%al
   0x7c18:	jne    0x7c14
   0x7c1a:	mov    $0xdf,%al
   0x7c1c:	out    %al,$0x60
   0x7c1e:	lgdtl  (%esi)
   0x7c21:	fs jge 0x7c33
   0x7c24:	and    %al,%al
   0x7c26:	or     $0x1,%ax
   0x7c2a:	mov    %eax,%cr0
   0x7c2d:	ljmp   $0xb866,$0x87d32
   0x7c34:	adc    %al,(%eax)
   0x7c36:	mov    %eax,%ds
   0x7c38:	mov    %eax,%es
   0x7c3a:	mov    %eax,%fs
   0x7c3c:	mov    %eax,%gs
   0x7c3e:	mov    %eax,%ss
   0x7c40:	mov    $0x7d00,%esp
   0x7c45:	call   0x7d0b
   0x7c4a:	jmp    0x7c4a
   0x7c4c:	add    %al,(%eax)
   0x7c4e:	add    %al,(%eax)
   0x7c50:	add    %al,(%eax)
   0x7c52:	add    %al,(%eax)
   0x7c54:	(bad)
   0x7c55:	incl   (%eax)
   0x7c57:	add    %al,(%eax)
   0x7c59:	lcall  $0x0,$0xffff00cf
   0x7c60:	add    %dl,0x1700cf(%edx)
   0x7c66:	dec    %esp

但是与之前相比而言，对于ljmp指令发生了改变，这里附上之前的内容：

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

Breakpoint 1, 0x00007c00 in ?? ()
(gdb) x/40i
   0x7c01:	cld
   0x7c02:	xor    %eax,%eax
   0x7c04:	mov    %eax,%ds
   0x7c06:	mov    %eax,%es
   0x7c08:	mov    %eax,%ss
   0x7c0a:	in     $0x64,%al
   0x7c0c:	test   $0x2,%al
   0x7c0e:	jne    0x7c0a
   0x7c10:	mov    $0xd1,%al
   0x7c12:	out    %al,$0x64
   0x7c14:	in     $0x64,%al
   0x7c16:	test   $0x2,%al
   0x7c18:	jne    0x7c14
   0x7c1a:	mov    $0xdf,%al
   0x7c1c:	out    %al,$0x60
   0x7c1e:	lgdtl  (%esi)
   0x7c21:	fs jl  0x7c33
   0x7c24:	and    %al,%al
   0x7c26:	or     $0x1,%ax
   0x7c2a:	mov    %eax,%cr0
   0x7c2d:	ljmp   $0xb866,$0x87c32
   0x7c34:	adc    %al,(%eax)
   0x7c36:	mov    %eax,%ds
   0x7c38:	mov    %eax,%es
   0x7c3a:	mov    %eax,%fs
   0x7c3c:	mov    %eax,%gs
   0x7c3e:	mov    %eax,%ss
   0x7c40:	mov    $0x7c00,%esp
   0x7c45:	call   0x7d0b
   0x7c4a:	jmp    0x7c4a
   0x7c4c:	add    %al,(%eax)
   0x7c4e:	add    %al,(%eax)
   0x7c50:	add    %al,(%eax)
   0x7c52:	add    %al,(%eax)
   0x7c54:	(bad)
   0x7c55:	incl   (%eax)
   0x7c57:	add    %al,(%eax)
   0x7c59:	lcall  $0x0,$0xffff00cf
   0x7c60:	add    %dl,0x1700cf(%edx)
   0x7c66:	dec    %esp

可以看到由$0x87c32变成了$0x87d32，在执行完了ljmp指令之后，程序就会出错了。

Exercise6

在0x7c00处添加断点，查看0x100000地址存放的内容，可以发现是全0，这就是BIOS在进入boot loader的时候，对应的内容。

1
2

0x100000:	0x00000000	0x00000000	0x00000000	0x00000000
0x100010:	0x00000000	0x00000000	0x00000000	0x00000000

之后再0x7d63处添加断点，此时是boot loader要进入内核的时点，0x100000存放的内容如下：

1
2

0x100000:	0x1badb002	0x00000000	0xe4524ffe	0x7205c766
0x100010:	0x34000004	0x7000b812	0x220f0011	0xc0200fd8

可以发现已经发生了改变，并不是一开始的全0，说明boot loader进行了一个载入内核的工作。

Exercise7

从entry.S中，可以看到mov %eax,%cr0位于入口的开头处，利用gdb在入口处设置断点，逐条执行可以发现，这条指令位于0x100025，在此处设置断点：

1
2
3
4
5
6

(gdb) x/8x 0x00100000
0x100000:	0x1badb002	0x00000000	0xe4524ffe	0x7205c766
0x100010:	0x34000004	0x7000b812	0x220f0011	0xc0200fd8
(gdb) x/8x 0xf0100000
0xf0100000 <_start-268435468>:	0x00000000	0x00000000	0x00000000	0x00000000
0xf0100010 <entry+4>:	0x00000000	0x00000000	0x00000000	0x00000000

执行完这条指令之后：

1
2
3
4
5
6

(gdb) x/8x 0x00100000
0x100000:	0x1badb002	0x00000000	0xe4524ffe	0x7205c766
0x100010:	0x34000004	0x7000b812	0x220f0011	0xc0200fd8
(gdb) x/8x 0xf0100000
0xf0100000 <_start-268435468>:	0x1badb002	0x00000000	0xe4524ffe	0x7205c766
0xf0100010 <entry+4>:	0x34000004	0x7000b812	0x220f0011	0xc0200fd8

可以发现，在执行这条指令之前，0xf0100000处是全0的，在执行之后，有了和0x00100000处一样的值。设置了%cr0后启用分页，让0xf0100000和0x00100000映射到了同样的物理地址，所以查看会有相同的值。

在entry.S中可以看到，之后他尝试执行的指令是：

1
2

mov	$relocated, %eax
jmp	*%eax

他要在执行C代码之前，跳转到KERNBASE上方，不再在低地址了。从gdb可以发现，这里移入%eax的值为0xf010002f，如果没有启用分页，那么跳转将会失败。

可以发现当注释掉那一行之后，会导致内核崩溃，卡在Booting from Hard Disk..，同时利用GDB查看也可以看到，跳转进入的0xf010002c位置为全0。

Exercise8

缺失的内容定义在printfmt.c中第206行，直接仿照上面的%u进行修改，将base改成8就可以了。

1
2
3
4
5
6

// (unsigned) octal
case 'o':
	// Replace this with your code.
	num = getuint(&ap, lflag);
	base = 8;
	goto number;

可以发现，修改完之后，命令行中的"6828 decimal is 15254 octal!"已经可以正确显示了。

1. Explain the interface between printf.c and console.c. Specifically, what function does console.c export? How is this function used by printf.c?

console.c里面cputchar()函数在printf.c里面被使用了。它的作用是往屏幕上打印一个字符，被用在printf.c里面的putch()函数中，之后作为参数传入vprintfmt()的调用过程。

2. Explain the following from console.c:

1
2
3
4
5
6
7

if (crt_pos >= CRT_SIZE) {
  int i;
  memmove(crt_buf, crt_buf + CRT_COLS, (CRT_SIZE - CRT_COLS) * sizeof(uint16_t));
  for (i = CRT_SIZE - CRT_COLS; i < CRT_SIZE; i++)
    crt_buf[i] = 0x0700 | ' ';
  crt_pos -= CRT_COLS;
}

CRT_SIZE指的应该是crt_buff里面显示缓冲区的大小，所以这里的情况实际是超过缓冲区最大上限的时候的处理方法。memmove()函数的定义如下所示，其作用是将str2处复制n个字符到str1处，在有重叠区域的情况下比memcpy()更加安全。

1

void *memmove(void *str1, const void *str2, size_t n)

所以这里所进行的内容是将缓冲区的内容整体前移了CRT_COLS字符，腾出了一部分的缓冲区空间。

3. For the following questions you might wish to consult the notes for Lecture 2. These notes cover GCC’s calling convention on the x86.
   Trace the execution of the following code step-by-step:

   1 2	int x = 1, y = 3, z = 4; cprintf("x %d, y %x, z %d\n", x, y, z);

   • In the call to cprintf(), to what does fmt point? To what does ap point?
   • List (in order of execution) each call to cons_putc, va_arg, and vcprintf. For cons_putc, list its argument as well. For va_arg, list what ap points to before and after the call. For vcprintf list the values of its two arguments.

在对于cprintf()的调用当中，fmt指的是格式化的字符串，ap指向的是参数列表。

其中cons_putc()的内容如下：

1
2
3
4
5
6
7
8

// output a character to the console
static void
cons_putc(int c)
{
	serial_putc(c);
	lpt_putc(c);
	cga_putc(c);
}

他的作用是向console输出一个字符，主要的操作位于cga_putc()内容当中，对于输入来确定字符，然后根据情况进行输出。

vcprintf()内容如下：

1
2
3
4
5
6
7
8

int
vcprintf(const char *fmt, va_list ap)
{
	int cnt = 0;

	vprintfmt((void*)putch, &cnt, fmt, ap);
	return cnt;
}

传入格式化的字符串以及对应的参数列表，然后通过调用vprintfmt()进行输出。

而va_arg()的调用在vprintfmt()当中出现，例如：

1
2
3

case '*':
	precision = va_arg(ap, int);
	goto process_precision;

他实现的内容实际上是从ap里面读取一个参数，然后将ap进行一个修改，即通过后面提供的数据类型来进行指针的移动。

这三个函数的关系是vcprintf()中调用了vprintfmt()，在vprintfmt()内部利用va_arg()对格式化字符串中的参数进行解析，之后得到确切的字符串利用cons_putc()函数一个一个字符的向console进行输出。

4. Run the following code.

1
2

unsigned int i = 0x00646c72;
cprintf("H%x Wo%s", 57616, &i);

What is the output? Explain how this output is arrived at in the step-by-step manner of the previous exercise.

The output depends on that fact that the x86 is little-endian. If the x86 were instead big-endian what would you set i to in order to yield the same output? Would you need to change 57616 to a different value?

得到的输出为：“He110 World”。

可以知道57616转换成16进制的结果为e110，所以前半部分得到的是He110。

后半部分对应ASCII码表可以知道：

由于小端法存储，0x00646c72的存储实际上是

1

72 6c 64 00

对应的字符串就是"rld\0"，得到的后半部分为World。

如果改为大端法，对前半部分不会有影响，后半部分需要改成i = 0x726c6400。

5. In the following code, what is going to be printed after ‘y=’? (note: the answer is not a specific value.) Why does this happen?

1

cprintf("x=%d y=%d", 3);

执行得到的结果为"x=3 y=-267288596"，因为此处y所对应的%d没有给出，那么他会尝试在栈上读取内容。通过gdb调试可以知道最后传入时候ap = f0117fd4

1
2
3

(gdb) x/8x 0xf0117fd4
0xf0117fd4:	0x00000003	0xf0117fec	0x00000000	0x00000000
0xf0117fe4:	0x00000000	0x00000000	0x00646c72	0x00000000

查看地址所对应的内容，可以发现所打印出来的y其实就是后面的0xf0117fec转换成int的值。

6. Let’s say that GCC changed its calling convention so that it pushed arguments on the stack in declaration order, so that the last argument is pushed last. How would you have to change cprintf or its interface so that it would still be possible to pass it a variable number of arguments?

需要能够从栈顶知道一共有多少参数才能规范后面的行为，通过调整参数顺序，把fmt字符串当做最后一个参数输入，或者添加一个新参数为参数的总个数n放在末尾都可以。

Exercise9

在kern/entry.S的末尾可以看到如下代码，在.data段里面为栈预留了KSTKSIZE大小的空间。

1
2
3
4
5
6
7
8
9
10

.data
###################################################################
# boot stack
###################################################################
	.p2align	PGSHIFT		# force page alignment
	.globl		bootstack
bootstack:
	.space		KSTKSIZE
	.globl		bootstacktop   
bootstacktop:

在obj/kern/kernel.asm中的第56-58行，通过设置%esp来初始化栈的位置。

1
2
3

	# Set the stack pointer
	movl	$(bootstacktop),%esp
f0100034:	bc 00 80 11 f0       	mov    $0xf0118000,%esp

栈底的位置就是0xf0118000，从高地址往低地址生长。

同时在kern/entry.S的69行处可以看到：

1
2
3
4
5
6

relocated:

	# Clear the frame pointer register (EBP)
	# so that once we get into debugging C code,
	# stack backtraces will be terminated properly.
	movl	$0x0,%ebp			# nuke frame pointer

将栈的终点设置为0，这能够使得后面进行的backtrace可以正常终止，不会陷入死循环或者出错访问到栈之外的空间。

Exercise10

流程就是不断进行函数的调用，输入的参数每一次都-1，从一开始的5到最后的1然后到达递归终点。

obj/kern/kernel.asm中的对应内容如下：

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

void
test_backtrace(int x)
{
f0100040:	55                   	push   %ebp
f0100041:	89 e5                	mov    %esp,%ebp
f0100043:	53                   	push   %ebx
f0100044:	83 ec 14             	sub    $0x14,%esp
f0100047:	8b 5d 08             	mov    0x8(%ebp),%ebx
	cprintf("entering test_backtrace %d\n", x);
f010004a:	89 5c 24 04          	mov    %ebx,0x4(%esp)
f010004e:	c7 04 24 80 18 10 f0 	movl   $0xf0101880,(%esp)
f0100055:	e8 34 09 00 00       	call   f010098e <cprintf>
	if (x > 0)
f010005a:	85 db                	test   %ebx,%ebx
f010005c:	7e 0d                	jle    f010006b <test_backtrace+0x2b>
		test_backtrace(x-1);
f010005e:	8d 43 ff             	lea    -0x1(%ebx),%eax
f0100061:	89 04 24             	mov    %eax,(%esp)
f0100064:	e8 d7 ff ff ff       	call   f0100040 <test_backtrace>
f0100069:	eb 1c                	jmp    f0100087 <test_backtrace+0x47>
	else
		mon_backtrace(0, 0, 0);
f010006b:	c7 44 24 08 00 00 00 	movl   $0x0,0x8(%esp)
f0100072:	00 
f0100073:	c7 44 24 04 00 00 00 	movl   $0x0,0x4(%esp)
f010007a:	00 
f010007b:	c7 04 24 00 00 00 00 	movl   $0x0,(%esp)
f0100082:	e8 cb 06 00 00       	call   f0100752 <mon_backtrace>
	cprintf("leaving test_backtrace %d\n", x);
f0100087:	89 5c 24 04          	mov    %ebx,0x4(%esp)
f010008b:	c7 04 24 9c 18 10 f0 	movl   $0xf010189c,(%esp)
f0100092:	e8 f7 08 00 00       	call   f010098e <cprintf>
}
f0100097:	83 c4 14             	add    $0x14,%esp
f010009a:	5b                   	pop    %ebx
f010009b:	5d                   	pop    %ebp
f010009c:	c3                   	ret    

通过:

1

f0100044:	83 ec 14             	sub    $0x14,%esp

可以看到，每次栈向下生长0x14，并且每一次函数调用都会传入参数，同时保存%ebp和%ebx的值，将其压入栈中。每次栈向下生长0x20。折算成32-bit字的话应当是8个。

Exercise11

补全的mon_backtrace()如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

int
mon_backtrace(int argc, char **argv, struct Trapframe *tf)
{
	cprintf("Stack backtrace:\n");
	uint32_t* ebp = (uint32_t*)read_ebp();
	while(ebp){
		cprintf("ebp %08x ",ebp);
		cprintf("eip %08x ",*(ebp+1));
		cprintf("args");
		int i;
		for(i=2;i<=6;++i)
			cprintf(" %08x",*(ebp+i));
		cprintf("\n");
		ebp = (uint32_t*)(*ebp);
	}
	return 0;
}

执行结果如下：

可以看到最顶上的是mon_backtrace()函数，下面是五次的test_backtrace()调用，符合题目要求。

Exercise12

在debuginfo_eip()中利用stab_binsearch()函数来查找行号，通过观察inc/stab.h中的宏定义可以发现对应的类型应当是N_SLINE，对于搜索得到的结果，将行号从stabs数组中提取填写到info里面。如果lline>rline说明出现了错误，直接返回-1。

1
2
3
4
5

stab_binsearch(stabs, &lline, &rline, N_SLINE, addr);
if(lline <= rline)
	info->eip_line = stabs[lline].n_desc;
else
	return -1;

之后修改mon_backtrace()函数内部如下：

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

int
mon_backtrace(int argc, char **argv, struct Trapframe *tf)
{
	cprintf("Stack backtrace:\n");
	uint32_t* ebp = (uint32_t*)read_ebp();
	struct Eipdebuginfo info;
	while(ebp){
		cprintf("ebp %08x ",ebp);
		cprintf("eip %08x ",ebp[1]);
		cprintf("args");
		int i;
		for(i=2;i<=6;++i)
			cprintf(" %08x",ebp[i]);
		cprintf("\n");

		debuginfo_eip(ebp[1], &info);
		cprintf("\t%s:%d: %.*s+%d\n", info.eip_file, info.eip_line, info.eip_fn_namelen, info.eip_fn_name, ebp[1]-info.eip_fn_addr);

		ebp = (uint32_t*)(*ebp);
	}
	return 0;
}

在kern/monitor.c文件中加入新的命令行指令，这样当输入backtrace的时候就会调用mon_backtrace()函数。

1
2
3
4
5

static struct Command commands[] = {
	{ "help", "Display this list of commands", mon_help },
	{ "kerninfo", "Display information about the kernel", mon_kerninfo },
	{ "backtrace", "Findout the the value of \%ebp, \%eip and the args of called functions", mon_backtrace},
};

执行结果如下：

可见该指令可以成功被调用。

在本地使用make grade评测可以得到满分50分：

Challenge

通过WIKI百科中对于ANSI escape code的描述可以知道，利用\e[可以开启一个控制序列，那么只需要调整在输出字符串的开头控制颜色，在结尾恢复就可以，例如以下代码就会将输出文本调整成红色：

1

\e[31m<output string>\e[0m

将mon_backtrace()中打印行号等部分修改如下：

1

cprintf("\t\e[92m%s\e[0m:\e[31m%d\e[0m: \e[36m%.*s+%d\e[0m\n", info.eip_file, info.eip_line, info.eip_fn_namelen, info.eip_fn_name, ebp[1]-info.eip_fn_addr);

可以看到产生图中所示的彩色输出：

某量化的机器学习岗笔试题，回忆如下，虽然我不知道这笔试和金融/机器学习有什么关系。考试时长四个小时，一共七道题，最后两道编程题选一题做就可以，所以平均下来是每题四十分钟。

一、最大回撤

题目背景：考虑一个股票的价格在$N$天内的价格为$P_1,P_2,\ldots,P_N$，一个投资者比较厌恶风险，他所能接受的最大回撤不能超过$D$，试着计算他在这个最大回撤限制下的最大收益，算法复杂度需要是$O(N)$的级别。最大回撤定义为$\max(P_i-P_j),i<j$，其中$i,j$都在买卖区间内。

我的解答：双指针+单调队列维护区间最大值

双指针靠左的指向买入日，靠右的指向卖出日，利用单调队列维护买卖区间中的最大值。每次当卖出日右移的时候检查是否满足最大回撤的约束，如果是就尝试更新最大收益，否则的话就左移买入指针，并尝试更新最大收益。卖出指针移动到末端的时候，仍然要依次左移买入指针直到末端，并尝试更新最大收益。由于两个指针都要遍历数组，容易知道复杂度是$O(n)$的。

二、概率题——打乒乓球

题目背景：ABC三个人喜欢打乒乓球，但是一张球桌只能有两个人，所以有如下规则：每次两人对打，输家下场，换场下的人上场和赢家对打。那么三个人都非常好强，想要赢下另外两个人至少一局才算打爽了，（如A要打得爽，那么A需要赢过B也要赢过C），且只有所有人都打爽了球局才会结束，如果任意两个人的对局，都是五五开的，那么考虑以下两种情况：

1. 如果第一局AB对阵，B胜利，第二轮BC对阵，C胜利，第三轮AC对阵，A胜利，第四轮AB对阵，A胜利。从这之后到所有人都打爽了，需要打的局数的期望是多少？
2. 如果此时三个人刚刚来打球，那么要所有人都打爽了，需要打的局数的期望是多少？

我的解答：

1. 考虑如下的状态转换：

   

   一共有一下六个状态$abcdef$，他们对应状态要打的局数期望有以下关系：

   $\begin{cases} a = 1 + (c+d)/2 \\ b = 1 + (a+e)/2 \\ c = 1 + (a+b)/2 \\ d = 1 + e/2 \\ e = 1+(d+f)/2 \\ f = 1 + (d+e)/2 \end{cases}$

   可以解得：

   $\begin{cases} a = 36/5 \\ b = 38/5 \\ c = 42/5 \\ d = 4 \\ e = 6 \\ f = 6 \end{cases}$

   所以期望应当是$36/5$轮次

2. 我确实不会（菜狗哭泣），用它给的做编程题的窗口写了个代码跑模拟，得到的结果是$62/5$的期望。

三、报数

题目背景：一共有2019个人依次编号，首尾相连占成一个圈，教练让从1号开始报数，依次报121212，每次报到2的人出局，由于是一个圈，所以可以一直循环下去。

1. 问最后留下来的那个人的编号是多少？
2. 小明拿到了1001号，但是他爸是教练，可以选择在任意时候给他爸一个眼神交流，让他爸讲报数顺序逆转，问小明有没有可能留到最后？

我的解答：

1. 为了叙述方便首先定义轮次，从第1个人跑到最后算一个轮次，那么可以知道从第一轮留下来的都是奇数，相邻的人差的都是2，第二轮留下来的差的都是4，依次类推。所以容易发现每一轮留下来的人，在二进制表示上，有一位是相同的
   2019的二进制表示为：

$111\ 1110\ 0011$

将其左移一位，末尾补1，找到在1~2019范围内的值就是所求的值，对应的二进制表示为

$111\ 1100\ 0111$

即留下来的是1991号。

2. 有了前面的推断方法，我们可以判断在一共$n$个人的队列中，处于第$k$个的时候是不是最后留下来的，考虑1001的二进制表示为：

$011\ 1110\ 1001$

在倒数第二位的二进制表示出现不同，那么可以知道如果他爸不改顺序的话，他计划是在第二轮就被淘汰的。
这里进行讨论，首先看在第一轮的情况下，如果他爸在报数还没报到他的情况下就反转了，能不能让他留到最后。假设在他前面已经有$n$个人出局了，那么就还剩下了$2019-n$个人，由于在他之前，所以可以知道$n<=500$，必定有$2019-n>=1519>1024$，所以二进制表示保持有11位。
他爸有两种方法，一个是在第$2n$号出局的时候，立刻反转由$2n-1$号开始报1，他在队列中排$1019+n$位，另一种是在$2n+1$号报了1之后在进行反转，他在队列中排$1019+n+1$位。
为了使得他能够留到最后，那么要满足以上情况：

$(2019-n-1024)*2+1 = 1019+n(+1)$

此处的$(+1)$表示两种情况，整理可以得到：

$972= 3n(+1)$

可以发现，当不带$(+1)$的时候，$n$是存在解的，即$n=324$，所以在628号淘汰出局的时候，他爸立刻转向，让627号报1，小明就可以成为留到最后的人。

四、桥牌

问题背景：

1. 一共除去大小王有52张牌，每人13张牌，大小次序为AKQJT98765432。
2. 桥牌分为东南西北四家，其中南北为一队，东西为一队。按西北东南顺序出牌。
3. 每一轮要根据第一轮出牌的花色来出牌，没有的话只能出其他花色的垫牌，垫牌必定小。这一轮最大的下一轮首先出牌。
4. 西家先出牌，南北获胜的方法是赢下所有十三轮，东西获胜只要赢下一轮就可以。

问当四人都明牌的情况下，南北方的必胜策略是什么？

1. 西家先出红心T

2. 西家先出红心T

3. 西家先出红心6

我的解答：真是绝了，这道题杀我，太久没打牌而陷入思维陷阱，笔试就只做出了第一个。

1. 红心方片梅花北南都是绝对大，所以直接到下面这种情况，由于之前都是绝对大，此时北南可以控制由哪一边出牌

此时南家出9，如果西家出J，北家出A大。如果西家出8，那么北家出5，让南家大。

2. 南北两家出红心方片在可以绝对大八轮，在这中间北家垫牌梅花2，出梅花A大一轮，这个时候东家要垫四张牌，此时都是南家大。

如果东家垫的全部都是梅花，那么南家出梅花Q，北家垫掉黑桃5，之后北家三轮大。

如果东家垫过黑桃，那么北家黑桃AKQ5四轮都大。

3. 第一轮打完东家出J逼南家出A大，之后北家有方片AKQ三张绝对大，之后难上手，一定会打掉梅花七张牌。由于西家黑桃J大不过北家的A和南家的Q，所以这里略去西家。

首先可以确定北家必定上手，那么东家不会留超过两张红心，红心789首先会被垫干净。

之后北家角度来看，东家必然垫完了987之后，北家和南家都无法打过东家的牌，必然不会再打红心，所以北家的两张红心也会被垫干净

那么北家不会再打红心，东家继续拿着两张红心是不合理的，但是南家还有一张红心，所以红心Q也会被垫掉

这个时候，由于轮次的问题，北家必须要垫掉四张牌，然后才轮到东家决策，北家垫掉方片3456

此时东家必定垫掉方片8，之后北家垫掉黑桃4

东家肯定不会再动方片，那么最后一张垫牌就在红心K和黑桃T之间决策。

如果东家垫了黑桃T，那么南家走一张黑桃2，牌权交给北家，北家打完之后打掉方片三张，之后用一张黑桃5让南家黑桃Q大，游戏结束。

如果东家垫了红心K，那么南家走一张红心T可以大一轮，北家垫掉黑桃5，之后北家四张牌都是绝对大，游戏结束。

五、个人项目简答

就一个有关自己曾经做过项目的简答题，要求简明扼要，所占的分并不多。

六、算法编程——信封嵌套

问题背景：给定$N$个信封，每个信封由两个数$w,h$描述，表示信封的宽和高，如果一个信封的宽和高分别小于另外一个信封，那么就可以放入另一个信封，每个信封都可以进行90°的旋转，所以$w,h$是可以互换的。

1. 求出嵌套层数最多的方案。
2. 如果不是信封而是三维盒子，求出嵌套最多的方案。

我的解答：在我的算法中，信封和盒子都没有任何区别，所以这里统一考虑。

容易写出针对于两个信封比较的函数，即一个信封能否装下另一个信封。对每两个信封都做一个对比，如果$A$信封能够装下$B$信封，那么建立一条$A \rightarrow B$的连边。这样就构成了一个有向无环图，问题转变成了求图上的最长路径。

采用图上动态规划的方法来进行求解，每个节点上的val表示这个节点的信封作为最外层，所能够嵌套的层数，如果这个节点没有出边，那么将其val设置为1。否则的话，将他的val设置为子节点最大的val再加上1。遍历完整张图之后得到的最大的val值就是最大的嵌套层数。然后从有最大val值的节点进行一个DFS，就可以找到嵌套层数最多的方案。

建图的时间复杂度为$O(N^2)$，进行遍历的时间复杂度为$O(N)$，所以总的时间复杂度为$O(n^2)$。可能有$O(N\log N)$的解法？

Update：首先将两个数值进行排序，小的为高，大的为宽。之后对于一个排序，另一个利用树状数组进行维护，查看有多少高宽都小于它的信封就可以了，时间复杂度$O(N\log N)$。

七、算法编程——螺旋数组

问题背景：给定一个边长为$N$，数值由行列递增的方阵，问顺时针螺旋来读的话，第$K$位数字是什么？要求算法能够在合理时间内求解$N=30000000$量级的输入。

例如一个$N=3$的方阵，数值就为：

$\begin{matrix}1&2&3\\4&5&6\\7&8&9\\\end{matrix}$

此时顺时针螺旋读的话，顺序就是$1,2,3,6,9,8,7,4,5$，所以对于$N=3,K=4$的情况得到的结果就是$6$。

输入：两个整数$N,K$

输出：一个整数

我的解答：首先确定对于$K$个数，是属于第几个圈，之后确定第$K$个数的行和列，然后计算得到结果。

时间复杂度为$O(\log N)$，如果不考虑计算开方的复杂度可以认为是$O(1)$的。

八、总结

笔试时长一共4个小时，除去高中竞赛之后好像基本没考过这么长的考试了。内容基本上全是智力测试，专业知识（金融知识）的考察基本为零，我觉得毫无准备硬冲基本非常容易一脸懵逼（对就是我）。不知道能不能过笔试（菜狗哭泣）。

Update

我这空了一道大题，编程算法题复杂度还写高了的居然过了笔试，不愧是我。

简介

从以往的实验中可以知道，神经网络中的深度是非常重要的，但是深度越深，网络就越难进行训练。存在Degradetion Problem：随着网络深度增加，训练集上的准确度可能会下降：

这说明并不是所有的网络结构都是好进行优化的。于是这篇论文提出了一种可以构建深层神经网络的结构：将原本的输入与一个浅层网络的输出相加作为最终的输出，然后将这样的结构进行堆叠。

和直接尝试让神经网络去拟合最终期望的函数不同，这里尝试让他去拟合一个残差映射。就好比本来希望得到的函数是$\mathcal{H}(x)$，这里我们让它去拟合一个$\mathcal{F}(x) = \mathcal{H}(x)-x$的映射，这样最终仍然可以得到原本的映射。我们假设这样可以得到相同的最终结果，并且这种结构更容易进行训练。

在极限情况下，可能identity是更优的，那么回是残差趋近于0，整个块就等同于一个非线性函数。在这里可以看做原本的堆叠之上添加了一些短路连接，但是短路连接并不会增加额外的参数和计算复杂度。所以可以认为ResNet最坏的结果只是增加了无用的层数，理论上不会使结果变得更差

论文作者在ImageNet的实验中得到了两个结论：

1. 利用残差连接的深度网络可以很好地进行优化，而直接进行堆叠的普通网络随着层数加深可能会难以收敛
2. 残差网络可以从额外的深度中获得提升，更深的网络可以得到更好地结果。

具体结构

对每一个基本块可以看成这样一个结构：

$\mathbf{y}=\mathcal{F}\left(\mathbf{x},\left\{W_{i}\right\}\right)+\mathbf{x}$

其中$\mathcal{F}\left(\mathbf{x},\left\{W_{i}\right\}\right)$代表的是要被学习的残差映射，后面是一个自映射，期中需要保证残差映射的结果和原本输入的维度是相同的，如果不相同的话，可以考虑通过一个线性的投影$W_{s}$使得维度可以match：

$\mathbf{y}=\mathcal{F}\left(\mathbf{x},\left\{W_{i}\right\}\right)+W_{s} \mathbf{x}$

$\mathcal{F}$的形式是很多样的，但是如果只采用一层Linear，那么实际上用不用这个结构是没区别的，一般的时候是使用一个多层的卷积层来作为残差连接。

代码实现

以下是基于pytorch做的复现，其中对应的网络结构如下所示：

两层的为BasicBlock，三层的为Bottleneck：

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

import torch
import torch.nn as nn

class BasicBlock(nn.Module):
    expansion = 1
    
    def __init__(self, input_channel, channel, stride):
        super(BasicBlock, self).__init__()
        
        self.downsample = lambda x: x
        if(input_channel != channel):
            self.downsample = nn.Sequential(
                nn.Conv2d(in_channels = input_channel, out_channels = channel, kernel_size = 1, stride = stride, bias = False),
                nn.BatchNorm2d(channel)
            )
        
        self.relu = nn.ReLU(inplace = True)
        
        self.convlayers = nn.Sequential(
            nn.Conv2d(in_channels = input_channel, out_channels = channel, kernel_size = 3, stride = stride, padding = 1, bias = False),
            nn.BatchNorm2d(channel),
            nn.ReLU(inplace = True),
            nn.Conv2d(in_channels = channel, out_channels = channel, kernel_size = 3, stride = 1, padding = 1, bias = False),
            nn.BatchNorm2d(channel)
        )
    def forward(self, x):
        out = self.downsample(x) + self.convlayers(x)
        out = self.relu(out)
        return out

class Bottleneck(nn.Module):
    expansion = 4
    
    def __init__(self, input_channel, channel, stride, expansion = 4):
        super(Bottleneck, self).__init__()
        self.expansion = expansion
        output_channel = channel * expansion
        
        self.downsample = lambda x: x
        if(input_channel != output_channel):
            self.downsample = nn.Sequential(
                nn.Conv2d(in_channels = input_channel, out_channels = output_channel, kernel_size = 1, stride = stride, bias = False),
                nn.BatchNorm2d(output_channel)
            )
        
        self.relu = nn.ReLU(inplace = True)
        
        self.convlayers = nn.Sequential(
            nn.Conv2d(in_channels = input_channel, out_channels = channel, kernel_size = 1, stride = 1, bias = False),
            nn.BatchNorm2d(channel),
            nn.ReLU(inplace = True),
            nn.Conv2d(in_channels = channel, out_channels = channel, kernel_size = 3, stride = stride, padding = 1, bias = False),
            nn.BatchNorm2d(channel),
            nn.ReLU(inplace = True),
            nn.Conv2d(in_channels = channel, out_channels = output_channel, kernel_size = 1, stride = 1, bias = False),
            nn.BatchNorm2d(output_channel)
        )
    def forward(self, x):
        out = self.downsample(x) + self.convlayers(x)
        out = self.relu(out)
        return out
    
    
class ResNet(nn.Module):
    def __init__(self, block, block_nums, input_channel, class_num):
        super(ResNet, self).__init__()
        
        self.stacklayers = nn.Sequential(
            nn.Conv2d(in_channels = input_channel, out_channels = 64, kernel_size = 7, stride = 2, padding = 3, bias = False),
            nn.BatchNorm2d(64),
            nn.ReLU(inplace = True),
            nn.MaxPool2d(kernel_size = 3, stride = 2),
            self.make_layers(block = block, input_channel = 64, channel = 64, stride = 1, block_num = block_nums[0]),
            self.make_layers(block = block, input_channel = 64 * block.expansion, channel = 128, stride = 2, block_num = block_nums[1]),
            self.make_layers(block = block, input_channel = 128 * block.expansion, channel = 256, stride = 2, block_num = block_nums[2]),
            self.make_layers(block = block, input_channel = 256 * block.expansion, channel = 512, stride = 2, block_num = block_nums[3]),
            nn.AdaptiveAvgPool2d(1),
            nn.Flatten(),
            nn.Linear(512*block.expansion, class_num)
        )
    
    def make_layers(self, block, input_channel, channel, stride, block_num, expansion = 4, reduction = 16):
        layers = []
        layers.append(block(input_channel, channel, stride))
        input_channel = channel * block.expansion
        for _ in range(1, block_num):
            layers.append(block(input_channel, channel, 1))
        return nn.Sequential(*layers)
    
    def forward(self, x):
        out = self.stacklayers(x)
        return out
    
def ResNet_18(input_channel, class_num = 1000):
    return ResNet(BasicBlock, [2,2,2,2], input_channel, class_num)

def ResNet_34(input_channel, class_num = 1000):
    return ResNet(BasicBlock, [3,4,6,3], input_channel, class_num)

def ResNet_50(input_channel, class_num = 1000):
    return ResNet(Bottleneck, [3,4,6,3], input_channel, class_num)

def ResNet_101(input_channel, class_num = 1000):
    return ResNet(Bottleneck, [3,4,23,3], input_channel, class_num)

def ResNet_152(input_channel, class_num = 1000):
    return ResNet(Bottleneck, [3,8,36,3], input_channel, class_num)
   

Gumbel-Softmax Distribution

考虑$z$是一个定类型的变量，对于每个类型有着概率$\pi_1,\pi_2,\ldots,\pi_k$。考虑到从这个概率分布中的采样可以用一个onehot向量来表示，当数据量很大的时候满足：

$\mathbb{E}_p[z]=[\pi_1,\ldots,\pi_k]$

Gumbel-Max trick 提供了一个简单且高效的来对符合$\pi$这样概率分布的$z$进行采样的方法：

$z = \text{onehot} \left(\arg \max_i [g_i+\log \pi_i]\right)$

其中$g_i$是从Gumbel(0,1)中独立采出的，它可以利用Uniform(0,1)中的采样来计算得到：

$\begin{aligned} u &\sim \text{Uniform}(0,1) \\ g &= -\log(-\log(u)). \end{aligned}$

之后利用softmax来获得一个连续可导对argmax的估计

$\begin{aligned} y_{i}=\frac {\exp \left(\left(\log \left(\pi_{i}\right)+g_{i}\right) / \tau\right)} {\sum_{j=1}^{k} \exp \left(\left(\log \left(\pi_{j}\right)+g_{j}\right) / \tau\right)}\quad \text{for} \ i=1, \ldots, k \end{aligned}$

Gumbel-Softmax分布的概率密度如下表是：

$p_{\pi, \tau}\left(y_{1}, \ldots, y_{k}\right)=\Gamma(k) \tau^{k-1}\left(\sum_{i=1}^{k} \pi_{i} / y_{i}^{\tau}\right)^{-k} \prod_{i=1}^{k}\left(\pi_{i} / y_{i}^{\tau+1}\right)$

可以知道对于温度$\tau$而言，越接近于零，那么从Gumbel-Softmax分布中的采样就越接近onehot并且Gumbel-Softmax分布同原始的分布$p(z)$也更加的相似。

Gumbel-Softmax Estimator

可以发现对于任意的$\tau>0$，Gumbel-Softmax分布都是光滑的，可以求出偏导数$\partial y / \partial \pi$对参数$\pi$。于是用Gumbel-Softmax采样来代替原有的分类采样，就可以利用反向传播来计算梯度了。

对于学习过程中来说，实际上存在一个tradeoff。当$\tau$较小的时候，得到的sample比较接近onehot但是梯度的方差很大，当$\tau$较大的时候，梯度的方差比较小但是得到的sample更平滑。在实际的操作中，我们通常从一个较高的$\tau$开始，然后逐渐退火到一个很小的$\tau$。事实上，对于很多种的退火方法，结果都表现的不错。

Straight-Through Gumbel-Softmax Estimator

对于有些任务需要严格的将其限制为得到的就是离散的值，那么这个时候可以考虑对于$y$来做一个arg max得到$z$，在反向传播的时候利用$\nabla_\theta z \approx \nabla_\theta y$来进行梯度的估计。

即通过离散的方式进行采样，但是从连续的路径进行求导。这个叫做ST Gumbel-Softmax estimator，可以知道，当温度$\tau$较高的时候，这依然可以采样得到离散的采样值。

Related Work

主要总结了一些随机神经网络训练的方法，进行了一个对比。

上图中

1. 正常的无随机节点的梯度下降
2. 存在随机节点的时候，梯度在这个地方不能很好地进行反传
3. 采用log trick绕开随机节点传递梯度
4. 估计梯度进行传播，例如前文提到的ST Estimator
5. 采用重参数化方法，就是这里的Gumbel-Softmax Estimator

Semi-Supervised Generative Models

对于重参数化和log trick就不再多说，这里看一个半监督生成模型的推断。

考虑到一个半监督网络，从带标签数据$(x,y)\sim\mathcal{D}_L$和不带标签数据$x\sim \mathcal{D}_U$中进行学习。

有一个分辨网络（D）$q_\phi(y|x)$，一个推断网络（I）$q_\phi(z|x,y)$，和一个生成网络（G）$p_\theta(x|y,z)$，通过最大化生成网络输出的log似然的变分下界来进训练。

对于带标签的数据，y是观测到的结果，所以变分下界如下：

$\begin{aligned} \log p_\theta(x,y) &\ge \mathcal{L}(x,y)\\ &= \mathbb{E}_{z \sim q_\phi(z|x,y)}[\log p_\theta(x|y,z)] - KL[q_\phi(z|x,y)||p_\theta(y)p(z)] \end{aligned}$

对于无标签数据，重点在于对于离散的分布没有办法进行重参数化，所以这里采用的方法是对于margin out所有类别的y，同样是在$q_\phi(z|x,y)$上面进行推断，得到的变分下界如下所示（有一说一我推的和论文不一样，但我觉得论文里面的公式写错了）：

$\begin{aligned}\log p_{\theta}(x) &\geq\mathcal{U}(x) \\&=\mathbb{E}_{z \sim q_{\phi}(y, z | x)}\left[\log p_{\theta}(x | y, z)+\log p_{\theta}(y)+\log p(z)-\log q_{\phi}(y, z | x)\right] \\&=\mathbb{E}_{z \sim q_{\phi}(y, z | x)}\left[\log p_{\theta}(x | y, z)-\log \frac{q_\phi(z|x,y)}{p_{\theta}(y) p(z)} + \log \frac{q_\phi(z|x,y)}{q_\phi(y,z|x)}\right]\\&=\mathbb{E}_{z \sim q_{\phi}(y, z | x)}\left[\log p_{\theta}(x | y, z)-\log \frac{q_\phi(z|x,y)}{p_{\theta}(y) p(z)} + \log \frac{1}{q_\phi(y|x)}\right]\\&=\sum_{y} q_\phi(y|x)\mathbb{E}_{z \sim q_{\phi}(z | x,y)}\left[\log p_{\theta}(x | y, z)-\log \frac{q_\phi(z|x,y)}{p_{\theta}(y) p(z)} + \log \frac{1}{q_\phi(y|x)}\right]\\&=\sum_{y} q_\phi(y|x)\mathbb{E}_{z \sim q_{\phi}(z | x,y)}\left[\log p_{\theta}(x | y, z)-\log \frac{q_\phi(z|x,y)}{p_{\theta}(y) p(z)}\right] + \sum_{y} q_\phi(y|x)\log \frac{1}{q_\phi(y|x)}\\&=\sum_{y} q_{\phi}(y | x)\mathcal{L}(x, y)+\mathcal{H}\left(q_{\phi}(y | x)\right)\end{aligned}$

最终得到的最大化目标为下面这个式子：

$\mathcal{J}=\mathbb{E}_{(x, y) \sim \mathcal{D}_{L}}[\mathcal{L}(x, y)]+\mathbb{E}_{x \sim \mathcal{D}_{U}}[\mathcal{U}(x)]+\alpha \cdot \mathbb{E}_{(x, y) \sim \mathcal{D}_{L}}\left[\log q_{\phi}(y | x)\right]$

容易发现，前两项一个是针对带标签数据的变分下界最大化，一个是针对无标签数据的最大化，最后一项代表分辨网络的对数似然，其中$\alpha$参数越大，说明越看重分辨网络的能力。是一个在分辨网络和生成网络之间进行tradeoff的参数。

对于这种方法，假设要margin out一共k个类别，那么对每个前向/反向步需要$\mathcal{O}(D+k(I+G))$，但是采用Gumbel-Softmax方法进行重参数化，就可以直接进行反向传播而不需要margin out，时间复杂度降低到了$\mathcal{O}(D+I+G)$，在类别很多的情况下可以有效降低训练的时间复杂度！

准备面试的时候找到了两套C++面试题，做了一下，解答直接写在上面了，放在这里分享出来。感觉难度并不是很高，这是第二套~

A. Show me the code

1. Please create a “String” class to process char strings. This string class should satisfy the following requirements:

• It could be used as an original type like “int” to define variables and support assignment and copy.
• It could be used as the parameter type of a function and the return value type of a function.
• It could be used as the element type of the STL container, e.g., vector/list/deque.

In other words, your “String” class could be used in the following code and be complied successfully by a standard C++ compiler.

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

void foo(String x)
{
}
void bar(const String& x)
{
}
String baz()
{
  String ret("world");
  return ret;
}
int main()
{
  String s0;
  String s1("hello");
  String s2(s0);
  String s3 = s1;
  s2 = s1;
  foo(s1);
  bar(s1);
  foo("temporary");
  bar("temporary");
  String s4 = baz();
  std::vector<String> svec;
  svec.push_back(s0);
  svec.push_back(s1);
  svec.push_back(baz());
  svec.push_back("good job");
}

略，感觉以前写过。

2. Imagine we have a single linked list, please write a function which could remove a specified node in the list.

• Please define the data structure for the list as you need.
• Pass the head pointer to the function.
• Pass the pointer to the node to be removed to the function. Remove the node in the list if it has the same pointer value.

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

struct ListNode{
  int val;
  ListNode* next;
  ListNode(int _val): val(_val){}
};

ListNode* deleteNode(ListNode* head, int val)
{
  if(!head)
    return NULL;
  while(head->val == val)
  {
    head = head->next;
  }
  if(!head)
    return NULL;
  ListNode* pnode = head->next;
  ListNode* prev = head;
  while(pnode)
  {
    if(pnode->val == val)
    {
      prev->next = pnode->next;
      pnode = pnode->next;
    }
    else
    {
      prev = pnode;
      pnode = pnode->next;
    }
  }
  return head;
}

B. Basic Part

1. What are wrong in the following code? Please point out.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

void main()
{
  char a = 'a';
  int b = 0;
  int *pInt1 = &b;
  int c = *pInt1;
  pInt1 = (int*)(&a);
  int *pInt2 = pInt1 + 1;
  int d = *pInt2;
  void *pV = &a;
  // char * pV = &a;
  pV++;	// 对空指针不能最算术运算
  char e = *pV;
}

2. What are wrong in the following code? Please provide your FIX.

Common.h

1
2
3
4
5

int var1;
void foo(int input)
{
  // some code
}

TestA.h

1
2
3
4
5
6
7
8

#include "Common.h"
#include "TestB.h"

class CTestA
{
  private:
    CTestB m_b;
};

TestB.h

1
2
3
4
5
6
7
8

#include "Common.h"
#include "TestA.h"

class CTestB
{
  private:
    CTestA m_a;
};

TestA.cpp

1
2

#include "TestA.h"
// some code

TestB.cpp

1
2

#include "TestB.h"
// some code

提前声明，结构体内部都采用指针而不是实体。

C. STL

1. Errors, inefficiency and potential bugs exsit in the following code, please point them out.

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

int foo(std::map<int, int>& mapIn, std::set<int>& setIn)
{
  std::vector<int> va(10);
  std::vector<int> vb;
  std::copy(va.begin(), va.end(), vb.begin());
  
  //std::vector<int> vb(va);
  
  std::vector<int> vc(100);
  auto iter = va.begin() + 5;
  int varInt = *iter;
  va.push_back(vc.begin(), vc.end());
  varInt = *(++iter);
  if (mapIn[4] == 0)
  {
    // do something 
  }
  auto itVec = std::find(vc.begin(), vc.end(), 100);
  if (itVec != vc.end())
  {
    // do something
  }
  
  //auto itSet = setIn.find(10);
  //Set本来就是有序的结构，利用可以进行二分查找，效率更高
  
  auto itSet = std::find(setIn.begin(), setIn.end(), 10);
  if (itSet == setIn.end())
  {
    // do something
  }
}

2. Please see the following code, TypeA could be either a function pointer or a functor, please try to provide the definition for TypeA in both function pointer way and functor way.

1
2
3
4
5
6

void foo(TypeA processor)
{
  int paraInt = 0;
  const char* pParaStr = "Test";
  int rtn = processor(paraInt, pParaStr);
}

函数指针:

1
2
3
4
5

int function_pointer(int pInt, const char* pStr)
{
		//do something
  	return 0;
} 

函数对象：

1
2
3
4
5
6
7

class functor{
public:
    int operator ()(int pInt, const char * pStr){
				// do something
        return 0;
    }  
};

准备面试的时候找到了两套C++面试题，做了一下，解答直接写在上面了，放在这里分享出来。感觉难度并不是很高，这是第一套~

For your answers, either Chinese or English are OK.

A. Coding

1. Please create a class to represent Int. Only declaration is required. Please give the declaration of all member functions, friend functions, and member variables.

略

2. Imagine we have a single linked list, please write a function which could move a specified node to the tail of the list.

• Please define the data structure for the list as you need.
• Pass the head pointer to the function.
• Pass the pointer of the node to be moved to the function. Move the node to the tail of the list if it has the same pointer value.

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

struct ListNode{
  int val;
  ListNode* next;
  ListNode(int _val): val(_val){}
};

ListNode* deleteNode(ListNode* head, int val)
{
  if(!head)
    return NULL;
  while(head->val == val)
  {
    head = head->next;
  }
  if(!head)
    return NULL;
  ListNode* pnode = head->next;
  ListNode* prev = head;
  while(pnode)
  {
    if(pnode->val == val)
    {
      prev->next = pnode->next;
      pnode = pnode->next;
    }
    else
    {
      prev = pnode;
      pnode = pnode->next;
    }
  }
  return head;
}

B. Read and Answer

1. What are wrong in the following code?

1
2
3
4
5
6
7
8

void foo(short startIndex)
{  
  short buffer[50000] = { 0 };
  for (auto i = startIndex; i < 40000; ++i) 
  {  
    buffer[i] = (char)i;  
  }
}

Because i is short, i < 40000 is always True, the loop NEVER ends.

2. Mark all lines which are wrong and provide the FIX.

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

class CBase
{
public:
    CBase() 
      : m_pVar1(NULL)
    {
        m_pVar2 = new int(4);
    }
    ~CBase()
    {
        delete m_pVar2;
        delete m_pVar1;	// Can't delete NULL pointer
      /*
      *if(! m_pVar1)
      *  delete m_pVal1;
      */
    }
    void Init(int* pVar)
    {
        m_pVar1 = pVar;
    }
private:
    int* m_pVar1;
    int* m_pVar2;
}
class CDerive : public CBase
{
public:
    CDerive(int var) : m_var(var) {};
  //CDerive(){}
    ~CDerive() {};
private:
    int m_var;
}
int main()
{
    CDerive* pDerives = new CDerive[10]; // can't init
    int *pVar = new int(10);
    for (int i = 0; i < 10; ++i)
    {
        pDerive[i].Init(pVar);
    }
    delete pDerives;	// pDerives is an array
  //delete[] pDerives;
    delete pVar;
}

3. The following code could not be compiled, give TWO ways to fix it.

1
2
3
4
5
6
7
8
9
10
11
12
13

class CFoo
{
public:
    CFoo() : m_var(0) {};
    ~CFoo() {};
    bool AddAndCheck() const
    {
        m_var += 5;
        return m_var < 10;
    }
private:
    int m_var;
};