Archive

Archive for November, 2010

MiBench Benchmark 简介

November 18th, 2010 No comments

MiBench Benchmark 是 Michigan 大学电子工程与计算科学学院推出的一个免费的嵌入式基准测试集合。2001年推出之后得到了广泛的使用,截止2010年11月被引用了1234次(Google Scholar 数据ACM portal 的数据显示MiBench论文被引用了325次)。

MiBench Benchmark 总共包含35个嵌入式程序,分成汽车及工业制造、消费电子、办公自动化、网络、安全、通信六个子类。所有程序都使用 ANSI C 编写,这使得 MiBench Benchmark 也具有了很好的可移植性。以下是 MiBench Benchmark 包含的程序介绍:

  • 汽车及工业制造

  1. basicmath:一些简单的数学计算测试;
  2. bitcount:统计一个整数数组包含的bit中1的个数;
  3. qsort:字符串快速排序程序;
  4. susan:图像识别工具包。
  • 消费电子

  1. jpeg:JPEG编解码程序;
  2. lame:MP3转换程序;
  3. mad:MPEG音频解码器;
  4. tiff2bw:将TIFF格式转换成黑白图的格式;
  5. tiff2rgba:将TIFF格式转换成RGBA的格式;
  6. tiffdither:TIFF图像抖动工具,降低分辨率,减少图片体积。
  7. tiffmedian:TIFF图像调色板调整工具;
  8. typeset:基于HTML的排版工具。
  • 办公自动化

  1. ghostscript:排版工具,CLI版本;
  2. ispell:快速拼写检查工具;
  3. rsynth:text to speech 工具;
  4. sphinx:语音解码工具;
  5. stringsearch:字符串查找工具。
  • 网络

  1. dijkstra:Dijkstra算法实现;
  2. patricia:Patricia Trie,用于叶子稀疏的树结构。
  • 安全

  1. blowfish enc./dec.:blowfish加密/解密算法;
  2. pgp sign/verify:pgp 签名/检验算法;
  3. rijndael enc./dec.:rijndael加密/解密算法;
  4. sha:SHA散列算法。
  • 通信

  1. CRC32:CRC32计算工具;
  2. FFT/IFFT:快速傅立叶变换及其逆变换;
  3. ADPCM enc./dec.:Adaptive Differential Pulse Code Modulation 编解码工具;
  4. GSM enc./dec.:GSM加密/解密算法。

参考资料:

PACE 项目介绍

November 18th, 2010 No comments

注:部分内容翻译自 Rice University 的 PACE Project 项目网站。

PACE(Platform-Aware Compiler Environment,具有平台感知能力的编译器环境)项目是由美国 Rice 大学的 Keith D. Cooper 教授领导的一个多研究机构参与的研究项目,团队规模超过30人。由DARPA/AFRL赞助一千六百万美元(2009年),作为具有感知架构能力的编译环境项目(Architecture-Aware Compiler Enviornment,AACE)的一部分。项目的预期长度是四年半,现在可能还没有结束。

过去几十年的经验表明为一个新的平台写一个优化的编译器平均需要3~5年时间。平台感知编译环境(PACE)项目的目标是将一个优化的编译器移植到新的系统的过程自动化。基本的方法是:

  • 重写优化,使得无论是单独的优化还是整个优化策略都根据目标系统的属性参数化。
  • 自动检测目标系统(target platform)的各种属性
  • 同时提供直接的运行时支持和长期的智能化的运行时支持(基于机器学习的参数制导优化)

PACE计划为性能可移植性提供了一个新的解决途径。PACE使用现有的本地C编译器作为代码生成器,而不是(像传统的编译器一样)重新实现一个汇编生成模块。
PACE系统应对前两个问题,解决方案如下:

  • 依赖一个本地的C编译器来作为代码生成器,而不是直接生成汇编代码。通过生成直观的C代码,可以将写一个新的汇编后端的代价降低;
  • PACE包含一个参数化的优化变换集合,这里的参数既包括硬件的特性也包括软件的特性。PACE会根据具体硬件/软件的特征来使用特定的优化参数,从而使得编译器得以根据目标平台的特点来进行优化。

最后,考虑到有些重要的特征无法静态的获得,PACE系统还包含了一个运行时环境,用于在运行时收集系统的特征,对已经编译过的代码进行优化参数调整。
PACE 是一个有远大目标的项目,Keith D. Cooper 是在编译领域响当当的大牛,在编译器优化自动调整方面做了超过二十年的努力。PACE 如果能够完美解决这个问题,那么在编译器的历史里应该是有浓重的一笔。可惜这个项目貌似是不开源的,至少目前我在项目网站上没有找到下载的链接地址。
参考资料
PACE项目主页:http://pace.rice.edu/
Keith Cooper 的介绍主页:http://compsci.rice.edu/Facultydetail.cfm?riceid=912
Keith Cooper 的个人主页:http://www.cs.rice.edu/~keith/
AACE项目主页:http://www.darpa.mil/tcto_aace.html

如何找到研究点 (转载)

November 8th, 2010 No comments

这是篇转载翻译文章,中文原文来自于编译点滴,中科院计算所的计算机硕士;英文原文来自于Jason Eisner宾夕法尼亚大学的计算机博士。

生物人类学家 Loren Eiseley曾将科学家分为两类:大家和小家。(他称自己为小家,在科研方向的大骨架中坐着丰富数据的工作。如果Eiseley是个程序员的话,他估计会把自己成为”自底向上“的科学)
计算机科学包括很多不同种类的研究方式,其中有一些相对于另外一些很庞大。你可以通过某个方式做出自己的贡献。

  • 估计你在计算机科学中能找到的最小研究点就是替换或者实现其他人的算法/工作。这种方式可能对你所在领域或者学习很有用,但无法让你的工作有独创性。当然如果你能使自己的工作对足够多的人们有用(比如,让他具有更好的可以执行和互联特性),你也能有点名气。
  • 稍微大点的研究点就是努力寻找改进现有著名技术的方式。(在很多子领域,别人更期望你的工作能确实带来改进).大多数的研究都是这种。读论文的时候,注意文章中的关键条件和问题。实际中,注意作者在他的机制中使用到的有害简化或者太过随意的假设。这些地方都是你能做的与众不同的机会。
  • 另外,还有个稍微大点的研究。针对两个或多个算法,通过一些客观的效率、准确性测量方式评估他们。设计一个合理清晰的对比,并且实现并给出对比结果,通常需要大量的工作。这个研究的好坏,不仅取决于需要多大的工作量,而且还需要看你所得到的结果是否很出人意料。要知道,这种量化的研究方法正在一些重要的领域变得越来越重要。(如操作系统、机器学习、自然语言、算法).
  • 写综述:你可以透彻的回顾某些领域的已有研究。但要注意,要想做得好,需要花费大量的时间,而且对于你的研究工作作用也不大,除非很多人想读并引用你写的牛综述。(要想发表此类综述,你需要和非常著名的导师一起写这类文章,或者找一个期望接受低水平研究生高层次综述文章的一流期刊吧)。好的方面是,通过写牛综述,你可以成为该方面的专家,可以游刃有余的和其他该领域的研究者探讨。而且可以给你关于过去研究成果的不足之处。而且这种综述对于一个高级本科生、硕士生论文,或者博士论文的第一部分很合适。当然,如果你还是忍不住想炫耀,可以在网页上发布。
  • 构建一个大型程序或者设备。这会让你有些知名度,毕竟这么大型的系统还不多,而且这也能证明你可以做个合格的软件工程师。但是,请想清楚:这个系统其他人可以直接用吗?如果不能,它能刷新性能记录之类的吗?如果还是不能,它还有其他的长处吗?比如,能演示如何整合和扩展已有技术,或者能引入新的技术或者前景。如果你只是实验室若干工程项目中的一个参与者,那么请务必确保你自己有独立的贡献–这个工作的某些方面让人印象深刻,独一无二,而且其他人的工作和你直接相关。
  • 你的领域有很多重大的问题。这种问题通常表现为该学科的主干结构上–问题经常出现,但解决方案却有很多种。了解一些这种问题和已经针对此类问题展开的工作。如果你发现了能首个解决此问题,或者找到更好的解决方案,或者有不同的解决方式,这就是个大发现!通常,寻找好的解决方案都需要稍微改改这个问题本身。
  • 如果你壮志踌躇,而且励志做大的科研,那就需要研究计算机分支中你所在的分支中著名的论文,了解一些相关会议上其他人都在做什么,并且多问问自己,在这个领域,是什么已经被发现的或者未知的问题阻碍了发展?我能解决吗?如果不能,我能先形式化他们吗?我能证明给同事们看,解决这个问题后会有什么不同吗?
  • 和你导师聊聊目前已经研究透彻的领域。每个领域都有些共性的问题,“有点重要”的问题,这些问题可能被提及和诺,但是还没有人做个认真的尝试。如果自己觉得找到了这样一个问题,别忘了向你的同事,以及图书馆求证这个问题还未被研究透彻。
  • 最后,你会找到一些有趣的问题,而且通常都不是听起来那么难。
    • 研究已有的(已经使用的)系统,关注哪些地方它们做的不好。
    • 如果你的领域是交叉学科,多询问另一学科的人感兴趣的是什么。实际就是问他们为什么计算机科学家都不着边际的乱弹。
    • 在很多领域,数据已经给出了存在的问题。语言学家能在任何一本杂志文章里找到不能解释的现象。系统程序员能在实际磁盘访问中收集数据,研究如何通过正则的方式表达。程序语言理论学家能够学习实际的编程语言,图形程序员能实际观察真实的图形和动画,只是不知道如何捕获他们。

请务必谨记:有很多的研究可以做,所以你可以选择某个领域。(即使你的导师是个实干派,你仍然有很多的选择).所以,尤其是当你在考虑非常耗时的工程时,要做好打持久战的准备,并且问问自己。这个项目是不是真的能:

  • 让你学到很多?
  • 带来更好的项目?
  • 能让你享受自己即将花费的时间?
  • 能让你从现在起坚持6个月、12个月甚至48个月的时间,仍然觉得很有价值做下去?
  • 从某种意义上,有成功的希望?(比如:能以此为话题,带来一个有趣的报告或者讨论)
  • 让导师不会太责怪?
  • 让整个学术界对你和你的工作感兴趣?
  • 给工业界的人证明你所做的工作正是他们需要的?
  • 让你成为所谓的“优秀毕业生”?

最后:现在你终于在研究生院了,没人为你设置课表和日程,你所做的每件事都是无期限的。这就意味着你很容易花费很多时间在任何一个任务上,尤其是固执的要求完美或者重复体力活的任务会让你觉得工作永远不会足够好。或者自己的潜意识在逃避下一个研究阶段。

  • 不要花费过多的时间在背景阅读上。你要意识到自己的工作肯定会在充满未知的情况下展开。你没有时间来学习所有你需要知道的事情。没什么,你的导师也是这么过来的。实际上,这是好事,因为未知让你的思想没有束缚,可能会有新的灵感迸发。所以,早点开始做自己的思考。你可以边做边读,只需要周期性的把你自己的想法告诉那些能在相关工作上给你指导,并推荐你读哪些相关论文的人就行了。
  • 不要在某一个问题上花过多时间。没有哪个解决方案是完备的。着力提高自己工作的健壮性,让自己的工作更好看些,更方便的秀出来。