禁忌搜索解决烘干窑调度问题

针对烘干窑生产周期长、成本高的问题,为提高其生产效率,缩短生产周期,对烘干窑的生产调度进行了优化,描述了一个现实中存在的烘干窑调度问题,提出了一种改进的融入了回溯思想的禁忌搜索算法,并给出了算法优化前后的生产计划比较。实际应用结果显示,该算法能有效地缩短生产周期,减少生产成本,提高设备利用率和合同准时率。     

ASIC测试生成和可测性分析系统ATGTA

本文介绍了一个面向非扫描设计的实用的ASIC测试生成和可测性分析系统—ATG－TA.它采用功能块组同步时序电路模型和功能块引腿固定故障模型．可接收四种常用语言描述的电路网表．用FDCM方法引导测试生成过程，用DRFM方法识别组合冗余故障，通过测度分析与规则判定相结合识别时序电路中的不可测故障．用G－F二值算法按有限回溯测试模式产生方法推导测试向量．反向追踪时，采用宽度和深度动态交替代先策略．ATGTA已实际用于四万门以内的非扫描单双向ASIC芯片，效果良好．     

收缩候选回溯集的有状态动态偏序归约方法

在验证多线程并发程序时,将基于无状态或有状态搜索的软件模型检测与动态偏序归约方法相结合,能大幅缩减待验证程序的状态空间,而动态偏序归约需不断利用当前候选回溯集更新相应回溯集,导致更新回溯集的计算成本过高。为此,形式化定义收缩候选回溯集,消除原候选回溯集中满足同一回溯条件的冗余迁移。针对各交织的回溯点,使用当前收缩候选回溯集更新相应回溯集,实现基于有状态动态偏序归约方法的并发多线程程序验证。实验结果表明,与现有动态偏序归约方法相比,该方法能减少遍历迁移数,加速回溯集更新,提高动态软件模型检测效率。     

Efficient data structures for backtrack search SAT solvers

The implementation of efficient Propositional Satisfiability (SAT) solvers entails the utilization of highly efficient data structures, as illustrated by most of the recent state-of-the-art SAT solvers. However, it is in general hard to compare existing data structures, since different solvers are often characterized by fairly different algorithmic organizations and techniques, and by different search strategies and heuristics. This paper aims the evaluation of data structures for backtrack search SAT solvers, under a common unbiased SAT framework. In addition, advantages and drawbacks of each existing data structure are identified. Finally, new data structures are proposed, that are competitive with the most efficient data structures currently available, and that may be preferable for the next generation SAT solvers.     

Statistical Regimes Across Constrainedness Regions

Much progress has been made in terms of boosting the effectiveness of backtrack style search methods. In addition, during the last decade, a much better understanding of problem hardness, typical case complexity, and backtrack search behavior has been obtained. One example of a recent insight into backtrack search concerns so-called heavy-tailed behavior in randomized versions of backtrack search. Such heavy-tails explain the large variance in runtime often observed in practice. However, heavy-tailed behavior does certainly not occur on all instances. This has led to a need for a more precise characterization of when heavy-tailedness does and when it does not occur in backtrack search. In this paper, we provide such a characterization. We identify different statistical regimes of the tail of the runtime distributions of randomized backtrack search methods and show how they are correlated with the “sophistication” of the search procedure combined with the inherent hardness of the instances. We also show that the runtime distribution regime is highly correlated with the distribution of the depth of inconsistent subtrees discovered during the search. In particular, we show that an exponential distribution of the depth of inconsistent subtrees combined with a search space that grows exponentially with the depth of the inconsistent subtrees implies heavy-tailed behavior. Research supported by the Intelligent Information Systems Institute, Cornell University (AFOSR grant F49620-01-1-0076), MURI (AFOSR grant F49620-01-1-0361) and Ministerio de Educación y Ciencia (TIN-2004 grant 07933-C03-03). We thank the anonymous reviewers for their insightful comments.     

一种实时异构系统的集成动态调度算法

提出了一种实时异构系统的集成动态调度算法.该算法通过一个新的任务分配策略以及软实时任务的服务质量QoS(quality of service)降级策略,不仅以统一方式完成了对实时异构系统中硬、软实时任务的集成动态调度,而且提高了算法的调度成功率.同时,还进行了大量的模拟研究.这些模拟以传统的近视算法为基准,将其应用在实时异构系统集成动态调度时的调度成功率与新算法进行比较,模拟结果表明,在多种任务参数取值下,新算法的调度成功率均高于传统的近视算法.     

Optimum cost design of welded box beams with longitudinal stiffeners using advanced backtrack method

The use of longitudinal stiffeners in box girders loaded in bending results in savings in weight and cost. To study these savings the optimized box beams without and with stiffeners are compared to each other. The minimum cross-sectional area design can be solved analytically. A cost function is defined containing material and fabrication (welding) costs. This function is nonlinear in the structural dimensions to be optimized, therefore an advanced backtrack method is worked out and applied. An illustrative numerical example shows the savings. Received June 30, 1999     

多处理器并行EDPF优化实时调度算法

实时多处理器系统的任务调度问题始终都是一个重要课题。针对该系统须保证任务截止期和有效性的特点,提出了一种并行EDPF（Earliest Deadline and Processing Time First）优化调度算法。该算法适用于可并行任务,并在考虑到了任务集的截止期和资源因素基础上,加入了运行时间因素,达到了减少调度返回次数以及提高有效性的目的。最后通过大量的仿真,分析了一些必要参数对调度成功率的影响,并通过比较证明了该算法明显优于Myopic算法。     

Automatic test pattern generation on parallel processors

Test generation for combinational circuits is an important step in the VLSI design process. Unfortunately, the problem is highly computation-intensive and for circuits encountered in practice, test generation time can often be enormous. In this paper, we present a parallel formulation of the backtrack search algorithm called PODEM, which is a highly used algorithm for this problem. It is known that the sequential PODEM algorithm consumes most of its execution time in generating tests for ‘hard-to-detect’ (HTD) faults and is often unable to detect them even after a large number of backtracks. Our parallel formulation overcomes these limitations by dividing the search space and searching it concurrently using multiple processes.

We present a number of experimental results and show that these match our theoretical results presented elsewhere. We show that the search efficiency of the parallel algorithm improves and even beats that of the sequential algorithm as the ‘hardness’ of a fault increases. We present speedup results and performance analyses of our formulation on a 128 processor Symult s2010 multicomputer. We also present preliminary results on a network of Sun workstations. Our results show that parallel search techniques provides good speedups as well as high fault coverage of the HTD faults in reasonable time when compared to the uniprocessor implementation. Our experimental validation of most of our theoretical results builds confidence in the following theoretical prediction: our parallel formulation of PODEM is highly scalable on a variety of commercially-available, large MIMD parallel processors (in additions to the ones with which we experimented).     

应用搜索原理解n皇后问题算法分析及优化

n皇后问题是非结构化的问题,人工智能中的搜索策略——回溯法是解决这类问题的有效方法。本文介绍了利用回溯法求解n皇后问题的基本思想以及实现方法,并对算法提出了优化的方法,使得算法的运行效率更高。