微代码全局压缩的改进型路径调度法及其实现

微代码全局压缩是当前固件工程的一个重要课题。本文介绍一个基于Fisher路径调度法的微代码全局压缩算法,对空间效益及循环压缩作了改进。这个改进型算法包括:(1)修改微操作移动规则;(2)采用启发式路径调度算法;(3)采用特殊的循环压缩算法。 我们已实现这个改进算法,并用实际机器的微代码进行验证。初步结果表明新算法无论在时间效益及空间效益上都比Fisher算法有明显提高,更接近于手工压缩。     

平行结构类问题的分解与任务分布

本文给出平行结构类问题及其求解系统的形式化描述,讨论了此类问题的分解与任务分布,并提出了一种IPD算法(Improved Problem Decomposition).该算法从规模上将问题分解为若干性质相同的任务,按就近原则将任务预分布到系统中各结点上,并通过启发式状态空间查找方法进行负载调整,使系统负载平衡.试验表明:IPD算法的分解分布结果负载平衡,系统潜在协作量小.     

多指令流多数据流并行处理仿真器

本文叙述一个大型MIMD(多指令流多数据流)并行处理系统的微程序仿真器,该仿真器可在目标系统实现之前调试要运行的应用程序及量测目标系统的性能。本文先介绍目标系统(大型MIMD并行处理系统),然后介绍微程序宿主机(PUMA),最后介绍仿真器PARCER的实现。     

一种软件流水的反流水算法

软件流水是一种循环程序的优化技术,已经广泛应用于现代优化编译器中.为了充分利用VLIW DSP处理机的指令级并行性,必须使用软件流水技术对DSP程序进行优化.然而,在串行源代码不存在的情况下,对软件流水后的原始代码进行变换、理解、测试和调试,并转换成其他处理机的代码是非常困难的.提出了一种反流水技术,它能够将软件流水后的优化汇编代码反向转换成语义等价的相应代码.通过20个程序的初步实验,验证了所提出的反流水算法的正确性.     

一种运行时消除指针别名歧义的新方法

提出一种采用软硬件结合的运行时消除指针别名歧义的新方法SHRTD（software/hardware run-time disambiguation）.为延迟运行时不正确的内存访问及其后继操作,SHRTD的功能单元执行NOP操作.为保证所有延迟操作执行顺序的一致性,编译时就确定执行NOP操作的所有功能单元的顺序和NOP操作的数目.SHRTD方法适用于不可逆代码,同时它的代码空间受限,也不存在严重的代码可重入性问题.新方法有效地解决了指针别名问题,为获得潜在的指令级并行加速提供了可能.     

循环体间相关问题及改进的URPR软件流水方法

本文首先在理论上分析了循环体间相关对软件流水的影响.提出了一个由循环本身性质决定的充分必要条件并证明了满足此条件的循环是可限制的,否则是不可限制的;其次我们证明了任意不可限制的循环展开K次后即可转换为可限制循环,K取决于循环本身的性质;最后给出了循环预处理算法和一个新的循环体压缩算法.实验结果表明,这两个算法可使URPR算法对任意循环都能得到最优时间效益并保持了良好的空间效益及低的计算复杂性.     

运行时消除指针别名歧义方法的加速比分析S

采用软硬件结合的运行时消除指针别名歧义方法SHRTD(software/hardware run-time disambiguation)适用于不可逆代码,同时,它的代码空间受到限制,不存在严重的代码可重入性问题.文章详细分析了SHRTD方法的指令级并行加速比,给出了发生地址冲突后的并行加速比与平均并行加速比以及发生地址冲突的依概率并行加速比.文章引入的三类理论加速比对指令级并行编译技术的研究和评测有重要的实际意义.     

分布式求解平行结构类问题中重选区域的研究

本文以平行结构类问题的形式化描述为基础,详细讨论了分布式求解平行结构类问题系统中相邻结点间重迭区域的作用,定义了最小重迭区域的概念,并提出一种新的设立重迭区域方法——“可变法”,最后在分布式运输调度系统上进行了试验研究,结果表明:〈1〉设置重迭区域是必要的;〈2〉最小重迭区域的定义是有意义的;〈3〉与美国麻省大学采用的“固定法”相比,“可变法”保证了求解质量,减少了冗余的计算与通信开销。     

具有时间约束的微代码压缩问题

微程序机器中的时间约束关系将使微代码压缩问题复杂化并影响压缩结果,这是一个重要的实际问题,但迄今尚无很好的解决办法.本文在对具有时间约束的微代码压缩问题进行系统分析的基础上,提出一个通用的启发式CAS方法,初步实验表明CAS方法的调度成功率及压缩结果均优于现有其它方法.