下载文档原格式
编译原理面试题
以下是一些可能的编译原理面试题：
解释一下编译器和解释器有什么区别？
解释一下词法和语法分析的概念。
什么是上下文无关文法？
解释一下递归下降解析器和预测分析树算法。
什么是语义分析？
解释一下类型检查和类型推导的概念。
什么是静态类型检查和动态类型检查？
解释一下代码优化是什么？
什么是中间代码生成？
解释一下指令选择和指令调度。
什么是循环展开和内嵌展开？
解释一下尾递归优化。
什么是垃圾回收？
解释一下增量编译和增量编译器的概念。
什么是并行编译和并行编译器？
请解释一下编译器的构建过程。
请解释一下编译器的错误处理机制。
如何实现跨平台编译器？
请解释一下编译器优化是什么？
请解释一下编译器如何处理多线程编程中的并发问题？。
python 递归效率摘要：1.Python 递归效率的影响因素2.递归算法的优化方法3.尾递归的优化4.避免递归的方法5.结论正文：Python 递归效率的影响因素：在Python 中，递归是一种非常常见的编程方法，但是递归的效率往往会受到一些因素的影响。
首先，递归的效率会受到函数调用次数的影响。
当递归深度增加时，函数调用次数会呈指数级增长，这会导致程序运行速度显著降低。
其次，递归还会受到函数参数传递和返回的开销影响。
每次递归调用都需要将函数的局部变量和返回值传递给子函数，并在递归结束时将子函数的返回值返回给父函数，这些操作都会带来额外的时间开销。
递归算法的优化方法：为了提高递归算法的效率，可以采用以下几种方法进行优化。
首先，可以通过memoization 技术来存储已经计算过的结果，避免重复计算。
其次，可以使用尾递归优化算法。
尾递归是指在递归调用中，最后一个操作是返回值，这种递归可以由编译器自动优化，从而提高程序的运行效率。
此外，还可以通过将递归算法转换为迭代算法来提高效率。
尾递归的优化：尾递归是一种高效的递归方式，可以由编译器自动优化。
尾递归的优化原理是将递归调用压入栈中，从而减少函数调用的开销。
尾递归的优化能够显著提高程序的运行效率，特别是在递归深度较大的情况下。
避免递归的方法：在某些情况下，递归算法可能并不是最优解，可以尝试使用其他算法来避免递归。
例如，可以使用迭代算法来替代递归算法，迭代算法通常具有较低的时间复杂度和较高的执行效率。
另外，还可以使用分治算法，将大问题分解为小问题，然后逐个解决小问题，最后将小问题的解合并为大问题的解。
结论：递归是Python 编程中常见的一种方法，但是递归的效率受到多种因素影响。
为了提高递归算法的效率，可以采用尾递归优化、memoization 技术等方法。
并行计算的算法设计与优化在计算机科学领域，随着计算机性能的提升和大规模数据处理的需求增加，并行计算逐渐成为一种重要的解决方案。
并行计算旨在通过同时执行多个计算任务来提高计算效率和性能。
本文将探讨并行计算的算法设计与优化。
一、并行计算的基本概念并行计算指的是将计算任务分解为多个独立的子任务，并在多个处理单元上同时执行这些子任务的过程。
通过并行计算，可以显著缩短计算任务的执行时间，提高计算系统的吞吐量和响应速度。
二、并行计算的算法设计原则1. 任务划分：将计算任务分解为多个互相独立的子任务，确保每个子任务间的计算关系尽可能少。
2. 数据划分：将输入数据分割为多个适当大小的块，以便每个处理单元可以独立地操作这些数据块。
3. 通信与同步：处理单元之间需要进行通信和同步操作，以便完成数据交换和协调计算任务的进度。
4. 负载均衡：分配任务给每个处理单元时，需要确保每个处理单元的负载相对均衡，避免出现某个处理单元繁忙而其他处理单元空闲的情况。
5. 数据局部性：合理利用数据局部性原则，减少处理单元之间的数据传输，以提高整体计算效率。
三、并行计算的算法优化技术1. 并行算法设计：根据具体的计算问题，设计高效的并行算法，使得各个子任务能够充分利用处理单元的计算能力。
2. 并行性分析：对计算任务之间的依赖关系进行分析，确定哪些计算任务可以并行执行，以及在并行执行时能否通过调整计算顺序来减少通信开销。
3. 算法细节优化：在编写并行算法时，注意细节上的优化，如减少数据冲突、合并通信操作、使用局部缓存等。
4. 并行化策略选择：根据具体应用场景和硬件平台的特点，选择合适的并行化策略，如任务并行、数据并行、管道并行等。
四、并行计算的实际应用1. 大规模数据处理：并行计算在大数据处理、数据挖掘和机器学习等领域具有广泛的应用，可以加速数据处理和分析过程。
2. 科学计算：并行计算广泛应用于科学计算领域，如天气预测、流体力学模拟和量子化学计算等，可以加快计算过程，提高计算精度。
对递归程序的优化的一般的手段全文共四篇示例，供读者参考第一篇示例：递归程序是一种常见的编程技术，但是在实际应用中往往会遇到效率低下的情况。
对递归程序进行优化是提高程序性能的关键。
本文将介绍一些对递归程序进行优化的一般手段，帮助开发人员提高程序的效率。
1. 减少递归深度递归深度是指递归调用的次数，递归深度过深会导致内存消耗增加，程序运行速度变慢甚至栈溢出的风险。
为了减少递归深度，可以考虑使用迭代算法替代递归算法，或者通过动态规划等技术将递归转化为非递归的形式。
2. 减少重复计算在递归程序中，有可能会进行大量的重复计算，导致程序效率低下。
为了减少重复计算，可以使用缓存技术将计算结果存储起来，避免重复计算。
也可以尝试对递归函数进行优化，减少不必要的重复计算。
3. 剪枝优化剪枝优化是指在递归程序中添加一些条件判断，减少无效的递归操作。
通过剪枝技术可以减少递归深度，提高程序效率。
在实际应用中，可以根据具体的问题特点添加适当的剪枝条件，避免不必要的递归操作。
4. 尾递归优化尾递归是指递归函数在最后一步调用自身。
尾递归优化是一种常用的递归优化技术，可以将递归转化为迭代算法。
通过尾递归优化，可以减少递归深度，提高程序效率。
5. 动态规划优化动态规划是一种常用的优化技术，可以将递归问题转化为非递归的形式。
通过动态规划技术，可以减少重复计算，提高程序效率。
在实际应用中，可以使用动态规划优化复杂的递归算法，提高程序性能。
6. 并行化优化并行化是一种提高程序性能的有效手段，可以将递归程序中独立的递归操作并行化处理，提高程序的运行速度。
通过并行化优化，可以充分利用多核处理器的性能，提高程序的并发能力。
对递归程序进行优化是一项具有挑战性的任务，需要根据具体的问题特点选择合适的优化技术。
通过减少递归深度、减少重复计算、剪枝优化、尾递归优化、动态规划优化和并行化优化等手段，可以有效提高递归程序的效率，提升程序性能。
希望开发人员能够根据这些优化技术，更好地优化递归程序，提高程序效率，提升用户体验。
教你如何简单解决递归问题递归问题是计算机科学中常见的一个概念，它在编程中经常被用到。
虽然递归算法能够帮助我们解决一些复杂的问题，但是在实际应用中，递归问题可能会导致效率低下、内存溢出等不良后果。
针对这些问题，本文将介绍一些简单有效的方法，帮助你解决递归问题，以提高程序的性能和效率。
1. 迭代代替递归递归算法的本质是函数不断调用自身，但是函数调用会产生额外的开销，尤其是在处理大规模的数据时。
为了简化递归问题，我们可以考虑使用迭代代替递归。
迭代算法使用循环结构来代替函数调用，从而减少开销，提高效率。
2. 减少递归深度递归算法的一个问题是递归深度过深，可能导致栈溢出。
为了解决这个问题，我们可以通过减少递归深度来降低风险。
一种常见的方法是使用尾递归优化。
尾递归是指在递归函数的最后一步调用自身，这样编译器可以将递归转化为迭代，从而减少递归深度。
3. 缓存中间结果递归算法的另一个问题是重复计算相同的子问题，这样会浪费时间和计算资源。
为了解决这个问题，我们可以使用缓存来存储中间结果。
缓存可以避免重复计算，提高计算效率。
一种常见的缓存方法是使用哈希表来记录已经计算过的结果，这样可以在下次遇到相同的子问题时直接查表而不需要重新计算。
4. 分治法分治法是一种常用的解决递归问题的方法。
其基本思想是将问题划分为多个子问题，然后分别解决这些子问题，并将结果合并得到最终的解。
分治法可以通过递归的方式来实现，但是由于分而治之的特点，它可以显著降低递归的复杂度。
5. 动态规划动态规划是一种高效解决递归问题的方法。
它基于问题的最优子结构特性，通过将问题分解为相互重叠的子问题，并使用递推的方式求解。
与递归算法相比，动态规划算法可以避免重复计算，提高效率。
总结：递归问题在计算机科学中广泛存在，但是在实际应用中，我们经常需要解决递归问题导致的效率低下、内存溢出等问题。
通过使用迭代代替递归、减少递归深度、缓存中间结果、分治法和动态规划等方法，我们可以简单解决递归问题，提高程序的性能和效率。
第一章一．填空题1．编译程序的工作过程一般可以划分为词法分析、语法分析、语义分析与中间代码产生、优化和生成目标程序等几个基本阶段，同时还伴有符号表管理和出错处理。
2．若源程序是用高级语言编写的，目标程序是汇编或机器语言，则其翻译程序称为编译程序。
3．编译方式与解释方式的根本区别在于运行目标程序时的控制权在解释器而不是目标程序。
4．翻译程序是这样一种程序，它能将用甲种语言书写的程序转换成与其等价的乙种语言书写的程序。
5．对编译程序而言，输入数据是高级语言（源）程序，输出结果是低级语言（目标）程序。
6．运行编译程序的计算机称宿主机，运行编译程序所产生目标代码的计算机称目标机。
7．当把编译程序划分成编译前端和编译后端时，前端主要由与源语言有关但与目标机无关的部分组成，编译后端包括编译程序中与目标机有关的部分，编译后端不依赖于源语言而仅仅依赖于中间语言。
8．描述词法规则的有效工具是词法分析器，通常使用语法分析器来描述语法规则，使用语义分析（与中间代码产生）器描述语义规则。
二．综合题（该答案仅供参考）1、给出C语言编译程序对下面语句进行编译时从词法分析到目标代码生成5个分析阶段的分析过程。
c=a+b*30;（1）给出每个阶段的输入和输出代码或其它数据形式。
（2）给出符号表，说明在哪些阶段会对符号表进行填写或查找。
（3）编译过程是否进行了代码优化？若有，请指出优化之处，并给出属于哪种优化？答：词法分析：出入源程序；输出识别出的记号流。
c=a+b*30 id1=id2+id3*30语法分析器：输入记号流，构造句子结构；输出语法树。
=id1 +id2 *id3 30语义分析与中间代码生成：出入语法树，输出中间代码变量地址数值注：赋值阶段会对符号表进行填写或查找1. id1 0 c （itr，30，，t1）2. id2 4 x （*，id3，t1，t2）3. id3 8 y （+，id2，t2，t3）4. t1 12 30 （=，t3，，id1）优化：1.（*，id3，30.0，t1）2.（+，id2，t1，id1）精简掉多余的复写传播mulf #30.0，r2 mov id2，r1 sub r1，r2 mov r2，id1第二章一．填空题1．上下文无关文法包括以下四个组成部分：一组终结符号，一组非终结符号，一个开始符号，以及一组产生式。
如何通过调整编译器选项优化程序性能编译器是软件开发中不可或缺的工具，它将我们编写的源代码翻译为机器语言，以便计算机能够理解和执行。
除了正确转换代码外，编译器还提供了一系列优化选项，可以帮助我们改善程序的性能。
在本文中，我们将讨论如何通过调整编译器选项来优化程序性能。
一、启用优化选项编译器通常提供了多个优化级别，例如-O0、-O1、-O2和-O3。
这些级别对应着不同的优化等级，-O0表示关闭所有优化，而-O3表示最高级别的优化。
一般而言，我们可以从低级别的优化开始，逐渐增加优化级别，直到达到一个合适的平衡点。
在开发调试阶段，可以选择低级别的优化，以便更好地理解代码和调试。
而在发布和性能优化阶段，可以提升到更高级别的优化，以达到更好的性能。
二、循环优化循环在大多数程序中占据了相当大的比例。
因此，优化循环的效果对于整个程序性能的提升非常重要。
编译器提供了一些循环优化选项，如循环展开、循环变量优化等。
循环展开可以减少循环迭代次数和分支跳转，提高代码的并行性和局部性。
而循环变量优化可以降低循环次数和计算量，进一步提高性能。
通过调整编译器选项，我们可以指导编译器进行适当的循环优化，以提升程序性能。
三、内存优化内存访问是程序性能的一个瓶颈之一。
编译器提供了一些选项来优化内存访问，如数据对齐、循环展开、循环交换等。
数据对齐可以提高内存访问效率，减少内存访问次数和延迟。
循环展开和循环交换可以改变访问内存的顺序，以提高内存的局部性，进而提高性能。
通过调整编译器选项，我们可以优化程序的内存访问，从而提高性能。
四、系统调用优化在程序中频繁进行系统调用会产生较大的开销。
编译器提供了一些选项，如内联函数、尾调用优化等，可以减少系统调用开销。
内联函数可以将函数调用内联展开，减少函数调用的开销。
尾调用优化可以将递归调用转换为迭代调用，以减少系统调用的开销。
通过调整编译器选项，我们可以优化系统调用，提高程序性能。
五、并行优化如今，多核处理器已经成为主流。
程序运行速度是开发者和用户都非常关心的问题。
一个高效的编译器可以通过各种优化手段，使得程序在运行时能够更快地执行。
本文将从编译器优化的角度来探讨如何提高程序的运行速度。
一、代码生成优化代码生成是编译器的最后一步，也是最重要的一步。
通过优化代码生成过程，可以显著提高程序的运行速度。
1、寄存器分配优化编译器可以通过寄存器分配优化，将变量存储于寄存器中，减少对内存的访问。
寄存器分配算法可以基于图染色理论进行优化，将变量分配到可用的寄存器中，并且尽量减少寄存器之间的数据传输。
2、指令选择优化在代码生成阶段，编译器需要将高级语言转化为机器指令。
指令选择优化可以选择适当的指令，使得程序在执行时更高效。
一些现代编译器还会利用SIMD指令集进行向量化优化，提高了计算密集型程序的性能。
二、优化算法和数据结构除了代码生成优化，还可以通过改进算法和数据结构来提高程序的运行速度。
1、算法优化选择合适的算法是提高程序运行速度的关键。
一些常见的算法，如排序算法、查找算法等，存在不同的实现方式，它们的时间复杂度和空间复杂度也各不相同。
通过选择更高效的算法可以减少程序的执行时间。
2、数据结构优化合理选择数据结构也能够提高程序的运行速度。
例如，对于需要频繁查找的操作，可以使用哈希表或二叉查找树等数据结构来加快查找速度。
对于需要频繁插入和删除的操作，可以选择使用链表等数据结构。
三、循环优化循环是程序中常见的结构，也是性能优化的热点。
通过循环优化可以显著改善程序的性能。
1、循环展开通过循环展开，可以减少循环的迭代次数，提高执行效率。
循环展开可以利用现代处理器的指令级并行性，使得多个迭代可以同时执行。
2、循环不变量代码外提循环中的不变量代码可以提到循环外执行，减少循环内的计算量。
这样可以避免重复计算相同的值，提高程序的运行效率。
四、内存访问优化内存访问是程序执行过程中的耗时操作，通过内存访问优化可以减少数据读写操作，提高程序的运行速度。
如何处理代码中的无限递归问题无限递归是指在程序中出现了不停地调用自身的情况，这样会导致程序陷入无限循环，最终导致程序崩溃。
这种问题通常会导致程序的性能下降和内存占用增加，甚至可能会导致整个系统崩溃。
因此，如何处理代码中的无限递归问题是程序开发中非常重要的一环。
在本文中，我们将探讨无限递归问题的产生原因、如何检测无限递归以及如何解决无限递归的方法。
一、无限递归问题的产生原因无限递归问题通常是由于程序中存在着逻辑错误或者编程错误所导致的。
比如，在编写递归函数时，忘记了设置递归的退出条件，导致递归无法正常结束。
又比如，在递归函数中调用了一个永远返回true的条件语句，导致递归无法退出。
此外，无限递归问题还可能是由于栈溢出所导致的，当递归层数过深时，栈空间会被耗尽，从而引发程序崩溃。
二、如何检测无限递归在编写代码时，我们需要时刻关注可能存在的无限递归问题。
在检测无限递归时，可以使用递归深度和递归次数这两种方法来进行检测。
递归深度是指递归函数的嵌套层数，当递归深度过深时，可能会出现无限递归的情况。
递归次数是指递归函数的调用次数，当递归次数过多时，也可能会出现无限递归的情况。
此外，还可以使用调试工具或者代码审查的方式来检测无限递归。
三、如何解决无限递归问题解决无限递归问题的方法有很多种，可以根据具体的情况选择合适的方法。
下面我们将介绍几种常见的解决无限递归问题的方法：1.设置递归结束条件在编写递归函数时，一定要记得设置递归结束条件，确保递归能够正常结束。
递归结束条件通常要考虑到递归函数的输入参数以及递归深度，确保递归结束条件能够覆盖所有可能的情况。
2.优化递归算法在编写递归函数时，要尽量避免不必要的递归调用，尽量优化递归算法，减少递归深度和递归次数。
可以考虑使用循环代替递归，或者使用尾递归优化来减少递归的开销。
3.使用辅助变量在递归函数中，可以使用辅助变量来记录递归的状态，以便在递归结束时能够正确返回结果。
idea编译 stackoverflowerror
当我们在使用idea编译项目时，有时会遇到
'stackoverflowerror'的错误，这是由于程序递归太深所导致的。
要解决这个问题，可以采取以下措施：
1. 增加程序的栈大小
在idea的VM Options中增加-Xss参数，将栈大小设置得更大一些，例如-Xss8m。
这样可以增加程序的栈大小，避免递归过深导致的错误。
2. 优化程序的递归算法
如果程序出现了递归过深的问题，可以尝试优化递归算法，减少递归次数。
例如，可以使用循环代替递归，或者使用尾递归等技术优化算法。
3. 优化程序的数据结构
有时，递归算法的问题可能源于数据结构的设计不合理。
可以通过优化数据结构来避免递归过深导致的问题。
例如，可以使用栈来替代递归，或者使用其他数据结构来优化算法。
总之，遇到'stackoverflowerror'错误时，可以通过增加栈大小、优化递归算法或优化数据结构等方式来解决问题。
- 1 -。
软件学报JOURNAL OF SOFTWARE1999年第1期No.1 1999并行化编译中递归标量的优化处理*王诚臧斌宇朱家菁朱传琪摘要提出了一种并行化编译中统一处理递归标量的通用方法.该方法将递归标量的处理转化为差分方程(组)的求解,然后利用Z变换与反Z变换来求解方程(组).提高了并行化编译器对递归标量的处理能力,有利于对串行程序的自动并行.关键词递归标量,相关性分析,差分方程,强连通分枝,Z变换.中图法分类号TP314Induction Scalar Optimization in Parallelizing CompilerW ANG Cheng ZANG Bin-yu ZHU Jia-jing ZHU Chuan-qi Abstract In this paper, a general method is put forward to process the induction scalars in paralleling compiler. This method changes the processing of induction scalars to the solving of difference equations and uses Z transformation and inverse Z transformation to solve equations. It improves the paralleling compiler's ability to process the inductive scalars, which is helpful to the automatic parallelization of serial programs.Key words Induction scalar, dependence analysis, difference equation, strongly connected components, Z transformation.相关性分析是并行化编译中的重要环节,相关性分析能力直接影响到并行化编译器的并行化能力,而对数组变量进行相关性分析是相关性分析的关键.数组的相关性分析依赖于对数组下标表达式的分析,已有的相关性分析方法只能够分析含有循环常量或循环参数的下标表达式,对于含有循环变量的下标表达式则通过表达式替代来消除.由于递归标量的值不仅依赖于循环参数,而且依赖于该变量上一次循环的值,因而数组下标中的递归标量不能通过简单的替代来消除,其值的不确定性影响了数组变量的相关性分析,而且递归标量本身也会产生跨循环的相关,影响并行化.递归标量在数组下标中广泛存在,如果不能对它进行有效的处理,许多可并行化的循环只能因信息不足做保守估计,而不能自动并行化.将递归标量变换为等价的非递归标量,消除其不确定性,可以有效地减少循环之间的相互依赖,提高数组变量相关性分析的精度,也有利于unimodular变换、变量归约及向前替代等并行技术的实现,成为提高并行编译器并行化识别能力的有效手段.递归标量不能通过常数、表达式的传播或其他常规方法来消除.到目前为止,尚没有统一、有效的方法来处理递归标量,已有的方法都只能处理某些个别和特殊的情况,缺乏普遍性,而且都存在一定的缺点.有些方法通过模式识别来识别固定模式,然后对其进行表达式的替换［1］, 例如：对于X的循环初值为X0,I为循环参数,初值与步长均为1,可识别X=X+1模式,将其替换为X=X0+I;识别X=X+I模式,将其替换为X=X0+I*(I+1)/2等.该方法只能处理简单的多项式,对于多维递归标量则无法处理.也有些方法先识别递归标量表达式的形式,求出一般通式,再利用特殊值求待定系数［2］,例如：对于X=2*X+1,变换为差分方程X(I+1)=2*X(I)+1,由差分方程的特征值可求出其一般通式为X(I)=C0*2**I+C1,此处C0,C1为待定系数,代入X(0)=X0,X(1)=2*X0+1,可求出C0=X0+1,C1=-1,所以可替换为X=(X0+1)*2**I-1.该方法处理范围仅限于一部分多项式的情况,而且由于多维递归标量的前几次循环受标量初值的影响而出现异常,无法满足一般通式,因而需要展开前几次循环实例(见例2).该方法难以确定异常出现的循环次数,从而难以选取适当的特殊值以求其待定系数.本文提出了对递归标量的统一的通用处理方法,通过将递归标量标准化为差分方程（组）,然后利用控制理论中常用的Z变换与反Z变换的方法来求解差分方程（组）,对递归标量进行优化,增强了对递归标量的处理能力,克服了其他递归标量处理方法的缺点.由于我们通过求解差分方程（组）来处理递归标量,因而有坚实的数学基础做保证,而且对多维与一维递归标量可同样处理.而对于受初值影响而需要展开的循环次数也可从方程的解中直接得出.我们对各方程（组）按数据依赖关系进行拓扑分类依次处理,一方程的解可通过变量的替代传至引用其变量的另一方程,因而可以按数据依赖对递归标量进行依次处理.而对于嵌套循环,也可由内向外对各循环进行依次处理.该方法的处理能力仅依赖于Z变换与反Z 变换的能力,对于所有可以变换为有理多项式或底数为有理数的指数表达式的递归标量,本文中介绍的算法都能够处理.由于当前对数组的相关性分析只限于处理数组下标为循环参数的线性、幂及简单的指数表达式的情况,因而该算法对递归标量的处理能够充分满足相关性分析的要求.下面,我们通过几个例子来加以说明.例1: DO 10 I＝1,100例2: DO 10 I＝1,100N＝N＋1 (1)M＝P(2)A(N)＝A(N)＋I P＝N(3)...N＝P＋1(4) 10CONTINUE A(M)＝A(M)＋IB(N)＝B(N)＋110CONTINUE递归标量是指循环中的整型标量,它的赋值直接或间接地依赖于上一次循环中该标量的值.例1中,标量N就是递归标量,因为它的赋值依赖于其上一次循环的值.我们可以通过对递归标量进行处理,将其变为非递归标量.例如,语句（1）可等价为N＝N0＋I,（5）其中N0为N的进入循环时的初始值.例2中,M,N,P都是递归标量,因为它们的值都间接地相互依赖于上一次循环的值.对其进行的处理,在展开一次循环实例后,也可等价地变为非递归标量的形式：A（P0）＝A（P0）＋1B（N0＋1）＝B（N0＋1）＋1DO 10 I＝2,100M＝N0＋I－2P＝N0＋I－1N＝N0＋IA（N0＋I－2）＝A（N0＋I－2）＋IB（N0＋I）＝B（N0＋I）＋110CONTINUE其中M0,P0,N0分别为M,P,N进入循环时的初始值.该例中,由于M的值受P初值的影响而出现异常,所以展开了第1次循环.由此可见,展开前几次循环后,有些递归标量的赋值可变为初始值与循环参数的表达式,从而变为非递归标量.在程序的并行化编译中,递归标量的存在常常会阻碍程序的并行化.递归标量本身的值依赖于上一次循环的值,从而产生跨循环的相关,使循环不能并行化.递归标量还常常出现在数组的下标中,其值的不确定性也妨碍了对数组的相关性的分析.如在例1中,如果不能知道N与I的关系,循环就不能并行化.如将式(1)变为式（5）,再代入数组变量A的下标中就不难看出,变量N 和A都没有跨循环的数据相关,因而可以并行执行.对于例2也是如此.本文第1节讨论如何将递归标量标准化为差分方程（组）,第2节给出利用Z 变换与反Z变换对方程进行求解的算法,第3节介绍一个实际的求解例子,第4节则介绍相关的工作及将来的发展.1递归标量标准化为差分方程对于递归标量的优化处理,首先要将其标准化为差分方程(组),然后解出其通解形式,代入原程序.通常,递归标量的值可等价于某一递归方程(组)的解.例如,式（1）可等价于如下差分方程：N(k+1)=N(k)+1(k≥0),其中N(k)为第k次循环时对N的赋值,N(0)为进入循环时N的初始值,下同.例2中,式(2)～(4)也可写为如下差分方程组:下面,我们通过一个例子具体介绍将递归标量标准化为差分方程的过程.例3: DO 10 I=1,NB=2*BA=－A－B＋CC=D+1B=－3*A－B＋CD=I10CONTINUE首先,通过改名将循环中的变量赋值变为单赋值语句.如下所示,循环中存在对同一标量的两赋值语句S1,S3：X=... S1... S2X=... S3将S1变为Y=...同时将S1与S3之间对X的引用变为Y.例3中对B有两处赋值,对第1处赋值的B改名为E,并将两赋值之间的对B的引用改为E,则变为：DO10 I=1,NT1E=2*BT2A=－A－E+CT3C=D+1T4B=－3*A－E+CT5D=I10CONTINUE对所有循环中的标量单赋值语句,将所有对变量X的赋值变为对X(k)的赋值,赋值以前的引用变为X(k),赋值以后的引用变为X(k+1),则例3中的赋值变为:E(k+1)=2B(k)A(k+1)=-A(k)-E(k+1)+C(k)C(k+1)=D(k)+1B(k+1)=-3A(k+1)-E(k+1)+C(k+1)D(k+1)=k+1对于所得赋值语句S1,S2,...,S n,将S1代入S2,S3,...,S n,将S2代入S3,S4,...,Sn,等等,依次类推,即可得到如下差分方程：对于例3,即可得E(k+1)=2B(k)(6)A(k+1)=-A(k)-2B(k)+C(k)(7)C(k+1)=D(k)+1(8)B(k+1)=3A(k)+4B(k)-3C(k)+D(k)+1(9)D(k+1)=k+1(10)再根据数据依赖关系构造有向图,对有向图求强连通分枝,强连通分枝的凝聚图和凝聚图的拓扑分类后,按拓扑分类顺序依次处理如下：由式(10)可得(D0为D的循环初始值,下同)我们定义k的函数L(n,k,C0,C1,...,C n)为L(n,k,C0,C1,...,C n)=则D(k)=k+L(0,k,D0) (k≥0).(11)此处的L函数即为差分方程受初值影响而产生的异常,它只影响递归标量的前n次循环,因而n即为需展开的循环次数.把式(11)代入式(8)得即C(k)=k+L(1,k,C0,D0) (k≥0)(12)把式(6)、(12)代入式(7)得A(k+1)=-A(k)-2B(k)+C(k) A(k+1)=-A(k)-2B(k)+k+L(1,k,C0,D0)(k≥0)(13)把式(6)、(12)代入式(9)得B(k+1)=3A(k)+4B(k)-3C(k)+D(k)+1=3A(k)+4B(k)-3［k+L(1,k,C0,D0)］+k+L(0,k,D0)+1, B(k+1)=3A(k)+4B(k)-2k+1+L(1,k,-3C0+D0,-3D0)(k≥0).(14)令B(k),由式(13)、(14),求差分方程组可得求解此差分方程即可将例3中的所有递归标量变为非递归标量.2差分方程的求解下面讨论对差分方程的求解.假设已求得方程：x(k+1)=Ax(k)+u(k),(15) A为m阶常数方阵,u(k)只含有循环参数和循环不变量且标准化为有限个Rk n c k或L(n,k,D0,D1,...,D n)的和,即u(k)=R l k n l+L(n,k,D0,D1,...,D n),其中R l,D l为m维向量,c l为常数,n l为非负整数.对函数f(k),定义其Z变换F(z)为:定义1.F(z)=Z［f(k)］=f(i)z-i.逆变换Z-1定义为：Z-1［F(z)］=f(k).其中k为原函数自变量,z为变换后函数自变量,小写字母f为原函数,相应的大写字母F为其Z变换后的函数,下同.为了本文的完整性与便于阅读,我们列出求解上述差分方程所要用到的引理.这些引理的证明可参考文献［3,4］.引理1.f(k),g(k)为任意函数,则Z变换有如下性质：①Z［af(k)+bg(k)］=aZ［f(k)］+bZ［g(k)］;②Z［f(k+1)］=zZ［f(k)］-zf(0);③Z［C i k c k］=c i z/(z-c)i+1(c≠0);④Z［L(n,k,d0,d1,...,d n)］=d i/z i.C为组合符号,即C i k=k!/［(k-i)!i!］,!为阶乘,a,i,c,d i为常数,i,n为非负整数.引理2.由任意m阶方阵A可得(zI-A)-1=B i z m-i/a i z m-i(16)B i,a i满足递推式：i0=1,B1=I m,a i=-tr(AB i)/i,i i+1=AB i+a i I m,其中tr(R)为方阵R对角线元素之和,即R=(r ij)m×m,则tr(R)=r11+r22+...+r mm.引理3.对任意i次多项式i(z)以及m次多项式p(z),存在u次多项式q(z)和υ次多项式t(z),使得r(z)=q(z)p(z)+t(z)且υ<m.定义2.对引理3中的r(z)=q(z)p(z)+t(z),定义q(z)=r(z)%p(z), t(z)=r(z) mod p(z).引理4.对任意n次多项式r(z),i次多项式q i(z),i=0,1,...,n,存在a i(i=0,1,...,n),a0≠0,使得r(z)=a n-i q i(z).引理5.n次多项式p(z)和m次多项式q(z)互素,对任意s次多项式r(z),如果s<m+n,则存在唯一的υ次多项式υ(z)和w次多项式w(z)(υ<m,w<n),使得υ(z)p(z)+w(z)q(z)=i(z).引理6.对于n次多项式q(z)=a i z n-i=a0(z-d l)i l,如果所有的a i都是整数,d l为有理数d l=p l/q l(p l,q l为整数且互素),则有p l整除a n,q l整除a0.下面,我们应用以上引理来求式(15)的x(k).对式(15)两边进行Z变换,应用引理1中Z变换的性质(1)、(2)得Z(x(k+1))=Z(Ax(k)+u(i)), zX(z)-zx(0)=AX(z)+U(z), X(z)=(zI-A)-1zx(0)+(zI-A)-1U(z),(17)可求得x(k)=Z-1［X(z)］=Z-1［(zI-A)-1zx(0)+(zI-A)-1U(z)］.首先,我们做Z变换,求式(17)中的X(z).定义3.称t(z)=p(z)/q(z)为n次真分式,如果p(z)为s次多项式,q(z)为n次多项式,并且n>s≥0.定理1.式(17)中的X(z)可表示为X(z)=T l zx(0)t l(z)+S l zs l(z).(18) T l为m×m矩阵,S l为m维向量,t l(z),s l(z)为真分式.证明：因为q i(k)=C i k为i次多项式,由引理4及引理1可得Z［k n c k］=Z a n-i C i k c k=a n-i Z［C i k c k］=a n-i c i z/(z-c)i+1,U(z)=Z［u(k)］=Z R l k n l c k l+L(n,k,D0,D1,...,D n)=R l a n l-i c i l z/(z-c l)i+1+D i/z.由引理2中式(16)可知,(zI-A)-1=B i z m-i a i z m-i=B i z m-i a j z m-j=B i t i(z),所以X(i)=(zI-A)-1zx(0)+(zI-A)-1U(z)=B i zx(0)［t i(z)］+［B i R l a n l-j c j l］z［t i(z)/(z-c l)j+1］+［B i D l］z［t i(z)/Z l+1］.由定义3可知,t i(z),t i(z)/(z-c l)j+1,t i(z)/z l+1为真分式.□定理1的证明是构造性的,不难从中得出求X(z)的算法.下面我们通过式(18)的反Z变换求x(k).定理2.任意真分式t(z)必可表示为有限个g/(z-d)i的和,即t(z)=g l/(z-d l)i l+1 (g l,i l为常数,且i l≥0).证明：设t(z)=p(z)/q(z),p(z)为s次多项式,q(z)为n次多项式,s<n,对n进行归纳：i=1时,q(i)=a0z+a1,a0≠0,因为s<n,所以s=0,p(z)=p,t(z)=(p/a0)/(z-a1/a0),定理成立.假设当n<k时,定理成立.当n=k时,由引理6,q(z)可表示为:q(z)=(z-z0)i r(z).z0为q(z)=0的根,i>0,r(z)为n-i次多项式,并且r(z)与(z-z0)i互素.因为s<n=(n-i)+i,由引理5可知,存在唯一的υ次多项式υ(z)和w次多项式w(z),使得υ(i)(z-z0)i+w(i)r(z)=p(z)(υ<n-i,w<i),则t(z)=p(z)/q(z)=［υ(z)(z-z0)i+w(z)r(z)］/［(z-z0)i r(z)］=w(z)/(z-z0)i+υ(z)/r(z).由引理4,w(z)可表示为w(z)=a l(z-z0)w-l,w(z)/(z-z0)i=a l/(z-z0)l+i-w,l+i-w>0,因为υ<n-i<k,由归纳假设得υ(z)/r(z)=g l/(z-d)i l+1(i l≥0),所以t(z)=a l(z-z0)l+i-w+g l(z-d l)i l+1.□由定理1、定理2可知X(z)=T l t l(z)zx(0)+S l s l(z)z=T l g l t z/(z-d l t)i l t+1x(0)+S l h l t z/(z-e l t)j l t+1,x(k)=Z-1［X(z)］=T l g l t x(0)Z-1［z/(z-d l t)i l t+1］+S l h l t Z-1/［z/(z-e l t)j l t+1］.由引理1中Z变换性质③、④,可得即可求得x(k).3实际求解的例子对例3求得的差分方程求Z变换得求反Z变换得由于结果中有L(1,k,0,1),所以展开第1次循环,则例3可消除递归标量而等价变形为：A=－A0－2*B0＋C0C=D0＋1B=3*A0＋4*B0＋1＋D0－3*C0D=1DO 10 I=2,NA=(3-2**(I+1))*A0+(2-2**(I+1))*B0-I*(I-1)/2+(2**(I+1)-3)*C0-D0C=IB=(3*2**I-3)*A0+(3*2**I-2)*B0+I*(I+1)/2+(3-3*2**I)*C0+D0D=I10CONTINUE4结论递归标量对相关性分析等其他并行化技术产生严重影响,详细情况可见参考文献［5,6］.本文讨论了利用Z变换及反Z变换将递归标量变为非递归标量的方法,该方法的处理能力与计算复杂度依赖于Z变换与反Z变换的算法.本文给出一种Z变换与反Z变换的具体算法,由于当前对数组的相关性分析只限于处理下标为循环参数的线性、幂及简单的指数表达式的情况,本文中介绍的算法能够处理所有可以变换为多项式或指数表达式的递归标量,因而该算法对递归标量的处理能够充分满足相关性分析的要求.本文介绍了将递归标量转化为差分方程的过程,文中的例子中没有涉及控制相关,对于存在控制相关的问题则有待于进一步的讨论.本文研究得到国家自然科学基金、国家863高科技项目基金、国家攀登计划基金和上海市重点学科与学术带头人基金资助.作者介绍：王诚,1971年生,硕士生,主要研究领域为并行处理.臧斌宇,1965年生,副教授,主要研究领域为并行处理.朱家菁,女,1972年生,硕士生,主要研究领域为并行处理.朱传琪,1943年生,教授,博士生导师,主要研究领域为并行处理.本文通讯联系人:王诚,上海200433,复旦大学并行处理研究所作者单位：王诚臧斌宇朱家菁朱传琪复旦大学并行处理研究所上海200433参考文献［1］Padua David A, Wolfe Michael. Advanced compiler optimizations for supercomputers. Communications ACM, 1986,29(12):1184～1202［2］Pottenger B, Eigenmann R. Idiom recognition in the Polaris parallelizing compiler. In: Wolfe M ed. Proceedings of the International Conference'95 on Supercomputing. New Y ork: ACM Press, 1995. 444～448［3］Lovaglia Anthony R, Preston Gerald C. Foundations of Algebra and Analysis. New Y ork and London: Harper & Row Publishers, 1966［4］Reid J Gary. Linear System Fundamentals, Continuous and Discrete, Classic and Modern. New Y ork: McGraw-Hill Book Company, 1983［5］Wolfe Michael. High Performance Compilers for Parallel Computing. New Y ork and London: Addison-Wesley Publishing Company, Inc. 1996［6］Allen John R, Kennedy Ken. Automatic translation of Fortran programs to vector form. ACM Transactions on Programming Languages and Systems,1987,9(4):491～542本文1997-09-29收到原稿,1997-12-26收到修改稿。
