Preparation

Create a new directory where all the files would live.

Install MPI in each node server

http://mpitutorial.com/tutorials/installing-mpich2/

Run hello world.

这里只是简单的把编译程序复制到用户的 home 目录下，然后执行。

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

# replace hello.c with your own source code file name
filename=hello.c
output=hello

master=10.0.0.10
slave1=10.0.0.15
slave2=10.0.0.16
slave3=10.0.0.18

# compile the source code
mpicc -o $output $filename 

# copy the executable file to other slaves
scp $output $USER@$slave1:~/ 
scp $output $USER@$slave2:~/ 
scp $output $USER@$slave3:~/ 

# deploy the program to 4 nodes
mpirun -n 4 -H $master,$slave1,$slave2,$slave3 ./$output

Succinct Data Structure

Succinct: expressed clearly and in a few words. 中文意思就是简洁明了的。首先看一下 wiki 引用对于 succinct data structure 的描述：

In computer science, a succinct data structure is a data structure which uses an amount of space that is “close” to the information-theoretic lower bound, but (unlike other compressed representations) still allows for efficient query operations.

Suppose that Z is the information-theoretical optimal number of bits needed to store some data. A representation of this data is called:

• implicit: if it takes Z+O(1) bits of space,
• succinct: if it takes Z+o(Z) bits of space,
• compact: if it takes O(Z) bits of space.

For example, a data structure that uses 2Z bits of storage is compact, Z + \sqrt{Z} bits is succinct, Z+lgZ bits is also succinct, and Z+3 bits is implicit.

一张图介绍 symbolic 和 hard link。

安装 QEMU

使用 Ubuntu 16.04.

1
2
3
4
5
6

sudo apt install libglib2.0-dev libgcrypt20-dev zlib1g-dev gcc-multilib autoconf automake bison flex
sudo apt install libpixman-1-dev libz-dev libtool libtool-bin libsdl1.2-dev
git submodule update --init dtc
./configure --disable-kvm --target-list="i386-softmmu x86_64-softmmu" # 默认安装到 /usr/local
make -j8
make -j8 install

Software Setup

下载实验材料：

1
2
3
4
5
6
7

athena% mkdir ~/6.828
athena% cd ~/6.828
athena% add git
athena% git clone https://pdos.csail.mit.edu/6.828/2017/jos.git lab
Cloning into lab...
athena% cd lab
athena%

Backgroud

Patricia Tree or Radix Tree or Compact Prefix Tree

A trie that each node which is the only child is merged with its parent.

Adaptive Radix Tree (ART)

The adaptive radix tree is a radix tree variant that integrates adaptive node sizes to the radix tree. One major drawback of the usual radix trees is the use of space, because it uses a constant node size in every level. The major difference between the radix tree and the adaptive radix tree is its variable size for each node based on the number of child elements, which grows while adding new entries. Hence, the adaptive radix tree leads to a better use of space without reducing its speed.