离散非线性系统Worst-Case辨识——小波逼近法

利用小波逼近的软阈（Ｓｏｆｔ－Ｔｈｒｅｓｈｏｌｄｉｎｇ）方法，研究了离散非线性系统的Ｗｏｒｓｔ－Ｃａｓｅ辨识问题．证明了该算法在Ｗｏｒｓｔ－Ｃａｓｅ误差下的拟最优性和光滑性；估计了该算法的Ｗｏｒｓｔ－Ｃａｓｅ误差：给出了存在鲁棒收敛的辨识算法的充要条件；最后，证明了小波网逼近算法是鲁棒收敛的．

A Genetic Approach to Analyze Algorithm Performance Based on the Worst-Case Instances

Search-based software engineering has mainly dealt with automated test data generation by metaheuristic search techniques. Similarly, we try to generate the test data (i.e., problem instances) which show the worst case of algorithms by such a technique. In this paper, in terms of non-functional testing, we re-define the worst case of some algorithms, respectively. By using genetic algorithms (GAs), we illustrate the strategies corresponding to each type of instances. We here adopt three problems for examples;the sorting problem, the 0/1 knapsack problem (0/1KP), and the travelling salesperson problem (TSP). In some algorithms solving these problems, we could find the worst-case instances successfully;the successfulness of the result is based on a statistical approach and comparison to the results by using the random testing. Our tried examples introduce informative guidelines to the use of genetic algorithms in generating the worst-case instance, which is defined in the aspect of algorithm performance.

Measuring Policy Performance in Online Pricing with Offline Data:Worst-case Perspective and Bayesian Perspective

The problems of online pricing with offline data,among other similar online decision making with offline data problems,aim at designing and evaluating online pricing policies in presence of a certain amount of existing offline data.To evaluate pricing policies when offline data are available,the decision maker can either position herself at the time point when the offline data are already observed and viewed as deterministic,or at the time point when the offline data are not yet generated and viewed as stochastic.We write a framework to discuss how and why these two different positions are relevant to online policy evaluations,from a worst-case perspective and from a Bayesian perspective.We then use a simple online pricing setting with offline data to illustrate the constructions of optimal policies for these two approaches and discuss their differences,especially whether we can decompose the searching for the optimal policy into independent subproblems and optimize separately,and whether there exists a deterministic optimal policy.

Worst-case total dose radiation effect in deep-submicron SRAM circuits

The worst-case radiation effect in deep-submicron SRAM （static random access memory） circuits is studied through theoretical analysis and experimental validation. Detailed analysis about the radiation effect in different parts of circuitry is presented. For SRAM cells and a sense amplifier which includes flip-flop structures, their failure level against ionizing radiation will have a connection with the storage state during irradiation. They are inclined to store or read the same state as the one stored during irradiation. Worst-case test scheme for an SRAM circuit is presented, which contains a write operation that changes the storage states into the opposite ones after irradiation and then a read operation with opposite storage states. An irradiation experiment is designed for one 0.25 μm SRAM circuit which has a capacity of I k×8 bits. The failure level against ionizing radiation concluded from this test scheme （150 krad（Si）） is much lower than the one from the simplest test scheme （1 Mrad（Si））. It is obvious that the failure level will be overestimated if the simplest test scheme is chosen as the test standard for SRAM circuits against ionizing radiation.

Robust mismatched filtering algorithm for passive bistatic radar using worst-case performance optimization

Passive bistatic radar detects targets by exploiting available local broadcasters and communication transmissions as illuminators, which are not designed for radar. The signal usually contains a time-varying structure, which may result in high-level range ambiguity sidelobes. Because the mismatched filter is effective in suppressing sidelobes, it can be used in a passive bistatic radar. However, due to the low signal-to-noise ratio in the reference signal, the sidelobe suppression performance seriously degrades in a passive bistatic radar system. To solve this problem, a novel mismatched filtering algorithm is developed using worst-case performance optimization. In this algorithm, the influence of the low energy level in the reference signal is taken into consideration, and a new cost function is built based on worst-case performance optimization. With this optimization, the mismatched filter weights can be obtained by minimizing the total energy of the ambiguity range sidelobes. Quantitative evaluations and simulation results demonstrate that the proposed algorithm can realize sidelobe suppression when there is a low-energy reference signal. Its effectiveness is proved using real data.

A Worst-Case Risk Measure by G-VaR

G-VaR,which is a type of worst-case value-at-risk(VaR),is defined as measuring risk incorporating model uncertainty.Compared with most extant notions of worst-case VaR,G-VaR can be computed using an explicit formula,and can be applied to large portfolios of several hundred dimensions with low computational cost.We also apply G-VaR to robust portfolio optimization,thereby providing a tractable means to facilitate optimal allocations under the condition of market ambiguity.

A HEURISTIC FOR F3/bi= b/C_(max) AND ITSWORST-CASE ANALYSIS

This paper describes a heuristic for solving F3/bi = b/Cmax scheduling problem. This algorithm first uses the Johnson’s algorithm solving F2Cmax, then, presents revised algorithm to solve F3/bi = b/Cmax. Lastly, an O(n log n) time heuristic is presented which generates a schedule with length at most 3/2 times that of an optimal schedule, for even number n 4, and 3/2 + 1/(2n) times that of an optimal schedule, for odd number n 4. These bounds are tight.

Worst-Case Finish Time Analysis for DAG-Based Applications in the Presence of Transient Faults

Tasks in hard real-time systems are required to meet preset deadlines, even in the presence of transient faults and hence the analysis of worst-case finish time （WCFT） must consider the extra time incurred by re-executing tasks that were faulty. Existing solutions can only estimate WCFT and usually result in significant under- or over-estimation. In this work, we conclude that a sufficient and necessary condition of a task set experiencing its WCFT is that its critical task incurs all expected transient faults. A method is presented to identify the critical task and WCFT in O（IVI ＋ IEI） where IVI and IEI are the number of tasks and dependencies between tasks, respectively. This method finds its application in testing the feasibility of directed acyclic graph （DAG） based task sets scheduled in a wide variety of fault-prone multi-processor systems, where the processors could be either homogeneous or heterogeneous, DVS-capable or DVS-incapable, etc. The common practices, which require the same time complexity as the proposed critical-task method, could either underestimate the worst case by up to 25%, or overestimate by 13%. Based on the proposed critical-task method, a simulated-annealing scheduling algorithm is developed to find the energy efficient fault-tolerant schedule for a given DAG task set. Experimental results show that the proposed critical-task method wins over a common practice by up to 40% in terms of energy saving.

A Worst-Case Execution Time Analysis Approach Based on Independent Paths for ARM Programs

To overcome disadvantages of traditional worst-case execution time （WCET） analysis approaches, we propose a new WCET analysis approach based on independent paths for ARM programs. Based on the results of program flow analysis, it reduces and partitions the control flow graph of the program and obtains a directed graph. Using linear combinations of independent paths of the directed graph, a set of feasible paths can be generated that gives complete coverage in terms of the program paths considered. Their timing measurements and execution counts of program segments are derived from a limited number of measurements of an instrumented version of the program. After the timing measurement of the feasible paths are linearly expressed by the execution times of program seg-ments, a system of equations is derived as a constraint problem, from which we can obtain the execution times of program segments. By assigning the execution times of program segments to weights of edges in the directed graph, the WCET estimate can be calculated on the basis of graph-theoretical techniques. Comparing our WCET estimate with the WCET measurement obtained by the exhaustive measurement, the maximum error ratio is only 8.259 3 %. It is shown that the proposed approach is an effective way to obtain the safe and tight WCET estimate for ARM programs.

Worst-Case Investment Strategy with Delay

This paper considers a worst-case investment optimization problem with delay for a fund manager who is in a crash-threatened financial market. Driven by existing of capital inflow/outflow related to history performance, we investigate the optimal investment strategies under the worst-case scenario and the stochastic control framework with delay. The financial market is assumed to be either in a normal state(crash-free) or in a crash state. In the normal state the prices of risky assets behave as geometric Brownian motion, and in the crash state the prices of risky assets suddenly drop by a certain relative amount, which induces to a dropping of the total wealth relative to that of crash-free state. We obtain the ordinary differential equations satisfied by the optimal investment strategies and the optimal value functions under the power and exponential utilities, respectively. Finally, a numerical simulation is provided to illustrate the sensitivity of the optimal strategies with respective to the model parameters.

Better-Than-Worst-Case Design: Progress and Opportunities

Today, designers are forced to reduce performance and increase power requirements in order to reserve larger margins that are required due to the greater variability introduced by smaller feature sizes and manufacturing variations of modern IC designs. The better-than-worst-case design can both address the variability problem and achieve higher performance/energy efficiency than the worst-case design. This paper surveys the progress to date, provides a snapshot of the most representative methods in this field, and discusses the future research directions of the better-than-worst-case design.

CRISIS FOCUS—Worst-case Scenario

Caught up in the whirlwind of the global fi-nancial crisis since last October, governments worldwide have rushed to adapt to the drastic economic changes that have occurred both in their own countries and internationally. Anticipating that this year may witness heavier storms, Wang Jian, Secretary General of the China Society of Macroeconomics under the National Development and Reform Commission, warned about some trends in China’s macro-control efforts in 2009. Edited excerpts of his interview with China Securities Journal follow.

Research on Multi-Core Processor Analysis for WCET Estimation

Real-time system timing analysis is crucial for estimating the worst-case execution time(WCET)of a program.To achieve this,static or dynamic analysis methods are used,along with targeted modeling of the actual hardware system.This literature review focuses on calculating WCET for multi-core processors,providing a survey of traditional methods used for static and dynamic analysis and highlighting the major challenges that arise from different program execution scenarios on multi-core platforms.This paper outlines the strengths and weaknesses of current methodologies and offers insights into prospective areas of research on multi-core analysis.By presenting a comprehensive analysis of the current state of research on multi-core processor analysis for WCET estimation,this review aims to serve as a valuable resource for researchers and practitioners in the field.

基于优先级时间Petri网的实时嵌入式多核系统分析

已有的基于点区间优先级时间Petri网分析实时嵌入式多核系统的工作,存在以下不足:(1)点区间优先级时间Petri网只考虑每个任务的执行时间是一个固定值的情况,而更多的实际应用中每个任务的执行时间是在一个区间范围内,因此不能模拟这些应用;(2)没有实现从任务依赖图到点区间优先级时间Petri网的自动转化,不便于工程设计人员使用;(3)没有考虑任务间互斥访问共享变量的情况.为此,定义了优先级时间Petri网(Pri-TPN)以弥补第1个不足;定义带有资源分配与优先级的任务依赖图(TDG-RAP)以弥补第3个不足;给出从TDG-RAP到Pri-TPN的转化规则与算法以弥补第2个不足,以及基于Pri-TPN分析任务最坏执行时间与系统死锁的算法;开发工具软件,方便工程设计人员使用.

资源限制性并行任务固定优先级可调度性分析

异构多核平台的发展,导致并行任务需要执行在具有多样性资源的多核平台上.虽然,并行任务的某个程序片段只能在规定的资源上执行,但是这样操作可以充分利用各类不同资源的特性,达到更加快速节能处理任务的目的.同时,具有资源限制任务的可调度性研究在实时嵌入式系统领域已有一定的研究成果,但是采用的任务模型相对简单,分析方法不够精确.鉴于此,本文对具有资源限制性的并行任务在全局固定优先级调度策略下的可调度性问题进行了研究,基于单并行任务的分析方法提出了基于全局固定优先级调度策略的分析方法.首先,基于分解策略提出了高优先级任务干涉的分析方法.然后,将高优先级任务干涉分析方法和单并行任务提出的路径抽象技术相结合,推导出并行任务的最差响应时间算法.最后,通过仿真实验进行验证所提出的算法在可调度性、精确度层面的性能.实验结果表明,提出的算法在各个参数下的接受率实验符合实验预期,分析时间相对降低,但平均分析时间仍然在离线分析的可接受范围内,提出的算法能够对实时系统并行软件设计提供一定的指导价值.

加权Korobov空间中多元L_(∞)-逼近问题的指数收敛易处理性

该文主要研究最坏框架下加权Korobov空间中多元L_(∞)-逼近问题的指数易处理性.多元逼近问题中的算法使用的信息取自由线性泛函组成的线性信息类Λall和函数值组成的标准信息类Λstd.该问题的指数收敛-拟多项式易处理性和指数收敛-一致弱易处理性之前并没有被研究,该文最终通过两个权参数序列给出使得多元L_(∞)-逼近问题具有这两种指数收敛易处理性的充分必要条件.

参数有界不确定下电磁分支电路阻尼优化研究

电磁分支电路阻尼是一种轻量化振动控制手段。经典参数优化方法通常只适用于确定性参数模型,当系统参数发生变化时,其抑振有效性可能会大大降低。考虑被控结构存在刚度有界不确定情况下,对串联型电阻-电感-电容电磁分支电路阻尼器进行最坏情况下的优化设计。采用一种改进型等峰优化设计代数方法,可以简洁地推导出分支电路电学参数最优值的近似解析表达式。最后,通过与经典等峰设计方法进行比较,验证了改进型参数优化设计在控制参数不确定性系统振幅上的有效性。

关于音频带通滤波电路的最坏情况分析

音频带通滤波电路是机载通信系统音频采集前端重要组成部分,对通信系统语音信号可靠传输发挥重要作用。本文通过Pspice软件对音频带通滤波电路进行了最坏情况分析,考虑了元器件容差参数组合中导致性能最差的情况,分析了不同元器件容差参数下音频带通滤波电路输出特性,找到符合设计要求的元器件容差参数,提升了音频带通滤波电路实际应用的可靠性。

基于多级一致性协议的多核处理器WCET分析方法

由于多核处理器优越的计算性能,多核处理器现已广泛应用在嵌入式实时系统中.相对于单核处理器,多核处理器存在资源共享竞争、并行任务干扰等因素,尤其是缓存(Cache)一致性问题,导致任务最坏情况执行时间(worst-case execution time,WCET)的预测更加困难.基于以上因素,提出基于多级一致性协议的多核处理器WCET分析方法.该方法针对多级一致性协议体系架构,提出多级一致性域的概念,将多核处理器的数据访问分为域内访问和跨域访问2个层次,根据Cache读写策略和MESI(modify exclusive shared invalid)一致性协议,得出一致性域内部和跨一致性域的Cache状态更新函数,从而实现多级一致性协议嵌套情况下的WCET分析.实验结果表明,在改变Cache配置参数的情况下,该方法分析结果与GEM5仿真结果的变化趋势一致,经过相关性分析,GEM5仿真结果与该方法分析结果相关性系数不低于0.98;在分析精度方面,该方法的平均过估计率为1.30,相比现有方法降低了0.78.

计算机辅助舵面装配公差分析与优化设计

针对飞机舵面装配模型,以翼尖扰动量最小为设计目标,以舵面各零件尺寸及装配约束定义三维空间尺寸链,基于商用软件CETOL建立装配公差分析模型.通过敏感度和贡献度分析选择影响测量目标的关键尺寸,对不同精度的关键尺寸进行最坏情况分析,从尺寸精度、装配工艺及产品成本等方面进行评估,确定关键尺寸合理的公差范围.根据分析结果,除了确定关键尺寸的公差值,还可适当降低非关键尺寸的精度.将装配公差设计方法同工程实际相结合,在确定设计公差、降低制造成本和提高装配精度等方面具有广泛的应用前景.