程序的正确性的一些理解–再谈一致性协议

2011年8月27日 sigma 没有评论 5,370 views

这几天,看论文,有个东西一直困惑我。那就是,如何判断程序是正确的,又如何判断程序的执行是正确的。下面谈谈我个人很直白,很初级的理解

个人以为,简单直白讲,程序正确,就是程序能做程序员预期希望做的事;程序执行正确,就是程序能够在一定输入下,输出程序员(设计者)所希望的输出。

个人以为,对于冯诺依曼机器,程序的输入包括:

整个程序空间的内存初始值以及任何改变程序空间内存的事件。

    对串行程序,上面的输入很好理解,其实就是内存初始值,以及各种外部改变内存的IO事件。一句话,串行程序的输入,其实就是内存输入(包括初始值以及外部改变的值)。并且,前述的输入可以确定地决定程序的输出。
    对串行程序,正确的程序,个人以为,就是能够处理程序员所定义的所有输入并得到期望的输出;程序的正确执行,也就是计算机能够将正确的程序得到期望的输出。其实,这里的正确,是基于程序员和计算机的一种协定,即计算机的指令集及每条指令的功能;正确的程序强调的是,程序元能用这套指令集实现所期望的功能;正确的执行,强调的是,计算机能够按指令定义及规范正确的执行每一条指令。
    而对于并行程序,理论上输入也只有这些,但是,现代的并行机器(多核,多处理机),由于同一份内存有多个备份,这时候,程序内部的内存改变,也是影响程序最终的输出。因为,不同备份的内存会出现不一致的情况,而消除不一致的值传播却不是瞬间的,甚至不是固定时间的。也就是说,不同备份内存值改变(包括因为其他备份传播导致的值更新)的时间也能成为一个伪输入,影响最终的结果。
    这时候,程序员和计算机,除了指令集约定,就需要新的约定,那就是一致性约定。对于计算机(或者对于计算机设计者)来说,希望这个值传播能够随意传播,时间没有限制,顺序也没有限制,因为,这样可以乱序执行,可以不用等待,可以提高计算机性能。而对于程序员,希望这个值传播是瞬间的,每个线程,只需要一改写内存,其他的内存备份,马上得到更新。

程序员所希望的一致性协议,叫做严格一致性,但是,这是这从物理上都是不可实现的,计算机肯定更无法实现。而计算机希望的一致性,则是不靠谱的,因为,那种情况下,程序员无法写出具有确定性输出的程序,因为很可能,在程序执行完毕后,同一地址对应不同的内存备份不一样,这时候,到底取哪个值,是一个问题。对于这种计算机来说,并行程序已经无所谓正确与否了。

阅读全文…

规划

2011年8月27日 sigma 14 条评论 4,890 views

昨晚和Yu聊了很久,收获良多,发现自己和很多人相比,尤其是grapeotrex相比,缺少对生活的规划。

今天下午和Chen同学聊天,也收获很多,也更意识到这个问题。的确,我也不小了,我该好好想想我想要的生活,好好规划自己的人生了。以前,我总是随遇而安,高考时,估了下分,知道top2没戏,就随便从学校列表按历年的录取分找学校,于是,看到科大的分数貌似还不错,并且看起来名字也挺唬人,我甚至没有仔细了解这所学校,更没想我想从这所大学收获什么,就浑浑噩噩来了科大。不过,这次选择我还挺满意,在科大,虽然没有我之前以为那么好的学风(其实,在科大,说实话,我从来没有认真上过课,都是靠突击),但是牛人却还是不缺,和牛人交流,能让自己变得更牛些,每天都能学到新的知识,那感觉很好。

大三了,我随大流来了计算所做大研,保研时,看到大家最想来的是计算所,而我也能来,于是毫不犹豫的来了,没想很多,其中有个有可能保研到MSRA的机会,也没去尝试,毕竟我这边几乎定下来了。刚来计算所,很多事物都是新鲜的,有种经验蹭蹭往上涨的感觉,还不错。可是,到了现在,这种感觉没了,有时有种感觉,自己做的事没什么用,基本上是在重复别人的工作,可是,我认了,继续做下去,没想那么多,但是,很显然的,不可能做的很好。当然,中间也会有一些困惑,但没怎么想,更没什么行动。

可是,在和同学的聊天中,我意识到,这也许会有问题,得好好想想,我想要的生活是什么,得好好规划,我的人生之路该怎么走。虽然,计划不如变化,但没有计划,何来变化。我改好好想想以下问题:

  1. 我的长期目标是什么,我希望我这辈子干些什么事,留下些什么?
  2. 当我老了时,我回望人生时,有哪些经历,可以回忆?
  3. 30年后,我希望我在做什么,过怎么样的生活?
  4. 20年后,我希望我在做什么,过怎么样的生活?
  5. 10年后,我希望我在做什么,回望以前,我会不会后悔,会不会想改变?
  6. 5年后,我希望我在做什么,能选择什么样的生活,和现在比有什么改变?
  7. 我的短期目标是什么,这短期目标和我长期目标有关吗,会矛盾吗?
  8. 现在我干的事,哪些是在为了短期目标,哪些是为了长期目标,哪些是在打酱油?

也许,想清楚以上问题很难,但是,当我想清楚了以后,我的人生规划也就算是出来了(我会写到某个记事本,并且默默记在心里)。不过,我还需要对自己说的是,赢在执行而不是计划



图片来源:http://acidcow.com/pics/15853-beautiful-roads-99-pics.html

分类: 随感 标签: , , ,

整理了下ISCA2000-2011所有论文的摘要

2011年8月20日 sigma 1 条评论 9,045 views

这周四,为了解近些年来的研究,需要看大量的论文,而在大量论文中找出最有价值的,我感兴趣的文章,除了标题外,就是摘要了。由于一篇一篇的看摘要很累(其实我有体系结构方面近些年来所有文章的全文,但一篇一篇打开看还是比较郁闷),于是突然想到可以先把摘要整理出来,这样以后过文章也方便一些。于是花了一天多差不多两天把ISCA2000-2011的所有文章的摘要整理出来个doc,后来突然想到这东西也许对别人有点用,于是又把他转化html,放到了网上。链接地址如下:

http://www.sigma.me/isca/

另外,在整理中,用到了几个工具和网站,在这里推荐下:

  1. 由于我是在linux下整理的,所以没用word,也不想用openoffice,用的是google docs,其实这段时间用google docs挺多的,发现还是挺不错的,基本的功能都有,多余的功能也没有。并且协作也很方便,存在互联网上,想看直接打开,不用再本地找来找去。
  2. 第二个,这个是强力推荐的,不过烟酒僧应该都知道的,那就是DBLP,上面搜文章还是挺方便的,虽然不能搜到全文,但按作者,按会议都有排列,非常方便找某一领域或者某一个会议的文章(这个工具我是大三从师兄那里知道的,但是还是不觉得咋的,现在越觉得好用)。我上面这个的文章的摘要列表就是通过DBLP那里得到标题,并且得到doi链接,从而手动把摘要搞出来的(本来想写个简单的爬虫的,但是发现doi上的摘要是通过js抓取的,貌似还不能直接通过fetch-url实现),没有doi的,就直接google。
  3. 最后一个,就是我把doc转化成html所用的工具Doc2html。本来想把这些文档直接用google docs转成HTML,但是每次转出来的html都很笨重,不简洁,很不爽。之后尝试用word的另存为功能将doc转化成html,可是,转出来还是不理想。于是就只好放狗搜,很快找到一个不错的工具,doc2html,试用了一下,转出来的html很干净,没有多余的东西,感觉很不错。Doc2html的链接是:http://ginstrom.com/software/doc2html/

这篇日记就写到这了,算是这周的任务,还得赶紧把这些整理出来的摘要扫一遍,从而找出想看的文章。现在感觉越来越难每周坚持写一篇日志了。不过无论如何,我还是会坚持的。

分类: study 标签: , ,

漫谈Google的Native Client(NaCl)技术(二)–技术篇(兼谈LLVM)

2011年8月14日 sigma 没有评论 67,458 views

上一篇文章介绍Google的Native Client技术的渊源及动力,解释了为什么Google要做这样一个技术。在这篇文章中,将介绍Native Client的一些技术概要。

Native Client简介

Native Client是Google在浏览器领域推出的一个开源技术,它允许在浏览器内编译Web应用程序,并执行原生的编译好的代码。Native Client有以下几个优势(参考Google官方英文介绍):

  • 为Web提供更多的图形,音频以及其他功能:可以直接在web上执行了原生的2D,3D图形渲染程序(对Web游戏很有用),播放音视频,响应鼠标键盘事件,多线程执行代码等等,而这一切,不需要浏览器安装任何插件。
  • 良好的可移植性:一个Web程序,只需要开发一份代码,即可以在所有平台(包括Windows,linux,Mac等)运行。
  • 高安全性:安装不被信任的桌面程序一级浏览器插件,可能带来很高的安全风险(如程序携带木马,病毒)。而Native client使用了双层沙盒(sandbox)设计来保护用户的本地资源。Native Client的架构可以保证web要应用的安全性,并且取得和原声代码相同或相近的性能。
  • 方便从桌面迁移:很多开发厂商之前花了大力气开发桌面程序,随着云计算的到来,越来越多的程序会被移植到互联网上,由于NaCl支持直接执行C/C++/Java等代码,Native Client技术可以简化移植过程,减少移植成本。
  • 高性能:Native Client可以让web应用已接近桌面程序的性能运行,这就为在浏览器内运行性能苛刻的程序提供了基础,如大型3D游戏。

Native Client技术概要

有人说,Native Client技术是抄袭ActiveX的,个人不以为然,ActiveX主要是基于COM的,是操作系统提供一套可重用的接口给web应用,而NaCl则是独立于操作系统的。说实话,感觉这技术更像是抄袭Adobe的Alchemy技术,Achemy技术主要目的是解决Flash的低性能,这和Native Client是接近的,并且,这两种技术都采用了LLVM技术,具体可以看这篇文章http://yjrl.iteye.com/blog/320665

LLVM 是 Low Level Virtual Machine 的简称,这个库提供了与编译器相关的支持,能够进行程序语言的编译期优化、链接优化、在线编译优化、代码生成。简而言之,可以作为多种语言编译器的后端来使用。而基于LLVM ,开源社区开发出了Clang,一个C++ 编写、基于 LLVM、发布于 LLVM BSD 许可证下的 C/C++/Objective C/Objective C++ 编译器,其目标(之一)就是超越 GCC。

Google 的Native Client的关键技术就是PNaCl(Portable Native Client Executables),而PNaCl实现的一个关键就是LLVM。下面是整个PNaCl结构示意图:
PNaCl示意图

在PNaCl中,开发者通过一些前端编译器将C/C++/Fortan源代码用对应的编译器前端编译成LLVM的中间字节码,并且进行优化以及链接(这一整套流程可以在Google提供的SDK中完成)。之后,服务器将链接好的字节码进行分发,在客户端,通过LLVM的后端将字节码翻译成本地的二进制对象文件,并且和本地的相关库链接,最终执行完成(这些功能应该是集成在浏览器中的)。

另外,为了保证安全性,NaCl采用了沙盒技术,具体可以看这篇论文:《Native Client: A Sandbox for Portable, Untrusted x86 Native Code》。

参考:

http://www.lingcc.com/2010/06/02/10955/

http://nativeclient.googlecode.com/svn/data/site/pnacl.pdf

漫谈Google的Native Client技术(一)–历史动力篇(Web本地计算发展史)

2011年8月13日 sigma 22 条评论 10,461 views

昨天在CB上看到一篇文章《最新Chrome Beta支持在浏览器内直接执行C/C++代码》,而实现这功能的最基本的技术就是Google几年前提出的Native Client技术,其实之前我在一个计算所师兄的博客里已经看过一篇介绍Native Client技术的文章,个人当时就感觉这东西挺有前途的,今天无聊,也了解了下,写篇博客总结下,其中不免有拾人牙慧之处。

Web计算本地化(前端技术)历史-HTML->CSS->Javascript

最初的网络上传输的内容是纯文本的,从网络上传输回来直接通过字符界面展示出来就够了,本地几乎不用计算。

后来,为了更直观,更层次化展现网络内容,人们在文本的基础上加上了什么<h1>之类的标签,于是出现了html,这时候,就出现了浏览器,浏览器是把这些标签解释,并且按照一定格式渲染,这时,就需要一定的本地计算来进行标签分析,字体渲染之类的。

再往后,出现了CSS,并且互联网有了富媒体元素,可以把网页展示的漂亮了,要求本地计算更多了。

但是,这还不够,除了将网页做得漂亮外,还需要减少用户的等待时间,提高用户体验。这时,有人发现,其实很多网络通信是可以避免的,比如,在用户登陆界面,用户输出email格式的用户名,之前是需要将这个信息发给服务器,服务器收到信息后,检查是否合法,不合法的话,返回一个页面,叫用户重新填写,这一来一往很花时间,用户体验非常不好。于是有人就想到,能不能把这些检查用户名之类的计算放到本地,于是,就出现了JavaScript,在用户提交信息时,JS可以在本地检查是否合法,不合法的话,提示原因并要求重新输入,这样用户体验就好了,并且减少了服务器计算以及通信(这貌似符合绿色通信的概念)。

再往后,有人发现,每次点击一个链接,在载入下一个页面的时候,出现空白页让用户很不爽,于是,有人想出了一个办法,那就是事实上,很多页面很大一部分是共同的,这部分其实不需要重新加载,只需要加载改变的部分,而这又可以通过JS实现,于是出现了Ajax技术。这个技术减少了空白等待,提高了用户体验,并且减少了网络通信量(有时绿色通信!)。

Web计算本地化进一步发展-Java-applet,Flash,html5

但是,用户在互联网上的需求还是没有得到满足,有人还想直接在网页上处理图片,玩游戏之类的,由于这类应用一方面计算量大,都放到服务器,服务器不堪重负,另一方面,这类应用都是实时生成画面的,假如通过服务器来计算生成画面(如游戏),再通过网络将每帧图像实时传送回来,对网络要求极高,几乎不可能实现。

于是,需要新的技术将更多的计算放到本地,这时候,出现Java applet,flash等。Java applet允许在网页中嵌入java程序,并在本地执行。Flash应该也是类似,只不过这些计算需要通过flash提供的api完成(这一点有点类似ActiveX通过COM来完成本地计算?)。

Flash的出现,一段时间内,几乎是一统互联网的视频播放以及网页游戏领域。这时,有人眼红也好,有人有更好的主意也好,结果就是有人抱怨flash不开放(还有不安全),有人就想到,我们做一个开放的标准,这标准里面就允许类似游戏等复杂的交互,于是出现了HTML5和CSS3。HTML5以及CSS3将很多JS以及Flash能完成的功能都已到了一个HTML标签里,其实,本质还是差不多,只是这时候这些渲染的计算不是通过flash程序来了,而是直接通过浏览器执行了。

云计算时代的本地计算-Native Client

再往后,随着网络带宽的增长,以及服务器存储能力的提高,出现了大量的数据中心,为了提高这些中心的利用率,出现了云计算。在云计算时代,用户可以把很多数据都放在云端,并且访问这些应用的方法都是统一的。开发者在云服务器开发程序的接口也是统一的(PaSS),这就可以很容易实现跨平台,给用户一个统一的体验。

在这个时代,由于访问云端的资源都是通过浏览器完成的,浏览器就成为一个很重要的平台,这也就是为什么Google会推出自己的浏览器以及ChromeOS的原因。在浏览器能做的事也越来越多,如玩游戏,但是,由于这些游戏是通过一个类似flash这样的东西执行的,效率很低,为了提高效率,并且进一步的将更多的计算密集的东西(如3D渲染)放到本地完成,Google提出Native Client技术,这种技术就是想直接在本地执行C/C++/Java/Python等代码,从而提高本地计算的效率。

从这里,也可以看出Google的野心,Google希望以后用户所有的需求都能在浏览器上完成,包括大型3D游戏,到时候,什么Windows,Linux,都是透明的了,只剩下一个Chrome Broswer,成为开发者的事实平台,得开发者得天下,Google就此一统江山,虽然不能千秋万代,但也能够衣食无忧上十年。

Web计算本地化的问题-安全性

由于web计算本地化是在本地执行服务器上下下来的代码,因此,服务器上要是发给用户的恶意代码,在本地执行的话,会出现严重的后果,因此,这些技术(包括JS,Java applet,Flash)的安全性非常重要。由于Flash应用最多,因此,Flash也被经常爆漏洞。

而对于Native Client技术,如何保证安全则是更大的挑战,为了保证安全,感觉这技术最好用于计算密集型应用,而尽量不让远程代码执行文件读写操作。为了保证文件读写的安全性,个人觉得有两个办法,一个是不读写本地文件,将文件直接写到云端的云存储(但是计算还是本地);另外一个就是在本地沙盒里面读写,不过这只适合临时数据,永久的还是要写到云端。

最后,附一张图,这张图反映了个人计算机应用平台的进化方向:

无觅相关文章插件,快速提升流量