现在的位置: 首页 > 综合 > 正文

cache oblivious algorithm

2013年10月25日 ⁄ 综合 ⁄ 共 506字 ⁄ 字号 评论关闭

http://en.wikipedia.org/wiki/Cache-oblivious_algorithm

 

道理相对简单,但是想法还是很不错的。

考量cache oblivious最好是对比完全不考虑memory hierarchy结构的算法复杂度测量机制,O(nlogn)这样的,只是计数计算的复杂度。

或者在console上常常做的cache aware的优化,就是针对cache line size来组织数据结构大小,一次prefetch一个cache line的数据做操作。

这个cache oblivious比理想算法更接近于电脑硬件(考虑到memory hierarchiy)但也没有变态到完全根据cache line size来设计数据结构和算法。

简单说来,就是假设一个cache line size,对问题进行分而治之,分的粒度到virtual cache line size,就停止分解。

 

wikipedia上也列举了很多算法。

 


某种程度上讲,自我管理也可以做这种cache相关,人脑有一个最佳处理事情的大小,小了会降低效率,大了导致体力消耗快效率同样低。

把事情分解成较小的一块块的,粒度由个人能力决定,成为解决事情的最佳方案。

抱歉!评论已关闭.