Streamware: Programming General-Purpose Multicore Processors Using Streams Jayanth Gummaraju, Joel Coburn, Yoshio Turner, Mendel Rosenblum ASPLOS 08上的文章 http://portal.acm.org/citation.cfm?id=1353534.1346319提出了一个通用的多核平台，支持Cell CUDA Brook等多种体系结构，用户只需使用这个平台统一提供的API。 另外还加入了cache hierarchy的管理，能很好的安排各级cache保存的内容，以至于某个测试结果中单核的情况下用了Streamware的程序比不用的程序跑得还快。 阅读全文 →

问题很简单，给定一个 8 位整型，要求写程序计算这个数的二进制表示中 1 的个数，要求算法的执行效率尽可能的高。 先来看看样章上给出的几个算法： 解法一，每次除二，看是否为奇数，是的话就累计加一，最后这个结果就是二进制表示中1的个数。 解法二，同样用到一个循环，只是里面的操作用位移操作简化了。 int Count(int v) { int num = 0; while (v) { num += v & 0x01; v >>= 1; } return num; } 解法三，用到一个巧妙的与操作，v & (v - 1) 每次能消去二进制表示中最后一位 1，利用这个技巧可以减少一定的循环次数。 解法四，查表法，因为 8 位整型的范围是 0 - 255，可以直接把结果保存在一张表中，然后查表就行。书上强调这个算法的复杂度为 O(1)。 int countTable[256] = { 0, 1, 1, 2, 1, ..., 7, 7, 8 }; int Count(int v) { return countTable[v]; } 好了，这就是样章上给出的四种方案，下面谈谈我的看法。 首先是对算法的衡量上，复杂度真的是唯一的标准吗？尤其对于这种数据规模给定，而且很小的情况下，复杂度其实是个比较次要的因素。 查表法的复杂度为 O(1)，用解法一，循环次数不会超过 8 次，所以时间复杂度也是 O(1)。至于数据规模变大，例如变成 32 位整型，那查表法自然也不合适了。 阅读全文 →

几个基本的优化： 用iaddl代替irmovl, opl，效果显著 删去不必要的andl，效果显著 改变判断分支（大多数是正数），效果显著 实现Load Forwarding，效果显著 函数结束时使用自己的epilogue，效果一般 Unrolling相关： 通过合并相邻两个循环，把mrmovl和rmmovl拆开，效果显著 32, 16, 8, 4, 1分段处理，效果显著，我用这个方法做到过7.2左右 Jump Table 由Duff’s Device引申出来的想法，代替了我原来那个32-16-8-4-1程序。 很好用的一个技巧，配合unrolling就不需要不断比较i和len的大小了。 比如len=15的时候，只要跳转到倒数第15个复制段落，就可以挨个做下来，而不需要多余的判断。 具体的实现可以想想x86里的情况，假设几个复制段落的标签为Loop1, Loop2, … jump: .long Loop1 .long Loop2 … 之后就只要取出jump + (len - 1) * 4处的值，然后跳到这个位置就行了。 跳的时候还有个技巧，最简单的是把这个值push到栈，然后再ret。这样的话bubble很多。 考虑到这个模拟器里代码段是不受保护的，也就是说运行的时候可以动态修改内存中的代码，于是在跳转的地方写个jmp 0，然后运行的时候动态把这个0改掉就行。 另外要注意用这个方法的时候得手动写几个nop，或者在改内存的语句和jmp语句之间加几个其他命令，因为y86模拟器是默认程序不会修改自己的代码的(p328 灰色背景部分)。 用这个方法的时候还有一些细节可以优化，就不列举了。另外不知道利用自我修改这个特点能不能做出更神奇的效果呢？ 比如我还想到另一种类似的方法，让程序从头到尾运行，不跳转，而是在程序运行时动态的插入ret语句直接把程序运行流掐断。我还没试过，有兴趣的同学可以试一试。 不知道还有没有其他的优化方法，欢迎讨论~ 阅读全文 →

编译 不安装图形界面： 修改sim/Makefile，把前三行非注释部分用#注释掉，变成 # GUIMODE ... # TKLIB ... # TKINC ... 保存后运行 make 图形界面 安装Tcl/Tk库 Redhat 9： 可以在Redhat菜单->System Settings->Add/Remove Applications中添加X Software Development，根据提示载入相关镜像文件。 然后在 sim 目录下运行 make Arch Linux： 有包管理机制的发行版直接用相关软件安装（比如 Arch 中 pacman -S tcl tk），注意安装好以后生成的动态链接库可能带有版本号（比如 libtcl8.5.so libtk8.5.so） 具体版本号通过 pacman -Ql tcl tk | grep '.so' 查得 接着只要修改Makefile中的TKLIBS参数，或者用ln建个链接即可 Ubuntu 由于ubuntu默认没有lex词法分析工具，在编译时需要先安装flex：sudo apt-get install flex 图形界面和Arch类似 sudo apt-get install tcl8.5-dev tk8.5-dev tcl8.5 tk8.5 然后修改 Makefile 阅读全文 →

这个 Lab 应该比上一个 Lab 简单不少， Lab 的说明文档也差不多把基本的过关要点都提到了，所以这里主要介绍一下几个相关工具的使用，帮助大家进一步熟悉 Linux 命令行 ;-) 首先从主页上下载一个压缩包，最简单的方法是直接在命令行使用 wget 工具 wget http://10.132.143.100/lab2007/buflab-handout.tar 顺便提一下 wget 的功能很强大，除了可以在后台运行，它还支持 ftp https http 等协议，提供整个网站下载的功能（类似于 Windows 下的 WebZIP ） 接着使用 tar 命令解压这个文件 tar xvf buflab-handout.tar 其中， x 参数表示解压工作， v 表示显示解压所得的文件列表， f 及其后面跟着的文件 名指定了待解压文件 这样在当前目录下就多出了三个文件： bufbomb, makecookie, sendstring 接下来使用 makecookie 得到自己学号对应的 cookie 号，用法是 ./makecookie 学号 这个 cookie 号在后面的几个关卡中都有可能会用到，同时 http://10.132.143.234/bufbombstatus.html中可以通过自己的 cookie 号随时获得自己现在的过关情况。 和上一个 Lab 一样，这里介绍一下怎么过 Level 0 。 这个热身关和两个函数有关， test() 和 smoke() ，正常情况下 smoke 不会被任何函数调用，我们要做的就是输入一串特定的字符，使得 smoke 被调用。另外这个关卡简单之处在于 smoke 被调用后就直接退出程序，我们在破坏了栈的数据后不需要恢复原样。 阅读全文 →

这个lab主要考察gdb的使用和对汇编代码的理解。后者在平时的作业中涉及得较多，这里不再赘述，主要介绍一下gdb。其实偶对这个也不是很熟，有错误请指正。 简单的说，gdb是一款强大的调试工具，尽管它只有文本界面（需要图形界面可以使用ddd，不过区别不大），但是功能却比eclipse等调试环境强很多。 接下来看看怎样让它为lab2拆炸弹服务，在命令行下运行gdb bomb就能开始调试这个炸弹程序，提高警惕，恩。 首先最重要的，就是如何阻止炸弹的引爆，gdb自然提供了一般调试工具都包括的断点功能——break命令。 在gdb中输入help break能够看到相关的信息。 可以看到 break 允许我们使用行号、函数名或地址设置断点。 按ctrl+z暂时挂起当前的gdb进程，运行 objdump –d bomb | more 查看反编译后的炸弹文件，可以看到里面有这么一行（开始的那个地址每个人都不同）： 08049719 <explode_bomb>: 这个就是万恶的引爆炸弹的函数了，运行 fg 返回 gdb 环境，在这个函数设置断点：break explode_bomb （可以使用tab键自动补齐） 显示 Breakpoint 1 at 0x8049707 接下来你可以喘口气，一般情况下炸弹是不会引爆的了 下面我们来拆第一个炸弹，首先同样是设置断点，bomb.c中给出了各个关卡的函数名，第一关就是phase_1，使用break phase_1在第一关设置断点 接下来就开始运行吧，输入run 我们已经设置了炸弹断点，这些恐吓可以直接无视。 输入ABC继续（输入这个是为了方便在后面的测试中找到自己的输入串地址） 提示Breakpoint 2, 0x08048c2e in phase_1 ()，说明现在程序已经停在第一个关了 接下来就是分析汇编代码，使用disassemble phase_1显示这个函数的汇编代码 注意其中关键的几行： 这个lab很厚道的一点就是函数名很明确地说明了函数的功能 ^_^ 估计这三行代码的意思就是比较两个字符串相等，不相等的话应该就会让炸弹爆炸了 因为字符串很大，所以传递给这个比较函数的肯定是他们的地址，分别为0x80499b4和0x8(%ebp) 我们先来看后者，使用p/x *(int*)($ebp + 8)查看字符串所在的地址 $1 = 0x804a720 ​```` 继续使用`p/x *0x804a720`查看内存中这个地址的内容 $2 = 0x434241 连续的三个数，是不是想起什么了？把这三个数分别转换为十进制，就是67 66 65，分别为 CBA 的 ASCII 码，看来这里保存了我们输入的串。 接下来 0x80499b4 里肯定保存着过关的密码 `p/x *0x80499b4` $3 = 0x62726556 阅读全文 →