Time Optimal Software Pipelining of Loops with Control Flows

Software pipelining is widely used as a compiler optimization technique to achieve high performance in machines that exploit instruction-level parallelism. However, surprisingly, there have been few theoretical or empirical results on time optimal software pipelining of loops with control flows. In this paper, we present three new theoretical and practical contributions for this underinvestigated problem. First, we propose a necessary and sufficient condition for a loop with control flows to have an optimally software-pipelined program. We also present a decision procedure to compute the condition. As part of the formal treatment of software pipelining, we propose a new formalization of software pipelining. Second, we present two software pipelining algorithms. The first algorithm computes an optimal solution for every loop satisfying the condition, but may run in exponential time. The second algorithm computes optimal solutions efficiently for most (but not all) loops satisfying the condition. The former one proves the sufficiency of the condition and the latter one suggests a practical optimal software pipelining algorithm. Third, we present experimental results which strongly indicate that achieving the time optimality in the software-pipelined programs is a viable goal in practice with reasonable hardware support.     

一种支持多重循环软件流水的寄存器结构

寄存器结构及其分配是软件流水算法的关键之一.为支持多重循环的软件流水,该文提出一种新颖的寄存器结构：半共享跳跃式流水寄存器堆.它可以有效地解决多重循环软件流水下的特殊问题,即：同层次和跨层次的寄存器重命名问题以及断流问题;有效地消除外层循环的体间读写相关,提高程序的指令级并行度.它有3种分配方式可供灵活使用：单个寄存器、流水寄存器和寄存器组方式.流水寄存器方式对生存期确定的、局限于一个循环层次的寄存器重命名问题提供简单而有效的支持.寄存器组分配方式解决了多重循环软件流水时变量生存期不确定的情况.跳跃操作为     

弹性数据相关与软件流水

最差路径是有分支循环软件流水的一大障碍.对于有分支循环,某些数据相关(称为弹性相关)在循环的动态执行中可能产生、也可能不产生实例.据此,可将严重限制并行性的弹性相关用限制较松的虚构相关代替,再进行软件流水.若调度没有遵守原来的弹性相关,则使用下推变换修正.从而缓解或者完全解除了最差路径的限制.该方法与经典的控制猜测互补,特点是允许调度含错,然后纠错.     

一个基于软件流水技术的VLIW体系结构

本文叙述一个正在开发的VLIW多处理单元单片机,这个机器的体系结构基于URPR软件流水技术,采用了流水寄存器堆来减少体间相关距离,因此,细粒度并行性可得到充分开发,从而提高了循环体重叠程度,使得优化后的循环体的长度可大大缩短.模拟实验结果表明,这个体系结构在优化编译器的配合下可达到很高的性能。     

Instruction-level experimental evaluation of the Multiflow TRACE 14/300 VLIW computer

Advances in compiler technology have recently led to the introduction of the architectural paradigm known as thevery long instruction word (VLIW) architecture. The Multiflow Trace series of processors is the first commercial line of processors with this architecture. This article presents experimental results concerning the performance and resource utilization of the TRACE 14/300 on a set of 11 common scientific programs written in both C and FORTRAN. Several characteristics of the application, architecture, implementation, and compiler that contribute to the observed results are identified. These characteristics include a conservative approach by the compiler in determining the existence of data dependence and disambiguating memory references, memory latency and resource dependences resulting from the TRACE 14/300 implementation, and actual data dependences that exist within the code. Alleviating the effects of the first three of these bottlenecks is found to improve the TRACE 14/300 performance by a factor of 1.55 on average. Performance of the TRACE 14/300 is also measured on several standard benchmarks, including the SPEC89 benchmark suite. Performance on the SPEC89 benchmarks is found to be comparable to the superscalar IBM RS/6000 when differences in implementation technology are considered. Concluding remarks concerning instruction-level parallel processing are also presented.     

Instruction-level parallel processing: History,overview, and perspective

Instruction-level parallelism (ILP) is a family of processor and compiler design techniques that speed up execution by causing individual machine operations to execute in parallel. Although ILP has appeared in the highest performance uniprocessors for the past 30 years, the 1980s saw it become a much more significant force in computer design. Several systems were built and sold commercially, which pushed ILP far beyond where it had been before, both in terms of the amount of ILP offered and in the central role ILP played in the design of the system. By the end of the decade, advanced microprocessor design at all major CPU manufacturers had incorporated ILP, and new techniques for ILP had become a popular topic at academic conferences. This article provides an overview and historical perspective of the field of ILP and its development over the past three decades.     

3种提高软件流水有效性的算法:比较和结合

软件流水是开发循环程序指令级并行性的技术,它通过并行执行连续的多个循环体来加快循环的执行速度.在软件流水中,循环体的重叠增加了寄存器需求,导致寄存器压力增大,当目标处理机所提供的寄存器不足时,软件流水可能失败.在Itanium处理机上评估了NAS和SPEC2000基准程序中的软件流水循环的寄存器需求,发现静态寄存器不足是造成软件流水失败的主要原因,提出了3种增加软件流水个数、提高软件流水有效性的算法:限制循环展开因子的算法(register sensitive unrolling,简称RSU)、堆栈寄存器分配算法(stacked registerallocation,简称SRA)以及变量类型转换的算法(variabletype conversion,简称VTC).RSU根据静态寄存器需求确定一个合理的展开因子,增加了软件流水的成功率;SRA和VTC分别使用空闲的堆栈寄存器和旋转寄存器来充当静态寄存器,提高了寄存器的利用率.在面向Itanium处理器的开放源码编译器ORC(open research compiler)上实现了这3种算法,通过NAS程序的测试比较了这3种算法的有效性,同时对它们的结合应用进行了研究和实验.     

一种基于遗传算法的硬件／软件划分方法

文中采用相邻块通信划分模型及由单处理器和专用硬件构件组成的目标结构,解决了硬件约束条件下系统执行速度的优化问题,与贪心算法相比,该方法可在合理的时间内为嵌入式系统寻找到满意的解决方案。     

A Preliminary Software Engineering Theory as Investigated by Published Experiments

The investigation of software engineering techniques by using the experiment sets up the discipline of experimental software engineering. The effectiveness and efficiency of software engineering techniques have been studied in experiments and confronted with empirical data. The results of these experiments are published in a diversity of journals and proceeding papers. However, there is not an overview so far which represents the available results systematically. By taking the results from published experiments that deal with analysis, design, implementation, test, maintenance, quality assurance, and reuse techniques a preliminary software engineering theory is developed. From this theory, fruitful problems, suggestions for gathering new data, and entirely new lines of investigation are deduced.     

A View of Software Development Environments Based on Activity Theory

We view software development as a collaborative activity that is typically supported by a software development environment. Since these environments can significantly influence the collaborative nature of a software development project, it is important to analyze and evaluate their capabilities with respect to collaboration. In this paper, we present an analysis and evaluation of the collaborative capabilities of software development environments using an activity theory perspective.The discipline of software engineering (SE) emerged to study and develop artifacts to mediate the collective development of large software systems. While many advances have been made in the past three decades of SE's existence, the historical origins of the discipline are present in that techniques and tools to support the collaborative aspects of large-scale software development are still lacking. One factor is a common ``production-oriented' philosophy that emphasizes the mechanistic and individualistic aspects of software development over the collaborative aspects thereby ignoring the rich set of human-human interactions that are possible over the course of a software development project.We believe that the issues and ideas surrounding activity theory may be useful in improving support for collaboration in software engineering techniques and tools. As such, we make use of the activity theory to analyze and evaluate process-centered software development environments (PCSDEs).     

一种基于效用和证据理论的可信软件评估方法

由于可信软件评估需求的动态多变以及专家主观决策的有限理性,多维多尺度可信软件评估问题是一个重要而困难的研究课题.在分析现有可信软件评估需求的基础上,提出一种基于效用和证据理论的可信软件评估方法.首先设计了一个需求驱动的可信指标树动态构造模型:开放式可信指标数据库和指标树生成算法;接着讨论分析了基于效用的可信软件定性和定量指标的信息预处理技术,并重点介绍基于分布式评估框架和Dempster合成规则的可信软件评估证据推理算法;最后通过案例证明了该方法的有效性和合理性.相信该模型的提出能对复杂环境下软件可信性评估理论的进一步研究起推动作用.     

HSSM:一种流数据分层次模最大化方法

从大规模数据中“摘要”出最能满足效用函数收益的有限个数据对象,可以被归纳为次模函数最大化问题.并行过滤算法在满足流数据访问次数限制与实时响应的条件下,通过分布式筛选的方式实现次规模最大化,但在提升摘要速率时效用函数收益损失较大.提出一种流数据分层次模最大化算法HSSM,在仅访问一次数据集的条件下,采用流水并行的分布式处理框架得到接近于标准贪心算法的次模函数收益,同时改进HSSM通过累积摘要的压缩存储、分层过滤低增益对象提升摘要速率.该方法在数据摘要问题的相关领域具有广泛的应用性,如文档集中代表性文章的选取、数据集中心点选取等.实验结果显示,分布式算法Spark-HSSM+对比于传统的算法在运行速率上达到与摘要规模k成k\\+2正比例关系的提升.而相对于其他分布式算法,其实验效用收益与理论最差收益都更接近于贪心算法.     

基于信息论的软件测试性分析方法的改进研究

随着软件产业的不断发展,软件不断向系统化、集成化发展,软件所实现的功能越来越强大,复杂程度越来越高,最终导致软件质量越来越难以保证。软件测试性分析能够提供软件测试性信息,通过这些信息设计人员能在设计和测试执行之前确定测试的难易程度和所需资源,从而决定是否需要修改设计以得到一个更易测试的软件。以信息论软件测试性分析方法为基础,将程序转化为信息转换图进而利用信息论的方法进行测试性分析,最后引入模糊综合评价的方法对分析结果进行评价,并通过实例对该方法的有效性进行验证。     

基于因果图的软件测试方法

因果图方法是一种有效的软件测试方法,适合于描述对于多种条件的组合、相应产生多个动作形式的测试用例设计。因果图最终被转换为判定表,但是由因果图到判定表的转换是很困难的。描述了因果图方法的原理并详细说明了因果图到判定表的转换算法,介绍了因果图方法测试用例的生成。     

一种应用机器学习和D-S证据理论的Linux病毒检测方案

设计了一种应用机器学习和D-S证据理论来进行Linux病毒检测的方案。主要包括方案的总体框架、样本特征选择方法、分类器选择、检测效果融合以及方案验证与结果分析等。在样本特征选择时引入了控制流程图的概念,在检测效果融合时使用了D-S证据理论的方法。最后在基于Weka软件的机器学习平台上实现和测试了该方案。验证结果表明,该Linux病毒检测方案具有良好的检测率和可靠性,可以应用于实际的商业产品中。     

A Road-Matching Method for Precise Vehicle Localization Using Belief Theory and Kalman Filtering

This paper describes a novel road-matching method designed to support the real-time navigational function of cars for advanced systems applications in the area of driving assistance. This method provides an accurate estimation of position for a vehicle relative to a digital road map using Belief Theory and Kalman filtering. Firstly, an Extended Kalman Filter combines the DGPS and ABS sensor measurements to produce an approximation of the vehicle’s pose, which is then used to select the most likely segment from the database. The selection strategy merges several criteria based on distance, direction and velocity measurements using Belief Theory. A new observation is then built using the selected segment, and the approximate pose adjusted in a second Kalman filter estimation stage. The particular attention given to the modeling of the system showed that incrementing the state by the bias (also called absolute error) of the map significantly increases the performance of the method. Real experimental results show that this approach, if correctly initialized, is able to work over a substantial period without GPS.Maan El Badaoui El Najjar was born in Tripoli-Lebanon in 1975. He received his engineer diploma and his M.S. degree in control system and automation from the Institut National Polytechnique de Grenoble, France, in 1999 and 2000 respectively and his Ph.D. degree in control system from the Université de Technologie de Compiègne, France, in 2003. He is research and teaching associate at the Heudiasyc laboratory of the Université de Technologie de Compiègne. His current research interests include robot localization, map-aided navigation techniques, sensor fusion and Bayesian estimation techniques.Philippe Bonnifait graduated from the Ecole Superieure d’Electronique de l’Ouest, France, in 1992 and received the Ph.D. degree in automatic control and computer science from the Ecole Centrale de Nantes, France, in 1997. He joined the Institut de Recherche en Communications et Cybernétique de Nantes (IRCCyN UMR 6597), France, in 1993. Since September 1998, he is with Heudiasyc UMR 6599, France, and he is Assistant Professor at the Université de Technologie de Compiègne. His current research interests are in intelligent outdoor vehicles, with particular emphasis on applications to dynamic localisation.     

建模样式:一种评估软件体系结构非功能属性的方法

软件体系结构设计是软件过程中最为重要的环节之一.在设计阶段完成对软件体系结构非功能属性的评估,对于高质量软件产品的开发非常重要.通过对统一建模语言(UML)的扩展,提出了“建模样式”用于在软件设计阶段对软件体系结构非功能属性进行评估,并结合“可用性链”建模样式在分析软件体系结构“单消息分发-多消息处理”可用性中的应用,给出了建模样式的使用示例.同时,针对建模样式的应用,还提出了“建模知识库”用于管理和维护建模样式,提供各建模样式中标签的参考值.基于UML的建模样式以及建模知识库的使用,可以简化对软件体系结构非功能属性评估的复杂度和工作量,使其可以为软件开发人员所用,并融入到高质量软件开发过程中.     

风险驱动的软件项目缓冲分配方法

提出一种风险驱动的项目缓冲分配方法,并开发了相应的项目模拟执行工具对方法进行验证.方法旨在通过综合考虑软件项目的风险因素、任务之间的进度约束和资源约束对项目的可用缓冲进行合理分配.模拟实验的结果表明,在风险较高的软件开发项目中,该方法相对于关键链项目管理中尾部集中的项目缓冲分配方法,可确保在对项目平均执行工期产生较小影响的同时,显著降低项目执行时计划变更的发生频率.该缓冲分配方法与项目模拟工具可以帮助软件项目经理确定合适的项目缓冲时间长度以及缓冲分配方案,进而提高软件项目计划的可信性和执行的稳定性.     

Reducing The Latency In Head-Mounted Displays By A Novel Prediction Method Using Grey System Theory

In this paper we propose a novel prediction method for the head motion using Grey System theory, where a 6D tracker is attached to an HMD on a user's head in virtual reality applications. Our prediction method using Grey System Model can greatly reduce the latency by at least one half and reduce image jittering. A system latency below 100 ms or even 50 ins can be achieved, even though without prediction the latency is around 200 ms. Using 6 points in prediction with Grey System Model is currently the best in tracker prediction as we tried from 2 points to 10 points. In order to measure the latency, we also propose a way to measure it in an HMD system precisely and conveniently. During the process, we have implemented four different prototypes respectively on a PC486, a SUN SparcStation10, an SGI IndigoR4000, and a high performance computer image generator. The computation complexity of our prediction method is relatively low and therefore real time requirement is easily met.     

The W-Process for Software Product Evaluation: A Method for Goal-Oriented Implementation of the ISO 14598 Standard

The importance of software product evaluations will grow with the awareness of the need for better software quality. The process to conduct such evaluations is crucial to get evaluation results that can be applied and meet customers' expectations. This paper reviews a well-known evaluation process: the ISO 14598 standard. The review focuses on the difficulties in selecting and evaluating the appropriate evaluation techniques. The review shows that the standard has problems in applying evaluation processes in practice due to insufficient attention to goal definition and to relationships between activities being implicit. Also, the standard ignores the trade-off between goals and resources and pays insufficient attention to feedback. To address these deficiencies, the W-process is proposed. It extends the standard through an improved process structure and additional guidelines.