计算的边缘

LUG——Linux User Group 这是我在浙大参加的第一次也可能是最后一次Linux用户组聚会。当然没有空着手去，我分享了一些我使用Shell脚本的经验，还现场写了一个简单的论坛灌水机。 幻灯片可以在这里下载。 生活的乐趣就在于学习知识、创造知识、分享知识。 这次活动，我至少知道了一点：我的Dell本＋Ubuntu 8.04是可以连接投影仪的。

I/O-Bound这个词实在不知道该如何翻译成中文，或许我该找本中文的操作系统来看看。它说的是这个意思： ———-科普开始———- 通常来说，一段程序的执行需要几个步骤：从存储器里取出需要操作的数字，然后进行运算，再将结果写入存储器里。就这么简单。 比如说，我们需要计算1+2=_。首先我们需要从存储器里获得1和2这两个数，然后将这两个数进行加法运算，最后再将结构3写入存储器里。 看似平凡的三个步骤，却暗藏着玄机。根据现在的处理器和存储器结构，做一个加法运算的时间大概需要1个周期，而访问一次内存需要的大概是500个周期。这是500倍的差距。这只是读写内存，而对硬盘的读写所需要的时间比内存还要多100,000倍！ 程序的差异性就主要体现在它们对处理器和存储器读写的不同需求上。有些程序主要的执行时间花在了处理器的运算上，这些就是CPU-Bound的程序，而有些花在处理器读写（更一般地，输入输出，Input/Output, I/O）上，这就是I/O-Bound。 下面的图可能更形象一些： 在图中，黑色的块代表处理器在计算，浅色的块代表正在进行I/O读写。 ———-科普结束———- 下面进入正题。 这些枯燥的叙述可能还不足以点燃你对I/O-Bound的仇恨，假如它发生在你的生活中呢？ 处理器的计算就好比我们办正事，而I/O读写就好比花在路上或者是排队的时间。假设你要拍毕业证了照片了，而学院的老师以管理小学生的办法要求你们明天上午9点集合，统一拍照。好吧，第二天你起晚了，到了指定的地点发现已经有一长串的队伍拍在那里了。你等啊等，不时拿出手机上会儿网，和同学聊会儿天，看看美女，再骂两句前面插队的人，在排了两个小时的队后，终于轮到你了。你刚端坐在椅子上，还想再调整一下姿势，只见闪光灯一闪，然后就听到一个似曾相识的声音：“下一个！” 拍照的时间不到一分钟，你却等了2个小时，先别急着骂街。你花在排队等待的时间只是办正事时间的120倍而已，想一想CPU同学，每时每刻都在忍受这大于500倍的I/O-Bound程序还这么任劳任怨，真是精神可嘉。只可惜CPU是老外发明的，要不然它早就获得五一劳动奖章了。 类似这样的事情每天都在发生，我们的时间，甚至生命每时每刻都在被浪费着。今天我去上海办签证，真正递送签证的时间也就只有15分钟，但我从早晨8点出门，晚上8点才回来。其他时间都花在排队买票、等车、坐车、认路上了。这个时间差距也足有48倍。 认清了I/O-Bound工作的真实面目，你一定像我一样深深地恨上它了吧。彻底摆平它是不大可能的，我们只能尽可能使它浪费的时间减小的最少。如何做到呢？先让我们来看看计算机设计者们是如何做的，因为他们也同样痛恨I/O-Bound的工作。 最土最暴力的方法就是减少I/O操作的时间，比如减少访问存储器所需要的时间。但这种提升空间毕竟有限而且成本昂贵。我们也可以这样做，下次去上海的时候就直接打的，这样就省去认路、买票、等车的时间了。这样做需要付出的代价也是极大的，可能就是你接下去几个星期就要啃馒头了。 还有一种方法就是利用时空的局限性，顺便帮别人也把事办了。计算机中的缓存（Cache）就是基于这种考虑设计的，取一个操作数的时候，顺便把其他操作数也取到了，而且以后再用到的时候就不用再花时间取了。当然，聪明的我们也在用着这种方法，只是不知道而已。你去食堂吃饭的时候，同学经常让你帮他们打包，你就在无形中减少着他们因为I/O-Bound所浪费的时间——至少，他们不用再去食堂、排队、打饭、找座位了。而且还可以为自己攒人品哦。你要是顺便再多打一份，留着晚饭吃（如果不嫌凉的话）就更像缓存的行为了。 一种最上档次方法就是同时进行多任务。对处理器来说，它可以在等待一个程序I/O操作的同时为另一个程序做运算，就像右图。这样，处理器可以说”随时都在办正事“，并没有浪费时间。当然，这需要巧妙的调度。我么当然也可以做到，甚至已经做到了。当我们排长队或者坐车的时候，我们可以做一些”CPU-Bound“的工作，比如读读论文、看看闲书、和女朋友煲电话粥、和旁边美女搭个讪等等。充分利用时间，决不让它无故地浪费。 可惜我一个都做不到，一坐上车，就浑身不舒服。只能听听京剧，然后就睡着了。 本文所有图片来自这里。

CPU能干什么？计算，烧水，煎鸡蛋？没错，它还能做成一个钥匙坠。最近淘到一块很老的CPU——赛扬633，与其放在抽屉里不见天日，不如做一个钥匙坠玩。 先简单介绍一下我们的钥匙坠原材料： 英特尔赛扬633大概是和奔三一个年代的产品，已经是上个世纪的古董了。主频633MHz，有370个针脚。是上世纪末电脑经销商居家旅行、杀人灭口之必备良品。 为了把CPU改造成钥匙坠，主要依靠下面的技术路线：割针脚——>打孔——>打磨，就这么简单。 确定了技术路线，就要确定工具：美工刀，划瓷砖的钢锥，四棱锥，砂纸。这些东西在五金店都能买到。 如图： 下面开始割针脚。这块CPU有370个针脚，都割掉还真是个体力活。开始割才发现用美工刀是个大错误。美工刀的刀刃很软，没割几下就卷了。稍使点劲就会把针脚连焊点整个掀起来，露出古铜色的接点。最后的结构就是黄一点，白一点，影响视觉效果…… 拔完针脚就该打洞了，理想状况下应该用小电钻。可惜搞不到，就只好手工打洞了。先用划瓷砖的钢锥和锤子在板子上凿出一个小洞，钢锥很硬，尖不会变钝，很轻松就搞定了。然后再用四棱锥慢慢地钻出一个大洞，两面都要钻才能保证洞的均匀。 现在已经基本成形了。再仔细打磨一下，用砂纸磨掉毛边和残留的针脚。最后穿上钥匙环，CPU钥匙坠就大功告成了！ 欣赏一下成品： 总而言之，言而总之，最费事的就是割针脚。现在比较新的CPU的针脚都是设计在插槽上，CPU上只有触点，这样的CPU做起钥匙坠来就轻松多了。不知道什么时候才能用新CPU再做一个钥匙坠。不过，虽然一个一个地割针脚很麻烦，DIY的乐趣不正是在此么？ 手头还有一条台式机内存，下次把它也做成钥匙坠。

注意：这篇文章是我这学期“计算机前沿技术讲座”的期末报告。转载请一定注明出处，否则会被认为是抄袭的，有嘴也说不清。 自从亚里斯多德的时代开始，人们探寻自身及宇宙的征途就从未停止。两千多年来，无数的物理学家都试图用一个简洁的定律解释宇宙万物，从伽利略、开普勒到牛顿的万有引力，从爱因斯坦的广义相对论，到玻尔等人的量子力学，再到温伯格等人的超弦理论，解释万物的终极理论正一点点地浮出水面。 这就是物理学家，乃至全人类的终极理论之梦。然而，作为计算机科学工作者，我们也有自己的终极梦想——终极计算之梦。 人的本性是贪婪的，正因如此，我们对计算机的要求从没有得到过满足。人们想让计算机变得更快，而它也正像我们希望的那样变得越来越快了。而我们的终极计算之梦就是如此吗？ 让我们回到计算机的基本模型——图灵机。在这个模型中，有一条数据带、一个可以左右移动读写头以及一系列状态和转移函数。机器从数据带中读到一个数据，根据当前的状态和输入的数据跳转到下一个状态或保持当前状态，与此同时，可以输出数据。 这种“自动机”的加强版模型能做一些“智能”的运算，例如判定一个字符串是否是回文、算术运算、逻辑运算等等。人们开始被这种“强大”的自动计算机震惊了。当然，你也可以训练一只狗来做一些简单的算术运算，但这只是一种条件反射的作用。图灵机可以做相当复杂的算术运算，而且速度比人脑快很多，难道说它真的具有“智能”了吗？ 计算机和人脑是如此得相似——都有输入、输出、处理中心。对人脑来说，我们通过眼睛、耳朵、鼻子、皮肤来采集输入信息，通过大脑分析，再通过嘴、四肢来产生输出信息。或许唯一不同的是我们有自我的意识，而自我意识是什么？这个问题先就此打住，否则就成为讨论哲学问题了。这种相似性，使得几代计算机科学家都在做着一个努力：让电脑像人脑一样工作。 或许这并不是计算机被发明的初衷，但它俨然已经成为了我们的终极计算之梦。 再深入地想一下，除了前面提到的自我意识之外，我们会发现计算机和人脑之间有很大的差异。首先就是性能上的差异。计算机更适合做那些死板的工作，当我们把一套算法输入给计算机后，它就会飞快地按照这个算法进行计算。例如，我们要找一幅的图中的最短路径（这幅图很复杂，以至于我们不可能一眼就看出最短路径），当我们把这幅图和相应的算法（例如Dijkstra算法）输入给一个计算机，它就开始疯狂地、严格地依据算法按部就班地计算，并且会在一个不长的时间内给出答案。 那么，试想一下如果让我们人来找最短路径该怎么办？我们同样面对一幅很复杂的图。当然，会有人用投机的方法直观地给出一条最短路径，但这总是不可靠的。一个“不聪明”的办法就是按照Dijkstra算法一步一步来计算。当然，我们每一步都要用一种方式（纸和笔）记录路径的信息。最终，我们也总能找到一条最短路径，但正如你想象的，我们花的时间比计算机要多很多很多。 上面说的是一个人脑不如计算机的例子。那么，有人脑超过计算机的的例子吗？当然有，而且它们生活中无处不在。想像一下我们平时上网时总会遇到一个讨厌的东西——验证码。经过痛苦地辨认，我们最终还是认出了藏在图形里面扭曲模糊了的字母数字。此刻，你可能在责备网站的管理员多此一举。殊不知，这是为了防止计算机程序的恶意注册才设置的。也就是说：计算机没法认出验证码。或许你最近听说过某家的验证码被攻破了之类的新闻，但总体来说，人们还没有想出一个通用的方来使计算机认出验证码，否则就辜负了验证码的由来了——完全图灵测试。 你一定已经听说过这个名词，把一台计算机和一个人分别关在小黑屋里，然后有另一个人向这它们问问题。当提问的人分不出哪个是人哪个是计算机时，我们说这台计算机通过了图灵测试。所以，现在最简单的提问方式就是给他们一套验证码图片，能认出来的就是人，否则是计算机。 从理论上讲，计算机可能通过图灵测试吗？至少据我所知，这个问题还没有确切的答案。我们不得不回到深奥的理论上来。 我们假设存在一个数学模型可以描述人的大脑行为，那么，根据这个模型语言的完备性，我们可以很容易地判断图灵机究竟能否模拟人脑。然而，如果根本就没有可以描述人类大脑的数学模型呢？“没有”是个很模糊的概念，也许某一天数学家可以证明，人类大脑的行为是无法用数学模型甚至任何语言描述的。这听起来很荒唐，或许这正是我们的“终极计算之梦”的答案。