《图染色算法的并行化：图染色算法的并行化》

  提示：宽带有限、当前游客访问压缩模式

本系列图表出处文件名：随高清版一同展现

《图染色算法的并行化》

1. 获取 高清版本忘记账户？点击这里登录

1. 下载图表忘记账户？点击这里登录

而对于基于点的方法，其测试结果却有一些不符合常规的地方，低线程数量取得了超过线程数的加速比，并且线程数上升时，加速比反而下降。这是因为，基于点的并行方法的加速来源主要并非来自于多线程的计算，而来自于访存模式不同带来的差异。通过time命令查看运行耗时，发现串行版本的sys_time的耗时是多线程版本的20倍，但二者所进行的系统调用操作相同。由此推测，在多线程版本中，由于大量数据被同时需要，使得大量的数据被同时装载进入cache中，这极大地减少了cache miss的出现，从而显著减少了由于miss带来的巨大耗时，带来了显著的加速比；而当并行度上升时，并行带来的cache miss减少的好处基本不变，但overhead则增大，因此加速比反而下降。