本来只是对高体报告的记录, 没想到变成了对所有事情记录的报告, 今天也算是遵从了昨天的规定, 不过有些地方还是需要改改的, 比如时间, 当然这个时间是需要改进的
今天天气不错, 准备下午去跑步, 所以午睡时间提前一点 1500-1600午休 1600-1730跑步,
qbittorrent加了track的速度的确不错, 最高基本3m封顶, 但是由于资源问题可能速度会下降
今天下午由于耳机未到, 所以去骑车了, 环城路一周->贵池路->合作化路
Arch
大约每篇论文占用两篇的版面, 但是实际大小需要根据内容进行调整, 比较新的论文适当增加内容, 反之减少, 总结占据3篇
在"UCP"中大约算法标点大约有2200字左右, 而纯字数应该也接近一千七八字左右, 再加上图的话, 应该可以占据两页的面积
UCP
在 ucp中主要提出了两部分的内容, 资源monitor UMON与核心划分算法, 这两部分组成了这篇文章的核心工作, 同时这也是这篇论文被其他核心工作所引用的主要工作
UMON
UMON的全称是utility monitor, 实现了对系统资源信息监控的功能, 其具体电路的实现独立于共享cache之外, 这样做可以使UMON监控cache中所有的way的实时信息, 而其后的划分算法也正是利用其获取的信息进行划分,
[./pic/ucp1.png]
UMON所要追踪的实时信息之一就是cache中所有way的命中情况, 举个例子, 对于16路的cache来说, monitor一般要对16种不同的情况进行跟踪, 从一个way到16个way, 这种情况虽然最简单, 但代价却相当地高, 实际上也不具备可行性, 因为这样做需要设置16组tag directory, 并且每一组要有与cache相同的set数, 所以硬件开销十分巨大, 所以这篇论文利用了LRU算法的一个stack property, 就是一旦在LRU算法管理下N路cache命中, 在超过N way时也同样会命中, 这使得在16路cache中只需要包含一组16way的tag directory即可.
[pic/ucp2.png]
如图, 在每个set中都有4个位置, 每个位置代表一个way, 其中每个位置都会设置一个hit counter, 用来记录在这个位置的cache命中情况, 比如说, 在第一个位置访问cache命中, 与其对应的计数器就会加一, 也就能通过这些计数器得出所有位置的命中情况, 进而计算出总的命中率, 而在图b中就显示了LRU的stack property, 如图所示, 当进行100次对cache的访问, 四个位置的命中次数分别为30,20,15,10, 也就是说总的命中率为25%, 这也间接反映出cache访问的一个局部性, 位置越靠前访问的频率越高, 而如果我们将4个cache way减少到3个, 命中率也就变成了65%, 以此类推。
UMON使用了ATD(Auxiiary tag directory)和hit counter来对整个cache信息进行跟踪, ATD与cache有着相同的相联度, 并且使用LRU作为总的替换策略, 一般来说, 在所有的set中都会有额外的tag directory, 并且都有hit counter, 但由于开销过大, 这里就只使用一组hit count对多个set进行跟踪, 但由于hit directory的原因, 这种方式的硬件开销依然不小, 所以这篇文章使用了切比雪夫算法, 估计了在所使用的数据减小到多少的时候, 准确度依然及其接近使用全部tag directory的情况, 而这个做法也使硬件开销变得真正可以接受.
[pic/ucp3.png]
algorithm
这篇文章的另外一个重要的部分就是其划分算法, 这也是整个way-partition领域最核心的部分, 虽然这个算法比较老旧, 也在后续的论文成果中被不断改进, 也不能磨灭其奠基的地位。
首先给出一个简单而又基本的划分策略
[此处有公式]
对于这个划分, 其中只涉及两个应用, UA与UB分别代表这两个应用的具体性能, 此处性能可以用命中率表示, 同时也可以使用IPC(instruction per cycle), 此处, 每个应用至少会分到一个cache way, 并且在每5 million调用一次划分算法, 用来找到对于所有应用性能最好的组合。乍一看算法本身合乎情理, 但却存在一个十分严重的问题, 这个算法的应用环境是两个core的, 而在实际应用场景下, 则可能远多于两个core, 而此时如果还依然按照穷举的方法列举出所有的划分, 再逐一的对比性能, 则成了一个不可能完成的任务, 举个例子, 在32way，8 core的环境下, 需要全部上千万次的划分, 此时开销是无法接受的, 而实际上这是一个NP-hard问题。为解决这个问题, 这篇文章提出了一个贪婪算法, 该算法会逐一分配cache way到所有的应用中, 在每一次分配时, 跟踪所有应用的性能变化, 找到那个能够影响性能最大的应用, 并将这个cache way分配给它, 以达到性能最大化。
多数情况, 上述算法已经是一种最优的情况, 但其本身却还是存在一个问题, 而这篇文章的重点也正是在不断发现问题中解决问题的, 就是贪婪算法本身的问题, 它只能对每一个cache way的性能变化进行预测, 而不能对总的情况有一个合理的把握, 导致最后的untility 曲线是非凸的(non-convex), 见下图, 前8个cache way的性能变化导致它永远不能得到资源分配, 这也就导致划分算法的性能不理想。
[pic/ucp4.png]
为了解决上面的问题, 这篇文章提出了最后一个划分算法, lookahead算法, 顾名思义, 在划分的同时也照顾到了之前的分配情况, 在讨论具体的算法之前, 先给出一个指标MU
[此处为MU公式]
MU可以表示在分配多个cache way时的命中率改变, 而不只是一个cache way, 而在实际的算法中, 也是首先对所有的应用逐一分配所有的cache way, 选出其中对命中率提升最大的进行分配, 以此类推, 这么做不仅可以避免非凸的问题, 也可以将总的时间复杂度降到N^2/2
[pic/ucp5.png]
lammps
上午编写问题20min
下午发过去
转 MD的格式要求
由于要把放到简书上, 所以需要把org的文档转到md格式
1. 属性信息不保留
2. 每段话尽量保证3-4行
3. 表格不保留, 但需要其他进行替换
org-mode
图片问题
* latex
使用的模板由于各种原因出现无法使用的问题, 需要在23号之前进行解决
这里进行问题跟踪与任务划分
21:
- 找出传统可以正常使用中文的方法
见latex网站, 使用的是xeCJK的方法, 而原来也同样是采用的是xeCJK的方法
- 找出如何下载包
tllocalmgr, install, texhash
- 找出本机有什么字体可用
在latex网站中, 本机可能的已经将原本windows的字体载入了进来, 这里未进行验证, 已经验证, 但系统级是否可以使用未知
使用fc-list :lang=zh, 可以看出win字体已经安装
--- 接下来要做的就是查看模板中的字体与本机已安装的字体是否不匹配, package是否有未安装的
*两个公式待整理*
TODO
1. ss
Timetable
1855-2155: 3h
1855-2100: 2000字ucp
1915-2000: umon
2000-2100: algorithm
2100-2120: latex
2120-2140: lammps
2140-2155: 整理+发布
