Quantifying the impact of uncertainty in embedded systems mapping for NoC based architectures

We describe a modeling framework to capture and account for uncertainty in design parameters in embedded systems. We then develop an uncertainty-aware solution to the problem of mapping in embedded systems that uses Network-on-Chip (NoC) based architecture platforms. The problem of mapping is formulated as a multi-objective - reliability, performance, and energy consumption - optimization problem. To solve this problem, we propose a solution based on the NSGA-II genetic algorithm and Monte Carlo simulation techniques. The solution is implemented as a computer-aid design tool that can generate robust 3D Pareto frontiers in the solution space formed by the design objectives of reliability, performance, and energy consumption. Comparison to several state-of-the-art models and solutions for the mapping problem, indicate that significant differences in the actual values of the design attribute of interest exist when one considers uncertainty in design parameters. For example, in the case of mapping with reliability as the only objective, 10% uncertainty in design parameters can lead to a 10.06% difference in MTTF estimation. In the case of mapping with execution time and energy consumption as objectives, the difference in 2D Pareto frontiers due to 10% uncertainty in design parameters can be up to 7.9%. These differences are important because they can mislead the overall optimization process of mapping toward suboptimal solution points. The DESUU-NOC tool that implements the proposed multi-objective mapping algorithm has as a main feature and contribution of this paper the ability to generate 3D Pareto frontiers comprised of robust solution points.     

UMOTS: an uncertainty-aware multi-objective genetic algorithm-based static task scheduling for heterogeneous embedded systems

Increasing manufacturing process variations due to aggressive technology scaling in addition to heterogeneity in design components are expected to cause serious challenges for future embedded system design steps including task scheduling. Process variation effects along with increased complexity in embedded applications result in design uncertainties, which in turn, reduce the accuracy and efficiency of traditional design approaches with deterministic values for the design component parameters. In this paper, a multi-objective task scheduling framework is proposed for embedded systems considering uncertainties in both hardware and software component parameters. The tasks which are modeled as a task graph are scheduled on a specific hardware platform consisting of processors and communication parts. Uncertainty is considered in both software (task parameters) and hardware (processor and communication parameters) of the embedded system. UMOTS takes advantages of a Monte-Carlo-based approach within a multi-objective genetic algorithm to handle the uncertainties in model parameters. The proposed approach finds the Pareto frontier, which is robust against uncertainties, in the objective space formed by performance, energy consumption, and reliability. The efficiency of UMOTS is investigated in the experimental results using real-application task graphs. In terms of Scheduling Length Ratio (SLR) and speedup, UMOTS provides 27.8% and 28.6% performance improvements in comparison to HSHD, one state-of-the-art task scheduling algorithm. Additionally, UMOTS, which is based on a multi-objective genetic optimization algorithms, finds robust Pareto frontier with 1%, 5% and 10% uncertainty in design indicators with respect to design limitations.

     

动态可靠性约束的多阶段测试资源分配研究

为满足测试资源分配过程中用户对软件可靠性的需求,构建一种动态可靠性约束的多阶段多目标测试资源分配模型DRC-MSMOTRA。从理论上分析不同阶段满足可靠性约束的测试时间下限并设计相应的种群初始化策略,结合参数估计、加权归一化方法和多目标差分进化,提出一种动态可靠性约束的多阶段多目标测试资源分配算法MS-DRC-GDE3。实验结果表明,与MSMOTRA模型相比,DRC-MSMOTRA模型在2种不同规模的软件系统上所获解的覆盖值分别提高约62和59个百分点,与MS-GDE3算法相比,MS-DRC-GDE3算法在2种软件系统上所获解的覆盖值分别提高约69和80个百分点,即所提模型和算法能够根据用户对可靠性的需求来为用户提供更多更优的测试资源分配方案。     

Automated design space exploration of multi-cycle transient fault detectable datapath based on multi-objective user constraints for application specific computing

A novel automated design space exploration (DSE) approach of multi-cycle transient fault detectable datapath based on multi-objective user constraints (power and delay) for application specific computing is presented in this paper. To the best of the authors’ knowledge, this is the first work in the literature to solve this problem. The presented approach, driven by bacterial foraging optimization (BFO) algorithm provides easy flexibility to change direction in the design space through tumble/swim actions if a search path is found ineffective. The approach is highly capable of reaching true Pareto optimal curve indicated by the closeness of our non-dominated solutions to the true Pareto front and their uniform distribution over the Pareto curve (implying diversity). The contributions of this paper are as follows: (a) novel exploration approach for generating a high quality fault detectable structure based on user provided requirements of power-delay, which is capable of transient error detection in the datapath; (b) novel fault detectable algorithm for handling single and multi-cycle transient faults.The results of the proposed approach indicated an average improvement in Quality of Results (QoR) of >9% and reduction in hardware usage of >23% compared to recent approaches that are closer in solving a similar objective.     

基于FDI算法在软件测试实践中的应用

软件测试对于软件系统的性能以及功能都有很重要的意义,是保证软件可靠运行的关键.在软件测试的实践应用中,对于软件故障定位时,提出了基于谓词统计故障定位的算法,也就是FDI频率差异积分算法.在软件测试实践中采用基于FDI频率差异积分算法,可以很好地监控软件程序,测试软件的覆盖率以及执行时间等内存占用情况,并找到软件的故障瓶颈,以便采取更好的方法改进软件性能.探讨了实践中基于FDI频率差异积分算法在软件测试内的应用.     

基于覆盖与故障注入的飞控软件测试技术研究

无人机飞控软件是典型的实时嵌入式软件系统,其可靠性、安全性测试与评估是军用软件保障工作与无人机技术发展中的重点与难点。针对飞控软件的特点,介绍基于覆盖与故障注入的测试方法．分析其测试与可靠性评估中的关键技术,并简要介绍应用于测试数据分析过程的软件可靠性建模工具MEADEP的构成与建模方法。实践证明对安全关键软件严格的测试与评估可大大降低错误隐藏数,减少不必要的经济损失与灾难性事件发生。     

A framework for modular analysis and exploration of heterogeneous embedded systems

The increasing complexity of heterogeneous systems-on-chip, SoC, and distributed embedded systems makes system optimization and exploration a challenging task. Ideally, a designer would try all possible system configurations and choose the best one regarding specific system requirements. Unfortunately, such an approach is not possible because of the tremendous number of design parameters with sophisticated effects on system properties. Consequently, good search techniques are needed to find design alternatives that best meet constraints and cost criteria. In this paper, we present a compositional design space exploration framework for system optimization and exploration using SymTA/S, a software tool for formal performance analysis. In contrast to many previous approaches pursuing closed automated exploration strategies over large sets of system parameters, our approach allows the designer to effectively control the exploration process to quickly find good design alternatives. An important aspect and key novelty of our approach is system optimization with traffic shaping.     

A synthesis of logic and bio-inspired techniques in the design of dependable systems

Much of the development of model-based design and dependability analysis in the design of dependable systems, including software intensive systems, can be attributed to the application of advances in formal logic and its application to fault forecasting and verification of systems. In parallel, work on bio-inspired technologies has shown potential for the evolutionary design of engineering systems via automated exploration of potentially large design spaces. We have not yet seen the emergence of a design paradigm that effectively combines these two techniques, schematically founded on the two pillars of formal logic and biology, from the early stages of, and throughout, the design lifecycle. Such a design paradigm would apply these techniques synergistically and systematically to enable optimal refinement of new designs which can be driven effectively by dependability requirements. The paper sketches such a model-centric paradigm for the design of dependable systems, presented in the scope of the HiP-HOPS tool and technique, that brings these technologies together to realise their combined potential benefits. The paper begins by identifying current challenges in model-based safety assessment and then overviews the use of meta-heuristics at various stages of the design lifecycle covering topics that span from allocation of dependability requirements, through dependability analysis, to multi-objective optimisation of system architectures and maintenance schedules.     

Physical programming for preference driven evolutionary multi-objective optimization

Preference articulation in multi-objective optimization could be used to improve the pertinency of solutions in an approximated Pareto front. That is, computing the most interesting solutions from the designer's point of view in order to facilitate the Pareto front analysis and the selection of a design alternative. This articulation can be achieved in an a priori, progressive, or a posteriori manner. If it is used within an a priori frame, it could focus the optimization process toward the most promising areas of the Pareto front, saving computational resources and assuring a useful Pareto front approximation for the designer. In this work, a physical programming approach embedded in an evolutionary multi-objective optimization is presented as a tool for preference inclusion. The results presented and the algorithm developed validate the proposal as a potential tool for engineering design by means of evolutionary multi-objective optimization.     

基于源代码分析的嵌入式软件高速仿真

现有嵌入式软件仿真工具的应用受到仿真速度等不足的限制。在一些领域中,此处介绍的方法将是更好的解决方案。该方法使用自行开发的分析器将嵌入式软件的源代码转换为ANSIC／C＋＋代码,并将其与仿真专用的函数库编译连接。最终生成的PC上的可执行程序就是目标嵌入式软件及其硬件平台的模型。由于具备可以达到目标系统运行速度数百倍的仿真速度,和合理的仿真精确度,该方法可以在设计空间探索阶段和算法级嵌入式编程中取代常用的开发工具包以及ISS,并有效缩短开发周期。     

MO-PSE: Adaptive multi-objective particle swarm optimization based design space exploration in architectural synthesis for application specific processor design

Architectural synthesis has gained rapid dominance in the design flows of application specific computing. Exploring an optimal design point during architectural synthesis is a tedious task owing to the orthogonal issues of reducing exploration time and enhancing design quality as well as resolving the conflicting parameters of power and performance. This paper presents a novel design space exploration (DSE) methodology multi-objective particle swarm exploration MO-PSE, based on the particle swarm optimization (PSO) for designing application specific processor (ASP). To the best of the authors’ knowledge, this is the first work that directly maps a complete PSO process for multi-objective DSE for power-performance trade-off of application specific processors. Therefore, the major contributions of the paper are: (i) Novel DSE methodology employing a particle swarm optimization process for multi-objective tradeoff, (ii) Introduction of a novel model for power parameter used during evaluation of design points in MO-PSE, (iii) A novel fitness function used for design quality assessment, (iv) A novel mutation algorithm for improving DSE convergence and exploration time, (v) Novel perturbation algorithm to handle boundary outreach problem during exploration and (vi) Results of comparison performed during multiple experiments that indicates average improvement in the quality of results (QoR) achieved is around 9% and average reduction in exploration time of greater than 90% compared to recent genetic algorithm (GA) based DSE approaches. The paper also reports results based on the variation and impact of different PSO parameters such as swarm size, inertia weight, acceleration coefficient, and termination condition on multi-objective DSE.     

Automated design of hierarchical intranets

This paper describes the use of i-CAD, a prototype tool for automatically synthesizing application specific intranets. i-CAD is a novel intranet computer-aided design software tool, and its ultimate goal is to concurrently design hierarchical network topologies and data management (content distribution) systems for data-intensive multimedia intranets. The prototype software tool introduced here synthesizes a three-level intranet architecture that entails minimal installation cost and yet enables all an intranet's clients to perform their tasks with acceptable performance. The tool chooses network technologies (hardware resources and protocols) based on requirements specified by the user and determines the topology. An evolutionary approach is used to search the design space for a minimal cost three-level network. The experimental results for several network design problems described here indicate the effectiveness of the prototype network tool in finding good designs from a large design space in a reasonable amount of time.     

Efficient multi-level fault simulation of HW/SW systems for structural faults

In recent technology nodes,reliability is increasingly considered a part of the standard design flow to be taken into account at all levels of embedded systems design.While traditional fault simulation techniques based on low-level models at gate-and register transfer-level offer high accuracy,they are too inefficient to properly cope with the complexity of modern embedded systems.Moreover,they do not allow for early exploration of design alternatives when a detailed model of the whole system is not yet ava...     

基于RTEMS的软件容错系统设计

在空间环境下运行的计算机系统,高空辐射可能引发各种各样的异常或错误而导致故障。为了提高系统的可靠性,同时尽可能减少对系统实时性能的影响,需要对其进行有效的容错。针对节点和应用软件的故障检测和故障恢复进行研究与分析,提出了多种灵活有效的软件容错策略与设计方案,并基于四节点的多机硬件体系结构和RTEMS软件操作系统,设计并实现了一个系统原型。运行结果显示,该方案有效地提高了嵌入式实时系统的可靠性。     

基于SoC的嵌入式DRAM存储器内建自测试设计

内建自测试(Built-in Self Test,BIST)是测试片上系统(System on- Chip,SoC)中嵌入式存储器的重要技术;但是,利用BIST技术采用多种算法对嵌入式存储器进行测试仍面临诸多挑战;对此,提出了一种基于SoC的可以带有多种测试算法的嵌入式DRAM存储器BIST设计,所设计的测试电路可以复用状态机的状态,利用循环移位寄存器(Cyclic Shift Register,CSR)产生操作命令,利用地址产生电路产生所需地址;通过对3种BIST电路支持的算法,全速测试,面积开销3个方面的比较,表明提出的嵌入式DRAM存储器BIST设计在测试时间,测试故障覆盖率和测试面积开销等各方面都取得了较好的性能.     

基于FMEA/FTA的嵌入式软件故障诊断模型与应用

嵌入式软件测试过程往往会出现一些随机发生的关键疑难故障,定位这些故障将耗费大量的时间和精力,然而,目前对于嵌入式软件故障诊断技术的研究还比较少,而且尚未发现利用FMEA和FTA等可靠性分析技术以及贝叶斯网络技术的嵌入式软件故障诊断研究;因此,文中结合嵌入式软件的特点,运用FMEA和FTA综合分析方法,将贝叶斯网络技术与FMEA和FTA分别结合,提出一种基于贝叶斯网络FMEA/FTA的嵌入式软件故障诊断模型,并举出实例加以验证,指导软件测试人员找出故障;实例应用表明,这种模型有助于提高软件故障诊断效率和保证软件质量。     

嵌入式API测试套生成方法和技术

随着嵌入式计算机系统应用的不断扩展,嵌入式系统的可靠性引起了学术界和工业界的广泛关注,也提出了很多增进可靠性的方法和技术.然而,现有的方法和技术在测试套生成方面论述不多,所以在处理大批量嵌入式系统测试工作中遇到了挑战.讨论抽象测试套生成方法和适配技术,提出了LTS(labeled transition system)到BT(behavior tree)的转换算法,从而使TTCN(test and testing control notation)测试套可以通过转换嵌入式软件的LTS描述产生.还介绍了基于上述转换算法的嵌入式软件测试工具包,以及一个嵌入式物联网识读器测试案例研究.     

基于程序运行形式化分析的软件故障监控技术

关键软件要求极高的可靠性和安全性,然而当前的技术途径尚不能完全消除软件故障——软件测试不能保证软件正确性,模型检查等形式化验证技术也存在着诸多局限。文章提出了基于监控程序运行途径来捕获软件故障和验证程序性质正确性,构建了基于程序运行形式化分析的软件故障监控（SFMRFA）模型,在监控逻辑表达、程序插桩、multi-agent设计等关键技术的基础上开发计算机辅助工具来监控、分析和引导程序执行,使软件运行当中可测、可控,避免软件失效。     

基于软件体系结构和广义差分进化的测试资源动态分配算法

测试资源分配是软件测试中的一个基础问题,然而已有研究大都针对并串联模块软件模型而鲜有涉及体系结构软件模型。为此,首先针对可靠性和错误数动态变化的测试环境,构建了一种基于体系结构的多阶段多目标测试资源分配模型。然后基于参数重估计、种群重新初始化、广义差分进化和归一化加权求和设计了一种面向动态可靠性和错误数的多阶段多目标测试资源分配算法。最后,在仿真实验中,与已有的归一化加权求和多目标差分进化（WNS-MODE）算法进行对比,所提算法在不同结构的体系结构软件模型实例上所获解集更优,容量值提高了约16倍,覆盖值提高了约84个百分点,超体积提高了约6倍。实验结果表明,所提算法能够更好地适应可靠性和错误数的动态变化,可为体系结构软件模型的动态测试提供更多和更优的测试资源分配方案。