Handling irregular ILP within conventional VLIW schedulers using artificial resource constraints
Handling irregular ILP within conventional VLIW schedulers using artificial resource constraints
复制标题
使用人工资源约束在传统 VLIW 调度程序中处理不规则 ILP
DOI：
--
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
S. Malik
中科院分区：
文献类型：
--
作者：
Subramanian Rajagopalan;Manish Vachharajani;S. Malik
指令集架构师和编译器编写者通常对指令集的设计有不同的要求。架构师受潜在的微架构复杂性和可能的代码大小的考虑所驱动；而编译器编写者更喜欢适合常规编译器算法的干净的正交指令集。在通用计算中，RISC和CISC体系结构风格之间产生了一个令人不安的界限，这使得这场斗争趋于稳定。然而，在嵌入式计算世界中，使用特定领域的处理器（例如数字信号处理器（dsp）），这种斗争仍在继续。它导致了非常不规则的体系结构，这些体系结构很难编译，需要专门的优化技术。嵌入式处理中越来越多的趋势是使用VLIW （Very Long Instruction Word）处理器，它需要eÆcient编译器的支持，这些编译器可以在编译时提取指令级并行性（ILP）。然而，这些机器的ISA（指令集体系结构）仍然受到嵌入式处理约束（小代码大小，更简单的硬件）的驱动，因此所有可用的ILP可能并不总是在ISA中被清晰地反映出来。这给编译器带来了一个严重的问题，因为传统的VLIW编译器直接使用物理资源来确定哪些可以并行调度，哪些不能并行调度。利用在VLIW编译中完成的大量工作显然是可取的，然而，许多嵌入式isa使这成为不可能。这迫使开发专门的优化技术为这些处理器一个不受欢迎的研究报告分配；或者更糟的是，用汇编语言编码是一种不受欢迎的工程精力分配。在本文中，我们展示了ISA中的违规行为是如何与经典VLIW编译器的常规资源要求相匹配的，通过生成一组许可，可以免费为个人或课堂使用制作全部或部分作品的数字或硬拷贝，前提是副本不是为了盈利或商业利益而制作或分发的，并且副本在第一页上带有此通知和完整的引用。以其他方式复制，重新发布，在服务器上发布或重新分发到列表，需要事先获得特定许可和/或付费。案例00,2000年11月17-19日，加州圣何塞。版权2000 ACM 1-58113-338-3/00/0011 .$5.00的人工资源基于ISA规范。这些资源可能不对应于任何实际的物理资源，但创建这些资源是为了向VLIW编译器（实际上是调度器）提供一个统一的规范，说明什么可以并行执行，什么不能并行执行。这使得VLIW编译中的大量工作（和软件）可以直接用于这些不规则的处理器。人工资源是通过求解ISA规范生成的组合图标注问题生成的。我们证明了这个问题等价于用最小数量的团（完全子图）覆盖给定图中的所有边的问题。这是一个已知的np完全问题，因此我们可以利用已经为此开发的启发式方法。此外，在这个问题和研究得很好的图着色问题之间有一个直接的转换。这种转换使我们能够在图着色问题领域中使用大量的工作（和软件）。最后，我们演示了这些思想在两个专有dsp（富士通的Elixir和Hiperion dsp）的编译器开发中的应用。在过去，编译器是使用高度专业化的优化算法为这些处理器开发的。这种方法现在被使用使用现有VLIW编译器（IMPACT编译器）生成人工资源的建议技术所取代。我们相信，这些思想的发展为不规则嵌入式VLIW dsp使用经典VLIW编译方法打开了大门，并且是嵌入式处理软件工具开发的重要一步。
Instruction set architects and compiler writers often have con icting requirements on the design of the instruction set. The architects are driven by potential micro-architecture complexity and possibly by code size considerations; while the compiler writers prefer clean orthogonal instruction sets amenable to regular compiler algorithms. This struggle has stabilized with a resulting uneasy boundary between the RISC and CISC architectural styles in general purpose computing. However, in the embedded computing world, with domain speci c processors (e.g. Digital Signal Processors (DSPs)), this struggle continues. It has resulted in very irregular architectures that are very hard to compile for and that need specialized optimization techniques. An increasing trend in embedded processing is to use VLIW (Very Long Instruction Word) processors, which need to be supported by eÆcient compilers that can extract the instruction level parallelism (ILP) at compile time. However, the ISAs (Instruction Set Architectures) for these machines are still driven by embedded processing constraints (small code size, simpler hardware), and consequently all available ILP may not always be cleanly re ected in the ISA. This presents a signi cant problem for the compiler, since tradition VLIW compilers work directly with physical resources to determine what can and cannot be scheduled in parallel. It is obviously desirable to leverage the large body of work done in VLIW compilation however, many embedded ISAs make this impossible. This forces the development of specialized optimization techniques for these processors an undesirable allocation of research e ort; or even worse, coding in assembly language an undesirable allocation of engineering e ort. In this paper we show how the irregularities in the ISA can actually be matched with the regular resource based requirements of classic VLIW compilers by generating a set Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. CASES’00, November 17-19, 2000, San Jose, California. Copyright 2000 ACM 1-58113-338-3/00/0011 ..$5.00 of arti cial resources based on the ISA speci cation. These resources may not correspond to any real physical resources, but are created to provide a uniform speci cation to the VLIW compiler (actually the scheduler) as to what can and cannot be done in parallel. This enables the use of the large body of work (and software) in VLIW compilation to be directly used for these irregular processors. The arti cial resources are generated by solving a combinatorial graph labeling problem which is generated from the ISA speci cation. We show that this problem is equivalent to the problem of covering all the edges in a given graph using the minimum number of cliques (complete subgraphs). This is a known NP-complete problem thus, we can leverage the heuristics already developed for this. In addition, there is a direct transformation between this problem and the well studied graph coloring problem. This transformation enables us to use the large body of work (and software) in the graph coloring problem domain. Finally, we demonstrate the application of these ideas in the development of compilers for two proprietary DSPs the Elixir and the Hiperion DSPs from Fujitsu. In the past, compilers were developed for these processors using highly specialized optimization algorithms. This is now being replaced by using the proposed technique of generating arti cial resources with an existing VLIW compiler (the IMPACT compiler). We believe that the development of these ideas opens the door for using classic VLIW compilation methods for irregular embedded VLIW DSPs and is a signi cant step forward in the development of software tools for embedded processing.