面向运行时分区的可重构片上系统的实时操作系统外文翻译资料

面向运行时分区的可重构片上系统的实时操作系统

Marcelo Gouml;tz, ¹ Achim Rettberg ² and Carlos Eduardo Pereira ³

¹Heinz Nixdorf Institute

University of Paderbom, Germany

mgoetz@uni-paderborn.de

²C-LAB

University of Paderborn, Germany

achim@c-lab.de

³Departamento de Engenharia Eletrica

UFRGS - Universidade Federal do Rio Grande do Sul - Brazil

摘要: 利用基于FPGA和CPU的体系结构的支持，成功设计了可重构计算。此外，新的混合 FPGA（例如 Virtex-ll ProTM）提供了嵌入可编程门阵列领域的硬核通用处理器 (GPP)。连同部分重新配置的能力，这些芯片对于实现运行时可重新配置的嵌入式系统非常有吸引力。然而，该领域的大部分努力都是为了在应用程序级别应用这些功能，而留给操作系统 (OS) 提供必要的机制来支持这些应用程序。本文提出了一种运行时可重构操作系统的方法，该方法利用新的混合FPGA芯片基于应用需求的在线估计来重构自身。本文重点介绍混合架构上操作系统服务的运行时分配和重新配置。所提出的模型使用 0-1 整数编程策略来分配混合架构上的 OS 组件，以及对其的替代启发式算法。此外，还介绍并讨论了对重新配置成本的评估。

关键字：可重构计算、片上系统、实时操作系统

*这项工作是在特殊研究计划 614 - 机械工程中的自我优化概念和结构 - 帕德博恩大学的过程中开发的，并代表其出版并由 Deutsche Forschungsgemeinschaft 资助。

1. 介绍

如今，现场可编程门阵列（FPGA）在可重构计算（RC）领域的使用已经得到广泛应用。特别是 FPGA 的运行时重新编程能力使其在可重新配置系统中的使用非常有吸引力 新兴的混合 FPGA 更具吸引力，它具有被大量可重新编程逻辑包围的硬核或软核通用处理器 (GPP) .这些新组件为为片上系统 (SOC) 设计可重构架构开辟了多种有趣的可能性。 [2]。

我们研究的挑战之一是为可用于自优化系统的运行时可重构架构提供支持。此类系统用于实现和实现对交通系统的控制，如 [1] 中描述的那样。在应用需求可能动态变化的动态环境中，出现了可重构操作系统的概念，这是新兴的研究领域。

与脱机完成此类操作系统 (OS) 设计的常规方法不同，所提出的方法建议使用新的部分可重构架构，以支持硬件/软件可重构操作系统的开发 [6]。在这个提议的架构中，RTOS 能够适应当前的应用需求，为此目的定制 RTOS 组件。因此，系统会不断分析需求，并在混合架构上重新配置 RTOS 组件，以优化系统资源的使用。因此，系统能够即时决定需要哪些 RTOS 组件以及将它们分配到哪个执行环境（CPU 或 FPGA）。

本文重点研究了一种实时操作系统服务的在线分区算法，该算法试图最小化整体资源利用率和组件的重新配置成本。

本文的其余部分组织如下：第 2 节简要介绍了有关操作系统服务的硬件实现及其灵活性的最新分析。然后，第 3 节简要介绍了所使用的架构。第 4 节介绍了使用 0-1 整数规划 (BIP) 和重新配置成本评估的系统公式。在第 5 节中介绍了该评估的运行时执行分析，以及针对组件分配问题的启发式算法。第 6 节介绍了使用 MATLAB 的一些评估结果，将所提出的启发式算法与 BIP 提供的最佳解决方案进行比较。最后，第 7 节显示了一些结论和未来的工作。

图 1. 基于 Virtex-ll ProTM FPGA 的建议架构。

1. 相关工作

在硬件中实现操作系统服务的想法并不新鲜。文献中的几项工作和 [14] 表明硬件实现可以显着提高 RTOS 功能的性能和确定性。由于通常缺乏资源，在嵌入式系统设计中仔细考虑了操作系统施加的开销，通过在硬件中实现 RTOS 服务，可以大大减少。但是，到目前为止，所有方法都基于本质上是静态的实现，这意味着即使应用程序需求可能发生显着变化，它们在运行时也不会更改。

在可重构计算领域，重构方面一直集中在应用层面（见[7]、[18]和[16]）。在操作系统级别，研究仅限于为这些应用程序提供运行时支持（参见 [10]、[20] 和 [191]）。

在本文提出的方法中，我们将这些概念的使用和硬件支持扩展到操作系统级别。此外，基于最先进的分析，对于自我优化的可重构 RTOS，还没有提出过类似的方法。

1. 架构

我们的目标架构由一个 CPU、可配置逻辑元件 (FPGA)、内存和连接组件的总线组成。 大多数这些元件都在单个芯片中提供，例如来自 Xilinx 公司的 Virtex Il ProTM。 能够重新配置的 RTOS 服务以两种不同的实现方式存储在外部 SDRAM 芯片上：作为软件对象和作为 FPGA 配置比特流（见图 1）。

运行时重配置 (RTR) 模块（参见 [5]）为 RTOS 提供必要的服务以管理 FPGA 资源：模块放置、加载和分配。 有关此架构的更多详细信息，请参见 [9] 和 [8]。

1. 问题描述

在两个执行环境上分配 RTOS 组件的问题可以看作是一个典型的分配问题。 因此，我们决定使用二进制整数规划 (BIP) [17] 和 [21] 对问题进行建模。 一组可用服务表示为 S = {Sio 其中每个服务 i 都有其针对 CPU (j = 1) 或 FPGA (j = 2) 的实现。 每个组件都有一个估计成本，它表示该组件使用的执行环境中的资源百分比。 在 FPGA 上，它代表组件所需的电路面积，在 CPU 上，它代表它使用的处理器。 请注意，这些成本不是静态的，因为应用程序需求被认为是动态的。 稍后将在第 4.2 小节中讨论该主题。

4.1操作系统服务分配

将组件分配给 CPU 或 FPGA 由变量 Ci,j 表示。如果将组件 i 分配给执行环境 j，则称 Ci,j = 1，否则称 Ci,j = 0。由于当前应用程序可能不需要某些组件，因此不应将它们分配给 CPU (j = 1) 或 FPGA (j = 2)。因此，为了正确表示这种情况，我们认为该组件应该留在内存池（j = 3）中。由于我们专注于 CPU 和 FPGA 之间的资源利用率优化，因此我们定义放置在内存池中的组件 (j = 3) 不消耗任何资源 (Ci,3 = 0)。操作系统组件的第三个分配位置的定义对于重新配置成本估计更有用，这将在第 4.2 节中看到。

资源是有限的，这对我们的 BIP 公式产生了两个约束：可用的最大 FPGA 面积 (Amax) 和为操作系统保留的最大 CPU 工作负载 (Umac)。因此，硬件组件和软件组件分别使用的总 FPGA 面积 (A) 和总 CPU 工作负载 (U) 不能超过它们的最大值。这些约束表示为

我们还认为一个组件 i 可以只分配给一个执行环境： 对应于每个 i = 1,hellip;, n。

为了避免其中一个执行环境的使用量接近最大值，我们指定了一个约束以在两个执行环境之间保持平衡的资源利用率 (B)：B = IU - Al le;delta;. 最大允许的不平衡资源在哪里 CPU 和 FPGA 之间的利用率。 权重 w1和 w2 用于正确比较两个不同执行环境之间的资源利用率。 如果从执行环境使用的资源未接近其最大值，它将有能力吸收应用程序需求的某些变化。 此特性对于实时系统很有用，以避免应用程序因工作负载瞬变而错过截止日期。 请注意，这种方法不能保证硬实时约束。 然而，对于软实时系统，它是有用的。

用于最小化整个资源利用率的目标函数定义为

该 BIP 的解决方案是赋值变量 Xi,j，我们将其定义为特定的系统配置：Gamma; = {}

4.2 重新配置成本

正如在第 4 节中所说，应用需求被认为是随着系统生命周期的变化而变化的。这些修改由组件成本 Ci,j 的变化表示。这会导致某些系统配置 I 在应用程序更改后可能不再有效。因此，有必要对组件分区进行持续评估。每当系统达到不平衡状态（IU -Al gt; delta;）时，应重新分配 RTOS 组件，以使系统再次处于所需配置。在这种情况下，不仅需要重新解决新的分配问题，还需要评估将系统从到 重新配置所需的成本（时间）。由于我们正在处理实时系统，因此这种评估是必要的. 因此，我们可用于重新配置活动的时间有限。

每个组件的重新配置成本表示将一个组件从一个执行环境迁移到另一个执行环境所需的时间。因此，我们需要为每个可能的组件迁移指定其相应的成本。正如第 4.1 节所示，我们的模型假设了三种不同的环境（j = {1, 2, 3}）。环境 j = 3（内存池）的定义对于正确表示新的 OS 服务到达系统的情况是必要的。当应用程序需要的服务既不在 CPU 上也不在 FPGA 上可用，但它存储在内存池中时，就会发生这种情况。这同样适用于离开系统的服务（应用程序不再需要它）。因此，我们为组件 i 定义了一个 3 x 3 大小的迁移成本矩阵 Ri。让 Ri ={ }，其中 j 和 j 是组件 i 的当前和新的执行环境。

如果和 是组件 i 的当前分配和新分配，则系统的完整重构成本 K（总重构时间）定义为：

在我们当前的方法中，与组件相关的迁移成本包括将组件从一个执行环境移除到另一个执行环境的所有必要步骤。 这些步骤代表了使用组件对 FPGA 进行编程或将软件组件与 CPU 程序链接、在不同执行环境之间转换上下文（必要时）以及从内存池读取组件实例的时间。

1. 运行时间分析

由于我们的操作系统旨在支持实时应用程序，因此需要使用服务分配和系统重新配置的确定性行为来处理应用程序时间限制。

5.1分配问题的启发式算法

BIP 的解决方案为分配问题找到了最佳解决方案。对于一小组组件，这种方法非常适合。然而，解决所有规模的问题在计算上过于复杂。因此，我们目前正在使用基于启发式贪婪的算法来解决这个问题。

算法开始选择当前应用程序所需的成本最小的组件，并将该组件分配给相应的执行环境。然后它在剩余的未分配组件中选择成本最小的组件，以便它尝试保持 CPU 资源 U 的使用量等于 FPGA 资源 A。重复此过程，直到所有组件都已分配。该算法通过检查是否满足 CPU 和 FPGA 资源使用约束来终止：U Umax； A Amax 。如果是，则算法返回有效的分配解决方案，否则返回错误。可以看出，该算法的多项式复杂度为 O(n2)，因为我们只有一个 for 循环，它在（最大）n 个元素的列表中生成 n 次搜索。该算法也显示在算法 l 中。

请注意，该算法不考虑平衡约束 6。因此，不能保证它会提供满足此约束的解决方案。因此，提出了第二种算法来改进平衡 B 以满足 ouml; 约束。它基于 Kernighan-Lin

Algorithm 1 Heuristic for service assignment

= {} Set of components available for CPU (j = 1)

= {} Set of components available for FPGA (j = 2)

= {} Assignment of CPU components

= {} Assignment of FPGA components

C = U; X = U ; U = A = 0

n = number of components

for k = 1 to n do

if U A then

Find an unassigned component i among {} so that it has the smallestcost.

Assign this component to CPU: = 1; = 0

else

Find an unassigned component i among {} so that it has the smallest cost.

Assign this component to FPGA: = 1; = 0

end if

U =

A =

剩余内容已隐藏，支付完成后下载完整资料

英语原文共 12 页，剩余内容已隐藏，支付完成后下载完整资料

资料编号：[596105]，资料为PDF文档或Word文档，PDF文档可免费转换为Word