高效与高度可移植的多线程系统(DetLock)
Hamid Mushtaq · Zaid Al-Ars · Koen Bertels
摘要
在本文中,我们提出“DetLock”，一种确保在多核系统上运行确定的多线程程序的运行时系统。“DetLock”并不依赖于任何硬件支持或内核修改以确保正确调度线程。它使用逻辑时钟来跟踪进程中的线程。不同于以往的依赖不可移植的硬件更新逻辑时钟的方法,“DetLock”使用了一个编译程序通过插入代码更新这些时钟,从而增加可移植性。对于4核，基准测试时钟的平均开销通过应用一些优化从16下降到到2%。此外, 包括确定调度的整体平均开销是14%。
1.介绍
单线程程序比它们的等同多线程程序更容易测试，调试和维护。这是因为非确定性的唯一来源是罕见的中断或信号。另一方面，多线程程序以共享存储器的访问形式具有更频繁的非确定性源。因此，多线程程序面对重复的问题使用相同的输入运行相同的程序可能会导致不同的输出。这种重复性问题使得多线程序列难以测试和调试。此外，构建这些程序的容错版本也是困难的。这是因为容错系统通常依赖于副本（冗余进程的相同备份）来检测错误。
如果对共享数据的访问不受多线程程序中的同步对象保护，我们可能产生竞争条件，这可能会产生意想不到的结果。以确定的方式运行具有争用条件的程序难以避免出现意外结果的问题，而只是确保相同的结果可以被复制。
理想情况是确保多线程程序的确定性，即使存在竞争条件。单独软件是不可能做到高效率的处理。可以使用宽松的内存模型，其中每个线程写入其自己的专用内存，而共享内存的数据只保证在间隔中提交。然而，定期终止线程提交到共享内存会降低性能，例如CoreDet[2]对于8核的最大开销可能达到11x。我们可以通过仅在同步点（例如锁，屏障或线程创建）提交来减少提交到共享内存的数量。这种方法被DTHREADS [15]采取。这里人们仍然可以想象在高锁定频率情况下应用运行的十分缓慢。此外，由于在这种情况下不太频繁地进行对共享存储器提交数据，所以每次必须提交更多的数据，因此频繁使用存储器的应用程序也是缓慢的。这就是为什么提出硬件方法来提高确定性执行的效率。两个这样的方法是Calvin [7]和DMP [4]。它们使用与CoreDet相同的概念用于确定性执行，但为此目的使用了特定的硬件。由于在软件自身中执行确定性执行是低效的，我们可以放宽要求以提高效率。 例如，Kendo [13]通过锁定保护每个共享内存访问来支持程序的确定性执行。换句话说，它仅支持没有竞态条件的程序的确定性执行。Kendo的作者称之为弱确定性。考虑到大多数编写的程序是无竞争的，并且存在检测竞争条件的工具，例如Valgrind [12]，弱确定性对于大多数编写良好的多线程程序是足够的。因此，DetLock也只支持弱确定性。
Kendo的基本思想是它为每个线程使用逻辑时钟来决定线程何时获取锁。逻辑时钟值最小的线程获得锁。虽然效率很高，Kendo仍然存在可移植性问题。首先，它需要用于给逻辑时钟计数的确定性硬件作为计数器。许多流行的平台（包括许多x86平台）没有任何确定性的硬件作为计数器。其次，Kendo需要修改内核以允许读取硬件计数器来实现确定性执行。
为了克服Kendo面临的可移植性问题，我们的工具DetLock拥有一个完全基于软件的更新逻辑时钟的方法。用于更新时钟的代码通过LLVM [8]编译器插入。因为，LLVM是在许多平台上可用的流行的开源编译器框架，我们的方法是通过一个可广泛移植的平台。此外，它不需要修改内核。我们可以总结出本文的内容如下。
—— 一种更新用于弱确定性调度逻辑的时钟的可移植机制，这取决于编译器而不是使用硬件计数器，因为许多平台没有这样的确定性计数器。
—— 一种用于更新逻辑时钟的不需要修改内核的用户空间方法。
—— 许多优化技术，减少用于更新逻辑时钟开销的代码，并提高确定性执行的性能。
本文是我们以前关于这个主题的工作的扩展[11]。在本文中，我们应用了更多的优化来提高性能。本文组织如下。在第二部分，我们讨论背景和相关工作，而在第三部分，我们概述了DetLock的架构。这之后是第四部分，其中我们介绍用于提高DetLock性能的优化方法。在第五部分，我们评估我们的方案的性能，我们最后在第六部分总结这篇论文。
2.背景和相关工作
在本节中，我们首先讨论确定性执行的当前发展状况，然后讨论我们的内容。
2.1当前发展状况
单线程程序在行为上大多是确定性的。我们这么说主要是因为可以在单线程程序中引入非确定性的中断和信号。然而，这些非确定性事件是很罕见的。另一方面，在多核处理器上运行的多线程程序中，共享内存访问是非确定性的常见来源。
确保多线程程序的确定性的一种方法是用确定性并行语言来编写代码。这样的语言的例子是Stream It [14]和SHIM [5]。
这种方法的缺点是难以将用传统语言编写的程序移植到确定性语言程序，因为这对于用传统语言编程的程序员的学习曲线很高。此外，在基于Kahn过程网络模型的语言中，例如SHIM，难以在不引入死锁[10]的情况下编写程序。
在程序运行时，确定性执行可以通过硬件或软件完成。Calvin [7]是一种硬件方法，以块的形式执行指令，之后在屏障点提交。它使用宽松的存储器模型，其中必须以维持程序的总存储顺序（TSO）的方式提交指令。DMP [4]使用类似的宽松的存储模型。硬件方法的缺点是它们局限于他们开发的平台。
除了硬件方法，还存在用于确定性执行的仅使用软件的方法。一种这样的方法是CoreDet ，其使用批量同步因子以及存储缓冲器和宽松的存储器模型来实现确定性。因此，它类似于Calvin，但仅通过软件实现。逻辑时钟用于确定性执行。由于CoreDet是在软件中实现的，因此它具有非常高的开销，对于8核可能高达11x，而对于Calvin来说最高为2x。另一个类似的方法是DTHREADS。它作为单独的进程运行线程，使得可以通过存储器管理单元跟踪被修改的存储器。仅在诸如锁，屏障和线程创建的同步点处，它从线程的本地存储器更新共享存储器。因此，它避免了像CoreDet一样使用批量同步因子的开销，也不需要像CoreDet那样维护逻辑时钟。然而，高锁定频率和大量使用存储空间的程序的开销仍然非常高。
由于纯软件中确定性执行的表现是低效的。Kendo放宽了要求，它仅在没有竞争条件的程序（弱确定性）下工作。除了在某些处理器中发现的确定性硬件计数器之外，它不使用任何硬件。它确定性地执行线程并当其时钟变得小于其他线程的线程时只允许一个线程完成同步操作，通过断开线程来执行负载平衡。时钟从收回存储时计算，在等待锁定时暂停，并在获取锁定后恢复。Kendo仍然遇到可移植性问题，因为它需要确定性的硬件计数器。许多平台，包括许多x86平台，没有任何确定性的硬件计数器。此外，Kendo需要修改内核以读取这种硬件计数器。一种与确定性多线程相关的技术是记录/重放。使用这种技术的系统的例子是Rerun [6]，Karma [1]和Respec [9]。
2.2我们的相关工作
如上一节所讨论的，我们已经有了诸如Kendo这样的工具，可以在多核平台上确定性地执行多线程程序。然而，使用Kendo的一个主要瓶颈是它需要确定性的硬件计数器，这在许多平台上不可用。为了评估他们的工具，Kendo的作者必须专门使用酷睿2处理器，该处理器具有可用的确定性回收存储计数器。
从图1中我们可以看出，其示出了与期望值相比的回收存储差异，除了酷睿2之外，所列出的处理器都不具有确定性回收存储计数器。此外，Kendo还需要修改内核以访问这些计数器。
图1 各种处理器的回收存储计数器的确定性
现在想象一个场景，公司希望降低软件测试的成本，并通过确定性来缓解软件的维护压力。如果他们使用Kendo技术，它会使他们的软件不可移植，因为它将无法运行在没有任何确定性硬件计数器的处理器上。此外，您可以预设用户不想修改其操作系统的内核。这就是我们的技术的优点，因为它将允许程序在每台机器上运行，而不需要修改内核。
这项工作是我们以前在这个主题上的工作的延伸。通过应用新的优化，我们能够进一步减少由我们的编译器传递插入的时钟更新代码的开销，并提高确定性执行的性能。
3. 架构概述
在本节中，我们讨论DetLock的架构以及它为程序员提供的应用程序编程接口（API）。
3.1框架
我们使用Kendo的算法来执行确定性执行。然而，与需要确定性硬件计数器的Kendo不同，Kendo在许多平台上不可用，而我们在编译时插入代码以更新逻辑时钟。这也意味着我们不需要像Kendo一样修改内核来读取计数器。图2显示了DetLock Pass执行编译的位置，它在LLVM IR（中间表示）代码由LLVM后端转换为最终二进制代码的点之间。
图2 DetLock通过插入更新逻辑时钟的代码来修改LLVM IR代码
我们的逻辑时钟的单位是一个指令。对于需要超过一个时钟周期的指令，逻辑时钟根据指令需要的相近的时钟周期数来更新。然而，为了保持我们的讨论简单易懂，在本文中，对于DetLock来说一个指令等于一个逻辑时钟计数。
图3中示出了Kendo的确定性获取锁的方法。在该图中，给出了具有两个线程的进程的示例。如果线程1在其逻辑时钟为1029时尝试获取锁，则由于线程2的时钟为329，因此它不能这样做，因为线程2的时钟小于线程1的时钟。但是，一旦线程2的时钟超过1029，线程1将获得锁。
所以我们的目的不仅是减少更新时钟的代码，而且还要尽可能快的更新时钟。事实上，在编译时，甚至在执行指令之前，也可以增加时钟。例如，假如我们知道一个末端函数（不调用其它函数的函数）执行固定量的指令，我们可以在执行该函数的任何指令之前增加逻辑时钟。
因此，在我们应用的所有优化中，除了尝试减少时钟更新开销之外，我们还尝试尽量加快时钟。在没有任何优化的情况下，我们在LLVM IR的每个基本块的开始处更新时钟。如果在该块中有一个函数调用，我们分割该块，使得每个块要么都不包含函数调用，要么以函数调用开始和结束。然后，如果该块不包含函数调用，则更新每个块顶部的时钟，否则我们更新函数调用之间的时钟。通过以这种方式分割块，我们可以更容易地应用优化。
图3 Kendo对于确定性执行的获取锁的方法
3.2应用程序接口
我们为锁，屏障和线程创建提供我们自己的函数用于确定性执行。它们在内部使用pthread库。然而，程序员不必为了使用它们而修改代码。我们提供了一个头文件来替换这些函数的定义。头文件可以在makefile中指定，因此不需要修改源代码文件。此外，用于初始化主线程时钟的代码由编译器插入。必须注意的是，由于我们的方法依赖于编译器插入用于确定性执行的时钟，所以不可能添加在库中实现的时钟到函数中（因为它们没有在传递中被编译）。对于在编译器中内置的函数，这个问题也存在，因为LLVM在IR层不为它们生成代码。对于许多内置函数，例如memset和math函数，我们只保留对它们执行指令消耗的时钟的估计，并相应地增加时钟。对于依赖于参数的memset和其他函数，我们参考参数来增加相应的时钟。由于大多数内置函数很简单，我们对他们进行预估。我们提供一个文本文件（指令评估文件）用于这样的目的，其中这些函数用它们接受的指令的大致数量以及它们依赖的输入参数来定义。但是，对于共享库中的函数，这并不总是可能的。一种方法是忽略它们，另一种方法是在尽可能的情况下将它们添加到指令估计文件中（如果它们的指令数目可以令人满意地近似）。
另一个问题是内部使用锁的函数，如malloc。 对于这样的函数，我们提供我们自己的实现方法，用我们自己的确定性锁来替换锁。
4．性能优化
我们应用一些优化来减少时钟更新开销。此外，我们尝试尽量加快时钟，以便等待其他线程的时钟超过自己的线程的等待时间减少。时钟更新代码在时钟被我们的优化置零的块中移除。在本文中，我们用灰色突出显示这些块。为了说明我们的优化的效果，我们将展示优化如何影响示例函数。与每个块相关的时钟显示在赋值运算符的右侧。此外，平行四边形形状的块意味着它包含一个或多个函数调用。下面讨论优化方法。
4.1优化1（时钟函数）
正如在3.1部分中所讨论的，时钟更新越快越好，并且仅具有一个基本块的末端函数是这种优化的理想候选。时钟可以从这样的函数中移除，而是被添加到调用这样的函数的基本块。除了只有一个块的函数之外，我们的方法还考虑具有多个块的末端函数，假定这些函数中没有循环。如果我们看到一个函数采用的所有可能路径没有太大差异，我们计算所有可能路径的平均值，并使用该平均值来更新时钟。我们设定的标准是所有可能路径的最小和最大时钟差应不大于平均值除以2.5。此外，所有不同路径之间的标准偏差不应大于平均值的五分之一。
我们将这样的末端函数称为时钟函数。通过直觉，我们判断可以仅调用时钟函数为需要的函数计时。这样，我们甚至可以对不一定是末端函数的函数进行计时。关于这种优化的更多细节可以在[11]中找到。
以前，在[11]中，我们没有考虑通过函数指针间接调用时钟函数的可能性。在这种情况下，由于我们删除了被计时的函数的时钟，所以时钟不会更新。为了纠正这个问题，我们创建了被计时函数的备份。来自克隆被计时函数的时钟被移除，但是时钟更新代码被插入到原始的被计时函数中。无论我们是什么时候找到一个被直接调用的时钟函数，它都会调用该时钟函数的克隆版本。然而，由于间接调用仍然调用的是原始的时钟函数，即使间接调用，时钟也会正确更新。
剩余内容已隐藏，支付完成后下载完整资料
高效与高度可移植的多线程系统(DetLock)
Hamid Mushtaq · Zaid Al-Ars · Koen Bertels
摘要
在本文中,我们提出“DetLock”，一种确保在多核系统上运行确定的多线程程序的运行时系统。“DetLock”并不依赖于任何硬件支持或内核修改以确保正确调度线程。它使用逻辑时钟来跟踪进程中的线程。不同于以往的依赖不可移植的硬件更新逻辑时钟的方法,“DetLock”使用了一个编译程序通过插入代码更新这些时钟,从而增加可移植性。对于4核，基准测试时钟的平均开销通过应用一些优化从16下降到到2%。此外, 包括确定调度的整体平均开销是14%。
1.介绍
单线程程序比它们的等同多线程程序更容易测试，调试和维护。这是因为非确定性的唯一来源是罕见的中断或信号。另一方面，多线程程序以共享存储器的访问形式具有更频繁的非确定性源。因此，多线程程序面对重复的问题使用相同的输入运行相同的程序可能会导致不同的输出。这种重复性问题使得多线程序列难以测试和调试。此外，构建这些程序的容错版本也是困难的。这是因为容错系统通常依赖于副本（冗余进程的相同备份）来检测错误。
如果对共享数据的访问不受多线程程序中的同步对象保护，我们可能产生竞争条件，这可能会产生意想不到的结果。以确定的方式运行具有争用条件的程序难以避免出现意外结果的问题，而只是确保相同的结果可以被复制。
理想情况是确保多线程程序的确定性，即使存在竞争条件。单独软件是不可能做到高效率的处理。可以使用宽松的内存模型，其中每个线程写入其自己的专用内存，而共享内存的数据只保证在间隔中提交。然而，定期终止线程提交到共享内存会降低性能，例如CoreDet[2]对于8核的最大开销可能达到11x。我们可以通过仅在同步点（例如锁，屏障或线程创建）提交来减少提交到共享内存的数量。这种方法被DTHREADS [15]采取。这里人们仍然可以想象在高锁定频率情况下应用运行的十分缓慢。此外，由于在这种情况下不太频繁地进行对共享存储器提交数据，所以每次必须提交更多的数据，因此频繁使用存储器的应用程序也是缓慢的。这就是为什么提出硬件方法来提高确定性执行的效率。两个这样的方法是Calvin [7]和DMP [4]。它们使用与CoreDet相同的概念用于确定性执行，但为此目的使用了特定的硬件。由于在软件自身中执行确定性执行是低效的，我们可以放宽要求以提高效率。 例如，Kendo [13]通过锁定保护每个共享内存访问来支持程序的确定性执行。换句话说，它仅支持没有竞态条件的程序的确定性执行。Kendo的作者称之为弱确定性。考虑到大多数编写的程序是无竞争的，并且存在检测竞争条件的工具，例如Valgrind [12]，弱确定性对于大多数编写良好的多线程程序是足够的。因此，DetLock也只支持弱确定性。
Kendo的基本思想是它为每个线程使用逻辑时钟来决定线程何时获取锁。逻辑时钟值最小的线程获得锁。虽然效率很高，Kendo仍然存在可移植性问题。首先，它需要用于给逻辑时钟计数的确定性硬件作为计数器。许多流行的平台（包括许多x86平台）没有任何确定性的硬件作为计数器。其次，Kendo需要修改内核以允许读取硬件计数器来实现确定性执行。
为了克服Kendo面临的可移植性问题，我们的工具DetLock拥有一个完全基于软件的更新逻辑时钟的方法。用于更新时钟的代码通过LLVM [8]编译器插入。因为，LLVM是在许多平台上可用的流行的开源编译器框架，我们的方法是通过一个可广泛移植的平台。此外，它不需要修改内核。我们可以总结出本文的内容如下。
—— 一种更新用于弱确定性调度逻辑的时钟的可移植机制，这取决于编译器而不是使用硬件计数器，因为许多平台没有这样的确定性计数器。
—— 一种用于更新逻辑时钟的不需要修改内核的用户空间方法。
—— 许多优化技术，减少用于更新逻辑时钟开销的代码，并提高确定性执行的性能。
本文是我们以前关于这个主题的工作的扩展[11]。在本文中，我们应用了更多的优化来提高性能。本文组织如下。在第二部分，我们讨论背景和相关工作，而在第三部分，我们概述了DetLock的架构。这之后是第四部分，其中我们介绍用于提高DetLock性能的优化方法。在第五部分，我们评估我们的方案的性能，我们最后在第六部分总结这篇论文。
2.背景和相关工作
在本节中，我们首先讨论确定性执行的当前发展状况，然后讨论我们的内容。
2.1当前发展状况
单线程程序在行为上大多是确定性的。我们这么说主要是因为可以在单线程程序中引入非确定性的中断和信号。然而，这些非确定性事件是很罕见的。另一方面，在多核处理器上运行的多线程程序中，共享内存访问是非确定性的常见来源。
确保多线程程序的确定性的一种方法是用确定性并行语言来编写代码。这样的语言的例子是Stream It [14]和SHIM [5]。
这种方法的缺点是难以将用传统语言编写的程序移植到确定性语言程序，因为这对于用传统语言编程的程序员的学习曲线很高。此外，在基于Kahn过程网络模型的语言中，例如SHIM，难以在不引入死锁[10]的情况下编写程序。
在程序运行时，确定性执行可以通过硬件或软件完成。Calvin [7]是一种硬件方法，以块的形式执行指令，之后在屏障点提交。它使用宽松的存储器模型，其中必须以维持程序的总存储顺序（TSO）的方式提交指令。DMP [4]使用类似的宽松的存储模型。硬件方法的缺点是它们局限于他们开发的平台。
除了硬件方法，还存在用于确定性执行的仅使用软件的方法。一种这样的方法是CoreDet ，其使用批量同步因子以及存储缓冲器和宽松的存储器模型来实现确定性。因此，它类似于Calvin，但仅通过软件实现。逻辑时钟用于确定性执行。由于CoreDet是在软件中实现的，因此它具有非常高的开销，对于8核可能高达11x，而对于Calvin来说最高为2x。另一个类似的方法是DTHREADS。它作为单独的进程运行线程，使得可以通过存储器管理单元跟踪被修改的存储器。仅在诸如锁，屏障和线程创建的同步点处，它从线程的本地存储器更新共享存储器。因此，它避免了像CoreDet一样使用批量同步因子的开销，也不需要像CoreDet那样维护逻辑时钟。然而，高锁定频率和大量使用存储空间的程序的开销仍然非常高。
由于纯软件中确定性执行的表现是低效的。Kendo放宽了要求，它仅在没有竞争条件的程序（弱确定性）下工作。除了在某些处理器中发现的确定性硬件计数器之外，它不使用任何硬件。它确定性地执行线程并当其时钟变得小于其他线程的线程时只允许一个线程完成同步操作，通过断开线程来执行负载平衡。时钟从收回存储时计算，在等待锁定时暂停，并在获取锁定后恢复。Kendo仍然遇到可移植性问题，因为它需要确定性的硬件计数器。许多平台，包括许多x86平台，没有任何确定性的硬件计数器。此外，Kendo需要修改内核以读取这种硬件计数器。一种与确定性多线程相关的技术是记录/重放。使用这种技术的系统的例子是Rerun [6]，Karma [1]和Respec [9]。
2.2我们的相关工作
如上一节所讨论的，我们已经有了诸如Kendo这样的工具，可以在多核平台上确定性地执行多线程程序。然而，使用Kendo的一个主要瓶颈是它需要确定性的硬件计数器，这在许多平台上不可用。为了评估他们的工具，Kendo的作者必须专门使用酷睿2处理器，该处理器具有可用的确定性回收存储计数器。
从图1中我们可以看出，其示出了与期望值相比的回收存储差异，除了酷睿2之外，所列出的处理器都不具有确定性回收存储计数器。此外，Kendo还需要修改内核以访问这些计数器。
图1 各种处理器的回收存储计数器的确定性
现在想象一个场景，公司希望降低软件测试的成本，并通过确定性来缓解软件的维护压力。如果他们使用Kendo技术，它会使他们的软件不可移植，因为它将无法运行在没有任何确定性硬件计数器的处理器上。此外，您可以预设用户不想修改其操作系统的内核。这就是我们的技术的优点，因为它将允许程序在每台机器上运行，而不需要修改内核。
这项工作是我们以前在这个主题上的工作的延伸。通过应用新的优化，我们能够进一步减少由我们的编译器传递插入的时钟更新代码的开销，并提高确定性执行的性能。
3. 架构概述
在本节中，我们讨论DetLock的架构以及它为程序员提供的应用程序编程接口（API）。
3.1框架
我们使用Kendo的算法来执行确定性执行。然而，与需要确定性硬件计数器的Kendo不同，Kendo在许多平台上不可用，而我们在编译时插入代码以更新逻辑时钟。这也意味着我们不需要像Kendo一样修改内核来读取计数器。图2显示了DetLock Pass执行编译的位置，它在LLVM IR（中间表示）代码由LLVM后端转换为最终二进制代码的点之间。
图2 DetLock通过插入更新逻辑时钟的代码来修改LLVM IR代码
我们的逻辑时钟的单位是一个指令。对于需要超过一个时钟周期的指令，逻辑时钟根据指令需要的相近的时钟周期数来更新。然而，为了保持我们的讨论简单易懂，在本文中，对于DetLock来说一个指令等于一个逻辑时钟计数。
图3中示出了Kendo的确定性获取锁的方法。在该图中，给出了具有两个线程的进程的示例。如果线程1在其逻辑时钟为1029时尝试获取锁，则由于线程2的时钟为329，因此它不能这样做，因为线程2的时钟小于线程1的时钟。但是，一旦线程2的时钟超过1029，线程1将获得锁。
所以我们的目的不仅是减少更新时钟的代码，而且还要尽可能快的更新时钟。事实上，在编译时，甚至在执行指令之前，也可以增加时钟。例如，假如我们知道一个末端函数（不调用其它函数的函数）执行固定量的指令，我们可以在执行该函数的任何指令之前增加逻辑时钟。
因此，在我们应用的所有优化中，除了尝试减少时钟更新开销之外，我们还尝试尽量加快时钟。在没有任何优化的情况下，我们在LLVM IR的每个基本块的开始处更新时钟。如果在该块中有一个函数调用，我们分割该块，使得每个块要么都不包含函数调用，要么以函数调用开始和结束。然后，如果该块不包含函数调用，则更新每个块顶部的时钟，否则我们更新函数调用之间的时钟。通过以这种方式分割块，我们可以更容易地应用优化。
图3 Kendo对于确定性执行的获取锁的方法
3.2应用程序接口
我们为锁，屏障和线程创建提供我们自己的函数用于确定性执行。它们在内部使用pthread库。然而，程序员不必为了使用它们而修改代码。我们提供了一个头文件来替换这些函数的定义。头文件可以在makefile中指定，因此不需要修改源代码文件。此外，用于初始化主线程时钟的代码由编译器插入。必须注意的是，由于我们的方法依赖于编译器插入用于确定性执行的时钟，所以不可能添加在库中实现的时钟到函数中（因为它们没有在传递中被编译）。对于在编译器中内置的函数，这个问题也存在，因为LLVM在IR层不为它们生成代码。对于许多内置函数，例如memset和math函数，我们只保留对它们执行指令消耗的时钟的估计，并相应地增加时钟。对于依赖于参数的memset和其他函数，我们参考参数来增加相应的时钟。由于大多数内置函数很简单，我们对他们进行预估。我们提供一个文本文件（指令评估文件）用于这样的目的，其中这些函数用它们接受的指令的大致数量以及它们依赖的输入参数来定义。但是，对于共享库中的函数，这并不总是可能的。一种方法是忽略它们，另一种方法是在尽可能的情况下将它们添加到指令估计文件中（如果它们的指令数目可以令人满意地近似）。
另一个问题是内部使用锁的函数，如malloc。 对于这样的函数，我们提供我们自己的实现方法，用我们自己的确定性锁来替换锁。
4．性能优化
我们应用一些优化来减少时钟更新开销。此外，我们尝试尽量加快时钟，以便等待其他线程的时钟超过自己的线程的等待时间减少。时钟更新代码在时钟被我们的优化置零的块中移除。在本文中，我们用灰色突出显示这些块。为了说明我们的优化的效果，我们将展示优化如何影响示例函数。与每个块相关的时钟显示在赋值运算符的右侧。此外，平行四边形形状的块意味着它包含一个或多个函数调用。下面讨论优化方法。
4.1优化1（时钟函数）
正如在3.1部分中所讨论的，时钟更新越快越好，并且仅具有一个基本块的末端函数是这种优化的理想候选。时钟可以从这样的函数中移除，而是被添加到调用这样的函数的基本块。除了只有一个块的函数之外，我们的方法还考虑具有多个块的末端函数，假定这些函数中没有循环。如果我们看到一个函数采用的所有可能路径没有太大差异，我们计算所有可能路径的平均值，并使用该平均值来更新时钟。我们设定的标准是所有可能路径的最小和最大时钟差应不大于平均值除以2.5。此外，所有不同路径之间的标准偏差不应大于平均值的五分之一。
我们将这样的末端函数称为时钟函数。通过直觉，我们判断可以仅调用时钟函数为需要的函数计时。这样，我们甚至可以对不一定是末端函数的函数进行计时。关于这种优化的更多细节可以在[11]中找到。
以前，在[11]中，我们没有考虑通过函数指针间接调用时钟函数的可能性。在这种情况下，由于我们删除了被计时的函数的时钟，所以时钟不会更新。为了纠正这个问题，我们创建了被计时函数的备份。来自克隆被计时函数的时钟被移除，但是时钟更新代码被插入到原始的被计时函数中。无论我们是什么时候找到一个被直接调用的时钟函数，它都会调用该时钟函数的克隆版本。然而，由于间接调用仍然调用的是原始的时钟函数，即使间接调用，时钟也会正确更新。
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[137464]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
