写在博客一周年,裤子大53周年

2011年9月20日 sigma 14 条评论 5,856 views

今天打开微博,一堆关于裤子大的历史的微博迎面扑来,我才意识到,今天是9月20日,我们裤子大的生日。

很荣幸的,我的这个博客开通日期也是这一天(纯属巧合~~),我的博客也有一周年了!下面列出博客一周年的一些静态参数,以便一年后再来比较:

  1. 我博客总共写了123篇日志(包括从Live Space导入的几篇日志)。
  2. 遵循码农传统,本博客的第一篇日志是《hello world》,地址http://www.sigma.me/?p=1
  3. 一年来,据flagcounter,博客的独立访客数为32648,访客来自86个国家与地区。
  4. 今天博客的RSS订阅量为114,之前出现的峰值为119
  5. 据flagcounter,博客总点击数为63030
  6. 点击最多的文章点击数为5600
  7. 评论最多的文章评论数为67
  8. 友情链接数为19(貌似有点多。。。)。
  9. 博客主题改版次数为x(我也记不清了…不过都是小改动)
  10. 最近一个月,日平均访客为180(据我观察,周末访客量大大减少)。
  11. 博客的PR值为4
  12. 博客Google收录量为722,百度收录量为106

附上一张FlagCounter的截图:

FlagCounter 阅读全文…

Hash和Bloom Filter

2011年9月13日 sigma 11 条评论 32,545 views

这几天的“科研”中涉及到了一个概念,Bloom Filter(有的中文翻译为布隆过滤器,不知道正确否),今天看了下相关的资料,发现这东西和Hash还挺有关系的,在这里一并讲下。

Hash(函数/表)

Hash (中译为哈希,或者散列)函数在计算机领域,尤其是数据快速查找领域,加密领域用的极广。其作用是将一个大的数据集映射到一个小的数据集上面(这些小的数据集叫做哈希值,或者散列值)。Hash table(散列表,也叫哈希表),是根据哈希值(Key value)而直接进行访问的数据结构。也就是说,它通过把哈希值映射到表中一个位置来访问记录,以加快查找的速度。下面是一个典型的hash函数/表示意图:

哈希函数有以下两个特点:

  • 如果两个散列值是不相同的(根据同一函数),那么这两个散列值的原始输入也是不相同的。
  • 散列函数的输入和输出不是唯一对应关系的,如果两个散列值相同,两个输入值很可能是相同的。但也可能不同,这种情况称为“散列碰撞”(或者“散列冲突”)。上图中,John Smith和Sandra Dee就存在hash冲突。

Hash一个应用就是对数据集分类,比如上图,Hash值为0的表示可能在A集合中,Hash值为2的表示B集合中,依次类推,值为15的表示F集合中。但Hash冲突会在这里会导致严重的问题,对于一个未知的新值,其可能不属于上面任何一个集合,但由于冲突,其Hash值和上面的某一个相同,导致误报(因为事先我们不可能做一个含有无限多项输入的完整的Hash表,也就是原来的Hash函数不可能是完美的)。并且,hash冲突也会导致查找效率低下。

Bloom Filter

Bloom Filter是1970年由Bloom提出的。它实际上是一个很长的二进制向量和一系列随机映射函数(Hash函数)。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。Bloom Filter广泛的应用于各种需要查询的场合中,如Orocle的数据库,Google的BitTable也用了此技术。

如果想判断一个元素是不是在一个集合里,一般想到的是将所有元素保存起来,然后通过比较确定。链表,树等等数据结构都是这种思路. 但是随着集合中元素的增加,我们需要的存储空间越来越大,检索速度也越来越慢(O(n),O(logn))。

这时候就可以利用哈希表这个数据结构(它可以通过一个Hash函数将一个元素映射成一个位阵列(Bit array)中的一个点)。这样一来,我们只要看看这个点是不是1就知道可以集合中有没有它了。这就是Bloom Filter的基本思想。

但这时,哈希冲突会是一个问题:假设Hash函数是良好的,如果我们的位阵列长度为m个点,那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m/100个元素。显然这就不叫空间效率了(Space-efficient)了。解决方法也简单,就是使用多个Hash,如果它们有一个说元素不在集合中,那肯定就不在。如果它们都说在,虽然也有一定可能性它们都在说谎,不过直觉上判断这种事情的概率是比较低的。这种多个Hash组成的数据结构就叫Bloom Filter。

一个Bloom Filter是基于一个m位的位向量(b1,…bm),这些位向量的初始值为0。另外,还有一系列的hash函数(h1,…hk),这些hash函数的值域属于1~m。下图是一个bloom filter插入x,y,z并判断某个值w是否在该数据集的示意图:

 

上图中,m=18,k=3;插入x是,三个hash函数分别得到蓝线对应的三个值,并将对应的位向量改为1,插入y,z时,类似的,分别将红线,紫线对应的位向量改为1。查找时,当查找x时,三个hash值对应的位向量都为1,因此判断x在此数据集中。y,z也是如此。但是查找w时,w有个hash值对应的位向量为0,因此可以判断不在此集合中。但是,假如w的最后那个hash值比上图中的大1,这是就会认为w在此集合中,而事实上,w可能不在此集合中,因此可能出现误报。显然的,插入数据越多,1的位数越多,误报的概率越大。

Wiki的Bloom Filter词条有关于误报的概率的详细分析:Probability of false positives。从分析可以看出,当k比较大时,误报概率还是比较小的,因此这存储还是很空间有效滴。

Bloom Filter有以下几个特点:

  1. 不存在漏报(False Negative),即某个元素在某个集合中,肯定能报出来。
  2. 可能存在误报(False Positive),即某个元素不在某个集合中,可能也被爆出来。
  3. 确定某个元素是否在某个集合中的代价和总的元素数目无关。

优点:

相比于其它的数据结构,Bloom Filter在空间和时间方面都有巨大的优势。Bloom Filter存储空间和插入/查询时间都是常数。另外, Hash函数相互之间没有关系,方便由硬件并行实现。Bloom Filter不需要存储元素本身,在某些对保密要求非常严格的场合有优势。

缺点:

另外,一般情况下不能从Bloom Filter中删除元素. 我们很容易想到把位列阵变成整数数组,每插入一个元素相应的计数器加1, 这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在Bloom Filter里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

参考资料:

  1. http://en.wikipedia.org/wiki/Hash_function
  2. http://en.wikipedia.org/wiki/Bloom_filter
  3. http://antognini.ch/papers/BloomFilters20080620.pdf

开始阅读并修改SESC模拟器代码,开始写关于SESC的日志

2011年9月5日 sigma 2 条评论 7,447 views

这段时间由于“科研”需要,需要改模拟器,经过和师兄们商量,最后基本定了用SESC(SuperESCalar Simulator)。但是,在使用SESC的过程中,发现文档极少(甚至完整的安装文档都没有),唯一比较好的参考来源就是偶尔有一两个更新的SESC邮件列表。

而这些天,我要开始看SESC模拟器代码,并且需要根据实验需求改一些SESC模拟器的结构,趁这个机会,我打算有空的话,把一些阅读的文摘写到这里,也算是对SESC的一些“贡献”吧。

先把官方的SESC介绍简要翻译下吧:

什么是模拟器

在微体系结构领域,经常会有一些新的结构提出,这些结构相比于老的处理器结构,可能(注意,仅仅是可能)性能更高,功耗更小,更可靠,等等。但是,直接将这些结构用硬件实现的代价是昂贵的,因此,出现了微体系结构的模拟器,通过模拟器,不仅能模拟一个微体系结构设计对应的性能,还能模拟面积,功耗等等。

什么是SESC

SESC是最早由UIUC的一些研究单位开发并使用的微体系结构的模拟器。它可以对不同类型的处理器建模,包括单核处理器,片上多核处理器,以及PIM(processors-in-memory)。其可以模拟支持乱序发射,转移猜测的流水线,以及各种其他的现代处理器所有的单元,如cache层次,总线等等。

SESC是一个事件驱动的模拟器,这是一个从MINT衍生而来的,MINT是一个古老的模拟MIPS处理器的项目。处理器核中大部分的功能函数都是每一拍都会执行,不过也有少部分的函数只有需要的时候执行(通过事件驱动)。

阅读全文…

分类: 芯片设计 标签: ,

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

2011年8月27日 sigma 没有评论 4,786 views

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

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

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

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

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

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

阅读全文…

规划

2011年8月27日 sigma 14 条评论 4,268 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

分类: 随感 标签: , , ,

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