目录

【转】调度亲和性与映射方法

原文链接:https://gitee.com/openeuler/wisdom-advisor/wikis/%E8%B0%83%E5%BA%A6%E4%BA%B2%E5%92%8C%E6%80%A7%E4%B8%8E%E6%98%A0%E5%B0%84%E6%96%B9%E6%B3%95?sort_id=3076139

亲和性定义

如何在充分利用众核处理器高计算能力的同时降低系统能耗是众核系统面临的关键问题。随着多核技术的发展,众核处理器片内集成的处理器核数越来越多,进一步加剧了多个处理核对片上共享计算资源(例如共享缓存和共享带宽)的争用。在程序运行过程中,如果将具有频繁信息交互的线程分配到不同处理核的硬件线程之上,会引入较高的存储访问延迟,造成高的数据传输开销;如果将无数据相关性的多个线程分配到同一个处理核上,会因不同线程访问不同数据,导致共享缓存数据的频繁换入换出,造成高的共享存储访问冲突,增加额外传输开销。只有将应用程序数据局部性和处理器存储架构有效结合起来,实现应用程序到处理核的合理映射,才能降低不同线程之间的共享存储访问冲突、减少额外传输开销,提高计算资源利用率,提升应用程序的计算性能,降低异构系统整体能耗。

线程间亲和性

我们两个不同的线程对同一地址的内存访问称为共享,大多数用于共享内存的并行编程 api,如 OpenMP 和 Pthreads,直接使用内存访问进行通信。即使是使用显式函数进行通信的消息传递接口(MPI)的实现,也会通过共享内存进行通信优化。通过优化线程在CPU上调度的位置,减少了访问延迟和芯片的通信流量,还减少了应用程序的Cache Miss。

NUMA内存亲和性

NUMA架构下,跨P访问内存时延是最大的,跨NUMA访问次之。通过迁移线程到访问次数最多的NUMA上,或者迁移内存页到线程所在numa(migrate_pages/move_pages系统调用),可以提升性能,但是需要注意的是,当多于一个线程访问同一页面时,线程可能在不同 NUMA 节点的CPU核上执行。在这种情况下,只有其中一个线程可以本地访问,所以线程间亲和性与内存亲和性需要综合考虑。

网络亲和性

当网卡收到数据包时,会将数据放入网卡驱动预先分配的内存(RxRingBuffer)中去,然后通过中断通知某个核A去取并提交协议栈处理,最终得到的数据会被某个跑在核B上的应用使用。在这个过程中,如果A和B是两个不同的核的话,会降低CPU的cache命中率,从而影响应用的性能,当收发包非常频繁时,这个影响也会被放大。

亲和性探测方法

函数调用跟踪

1.ForestGOMP

《Structuring the execution of OpenMP applications for multicore architectures》

来自:https://ieeexplore.ieee.org/document/5470442

https://runtime.gitlabpages.inria.fr/forestgomp/

ForestGOMP是与GCC 4.2兼容的OpenMP运行时库,它提供了一种结构化的方式来有效地将OpenMP应用程序执行到分层(NUMA)架构上。

2.EZTrace

https://ieeexplore.ieee.org/document/5948661

http://eztrace.gforge.inria.fr/about.html

它可以记录对MPI函数,OpenMP指令,pthread同步原语的调用。当然,您可以混合使用编程模型:EZTrace专为支持MPI + threads应用程序而设计。此外,EZTrace可以跟踪进程的内存消耗以及对POSIX I / O的调用(读取,写入,选择,…)

3.wisdom

wisdom会通过ptrace跟踪系统调用统计futex锁的次数,来推测哪些线程具有亲和性,将这些线程绑定在同一NUMA

内存访问跟踪

1.carrefour

《Traffic management: a holistic approach to memory placement on NUMA systems》

来自:https://dl.acm.org/doi/10.1145/2499368.2451157

代码: https://github.com/Carrefour/carrefour-runtime

此文通过基于指令的采样(IBS)(AMD Family 10h特有)统计页面访问信息

2.numalize

《Characterizing communication and page usage of parallel applications for thread and data mapping》

来自:https://www.sciencedirect.com/science/article/pii/S016653161500019X

代码:https://github.com/matthiasdiener/numalize

Numalize是一种内存跟踪工具,用于检测通信(即访问共享内存区域)和使用共享内存API(例如OpenMP和Pthread)的并行应用程序的页面使用情况。它是基于英特尔Pin动态二进制工具(DBI)工具( https://software.Intel.com/en-us/articles/pintool/)使用参考http://brieflyx.me/2017/binary-analysis/intel-pin-intro/,程序运行时在自身代码中插入一定分析代码。

numalize代码片段:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
VOID trace_memory_comm(INS ins, VOID *v)
{
	if (INS_IsMemoryRead(ins)) 
		INS_InsertCall(ins, IPOINT_BEFORE, (AFUNPTR)do_comm, IARG_MEMORYREAD_EA, IARG_THREAD_ID, IARG_END);

	if (INS_HasMemoryRead2(ins))
		INS_InsertCall(ins, IPOINT_BEFORE, (AFUNPTR)do_comm, IARG_MEMORYREAD2_EA, IARG_THREAD_ID, IARG_END);

	if (INS_IsMemoryWrite(ins))
		INS_InsertCall(ins, IPOINT_BEFORE, (AFUNPTR)do_comm, IARG_MEMORYWRITE_EA, IARG_THREAD_ID, IARG_END);
}

3.wisdom

打开EULEROS_TASK_FAULT_SIBLINGS,启动项task_faulting=1开启页面访问统计

wisdom会通过访问/proc/tid/task/tid/task/tid/task_fault_siblings得到页面访问统计信息,然后将线程绑定到与其相关内存最多的numa

线程映射方法

OpenMp

来自

https://software.intel.com/content/www/us/en/develop/documentation/fortran-compiler-developer-guide-and-reference/top/optimization-and-programming-guide/openmp-support/openmp-library-support/thread-affinity-interface-linux-and-windows.html

  • compact

线程将被绑定到系统中最靠近的虚拟 处理器。COMPACT 允许线程共享数据高速缓存,从而改进数据局域性。

线程会先充分利用第一个核,当第一个核上所有硬件线程都被分配后,再充分分配到第二个核,依次类推下去.例如有6核12线程的处理器,分配7个线程,前3个核各获得2个线程,最后一个线程被分配到第四个核,最后两个核没有用到

  • scatter

线程将被绑定到远离的虚拟处理器。这 将允许每个线程具有更高的内存带宽。SCATTER 与 COMPACT 相反。采用scatter方式,线程会被尽可能平均分配.例如一个6核12线程的处理器,分配7个线程, 6个核上先各获得一个线程,再把最后一个线程分配给第一个核.

  • Balanced

线程将以循环(共享)方式绑定到虚拟处 理器。绑定的起始处理器由运行时库以获得最佳性能为目标进行确定。

kMAF

《kMAF:Automatic kernel-level management of thread and data affinity》

来自:https://ieeexplore.ieee.org/document/7855906 代码:https://github.com/matthiasdiener/kmaf

https://www.labri.fr/perso/pelegrin/scotch/

初始化:

  • 线程间亲和性:建立一个矩阵 m,其中每个元素 m[i][j]包含线程 i 和 j 之间共享访问计数。我们可以通过分析线程之间共享访问计数的差异来确定应用程序的线程亲和性的潜力,另外线程间的共享内存的大小也很重要,当共享内存很小时,线程亲和性潜力也较小。

  • NUMA内存亲和性:线程与占有大量内存和访问计数最多的NUMA具有最高的亲和性

运行流程:

  1. 在handle_pte_fault缺页处理中统计页面访问信息;在正常操作期间,每个内存页只有一个page fault(first-touch),这将限制检测机制的准确性。可以通过在每个内存页启用多个page fault来克服这个限制。kMAF 通过周期性清除当前可在线程之间共享的页位,注入这些额外的页面错误。
  2. 分析内存访问行为。有关内存访问的信息存储在矩阵中,同时存储的还有访问页的 NUMA 节点和线程号
  3. 管理NUMA内存亲和性映射,分析每个线程对内存页的访问次数,以检查它们是否应该迁移到不同的 NUMA 节点。如果从一个节点访问的最高数量是次高数量的两倍以上,那么页面将迁移到访问数量最高的节点,背后的思想是防止在应用程序早期初始化过程中迁移页面。
  4. 管理线程亲和性映射。 kMAF 定期应用映射算法( Scotch 映射库)来确定是否需要迁移线程。

https://img.dawnguo.cn/OS/7855906-fig-6-source-small.gif

Machine Learning

《Modeling and Optimizing NUMA Effects and Prefetching with Machine Learning

来自:https://dl.acm.org/doi/epdf/10.1145/3392717.3392765

通过建模和在线分析,提供了在运行时优化NUMA线程/数据放置和预取器配置。我们提出了一种预测模型,该模型可以减少所需的输入信息量和所需的预测复杂性。我们通过选择性能计数器和应用程序配置的子集来提供最丰富的配置文件信息作为输入,并通过将输出预测限制为覆盖大部分性能的配置子集来实现。

Statistical Learning

《Data and Thread Placement in NUMA Architectures: A Statistical Learning Approach》

来自:https://dl.acm.org/doi/epdf/10.1145/3337821.3337893