Snowdream

GP-GPU 阅读笔记 (3)

4. GPGPU Techniques
4.1. Stream Operations
4.1.1. Map
Given a stream of data elements and a function, map will apply the function to every element in the stream.
4.1.2. Reduce
Sometimes a computation requires computing a smaller stream from a larger input stream, possibly to a single element stream. This type of computation is called a reduction. For example, computing the sum or maximum of all the elements in a stream.
On GPUs, reductions can be performed by alternately rendering to and reading from a pair of textures.
也就是用分治法，不断切换输入和输出数据，每次都能减少一定比例的数据规模。
4.1.3. Scatter and Gather
If the write and read operations access memory indirectly, they are called scatter and gather respectively.
4.1.4. Stream Filtering
This stream fitering operation is essentially a nonuniform reduction.
4.1.5. Sort
Classic sorting algorithms are data-dependent and generally require scatter operations.
主要的几个算法都和Sorting Network有关，还有一种adaptive sort，和原来序列的有序度相关。
4.1.6. Search
4.2. Data Structures

posted @ 2008-02-09 13:14 ZelluX 阅读(346) | 评论 (0) | 编辑收藏

Windows - QQ、网页Flash视频无声音的解决方法

注册表
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows NT\CurrentVersion\Drivers32
新建一个字符串值
名为 wavemapper
值为 msacm32.drv

posted @ 2008-02-09 01:00 ZelluX 阅读(4972) | 评论 (14) | 编辑收藏

GP-GPU 阅读笔记 (2)

2.4 GPU Program Flow Control
最新的GPU支持多种形式的分支，但是由于它们的高度并行化的本质，使用这些分支的时候一定要注意。
2.4.1 Hardware Machanisms for Flow Control
三种主要实现：
Predication 并非真正的data-dependent branch
MIMD branching
SIMD branching 同时进行的指令唯一，即各个点的分支选择应该一致
2.4.2 Moving Branching Up The Pipeline
2.4.2.1 Static Branch Resolution
静态分析，避免循环内部的分支。这里举了一个在离散空间点格(discrete spatial grid)上解偏微分方程的例子，不过没怎么看懂，大致是把循环拆成两部分的做法。
2.4.2.2 Pre-computation
有时候一段时间内或者几次循环中某个分支的结果会是一个常数。这时候就只要在知道结果会改变的时候重新计算即可。
2.4.2.3 Z-Cull
现代GPU有一系列用于避免处理不会被看到的像素的技术，其中之一就是Z-cull。简单的说Z-cull把没有通过深度测试（Z轴覆盖）点直接放弃。在流体模拟中，把land-locked障碍单元的Z深度标记为0，即可跳过这些点的计算。
2.4.2.4 Data-Dependent Looping With Occlusion Queries
同样是避免处理不可见的点的技术

3 Programming Systems
GPU的架构发展非常迅速，使得profiling和tuning需要由GPU生产商解决。
3.1 High-level Shading Languages
Cg, HLSL 和底层硬件很接近
OpenGL Shading Language 有一些不直接映射到硬件的特性，比如整数支持
Sh, Ashli, ...
3.2 GPGPU Languages and Libraries
上面提到的几个语言在使用时都要求编程人员站在几何元素的视角写代码。下面的几个系统试着把一些GPGPU功能抽象出来，隐藏底层的GPU实现。
Brook 前几星期打过交道的东东
Scout, Glift 都没听说过。。。
3.3 Debugging Tools
GPU的调试功能很受局限。它必须提供在某一时刻显示多个点的调试信息的功能。一种printf-style的方法是把他们直接显示在屏幕上（汗，如果是GPGPU编程岂不是花屏了 >,<）。

posted @ 2008-02-08 16:05 ZelluX 阅读(513) | 评论 (0) | 编辑收藏

GP-GPU 阅读笔记 (1)

实验室的寒假任务 =_=
No.1
A Survey of General-Purpose Computation on Graphics Hardware
on EUROGRAPHICS 2005

1. Why GP-GPU?
1.1 Powerful and Inexpensive
高内存带宽：Nvidia GeForce 6800 Ultra - 35.2GB/sec
强大的计算能力：ATI X800 XT - 63GFLOPS, Intel Pentium4 SSE unit(3.7GHz) - 14.8GFLOPS
尖端处理科技的应用：最新公布(指该survey发布的时间)的GPU包含三亿个晶体管，由0.011微米技术制作
快速发展：GeForce 6800的throughput为5900的两倍。通常GPU的计算能力平均每年增长速度为1.7x(pixels/second)和2.3x(vertices/second)，而根据摩尔定律，CPU的对应数值大概为每年1.4x。粗略的说，GPU性能每六个月增长一倍。

1.2 Flexible and Programmable

1.3 Limitations and Difficulties
GPU的强大计算性能是建立在它高度针对的架构上的，因此很多应用都不适合放到GPU上做。比如文字处理，主要包括内存通信，而且很难并行化。
如今的GPU也缺少一些基本的计算功能，比如整数运算。而且很多只支持32位浮点数（貌似最近的R670指令集可以处理double类型了），这样导致很多科学计算都没法在GPU上做。
另外即使对于适合GPU这些特性的问题，真正使用GPU做时也有不少问题。GPU的编程模型很不一样，高效的GPU编程不仅仅是说多学一门高级语言。如今要借助GPU的计算能力，需要编程人员同时掌握相应的科学计算知识和计算机图形学知识。尽管如此，GPU对性能提升的帮助还是很诱人的。

1.4 GPGPU Today
http://gpgpu.org
一些GPGPU的应用包括
Dense and sparse matrix multiplication 计算领域
Multigrid and conjugate-gradient solves for systems partial differential equations   计算领域
Ray tracing   图像处理
Photon mapping   图像处理
Fluid mechanics solvers   物理模拟
Datamining operations   数据库/数据挖掘

2. Overview of Programmable Graphics Hardware
2.1 Overview of the Graphics Pipeline
当今的GPU都采用了称为graphics pipeline的架构。pipeline被分成不同的stage，硬件上每个stage都被放到task-parallel machine organization上实现。

2.2 Programmable Hardware
显卡商们把固定功能的pipeline转化成了一个更灵活的可编程的pipeliine。主要在geometry stage和fragment stage。原来的固定的操作被用户定义的vertex program和fragment program代替
通常来说，这些可编程阶段读入一组含有限数量的有4个32位浮点的向量数组并输出一组含有限数量的4*32浮点向量的数组。每个可编程阶段都可以访问常数寄存器，也可以读写对应的寄存器。

2.3 Introduction to the GPU Programming Model
典型的GPGPU程序都使用了fragment processor作为计算引擎。通常的结构为：
a. 程序员确定该应用的并行部分。应用程序被分成几个独立的可并行段，每段都被看成是一个kernel，被当成fragment program实现。每个kernel的输入输出都是一个或多个数据数组，以texture形式保存在GPU内存中。用流相关的术语表述的话，这些在texture中的数据组成了stream，每个stream上的元素都要被kernel分别处理。
b. 调用kernel前要先确定计算范围，程序员可以传递点的数据给GPU。注意GPU在处理一维数组时性能有所局限。
c. rasterizer为每个像素生成一个fragment。
d. 每个fragment被同一个活动的kernel程序处理。fragment程序可以读入任意的全局内存，但只能写到rasterizer决定的frame buffer中。这块还没怎么搞懂
e. 每个fragment的输出是一个值或者向量值，可以作为作中的程序结果，也可以保存为一个texture，用于后面的计算，复杂的应用通常需要多个pipeline之间的传递(multipass)

posted @ 2008-02-07 16:31 ZelluX 阅读(758) | 评论 (1) | 编辑收藏

读核笔记(1) - 内核模块

include/linux/module.h
struct module:

struct module

{

// 用于在用户空间传入module对象时判断传入的结构是否有效

unsigned long size_of_struct; /* == sizeof(module) */

struct module *next;

// 指向本module的名称，通常内核空间里申请的name内存位置都是紧跟在module{}结构后面的

const char *name;

// 本module{}结构的空间 + 紧接着这段内存申请的归module{}结构使用的一部分空间

// size = sizeof(struct module) + sizeof(misc data)

unsigned long size;

// 模块引用计数器，还没搞清楚这里的pad是干什么用的

// i386中atomic_t的定义: typedef struct { volatile int counter; } atomic_t;

union

{

atomic_t usecount;

long pad;

} uc; /* Needs to keep its size - so says rth */

// 模块当前状态，已初始化/运行中/被移除/被访问过等

unsigned long flags; /* AUTOCLEAN et al */

// 定义的内核模块符号数

unsigned nsyms;

// 引用的模块链表节点数，遍历模块依赖性时使用

unsigned ndeps;

// 符号表

struct module_symbol *syms;

// 记录依赖的其他模块的数组

struct module_ref *deps;

// 记录引用该模块的其他模块的数组

struct module_ref *refs;

// 初始化和删除模块时调用的函数指针

int (*init)(void);

void (*cleanup)(void);

// 中断向量表的入口和结束位置

const struct exception_table_entry *ex_table_start;

const struct exception_table_entry *ex_table_end;

#ifdef __alpha__

unsigned long gp;

#endif

/* Members past this point are extensions to the basic

module support and are optional. Use mod_member_present()

to examine them. */

// 这两个指针维持一些模块相关信息，方便卸载后再次装载模块时的配置

const struct module_persist *persist_start;

const struct module_persist *persist_end;

int (*can_unload)(void);

int runsize; /* In modutils, not currently used */

const char *kallsyms_start; /* All symbols for kernel debugging */

const char *kallsyms_end;

const char *archdata_start; /* arch specific data for module */

const char *archdata_end;

const char *kernel_data; /* Reserved for kernel internal use */

};

struct module_symbol:
保存目标代码中的内核符号，读取文件装入模块时通过这个数据结构将里面包含的符号信息读入。

struct module_symbol

{

unsigned long value; // 入口地址

const char *name; // 内核符号名称

};

struct module_ref:
注意这里dep和ref记录的不对称，应该可以看成是一个ref链表吧
module{} 中的deps数组分别指向了各个依赖的module_ref{}

struct module_ref

{

struct module *dep; /* "parent" pointer */

struct module *ref; /* "child" pointer */

struct module_ref *next_ref;

};

struct kernel_sym:
在sys_get_kernel_syms()中用到的结构，该函数将内核符号拷贝到用户空间的kernel_sym{}中，从而可以在用户态存放模块信息。

struct kernel_sym

{

unsigned long value; // 内核符号地址

char name[60]; /* should have been 64-sizeof(long); oh well */

};

module.c中的一些函数先略去了，书上蛮详细的

模块的加载和卸载
insmod的任务：
从命令行中读入模块名，确定代码所在文件的位置
计算需要的内存
执行系统调用create_module()，传递新模块的名称和大小
用QM_MODULES获得所有已经链接模块的模块名
用QM_SYMBOL获得内核符号表和已经链接到内核的模块的符号表
使用这些信息重新定位该模块文件中的代码
在用户空间分配内存，拷贝相关信息
调用sys_init_module()，传递上面创建的用户态的内存区地址
释放用户态内存，结束

rmmod的任务：
用QM_MODULES和QM_REFS取得已经链接的模块列表和依赖关系
调用delete_module

posted @ 2008-02-07 11:22 ZelluX 阅读(556) | 评论 (3) | 编辑收藏

Minesweeper is NP-complete

http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm

居然是NPC...

posted @ 2008-02-06 19:40 ZelluX 阅读(459) | 评论 (0) | 编辑收藏

Linux 内核相关资料链接

如果一些文章的链接失效，google相应的标题应该还是很容易找到其他网站的转载的。

中断处理：
Interrupt in Linux
相当不错的中文资料

内核调度：
Inside the Linux scheduler
讲的是用expired/active两个数组维护的O(1)算法，大多数讲2.6内核的书上都会提到的调度算法 (2008-02-06)

Multiprocessing with the Completely Fair Scheduler
最新的2.6.23采用的CFS，还没搞懂 (2008-02-06)

http://www.ibm.com/developerworks/cn/linux/l-cn-scheduler/index.html
Linux 调度器发展简述 (2008-02-13)

内核模块：
2.6 内核中的模块注入 (2008-02-17)
http://www.linuxforum.net/forum/showflat.php?Cat=&Board=security&Number=536404&page=0&view=collapsed&sb=5&o=31&fpart

系统调用：
Linux 2.6 新增的 vsyscall 系统服务调用机制 (2008-02-18)
http://blog.csdn.net/wishfly/archive/2005/01/23/264435.aspx

Linux on-the-fly kernel patching without LKM (2008-02-19)
http://doc.bughunter.net/rootkit-backdoor/kernel-patching.html

内存管理：
http://linux-mm.org/LinuxMM
Linux-mm.org is a wiki for documenting how memory management works and for coordinating new memory management development projects. (2008-02-21)

并发同步：
http://hi.baidu.com/charleswen/blog/item/61f3e40ebc26dcce7acbe1c8.html
Linux内核中的同步和互斥分析报告 (2008-02-21)

http://www-128.ibm.com./developerworks/cn/linux/kernel/sync/index.html
Linux 2.4.x内核同步机制 (2008-02-22)

Big Picture:
http://www.linuxdriver.co.il/kernel_map
Interactive Linux kernel map (2008-02-16)
把内核中的函数相互调用做成了一张可放大缩小的地图，单击相应函数名会跳转到lxr的相应代码链接。

编程资料：
http://www.jegerlehner.ch/intel/
Intel Assembler CodeTable 80x86 (2008-02-21)

相关站点：
http://kernelnewbies.org
Linux Kernel Newbies

http://bbs4.newsmth.net/bbsdoc.php?board=KernelTech
水木KernelTech版

http://www.phrack.org
Phrack is an underground ezine made by and for hackers.
有不少和内核相关的hack资料