《表2:图染色算法的并行化》
而对于基于点的方法,其测试结果却有一些不符合常规的地方,低线程数量取得了超过线程数的加速比,并且线程数上升时,加速比反而下降。这是因为,基于点的并行方法的加速来源主要并非来自于多线程的计算,而来自于访存模式不同带来的差异。通过time命令查看运行耗时,发现串行版本的sys_time的耗时是多线程版本的20倍,但二者所进行的系统调用操作相同。由此推测,在多线程版本中,由于大量数据被同时需要,使得大量的数据被同时装载进入cache中,这极大地减少了cache miss的出现,从而显著减少了由于miss带来的巨大耗时,带来了显著的加速比;而当并行度上升时,并行带来的cache miss减少的好处基本不变,但overhead则增大,因此加速比反而下降。
图表编号 | XD0015594600 严禁用于非法目的 |
---|---|
绘制时间 | 2018.03.18 |
作者 | 杨兆程 |
绘制单位 | 北京大学 |
更多格式 | 高清、无水印(增值服务) |