分类目录归档:杂文

运行在裸机上的俄罗斯方块游戏

操作系统课的第一个大实验…

Github:https://github.com/wx-csy/OSLab0-Tetris

因为关于硬件的具体细节都在AM里面封装好了,所以写起来和写正常的程序并没有太大的区别,只是轮子得重新再造一遍…

玩法说明

运行make run,进入游戏。注意,工程的Makefile文件已经被修改,请运行修改过后的Makefile文件。

进入qemu后,首先运行自检程序,并在终端中打印当前机器的基本情况、设备信息和时间信息。随后,播放Splash界面(可按return键跳过)。按C键进入游戏。

左右键控制当前方块的位置,上键顺时针旋转当前方块,下键逆时针旋转当前方块,空格键加速下落。消除单行可获得1分,单次消除2行获得3分,单次消除3行获得5分,单次消除4行可获得8分。其他规则和经典的俄罗斯方块游戏基本一致。由于Wall kick系统尚未实现,诸如L-spin等骚操作暂时无法使用…

主要技术说明

图片和文字

游戏中的图片素材,除ProjectN的logo外,均使用GIMP工具制作。

使用GIMP的export功能,可将图片导出为C源代码格式,然后逐点绘制在屏幕上即可。

文字使用点阵字模。每个ASCII文字的形状以16*8点阵的形式存储在程序中,绘制时根据字模数据逐点绘制即可。

Splash界面的渐变效果

绘制图片时,可以附加一个透明度参数\(\alpha\),使得绘制出的颜色满足下式

\[
\begin{cases}
r = r_f \alpha + r_b (1 – \alpha) \\
g = g_f \alpha + g_b (1 – \alpha) \\
b = b_f \alpha + b_b (1 – \alpha)
\end{cases}
\]

其中\(r_f, g_f, b_f\)为图像颜色的三个分量,\(r_b, g_b, b_b\)为背景色的三个分量。

在播放渐变动画时,只需要将\(alpha\)从0逐渐调整为1,就可实现渐变效果。

Gameover界面的变灰效果

在绘制图片时,还可附加一个颜色矩阵\(M\)。\(M\)是\(3\times3\)的矩阵,用于对颜色的三个分量进行线性变换:

\[
\begin{cases}
r’ = rM_{11} + gM_{12} + bM_{13} \\
g’ = rM_{21} + gM_{22} + bM_{23} \\
b’ = rM_{31} + gM_{32} + bM_{33}
\end{cases}
\]

其中,\(M_I = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}\) 表示恒等变换,
\(M_G = \begin{bmatrix} 0.33 & 0.59 & 0.11 \\ 0.33 & 0.59 & 0.11 \\ 0.33 & 0.59 & 0.11 \end{bmatrix}\)表示灰度变换(即将彩色图片变换为黑白图片)。

这样,只需设置一个混合因子\(\lambda\),并且使用\(\lambda M_G + (1-\lambda)M_I\)绘制图片,同时将\(\lambda\)从0逐渐调整为1,即可实现逐渐变灰的效果。

如何编写缓存友好的代码——从一道卡常数的题目说起

WC2017的第二题是一道卡常三合一题。其中,第一个子任务要求对最多2e8个32位无符号整数排序,时限3s,内存2G。输入采用伪随机数,输出采用hash,从而避免输入输出的影响。

看到题目第一反应是暴力。采用标准库中的sort函数,可以很容易地写出下面的代码

#include <cstdio>
#include <algorithm>
using namespace std;

typedef unsigned uint32_t;

inline uint32_t next_integer(uint32_t &x) {
  x = x ^ (x << 13);
  x = x ^ (x >> 17);
  x = x ^ (x << 5);
  return x;
}

const int n = 200000000;
uint32_t arr[n];

void genarray() {
  uint32_t x = 0x98765432;
  for (int i=0; i<n; i++) arr[i] = next_integer(x);
}

uint32_t output(uint32_t* ptr) {
  uint32_t ret = n * 4;
  uint32_t x = 23333333;
  for (int i=0; i<n; i++) {
    ret ^= ptr[i] + x;
    next_integer(x);
  }
  return ret;
}

int main() {
  genarray();
  sort(arr, arr+n);
  printf("%x\n", output(arr));
  return 0;
}

显然,这段代码是会TLE的。在我的电脑配置下(Intel Core i5-7200U, 8G, Ubuntu 16.04 LTS, 编译参数 g++ -O2 -m32 <source>,下同)一共跑了22.4s。

众所周知,标准库中的sort的复杂度是\(O(n \log n)\)。看来,必须使用线性时间排序才行。计数排序在这边用不了,因为32位无符号整数的取值范围太大了。那么,使用基数排序如何?将每个整数拆分为前16位和后16位,然后先以后16位为key使用计数排序,再以前16位为key使用计数排序,就可以在2倍线性时间内完成整个排序。

// ...
typedef unsigned uint32_t;
typedef unsigned short uint16_t;
typedef unsigned char uint8_t;

union {
  uint32_t u32;
  uint16_t word[2];
} arr[n], arr2[n];

uint32_t cnt[2][65536];

void counting() {
  for (int i=0; i<n; i++) {
    cnt[0][arr[i].word[0]]++;
    cnt[1][arr[i].word[1]]++;
  }
  for (int j=0; j<2; j++) partial_sum(cnt[j], cnt[j]+65536, cnt[j]);
}

void sort0() {
  for (int i=n-1; i>=0; i--)
    arr2[--cnt[0][arr[i].word[0]]].u32 = arr[i].u32;
}

void sort1() {
  for (int i=n-1; i>=0; i--)
    arr[--cnt[1][arr2[i].word[1]]].u32 = arr2[i].u32;
}

int main() {
  genarray();
  counting();
  sort0(); sort1();
  printf("%x\n", output((uint32_t*)arr));
  return 0;
}

这回运行时间为5.2s,比之前快了许多,但仍然不能在时间限制内通过。使用perf工具监测cpu用时,发现sort1和sort0函数是瓶颈,时间占比分别达到了34.37%和33.91%。再监测cache miss数量,发现程序总共发生约6.38亿次cache miss,而sort1和sort0中的占比分别为44.88%和43.74%。考虑基数排序的原理:每一趟基数排序是一次计数排序,对于相同key的元素,它们是在内存中连续放置的,而key不同的元素,则需要随机访问。通常,一趟基数排序的cache hit率可以如下估算:

\[ hit\% = \min\{1,  \frac{\#\text{cache line}}{k}\} * \left( 1 – \frac{\text{size of element}}{\text{size of cache line}}\right) \]

其中,k表示基数排序中基的大小,这里为65536。Intel i5-7200U的cache信息如下:

L1 data cache: 2 x 32 KBytes, 8-way set associative, 64-byte line size
L2 cache: 2 x 256 KBytes, 4-way set associative, 64-byte line size
L3 cache: 3 MBytes, 12-way set associative, 64-byte line size

经过简单的计算发现L3 cache一共只有约5万行,也就是说,这样写连3级缓存都不能充分利用,CPU必须经常花费数倍的时间访问主存,因此效率十分低下。

L1 cache一共只有512行,那么我们将32位整数分为4段,每段8位,然后进行基数排序行不行呢?让我们重新改写一下程序。

// ...

uint32_t cnt[4][256];

void counting() {
  for (int i=0; i<n; i++) {
    cnt[0][arr[i].byte[0]]++;
    cnt[1][arr[i].byte[1]]++;
    cnt[2][arr[i].byte[2]]++;
    cnt[3][arr[i].byte[3]]++;
  }
  for (int j=0; j<4; j++)
    partial_sum(cnt[j], cnt[j]+256, cnt[j]);
}

void sort0() {
  for (int i=n-1; i>=0; i--)
    arr2[--cnt[0][arr[i].byte[0]]].u32 = arr[i].u32;
}

void sort1() {
  for (int i=n-1; i>=0; i--)
    arr[--cnt[1][arr2[i].byte[1]]].u32 = arr2[i].u32;
}

void sort2() {
  for (int i=n-1; i>=0; i--)
    arr2[--cnt[2][arr[i].byte[2]]].u32 = arr[i].u32;
}

void sort3() {
  for (int i=n-1; i>=0; i--)
    arr[--cnt[3][arr2[i].byte[3]]].u32 = arr2[i].u32;
}

int main() {
  genarray();
  counting();
  sort0(); sort1(); sort2(); sort3();
  printf("%x\n", output((uint32_t*)arr));
  return 0;
}

跑下来运行时间为2.7s,能够在时限内通过。使用性能分析工具perf,发现总共只发生了2.5亿次cache miss。虽然经过修改后,理论运行时间变为2倍,但实际运行时间反而减少了将近一半。

CPU在访问主存时,往往需要等待数百个时钟周期。由于burst机制的存在,CPU可以一次性与主存交换大量连续数据,使得cache能够被十分有效的实现。要增加cache的利用率,主要是要提高程序访问数据的空间局部性和时间局部性。将 \(O(n \log n)\) 的排序改为线性时间排序,是一种典型的space-time tradeoff, 如果排序的基数太大,那么count数组会变得很大,排序后的数据在内存中的分布会很散,降低了缓存利用率,这时就可以通过适当降低基数的方式,提高cache利用率,从而达到理论运行时间和cache利用率之间的平衡。