从循环静态过程网络到多维软件流水的代码生成

从循环静态过程网络到多维软件流水的代码生成引用此版本：穆罕默德·费拉希从循环静态过程网络到多维软件流水的代码生成。其他[cs.OH]。巴黎南大学-巴黎Xi，2011年。英语NNT：2011 PA 112046。电话：00683224HAL Id：tel-00683224https://theses.hal.science/tel-006832242012年3月28日提交HAL是一个多学科的开放获取档案馆，用于存放和传播科学研究文件，无论它们是否已这些文件可能来自法国或国外的教学和研究机构，或来自公共或私人研究中心。L’archive ouverte pluridisciplinaire博士论文集专业：信息巴黎信息学博士学校Présenté par穆罕默德·费拉希苏耶特-德拉泰斯从循环静态过程网络到多维软件流水的多维管道编码中的循环静力学过程研究从2011年4月22日起至陪审团成员：PR. Yannis Manoussakis总统PR. Pierre Boulet特别报告员PR. Alain Girault特别报告员PR. Albert Cohen导演PR. Daniel Etiemble考官M. 莱昂内尔·拉卡萨涅巴黎南我简历流动数据的应用是优化程序的重要内容，这是由于计算的高度紧迫性和应用领域的多样性：通信、禁运系统在这一点上，我们提出了一种“框架工作”，以便在一般情况下应用于焊剂和夹杂物。对应用逻辑管线时最大边界值的平行化进行了初步探讨。Après on fusionne le prologue etCe process is un pipeline multidimensionnel ，quelques occurrences （ ou instructions ） sont décalées par des itérations de laboucle interne et该技术的应用可以改善性能，在没有增加代码尾部的情况下提取并行代码，并在一般情况下应用于流量和流量计摘要基于流的应用程序，有序序列的数据值，是程序优化的重要目标，因为他们的高计算要求和他们的应用领域的多样性：通信，嵌入式系统，多媒体等，在专用流语言的设计和实现中最重要和最困难的问题之一是如何调度这些应用程序在细粒度的方式来利用可用的机器资源。在这篇论文中，我们提出了一个框架，用于细粒度调度流应用程序和嵌套循环一般。首先，我们尝试通过找到重复的内核模式来流水线化稳定状态阶段（内部循环），并尽可能并行地执行Actor occurrence。然后，我们合并内核的prolog和epilog的流水线阶段，将它们移出外循环。合并内核prolog和epilog意味着我们将actor事件或指令从一个阶段迭代转移到另一个阶段迭代，从一个外部循环迭代转移到另一个外部循环迭代，这是一个多维转移。实验表明，我们的框架可以提高性能，并行提取，而不增加代码大小，在流媒体应用程序和嵌套循环一般。IVIII内容摘要内容1引言我I11.1导言。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11.2艺术状态. . . . . . . . . . . . . . . . . . . . . . . . . . . . .21.3我们的贡献. . . . . . . . . . . . . . . . . . . . . . . . . . .31.4论文概述. . . . . . . . . . . . . . . . . . . . . . . . . . . . .3我52流理论72.1导言。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72.2基本概念. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .72.3流应用程序。. . . . . . . . . . . . . . . . . . . . . . . . .82.4计算模型. . . . . . . . . . . . . . . . . . . . . . . . .92.4.1卡恩过程网络。. . . . . . . . . . . . . . . . . . . .92.4.2数据流网络。. . . . . . . . . . . . . . . . . . . . . . .12同步数据流网络. . . . . . . . . . . . . . .142.5结论。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .153依赖分析和循环转换173.1导言。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .173.2依赖性分析. . . . . . . . . . . . . . . . . . . . . . . . . .173.2.1依赖的类型. . . . . . . . . . . . . . . . . . . . . .173.2.2表示依赖关系。. . . . . . . . . . . . . . . . . . .203.2.3循环依赖性分析。. . . . . . . . . . . . . . . . . . .203.3循环变换。. . . . . . . . . . . . . . . . . . . . . . . . .223.3.1环路融合。. . . . . . . . . . . . . . . . . . . . . . . . . . .223.3.2环路交换。. . . . . . . . . . . . . . . . . . . . . . . .233.3.3循环平铺。. . . . . . . . . . . . . . . . . . . . . . . . . . .243.3.4重新定时。. . . . . . . . . . . . . . . . . . . . . . . . . . . . .253.3.5软件流水线。. . . . . . . . . . . . . . . . . . . . . . .273.4结论。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .30IV4依赖消除技术314.1导言。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .314.2虚假依赖消除技术。. . . . . . . . . . . . . . . .314.2.1更名。. . . . . . . . . . . . . . . . . . . . . . . . . . . .324.2.2私有化。. . . . . . . . . . . . . . . . . . . . . . . . . .324.2.3节点拆分。. . . . . . . . . . . . . . . . . . . . . . . . . .334.2.4转换为单一分配形式。. . . . . . . . . . . .344.3结论。. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .355背包问题375.1一.导言. 375.2定义375.3背包问题385.3.10-1-背包问题5.3.2有界背包问题395.3.3无界背包问题395.4计算复杂性395.5背包问题解决方案405.5.1动态规划解405.5.2贪婪近似算法：415.6结论41II不完全嵌套多维移位（INMS） 436问题概述6.1导言. 456.2规格456.3全球视野466.4预调度算法476.5不完全嵌套多维移位506.5.1PhasePhaselization516.5.2演员射击指数516.5.3PhaseProlog-EpilogMoving 526.5.3.1PhaseProlog-Epilog合并536.5.3.2其他阶段的阶段后记填充6.5.4Phase Prolog-Epilog Moving Effect onOther Phases对其他6.6多维转换形式化566.6.1PhaseProlog-Epilog合并576.6.2其他阶段的阶段后记填充6.7INMS实施60III7图案表移位617.1导言. 617.2启发式617.3图案表移位627.3.1第63周期7.4简单案例算法637.4.1算法647.4.2运行实施例667.4.3终止677.4.4正确性677.4.5备注。...........................................................................................697.5结论708Prolog EpilogMerging 738.1导言. 738.2问题陈述738.2.1运行实施例748.2.2阶段间依赖性768.3可流水线化阶段的表征8.3.1因果关系788.3.2第80章充分必要条件8.4全局优化问题808.4.1多维背包问题808.4.2算法818.5返回运行示例828.6去除依赖8.6.1用重命名算法84实现8.6.2代码生成858.7相关工作和挑战858.7.1管理寄存器压力868.7.2管理代码大小868.7.3多维调度868.8结论879Prolog-EpilogMerging 89的代码生成9.1一、导言. 899.2序言-尾声合并实现思路899.2.1PhaseProlog-Epilog合并919.2.2Phase Prolog-Epilog合并实施929.2.2.1循环嵌套检测939.2.2.2Prolog Epilog移动和核心复制939.2.2.3计算迭代器边界959.2.2.4演员出现坐标的计算959.2.3Phase Prolog-Epilog合并对LoopNest 959.2.3.1理念96IV9.2.3.2算法989.2.3.3Epilog建筑1039.2.3.4演员出现坐标的重新计算1059.3技术扩展1059.3.1参数深度序言-尾声合并1069.3.2将INMS与其他优化技术相9.4结论10710 实验10910.1 导言. 10910.2 Prolog-epilog合并适用性10910.3 多相图像放大基准11010.4 结论11211 结论11311.1 我们的贡献11311.2 未来的工作1141第1章绪论1.1介绍许多体系结构已经被设计和构造来利用流应用的并行性。专门的硬件用于Cheops视频处理系统的流操作[7]。媒体处理的Imagine架构也考虑了流操作，但没有专门的功能单元[51]。原始架构可以支持流代码，因为它的概念，复制处理元素和快速编译器控制的互连网络[65]。其他架构也存在，如Cell处理器。尽管有所有这些架构，但它们中很少有编译器和语言用于流应用程序编程。这样的编译器或语言应该帮助程序以自然的方式表达流计算，而不需要关于目标机器的信息。程序员也不需要关心流操作的调度;这是编译器的任务。语言设计和范例应该足够容易使其流行，特别是当语言用户来自不同的科学领域时，如流应用程序。一个有趣的问题可能会被问到：为什么我们不使用通用语言，比如C语言，当它已经很容易和流行的时候？通用语言不适合流编程：它们不提供流的直观表示，这降低了可读性，鲁棒性和程序员的生产力。此外，由于数据的广泛并行性和规则通信模式，流在通用语言中是隐式的;编译器没有流意识，不能执行流特定的优化。此外，大多数通用语言都是为Von-Neumann架构构建的，这不适合流应用及其架构[4]。令人惊讶的是，很少有特殊用途的流语言。它们在理论上是合理的，但它们不足以用于任何流媒体应用程序的开发。有时，使用一种流语言开发流应用程序是一个研究项目。原因是流应用程序不像一般的应用程序：流的性质直接影响它们的设计和开发。 数据可以以静态或动态的方式流传输。 这意味着数据流可以是统一的，也可以是不统一的，也可以是角色模型（独立操作）。2通信可以是静态的或动态的，这取决于它是否可以在执行时间期间改变这取决于应用程序运行的系统。一个例子是：一个移动电话用户离开一个车站区域，并前往另一个是一个异步事件。因此，应用环境也影响应用程序的设计和实现。在理论上，人们做了大量的工作和研究。 研究人员已经尝试根据其流和通信性质对不同的流应用进行分类，并且存在用于它们的计算模型，如Kahn网络、数据流网络、同步数据流（SDF）、布尔数据流（BDF）、动态数据流网络（DDF）等[42]。例如，SDF用于均匀流应用，DDF用于非均匀流应用。找到适合应用程序的模型并不足以开发应用程序，执行应用程序意味着执行不同的参与者，每个参与者在多个实例中执行多次。行动者是独立的，因为他们只依赖于他们的投入。如果有足够的输入数据，它们就可以被执行。那么所有的演员执行序列都是有效的时间表吗？是否存在无效的演员订单？制约这一选择的因素是什么？是否总是可以找到一个有效的时间表？是否应该在编译时找到此调度？令人惊讶的是，目标体系结构会影响有效计划的选择。在一台机器上编译的代码不能在另一台机器上执行。流媒体应用程序的执行意味着资源和时间的消耗。调度大小和通道大小直接取决于空闲内存和缓冲区大小。并行性的提取意味着尽可能好地利用机器资源，包括寄存器和操作单元。如果应用有时间限制，例如实时应用，对有效调度的研究变得更加困难。我们关注SDF应用程序的静态调度，编译期间的调度，我们试图回答上面提出的问题。1.2现有技术因此，问题是如何安排SDF应用程序。据我们所知，StreamIt和Lucid Synchrone是流应用程序语言的最新作品。它们来自不同的语言范式。 StreamIt被设计和开发为流应用程序的命令式语言，SDF应用程序，尽管StreamIt研究人员已经开始研究DDF应用程序。它的目标是提供一个高层次的流抽象，以提高程序的生产力。 它也是一种通用的语言，适用于不同的流目标架构，让研究人员也可以在可移植性上工作[4][57][58][59]。调度任务提供了一个粗粒度的调度，分阶段调度[30][29]，参与者是粗粒度的参与者，调度也是粗粒度的。因此，它没有利用所提供的并行性。此外，应用程序图模型（SDF）受到限制：它是使用一组预定义的结构构建的[4][57][58][59]，而不是所有SDF应用程序可以使用它们建模。Lucid Synchrone也是为流媒体应用程序设计的，但它是建立在一个函数语言（OCAML）上的，Lus-3流语言的三个家族。 由程序员决定是否使用语言语法来构建同步应用程序。一个接一个地使用关键字和调度指令所有困难的任务都由用户自己执行，这是不实际的。不要忘记函数式编程本身也不容易。其他语言在[55]中引用。那么，如何以细粒度的方式调度SDF应用程序，以便从可用的机器资源中获益呢？1.3我们的贡献我的工作的目标是集中在流应用程序扩展的问题。在专用流语言的设计和实现中，最重要和最困难的问题之一是回答这个问题：如何以细粒度的方式调度SDF应用程序以利用可用的机器资源？其主要思想是：开发一种细粒度的调度方法：一个执行者是一个没有循环或分支语句的几条指令的块，这对于构建细粒度的调度和利用所提供的并行性是有用的; SDF调度是一个周期序列的无限执行，稳定状态，这种序列调度看起来像嵌套循环调度。因此，我们的调度工作都是基于嵌套循环调度和SDF调度的相似性，这样我们就利用了嵌套循环调度方法的优势，并开发了机器并行性。此外，循环调度和并行可以利用我们提出的技术和算法，因为它们适用于嵌套循环和稳态。本论文的贡献在于：• 一种粗粒度调度算法。 它负责代码和缓冲区大小。• 一种细粒度调度技术INMS。• 思想转变：它打破了演员之间的依赖关系，利用并行性。• Prolog-Epilog合并技术。• 使用重命名合并Prolog-Epilog。• prolog-epilog合并技术的代码生成。1.4论文综述本论文将针对串流应用的排程问题进行研究。它分为两个部分。第一部分介绍基本概念。在第二章中，我们介绍了流应用及其计算模型，特别是SD模型。第三章介绍了循环的基本概念及其变换，4是读者理解我们工作的必要条件。第4章描述了“依赖删除技术”，特别是“重命名”，我们使用它来扩展我们的调度技术，“Prolog-Epilog合并”。在第五章中，我们提出了背包问题，因为“Prolog-Epilog合并”解决方案是基于解决这个问题。论文的第二部分主要介绍了我们的工作。第六章是对问题的概述。列举了我们所关注的应用的不同规范和特点，提出了“不完全嵌套多维移位（INMS）”框架。第7章讨论了模式表移位，这是我们首次尝试为流应用程序提出细粒度调度。在第八章中，我们介绍了“Prolog-epilog合并”调度技术，在第九章中，我们解释了如何生成代码。第十章展示了不同的实验和结果。最后，我们在第11章中总结并建议未来的工作。5第一7第二章溪流理论2.1介绍基于流（数据值的有序序列）的应用正变得越来越重要和广泛，这是因为其高计算要求和其领域的多样性：通信、嵌入式系统、多媒体等。在嵌入式领域，手持计算机、手机和DSP的应用都围绕语音或视频数据流。流抽象对于智能软件路由器、移动电话基站和HDTV编辑控制台等高性能应用也具有重要意义。这些应用程序的一个重要特性是它们由独立的重复操作组成。这是管道的形式。当数据通过流水线传输时，每个阶段可以同时对输入的不同部分进行操作。我们将在本章中看到一些基本的流概念，在2.2节和2.3节中，然后在2.4节中，我们将看看不同的计算模型，最后我们将选择其中一个，适合我们的情况。2.2基本概念流处理：它指的是许多不同系统的活跃研究领域，例如并行系统、反应系统、同步并行算法、信号处理系统和某些类别的实时系统。他们都在处理溪流[55]。Stream：它是一个无限的元素列表，元素为a 0，a 1，a 2，... 从感兴趣的数据A中提取，A可以是一组整数，实数，布尔值或任何其他类型，或流本身[55]。流处理系统基本概念模型：流处理系统（SPS）可以被看作是模块的集合，也称为演员或代理，这取决于系统及其特定模型，并行计算并通过通道进行数据通信。模块可以是将数据传递到系统中的源、执行原子计算的过滤器（或代理）或将数据从8In1M3M1out1In2M4M2out2In3 M5系统[55]。这个基本模型可以用有向图来表示，其中节点是模块，弧是通道。图2.1显示了一个典型的SPS。模块和通道的特性提供了更具体的模型，如Kahn过程网络、Bronchlow网络等。三个主要特点是：(1) 同步或异步参与者：参与者是否同步。它们是以与其他过滤器同步的方式运行，还是不同步地计算？(2) 确定性或非确定性参与者：参与者要么计算函数，要么不计算函数。(3) 单向或双向信道。图2.1.典型SPS2.3流应用使用流抽象的应用程序是多种多样的，但它们有一些共同的特征，将它们识别为这些特点如下：1. 大数据流：这是流应用程序最重要的特性。流是输入和输出数据。它们可能是无限的。这使得流应用程序和科学代码之间有很大的区别，科学代码处理一组数据，具有很大程度的数据重用。2. 独立的流过滤器：Actor是基本的操作单元。如果我们将流计算看作是数据流上的一系列转换图中解释了参与者之间的所有通信Actor不通过共享变量进行通信流应用程序是流图中这些过滤器的组合93. 稳定的计算模式：通常，图结构在计算期间是静态的，或者精确地说，在稳态序列期间是静态的，稳态序列是预定义的周期，从而对滤波器执行进行排序。在同步数据流（SDF）的情况下，图结构总是静态的。4. 流结构的偶然修改：由于某些异步事件，图结构的偶然改变发生这些事件将通过向图中引入一些新的过滤器，省略一些其他过滤器或修改一些数据值（如初始化）来打破常规执行例如，当用户从AM切换到FM时，或者当网络协议在传输期间从蓝牙改变到802.11时，软件无线电重新标识流图的一部分5. 偶尔的流外通信：在实践中，过滤器可以在不频繁和不规则的基础上交换另一种数据、少量的控制信息。例如，更改手机音量或在屏幕上打印错误消息。6. 高性能期望：许多流应用，如嵌入式系统中的流应用，具有实时约束，而其它流应用具有它们自己的适当约束，这取决于流应用的种类。例如，移动环境中的功耗是关键的约束。此外，在内存大小不是很大的一些特定架构中，在内存非常昂贵的一些特定嵌入式架构（缓存或ROM）中，内存需求和代码大小我们感兴趣的是在这篇论文中的流应用程序，有一个静态图，同步数据流（SDF）的应用程序。详细情况见第2.4.3节。2.4的计算模型正如我们上面所说的，通道、参与者和流的特征定义了计算模型。我们在这里不讨论模型，如反应系统模型，其中通道是双向的。我们将只介绍非线性系统模型：卡恩网络及其限制模型。Kahn过程网络是描述混沌系统的自然模型。它用于ADU-SPS（异步确定单向SPS），通常低速系统也是ADU-SPS。介绍了Kahn网络模型及其衍生模型，特别是SDF模型，它们的数学表示以及有界性和终止性问题。2.4.1Kahn过程网络Kahn过程网络（KPN）与基本概念模型一样，是一种计算模型，其中过程通过通道连接形成网络。有趣的10使其成为适合计算的模型的属性是[42]：• 每个进程是顺序程序，其消耗来自其输入的令牌并产生令牌到输出队列。• 渠道是信息交流的唯一途径，是单向的。• 每个进程在试图从空通道读取时被阻塞。它不能检查通道来测试数据的存在• 写入是非阻塞的，但实际上我们对具有有限大小的信道感兴趣• 可以由该模型建模的系统是确定性的。在通道上产生的结果或令牌不依赖于执行顺序[42]。其目标是尽可能在有界通道中执行过程网络程序。流应用程序和科学计算之间的真正区别是：无限流和无限程序执行。 由于每个进程都可以看作是一个图灵机，所以该模型是一个图灵机网络，由于图灵机的终止是一个不可判定的问题，我们不能总是在有限时间内知道这个进程是否终止，因此进程网络程序的终止也是不可判定的。有界缓冲是另一个问题，实际上缓冲区或内存的大小是有限的。 它可以转化为一个终止问题。因此，它是不可判定的。但是缓冲取决于执行顺序，所以如果我们找到一个有效的执行顺序，它不会无限地增加缓冲区大小，那么问题就解决了。虽然这两个属性对于Kahn过程网络程序是不可判定的，但是对于某些受限模型，如SDF，它们是可判定的，我们将在后面看到数学表示：Kahn的过程网络的形式化数学表示是非常简单、有效的，它证明了KPN程序的确定性。生成的令牌仅依赖于程序定义，而不依赖于执行顺序。在这种形式主义中，通道由流表示，过程是将流映射为流的函数，过程网络是这组方程。这些方程的最小不动点是唯一的，它对应于网络中流的历史，这证明了KPN程序的确定性[42]。流：流是有限或无限元素的序列：X =[x 1，x 2，x 3，. ]. X，Y是流，XY表示X是前缀或等于Y，例如X=[0]是Y=[0， 1]的前缀是空流，每个递增链X→=（X1，X2，.. . ）其中X1<$X2<$. 有一个最小上界<$X→= li mi→∞Xi。流程：流程是将输入流映射到输出流的函数。这个函数映射可以用一个方程来描述。例如，图2.2中的过程可以用下面的方程来描述：（Y1，Y 2）=f（X1，X 2，X 3）（2.1）11图2.2. 过程的图形表示函数映射是连续的当且仅当X→，X1f（limi→ ∞Xi）=limi→ ∞f（Xi）（2.2）不动点方程：如前所述，我们可以用一组表示不同函数映射（不同过程）的方程来表示如果函数是完全偏序上的连续映射，则这组方程存在唯一的最小不动点，并且该解对应于通信信道上产生的历史，这证明了KPN程序的确定性图中的KPN2.3可以描述为：• （T1，T2）=g（X）• X=f（Y，Z）• Y=h（T1，0）• Z=h（T2，1）图2.3. 过程网络的图形表示这个系统可以简化为一个方程：（T1，T2）=g（f（h（T1，0），h（T2，1）））由于解对应于信道的 历 史 ， 所 以 它 是 信 道 的 最 小 上 界 的集 合 ， 并 且 如 果 它 是 一 个 终 止 程 序 ， 则 所 有 流 都 是 有 限 的 ，否 则 至 少 有 一 个 流 是 无 限 的 。在我们的例子和归纳：• （T1，T2）0=（λ，λ）• （T1，T2）1=g（f（h（n，0），h（n，1）=（[0]，[1]）12• （T1，T2）2=g（f（h（[0]， 0），h（[1]， 1）=（[0，0]，[1，1]）• （T1，T2）3=g（f（h（[0， 0]， 0），h（[1， 1]， 1）=（[0， 0， 0]，[1， 1，1]）• （T1，T2）j+1= g（f（h（T j，0），h（T j，1）=（[0，0，0，. ]、[1、1、1、. ]）1 2最小不动点解为：T1=[0，0，0. ]，T2=[1，1，1，. ]. Y=h（T1，0）=[0，0，0，...... ]和Z = h（T2，1）=[1，1，1，. ]. X = f（Y，Z）=[0，1，0，1，. ].决定论、终结性和有界性。确定性：如果计算的结果不依赖于执行顺序，则PN是确定的。KPN程序是确定的，因为它们基于这样的事实，即代表通道历史的最小不动点终结性：它与决定论密切相关最小不动点解确定节目中每个通道的流值。如果我们知道流的值，我们就知道每个长度。然后我们就可以知道这个流是否是有限的。KPN程序的完整执行对应于最小不动点。终止KPN程序是所有完整执行具有有限数量的操作（有限流）的程序，而非终止KPN程序是所有完整执行具有无限数量的操作的程序。有界性：尽管每个通道中生成的令牌的长度由程序定义，但通道中未消耗的令牌数量取决于执行顺序。 严格受b约束的通道是这样一个通道，在该通道中，对于任何完整的执行，未消耗的令牌的如果有一个完整的执行，其中该通道中未使用的令牌数不超过b，则通道以b为最后一个定义是一个较弱的条件，但并不总是容易或可能找到这个完整的执行或这个执行顺序。2.4.2数据流网络数据流网络（如KPN）可以用图表示，其中弧表示FIFO通道和节点表示参与者。这两个模型之间的区别在于，Cowllow网络不使用阻塞读取语义。它们有触发规则来代替它。准备好在每个演员输入通道，使执行的演员和演员是原子的。 一个过程是通过无数次地解雇一个演员来形成的，无限的溪流[42]。这里的流有同样的意思。它由令牌表示，它可以是有限的还是无限的与流程（从流到流的函数映射）相反，参与者是将输入标记映射到输出标记的函数。它们指定每个输入通道中应该有多少令牌可供参与者触发。当它触发时，它会消耗一些输入令牌并产生一些输出令牌。触发规则：一个参与者可以有一个或多个触发规则：R= R→1，R→2，...，R→N（2.3）