IDSeeX

黄亚生：中国经济增长的南柯一梦

11106028@qq.com(IDSeeX) — Mon, 16 Nov 2009 04:32:51 GMT

黄亚生：中国经济增长的南柯一梦

还记得风靡一时的“脱钩论”吗？就在不久前，西方分析师，尤其是投资银行的经济学
家们还在贩卖一个说法，即中国本身已成为一个强有力的经济中心，不但能够独立于美
国之外自行增长，还能为全球经济的增长提供动力。

但凡这些华尔街经济学家目前仍没有失业, 他们中很少会有人再提出如此论调了。中国
不断传出的经济数据正在使人清醒过来。最新数据显示，依然在中国经济中起骨干作用
的出口出现了7年来的首次负增长。这是受海外需求增速放缓拖累所致。更糟糕的是进口
也急速下降，这明确显示出中国的内需正在下滑。两件事结合在一起让人不难看出，中
国经济即将面临严峻挑战。显然中国经济无法逆全球趋势而动。

为什么那些脱钩论者会错得如此离谱？搞清楚这一点很有必要。脱钩论源自于错误的经
济分析，而脱钩论的失势尚未使这些分析失去市场。揭穿这些分析的假面对中国政府今
后的政策制定将有重要意义。

经济学家们的根本问题或致命偏好就是对一些简单的经济指标太过重视，尤其是对国内
生产总值(GDP)数据。如果你问一位专业经济学家中国有多少省，他可能两眼发呆。但如
果你问他中国的GDP增长率是多少，他会马上告诉你说，中国经济过去30年的平均增长率
达到两位数，按照这个增长速度中国经济会在 2035 年 (或其他某一天)超过美国。GDP
中心论是经济学家们常犯的毛病，它往往使人不去做更深的研究。这一点从经济学家和
分析师们大肆追捧高盛(Goldman Sachs)那赫赫有名的“金砖四国”说上便可见一斑。高
盛在研究报告中预测巴西、俄罗斯、印度和中国经济将急剧增长，而这份报告的依据比
小学五年级算术高明不了多少。

那些痴迷于中国GDP高增长率的人经常忽略了探讨导致这一高增长的原因，以及这种增长
是否可自我持续。而这正是脱钩论痴迷者的硬伤，也是政策制定者容易犯大错误的地方
。比方说，让我们考察一下有关中国家庭收入的数据。中国家庭收入增长非常缓慢，这
种情况在农村家庭中尤为明显。过去20年左右，中国农村家庭收入增幅只及中国GDP增长
率的一半。中国GDP增长和家庭收入增长的一快一慢意味着，中国以牺牲自身消费基础为
代价创造了巨大的生产能力。仅这一个事实就应足以推翻脱钩论了。那些新生成的“富
余”生产能力必须转向什么地方，这就是美国。更进一步说，中国的农村家庭收入和GD
P增长率之间的鸿沟持续存在这一事实表明，随着时间的推移，中国经济增长已经愈来愈
成为美国消费欲望的衍生品。

这就引发了一个重要的政策问题：中国经济增长为何以及怎样系统性地损害了中国自身
的消费潜力。要回答这个问题，人们首先要搞清楚中国GDP的高增长是如何实现的。虽然
中国经济增长应部分归功于经济自由化，但经济增长中由市场驱动的部分并不大，且还
在逐渐减弱。而与此同时，严重受控于政府的固定资产投资增速却从上世纪80年代的30
-35%提高到了当前近45%的水平。90年代中期以来，中国的GDP增长主要得益于由政府组
织的基础设施、城市建设以及城市化方面的大规模投资。这种高度依赖政府投入的经济
增长对中国消费潜力造成了最严重的破坏，进一步提高了中国对发达国家市场的依赖度
。

让我来举例说明这一点。与中国急于吸引外资的地方官员打过交道的许多外国投资者，
对下面这些话应该不会陌生：“你想在一片人口居住密集的10英亩土地上新建工厂吗？
没问题。我们会在三周时间内为你清理出这片土地。”许多外国投资者都对中国地方政
府这种“亲商”态度称奇，与似乎无法将这些事情做好的印度政府比起来，更是形成了
鲜明反差。

但这种“亲商”做法正是问题的核心所在。当自己的住宅用地被转为工商业用地时，许
多中国家庭几乎得不到到任何经济好处。中国政府对国内全部土地都拥有正式所有权，
它能够以在市场经济国家不可想像的规模将一块土地上居住的家庭异地安置，而这些家
庭所获补偿往往远低于他们所让出土地的市场价值。正因为如此，工厂主们在中国的办
厂成本会大大低于其他国家，而成千上万幢摩天大厦也会彷佛一夜间便从中国许多城市
冒了出来。

但中国也无法摆脱一个基本经济规律的支配：一个人的成本就会是另一个人的收入。工
厂主和房地产开发商在中国的低成本，也就意味着中国经济生活中其他一些参与者的低
收入。而中国这些只拿到低收入的人碰巧又是国民中的大多数，其中尤以农村居民为多
，他们几乎没有什么政治力量来保护自己的权益。因此一条创造私人财富的可靠途径─
─小土地所有者在城市化进程中以市场价格向开发商出售土地，在中国几乎完全缺失，
尽管中国的城市化正在以惊人的速度进行着。

所有这些都大大超出了脱钩论的争论范围。要真正扭转中国经济的失衡局面，中国政府
必须致力于推动中国人民的收入增长，而不能只盯着GDP增长。要做到这点有一个直截了
当的做法，那就是在土地开发时采用市场定价原则，允许和鼓励开发商以竞价方式从农
民手中获取土地，并将这作为政府当前经济刺激方案的一项内容。过去两年中，中国领
导层在降低农民负担方面做得很不错，比如说取消了农业税，降低了教育和医疗收费等
。现在是增加农民收入的时候了。

环顾当今世界，没有几个国家像中国那样拥有广袅的土地、勤劳而聪慧的人民以及确保
中国真正成为全球经济大国的企业家队伍。但这些潜力却被误入歧途的发展战略浪费掉
了，这一战略以牺牲消费为代价来发展生产，用政治权力来压低成本，而不是凭借市场
机制来增加收入。值此全球经济衰退之际，中国及其13亿人民正在为这一错误付出高昂
代价。

【本文作者黄亚生是麻省理工学院萨隆管理学院的的国际管理教授，他撰写了《有中国
特色的资本主义》(Capitalism with Chinese Characteristics)一书。】

抢CPU生意 NVIDIA GPU将可独立运行操作系统

11106028@qq.com(IDSeeX) — Wed, 21 Oct 2009 03:13:18 GMT

据Fudzilla的报道称，NVIDIA的高级副总裁Tony Tamasi表示Fermi具备了独立运行操作系统的能力。
当然了，Fermi并不能运行我们熟悉的Windows操作系统，但如果对Linux系统稍加优化即可靠Fermi来独立运行，这听起来相当有趣。
Fermi更加注重计算方面的提升，具备了更多的CPU功能，但即便如此仍热无法取代CPU的地位，黄仁勋亦曾在GTC大会上表示过你需要一个CPU才能运行操作系统。
NVIDIA Fermi所着重的已不再仅仅是一颗纯粹的GPU那么简单了，而是扩展到了CGPU的范畴，C代表着计算（Computation），而且相信未来还会融入更多的CPU功能。

采用Fermi架构的Tesla

医生有时候说话，是很寒的= =zz

11106028@qq.com(IDSeeX) — Wed, 14 Oct 2009 11:17:34 GMT

1我有个同学去做妇科检查，医生是个男的，　　

检查胸部是否有增生什么的时候，那医生非常嫌弃的摸了摸我同学的胸，　　

华丽丽的说了一句：没啥毛病，就是小点儿~ 哈，把我同学囧死了~

2当年去医院，陪我妈看妇科，在我妈之前的是一个差不多20岁出头的女孩，被妈妈陪着，
似乎经期不调的样子，医生说要检查　　

医生：（不抬头）有没有性生活？　　

女孩：…… 　　她妈：她小孩，没有的　　

医生：我问你女儿呢，有没有性生活？　　

女孩：…… 　　

医生：你要是破了就能直接检查不用做B超。　　

女孩：有过一次。　　

医生：（起身，准备给她做检查，嘟囔道）你还能破几次……

3有一次是生baby的时候，剖腹产，在手术室，上了麻醉，局麻，药劲上来了以后我就开始
狂抖、打冷战，不过神志是清醒的，就听麻醉师在后面说“她high了”- -|||

4ICU里每天会有十五分钟的探望,一个护士和另一个护士说,床位太紧了,外面的都安排不过
来,另一个说,不用急,你看这个,那个,和那边那个,都差不多了,过不了今晚的...很快就有地
方了..

5我做个小手术，一星期后要缝合。　　

是个新来的医生缝的，旁边有一个老医生现场指导。　　

那个年轻女生模样的医生颤颤巍巍哆哆嗦嗦缝了很久，针穿过肉的时候都很痛，我忍了很久
，快要坚持不住的时候。突然听旁边那个老医生说：喂，你这样缝不对，伤口要裂开来的。
。。要这样这样这样缝。。。　　

我当时就要崩溃了＝＝|||裂开来，我这个可是胸口上的刀呀，要裂开来是什么后果？

6手术缝合时医生跟我说：　　

给你打个漂亮的蝴蝶结！　　

奶奶的　　

又不是一辈子不拆线　　

再漂亮有个p用！

7这个是我爸爸前段时间讲给我听的　　

我妈妈在我小时候有次大出血很严重，一个小时内下了两次病危通知书　　

然后我爸在等妈妈手术的时候居然睡着了....我爸爸就是那种走到哪睡到哪的人... 　　

后来手术完了，医生出来摘下口罩把我爸吼醒说：“你还睡得着啊！你老婆死了....”我爸
爸脑袋就嗡了，然后医生补了两个字“差点！” 　　

我听了后不知道有多寒啊

8还有一次，去做x光还是什么的，需要要躺在一张床上，脱掉外面的裤子。那时我是小
loli，不好意思，结果一个帅哥医生说，怎么还不脱，你是不是没穿内裤啊…… 　

9一次单位出去吃饭，席间喝酒喝多了，　　

回到家很难受　　

朋友送我去医院打点滴。　　

结果吐得很厉害！　　

那医生很无耻的问我是不是嗑药了！

10做麦粒肿手术，眼睑被打了两针麻药，虽然痛觉剥离还是能感到医生扯着我的眼睛。。。
　　　　

战战兢兢的问：大夫~~~~你把什么扯出来了啊~~~ 　　　　

大夫：你的眼珠子。。。-

11　我牙齿痛，到医院去看，女医生掰开我的嘴看的时候，夸奖我说，你的牙齿跟仓库一样
，什么都有

12 我老婆讲的啊，我老婆做护士的他们医院还有个结巴主刀，　　

有次手术中说了句：剪....剪.... 　　

他带的那个实习医生就一溜剪下去　　

然后他说：哎剪子给..给我!!....谁他妈...让.....让你剪的...我是要..要剪子！！

【zt】婚礼当天新娘拒嫁，新郎立马迎娶女同学

11106028@qq.com(IDSeeX) — Wed, 14 Oct 2009 07:42:30 GMT

婚礼当天新娘拒嫁，新郎立马迎娶女同学　
10月5日，网友“沈郎”，向网友们讲述了牛人牛事：　　这是一个婚庆公司的老板告诉我的，绝对属实！前些天有个婚礼，由于生意不算忙，婚庆公司老板就自己开着车去了，结果新郎从7点多上楼接新娘，直到中午11点还没下来！老板怒了，上楼一看，新娘子在拿捏新郎！说之前看好一个大液晶电视，新郎没给买，让他现在去买！新郎说后补，新娘不干！说现在不买就不结！最后新郎怒了！说再问你一遍：“跟不跟我走？”新娘说不走！新郎扭头就跟伴郎、摄像等人说：“走！”楼下的车队一个也不吭声！老板问他去哪？他说去某某小区。去了之后给一个女孩跪下，让她嫁给他，说一定给她幸福、对她好！跪了好久！结果，就真的带下来一个没穿婚纱的新娘。　　老板说：“我靠！哥们你还有替补队员啊？” 　　新郎说：“你别拿我开心了！这个是我同学，一直喜欢我，是我以前有眼无珠……” 　　据说后来准新娘去闹会场了！而且新娘家的也开始闹。新郎说是她自己不嫁我的！　　第二天就和原来的新娘办了离婚，要和他那个同学办结婚证！厉害吧，这就叫爷们！　　
------------------------网友回复----------------------- 　
　46楼【suntaohenshe】：支持哦，以前我邦我同学去迎娶新娘也是这样，从中午一点去，到了晚上6点还不肯走。我同学气了，掉头就走，说这个老婆我不要了.当天晚上，这家里人连夜的把新娘送过去，我同学还是不要，最后到第三天离了　　
66楼【282778437】：和我一样，年初我父母送钱给我买房子（那时候我还在另一座城市工作，和女友一起），女友家分文不出。我父母让先登记再交首付，女友死活不肯，非要彩礼，才登记。我一怒之下，辞去那边工作，彻底分手，随父母回到老家找了份工作，男人就要对自己狠一点！　
　69楼【jones911】：我们小区也有过这种事情，结婚那天，新娘因为位子的问题跟新郎大吵，据说她要坐东面，让新郎不识趣的坐了，后来小朋友说让新郎抱过去坐东面都不行，晕掉，这种新娘也有，反正闹到后来，娘家人全来了，婆婆给她下跪都不行，那天就直接回娘家了，第二天办了离婚，婆家没办法把她的嫁妆全卖了，弥补损失，现在过去几年了，那男的已经结婚，小孩子也挺大了，听说那女的两年后还没嫁出去，现在不知道怎么样了，这种人我想谁敢要啊，其实那男的我见过，挺不错的，做牙医的，晕，那女的一定要占便宜，连个位子都不肯让，这种人啊其实没结好，结了以后的日子有的苦了！　
　159楼【gntlman】很多时候搞不懂那些女的是怎么想的。不知道是不是没文化、没修养的女人？结婚的前提是你愿意嫁给他啊，又不是闹着玩的。我认识好几个30多还没结婚的，个别是她们20出头就认识了，我发现她们或多或少都有问题，考虑问题只从“我要……”，“我想……”，“我要求男方……”单向出发，而不去想自己做了哪些事情，或者自己有哪些优势，让男方觉得为她做这些事情是值得的。真是夷匪所思啊！！

剑3程序讲述剑侠叁3D引擎（图）

11106028@qq.com(IDSeeX) — Tue, 13 Oct 2009 10:39:16 GMT

作者：西山居工作室/剑网3/程序　Readme　　编者按：西山居作为国内知名的游戏工作室，十余年来积累和沉淀了很多东西，无论是美术还是策划或程序或测试，无论是早期的《中关村启示录》、还是现在的《剑侠情缘》系列。金山官方博客将会邀请西山居美术、策划等同事为我们分享游戏制作过程中的点点滴滴。希望通过这些，能够让大家更多地了解到游戏是如何“炼”成的，也希望通过此，为有志于游戏行业的朋友们提供一些指导和建议。
　　本期我们有幸邀到了剑3的程序Readme来为我们讲述“剑侠叁3D引擎”。

　剑侠情缘叁为什么要自己开发引擎？
　　剑侠情缘叁是西山居的第一款全3D网络游戏，使用的是我们自主开发的剑侠叁3D引擎。也许有人会好奇的问：市面上有这么多的游戏引擎，为什么不选择成熟的引擎而要选择自主研发呢？你们真的有信心能做的出来？这个问题就需要从金山的传统说起了。金山是一个以技术立业的公司，我们的核心竞争力在于自主研发能力。从WPS到毒霸再到剑侠情缘网络版，都是从无到有，自主研发出来的。全3D网络游戏代表着网络游戏的发展趋势，而其中的核心技术之一就是3D图像引擎。3D图像引擎技术的理论基础是计算机图形学，这是一门成熟的学科；而在开发剑叁3D引擎之前，我们使用过一款商业化的引擎，在技术上有了一定的积累。有了理论的指导和实际的经验，我们对自主开发并完成一款3D引擎有相当的信心。我们也希望通过引擎的开发建立一支稳定高效的团队。在剑叁引擎的开发过程中，我们的团队始终保持着对技术的不懈追求，不断的完善着3D引擎的功能和效果。同时通过和美术策划同事的合作，我们在引擎相关工具的制作上也积累了大量的经验。这些收获为我们今后追求更高的目标打下了坚实的基础。
　　我们做了什么？
　　从立项到现在，剑侠情缘叁经过了多年的开发。在这漫长的过程中，我们都做了些什么呢？我们主要的工作包括3D图像引擎和相关的工具的开发。
　　图像引擎的作用，是把抽象的数据转换成图像显示到屏幕上。剑叁采用的是由多张地图组合成为整个游戏世界的方式。我们把每张地图都称为一个场景，玩家的人物就在各个场景中活动。场景由多个部分组成，比如说大地我们称为地表；地上的房子、树、城墙什么的，被称为物件；玩家的人物，NPC等活动的元素，被称为活动物件。3D引擎的作用，就是组织好地表和分布其上的物件和活动物件，把它们按照策划和美术同事的设计完美的显示出来。
　　在剑侠情缘叁开始之前，我们做了一个小的演示程序。这个演示的主要目的是测试一些关键的技术是不是可行，效果如何，并且为美术同事制定美术元素制作规范提供参考。当时，剑侠情缘叁是一个采用传统2D游戏斜45度视角的游戏，所以我们的演示程序也是按照这个要求来做的。通过这个Demo，我们主要测试了2D逻辑下的场景管理，3D模型和特效的显示，骨骼和顶点动画技术。

技术测试的3D引擎项目炸弹人

　　在这个Demo里玩家可以控制一个人物在场景里来回跑动，放置炸弹。玩法和以前FC上的炸弹人类似。当然这个Demo不是说剑侠情缘要做成这样的游戏，他的目的是帮助我们测试上面提到的关键技术，证实已知的方法是确实可行的。测试完成的相当不错，这些技术到现在的都还在使用中。
　　有了良好的测试结果，我们就准备开始大干一场了。在M1的期间（PS， M是指里程碑，是我们对项目一个目标阶段的说法），我们制作了地图编辑器和特效编辑器。有了地图编辑器，美术同事可以给地表刷上不同的图，表现出草地、沙地之类的变化，然后在刷好的地表上，摆放上房子、路灯、树等等物件，再加上NPC，一个基本的场景就完成了。我们就可以进入到场景里，活动活动腿脚，欣赏下美丽的风景，和NPC做做友好的交流；有了特效编辑器，我们就可以制作火焰、雨雪、水花这些华丽的效果，把这些东西也放到场景里面，画面就显得更有生气了。
　　随后我们的工作主要是一些修整和完善。等到WOW推出之后，我们发现2D方式的斜45度视角和WOW的全开放视角比起来，在表现力和游戏体验上都有相当的差距。所以整个项目组在讨论之后，在剑侠情缘叁M2.1的时候作出了一个重大的决定。我们放弃了斜45度锁定视角，转而采用全开放的视角。
　　这个决定对3D引擎的影响是巨大的。本来我们采用斜45度视角只要把以前2D游戏的场景管理方式稍加修改就可以了，但改成开放视角之后，需要采用全新的场景管理方式。更要命的是，这个变化不只影响到我们3D引擎，还影响到美术的的制作。

M1时的剑叁3D引擎截图

　　对程序来说，3D场景的管理，是有着成熟的技术理论的支持的。经过一段时间的努力，我们完成了程序上的调整。但是这并不代表整个项目调整的完成。全开放视角对美术的场景制作的观念也带来了巨大的冲击：以一个房子来说，在开放视角下，玩家可以从各个角度各个距离观察这个房子，而以前45度锁定视角，玩家只能在一个固定的角度和有限的距离范围内来查看。这就对房子的制作精度有了更高的要求。很多美术之前出于效率考虑采用的优化方法，比如说只制作能被看见的部分，就不能再被使用了。
　　开放视角带来的另外一个问题，是可视距离增大带来的场景复杂度的上升。以前斜45度视角只能看到有限的范围，而开放视角之后，如果在平视状态下，视野范围会比以前大很多倍。在程序上，我们采用了LOD技术来动态的调整场景的复杂度，以达到效率上的要求。而对美术来说，场景的规划比以前有了更高的要求，把很多的东西集中的堆在地图某些区域之内是绝对不被允许的。如何合理的规划一张地图上的物件，物件应该如何制作才能在画面效果和运行效率间找到平衡，这些都是急需解决的问题。
　　因为美术同事也是第一次制作全3D的地图，缺乏全3D场景的制作的经验。所以他们也做了一个Demo，一张模板地图。最终的选择是剑侠情缘叁的新手村地图。就好像玩家今后都诞生于新手村一样，我们其他所有的地图也都诞生自新手村地图。通过这张地图的制作，美术同事总结出了地图制作和物件制作的规范。那个过程是痛苦而快乐的。痛苦在于很多之前的美术工作被完全的推翻和制作上作出的许多调整；快乐在于开放视角带来的全新游戏体验：忽然可以看到一个广阔的空间的震撼，是每一个从锁定视角游戏过渡到开放视角游戏的玩家都难以忘却的。

M2.1改版之后的剑叁3D引擎

　　在程序的调整完成之后，我们的程序员爆发出了旺盛的创造欲望。那时显卡的可编程管线技术已经比较普及了，所以我们修改了3D引擎，正式加入了对可编程管线的支持。对于热爱画面表现胜过一切的3D图像程序员来说，这就好像打开了通往新世界的大门。基于贴图模板的四层地表贴图、法向量贴图、水面反射、全屏幕特效、环境光阻挡图，预渲染阴影图、柔体，剑侠情缘叁的画面就像从侏罗纪公园回到了现实中。
　　在那之后一直到现在， 3D引擎组除了继续美术工具的制作之外，提高渲染效率和效果的变成了我们的主要工作。
　　更高的渲染效率，意味着图像引擎可以承受更高的场景复杂度，也就是说可以在场景里面放置更多的东西，让画面显得更丰富，从而提高整体画面感觉。在这方面我们通过优化场景管理和渲染流程，并采用了一些DX9的新技术，效率得到了显著提升。然后我们充分使用了这部分优化带来的空闲性能，实现了大规模地形植被（地上长满了各种各样的植物），动态光影（从此不再只有刀光没有剑影了），并整合了物理引擎（长袖飘飘的效果）。
　　在美术的工具上，在完成基本功能之后，我们的工作重点放在了工具的易用性上，主要的方向是制作工具的自动化。举个例子来说，比如需要在地图上的两个地方之间勾出一条道路。以前的做法，是美术用类似画笔的工具在这个路线上画上道路的贴图。设想一下，如果两个点之间有一公里远，那么美术同事就需要用笔刷一点点的涂完这个一个公里的长度。如果有这样一个工具，只要在两个点之间连一条线，并在两点之间根据需要设定一系列的关键点，然后点“确定”，瞬间就可以自动生成一条连接两点，并且经过所有关键点的道路，世界会变得多么美好。

目前的3D引擎效果

　　剑叁3D引擎的历史到这里基本上就介绍完了，更多的历史在等待着我们去书写。剑侠情缘叁背负着西山居的光荣与梦想，体现着金山对技术的执着追求，能够参与这样一个激动人心的项目，是我们每一个人的荣幸。

部分同事在去年愚人节剑叁发生大头事件的合照

How to optimize code for MMX processors.

11106028@qq.com(IDSeeX) — Sat, 10 Oct 2009 03:11:45 GMT

JPEG compression has done bad things to this image; click on it to see a PNG of the same scene (288K).
Table of Contents:

0.Caveat
I wrote this document in 2000. Since then, everything has probably changed. So, if this document conflics with what you have learned elsewhere, trust them, not me.
1.Who this document is for:
This document is for you if you are a programmer who needs speed in your application. I will assume that you have a basic knowledge of x86 assembly language. (skip this) Many people have not used the GNU assembler; I will discuss briefly how its syntax differs from traditional Intel style assemblers: Intel:
add (edx), eax
GNU (AT&T):
addl %eax, (%edx)
The order of arguments is reversed; registers have a % in front of them. Constants start with $. All instructions end with a single letter representing their type: l = 32 bits, w = 16 bits, b = 8 bits Intel:
add ebx:[ecx * 4 - 4], $8
GNU (AT&T)
addl $8, -4(%ebx, %ecx, 1)
GNU syntax is easy to get used to, and after a few minutes, you won't even notice that you are using it. To assemble a source file, just use GCC on it as if it were a C program:
gcc -l baz -o foo foo.s foobar.c

2.When to use MMX
MMX is good for low-level pixel manipulation, digital signal processing, 3D geometry, and much more. Since I am a 2d graphics hacker, this document will discuss only the first. For specific algorithms in other areas, see Intel's web site1.
Use MMX only when you need the speed. To turn a function into an fully optimized MMX function will take a few hours. It is not worthwhile for code that will only be called occasionally. Make sure that you are using the best algorithm before you convert a function to MMX; if you change the algorithm, you'll have to start the conversion more or less from scratch.

3.When not to use MMX
MMX is integer only. If you need floating point accuracy, you can use SSE (available only on Pentium III processors, and not discussed in this document). MMX will not speed up memory accesses. If your algorithm requires frequent random-access memory lookups, it will likely not benefit from MMX. MMX cannot be mixed with floating point code. It borrows the floating point registers for itself.

4.Assumptions in this document:
a. 32 bit color will be used. 32 bit color is in the format ABGR. The A is not used for anything by default (although it can be). b. All data will be aligned properly. GCC will do this for you with -O. c. Images will have an even number of pixels in the X direction. d. For performance discussions, all data is assumed to be in the L1 cache.

5.MMX registers and instructions:
MMX operates on 64 bit registers (mm0 - mm7). The MMX registers are actually the floating point registers. To avoid horrible bugs, use the emms instruction at the end of your MMX code.
The registers can each be divided into 8 bytes, 4 words, 2 doublewords, or left undivided as 1 quadword. The MMX instruction set consists of 56 instructions which operate on MMX registers, plus emms. A good reference for the MMX instruction set is available on Intel's web site2.
MMX instructions (except for movd, movq, and emms) start with p and end with a letter representing the data type they operate on. For example, paddw adds words. Some MMX instructions convert types; they have a longer type description. Packsswb and punpckldw are examples of this. Packsswb converts words to bytes, and punpckldw converts doublewords to words. Some instructions end with ss or us; these mean signed or unsigned saturation. Saturation means that values are clamped to a max rather than overflowing, so that if a and b are bytes containing 100 and 200, adding with unsigned saturation will produce 255, not 44.

6.How to begin:
Start by writing your function in C. Compile it to assembly language source using gcc -S -O3 foo.c -o foo.s For this example, put just the function to be optimized in foo.c. Mostly MMX is used for texturing, lighting, or blending effects. This means that you'll have a loop that looks like this: for (y = 0; y < ysize; y ++) { for (x = 0; x < xsize; x ++) { .... } }
Locate the inner loop in the assembly language output and try to identify what gcc has done with the parameters and local variables. An inner loop might look like this: .L10: movl 32(%ebp),%ecx movl (%ebx,%ecx,4),%eax ... movl (%edx), %eax ... really long section of code with lots of shifts and the like ... movl %eax,(%edx) addl $4,%edx incl %ecx cmpl %edi,%ecx jl .L10
Let's look at the last 4 lines first: First, edx, which is a pointer into the destination buffer, is moved ahead by one pixel. Similarly, ecx is incremented. The jump to the top is not at all out of the ordinary. The last line before the loop control stuff usually puts the final product into the destination buffer. This shows us what register is used to index that buffer. Likewise, one of the first lines usually grabs data from one of the source buffers. This example uses 2 source buffers, one of which is also the destination.

7.MMX conversion:
Once you have located these buffers, delete every line but those that get data from the source buffers or put it into the destination buffers (also save any instructions they need to set up pointers to these buffers). You will be re-writing the algorithm to operate in parallel. Alter the remaining instructions to use MMX registers. For the code listing presented above: .before_loop: movl 32(%ebp),%ecx.L10: movd (%ebx,%ecx,4),%mm0 movd (%edx), %mm1 movd %mm1,(%edx) addl $4,%edx incl %ecx cmpl %edi,%ecx jl .L10
At this point, it is worthwhile to consider how to work with your data in parallel. Some algorithms can operate on 2 pixels with each MMX instruction. Usually these are algorithms that do not involve multiplication. One example of this is simple sprite transparency (not translucency). Mostly, algorithms will operate on one pixel per instruction. MMX has instructions to pack and unpack data; these are critical to one-pixel-per-instruction applications. An example of a one-pixel-per-instruction algorithm is tinted lighting. This takes a light buffer, a tint color, and a canvas, and writes back to the canvas. The image at the top of this document is from a program which uses this effect. The effect shown in the image is based on an effect from the game Nox (but improved). I don't know for sure how they do it, but the listing it 8 (h) is how I did it. Near the beginning of the function, the tint should be unpacked: movd 16(%ebp), %mm6 punpcklbw %mm7, %mm6
Mm7 is zero in this case; often it is useful to keep one register as zero for unpack operations. The result of this for an orange tint is : (before) 16(%ebp) = |00000000|11111111|10000000|01000000| (after) %mm6 = |00000000|00000000|00000000|11111111|00000000|10000000|00000000|01000000|
Our listing with unpacking and repacking will be: .L10: movd (%ebx,%ecx,4),%mm0 punpcklbw %mm7, %mm0 movd (%edx),%mm1 punpcklbw %mm7, %mm1 packuswb %mm7, %mm1 movd %mm1,(%edx) addl $4,%edx incl %ecx cmpl %edi,%ecx jl .L10
Notice that this still doesn't have code to do anything. Here is a version with such code: .L10: movd (%ebx,%ecx,4),%mm0 punpcklbw %mm7, %mm0 movd (%edx,4),%mm1 pmullw %mm6, %mm0 psrlw $8, %mm0 packuswb %mm7, %mm0 paddusb %mm0, %mm1 movd %mm1,(%edx) addl $4,%edx incl %ecx cmpl %edi,%ecx jl .L10
In this case, it seems that mm1 doesn't need to be unpacked or repacked (since it isn't being multiplied), so those instructions were removed. I will now discuss briefly how the algorithm works (skip this). movd (%ebx,%ecx,4),%mm0 punpcklbw %mm7, %mm0(before) %mm0 = |00000000|00000000|00000000|00000000|00000000|11111111|10000000|01000000| (after) %mm0 = |00000000|00000000|00000000|11111111|00000000|10000000|00000000|01000000|
mm0 (in this case, representing a brownish color) is unpacked so that it can be treated as 4 16-bit words.
movd (%edx,4),%mm1 (after) %mm1 = |00000000|00000000|00000000|00000000|00000000|11111111|11110000|01000000|
mm1 gets the old value of this pixel on the canvas (cyan).
pmullw %mm6, %mm0(before) %mm6 = |00000000|00000000|00000000|01000000|00000000|01000000|00000000|01000000| %mm0 = |00000000|00000000|00000000|00000000|00000000|11111111|00000000|01000000| (after) %mm0 = |00000000|00000000|00000000|00000000|01111111|10000000|00010000|00000000|
mm6 (the tint) is multiplied by mm0, the lightfield. In this case, the tint is a dark gray.
psrlw $8, %mm0(before) %mm0 = |00000000|00000000|00000000|00000000|01111111|10000000|00010000|00000000| (after) %mm0 = |00000000|00000000|00000000|00000000|00000000|01111111|10000000|00010000|
mm0 is shifted down 8 places. This is because each channel (R, G, B) of the tint ranged from 0 to 255, as did the light field. This gave us a total range of 16 bits. Only the most significant 8 are needed, so mm0 is shifted.
packuswb %mm7, %mm0(before) %mm0 = |00000000|00000000|00000000|00000000|00000000|01111111|10000000|00010000| (after) %mm0 = |00000000|00000000|00000000|00000000|00000000|00000000|01111111|00010000|
mm0 is repacked. Now the top 4 bytes are 0 and the bottom 4 are ABGR again.
paddusb %mm0, %mm1 (before) %mm0 = |00000000|00000000|00000000|00000000|00000000|00000000|01111111|00010000| %mm1 =|00000000|00000000|00000000|00000000|00000000|11111111|11110000|01000000| (after) %mm1 =|00000000|00000000|00000000|00000000|00000000|11111111|11111111|01010000|
mm0 and mm1 are added with unsigned saturation. This means that values over 256, are clamped to 256. You can see this in the green channel.
movd %mm1,(%edx)
This line puts the result of the addition back onto the canvas. The last four lines increment the index registers and loop.
This now does exactly the same thing as the 30 instructions that it replaces. It is slightly faster than the non-MMX version, but can still be improved.

8.Optimization
a.Analyze the running time of the inner loop; consider the time taken by each instruction. The Pentium processors have 2 pipelines; certain instructions can only be issued in the U pipeline, and certain instructions can only be issued in the V pipeline. Most MMX instructions can be issued in either. Some instructions cannot be executed at the same time as others; for a full list of pairing rules, see:
http://fatphil.org/x86/pentopt/28.html
Listing with instruction timing: Instructions that pair are shown together. .L10: movd (%ebx,%ecx,4),%mm0 ;1 and used. This doesn't pair since punpcklbw %mm7, %mm0 ;2 mm0 is assigned and used movd (%edx),%mm1 ;3 memory accesses must be in the U pipe pmullw %mm6, %mm0 ; MMX multiplies take 3 clocks ;4 It would be good to fill up this ;5 time somehow. psrlw $8, %mm0 ;6 this and each of the next 3 lines packuswb %mm7, %mm0 ;7 depend on the last; paddusb %mm0, %mm1 ;8 no pairing can happen here. ;9 stall: store must wait 2 cycles ; after update movd %mm1,(%edx) ;10 addl $4,%edx ;11 incl %ecx ; cmpl %edi,%ecx ;12 jl .L10 ;
This listing takes 12 clocks per pixel.
b.Some code turns out to be redundant: movd (%edx,4),%mm1 ... paddusb %mm0,%mm1
can be replaced with: paddusb (%edx,4),%mm0
This accomplishes the same thing with fewer cycles and fewer registers Simple rearrangement yields: .L10: movd (%ebx,%ecx,4),%mm0 ;1 punpcklbw %mm7, %mm0 ;2 pmullw %mm6, %mm0 ;3 incl %ecx ;4 addl $4,%edx ; ;5 psrlw $8, %mm0 ;6 packuswb %mm7,%mm0 ;7 paddusb (%edx,4),%mm0 ;8 ;9 movd %mm0,-4(%edx) ;10 cmpl %edi,%ecx ;11 jl .L10 ;
This saves only one instruction. One reason that this gives such a small change is that the algorithm is very linear; each step depends on the last. c.Since all of our data has an even number of pixels in the x dimension, unrolling the loop will be simple, and could give better performance e: Simple unroll: .L10: movd (%ebx,%ecx,4),%mm0 ;1 punpcklbw %mm7, %mm0 ;2 pmullw %mm6, %mm0 ;3 incl %ecx ;4 addl $4,%edx ; ;5 psrlw $8, %mm0 ;6 packuswb %mm7,%mm0 ;7 paddusb (%edx,4),%mm0 ;8 ;9 movd %mm0,-4(%edx) ;10 movd (%ebx,%ecx,4),%mm0 ;11 punpcklbw %mm7, %mm0 ;12 pmullw %mm6, %mm0 ;13 incl %ecx ;14 addl $4,%edx ; ;15 psrlw $8, %mm0 ;16 packuswb %mm7,%mm0 ;17 paddusb (%edx,4),%mm0 ;18 ;19 movd %mm0,-4(%edx) ;20 cmpl %edi,%ecx ;21 jl .L10 ;
(10.5 clocks per pixel). The only difference is that the loop instructions are only done once every other pixel, rather than every pixel. It would be simple to make the index increments do twice as much, and reduce the number of clocks to 10 per pixel. This will be done later.
d.The next step is to interleave the calculation of the first pixel with the calculation of the second. Generally, a good strategy is to move the first instruction of the second pixel up to below the first instruction it can pair with, and continue with each of the instructions of the second pixel in a linear manner. Note how the instructions of the second pixel fill up the delay that the first multiply causes. Be careful when moving lines with memory accesses; If you move one across an increment, you will need to change the index of your access.
.L10: movd (%ebx,%ecx,4),%mm0 ;1 movd 4(%ebx,%ecx,4),%mm1;2 punpcklbw %mm7, %mm0 ; pmullw %mm6, %mm0 ;3 mm0 is next used in clock 6 punpcklbw %mm7, %mm1 ; addl $4,%edx ;4 pmullw %mm6, %mm1 ; mm1 is next used in clock 8 incl %ecx ;5 addl $4,%edx ; psrlw $8, %mm0 ;6 incl %ecx ; packuswb %mm7,%mm0 ;7 paddusb -8(%edx),%mm0 ;8 packuswb %mm7,%mm1 ; psrlw $8, %mm1 ;9 movd %mm0,-8(%edx) ;10 paddusb -4(%edx),%mm1 ;11 ;12 movd %mm1,-4(%edx) ;13 cmpl %edi,%ecx ;14 jl .L10 ;
This is certainly an improvement, at 7 clocks per pixel, but the tail end of the function has a bunch of non-paired instructions, and there are still 4 index increment commands when there should be 2. There is also a space to fill between the multiply of mm0 and its next use, as well as 2 gaps between writes to registers and their stores to memory.
e.Our next step is to remove the extra increment commands and move the first 5 lines of the loop to the end: .before_loop: movd (%ebx,%ecx,4),%mm0 movd 4(%ebx,%ecx,4),%mm1 punpcklbw %mm7, %mm0 pmullw %mm6, %mm0 punpcklbw %mm7, %mm1.L10 pmullw %mm6, %mm1 ;1 psrlw $8, %mm0 ; packuswb %mm7,%mm0 ;2 addl $8,%edx ; paddusb -8(%edx),%mm0 ;3 addl $2, %ecx ; psrlw $8, %mm1 ;4 movd %mm0,-8(%edx) ;5 packuswb %mm7,%mm1 ; movd (%ebx,%ecx,4),%mm0 ;6 Moved from top paddusb -4(%edx),%mm1 ;7 punpcklbw %mm7, %mm0 ; Moved from top pmullw %mm6, %mm0 ;8 Moved from top movd %mm1,-4(%edx) ;9 movd 4(%ebx,%ecx,4),%mm1;10 Moved from top punpcklbw %mm7, %mm1 ;11 Moved from top cmpl %edi,%ecx ;12 jl .L10 ;
This takes us down to 6 clocks per pixel. There are now 6 un-paired instructions, but no stalls. Continuing to move instructions from the top to the bottom will not be productive; there appears to be no way to rearrange the instructions to fill the holes left by the stalls. One reason for this is the high percentage of memory accesses. Since MMX instructions that access memory can only be issued in the U pipe, only one may be issued per cycle. This severely limits pairing opportunities. f.Another unrolling (4 pixels per iteration) would make the loop almost unmanageable. Nonetheless, to get to the optimal performance level, it is necessary. I will start with the code from d, since it is doesn't require priming (code before the loop). Basic unrolling: .L10: movd (%ebx,%ecx,4),%mm0 movd 4(%ebx,%ecx,4),%mm1 punpcklbw %mm7, %mm0 pmullw %mm6, %mm0 punpcklbw %mm7, %mm1 addl $16,%edx pmullw %mm6, %mm1 psrlw $8, %mm0 addl $4, %ecx packuswb %mm7,%mm0 paddusb -16(%edx),%mm0 packuswb %mm7,%mm1 psrlw $8, %mm1 movd %mm0,-16(%edx) paddusb -12(%edx),%mm1 movd %mm1,-12(%edx) movd -8(%ebx,%ecx,4),%mm2 movd -4(%ebx,%ecx,4),%mm3 punpcklbw %mm7, %mm2 pmullw %mm6, %mm2 punpcklbw %mm7, %mm3 pmullw %mm6, %mm3 psrlw $8, %mm2 packuswb %mm7,%mm2 paddusb -8(%edx),%mm2 packuswb %mm7,%mm3 psrlw $8, %mm3 movd %mm2,-8(%edx) paddusb -4(%edx),%mm3 movd %mm3,-4(%edx) cmpl %edi,%ecx jl .L10
g.Interleaving:
When the loop was unrolled the first time, code was interleaved from the first and second pixels. This time, interleaving will be easier, since there are more choices of instructions. The strict form of this strategy, where instructions from each concurrent instruction stream (in this case, each of the four pixels) are interleaved per-instruction, is called pipelining. I chose not to follow this strategy precisely, since it tends to leave the top and bottom of the loop unpaired. Instead, I just moved instructions from the second unrolling to fill out places that looked a little loose.
.L10: movd (%ebx,%ecx,4),%mm0 ;1 movd 4(%ebx,%ecx,4),%mm1 ;2 punpcklbw %mm7, %mm0 movd 8(%ebx,%ecx,4),%mm2 ;3 pmullw %mm6, %mm0 movd 12(%ebx,%ecx,4),%mm3;4 punpcklbw %mm7, %mm1 addl $16,%edx ;5 punpcklbw %mm7, %mm2 pmullw %mm6, %mm1 ;6 psrlw $8, %mm0 pmullw %mm6, %mm2 ;7 punpcklbw %mm7, %mm3 addl $4, %ecx ;8 packuswb %mm7,%mm0 paddusb -16(%edx),%mm0 ;9 packuswb %mm7,%mm1 pmullw %mm6, %mm3 ;10 psrlw $8, %mm1 movd %mm0,-16(%edx) ;11 psrlw $8, %mm2 paddusb -12(%edx),%mm1 ;12 packuswb %mm7,%mm2 movd %mm1,-12(%edx) ;13 packuswb %mm7,%mm3 paddusb -8(%edx),%mm2 ;14 psrlw $8, %mm3 paddusb -4(%edx),%mm3 ;15 ; movd %mm2,-8(%edx) ;16 ;17 movd %mm3,-4(%edx) ;18 cmpl %edi,%ecx ;19 jl .L10
(4.75 clocks per pixel)
Because the interleaving was performed from the top down, there are still a few unpaired lines at the end. The index increments pair with most things; in this listing they sit wasted at the center.

h.Perfect pairing: Compared to the convolutions needed to shave 1 cycle off d to get e, this was a piece of cake.
.before_loop: movd (%ebx,%ecx,4), %mm0 movd 4(%ebx,%ecx,4), %mm1 punpcklbw %mm7, %mm0 pmullw %mm6, %mm0 punpcklbw %mm7, %mm1.L10 movd 8(%ebx,%ecx,4), %mm2 pmullw %mm6, %mm1 movd 12(%ebx,%ecx,4), %mm3 punpcklbw %mm7, %mm2 psrlw $8, %mm0 punpcklbw %mm7, %mm3 packuswb %mm7, %mm0 pmullw %mm6, %mm2 paddusb (%edx), %mm0 psrlw $8, %mm1 packuswb %mm7, %mm1 pmullw %mm6, %mm3 paddusb 4(%edx), %mm1 psrlw $8, %mm2 movd %mm0, (%edx) packuswb %mm7, %mm2 movd %mm1, 4(%edx) psrlw $8, %mm3 paddusb 8(%edx), %mm2 packuswb %mm7, %mm3 paddusb 12(%edx), %mm3 addl $4, %ecx movd (%ebx,%ecx,4), %mm0 addl $16, %edx movd %mm2, -8(%edx) punpcklbw %mm7, %mm0 movd 4(%ebx,%ecx,4), %mm1 pmullw %mm6, %mm0 movd %mm3, -4(%edx) punpcklbw %mm7, %mm1 cmpl %edi, %ecx jl .L10 (16 clocks = 4 clocks per pixel).
The pairing on this listing is perfect. Except by using a better algorithm, this listing will be very difficult to improve.

9.Further possibilities for improvement:
In one of my applications, the width of a light field is 8 pixels. I can unroll the loop one level further, re-shuffle a little, and eliminate the loop entirely.
If the tint has only a few possible values, the light buffer can be pre-tinted in each of these, and stored. Then there is no further need for multiplies, and thus no need for unpacking. Now 2 pixels can be done at once:
.L10: movq (%ebx,%ecx,4),%mm0 addl $8,%edx paddusb -8(%edx,4), %mm0 addl $2, %ecx ;stall movq %mm0, -8(%edx,4) cmpl %edi,%ecx jl .L10
(2.5 clocks per pixel).
Note that the above algorithm will not benefit much from unrolling. Since all of the instruction but the loop instructions require memory accesses, they cannot be paired. This eliminates most of our optimization opportunities. Still, the stall can be removed: .before_loop: movq (%ebx,%ecx,4),%mm0 addl $16,%edx.L10: paddusb (%edx,4), %mm0 addl $4, %ecx movq %mm0, 8(%edx,4) movq (%ebx,%ecx,4),%mm1 paddusb 8(%edx,4), %mm1 movq (%ebx,%ecx,4),%mm0 addl $16,%edx movq %mm1, -8(%edx,4) cmpl %edi,%ecx jl .L10
(1.75 clocks per pixel)

10.Common optimization errors:
When moving instructions, be careful. You may move an instruction before one it depends on. If you are moving an instruction with a memory access and you pass an instruction that changes its index, don't forget to alter the memory access. Example: Before: addl %8, %edx movl %eax, (%edx)
After:
movl %eax, 8(%edx) addl %8, %edx
Do not forget emms. It is crucial, and omitting it causes subtle floating point bugs that will cause you to tear your hair out.

Well, you've made it to the end. Hopefully, you'll make some great MMX routines and share them with the world. If I can improve this document in any way, feel free to write to me. Let me know about broken links, especially if you can suggest resources to replace them. Better yet, write your own replacements and license them under the FDL.
Notes:1 It used to be at http://developer.intel.com/drg/mmx/AppNotes/, but Intel has rearranged their site around several times since then. Anyway, their (new?) license agreement sucks.
2 It used to be at http://developer.intel.com/drg/mmx/Manuals/prm/prm_chp5.htm,

Copyright 2000, 2001, 2002 David M. Turner.
Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.1 or any later version published by the Free Software Foundation; with Invariant Sections being The GNU Free Documentation License, no Front-Cover Texts, and no Back-Cover texts. A copy of the license is included in the section entitled "GNU Free Documentation License". Code snippets (included within

 tags) are released to the public domain (they are probably too small to copyright anyway)

A copy of the GNU Free Documentation License is available at http://novalis.org/documents/fdl.txt 

Good luck!

- David "Novalis" Turner novalis@novalis.org www.novalis.org Novalis on irc.worldforge.org

Philip Katz传奇

11106028@qq.com(IDSeeX) — Sat, 29 Aug 2009 05:10:41 GMT

Philip Katz，这个英年早逝惨淡一生的程序员，天才地缔造了ZIP这种压缩文件格式和Internet历史上最有名的共享软件之一——WinZIP。缔造了自由软件打败商业公司的典型成功范例。不仅如此，他的传奇经历曾激励着那么多的年轻人坚定地从事程序员的工作，实现他们的软件梦想。
1988年20岁的Philip对当时流行的BBS非常痴迷，然而一直为断线和传输大文件速度低下所困扰。为了将文件体积缩小或者将多个文件打包成一个文件便于传输，他经常使用那时美国BBS上比较流行的ARC压缩技术。然而，使用ARC需要对开发它的SEA公司付高额的费用，这一点令Philip 非常不满，于是自己动手开发了一个叫做PKARC的程序。这个程序与ARC完全兼容，可以压缩和解压缩ARC文件。Philip将PKARC放在网上，以共享软件的方式为其他用户提供下载使用。
用户只需为作者支付微薄的注册费就能几乎免费使用功能毫不逊色的PKARC，因此迅速获得了大批原来ARC用户的极力拥护，这无疑是在断SEA的财路。盛怒之下的SEA将Philip告上了法庭。法庭自然只相信法律而不会考虑PKARC为用户带来了什么。最后判决禁止Philip继续开发和传播 PKARC。就这样Philip被迫放弃了PKARC的开发，并为自由创新的权利被人剥夺而气愤不已。
然而这次不小的打击并没有磨灭Philip的斗志，反而激起了信奉自由和平等的他要与ARC斗争到底的决心。在这之后Philip这个天才程序员将他的智慧发挥得淋漓尽致，仅在短短的几周后，就创造了PKZIP。全新的PKZIP压缩工具，使用他发明的后来统治整个BBS世界乃至Internet的 ZIP压缩算法，比ARC速度快了将近一倍，压缩率也有一定的提高。Philip继续对PKZIP实行和PKARC一样的做法，坚持对它进行免费发放。 PKZIP的出现很快让遍及美国各大BBS的管理员们都先后将原有的.Arc格式的压缩文档转换成Philip的.ZIP格式，又推起了大家对 Philip支持的狂潮。在这种强大攻势下，不出半年光景，原来几乎一手遮天的ARC失去了生存的空间近乎于灭绝！正如后来有人评价Philip时所说的那样：“他无疑扮演了ARC掘墓人的角色，为ARC的棺材钉上了最后一颗钉子！”
Philip以一人之力，用自己开发的自由软件击败商业软件公司产品的传奇故事使他成为众多程序员顶礼膜拜的偶像。此后Philip一直坚定不移地进行PKZIP的开发和维护工作。随着PKZIP以燎原的速度被广泛使用，ZIP这种压缩文件格式最终建立并成为DOS时代的压缩标准。直到 Windows的诞生，使用Philip创造的压缩算法的软件WinZip更使ZIP格式成为Internet的传输标准，最终ZIP压缩格式成为所有压缩文档的事实标准。这些成就给这个天才程序员又增加了许多耀眼的光环。
然而，光环的背后总会有阴影的存在。这位天才程序员一直恪守自由软件的信念，长期在巨大的压力下编写软件，加之Philip的个人生活一直非常不顺利，为了释放这些压力和缓解精神上的痛楚，他没有选择合适的方式，却不正确地选择了不良的生活习惯，沾染上了许多恶习。最终长期无节制地酗酒摧毁了他的健康，也带走了他宝贵而短暂的生命。2000年4月14日，在一家汽车旅馆里，身边陪伴他的只有几个空酒瓶，就这样年仅37岁的天才程序员Philip Katz永远离开了我们。
Philip Katz的生命是如此短暂，但是，他给世人带来的恩惠却会让我们一直受益下去。现在几乎全世界的每一台个人电脑上都有用Philip创造的压缩算法生成的文档。在下载量高达到1亿4000万次、成为压缩文件标准的ZIP格式的文档开头，都嵌有Philip姓名的字头缩写字母“PK”。也许，我们可以用这种方式永远记住这个自由软件的勇士。

动态网络负载平衡集群时间方法

11106028@qq.com(IDSeeX) — Tue, 25 Aug 2009 02:46:39 GMT

1．引言
本质上讲，网络负载平衡是分布式作业调度系统的一种实现。平衡器作为网络请求分配的控制者，要根据集群节点的当前处理能力，采用集中或分布策略对网络服务请求进行调配，并且在每个服务请求的生命周期里监控各个节点的有效状态。一般的说，平衡器对请求的调度具备以下的特征：
网络服务请求必须是可管理的
请求的分配对用户是透明的
最好能够提供异构系统的支持
能够依据集群节点的资源情况进行动态分配和调整
负载平衡器在集群的各个服务节点中分配工作负载或网络流量。可以静态预先设置或根据当前的网络状态来决定负载分发到哪个特定的节点，节点在集群内部可以互相连接，但它们必须与平衡器直接或间接相连。

网络平衡器可以认为是网络层次上的作业调度系统，大多数网络负载平衡器能够在网络的相应层次上实现单一系统映像，整个集群能够体现为一个单一的IP地址被用户访问，而具体服务的节点对用户而言是透明的。这里，平衡器可静态或动态配置，用一种或多种算法决定哪个节点获得下一个网络服务请求。 2．网络平衡原理
在TCP/IP协议中，数据包含有必要的网络信息，因而在网络缓存或网络平衡的具体实现算法里，数据包的信息很重要。但由于数据包是面向分组的（IP）和面向连接的（TCP），且经常被分片，没有与应用有关的完整信息，特别是和连接会话相关的状态信息。因此必须从连接的角度看待数据包——从源地址的端口建立到目的地址端口的连接。
平衡考虑的另一个要素就是节点的资源使用状态。由于负载平衡是这类系统的最终目的，那么及时、准确的把握节点负载状况，并根据各个节点当前的资源使用状态动态调整负载平衡的任务分布，是网络动态负载平衡集群系统考虑的另一关键问题。
一般情况下，集群的服务节点可以提供诸如处理器负载，应用系统负载、活跃用户数、可用的网络协议缓存以及其他的资源信息。信息通过高效的消息机制传给平衡器，平衡器监视所有处理节点的状态，主动决定下个任务传给谁。平衡器可以是单个设备，也可以使一组平行或树状分布的设备。
3．基本的网络负载平衡算法
平衡算法设计的好坏直接决定了集群在负载均衡上的表现，设计不好的算法，会导致集群的负载失衡。一般的平衡算法主要任务是决定如何选择下一个集群节点，然后将新的服务请求转发给它。有些简单平衡方法可以独立使用，有些必须和其它简单或高级方法组合使用。而一个好的负载均衡算法也并不是万能的，它一般只在某些特殊的应用环境下才能发挥最大效用。因此在考察负载均衡算法的同时，也要注意算法本身的适用面，并在采取集群部署的时候根据集群自身的特点进行综合考虑，把不同的算法和技术结合起来使用。
3．1 轮转法：
轮转算法是所有调度算法中最简单也最容易实现的一种方法。在一个任务队列里，队列的每个成员（节点）都具有相同的地位，轮转法简单的在这组成员中顺序轮转选择。在负载平衡环境中，均衡器将新的请求轮流发给节点队列中的下一节点，如此连续、周而复始，每个集群的节点都在相等的地位下被轮流选择。这个算法在DNS域名轮询中被广泛使用。
轮转法的活动是可预知的，每个节点被选择的机会是1/N，因此很容易计算出节点的负载分布。轮转法典型的适用于集群中所有节点的处理能力和性能均相同的情况，在实际应用中，一般将它与其他简单方法联合使用时比较有效。
3．2 散列法
散列法也叫哈希法（HASH），通过单射不可逆的HASH函数，按照某种规则将网络请求发往集群节点。哈希法在其他几类平衡算法不是很有效时会显示出特别的威力。例如，在前面提到的UDP会话的情况下，由于轮转法和其他几类基于连接信息的算法，无法识别出会话的起止标记，会引起应用混乱。
而采取基于数据包源地址的哈希映射可以在一定程度上解决这个问题：将具有相同源地址的数据包发给同一服务器节点，这使得基于高层会话的事务可以以适当的方式运行。相对称的是，基于目的地址的哈希调度算法可以用在Web Cache集群中，指向同一个目标站点的访问请求都被负载平衡器发送到同一个Cache服务节点上，以避免页面缺失而带来的更新Cache问题。
3．3 最少连接法
在最少连接法中，平衡器纪录目前所有活跃连接，把下一个新的请求发给当前含有最少连接数的节点。这种算法针对TCP连接进行，但由于不同应用对系统资源的消耗可能差异很大，而连接数无法反映出真实的应用负载，因此在使用重型Web服务器作为集群节点服务时（例如Apache服务器），该算法在平衡负载的效果上要打个折扣。为了减少这个不利的影响，可以对每个节点设置最大的连接数上限（通过阈值设定体现）。
3．4 最低缺失法
在最低缺失法中，平衡器长期纪录到各节点的请求情况，把下个请求发给历史上处理请求最少的节点。与最少连接法不同的是，最低缺失记录过去的连接数而不是当前的连接数。
3．5 最快响应法
平衡器记录自身到每一个集群节点的网络响应时间，并将下一个到达的连接请求分配给响应时间最短的节点，这种方法要求使用ICMP包或基于UDP包的专用技术来主动探测各节点。
在大多数基于LAN的集群中，最快响应算法工作的并不是很好，因为LAN中的ICMP包基本上都在10ms内完成回应，体现不出节点之间的差异；如果在WAN上进行平衡的话，响应时间对于用户就近选择服务器而言还是具有现实意义的；而且集群的拓扑越分散这种方法越能体现出效果来。这种方法是高级平衡基于拓扑结构重定向用到的主要方法。
3．6 加权法
加权方法只能与其他方法合用，是它们的一个很好的补充。加权算法根据节点的优先级或当前的负载状况（即权值）来构成负载平衡的多优先级队列，队列中的每个等待处理的连接都具有相同处理等级，这样在同一个队列里可以按照前面的轮转法或者最少连接法进行均衡，而队列之间按照优先级的先后顺序进行均衡处理。在这里权值是基于各节点能力的一个估计值。
4、动态反馈负载均衡
当客户访问集群资源时，提交的任务所需的时间和所要消耗的计算资源是千差万别的，它依赖于很多因素。例如：任务请求的服务类型、当前网络带宽的情况、以及当前服务器资源利用的情况等等。一些负载比较重的任务需要进行计算密集的查询、数据库访问、很长响应数据流；而负载比较轻的任务请求往往只需要读一个小文件或者进行很简单的计算。
对任务请求处理时间的不同可能会导致处理结点利用率的倾斜（Skew），即处理结点的负载不平衡。有可能存在这样情况，有些结点已经超负荷运行，而其他结点基本是闲置着。同时，有些结点已经忙不过来，有很长的请求队列，还不断地收到新的请求。反过来说，这会导致客户长时间的等待，而集群整体的服务质量下降。因此，有必要采用一种机制，使得平衡器能够实时地了解各个结点的负载状况，并能根据负载的变化做出调整。
具体的做法上采用了基于负反馈机制的动态负载均衡算法，该算法考虑每一个结点的实时负载和响应能力，不断调整任务分布的比例，来避免有些结点超载时依然收到大量请求，从而提高单一集群的整体吞吐率。
在集群内，负载均衡器上运行服务端监控进程，监控进程负责监视和收集集群内各个结点的负载信息；而每个结点上运行客户端进程，负责定时向均衡器报告自身的负载状况。监控进程根据收到的全部结点的负载信息来进行同步操作，既对将要分配的任务按照权值得比例重新进行分布。权值得计算主要根据各个结点的CPU利用率、可用内存以及磁盘I/O状况计算出新的权值，若新权值和当前权值的差值大于设定的阀值，监控器采用新的权值对集群范围内的任务重新进行分布，直到下一次的负载信息同步到来之前。均衡器可以配合动态权值，采用加权轮询算法来对接受的网络服务请求进行调度。
4．1 加权轮询调度
加权轮询调度（Weighted Round-Robin Scheduling）算法用相应的权值表示结点的处理性能。该算法根据权值的高低顺序并按照轮询的方式将任务请求分配到各结点。权值高的结点比权值低的结点处理更多的任务请求，相同权值的结点处理相同份额的请求。加权轮询的基本原理可描述为：
假设某集群内有一组结点N = {N0, N1, …, Nn-1}，W(Ni)表示结点Ni的权值，一个指示变量i表示上一次选择的服务器，T（Ni）表示结点Ni当前所分配的任务量。
∑T(Ni) 表示当前同步周期需要处理的任务总量。
∑W(Ni) 表示结点的权值总和。
则： W(Ni)/ ∑W(Ni)= T(Ni)/ ∑T(Ni)
表示任务的分配是按照各个结点权值占权值总数的比例来进行分配。 4.2 权值计算
当集群的结点初次投入系统中使用时，系统管理员根据结点的硬件配置情况对每个结点都设定一个初始权值DW（Ni）（通常根据结点的硬件配置来定义，硬件配置越高的结点默认值越高），在负载均衡器上也先使用这个权值。然后，随着结点负载的变化，均衡器对权值进行调整。
动态权值是由结点运行时各方面的参数计算出来的。我们在实验中选取了最重要几项，包括：CPU资源，内存资源，当前进程数，响应时间等信息作为计算公式的因子。结合每个结点当前的权值，可以计算出新的权值的大小。动态权值目的是要正确反映结点负载的状况，以预测结点将来可能的负载变化。对于不同类型的系统应用，各个参数的重要程度也有所不同。典型的Web应用环境下，可用内存资源和响应时间就非常重要；如果用户以长的数据库事务为主，则CPU使用率和可用内存就相对重要一些。为了方便在系统运行过程中针对不同的应用对各个参数的比例进行适当调整，我们为每一个参数设定一个常量系数 Ri ，用来来表示各个负载参数的重要程度，其中Σ Ri = 1。因此，任何一个结点Ni的权值公式就可以描述为：
LOAD(Ni)=R1*Lcpu(Ni)+R2*Lmemory(Ni)+R3*Lio(Ni)+R4*Lprocess(Ni)+R5*Lresponse(Ni)
其中Lf(Ni) 表示结点Ni 当前某一项参数的负载值，
上述公式中依次表示为：CPU使用率、内存使用率、磁盘I/O访问率、进程总数以及响应时间。
例如，在WEB服务器集群中，我们采用以系数{0.1, 0.4, 0.1, 0.1, 0.3}，这里认为服务器的内存和请求响应时间较其他参数重要一些。若当前的系数Ri不能很好地反映应用的负载，系统管理员可以对系数不断地修正，直到找到贴近当前应用的一组系数。
另外，关于采集权值的周期置，虽然很短的周期可以更确切地反映各个结点的负载，但是很频繁地采集（如1秒1次或者多次）会给均衡器和结点带来负担，也可能增加不必要的网络负荷。另外，由于采集器是在采集时刻进行负载计算的，经实验证明，均衡器反映出来各个结点的负载信息会出现剧烈的抖动，均衡器无法准确捕捉结点真实的负载变化趋势。因此解决这些问题，一方面要适当地调整采集负载信息的周期，一般在5～10秒；另一方面，可以使用移动平均线或者是滑动窗口来避免抖动，使得均衡器收集到的负载信息表现为平滑曲线，这样在负反馈机制的调整效果上就会比较好。
均衡器的动态权值采集程序周期性地运行，若缺省权值不为零，则查询该结点的各负载参数，并计算出动态权值LOAD(Ni) 。我们引入以下权值计算公式，结合结点的初始权值和采集的动态权值来计算最终的权值结果。
Wi = A*DW(Ni)+B*(LOAD(Ni)-DW(Ni))1/3
在公式中，如果动态权值恰好等于初始权值，最终权值不变，则说明系统的负载状况刚好达到理想状况，等于初始权值DW(Ni)。如果动态权值计算结果高于初始权值，最终权值变高，则说明系统负载很轻，均衡器将会增加分配给该结点的任务比率。如果动态权值低于初始权值，最终权值变低，说明系统开始处于重载状况，均衡器将会减少对该结点分配的任务。在实际使用中，若发现所有结点的权值都小于他们的DW(Ni)，则说明当前个集群处于超载状态，这时需要加入新的结点到集群中来处理部分负载；反之，若所有结点的权值大大高于DW(Ni)，则说明当前系统的负载都比较轻。
5、总结
网络负载平衡是集群作业调度系统的具体实现。由于其处理的作业单元是TCP/IP协议下的网络连接，因此可以采用面向网络连接的集中基本调度算法。考虑集群负载不平衡的可能，采取了动态获取服务节点的权值并使用负反馈机制调整平衡器对网络服务请求的分布，以适应服务节点在运行过程中资源的变化。笔者也在LVS集群系统的基础上，配合原有的轮询算法对其进行改进，增加了采集动态权值的程序并实时反馈到负载平衡器的调度系统上。实践证明，采用动态平衡在集群系统的整体吞吐量方面有所提高，特别是在集群各个节点性能不一，集群提供的网络服务程序所访问的资源多样化的情况下，负反馈机制的效果尤其明显。在其他类型的集群中，负反馈机制的动态负载平衡也能够得到很好的应用，只是平衡器所处理的作业单元不同于网络连接，而具体的负载算法上也将有所不同

用基于GPU的Geometry Clipmap渲染地形（下）

11106028@qq.com(IDSeeX) — Fri, 14 Aug 2009 05:31:58 GMT

用基于[url=javascript:;]GPU[/url]的[url=javascript:;]Geometry[/url] [url=javascript:;]Clipmap[/url]渲染[url=javascript:;]地形[/url]（下）
使用基于GPU的Geometry Clipmap渲染地形（Terrain Rendering Using GPU-Based Geometry Clipmaps）（下）
翻译：clayman
clayman_joe@yahoo.com.cn
仅供个人学习使用，勿用于任何商业用途，转载请注明作者^_^
1.3.5 Vertex Shader
我们使用同一个vertex shader来渲染之前描述的所有2D footprint。首先，对于给定的footprint坐标(x,y)来说，shader通过简单的缩放和变换来计算它的[url=javascript:;]世界[/url]坐标(x,y)。接下来，从顶点纹理中读取高度值z。这里不需要任何过滤器，因为顶点和纹理采样是一一对应的。
为了平滑的过渡，vertex shader将对两个不同层次边界的顶点进行几何混合（blend）。根据顶点（x,y）相对于观察点（Vx，Vy）的位置来计算混合参数alpha。这里：
alpha = max( alphax,alphay):
alphax = clamp(( | x – Vx ) – ( (n-1)/2 – w – 1)) /w , 0, 1)
使用类似的方法计算alphay。
这里，所有的坐标都以clipmap网格范围内[ 0….n-1]之间的值来表示，w是交换区域的宽度（这里选择了 w= n/10）。我们希望除了交换区域外，alpha值都为0，而在交换区域内，值线形的从0增加到1，当达到外围的层次时值为1。下图的蓝色部分即为交换区域。

对于几何混合来说，我们对同一位置（x,y）在不同层次之间的高度值Zf（较好层次的高度值）和Zc（教粗糙层次的高度值）之间进行线形插值。
Z’ = ( 1 – alpha)Zf + alpha * Zc
一般情况下，采样点位于较粗糙网格的边缘，Zc则通过对较粗糙层次边缘两个采样点的均值来计算。我们可以在运行时来完成这一步计算，但这将会导致3次顶点纹理查找（Zf一次，Zc = （Zc1 + Zc2）/2 两次），而对于现在的显卡来说，读取顶点纹理的代价还是很大的。
因此，我们把计算Zc作为更新clipmap的一部分来实现，把Zf和Zc打包为同一个单通道的浮点纹理（pack both Zf and Zc into the same 1-channel floation-point texture）。我们把Zf作为浮点数的整数部分，而差值Zd = Zc – Zf则保存为小数部分。这个打包的步骤将在pixar shader中upsampling的时候完成（详见1.4.1）。
以下是实现clipmap渲染的vertex shader的部分HLSL代码：
struct OUTPUT
{
vector pos: POSITON;
float2 uv: TEXCOORD0; //coordinates for normal-map lookup
float z: TEXCOORD1; //coordinates for elevation-map lookup
float alpha: TEXCOORD2; //transition blend on normal map
};
uniform float4 ScaleFactor, FineBlockOrig;
uniform float2 ViewerPos,AlphaOffse,OneOverWidth;
uniform float zScaleFactor,zTexScaleFactor;
uniform matrix WorldWiewProjMatrix;
uniform sampler ElevationSampler = sampler_state // fine level height sampler
{
Texture = (fineLevelTexture);
MipFilter = None;
MinFilter = Point;
MagFilter = Point;
AddressU = Wrap;
AddressV = Wrap;
};
OUTPUT RenderVS(float2 gridPos: TEXCOORD0)
{
OUTPUT output;
//convert from grid xy to workld xy coordinates
//ScaleFactor.xy:grid spacing of current level
//ScaleFactor.zw:origin fo current block within world
float2 worldPos = gridPos*ScaleFactor.xy + ScaleFactor.zw;
//compute coordinates for vertex texture
//FineBlockOrig.xy: 1/(w,h) of textrue
//FineBlockOrig.zw: origin of block in texture
float2 uv = gridPos * FineBlockOrig.xy + FineBlockOrig.zw;
//sample the vertex texture
float zf_zd = tex2Dlod(ElevationSampler, float4(uv, 0, 1));float zf_zd = tex2Dlod(ElevationSampler,float4(uv,0,1));
//unpack to obtain zf and zd = (zc-zf)
//zf is elevation value in current(fine) level
//zc is elevation value in coarser level
float zf = floor(zf_zd);
float zd = frac(zf_zd) * 512 - 256; // zd = zc - zf
//computer alpha (transition parameter) and blend elevation
float2 alpha = clamp((abs(worldPos - ViewerPos) - AlphaOffset)* OneOverWidth , 0, 1);
alpha.x = max(alpha.x,alphal.y);
float z = zf + alpha.x * zd;
z = z * ZScaleFactor;
output.uv = uv;
output.z = z * ZtexScaleFactor;
output.alpha = alpha.x;
return output;
}
1.3.6 The Pixar Shader
Pixar shader访问法线图（normal map）并对表面进行着色。我们让法线图的分辨率为几何地形的两倍，因为每个顶点一条法线效果是很模糊的。当更新clipmap时，我们将逐渐计算法线图（详见1.4.3）。
为了平滑的着色过渡，着色器查找当前层次和下一个较粗糙层次的法线值，之后使用vertex shader中计算的alpha值进行混合。一般情况下，这将导致2次纹理查找。因此，我们把两个法线值以（Nx , Ny , Ncx , Ncy）的形式放到一张4通道，每通道8bit的纹理中，这里假设Nz = 1，Ncz = 1。因此在读取之后需要重新归一化（renormalize）。
所上的颜色通过读取一张基于z方向（z-based）的1D纹理贴图来获得。
以下代码是实现clipmap rendering的pixar shader的部分HLSL代码（Upsample和Zcoarser函数详见附件）：
//paramters uv,alpha,and z are interpolated form vertex shader.
//Two texture samplers have min amd mag filters set to linear:
//NormalMapSampler: 2D texture containing normal map
//ZBasedColorSampler: 1D texture containing elevation-based color
uniform float3 LightDirection;
//pixar shader for rendering the geometry clipmap
float4 RenderPS(float2 uv: TEXCOORD0,
float z: TEXCOORD1,
float alpha: TEXCOORD2) : COLOR
{
float4 normal_fc = text2D(NormalMapSampler,uv);
//normal_fc.xy contains normal at current(fine) level
//normal_fc.zw contains normal at coarser level
//blend normals using alpha computed in vertex shader
float3 normal = float3((1-alpha) * normal_fc.xy + alpha * (normal_fc.zw),1);
//unpack coordinates from[0,1] to [-1,1]range,and renormalize
normal = normalize(normal * 2 -1);
//computer simple diffuse lighting
float s = clamp(dot(normal,LightDirection),0,1);
//assign terrain color based on its elevation
return s * tex1D(ZbasedColorSampler,z);
}
1.4 更新
当观察者在场景中移动时,clipmap每层中的窗口都必须进行变换，以保证观察点位于窗口的中央，因此，我们必须有根据的来更新这些窗口。由于观察者的移动是连续的，因此每帧基本上只需要为窗口更新一个L形的区域。另外，对较粗糙的层次来说，相对于观察者移动的距离，它所改变的位置是成指数减少的（the relative motion of the viewer within the windows decreases exponentially at coarser levels），因此，很少需要进行更新。
我们以从粗糙层到较好层的顺序来更新有效的clipmap层。还记得每个clipmap层都储存了两张纹理吗：一张单通道的浮点高度图，一张4通道，每通道8bit的法线图。在更新的过程中，我们通过使用pixel shader进行渲染的方法来对这些纹理区域进行修改。为了避免改变已有的数据，所有的访问操作都是以一种环形（toroidal）的方式来进行，如下图所示：

（红色为进行更新的区域，绿色箭头为观察者移动的方向）
我们使用环绕寻址（wraparound addressing）的方式来定位clipmap窗口在纹理图中的位置。在这种环形的访问方式下，L形的更[url=javascript:;]新区[/url]域通常变为一个十字形的区域，如上图所示。通过渲染2个矩形来组成这个渲染区域。需要注意的是如果更新区域跨越了纹理的边界，则有可能需要3到4个矩形。
1.4.1 Upsampling
我们使用一种插值细分（interpolatory subdivison）的方法，通过较混乱的层次来预测较好层次的几何体。这里将使用众所周知的四点插值细分曲线方法的张量积版本， mask weights取( -1/16, 9/16,9/16,-1/16)（We use the tensor-product version of the well-known four-point subdivision curve interpolant ,which has mask weights ( -1/16, 9/16,9/16,-1/16)）。这种upsampling过滤器恰好可以达到我们所希望的C1平滑效果。
根据采样点在网格中的位置（偶数-偶数，偶数-奇数，奇数-偶数，奇数-奇数），选则不同的mask。对一个偶数-偶数的像素来说，只需对纹理进行一次查找，因为采样是通过插值计算得来的；而对一个奇数-奇数的像素来说，则需要对纹理进行4x4次查找；另外的两种情况均需要4次查找。对于CPU来说，可以用一个if块来方便的选择所用的mask值。但是，分支语句对于pixar shader来说代价是很大的。因此，我们总是进行16次纹理查找，另外，通过对一张2x2纹理的查找来选择不同的mask值。
以下是部分upsampling shader的HLSL代码实现：
//residualSampler: 2D texture containing residuals,which can
//be either decompressed data or synthesized noise
//p_uv:coordinates of the grid sample
uniform float2 Scale;
//pixel shader for updating the elevation map
float4 UpsamplePS(float2 p_uv : TEXCOORD0) : COLOR
{
float2 uv = floor(p_uv);
//the Updample function samples the coarser elevation map
//using a linear interpolatory filter with 4x4 taps
//(depending on the even/odd configuration of location uv,
//it applies 1 of 4 possible masks)
float z_predicted = Upsampler(uv);//detail omitted here
//add the residual to get the actual elevation
float residual = tex2D(residualSampler,p_uv * Scale);
float zf = z_predicted + residual;
//zf should always be an integer,since ite gets packed
//into the integer component of the floating-point texture
zf = floor(zf);
//compute zc byu linearlyu interploating the vertices of the
//coarse-grid edge on which the sample p_uv lies
float zc = ZCoarser(uv);
float zd = zc - zf;
//pack the signed difference zd into the fractional componnent
float zf_zd = zd + (zd + 256)/512;
return float4(zf_zd,0,0,0);
}
1.4.2 Residuals
可以通过解压数据或合成的方法获得residuals值，并把它添加到使用upsampling方法获得的较粗糙的数据中。
对于使用压缩数据的方法，我们通过图片压缩技术来对residuals数据进行编码。我们使用了一种称为PTC的有损（lossy）图片编码方式，因为它支持一种高效的region-of-interest解码（Malvar 2000）。通过CPU来进行解压缩，并且把结果储存为一张residual纹理图。
而对另一种方法来说，我们使用不相关高斯噪声（uncorrelated Gaussian noise）（Fournier et al. 1982）作为residuals值，来合成地形的细节（fractal detail）。GPU读取一小张预先计算好的包含了高斯噪声的2D纹理来完成合成，这个过程执行起来是相当快的。另外，把纹理环绕起来，扩展为一张无限大的高斯噪声纹理，同时，对纹理坐标进行一点点放大，来消除规则的周期效果（we enable texture wrapping to extend the Gausian texture infinitely,and apply a small magnification to the texture coordinates to break the regular periodicity）。跨越不同层次的噪声叠加在一起，因此对地形产生的起伏效果不会显示出任何模式性，如下图所示：

1.4.3 法线图（Normal Map）
着色器使用当前层的高度图来为这一层更新法线图。计算两个grid-aligned的切线的叉积来获得当前法线。此外，还对较粗糙的层次进行一次纹查找，获得它的所有法线值。最后，把（Nx, Ny, Ncx, Ncy）打包为一张4通道的纹理。代码详见附件。
1.5 结果和讨论
我们主要的数据是一张216000 * 93600的[url=javascript:;]美国[/url]地形高度图，其水平分辨率为30米，垂直分辨率为1米。进行了100倍以上的压缩之后，只需要355MB的内存就可以容纳它。我们在P4 2.4G，1G内存，NIVIDIA Geforce6800 GT的[url=javascript:;]系统[/url]上，以1024 * 768的分辨率对地形进行了渲染。
渲染率：在L=11，网格大小n=255，使用了裁减的情况下，获得了每秒130帧的效果，每秒渲染了6千万三角形。使用顶点纹理查找是系统的瓶颈，在移除了查找之后，渲染率提高到了185frames/sec （对n=127的情况来说，使用了顶点纹理也可以达到298 frames/sec.）
更新率：下表显示了更新过程中每个步骤所需要的时间，这里所统计的时间是最坏情况即每次更新整个层所需的时间。在CPU上完成的解压缩显然是系统的瓶颈。
Previous Implement GPU-Based Implementation
Upsampling 3ms 1.0ms
Decompression(on CPU) 8ms 8ms
Synthesis 3ms ~0ms
Normal-Map Computation 11ms 0.6ms
最终的帧数：对于使用解压方式的地形来说，当观察着移动时，帧数大约在87 frames/sec，对于使用合成方法的来说，则是120 frames/sec。
1.6 总结和改进
我们描述了一个使用GPU实现geometry clipmap的框架。几乎把所有显示几何图形的过程都使用GPU来完成，从而减少CPU的负载。
1.6.1 顶点纹理
Geometry clipmap通过一种非常特别也是受限制的方法来使用vertex texture：实质上每个texels是以光栅扫描（raster-scan）的顺序来访问，和顶点是一种一一对应的关系。因此，我们希望以后的访问机制可以提高渲染效率。
1.6.1 取消法线图
通过访问高度图中四个过滤之后的采样（filtered samplers）点，应该可以直接在pixel shader中计算法线。目前，顶点纹理查找只能使用32-bit的浮点图片，因此不能进行高效的双线形过滤（bilinear filtering）.
1.6.3 Memory-free Terrain Synthesis
在GPU上合成地形细节是如此之快，因此我们可以考虑每一帧都重建clipmap层次，从而节省显存。我们分配2张纹理T1和T2，然后在他们之间相互转换。把T1初始化为较粗糙的几何体作为合成过程的种子。首先，通过pixar shader的更新产生源纹理T1，接下来通过upsample和合成，创建一个较好的层次，并把它保存为T2。然后，把T1作为顶点纹理，渲染他所在的clipmap环。之后，交换两张纹理的规则并重复整个过程，直到所有层都完成合成以及渲染。最初的尝试是很有前途的，在L=9的时帧率约59 frames/sec。

使用基于GPU的Geometry Clipmap渲染地形（上）

11106028@qq.com(IDSeeX) — Fri, 14 Aug 2009 05:31:24 GMT

使用基于[url=javascript:;]GPU[/url]的[url=javascript:;]Geometry[/url] [url=javascript:;]Clipmap[/url]渲染[url=javascript:;]地形[/url]（上）
使用基于GPU的Geometry Clipmap渲染地形（Terrain Rendering Using GPU-Based Geometry Clipmaps）（上）
翻译：clayman

注：这篇文章翻译的是《GPU Gem2》中第二章的内容，老早就翻译的东西了，但因为翻的不太好，一直放着，找不到原版的PDF文档，截图有些是在网上找的，有些是我自己做的，大家凑活看了，基本和原图还是差不多的。《GPU Gem2》中的内容实在很难，本人水平有限，有错的地方还请大家指正。
Geometry clipmap是用于渲染地形LOD的新方法。它把地形缓存在一组嵌套的规则网格中，同时在观察点移动时，不断更新这些数据。和之前不规则网格（irregular-mesh）技术相比，规则的网格有很多优点：简洁的数据结构、平滑的视觉效果，稳定的渲染速率，合适的分级（graceful degradation），高效的压缩，以及运行时的细节合成（synthesis）。这里，我们将描述一种通过顶点纹理（vertes texture）实现的几何clipmap。把地形几何体作为图片来处理，几乎所有计算都能通过GPU来完成，从而减少CPU的负担。
1.1 Geometry clipmap简述
在大型户外环境中，处理地形数据将会占用大量的储存空间以及渲染带宽。我们已经[url=javascript:;]开发[/url]了多种LOD技术来处理地形。但是，大多数技术需要在运行时创建和修改mesh数据（顶点和索引缓冲），而这些操作对当前的图形处理技术(graphics architecture)来说代价是很大的。此外，不规则的网格通常需要使用CPU来处理，而在诸如[url=javascript:;]游戏[/url]之类的应用中，CPU本来就不够用了。
Gemetry clipmap框架中（Losasso and Hoppe 2004）把地形作为一张2D的高度图（elevation image）来处理，并预先把它过滤为一张包含L层的mipmap金字塔。

处理复杂地形时，完整的金字塔可能对内存来说太大了。Geometry clipmap结构对每一层进行窗口大小为n x n的采样并缓存，这和Tanner 1998介绍的texture clipmap方法有些类似。对观察者来说，这些窗口相当于一组嵌套规则的网格。注意，高细节层次所占的空间总是比较粗糙的层次少。这样的目的是保证在屏幕空间，所有三角形都统一大小（the aim is to maintain trangles that are uniformly sized in screen space）。如果clipmap大小为 n = 255, 那么在1024 x 768的分辨率下，每个三角形大约是5个像素。

只有最高的层次（L-1级）渲染为完整的方形网格。其他层次都渲染为空心环，因为空心部分已经由较高层次填充了。
当观察者移动时，clipmap窗口也作相应的改变，同时更新数据。为了保证高效的持续更新，以一种环形的方法来访问clipmap每一层的窗口，也就是说使用2D环绕寻址（the clipmap window in each level is accessed toroidally, that is ,with 2D wraparound addressing）。
其中，挑战之一就是如何隐藏相邻层次之间的边界，同时，保证一个完美的网格，避免临时的撕裂效果。Geometry clipmap的嵌套网格结构提供了一种简单的解决方案。其中，关键的思想就是每层在靠近外层边界的地方引入一个交换区域（transition region），这样，几何体和纹理都能平滑的通过插值过渡到下一个粗燥级别。使用顶点和像素着色器，可以分别高效的实现这些交换区域。

Geometry clipmap的嵌套网格结构同样能实现高效的压缩以及合成。它可以通过对较粗糙的层次的数据进行upsample（提高取样率），预测（prediction）每一层的高度数据。因此，我们只需要储存多余的细节信息并合成到这个预测的信号上就可以了。
1.2 Overview of GPU Implementation
Geometry cliipmap最初的实现方法把每一层数据当作普通的顶点缓冲。由于当前的GPU缺乏修改顶点缓冲数据的能力，所以这种实现在更新数据和渲染时都需要CPU参与。而这里，我们将使用顶点纹理来实现geometry clipmap。这样做是有益的，因为clipmap 2D的窗口网格数据更适合保存为一张2D纹理，而不是通过人工线形化处理保存为1D的顶点缓冲。由于clipmap包含L层，每一层又包含了n x n的几何采样，我们将把采样的（c,y,z）信息分为两部分：
* （x,y）坐标储存为常量顶点数据
*Z坐标储存为一个单通道（single-channel）的2D纹理——高度图（elevation map）。为每层都定义一个n x n的高度图。这些纹理都将在clipmap层次根据观察点变换时更新。
由于clipmap的层次是统一的2D网格，（x,y）坐标也是规则的，同时，变换和比例也是常量。因次，我们定义了一组只读的顶点和索引缓冲，用来表示2D“footprints”，同时，在每个层次都重复使用这些footprints。
顶点通过把高度图作为顶点纹理来采样，获得高度值。在顶点着色器中访问纹理是DirectX 9 Shader Modle 3.0的新特性，NVIDIA Geforce6 系列的GPU都支持这个功能。把高度数据保存为图片，可以直接使用GPU的光栅管道（rasterization pipeline）来进行处理。对于需要进行合成操作的地方，所有运行时的计算（高度图的upsample，地形细节合成，法线计算，以及渲染）都完全由GPU来执行，这样就可以留出宝贵的CPU资源）。对压缩地形来说，就需要CPU不停的为图形卡解压和更新数据。
1.2.1 数据结构
总的来说，主要的数据结构如下。我们预先定义一组顶点和索引缓冲常量，为clipmap的网格（x，y）编码。对0…..L-1中的每一层，分配一张高度图（单通道浮点2D纹理 1-channel floating-point 2D texture）和一张法线图（4通道 8-bit 2D纹理）。以上所有数据结构都保存在显存中。
1.2.2 Clipmap的尺寸
由于每层的外边界都必须覆盖在下一个粗糙层次的网格上，网格尺寸n必须是奇数。当纹理尺寸是2的幂时，硬件可以进行优化，所以我们选择n = 2^k-1，保留一行一列作为未使用的纹理。我们的例子中大多数情况下使用n = 255。
选择 n = 2^k-1还有一个优点就是较好的层次永远不会位于下一个粗糙层次的中心（the finer level is never exactly centered with respect to its parent next-coarser level）。换句话说，就是对于下一个层次，它在x或y方向总有一个网格单位的偏移，具体偏向那个位置则根据观察点的位置来决定。事实上，当下一个粗糙层次不变时，应该允许较好的层次可以改变，因此，较好的层次有时就必须进行偏移。当然，我们也可以选择n = 2^k+3作为网格尺寸，来达到中心对齐的效果，但是这样仍然需要处理中心偏移的情况，导致最后的结果过于复杂。
1.3 渲染
1.3.1 有效层（Active Levels ）
虽然我们为clipmap分配了L层，但是通常只渲染（和更新）一组有效的层次0……L’-1，L’的值基于观察点的高度来计算。这样做的目的是，当观察点足够高时，clipmap中最好的层次就不必渲染了。特别的，我们把网格范围小于2.5h的层次作为无效层，这里，h表示观察点到地形的垂直距离。由于地形数据都储存在显存中，计算h将导致重新读取最好的有效层高度纹理图采样点数据。这个重新读取的工作将带来一些小小的额外开销，因此，每过几帧检测一次。当然，需要把L’-1层渲染为一个完全的方形而不是空心环。
Losasso和Hoppe2004描述的方法中，对于在观察者移动时没有完全更新的层进行了裁剪（cropping）。为了简化GPU的实现，我们放弃了这个特性。我们假设每个层是完全更新的，或者完全无效。
1.3.2 顶点和索引缓冲
正如之前所说的，我们把网格的（x，y）值作为顶点数据，同时，z方向的高度值保存为单通道的浮点纹理。为每层的环定义一个单独的顶点缓冲来保存（x,y）数据是一种有效的方法。但是，为了减少内存空间和实现可视区域裁剪，我们把环分为一些小的footprint片。

大部分环都由12个m x m的渲染单元块（block）组成，如图中的灰色区域，这里m = (n + 1) / 4。因为2D网格是规则的，同一个层中的（x，y）都进行同样的变换。此外，不同层次之间也可以使用统一的缩放值。因此，使用一个只读的顶点和索引缓冲，以及一些额外的参数，就可以让vertex shader对每个渲染单元块进行缩放和变换，完成所有渲染。
当clipmap大小为255时，每个规则的渲染单元块包含64x64个顶点。使用顶点缓冲来保存这些三角形带的索引。为了减少储存空间，将使用16位的索引值作为索引缓冲，这样，渲染单元块的m最大值就为255，同时，clipmap中n的最大值为1023。
但是12个渲染单元块的大小并不能完全覆盖整个环。我们使用一些小的2D footprint来填充这些裂缝。注意，这些额外区域的大小和渲染单元块相比应该是很小的，就像上图所示的那样。首先，环每条边的中间都有 (n – 1) – ((m -1) x 4) = 2个方格的裂缝，图中黄色部分，可以使用4个m x 3的固定区域来填充他。我们把这些区域编码为一个顶点和索引缓冲，并且对所有层复用这个缓冲。第二，在内层环的两条边界处会产生一个方格大小的裂缝，图中蓝色部分，以满足较好层次中心偏移的效果。这条L形的裂缝可能出现在四个位置（左上，左下，右上，右下），我们将使用4个顶点以及一个索引缓冲来填充这条内部的裂缝，使用对所有层次复用这几个缓冲。
此外，还需要在环的外边界渲染一系列退化（degenerate）三角形（图中橙色的部分）。为了避免T-junction效果，这些0区域（zero-area）三角形是必须的。最后，使用4个额外的渲染单元块以及一个L形区域填满整个环。
由于每个footprint（x,y）都为局部坐标，所以，不需要32－bit的精度，使用D3DDECLTYPE_SHORT2类型就可以了，这样每个象素只需要4 bit。将来，我们甚至可以在每个m x m大小的小的块内使用顶点索引i来计算这些坐标（x,y），比如（fmod( i , m) , floor (i/m)）。
1.3.3 View Frustum Culling
我们以块为最小单元在CPU上进行view frustum culling计算。每个块都扩张到[ Zmin, Z max]的范围内，并且在三维空间内由可视平截体进行分割。只有在分割快不为空时，才对它进行渲染。根据观察点的位置，对于90的观察范围来说，可以把渲染负载减少到原来的1/2 ~ 1/3之间，如下图所示。

1.3.4 关于DrawPrimitive调用
对于每一层来说，我们余姚调用14次DrawPrimitive(DP)方法：12个块每个一次，为footprint调用一次，为剩下的三角形再调用一次。但是，在视平截体裁减之后，平均每帧只需要渲染12个块中的4个。而对于最好的层来说，则需要多调用5次来填充中间的空间。因此，总的来说，平均每帧需要调用6L+5(当L＝11时为71)次DP方法。更进一步，使用Geometry Instancing技术把每个层次中的所有大块作为一个统一的整体调用一次DP，则可以把DP的次数减少到 3L + 2 (35)
（未完待续，下一部分将给出具体的代码实现）