摘要
用激进的称为轨迹调度的技术编译普通的科学应用程序，我们为并行机器生成代码，其运行这些程序将会比等价的顺序机器来得快 – 我们期望是 10 到 30 倍快。
轨迹调度为称为超长指令字架构的机器生成代码。在超长指令字机器中，许多静态调度，紧密耦合，和细粒度的操作都是在单指令流里并行执行的。VLIW 是一些当前架构的并行扩展。
这些现存的架构从未突破基本的性能屏障。它们能从并行中获得的加速比从没有超过 2 到 3 倍。并不是说我们不能建造这种更高并行类型的机器；而是在轨迹调度之前，我们不知道如何为为它们生成代码。轨迹调度会在普通代码中发现足够多的并行性，从而可以证明考虑高并行度的 VLIW 是合理的。
在耶鲁，我们正在建造一个这种类型的机器。我们的机器，ELI-512，有超过 500 位的水平指令字，每个周期会执行 10 到 30 条 RISC 级别的操作 [Patterson 82]。ELI 表示极大长字指令；512 表示我们希望达成的指令字大小。（当前的设计已经有 1200 位指令字了。）
一旦清楚了我们可以为 VLIW 编译代码，一些新的问题就会出现，本文会给出这些问题的答案。我们如何在不使得机器太大的情况下，在每个周期里放入足够多的测试？我们如何在不使得机器太慢的情况下，在每个周期里放入足够多的内存依赖？
什么是 VLIW？
每个人都想并行地使用廉价的硬件来加速计算。一种显而易见的方式是使用你最喜欢的精简指令集计算机，让它可以由一个超长指令字控制下在每个周期里执行 10 到 30 个 RISC 级的操作。（事实上，称它为 VLIW。）一个 VLIW 类似于许多并行的水平微码。
更正式的说，VLIW 架构由如下的属性：
一个中央控制单元每个周期发射一条单一超长指令。
每条长指令由许多紧耦合的独立操作组成。
每个操作需要一个小的，静态可预测的周期数来执行。
操作可以并行化。这些属性区分了 VLIWs 和多进程机器（大型异步任务），数据流机器（没有简单的控制流，且没有紧耦合）。VLIWs 没有矢量处理器或者真阵列处理器所需的规则性。
已经构建了许多类似的机器了，但是它们所能提供的并行度的上限都非常的低。除了水平微码引擎，这些机器包括了 CDC 6000 和它的许多后继，如 CRAY-1 的标量部分；IBM Stretch 和 360/91；以及斯坦福的 MIPS [Hennessy 82]。不出意外的，它们都没有提供太多的并行度。实验和经验表明在基本块里有效的并行只能加速 2 到 3 倍。（一个基本块代码除了开头不会被跳入，除了结尾不会被跳出。）没有人知道如何在条件跳转之外找到并行性，而且显然也没有人在寻找。显然似乎不能把来自不同基本块的操作放入到同条指令中。没有办法提前告知控制流。你是怎么知道你是否希望让它们一起执行的？
有时候，人们会为了特殊的目的创建更高并行的 VLIW 机器。但都是硬编码的。硬编码长指令字是个可怕的任务，任何写过水平微编码的人都会这么告诉你的。代码的排列都是客制化的，几乎是无法重复。特殊处理器可以不用手写编码，因为它们只需要很少的代码量。浮点系统 AP-120b 在少数特定目的的应用上可以提供 5 到 6 倍的加速，因为这些代码是花费了极大代价手写的。但是这些代码不具有代表性，大部分的用户只有标准的 2 或者 3 – 且需要经过大量的工作，然后只能在小程序上。
我们正在谈论的是一个数量级的并行度；显然我们可以忘掉硬编码。但是并行度要来自哪呢？
不是来自基本块。实验表明基本块里的并行度是有限的 [Tjaden 70，Foster 72]。但一种全新的全局压缩技术称为轨迹调度，可以跨基本块边界找到大的并行度。轨迹调度在一些代码上无法使用，但是它适用于大多数通常的科学代码。它的工作方式使得构建生成高度并行代码的编译器成为可能。在考虑轨迹调度的情况下进行的实验验证了在基本块外存在了大量的并行性 [Nicolau 81]。Nicolau81 在不同的背景下重复了更早的实验，发现了相同的并行性，但反驳了它；当时轨迹调度还是未知的，并且需要大量的硬件来利用并行性 [Riseman 72]。
为什么不用向量机？
向量机似乎可以提供的并行度比当前 VLIWs 提供的 2 到 3 倍并行度更高。虽然向量机也由它们的应用场景，但是我们认为它们在通用科学计算的代码上没有太多成功的机会。它们非常难以编程，且它们只能加速内循环，其余部分就不行了。
为了向量机的编程，编译器或者手写编码者需要让代码中的数据结构几乎完全符合硬件内置的规则结构。首先就很难做到，然后也很难改变。只要稍加调整，低级别的代码就必须由一位非常聪明和专业的程序员重写，其了解硬件并且知道应用领域的一些细节。经常重写不成功，需要回去修改板子。许多人希望通过一个非常智能的编译器可以从普通的标量代码生成高向量化的代码 [Padua 80]。我们认为只有少数的程序经过向量化可以产生足够的并行度。
只能在内循环里向量化；剩余的代码得不到任何的加速。即使有代码的 90% 都在内循环里，剩下的 10% 运行速度和顺序机器上是一样的。即使你可以使得 90% 无耗时地跑完，其它的 10% 也会限制加速比到达 10 。
轨迹调度
我们构建的 VLIW 编译器使用了最近的全局压缩技术，称为轨迹调度 [Fisher 81]。这个技术最初是为了微码压缩开发的，压缩成为了从某些顺序源码生成超长指令字的一个步骤。
水平微码在并行性方面类似于 VLIW 架构。不同之处是具有特殊的操作和较少的并行硬件。除了轨迹调度，其它技术也为微码压缩开发过了 [Tokoro 78，Dasgupta 79，Jacobs 82]。它们与轨迹调度不同的是，它们使用已经压缩好的基本块，搜索基本块间单个代码移动获得的并行性。这可能使用于水平微码，但它可能不适合于 VLIWs。VLIWs 比起水平微码有更高的并行度，这些技术需要更昂贵的搜索才能利用起来。
轨迹调度将一块一块的代码压缩替换成长代码流的压缩，可能有上千条指令的长度。这里有个小技巧：你可以做一点预处理。然后你可以假装它们是基本块一样，调度长代码流。然后你可以去除假装成基本块的负面影响。你从中可以获得的能力是，可以在全流中使用已知的非常有效的调度技术。这些技术之前似乎仅受限在基本块中。
为了简单说明，我们从一个无回边的没有循环的代码开始。给定一个可归约的图，我们可以找到无环的最内侧的代码[Aho77]。图的（a）部分给出了一个小的没有回边的流图。动态信息 – 跳转预测 – 在编译期间被用来选择最高执行可能性的流。这些流我们称为”轨迹“。我们从最频繁执行的代码中选出我们的第一条流。在图的（b）部分，已经从流图中选出了一条轨迹。
预处理可以防止调度器在块间做一些绝对非法的代码移动，它们可能会破坏轨迹外的存活变量的值。通过往为轨迹构建的数据优先级图里添加新的、特殊的边可以完成这个。新边会画在测试操作和可能会破坏变量的操作之间，测试操作指的是会条件跳转到变量存活的地方的操作。这些被添加到数据优先级图中的边和其它所有的边看起来都是一样的。调度器，没有更明智的了，则被允许表现得像是在单个基本块里调度一样。它不需要关注任何得块边界。
在调度完成后，调度器会做许多可能不正确的保留从流到外面世界的跳转（或者往回重新加入）的代码移动。所以需要一个后期处理，在流退出和入口之间插入新的代码来恢复流之外的正确的机器状态。没有这个能力，有效的并行度会因为需要保留跳转边界而被过度限制。在图的（c）部分，轨迹会被独立出来，在（d）部分，新的不能压缩的代码出现在代码拆分和重新加入的地方。
然后我们寻找我们的第二条轨迹。我们再一次观察最频繁执行的代码，其现在不止包含第一条轨迹之后的源码，也包含所有的我们为恢复拆分和重新加入的任何新的代码。我们用相同的方式压缩第二条轨迹，可能会产生恢复代码。（因此在我们的实际实现中，我们对只生成少量的恢复代码感到惊喜。）最终，这个过程以这个方式运行输出极低执行概率的代码，然后如果需要，可以使用更普通的压缩方法，以免产生新的代码。
轨迹调度为循环提供了一种自然的解决方案。手动编码者使用软流水来增加并行度，重写一个循环，以便同时进行几个连续的循环。在任意的循环中，轨迹调度都可以平凡地扩展来做软流水。我们简单地将循环展开多次。展开的循环是一个流，所有的中间循环测试现在是条件跳转，流可以像上面那样被压缩。
虽然，这种处理循环的方法可能比理论上所需的空间效率低一些，但它可以处理每个旧循环迭代里的任意控制流，这是尝试编译真实代码的主要优势。上图，这通常与之前的类似，展示了如何处理循环。
BULLDOG，一个轨迹调度编译器
我们已经在 DEC-2060 上的已编译 Maclisp 中实现了一个轨迹调度的编译器。我们称它为 Bulldog 以表明它的坚韧（还有防止人们认为它是由哈佛写的）。Bulldog 有 5 个主要的模块，如下图所示。
我们的第一个代码生成器是给理想化的 VLIW 机器的，这种机器每个周期都只执行一个 RISC-级别的操作（不太理想化），且每个周期进行无限制的内存访问（完全过于理想化）。我们使用这个代码生成器来协助调试编译器的其它模块，以及测量有效的并行性。每条指令平均的打包操作数是一个虚假的加速比测量值。相反，我们将代码执行的并行周期数除以未编译代码执行的顺序周期数来获得加速比。
通过与理想的代码对比，真实的 ELI 代码将会包含许多额外的小操作。这是否意味着相同的加速，或者更少，或者更多，还有待讨论。这些附带操作可能会使顺序代码的速度比并行代码的速度慢很多，从而使并行导致的加速更多。只有时间会给出答案。
我们当前使用的前端生成了我们的 RISC-级别的中间码，N-address code 或 NADDR。输入是一个本地 Lisp-语法糖的 FORTRAN，C，Pascal 级别的语言称为 Tiny-Lisp。这是我们快速构建的东西，给了我们最大的灵活性。我们很容易为它编写示例代码，我们不需要写解析器，我们可以很容易地摆弄编译器，这已经被证明是很有用的。一个 FORTRAN‘77 子集到 NADDR 编译器已经写好了，正在调试中，在这之后我们将会考虑其它语言。我们 RISC-级别的 NADDR 很容易生成代码，并且可以在上面应用标准的编译器优化。
我们现在有两个代码生成器正在开发中。一个全的 ELI-512 生成器已经很久了 – 它的一个子集现在被连接到了轨迹选择器和代码修正上了。我们也在开发一个 FPS-164 代码生成器。我们也在开发 FPS-164 代码生成器。FPS-164 是浮点系统 AP-120b 的后继，可能是有史以来将水平微代码作为唯一语言的机器中销量最大的。FPS-164 有个 FORTRAN 的编译器，但是以我们的经验而言，它只能使用了这台机器上少量的可用并行性。能与手写编码比较的编译器可能会真正地改变该机器的潜在可用性（难以手写编码的），且会证明轨迹调度的通用性。
BULLDOG 上的内存反混淆
轨迹调度中大量的代码移动是必须的，为了将来自程序广泛分散位置的操作填充到指令中。代码移动被数据优先级严格限制着。例如，假设我们的程序有如下的步骤：
1 | (1) Z := A + X |
我们的代码移动不会让（2）比（1）早调度。因此，轨迹调度在调度之前构建了一个数据优先边。
但当 A 是数组依赖的时候会发生什么呢？
1 | (1) Z := A[expr1] + X |
（2）能否早于（1）是不确定的。如果 expr1 可以保证不同于 expr2，则代码移动是合法的；否则是不合法的。回答这个问题的是反别名内存引用问题。使用其它间接形式，如追逐指针，则反别名没有半点的成功希望。但是如果间接引用是在数组元素上，则我们通常可以在编译时识别出它们的不同。科学代码的内循环中的间接引用几乎都是到数组元素的。
Bulldog 编译器中实现的系统尝试去解决相等式 expr1 = expr2。它使用到达定值[Aho 77] 来缩小表达式中每个变量的范围。我们可以假设变量是整形的，然后使用一个丢番图方程求解器来确定它们是否相同。范围分析可以是相当复杂的。在已经实现的系统里，定值被尽可能地传播，并按照可能的最简单的变量来求解方程。我们还没有使用分支条件来缩小可以取到的值的范围，但后续会使用上。
反别名已经实现了并且可以正常地工作（如果不是很快的话）。不幸地是，虽然它只缺少少数能力 – 非常少，但还是严重减慢了它的速度。在这种情况下，定理恒成立：链表的强度取决于它最弱的部分。到目前为止，我们所研究的实际代码的加速比在 5 到 10 之间。很好，但不是我们想要的。手动检查这个结果，可以清楚地发现，当提供了缺失的零件，则速度会大量地提升。
运行轨迹调度的机器
ELI-512 有 16 个集群，每个集群都包含一个 ALU 和一些内存。集群以环形的方式排列，每个都与其最相邻的通信，一些还会与更远的集群通信。（ELI 和它集群的草图在下一页。）
在每个指令周期里，ELI 使用它 500+ 位长度的指令字来发起下面的操作：
16 个 ALU 操作。8 个 32 位整形操作，8 个会使用带有多种特性的 64 位 ALU 来完成功能，包括流水化的浮点计算。
8 流水化的内存引用 – 稍后会详细介绍。
32 个寄存器访问。
非常多的数据移动，包括为上面的操作进行操作数选择。
一个基于几个独立测试的多路条件跳转 – 稍后也会详细介绍。（这么多事情同时发生，只有疯子才会想手动编写 ELI 的代码。）
为了执行这些操作，ELI 有 8 个 M-clusters 和 8 个 F-clusters。每个 M-cluster 里有：
一个局部内存模块（迄今为止未确定大小的）。
一个整型 ALU ，其可能大部分时间在做地址计算。确切的功能可能每个集群都有差异，它不会固定的，直到我们使用实际的代码调优架构之前。
一个多口的整型寄存器库。
一个有限的集群交叉开关，少于 8 个参与者。
一些参与者是非集群总线上的。一些交叉开关的连接无法进行。
每个 F-cluster 里有：
一个浮点的 ALU。集群间的 ALU 的特性都是不同的，之前我们调优架构前都不会固定。
一个多口的浮点寄存器库。
一个有限的集群交叉开关，少于 8 个参与者。
一些参与者是非集群总线上的。一些交叉开关的连接无法进行。
不要被结构中偶然的规律所欺骗。它们在这里只是为了让硬件更容易构建。编译器不知道它们，且它也不会尝试去使用它们。当我们开始用编译器运行科学代码时，我们必定会进一步调优这个架构。我们将会尽可能多地移除我们能移除的总线，然后很多有规律的东西都可能消失了。
当前的计划是用 100K ECK 逻辑构建 ELI 原型机，尽管我们可能会选择 Shottkey TTL。
问题
在这之前，没有人曾经想过要构建一个 512-位宽的指令字机器。当我们一开始构思它的时候，我们发现了有两个大问题。如何在每条指令里放入足够多的测试而不会使得机器太大？如何在指令里放入足够多的内存依赖而不会使得机器太慢？
将 VLIW 与矢量机进行比较，来说明需要解决的问题。VLIW 将细粒度的，紧耦合，但逻辑无关的操作放入单条指令中。矢量机对向量的元素同时做许多细粒度，紧耦合，逻辑相关的操作。矢量机可以在测试间做许多并行操作；VLIW 则不行。矢量机可以构建到整个数组或数组切片的内存依赖；VLIW 则不行。当然，我们也讨论过矢量机在通用科学代码上的失败还有其它原因。我们如何排除它们的恶习而获得它们好的一面呢？
VLIWs 需要巧妙的跳跃机制
短的基本块意味着缺乏局部并行性。它们还意味着操作和测试的比率很低。如果我们要在每个周期中打包大量的操作，我们最好准备好每个周期都进行一次以上的测试。注意到这对于当今的静态调度操作机器并不是问题，其不能再每个指令中打包足够多的操作来达成这个比率。
很清楚地是，我们需要一个机制，可以跳转到几个测试的结果声明的几个地方中的一个。这不是任意的单纯的多路跳转机制可以做到的。许多水平的微编码机器允许在每条微指令中指定几个测试。但是做这些的机制太不灵活了，无法在这里发挥重要的作用。他们不允许多个独立测试，而是提供可以同时完成的硬连接选择的测试。一些机器允许一些比特位的特定集合来改变下一个地址计算，允许一个 $2^n$ 路跳转。例如，这是用于实现一个操作码的解码，或者一些其它硬件场景的语句。
另一个不能满足我们的方案是 VAX 11/780 微编码中找到的 [Patterson 79]。那里，测试的几个固定集合中的任意一个都可以在给定指令中指定。一个掩码可以用于选出那些测试中的任意子集，它们与跳转指令进行逻辑与运算。不幸地是，两个给定的条件测试出现在指令表中的相同集合的可能性是非常低的。在压缩的过程中，非常不可能在一条指令中准确地放入想要的测试，甚至是大部分的子集都不行。相反，组合预先硬连接的。有人会猜测，这个组合是表示对一些给定的应用程序的方便分组，在 VAX 的场景中，大概是 VAX 的指令集的仿真器。
架构可能提供的最方便的支持是一个基于测试 n 个独立条件的结果的 $2^n$ 路跳转。这并不像听起来那么不切实际；在开发轨迹调度的过程中考虑了这种机制 [Fisher 80]，并且看起来是很使用的。但是，事实证明，它比我们需要的更通用。
在我们实际实现了轨迹调度后，出现了一个令人意外的事实：轨迹调度需要的是一个机制，作为 n 个独立测试的结果可以跳转到 n+1 位置中的任意一个。测试必须是来自机器上有效的测试的指令表 n 的任意组合。
跳转的工作方式与 LISP 中的 COND 语句的工作方式相同。为了简单，我们假定测试 FAILing 意味着失败然后想要待在轨迹中，然后 SUCCEEDing 意味着成功，然后想要跳出轨迹。一个表示多路跳转的语句可能会出现如下所示：
1 | (COND (test1 label1) |
如果第一个测试，test1， FAIL，它想要待在轨迹中，然后做第二个测试，test2。如果 FAIL，则它也想要待在轨迹中。如果测试，testk，SUCCEEDs，则它想要跳出轨迹到 labelk；在 testk 之后不会在有轨迹内的测试了。如果所有的测试 FAIL，我们最终到达了指令中的最后一个地址并且顺序执行下去。
我们发现 n+1 个目标标签就足够了；不需要 $2^n$ 个。我们按出现在轨迹中的顺序排序一条指令中的所有测试。然后当一个测试 SUCCEEDs 时，我们很高兴我们已经执行了源码顺序中较早出现的测试，但我们不太关心后面出现的测试，因为此时我们已经离开了轨迹。
构建一个 n+1 路跳转机制并不困难。如图所示，我们所需要的是一个优先级编码器和一个 n 测试多路复用器。宽指令字通过 n 个 j-位（j 是测试次数）的域选出 n 个测试中的每一个。n 个测试（按顺序）中想要跳出轨迹的第一个实际是选择了下一条指令。
但是我们实际是如何产生下一个地址的呢？我们可以在每条指令中完全放置 n+1 个下一条指令地址的候选。但即使是在 使用如此多指令位的 ELI 上，这样做也似乎有点过分了。使用选择位作为下一个地址的一部分（就像上面提到的受限的多路跳转）的想法似乎才是对的，如果我们可以战胜一个小的打包问题。
例如，如果 n == 3，且如果当前指令有下一条指令地址域，比如说，00000011，则我们有如下的情况：
在这个方案中，我们不会自增程序计数器来获得下一条指令。但是如果特定硬件实现的速度有优势的话，则可以使用它。
如果我们在一个周期里打包的测试少于 n 会发生什么呢？根据上面的例子，在 n == 3 时，看起来对于每组目标地址，我们都需要花费四个程序内存位置。但如果我们有直连的代码，或者想要在某些周期里只做一到两个测试（我们肯定会的），会发生什么呢？我们不得不浪费没用到的 slots 吗？如果我们包含一个测试总是 SUCCEEDs，另一个总是 FAILs 的，则我们可以避免浪费 slots。有这些测试，我们可以让两条都要打包一个测试的指令共享一个地址片，或者我们也可以打包一条会做两个测试的指令，和一条不做测试的指令。例如，取两条指令，INSTR1，其想要做 TEST1，和 INSTR2，其想要做 TEST2。我们可以安排让它们都跳转到一个标签上，这个标签在地址切片 00000011里（因此同时都有 00000011 作为它们的下一个地址域）如下：
在 INSTR1 之后，我们要么跳转到 00 00000011，要么到 01 00000011。作为一个结果，INSTR1 的下一个地址域是 00000011，然后这个测试域填充如下。
在 INSTR2 之后，我们要么跳转到 10 00000011，要么到 11 00000011。所以它看起来是：
因为我们没有自增的程序计数器，且可以随意重新安排地址，所以这些分配可以在 postpass 程序中直接完成。代码重新加入时可能会浪费一点空间，但不会太多。
我们之前在 $2^n$ 路跳转上的工作也可以应用到 n+1 路跳转上，包含了这些想法的一个更完整的解释 [Fisher 80]。
ELI-512 上的跳转机制
ELI-512 上有一个类似上面描述的 n+1 路跳转机制。在我们调优机器设计和编译器的时间里，我们会确定多少的测试是合适的；它似乎可能是 3，4，或者 5。我们正在考虑两种指令取指机制。
延迟分支是一个老的微编码指令预取技巧，其在这里运行的特别好[Gross 82，Patterson 82]。在延迟分支机制中，指令 M+k 的地址是由指令 M 中的测试结果决定的。无论测试是成功还是失败，M 和 M+k 之间的 k 条指令都会完成的。使用轨迹调度，我们知道最有可能跳转的是哪一路；所以我们可以用可能会在执行流中的指令填充这个区间。虽然当前编译器理所应当地处理了延迟跳转，但是我们没有测量出它们是否使得代码变慢了，以及变慢了多少。
当前选择的是一次取一片。我们有 n+1 个指令内存库，可能会预取所有的下一个条件码，一旦选择了某条指令，就使用它的下一条指令地址。然后，当测试稳定下来后，来自优先级编码器的比特位可以从 n+1 个选择中复用。ELI 上的大字可能会让这个技术变难。
VLIW 编译器必须预测内存库
每个周期中包含了如此多的操作，其中许多操作必须是内存引用。但（与任意的并行处理系统一样）我们无法简单地在每个周期中发射许多的引用；有两件事会出错。通过某个全局仲裁系统获得地址需要花费很长的时间。然后库冲突的可能性会逼近 1，需要我们冻结整个系统更多的周期。
但现在我们可以依赖（和之前一样）于智能编译器和静态代码的组合了。我们要求我们的编译器关注在代码上，尝试去预测引用了哪个库。当我们能预测库的时候，我们可以使用一个专用的地址寄存器直接去应用它。为了每个周期可以做几个引用，我们单独地访问每个内存库地址寄存器。因为地址路径将不会交叉，所以仲裁不是必须的。
当我们询问编译器引用会在哪个库的时候，得到答案的机会有多大？在我们期望能运行在 VLIW 上的静态代码上，效果是非常好的。标量总是知道位置的。数组呢？相同的做反别名的系统可以尝试去引用是在哪个库里。你可以想起，循环展开后可以增加并行度。事实上，它是一个做了展开的反别名系统，因为它知道哪个是归纳变量，哪个不是。（它重命名了在连续展开中出现的非归纳变量，避免不必要的数据优先级。）通过展开，则每次迭代数组下标通过库的数量乘积来增加，反别名系统经常让它变得可以预测库。
不能预测的引用呢？两类不能预测的引用会混淆这个方案。
首先，我们可能没有机会去预测引用的库地址。例如，我们可能会追着一个指针，然后需要去访问整个内存地址空间。但这样的访问假定是很少数的；我们所需要做的仅是确定他们不会过分地减慢局部可预测访问的速度。我们的方法是构建一个影子内存方法系统，不管怎样它都可以从任意的库获得地址，并返回这些地址上的值。这要求我们的内存库是双端口的，以及有锁定的能力。硬件资源的分配应该有利于可预测访问；不可预测访问可以做得比较慢。可预测访问应该在库冲突的场景中有个优先级；当不可预测引用没有完成的期间里，我们可以让机器冻住。如果有太多这样的引用，则机器的性能会变得很糟糕。而且这种情况下，保守的数据优先级无论如何都会破坏大量并行的机会。
第二个问题是，即使我们有数组且适当地展开了循环，我们也可能无法预测一个下标的库位置。例如，这个下标的值可能依赖于带有数据依赖起始点的循环下标值。未知的起始值不会破坏我们在循环里做预测引用的机会。我们不得不做的是要求编译器建立一种预循环。这种预循环类似于原始循环，但它会在未知变量到达某个值的时候退出，这个值是存储体数量的模值。虽然它本身可以展开和压缩，但是预循环也不得不在不可预测的引用上使用慢速的不可预测地址系统。但是它将会执行一些较短的循环周期，而不是非常长的展开循环。给定的 B 存储体的情况在下一页说明。
ELI-512 的内存访问
ELI 当前的设计依赖于上面描述的系统：存储预测，局部搜索优先级，和预循环。8 个 M-clusters 中的每个都有一个内存访问端口，在存储体已知的时候使用。每个 M-cluster 的每个周期我们都会启动一个流水化的访问（其可能需要我们能够区分至少 16 个物理存储库，每个模块 2 个，取决于内存的设计）。这可能会给我们一个带宽大约是 400 Mbytes/sec 的潜在数据内存访问，如果我们的周期时间是在 150 ns 区间里。为了实现预循环，我们会有地址模存储库的测试。
此外，ELI 将会有两个全局的地址内存访问口。当它们准备好的时候，全局预取的结果放入一个局部的寄存器存储体中。当引用数据的时候，如果数据不在寄存器中，则系统会冻结，然后所有等待的全局引用在有机会的时候就会执行完。我们期望事务的这种状态是比较罕见的。
我们已完成的和未做的
本文提供了使用超长指令字架构来加快科学代码的问题的解决方案。这些问题包括高并行代码的生成，每个周期多测试，每个周期多内存引用。
Bulldog 编译器和真实代码上完成的实验已经证明了典型的科学代码存在着巨大的并行度。基于存在这种并行性，让 VLIW 机器是可取得，我们正在构建一台：ELI-512，一个并行度高的处理器，有 500+ 位指令字。我们期望 ELI 比等价的顺序机器多加速代码 10 ~ 30 倍。在我们构建之前，我们会为 ELI 生成好的代码。我们也为 FPS-164 编写了一个编译器，一个较少的并行但结构类似的机器。
我们的代码生成器使用轨迹调度来定位和指出代码中源自远处位置的并行性。n+1 路 跳转机制让它能在每个周期里调度足够多的测试而不会让机器太大。存储体预测，局部搜素优秀，和预循环让它能够在一个周期里调度足够多的内存引用，而不会让机器太慢。
部分是为了缩小项目的范围，部分是因为VLIW的性质，我们在各个方面都进行了限制。ELI 会是一个附加处理器 – 没有 I/O，没有编译器，没有 ELI 模拟器，没有用户便利设施。相反，我们会选择一个理智的主机。ELI 不会了高效的上下文切换或过程调用进行优化。ELI 会运行计算边界的科学代码。很难将 VLIW 的并行性扩展到过程调用之外；如果我们想要的话，我们可以在线扩展这类调用。任何 VLIW 架构都在动态代码上表现不佳的，包括大部分的系统，通用目的的代码和一些科学代码。我们满足于 ELI 在大部分科学代码都表现出色的。
致谢
略。