You tell me I'm wrong. Then you'd better prove you're right.

2014-03-11
简单易懂的XML parsing

读取一个XML文件,返回一个DOM对象。

什么是DOM对象?全称为Document Object Model, XML文件中的每一个东西都对应为一个node。DOM node的属性和方法遵循国际互联网的标准。

有以下类型的nodes:

  • Element nodes* Text nodes 每一个Text node都是Element node的child
  • Attribute nodes 不是任何node的parent 或 child,从属于element node
  • Comment nodes* Document nodes 只有使用document node的方法才能创造新element, text, attribute, comment

现有以下xml文档:

1
2
3
4
5
6
7
8
9
<listitem>
<label>Import Wizard</label>
<callback>uiimport</callback>
<icon>ApplicationIcon.GENERIC_GUI</icon>
</listitem>
<listitem>
...
</listitem>
...

其中的一个label标签有字符Plot Tools。假设你想在同样的listitem里面寻找callback标签的字符:

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
findLabel = 'Plot Tools';
findCbk = '';
xDoc = xmlread(fullfile(matlabroot, ...
'toolbox','matlab','general','info.xml'));
allListitems = xDoc.getElementsByTagName('listitem');
for k = 0:allListitems.getLength-1
thisListitem = allListitems.item(k);

% Get the label element. In this file, each
% listitem contains only one label.
thisList = thisListitem.getElementsByTagName('label');
thisElement = thisList.item(0);
% Check whether this is the label you want.
% The text is in the first child node.
if strcmp(thisElement.getFirstChild.getData, findLabel)
thisList = thisListitem.getElementsByTagName('callback');
thisElement = thisList.item(0);
findCbk = char(thisElement.getFirstChild.getData);
break;
end

end

if ~isempty(findCbk)
msg = sprintf('Item "%s" has a callback of "%s."',...
findLabel, findCbk);
else
msg = sprintf('Did not find the "%s" item.', findLabel);
end
disp(msg);

MATLAB本身就提供一个xmlread函数,其返回的是Document Node。根节点哦。其余与Document Node的函数都是标准已经定义了的,这个标准详情请见这里.在上面一段代码中,我们可以看见几个常用的API:

  • getElementsByTagName是Document Node的方法,返回一个list。
  • 这个list是node的列表,要得到其中一个元素,需要调用list的item方法。
  • 一个有child的element node,获得其内容,要调用getFirstChild.getData

如果我们想写一个XML文档:

1
2
3
4
5
6
7
8
9
<?xml version="1.0" encoding="utf-8"?>
<toc version="2.0">
<tocitem target="upslope_product_page.html">Upslope Area Toolbox<!-- Functions -->
<tocitem target="demFlow_help.html">demFlow</tocitem>
<tocitem target="facetFlow_help.html">facetFlow</tocitem>
<tocitem target="flowMatrix_help.html">flowMatrix</tocitem>
<tocitem target="pixelFlow_help.html">pixelFlow</tocitem>
</tocitem>
</toc>

MATLAB代码如下:

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
docNode = com.mathworks.xml.XMLUtils.createDocument('toc');

toc = docNode.getDocumentElement;
toc.setAttribute('version','2.0');

product = docNode.createElement('tocitem');
product.setAttribute('target','upslope_product_page.html');
product.appendChild(docNode.createTextNode('Upslope Area Toolbox'));
toc.appendChild(product)

product.appendChild(docNode.createComment(' Functions '));

functions = {'demFlow','facetFlow','flowMatrix','pixelFlow'};
for idx = 1:numel(functions)
curr_node = docNode.createElement('tocitem');

curr_file = [functions{idx} '_help.html'];
curr_node.setAttribute('target',curr_file);

% Child text is the function name.
curr_node.appendChild(docNode.createTextNode(functions{idx}));
product.appendChild(curr_node);
end

xmlwrite('info.xml',docNode);
type('info.xml');
  • 这个函数首先先创建出一个Document Node,也就是最重要的根节点;
  • SetAttribute是Element Node的方法;
  • element, text, attribute, comment只能由docNode创建,方法是createXXXNode
  • Element Node间的父子关系由appendChild确定。

以上就是MATLAB里面处理XML文档的最基本知识。由于XML文档的处理方式是统一的,因此很容易就能拓展到其他语言。从代码中就可以挖掘出许多东西。在实际中,要使用到的XML API恐怕还远远不够。这篇文章只是作为一个入门性质的导引。

2014-02-04
简单易懂的Sublime Text 2

由于这几天一看见Python自带的IDLE我就作呕,我觉得很有必要花点时间研究一下Sublime Text 2

为什么要用Sublime Text 2?其实我也不知道。我第一次知道这个编辑器是在Azure的培训上。后来我发现,许多专业人士都非常推崇此编辑器。Sublime Text 2在Windows、Mac和Linux下都有相应的版本。

如果你去看Sublime Text 2的主页,你会发现这个编辑器的最大优点就是多光标编辑。没有其他任何一个编辑器能做到这一点。

下面,我把Sublime的文档简要翻译了一下,权作参考。如果没有特殊说明,下面都是在Windows平台下操作。

大规模行选择

multiple line selecting
方法一:Shift+右键拖动,或按下中键拖动。
如果要额外添加一行光标,使用Ctrl+左键选择。(虽然文档上说Alt是撤销一行光标,但是我从来都没试成功过)
方法二:使用键盘:Ctrl+Alt+Up向上选择,Ctrl+Alt+Down向下选择。

多重选择

选择块区域并分裂成多行

选择一个块区域,然后按下Ctrl+Shift+L,可把一整块的选择区域分成每一行一块的选择区。

快速添加下一相同区域

我们在文字编辑器里会有相同的变量名,如果我们的光标在其中一个变量名之上,按下Ctrl+D,整个变量名就会被选择。
如果再按下Ctrl+D,下一个相同的变量名也会被选择。
multiple block selecting

一起选定所有相同区域

光标在变量名上,按下Alt+F3

退回到单个选择模式

按下Esc

自动补全

自动补全是自动开启的,设置在Preferences/Settings-Default里面,有个”auto_complete”。
如果当前弹出窗没有弹出,可以按下Ctrl+空格,强制显示当前可补全选项。不会引发输入法吗,我想。
在HTML文档里,’<’键是触发自动补全的按键。

Tab补全

Tab补全是自动开启的,有个”tab_completion”的选项。
如果当前的补全结果并非为我所愿,可以按下Ctrl+空格,显示补全选框。
如果按下Tab不想补全而是写下制表符,可以按下Shift+Tab。

不受干扰模式

这种模式跟全屏模式还有些区别。
View/Enter Distraction Free Mode打开此模式。或直接按Shift+F11。
设置不受干扰模式:与上文不同,路径在_Preferences/Settings - More

1
2
3
4
5
6
7
8
{  
"line_numbers": false,
"gutter": false,
"draw_centered": true,
"wrap_width": 80,
"word_wrap": true,
"scroll_past_end": true
}

这是一个设置样本。特别注意的是”wrap_width”这个选项,这个选项之大小决定了该模式下的编辑宽度。

Vintage Mode

这个是Vi模式。此模式在默认状态下是关闭的,你需要做的是将其从ignored-packages中去除。编辑"ignored_packages": ["Vintage"] "ignored_packages": []即可。

Vintage模式默认状态是insert mode。如有不适请添加如下一行:

1
"vintage_start_in_command_mode": true

需要注意的是,Vintage模式下的insert模式是Sublime正常工作的模式,在此情况下的vi快捷键不可用。而且Ex模式也不可用。

Ctrl快捷键与Sublime冲突,默认关闭。如需启用,请打开

1
"vintage_ctrl_keys": true

Projects

在Sublime Text 2中,Projects由两个文件组成:

  • Sublime Project File:定义Project,需要加入版本控制;* Sublime-workspace file:用户的数据。

Sublime-Project File是一个JSON文件,顶层分三大部分:Folders明确包含的文件,Settings会覆写用户设置,还有Build_systems。

2014-01-26
Permalink 404 Error 之解决方案

Ike本人在设置wordpress的时候,在settings里面发现了Permalink。从这个页面的主要介绍来看,Permalink的作用就是自定义文章的Link,使之更为结构化和友好。

但是当Ike设置了某个除Default之外的某个Permalink的时候,如果点击一篇发表的文章,就会出现Page Not Found的404错误。

经反复查证,Ike发现Permalink与.htaccess和Apache的设置紧密相关。

如果我们在Settings页面的Permalink中就某个选项进行了保存,wordpress在后台就会改写.htaccess:

1
2
3
4
5
6
7
8
9
10
# BEGIN WordPress
<IfModule mod_rewrite.c>
RewriteEngine On
RewriteBase /blog/
RewriteRule ^index\.php$ - [L]
RewriteCond %{REQUEST_FILENAME} !-f
RewriteCond %{REQUEST_FILENAME} !-d
RewriteRule . /blog/index.php [L]
</IfModule>
# END WordPress

这个.htaccess文件是存放在网页的根目录下的,和wp-config.php存放的位置一样。如果wordpress不能改写此文件,则需要手动改写,但需要注意到的是Ike本人的网页是放在/blog文件夹下的,如果放在别的文件夹下,正确的.htaccess内容可能和上面不一样。

如果成功改写.htaccess,只是成功了一半。因为Ike本人发现即使赋予了后台改写.htaccess的权限,还是不能访问。

有文献报道指出,Apache需要使能rewrite_module才能使得Permalink正常工作。这就需要改写Aapche的配置文件。

运行以下命令:

1
sudo find / -type f -iname "httpd.conf"

找到Apache的配置文件的位置。据相关文献报道,需要做的是将

1
#LoadModule rewrite_module modules/mod_rewrite.so

的注释去掉。

但甚为坑爹的是,Ike发现虚拟机上的Apache配置文件本来就没有把这一行给注释掉。

经过一番查证,这里一篇帖子为我们给出了解决方案的暗示。于是Ike在配置文件下找到了如下若干行:

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
#
# Each directory to which Apache has access can be configured with respect
# to which services and features are allowed and/or disabled in that
# directory (and its subdirectories).
#
# First, we configure the "default" to be a very restrictive set of
# features.
#
<Directory />
Options FollowSymLinks
AllowOverride All
</Directory>

...

#
# Possible values for the Options directive are "None", "All",
# or any combination of:
# Indexes Includes FollowSymLinks SymLinksifOwnerMatch ExecCGI MultiViews
#
# Note that "MultiViews" must be named *explicitly* --- "Options All"
# doesn't give it to you.
#
# The Options directive is both complicated and important. Please see
# http://httpd.apache.org/docs/2.2/mod/core.html#options
# for more information.
#
Options Indexes FollowSymLinks

#
# AllowOverride controls what directives may be placed in .htaccess files.
# AllowOverride controls what directives may be placed in .htaccess files.
# It can be "All", "None", or any combination of the keywords:
# Options FileInfo AuthConfig Limit
#
AllowOverride All

按照上面配置,再重启Apache即可。大功告成。

2014-01-26
坡道的起点——AWS上Wordpress建站小记

经过若干天的反复瞎搞,这个名为”Pursuing Freedom”的博客终于上线了。

建立一个个人博客本来不是难事,只要你肯花钱。国内国外本来就有很多主机提供商,而且有些还是提供注册域名、服务器搭建的一条龙服务。但是Ike酱认为,有钱首先应该花在手办上,其他的能省就省~上个学期接受了一个Azure的培训,从那个培训中Ike酱得知现在云服务可以做很多事情。而且亚马逊的AWS在一定的使用范围内是免费的,这就提供了无限多的可能构造一个自由定制的主页。下面Ike将会把这次建站的各个方面记录一下,供以后参考。

首先我们从AWS讲起。AWS全称Amazon Web Services。和Windows Azure一样,AWS提供了一系列云解决方案。在注册AWS用户的一年时间之内,可以在限定的范围内,免费使用AWS的部分服务。有关这些详情,请参考How Do I Get Started with the Free Usage Tier?

有必要强调一点的是,注册AWS的账号需要一张国际信用卡。对于弊校学生来说,这还是一件比较容易办得到的事情,因为Ike常常见到食堂附近有建行的人在接受集体办卡。(Ike能说Ike拿到这个信用卡之后的第一件事就是开通了AWS账号么)

建站的过程其实很简单,因为AWS的Documention上已经把步骤都写好了。概要地说,就是使用AWS EC2建立一台虚拟机,进行安全和账户控制,然后在这个虚拟机上安装各式各样的东西~怎样建立一个虚拟机的Instance,怎样通过远程终端连接上去,怎样配置Apache+PHP+MySQL,其实我不是Linux的专家,但是Amazon EC2 User Guide上面都说得一清二楚。别看文档有600页,其实建立个人博客只要前几页就够了。

在这里整理一下,我参考文档的顺序是:
1. Getting Started with AWS
2. Getting Started with AWS Free Usage Tier
3. Amazon EC2 User Guide
我并不想把这里面的内容再抄一遍放在这里来,说实在的,这一建站步骤唾手可得。

在完成wordpress博客的创建之前,如果有任何问题,都可以归结到文档步骤没有仔细遵循的原因上。总体而言,建立wordpress博客的步骤要比Windows Azure复杂,但是也可以说Windows Azure忽略了许多重要的东西。

但是,在建立了这个wordpress博客、并可以访问之后,是否说明真的可以用了呢?其实后续还有许多复杂的事情要做。

首先就是虚拟机的权限设置问题。在EC2 UG里面,我们给虚拟机创建了一个名为www的group,理由是可以让ec2-user获得对/var/www/的修改权限。但是在实际中,光给ec2-user一个用户这些权限还不够。Wordpress程序可以进行插件的自动安装和自动更新,如果apache拿不到这些权限,Wordpress的更新和拓展都很麻烦。理论上说我们可以每次都登录虚拟机用ec2-user做这些事情,但这样大大提高了博客的使用门槛。

其次,在UG里面没有提到ftp的设置。ftp会给个人网站的部署和更新带来很大便利。wordpress进行更新也需要用到ftp。

关于这两个问题,我给ftp的user和服务器apache都加入到用户组www中,确认网站的根目录下对www都有读写权限。关于ftp的部署,我主要参考了AWS EC2上架设 FTP

但是真正麻烦的,是Wordpress服务器经常连接不上数据库的问题。虽然wp-config.php里面的参数都配置正确,但就是无法连接。这个博客其实是第三代博客,就是因为这个问题。一种可能的解决方案是重启虚拟机,但是发现有时候不可行。这个问题Ike参考了许多中外网站,总的来说都不适用。博客所维持时间的长短几乎就取决于什么时候出现这个数据库的问题。

Ike对Linux只是略知皮毛,连鸟哥私房菜第一卷都没看完的战五渣,上面这些问题的解决真的是瞎搞,所以要是把详细的步骤写出来反而有误人子弟之嫌。所以说,建立了这个博客只是站在长长的坡道的起点,以后还要建设邮件系统之类的东西,还要有个像模像样的主页面,但在当前看来最重要的是把MySQL学会。

域名的注册是在Godaddy上注册的,原来想用ikely.cc以暗示真名,或是ike.ly,但是.me的域名实在是便宜,10刀一年。域名前面原来有www,要去掉www很简单,只要在Godaddy的域名转发里面设置子域名转发就可以了。

2013-07-20
关于 CUDA 中 reduction 运算的优化

最近在Udacity上学习有关基于CUDA的并行运算。在学习当中除了Udacity上面所给的资源以外,我本人还查找了很多其他资料。我计划把我所查找到的这些资料写成技术blog,以供以后查阅。

在Unit 3当中,讲到了三种常见的并行运算:reduce、scan和histogram。简单地讲,reduce运算的输入是一个数据集,和一个运算符(二值,结合性),输出为一个数据,其为数据集中的数据依次与运算符相作用后的结果,如求和、求最大值、求最小值都是reduce. Scan运算的输入是一个数组,一个二值运算符和一个identity element. 这个identity element正如0之于加,1之于乘。常见的scan运算为求累积概率。当然我这种说法很不科学,只要能意会就行了。

最常见的reduce算法就是利用了完全二叉树的结构,分两步完成:

对于这一算法的实现,文献[1]以七种算法的逐级演进说明了reduce的优化过程。下面主要讲讲这个优化思想和过程。

首先一种是二叉树结构的直接实现算法,interleaved addressing:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
__global__ void reduce0(int *g_idata, int *g_odata) {
extern __shared__ int sdata[];

// each thread loads one element from global to shared mem
unsigned int tid = threadIdx.x;
unsigned int i = blockIdx.x*blockDim.x + threadIdx.x;
sdata[tid] = g_idata[i];
__syncthreads();

// do reduction in shared mem
for(unsigned int s=1; s < blockDim.x; s *= 2) {
if (tid % (2*s) == 0) {
sdata[tid] += sdata[tid + s];
}
__syncthreads();
}

// write result for this block to global mem
if (tid == 0) g_odata[blockIdx.x] = sdata[0];
}

对于红字那一段,高度分支结构会导致性能下降,因此利用strided index将其修改成非分支结构:

1
2
3
4
5
6
7
for (unsigned int s=1; s < blockDim.x; s *= 2) {
int index = 2 * s * tid;
if (index < blockDim.x) {
sdata[index] += sdata[index + s];
}
__syncthreads();
}

由于偶数strided index会产生bank conflicts(以后会讲什么是bank conflicts),我们将其改进为sequential addressing:

1
2
3
4
5
6
for (unsigned int s=blockDim.x/2; s>0; s>>=1) {
if (tid < s) {
sdata[tid] += sdata[tid + s];
}
__syncthreads();
}

Sequential addressing中,红字凸显的部分说明有一半的线程在第一循环迭代的时候就处于空闲状态。为了改进,我们采用first add during load技术。简单地说,我们采用上述过程一半的block,在刚进入线程的时候就进行一次operation,具体实现如下:

1
2
3
4
5
6
// perform first level of reduction,
// reading from global memory, writing to shared memory
unsigned int tid = threadIdx.x;
unsigned int i = blockIdx.x*(blockDim.x*2) + threadIdx.x;
sdata[tid] = g_idata[i] + g_idata[i+blockDim.x];
__syncthreads();

我认为将代码优化到这一地步已经足够了,但是令我惊讶的是,文献[1]进行了如下分析:当前代码的带宽仍没有达到GPU的上限,究其原因,由于对于核心运算的不是存储、运算的辅助性指令造成了代码的瓶颈,代码没有达到最大性能。解决的办法就是拆开循环。

分析指出,当s<=32时,有效线程减少至一束(wrap)。一束线程是SIMD(单指令多数据) synchronous的。这就意味着s<=32时不需要__syncthreads()和if (tid < s)。因此,我们可以拆解最后六个循环:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for (unsigned int s=blockDim.x/2; s>32; s>>=1)
{
if (tid < s)
sdata[tid] += sdata[tid + s];
__syncthreads();
}
if (tid < 32)
{
sdata[tid] += sdata[tid + 32];
sdata[tid] += sdata[tid + 16];
sdata[tid] += sdata[tid + 8];
sdata[tid] += sdata[tid + 4];
sdata[tid] += sdata[tid + 2];
sdata[tid] += sdata[tid + 1];
}

值得注意的是,这减少了所有线程束的无用功,而不仅仅是最后一个线程束。

进一步地,该文献还指出,在已知迭代数的情况下,可以完全拆解循环。在只讨论二的n次方大小的数组时,我们通过模板,给出blocksize,就可以给出一个通用的reduce算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if (blockSize >= 512) {
if (tid < 256) { sdata[tid] += sdata[tid + 256]; } __syncthreads();
}
if (blockSize >= 256) {
if (tid < 128) { sdata[tid] += sdata[tid + 128]; } __syncthreads();
}
if (blockSize >= 128) {
if (tid < 64) { sdata[tid] += sdata[tid + 64]; } __syncthreads();
}
if (tid < 32) {
if (blockSize >= 64) sdata[tid] += sdata[tid + 32];
if (blockSize >= 32) sdata[tid] += sdata[tid + 16];
if (blockSize >= 16) sdata[tid] += sdata[tid + 8];
if (blockSize >= 8) sdata[tid] += sdata[tid + 4];
if (blockSize >= 4) sdata[tid] += sdata[tid + 2];
if (blockSize >= 2) sdata[tid] += sdata[tid + 1];
}

函数声明变为:

1
2
template <unsigned int blockSize>
__global__ void reduce5(int *g_idata, int *g_odata)

最后,文献指出,通过算法级联的思想,可以把上文中first add during load变成multiple add.

1
2
3
4
5
6
7
8
9
unsigned int tid = threadIdx.x;
unsigned int i = blockIdx.x*(blockSize*2) + threadIdx.x;
unsigned int gridSize = blockSize*2*gridDim.x;
sdata[tid] = 0;
while (i < n) {
sdata[tid] += g_idata[i] + g_idata[i+blockSize];
i += gridSize;
}
__syncthreads();

注意这个是更改的开头部分。

参考文献:

[1] Optimizing Parallel Reduction in CUDA - Nvidia