这学期上了一门多核计算的课程，讲到了Cache优化，虽然很久之前就知道各种各样的优化技术，但自己从来没有试过。趁此机会，做了几个实验。主要参考An Overview of Cache Optimization Techniques and Cache。

Cache的作用就是利用数据局部性原理，先预测性的把数据从内存缓存到Cache。参考wiki，i5的L1-Cache的存取周期只有4 clocks，L2是11 clocks。内存则是近百clocks。性能差异显而易见。所以我们要做的就是如何利用这个特点。文章中介绍了6种方法。

Loop Interchange

这是最简单的一种，而且一般不会写出Cache不友好的代码。原理是计算机内存在存储数组时是按行存的，所以如果按行取效率高，按列取就会傻b。所以正确的代码，应该如下这么写。同时，要获得更好的测试效果，应该让M比较大。

int a[N][M] = {0};
void perf_test(int sum) 
{
    int i, j;
    for (i=0; i<N; ++i) {
        for (j=0; j<M; ++j) {
            sum += a[i][j];
        }
    }

    return;
}

int a[N][M] = {0};

void perf_test(int sum)

{

int i, j;

for (i=0; i<N; ++i) {

for (j=0; j<M; ++j) {

sum += a[i][j];

}

return;

}

Loop Fusion

这个的原理也很好理解，比如有如下代码。b[i]分别在一个循环里面读写，这样显然利用cache的优势。如果把下面的循环分成两部分，分别计算 b[i] = a[i] + 1; c[i] = b[i] * 2; ，那效率显然低下，我会有测试结果。

void perf_test() 
{
    int i;
    for (i=0; i<N; ++i) {
        b[i] = a[i] + 1;
        c[i] = b[i] * 2;
    }
    return;
}

void perf_test()

{

int i;

for (i=0; i<N; ++i) {

b[i] = a[i] + 1;

c[i] = b[i] * 2;

}

return;

}

Loop Blocking

这是主要用在矩阵里，比如矩阵乘法，不可避免的两个矩阵中有一个不是按行取的，导致缓存性能差。解决方法是按块计算，如下图所示。

下面的例子用了比较简单的算法，可以参考。这个性能的提高也是能目测的，见测试。

void perf_test() 
{
    int i, j, ii, jj;
    for (i=0; i<N; i+=B) {
        for (j=0; j<N; j+=B) {
            for (ii=i; ii<MIN(i+B-1, N); ++ii) {
                for (jj=j; jj<MIN(j+B-1, N); ++jj) {
                    b[jj][ii] = a[ii][jj] + 1;
                }
            }
        }
    }
    return;
}

void perf_test()

{

int i, j, ii, jj;

for (i=0; i<N; i+=B) {

for (j=0; j<N; j+=B) {

for (ii=i; ii<MIN(i+B-1, N); ++ii) {

for (jj=j; jj<MIN(j+B-1, N); ++jj) {

b[jj][ii] = a[ii][jj] + 1;

}

return;

}

Inter-array Padding

这个优化不针对数据的存取方式，而是数据在内存中的分布方式。比如现在有两个数组，都比较小如1024个int。然后可能映射到同一个cache块，导致相互读取的时候不断刷新cache，自然导致性能不好，解决方法是，放置一个padding的数组在这两个数组中间。这个比较难测试，性能优化也不是很突出。

double a[N] = {0};
double pad[800];
double b[N] = {0};

double a[N] = {0};

double pad[800];

double b[N] = {0};

Array Merging

这个比较有意思，也比较难理解。原算法是有两个数组，假设要统计分别相加的和。如下

int perf_test(int *A, int *B, int sum) 
{
    int i,j;
    for (i=0; i<N; ++i) {
        A[i] += (A[i] + B[i]);
    }

    return sum;
}

int perf_test(int *A, int *B, int sum)

{

int i,j;

for (i=0; i<N; ++i) {

A[i] += (A[i] + B[i]);

}

return sum;

}

那么问题在哪？就是A，B都比较小时，这种做法会产生两次cache miss，所以要优化。优化有好几种，比如用一个结构体或者用个二维数组。这测试还是有点麻烦的，因为比较一次miss和两次miss这个时间差太小了，所以要多次。多次的话又要每次清空cache，所以只能动态分配数组。二维数组的代码如下。

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

#define N  1024
#define ITER    1000000

int perf_test(int (*A)[2], int sum) 
{
    int i,j;
    int *tmp;
    for (i=0; i<N; ++i) {
        tmp = A[i];
        sum += (tmp[0] + tmp[1]);
    }

    return sum;
}

int main ( int argc, char *argv[] )
{
    int i;
    int (*A)[2];
    int sum = 0;
    for (i=0; i<ITER; ++i) {
        A = malloc(N * sizeof(*A));
        sum += perf_test(A, sum);
        free(A);
    }
    printf("%d\n", sum);
    return EXIT_SUCCESS;
}

#include <stdio.h>

#include <stdlib.h>

#define N 1024

#define ITER 1000000

int perf_test(int (*A)[2], int sum)

{

int i,j;

int *tmp;

for (i=0; i<N; ++i) {

tmp = A[i];

sum += (tmp[0] + tmp[1]);

}

return sum;

}

int main ( int argc, char *argv[] )

{

int i;

int (*A)[2];

int sum = 0;

for (i=0; i<ITER; ++i) {

A = malloc(N * sizeof(*A));

sum += perf_test(A, sum);

free(A);

}

printf("%d\n", sum);

return EXIT_SUCCESS;

}

Array Transpose

这相当于loop interchange，就是把A[N][M]换成A[M][N]。因此我没有进行测试。

测试结果

我使用perf工具，稍微进行了几个技术的测试，其中有cache miss和miss rate，我从结果来看是miss rate会影响性能，但是直观来说应该是cache miss会影响性能。为了保证结果的真实性，我就放了miss rate的比较结果。当然还有加速比，如下面两张图所示，感觉还是比较符合实际的。

除了cache优化外，还有很多优化技术，看来写程序还有很长的路要走啊。但是也不用太在意，因为现在编译器太牛b。gcc -O2 绝对是满足需求的，可以自己测试下，这性能没法比。这从我写的一个很简单的程序就可以看出，但是也应该注意自己的编码习惯。

已经1个多月没有更新了，上个月突然就事情多了。比如开学交报告，面试工作，然后就是保研了。当然还有其他事，简直麻烦。现在成了保研狗，之前还信誓旦旦说要工作，现在仔细想想，确实现在准备还不充分，1写代码能力还很差，2没有在某个专业有很深的研究。所以还得在读研期间好好学习。

SSH在Linux下，是个绝好的东西。因此很有必要进一步掌握它，而不仅仅是只会ssh登录主机。我直接就看了一本书，叫SSH: The Secure Shell The Definitive Guide。我在这里介绍一点其中的精华和比较实用的技巧以及一些SSH高级特性，详细的还得参考书籍。

escape sequences

这是我之前从来没有听说过的，但是却很好用，所以看书还是很有用的。在ssh中同样有转义字符，通常是~。可以在登录ssh后，按下 ~? 来查看用法，会出现以下内容：

Supported escape sequences:
 ~.   - terminate connection (and any multiplexed sessions)
 ~B   - send a BREAK to the remote system
 ~C   - open a command line
 ~R   - request rekey
 ~V/v - decrease/increase verbosity (LogLevel)
 ~^Z  - suspend ssh
 ~#   - list forwarded connections
 ~&   - background ssh (when waiting for connections to terminate)
 ~?   - this message
 ~~   - send the escape character by typing it twice
(Note that escapes are only recognized immediately after newline.)

Supported escape sequences:

~. - terminate connection (and any multiplexed sessions)

~B - send a BREAK to the remote system

~C - open a command line

~R - request rekey

~V/v - decrease/increase verbosity (LogLevel)

~^Z - suspend ssh

~# - list forwarded connections

~& - background ssh (when waiting for connections to terminate)

~? - this message

~~ - send the escape character by typing it twice

(Note that escapes are only recognized immediately after newline.)

我觉得最有用的是 ~^Z ，可以暂时挂起ssh连接，可以使用jobs查看效果，然后fg，重新连接。

ssh-config

直接 man ssh_config ，就能获取大量有用配置。想想现在我有7、8台主机，我还要记IP什么的，很麻烦。最初的做法是用alias，后来发现真是弱爆了。这个只能用来登录什么的，scp就没办法了。使用ssh-config只要创建一个 ~/.ssh/config 文件，然后怎么配置就可以看man，或者参考Simplify Your Life With an SSH Config File。以下是个例子：

# my mobile phone
Host  cm
        port 19922
        HostName the-ip-address
        User root
        IdentityFile /home/york/.ssh/id_rsa

# aws
Host aws
        HostName the-ip-address
        User ubuntu
        Compression yes
        CompressionLevel 2
        IdentityFile /home/york/.ssh/RH-Hadoop.pem

# my mobile phone

Host cm

port 19922

HostName the-ip-address

User root

IdentityFile /home/york/.ssh/id_rsa

# aws

Host aws

HostName the-ip-address

User ubuntu

Compression yes

CompressionLevel 2

IdentityFile /home/york/.ssh/RH-Hadoop.pem

这样就方便多了，无论scp还是ssh，都能直接使用 ssh aws ，如此简洁的命令。

ssh-keygen

我相信很多人的密钥都没有密码，什么意思呢？就是ssh host时，不需要输入密码。其实这是很不安全的。当然现在还来得及补过，只要 ssh-keygen -p -f .ssh/id_rsa 就能在原key的基础上加上一个密码。以下还有一些关于ssh-keygen的用途：

ssh-keygen -l -f ~/.ssh/known_hosts 查看本机登录的主机及其指纹
ssh-keygen -f .ssh/id_rsa.pub -e -m pem > .ssh/id_rsa_pub.pem 生成pem格式的公钥

ssh-agent

确实id_rsa有密码有时会很不方便，这时可以用ssh-agent解决。我还没有意识到这个问题，所以还没怎么使用，有兴趣的可以参考ssh-agent

scp

这也是非常有用的命令，结合ssh config，我最常用的命令一共3条。

scp aws:text1 text1 从服务器上cp到本机
scp text2 aws:text2 从本机cp到服务器
scp -rp aws:/home/ubuntu ./ubuntu cp目录并保持权限

exec command

有时登录ssh，只是为了运行一个命令，那么可以简单直接运行。最简单的是 ssh aws ls -al ，当然也有在本地运行命令，然后保存结果到服务器。如 ls -la | ssh aws 'cat > test' 。如果运行的命令比较复杂，则可以通过linux常用方法批量运行。

ssh aws << EOF
> uname -a
> ls -la
> EOF

ssh aws << EOF

> uname -a

> ls -la

> EOF

X11

ssh也支持图像化(X11)，首先要在服务器端启用X11 forwarding，当然还要有相应的库。本机执行 ssh -Y aws ，然后试试xterm看看有没有图像，然后接着操作其他高级的图像界面。为了安全起见，最好不要启用X11，实在要用也可以使用vnc。

有时为了远程运行一个图形界面的程序，并且ssh退出后不打断图形程序的运行。比如运行一个bt程序。首先要 export DISPLAY=:0 ，表明使用远程主机的DISPLAY (简单来说，DISPLAY会被设置为localhost:10.0，类似的。10表示监听端口为6000+10，0表示第一个screen，远程主机将图形信息发送的6010,ssh则负责转发到本地)，然后使用nohup，如 nohup vuze &

forwarding

这也是ssh不得不说的吊功能。不但可以用来加密，还可以用来穿透防火墙，或者说翻墙。具体有local forwarding，remote forwarding，dynamical forwarding。具体看前一篇，DNS配置。

match

如果有个用户比较特别，允许其用密码登录，其他不能用密码登录。Match就能发挥作用了。详细查看man ssh_config. 简单最常用的配置如：

Match User socks
        PasswordAuthentication yes

1 2	Match User socks PasswordAuthentication yes

注意match下的规则，是从match下一直结束或者遇到下一个match，小心操作，登不上去就麻烦了。

subsystem

这是ssh的特性之一。最常用的是sftp。然后又发展出sshfs，就是以ssh形式挂载远程文件目录。这体验跟网速延迟有很大关系。延迟小网速快，体验就非常好，跟本地磁盘差不多。简单用法: sshfs -o IdentityFile=/home/york/.ssh/RH-Hadoop.pem ubuntu@54.64.60.106: ~/tmp 其他可以参考sshfs.

这个功能在局域网里简直算吊炸。比如我远程挂载了一个目录/opt，里面有matlab。我就可以在本地执行matlab了。爽不爽。

restart

为了使配置生效，必须重启sshd。这个很讨厌，如果不小心配置错了，登不了服务器就麻烦了。如果能不打断连接的情况下，重启sshd就好了。这点开发者早就想到了。可以用如下命令重启。

kill -HUP pid
sudo kill -HUP $(cat /var/run/sshd.pid)

1 2	kill -HUP pid sudo kill -HUP $(cat /var/run/sshd.pid)

reverse ssh

如果你有一台内网机器A（外网无法直接ssh到A），但有一台外网机器B（可以从A直接ssh连接到B），当你要在外网ssh连接A时，就是reverse ssh的用武之地。具体如下：

# from A to B, add a listen port 20002 on B (localhost is relative to B)
# port 22 is ssh listen port of A
ssh -R 20002:localhost:22  B 

# from B to A
ssh -p 20002 localhost

# from A to B, add a listen port 20002 on B (localhost is relative to B)

# port 22 is ssh listen port of A

ssh -R 20002:localhost:22 B

# from B to A

ssh -p 20002 localhost

其中20002端口可以设置成任意其他空闲端口。perfect!

链接：

我很高兴有人通过博客联系我。我之前没有外链，纯粹通过搜索引擎。有人能到这里就说明我的内容还是有用的，这也是写博客的动力之一。现在我决定分享到g+和twitter，虽然也没有多少好友。

月份：2014年10月

Cache优化

Loop Interchange

Loop Fusion

Loop Blocking

Inter-array Padding

Array Merging

Array Transpose

测试结果

实用SSH

escape sequences

ssh-config

ssh-keygen

ssh-agent

scp

exec command

X11

forwarding

match

subsystem

restart

reverse ssh

近期文章

近期评论

分类目录