英语原文共 22 页，剩余内容已隐藏，支付完成后下载完整资料
程序覆盖的最优映射到具有有限内存容量的多核平台
摘 要
本文讨论了将任务映射到基于fpga的多核平台上的问题，在该平台中，核心通常具有有限的内存，因此应该经常使用实现任务的小程序块。在这方面，我们支持一个采用整数线性规划(ILP)的框架，以便在粒度级别的任务级别上找到一个应用程序的最优映射到这样一个多核心的平台上。最优性是在ILP模型的范围内定义的。所提议的框架不仅适用于可以容纳在可用核心上的应用程序，而且也适用于需要比平台提供更多核心的更大的应用程序(甚至多个应用程序)。这是通过将应用程序的不同分区映射到相同的核心集并动态地(在应用程序的生命周期内)覆盖另一个分区来实现的。所提议的映射流使用ILP公式将调度、绑定和放置和路由步骤集成到一个映射过程中。由于ILP解决方案的缓慢性，我们的解决方案仅适用于设计时。它是使用TOMLAB/CPLEX工具箱实现的，我们评估了它对一组40个合成任务图以及一些多媒体应用的有效性。
关键词 应用映射 多核心 FPGA 部分重编程
1介绍
多媒体处理和通信栈的特点是速度和性能的提高。所需的原始计算能力已经被VLSI领域的创新所支持的日益增长的晶体管密度所提供。然而，这种增长必须考虑到在工艺技术、短时间市场和高非经常性工程(NRE)成本的增加方面的困难。现场可编程门阵列(FPGA)是一种有效的降低市场时间和成本的方法。从计算机架构的角度来看，为了提高系统的性能，增加一个核心尺寸不再有效，而许多合理大小的内核正在集成。
在本文中,我们专注于许多核心fpga架构工程师协会等,八开本,马克,VDR,,QUKU,reMORPH ,LWP,来描述,其中核心通常有一个有限的内存,因此应该常常覆盖着一块小程序实现一个任务(在本文中,我们使用术语程序块和任务互换)。除了前面提到的基于fpga的many-core，一个非fpga的多核心架构也可以成为目标。例如,KiloCore包含1000个大小为256times;32位可编程处理器。
应用映射到多核结构已经研究了几十年。还提出了许多基于ILP和基于启发式的映射解决方案。但是，它们都没有考虑到重要的问题，比如程序在内存资源有限的平台上覆盖所需的开销。在FPGA上实现的reMORPH是这样一种体系结构，它包含了一组tiles和本地数据以及对这些块的指令记忆。它并没有实现一个昂贵的网络芯片(NoC)，用于在核心之间进行通信，但是实现了点对点连接，比如粗粒度可重构数组(CGRA)。因此，路由是通过一个固定的互连网络完成的。在这个体系结构中，如果某些路由不可能通过固定的点对点互联，一些tiles可以用来将数据从源任务路由到目标任务。
我们的目标是嵌入和多媒体应用程序，可以被描述为任务图。我们只允许任务图的SDF(同步数据流)。这样的应用程序可以使用建议的ILP公式映射到目标体系结构。目前，唯一的限制是每个任务的大小(在数据和指令方面)，这仅限于对瓦片的局部记忆的大小。即使满足了约束条件，将这样一个任务图映射到动态可重新编程的块的二维数组中，也可能需要任务图的时间划分，因为在这些情况下，图中位数小于任务的数量。本文提出了一种基于ILP公式的任务级映射框架，该框架基于FPGA平台上实现的紧密耦合多核架构，考虑到程序覆盖问题。该框架找到了一个应用程序的最优映射，给出了它的任务图，并找到了部分运行时可编程的多核架构。
激励我们使用一个示例架构组成的3times;3的核心任务映射图所示图1。我们表示数组的第i行和第j列的核心tile (i, j)。在数组中只有9个块，而任务图中有10个任务。因此，任务图被分区，每个分区在一个时间内被数组覆盖。每次将一个新分区映射到该数组时，该数组就应该为该分区重新编程，即。，新分区中的任务应该被覆盖在具有适当连接的核心块上(我们将这个覆盖的分区称为程序覆盖)。任务图分区的数组的单个配置称为快照。在图1的示例中，任务图被划分为两个分区，从而生成两个快照。图1b演示了任务图到数组的映射。我们用映射到tile的任务的索引(正整数)来注释一个tile。如果一个tile用于由一个任务产生的路由数据，我们用生产者任务的索引来标注这个tile，但是用一个减号来标注。例如,瓷砖(1、3)标记(minus;1),因为它是作为路由瓷砖从节点1((1、2)节点6(2、3)。
图1 c显示了一个简单的任务图的另一个例子只有三个任务序列映射到数组大小为3times;3。在tile(1,1)中的task 1处理一个数据块时，它将结果发送到tile(1,2)中的task 2;然后，task 1可以立即开始处理下一个数据块。任务2和任务3之间也是如此。因此，所有的三个tiles都将以流水线方式处理传入的数据块。支持这种流水线实现的一系列核心能力有助于提高系统吞吐量。
像reMORPH这样的多核阵列架构的任务级映射问题已经在中进行了研究。但是，建议的流程有一些限制。首先，基于ilp的映射解决方案目标架构只包含一组具有二维网格互连拓扑的同构块。其次，它不用于任务图，任务图有超过四个传入边。第三，它不允许任务图与后边缘的映射。
在本文中，我们通过放松上述三个限制来扩展之前的工作。我们改进了ILP公式来覆盖任意的互连拓扑(第4节)。目标体系结构可以是同构的，也可以是异构的(第4.2节)。通过添加额外的节点来缓冲通过多个传入边缘传输的数据，并将它们打包成一个输出，就可以解决任务的传入边数。图2中的示例演示了如何通过在相关节点之前添加一个节点来解决5个传入节点的问题。新添加的节点包含一个包含传入数据的简单任务;额外的节点G执行数据打包，而目标节点F则添加了一个代码块，用于打开传入的数据。这个阶段的细节超出了本文的范围。后边缘的覆盖范围是在第3.3节中。最后，通过提出的ILP公式，提出了一种最优映射。作为一种基于fpga的样本，用于实验。我们还为C/ c 应用程序的情况建立了一个实验设置。我们注意到由于ILP解决方案的慢度，我们的解决方案只适用于设计时。
本文的其余部分组织如下。第2节定义要解决的问题。第3节和第4节针对不同的目标和扩展提出了问题。第5节给出了一个解决问题的框架。第6节给出了我们的实验结果和分析。第7节描述了相关的工作，最后是第8节。第8节也提供了关于未来方向的讨论。
2问题定义
我们的算法的目标是将一个数据流应用程序映射为一个二维数组的“任务图”。每个瓦片都可以有一个简单的RISC处理器。特别是，该算法解决了一个大型应用程序的映射问题，该应用程序需要更多的瓦片数量，而不是在织物上使用，同时将多个应用程序映射到织物上。
目标是最小化总执行时间。我们对每个任务做出如下假设。每个任务的代码大小和数据大小分别对应于每个瓦片的指令和数据记忆;否则，任务必须被分解。每个任务的计算时间是固定的，或者可以使用每个任务的平均执行时间。无论如何，我们应该能够估计在设计时的执行时间。
给定应用程序的快照数量的下界取决于任务的数量(n)、行数(K)和列(L)的数量，如下所示。
我们从S的最小可能值开始，如果结果是不可行的，那么我们就增加S，然后重复这个映射过程。
该算法的输入是一个任务图G=lt; V, E gt;表示应用程序。V是一组任务V = {vi |i = 1,2，hellip;，n}和E是表示任务之间数据通道的定向依赖边的集合;E j | E j =lt; vi p, viq gt;， j = 1,2，hellip;，}，在任务图中边缘的数量。
每项任务和边缘都有两种不同的成本:计算成本和支持gramming成本。计算成本ci是任务vi的运行时，或者在仅实现数据路由的情况下，计算成本cj是通过对应于edge ej的瓦片传输数据的延迟。Reprogramming cost ri是在vi中设置计算任务的时间，或者在数据路由瓦的情况下，Reprogramming cost rj是通过ej设置数据路由的时间。
硬件平台是在K行和L列中设置的一组均质砖，{(K, L)| K = 1，hellip;K和l = 1，hellip;，L}，其中任何一块瓦片都可以用于计算或路由。互连是一个网格;每个瓦片都连接到它的四个最近的邻居，除了边界瓷砖。
算法的输出是一组S快照xi;= {xi;s | = 1,。,年代}这样xi;s = { X,y },X S组计算瓷砖,y是一组路由瓷砖的s-th快照。必须提到的是，虽然每个任务只分配一个计算瓦，但可以将一个或多个路由块分配到一个边缘。
映射函数f:G→xi;分区应用程序任务图形为标记的分区p1,p2,hellip;,和pS,每个分区映射到相同的织物在自己的实例的时候(快照),尊重数据依赖的约束。在这种情况下,计算时间delta;s s-th快照将评估基于关键路径延迟那快照。重组时间gamma;s s-th快照是重组时间的计算和路由任务分配给快照。
所提议的映射流的目标应用程序是数据流应用程序，其中输入数据块或帧通过一组任务来生成输出数据。假设A是要处理的帧数，那么应用程序的外部循环将会有一个迭代。在这种情况下，总执行时间是给定的。
但是，如果分配给每个快照的任务在切换到下一个快照之前(这可能需要更大的缓冲区)，可以执行B次来处理B帧(这可能需要更大的缓冲区)，那么总执行时间是给定的。
在delta;s表示关键路径延迟处理B帧在快照年代。注意,一般来说,delta;s远小于Btimes;delta;s流水线数据处理内部快照。
映射过程包括映射任务和边缘。到目前为止，我们还没有讨论到在任务级别上对具有有限内存资源的多内核结构进行最优映射的问题，尽管有一些基于启发式的解决方案来处理NoC互连架构。如果存在这样的解，则ILP找到最优解;它还可以用来研究基于启发式的解决方案对相同问题的效率。在第3、4和5节中，我们开发了一个ILP公式来解决这个映射问题并找到最优解。
一旦一个映射解决方案(将每个任务的绑定和调度映射到一个tile和一个快照)在设计时获得，在运行时进行重新编程，基于映射解决方案。也就是说，控制处理器重新编程，使瓦片能够在预定的时间(快照)上执行绑定到它们的任务。
3问题公式化
在我们的工作环境中总执行时间是总计算时间和总重编程时间的总和。我们首先说明了ILP的制定目标是最小的重新编程成本，然后是应用程序的最小执行时间。最初的提法已在中作了简要的报道。然而，它仅适用于具有二维网格互连拓扑的均质砖。由于在一些任务图中可能会有正向和向后的数据传输边缘，所以我们扩展了算法来覆盖这些边缘。我们进一步扩展了该公式，以覆盖第4节中通用的互连拓扑和异构的tile类型。最后，我们提出了一种基于minec -exec的最优映射的框架。
3.1最小化总重编程时间(min-reprog)
我们首先提出了一个ILP公式，以减少总重编程时间。为了建立约束集，引入了两个二元变量;xi kl s和y j kl s。
每个任务都必须映射到一个并且只有一个在一个快照和因此。
在任何快照中，每个块都可以分配给最多一个任务，或者分配给来自同一个源任务的任意数量的边。在两个独立任务之间没有直接连接的情况下，相关任务之间的边界会经过路由块。因此，边缘被分割成段，每个段被映射到路由路径上的物理连接。也就是说，任何快照s中的任何tile (k,l)都可以由一个任务或来自同一个源节点的大多数边所占用，这可以由它们来表示。
在任务图中表示节点的最大程度。
在任何快照中，瓦片只能路由一个信号(一条边或多条边传递来自同一源节点的相同信号)。下面的不等式表明，来自两个不同来源的任何一对边都不能映射到同一块。
两个任务之间的一个边缘，每个任务映射到它自己的tile，可以映射到两个tiles之间的物理连接。但是，如果没有这样的直接物理连接，则连接应该通过一个或多个路由块。因此，边缘被分割成段，每个段被映射到路由路径上的物理连接。如果一条边被瓦片路由，那么瓦片应该有一个空间或时间(之前的快照)邻居瓷砖，它映射了边缘的源节点，或者路由前一部分的边缘。约束条件是给定的。
类似地，如果一条边被瓦片路由，那么瓦片应该有一个空间或时间(下一个快照)的邻域瓦，它映射边缘的目的节点或路由下一段的边缘。约束条件是给定的。
类似的约束对于映射到一个瓦片以表示其边缘或其边缘的任务来说是必需的。
给出了覆盖任务和实现边缘连接的总重编程成本。
Eq.(13)中的第一项是固定的，因为每个任务都必须映射到计算块上。因此，目标函数可以简化为第二项，即边的总重编程成本。将总重编程成本最小化，结果是最少的路由块。然后基于Eqs中定义的约束集的目标。(4)通过(13)成为边缘的重组总成本最小化所有帧如下由tau;3给出:
我们的映射问题的主要目标是最小化应用程序的总执行时间。但在第一眼看来，用ILP解决问题是不可能的，因为问题的本质是非线性的。为了简化问题，我们可以解决Eq.(14)给出的最小重新编程成本的问题，可以很容易地将其表述为ILP。在接下来的部分中，我们将讨论我们的新技术(使用边缘和任务路径矩阵)，以使min- reg ILP适应主要的目标函数，即minec -exec，同时保持问题的线性。
3.2最小化总执行时间(min-exec)
在这个新的ILP公式中，我们可以使用约束(4)到(13)中描述的相同约束。我们需要改变我们的目标从tau;3 Eq。(14)tau;1或tau;2方程式。(2)和(3)。当B的不同值收敛到相同的min- reg的解时，它可能收敛于minexec的不同解，因为B的不同值可能导致快照s中不同的关键路径。
寻找关键路径延迟delta;s在每个快照的年代,同时保持线性优化问题得到解决通过定义一个新功能叫做路径李斯特。我们的新路径Lister接收一个任务图作为输入，并生成两个矩阵作为输出。在这两个矩阵中，行数等于任务图中的路径数。
在一个矩阵用Pt,州哪些任务存在于每一行对应的路径,而在另一个矩阵用Pe、州边缘存在于每一行对应的路径(例如图。3)。因此Pt和体育用Pt的条目和Pe
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[466826]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
