用GPU加速拼音输入法?

看到IBM申请了用GPU加速数据库的专利,想起来自己之前还有过用GPU来加速拼音输入法的想法,当时写在了twitter上,幸亏当初有在google reader里订阅了twitter中有关sunpinyin的关键字搜索,否则还真翻不出来了呢…

Jun/16, 2011:

这几天我一直在想,能否用GPU来加速输入法,我可以把SunPinyin Syllable Graph的所有组合,发到GPU上去开足够多的线程做并行搜索,或者在做viterbi时,栅格间的状态节点转移,也可以放到GPU上来并行运算,可大幅度提高beem宽度… 个人倾向于第一种方式…

http://twitter.com/#!/yongsun/statuses/81130853278822400

当时还和熟悉GPU/OpenCL的@reminisce1989同学探讨来着,reminisce1989同学认为用GPU加速Graph算法是很困难的,不过后来reminisce1989同学好像删推了,没有原推可以refer了。

yongsun: @reminisce1989 @jjgod 既然是基础服务,肯定不能随便down掉,应该是可以想办法避免的… 我的想法主要是,现在sunpinyin的搜索规模还很小,不知道能否借助GPU来大幅提高搜索的规模,回头有问题还要向您请教了 :)

reminisce1989: @yongsun @jjgod 最后提醒一下,GPU是不支持指针的(或者说只能模拟指针)。而我不知道你的sunpinyin用的搜索是什么图算法。如果用到任何常规图论算法,不用说难用OpenCL之类的语言实现,实现了效率也提不上去,因为是非顺序化读取,而且还要考虑拷贝数据的时间。

后来,我仔细阅读了OpenGL的一些文章和书籍,觉得应该是有希望的,不过一直没有时间去做实验,先记录在这里吧…

关于触摸屏输入法误按键纠错的一点想法

现在许多用于触摸屏的输入法,都有误按键纠错的功能,例如本意是按下i,但由于键盘比较小而手指比较粗,实际按下的是o,输入法可以自动将其修正为i。Wi和Sogou的手机输入法都支持这个功能,据说Sogou的纠错比较aggressive。不过目前看来,好像还没有人考虑用户手持手机的习惯,例如我是左撇子,那么容易误按的键和右手用户是不同的,具体来说,左撇子在按屏幕右方的按键时,容易向左侧偏;还有如果我是习惯用双手拿着手机进行输入,这个容易误按的键也是有所不同的。

前两天有一则新闻,是关于重力感应器可以用来截获用户输入内容的,而且原文是说用户将手机平放在桌子上,重力感应也可以达到如此的精度。我由此想到,是否可以通过重力感应器和电子罗盘,甚至陀螺仪,来判断当前用户手持手机的方式,例如是单左/右手,还是双手等。在判断出手持的方式(或姿势)之后,调整纠错的行为,使之更符合用户的使用场景。

我的初步想法是,在单手持机时,用户按比较远的键时,手机会有一定的转动或位置移动的轨迹。左手持机和右手持机的模式,可能会不同。如果我们能总结出一些pattern,就可以做一些工作了…

不过,还不清楚是否已经有类似的工作已经开展了,或者在技术上是否真正可行。希望大家多给些意见…

Gibbs采样的粗浅理解

前段时间一直在看LDA,原论文采用的Variational Inference有点看不懂,后来看到很多人推崇Gibbs采样是求LDA参数的一种非常有效的方式,于是就埋头去看Gibbs采样去了。不过还是有些云里雾里,这里记下一些自己粗浅的理解,请大家批评指正…

1. MC积分巧妙的把对解析式的积分,拆解成一个概率期望问题,并通过大量采样来得到近似的期望;为了将采样集中在概率比较大的地方,提出了多种采样方法,例如rejection,importance,sampling-importance-resampling等等,MCMC就是其中的一种…

2. MCMC中的MH算法所构造的Markov链,其状态节点x^(t),是在样本空间X上,⑴ 其构造方法是具有Markov性质的 ⑵ 且MH kernel满足交换性 P(j→k) π_j = P(k→j) π_k;因此MH构造的是一个非周期不可约稳定收敛的马氏链…

3. 而因为Gibbs采样是MH算法的一种特例(α==1),因此可以保证Gibbs抽取的样本,也构成一个非周期不可约稳定收敛的马氏链;Gibbs采样适用于样本是两维或以上的情况;通过积分去除掉相关但是不感兴趣的变量,称为“collapsed”的Gibbs采样;并且个人的一个感觉是,观测量所直接依赖的那些变量是不能被积分掉的,否则无法有效的进行抽样…

4. Gibbs采样中的概率 P(z_i|Z_\i),(其中Z_\i表示不含有z_i的向量),只是用来进行下一个随机采样(z_i的采样服从这个条件概率的分布),而最后反复迭代得到的关于z的分布,可以用count(z)/sample_numbers,来近似得到。而这个P(z)也是Gibbs采样形成的Markov链的收敛后的概率分布…

参考:

  1. Markov Chain Monte Carlo and Gibbs Sampling
  2. An Introduction to MCMC for Machine Learning
  3. Gibbs Sampling for the Uninitiated
  4. Bayesian Inference with Tears
  5. Parameter Estimation for text analysis
  6. Distributed Gibbs Sampling of Latent Dirichlet Allocation: The Gritty Details
  7. Explaining the Gibbs Sampler

也翻译一下乔布斯给妻子的信

We didn’t know much about each other twenty years ago. We were guided by our intuition; you swept me off my feet.
二十年前萍水相逢。似冥冥中你我有缘;为你一见倾心。

It was snowing when we got married at the Ahwahnee. Years passed, kids came, good times, hard times, but never bad times.
阿瓦尼的白雪为鉴,我们许下婚姻的誓言。多年过去了,我们有了自己的孩子,有欢乐有艰困,但从未怀疑动摇。

Our love and respect has endured and grown. We’ve been through so much together and here we are right back where we started 20 years ago—older, wiser—with wrinkles on our faces and hearts.
你我相爱相敬,爱历久弥新。二十年来历经风雨,我们依然相爱如初 ——不同的只是年老了些,心成熟了些—— 岁月在我们的脸上、和心上都刻下了印记。

We now know many of life’s joys, sufferings, secrets and wonders and we’re still here together.
而今,了解了人生的喜悦、困苦、奥秘、奇迹,而我们始终相知相守。

My feet have never returned to the ground.​
爱你不渝。

【另:关于feet】
可以google一下sweep her off her feet,或在“有道词典”中搜索一下这个短句,有道翻译为“使某人倾心”,我觉得还是贴切的,可以对应于我们常说的“为之倾倒”。开头这句可以翻译为“为你一见倾心”。那么最后一句的意思就是,我依然为你倾心不已…

open-gram词表协议改为Apache V2.0

经过社区的讨论,我们一致同意,将open-grame词表的协议改为Apache V2.0

  • 新的词库将以android-google-pinyin的词库为基础
  • 废弃之前基于cc-cedict的老词库,但是将open-gram自己发现/汇总的一些新词以Apache V2.0协议重新贡献给open-gram词表
  • libpinyin/novel-pinyin/smart-pinyin 项目lead已同意,将各自项目的词库,以Apache V2.0的协议贡献给open-gram项目
  • FIT团队同意将FIT输入法的网络热词,定期反馈给open-gram社区

非常感谢大家的支持和帮助!

SunPinyin的词库一直以来为大家所诟病,希望这次能为大家带来质量更好的词库,和更好的输入体验…

《浪潮之巅》的一点儿读后杂感

读了《浪潮之巅》,书甚好,不过有一些疑问,例如作者谈到百度只能作为一家区域性的互联网公司,和后来的雅虎一样技术竞争力不强,不能和作为科技公司的google相类比…而且已经不可能再从搜索领域诞生一个和google相当的新兴公司了…可是腾讯和百度相比如何呢?作者却要去腾讯做负责搜索的副总裁…

《浪潮之巅》还提到,李开复是因为美国总部对中国大陆网络管制的方式(注意不是制度)不满,中间的矛盾与压力都集中到他一人身上,终于不堪重负而离开谷歌的…这也和李本人的描述有出入,李的说法是“做想做的事”…如果李是因为不堪重负而离开,其实是可以预见到谷歌中国的未来走势一定不很乐观…

《浪潮之巅》贯穿全书有一条“基因决定论”,感觉有些宿命论的味道,我觉得也许google的基因和sun的基因没什么大不同,都是强调创新,工程师驱动的企业文化,况且sun为google提供了许多的管理和工程高层;但是google的商业模式成功了,sun一直没有找到好的商业模式…   

《浪潮之巅》还提到如果Java的商业价值问题,其实Java的商业价值和linux的商业价值是有相似的地方,如果Sun不开放Java标准,可能Java也不会真的发展壮大起来…Linux本身的商业价值可能也是个问题,RedHat不是靠卖Linux发行版来赚钱的,主要还是要靠服务,自己服务都做不过来,还要外包给IBM和HP…

《浪潮之巅》提到Solaris开源的问题,我觉得Solaris开源的晚了,已经被Linux抢了先机;但是开源Solaris,如果还是单纯靠卖硬件,还是一样无以为继;Sun历来还是一个比较open的公司,为Unix贡献了很多,包括NFS等等…Linux很多的特性,都可以说受到Solaris的影响,例如中断处理线程化,systemtap等等…

有人说Sun当初是可以成为服务器领域的苹果,其实如果苹果不是在内容服务上打开局面,仅靠卖个人电子消费品,很难说有现在的成就…没有Music/App store的iPod和iPhone,就算是工业设计一流、精美绝伦,市场潜力又能有多大呢?而且很容易被“山寨”…

#浪潮之巅# 还是说回Sun,Sun是被M$打败的么?我觉得比较勉强… Sun更多是被自己打败了,互联网泡沫的时侯硬件卖得太容易了,钱太容易赚了…纯硬件公司是很难维持高高增长的,还会面临“反摩尔”定律的极大压力…互联网泡沫一破,营收就巨幅缩水,立刻被华尔街抛弃了…

#浪潮之巅# 提到了RISC和CISC之争,我印象中后来的Intel CPU,虽然指令是CISC的,但指令是最终被翻译为类似RISC的微指令来执行的,另外增加了很多SIMD的指令…兼容性是一个巨大的利益,Intel想搞IA64,被AMD的x64整得灰头土脸,最后基本上停滞下来了…

#浪潮之巅# 说到腾讯,我觉得腾讯靠亿万QQ用户为其输血(买Q币,搞一点个性化展示啥的)来赚取高额利润,这个东西好像基础不很牢靠;QZone应该是腾讯转型的起点,不过来的晚了些…在SNS领域被人人和新浪微博占了先机…仅靠IM的优势,恐怕终究不是长久之计…

最后,总而言之,#浪潮之巅# 是本好书,带给自己很多思考,对IT界的历史又多了很多认识和了解…感谢作者,感谢出版商…

暖泉镇与空中草原之行

上周五老婆单位组织outing,去坝上。周五下了一天的雨,一天的时间基本都在赶路,只是在暖泉镇停留了1个多小时。特意穿的一双防水的徒步鞋,在暖泉镇因为雨急水深,被灌了一鞋的水啊,幸好还带了一双拖鞋,周六一天都在穿拖鞋。

周六一天基本也在路上,只是在空中草原停留了一个多小时,景色不及张北的漂亮,骑马也很贵。小小和一众小朋友倒是玩地很开心。回京的路上,有个很会讲故事的叔叔,故事里还穿插很多需要小朋友表演或者解谜的成分,小朋友们围坐在一旁,一直要求叔叔给讲故事,最后把他累得实在讲不动了,小朋友们才悻悻散去…

晚上回到家里已经8点了,草草吃了点饭,困顿非常,儿子也很快就入睡了…

说说我和朋友的矿机配置

因为有一些朋友问起,每次都要单独回复很费事,所以就整理在这里。我和朋友@jackycao只是很初级的矿友,比不得大手笔的玩家,仅供初级矿友们参考,高级矿友勿笑。

  1. CPU: AMD 240E,价格399元,低功耗45W,看中它比较便宜和省电。
  2. 主板:技嘉880G或者870G的双显卡槽的主板,价格619~649左右。
  3. 电源:建议直接上700W以上的电源,注意支持的显卡电源插口的个数。我们选用的是酷冷至尊的GX750W,价格719元。
  4. 内存:随便什么单条2G的内存就好了,大概在110元左右。
  5. 硬盘:如果是装Ubuntu,找个8G的U盘就OK了(Ubuntu 11.4 需要4.4G的空间,虽然安装之后占用的空间不到3G)。
  6. 显卡:我们配的是HD5870*2,650W左右的电源应该可以支持5870*2或者6970*2,不过6990*2的话需要1000W以上的电源;现在应该是双5850性价比比较高了。
  7. 如果要配机箱的话,请注意其支持的显卡长度,我自己用的是酷冷至尊 RC-370-KKN1,价格219元。
  8. TP-Link WR700N迷你无线路由器,89元。我们没有为矿机购买内置或USB的无线网卡,担心Linux的驱动不好找,而TP-Link的这款路由器支持client模式,等同于一个无线卡了,以后还可以用作其他用途。这款路由器的client模式有一些兼容性的问题,请升级到最新的固件,以支持Netgear和D-Link的路由器。

bitcoin python OpenCL mining setup on Ubuntu 11.04

Credits: Thanks to Syke's article on forum.bitcoin.org!!!

0. Install Ubuntu/Drivers/APPSDK/pyopencl

  • Install Ubuntu 11.04 (desktop edition is recommended) on your disk, and install the 3rd party AMD/ATI graphic driver through "System->Administration->Additional Drivers".
  • $ sudo apt-get install python-pyopencl subversion git
  • Download AMD APP SDK for your platform (either 32bits or 64bits), and extracted to somewhere (referred as $SDK_HOME), remove the symbol link /usr/lib/libOpenCL.so (links to nvidia implementation), and cp the *.so files in $SDK_HOME/lib/x86 to /usr/lib; extract the $SDK_HOME/icd-registration.tgz archive, and copy the *.icd files to /etc/OpenCL/vendors.
  • if you have multiple GPU, run $ aticonfig --adapter=all --initial, and relogin, then run $SDK_HOME/bin/x86/clinfo, to check if you have all GPU recognized.

1. Install python-jsonrpc

  • $ svn checkout http://svn.json-rpc.org/trunk/python-jsonrpc
  • $ cd python-jsonrpc/
  • $ sudo python setup.py install

2. Retrieve and run poclbm mining scripts

  • $ git clone http://github.com/m0mchil/poclbm
  • $ cd poclbm
  • $ python poclbm.py -d 0 --user un --pass pw

3. aticonfig over ssh (the easiest way)

  • $ sudo apt-get install openssh-server
  • set autologin when you install/configure ubuntu gdm display manager
  • export DISPLAY=:0.0 after you connected to remote miner machine via ssh/telnet

4. Useful aticonfig commands

  • $ aticonfig --od-enable (enable overdrive)
  • $ aticonfig --odgc --adapter=all (get clocking information for all adapters)
  • $ aticonfig --odgt --adapter=all (get temperature for all adapters)
  • $ aticonfig --adapter=0 --pplib-cmd 'get fanspeed 0' (get speed of fan #0 on adapter #0)
  • $ aticonfig --odsc=950,1225 --adapter=1 (change the peak clock of adapter #1 to 950MHz)

5. Over-clocking with AMDOverdriveCtrl

  • Download and install the deb package here, and install depended wxgtk packages
  • $ AMDOverdriveCtrl -h (check which graphic card is active, and remember the index)
  • $ AMDOverdirveCtrl -i <card index> (you need to run it in native X11 environment), tune the parameters, and save it as default.
  • move the $HOME/.AMDOverdirveCtrl/default.ovdr to different location, then configure another card
  • add AMDOverdirveCtrl -b -i <card index> <profile_file> in your miner start script, note the profile_file must be in the current working directory.

Note: If you run the miner on multiple GPUs with overclocking, the master branch of poclbm seems not very stable as I experienced, the GPU stops to process anymore after running for a while, that I need a hard reset on my machine. Phoenix (though with poclbm kernel) seems much more stable, and comes up with better performance.

bitcoin python OpenCL mining setup on MacOS

Credits: Thanks to Syke's article on forum.bitcoin.org!!! This is only applicable for Mas OS X Snow Leopard (10.6.x).

0. Download and install bitcoin client for MacOS from bitcoin.org

$ cd "$HOME/Library/Application Support/Bitcoin" ### if not exists, run bitcoin client first
$ touch bitcoin.conf
$ echo "rpcuser=un" > bitcoin.conf
$ echo "rpcpassword=pw" >> bitcoin.conf
$ /Applications/Bitcoin.app/Contents/MacOS/bitcoin -server & ### assuming you installed bitcoin in "/Applications"

1. Install c++ boost libraries with homebrew

$ brew install boost

Refer to https://github.com/mxcl/homebrew/wiki/installation, if you do not have homebrew installed.

2. Retrieve, build and install pyopencl

$ git clone http://git.tiker.net/trees/pyopencl.git
$ cd pyopencl
$ ./configure.py --boost-inc-dir=/usr/local/include \
--boost-lib-dir=/usr/local/lib \
--boost-python-libname=boost_python-mt
$ make
$ sudo make install

Note: You may install git via homebrew or installer from git-osx-installer.googlecode.com.

3. Install python-jsonrpc

$ svn checkout http://svn.json-rpc.org/trunk/python-jsonrpc
$ cd python-jsonrpc/
$ sudo python setup.py install

4. Retrieve and run poclbm mining scripts

$ git clone http://github.com/m0mchil/poclbm
$ cd poclbm
$ python poclbm.py -d 0 --user un --pass pw

P.S., the scripts run well, 58000 khash/s with 4850 on my iMac…