Simulated Annealing Based Parallel State Assignment of Finite State Machines

Simulated annealing is an effective tool in many optimization problems in VLSI CAD but its time requirements are prohibitive. In this paper, we report parallel algorithms for a well established simulated annealing based algorithm for the state assignment problem for finite state machines. Our parallel annealing strategy uses parallel moves by multiple processes, each performing local moves within its assigned subspace of the state encoding space. The novelty is in the dynamic repartitioning of the state space among processors, so that each processor gets to perform moves on the entire space over time. This is important to keep the quality of the parallel algorithm comparable to the serial algorithm. Our algorithm gives quality results within 0.05% of the serial algorithm on 64 processors. Our algorithms, ProperJEDI and PartJEDI, are portable across a wide range of MIMD machines. PartJEDI is memory scalable and is incrementally developed from ProperJEDI which is data replicated. For a large circuit, ProperJEDI reduces the runtime from 11 h to 10 min on a 64-processor machine. For the same circuit, PartJEDI reduces the runtime from 11 h to 20 min and memory requirement from 114 to 2 MB.     

A hardware Memetic accelerator for VLSI circuit partitioning

During the last decade, the complexity and size of circuits have been rapidly increasing, placing a stressing demand on industry for faster and more efficient CAD tools for VLSI circuit layout. One major problem is the computational requirements for optimizing the place and route operations of a VLSI circuit. Thus, this paper investigates the feasibility of using reconfigurable computing platforms to improve the performance of CAD optimization algorithms for the VLSI circuit partitioning problem. The proposed Genetic algorithm architecture achieves up-to 5× speedup over conventional software implementation while maintaining on average 88% solution quality. Furthermore, a reconfigurable computing based Hybrid Memetic algorithm improves upon this solution while using a fraction of the execution time required by the conventional software based approach.     

Effective Memetic Algorithms for VLSI design = Genetic Algorithms + local search + multi-level clustering

Combining global and local search is a strategy used by many successful hybrid optimization approaches. Memetic Algorithms (MAs) are Evolutionary Algorithms (EAs) that apply some sort of local search to further improve the fitness of individuals in the population. Memetic Algorithms have been shown to be very effective in solving many hard combinatorial optimization problems. This paper provides a forum for identifying and exploring the key issues that affect the design and application of Memetic Algorithms. The approach combines a hierarchical design technique, Genetic Algorithms, constructive techniques and advanced local search to solve VLSI circuit layout in the form of circuit partitioning and placement. Results obtained indicate that Memetic Algorithms based on local search, clustering and good initial solutions improve solution quality on average by 35% for the VLSI circuit partitioning problem and 54% for the VLSI standard cell placement problem.     

Recursive bi-partitioning of netlists for large number of partitions

In many application in VLSI CAD, a given netlist has to be partitioned into smaller sub-designs which can be handled much better. In this paper we present a new recursive bi-partitioning algorithm that is especially applicable, if a large number of final partitions, e.g., more than 1000, has to be computed. The algorithm consists of two steps. Based on recursive splits the problem is divided into several sub-problems, but with increasing recursion depth more run time is invested. By this an initial solution is determined very fast. The core of the method is a second step, where a very powerful greedy algorithm is applied to refine the partitions. Experimental results are given that compare the new approach to state-of-the-art tools. The experiments show that the new approach outperforms the standard techniques with respect to run time and quality. Furthermore, the memory usage is very low and is reduced in comparison to other methods by more than a factor of four.     

On the initial estimate of interface forces in FETI methods

The balanced domain decomposition (BDD) method and the finite element tearing and interconnecting (FETI) method are two commonly used non-overlapping domain decomposition methods. Due to strong theoretical and numerical similarities, these two methods are generally considered as being equivalently efficient. However, for some particular cases, such as for structures with strong heterogeneities, FETI requires a large number of iterations to compute the solution compared to BDD. In this paper, the origin of the poor efficiency of FETI in these particular cases is traced back to bad initial estimates of the interface stresses. To improve the estimation of interface forces, a novel strategy for splitting interface forces between neighboring substructures is proposed. The additional computational cost incurred is not significant. This yields a new initialization for the FETI method and restores numerical efficiency which makes FETI comparable to BDD even for problems where FETI was performing poorly. Various simple test problems are presented to discuss the efficiency of the proposed strategy and to illustrate the so-obtained numerical equivalence between the BDD and FETI solvers.     

A BDD SAT solver for satisfiability testing: An industrial case study

The satisfiability problem (SAT) is a fundamental problem in mathematical logic, constraint satisfaction, VLSI engineering, and computing theory. Methods to solve the satisfiability problem play an important role in the development of computing theory and systems. In this paper, we give a BDD (Binary Decision Diagrams) SAT solver for practical asynchronous circuit design. The BDD SAT solver consists of a structural SAT formula preprocessor and a complete, incremental SAT algorithm that is able to find an optimal solution. The preprocessor compresses a large size SAT formula representing the circuit into a number of smaller SAT formulas. This avoids the problem of solving very large SAT formulas. Each small size SAT formula is solved by the BDD SAT algorithm efficiently. Eventually, the results of these subproblems are integrated together that contribute to the solution of the original problem. According to recent industrial assessments, this BDD SAT solver provides solutions to the practical, industrial asynchronous circuit design problems.This research is supported in part by the 1993 ACM/IEEE Design Automation Award, by the Alberta Microelectronics Graduate Scholarship, by the NSERC research grant OGP0046423, and was supported in part by the NSERC strategic grant MEF0045793.Presently, Jun Gu is on leave with the Department of Computer Science, Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong.     

一种结合页分配和组调度的内存功耗优化方法

多核系统中,内存子系统消耗大量的能耗并且比例还会继续增大.因此,解决内存的功耗问题成为系统功耗优化的关键.根据线程的内存地址空间和负载均衡策略将系统中的线程划分成不同的线程组,根据线程所属的组,给同一组内的线程分配相同内存rank中的物理页,然后,根据划分的线程组以组为单位进行调度.提出了结合页分配和组调度的内存功耗优化方法（CAS）.CAS周期性地激活当前需要的内存rank,从而可以将暂时不使用的内存rank置为低功耗状态,同时延长低功耗内存rank的空闲时间.仿真实验结果显示：与其他同类方法相比,CAS方法能够平均降低10%的内存功耗,同时提高8%的性能.     

Automated BIST for sequential logic synthesis

An automated built-in self-test (BIST) technique for general sequential logic is described that can be used directly at all levels of testing from device testing through system diagnostics. The technique selectively replaces existing system memory elements with BIST flip-flop cells, which it then connects to form a circular chain. Data are compacted and test patterns are generated simultaneously. The approach has been incorporated in a system for behavioral model synthesis to implement BIST in VLSI devices based on standard cells and in circuit packs based on PLDs, automatically. Seven production VLSI devices have been implemented with this automated BIST approach. Area overhead was between 6% and 19% for a fault coverage of 90%+ with the BIST capability alone     

On some union and intersection problems for polygons with fixed orientations

Objects with fixed orientations play an important role in many application areas, for instance VLSI design. Problems involving only rectilinearly oriented (rectangular) objects, as a simplest case, have been studied with the VLSI design application in mind. These objects can be transistors, cells or macros. In reality, they are more suitably represented by polygons rather than just rectangles. In this note we describe how to perform a general decomposition of a set of polygons with fixed orientations in order to solve various computational geometry problems which are important in VLSI design. The decomposition is very simple and efficiently computable, and it allows the subsequent application of algorithms for the rectilinear case, leading to some very efficient and some optimal solutions. We illustrate the technique in detail at the problem of finding the connected components of a set of polygons, for which we derive an optimal solution. The wide applicability of the method is then demonstrated at the problem of finding all pairs of intersecting polygons, yielding an optimal solution.The work of this author was partially supported by the National Science Foundation under Grants MCS 8342682 and ECS 8340031. This work was performed while this author was a summer visitor at the IBM T. J. Watson Research Center.     

A binary decision diagram based approach for mining frequent subsequences

Sequential pattern mining is an important problem in data mining. State of the art techniques for mining sequential patterns, such as frequent subsequences, are often based on the pattern-growth approach, which recursively projects conditional databases. Explicitly creating database projections is thought to be a major computational bottleneck, but we will show in this paper that it can be beneficial when the appropriate data structure is used. Our technique uses a canonical directed acyclic graph as the sequence database representation, which can be represented as a binary decision diagram (BDD). In this paper, we introduce a new type of BDD, namely a sequence BDD (SeqBDD), and show how it can be used for efficiently mining frequent subsequences. A novel feature of the SeqBDD is its ability to share results between similar intermediate computations and avoid redundant computation. We perform an experimental study to compare the SeqBDD technique with existing pattern growth techniques, that are based on other data structures such as prefix trees. Our results show that a SeqBDD can be half as large as a prefix tree, especially when many similar sequences exist. In terms of mining time, it can be substantially more efficient when the support is low, the number of patterns is large, or the input sequences are long and highly similar.     

弹载记录器存储模块优化设计与实现

弹载记录器是弹上关键设备,具有存储容量大、体积小及可靠性高等特点,其存储模块与其他存储模块相比,在可靠性方面具有更高的要求;简单介绍了弹载记录器及存储模块的工作方式,针对存储模块在可靠性方面存在的隐患,从软件上对存储模块指令的识别、工作状态的转换等进行了优化设计,并将异步串行通讯应用于存储模块中,实现存储体工作状态的实时监控,与之前的存储模块相比,此存储模块工作方式更加灵活、可靠。     

一种基于WEB的VLSI协同设计平台

文章结合CSCW理论与VLSICAD技术,介绍了一种基于WEB的远程VLSI协同设计的网络平台,提出在WEB上实现VLSI协同设计系统要满足的要求,并给出具体实施的模型框架,指出了实施的关键技术。     

Heuristic Learning Based on Genetic Programming

In this paper we present an approach to learning heuristics based on Genetic Programming (GP) which can be applied to problems in the VLSI CAD area. GP is used to develop a heuristic that is applied to the problem instance instead of directly solving the problem by application of GP. The GP-based heuristic learning method is applied to one concrete field from the area of VLSI CAD, i.e. minimization of Binary Decision Diagrams (BDDs). Experimental results are given in order to demonstrate that the GP-based method leads to high quality results that outperform previous methods while the run-times of the resulting heuristics do not increase. Furthermore, we show that by clever adjustment of parameters, further improvements such as the saving of about 50% of the run-time for the learning phase can be achieved.     

The analysis of decomposition methods for support vector machines

The support vector machine (SVM) is a promising technique for pattern recognition. It requires the solution of a large dense quadratic programming problem. Traditional optimization methods cannot be directly applied due to memory restrictions. Up to now, very few methods can handle the memory problem and an important one is the "decomposition method." However, there is no convergence proof so far. We connect this method to projected gradient methods and provide theoretical proofs for a version of decomposition methods. An extension to bound-constrained formulation of SVM is also provided. We then show that this convergence proof is valid for general decomposition methods if their working set selection meets a simple requirement.     

Segmentation,paging and optimal page sizes in virtual memory

On the basis of empirical data two topics concerning virtual memory systems are discussed: determining an optimal page size and performance of segmentation as compared to paging. Several production programs have been executed (on a simulator) both in a segmented system and in a paged system with various page sizes; the memory management was based on the working set policy. The memory usage and the fault rates were recorded, and the lifetime functions and space-time integrals were evaluated. The observations are explained using a new model of program behaviour which is a refinement of the phase-transition model. The results show that there is no globally optimal page size. Two characteristic types of programs are observed: the first requires a small page size and a large window size, the second requires a large page size and a small window size. Segmentation and paging are compared with respect to their usage of various resources. In the sense of the space-time integral, segmentation usually outperforms paging; if the mean segment size is large, the difference is remarkable. Several commonly used assumptions about the effects of page size on program behaviour are validated; some of them are found inaccurate or even wrong.     

A Stable Domain Decomposition Technique for Advection–Diffusion Problems

The use of implicit methods for numerical time integration typically generates very large systems of equations, often too large to fit in memory. To address this it is necessary to investigate ways to reduce the sizes of the involved linear systems. We describe a domain decomposition approach for the advection–diffusion equation, based on the Summation-by-Parts technique in both time and space. The domain is partitioned into non-overlapping subdomains. A linear system consisting only of interface components is isolated by solving independent subdomain-sized problems. The full solution is then computed in terms of the interface components. The Summation-by-Parts technique provides a solid theoretical framework in which we can mimic the continuous energy method, allowing us to prove both stability and invertibility of the scheme. In a numerical study we show that single-domain implementations of Summation-by-Parts based time integration can be improved upon significantly. Using our proposed method we are able to compute solutions for grid resolutions that cannot be handled efficiently using a single-domain formulation. An order of magnitude speed-up is observed, both compared to a single-domain formulation and to explicit Runge–Kutta time integration.     

A survey of memory deduplication approaches for intelligent urban computing

Limited memory size is considered as a major bottleneck in data centers for intelligent urban computing. It is shown that there exist a large number of duplicated pages when various processes working with big data are hosted in data centers. Memory deduplication aims to automatically eliminate duplicate data in memory. It is an efficient technique to reduce memory requirement. In memory deduplication, pages with same content are detected and merged into a single copy. Recently, several system-level techniques have been proposed to address this issue, in which content-based page sharing (CBPS) is most widely used, since CBPS can be performed transparently in the hypervisor layer without any modification to guest operating systems of data center. In this paper, we survey several techniques for memory deduplication. We also classify these techniques based on their characteristics to highlight their similarities and differences. The aim of this paper is to provide insights to researchers into working of memory deduplication techniques and also to motivate them to propose better intelligent urban computing systems.     

Huge Page Friendly Virtualized Memory Management

With the rapid increase of memory consumption by applications running on cloud data centers,we need more efficient memory management in a virtualized environment.Exploiting huge pages becomes more critical for a virtual machine's performance when it runs large working set size programs.Programs with large working set sizes are more sensitive to memory allocation,which requires us to quickly adjust the virtual machine's memory to accommodate memory phase changes.It would be much more efficient if we could adjust virtual machines'memory at the granularity of huge pages.However,existing virtual machine memory reallocation techniques,such as ballooning,do not support huge pages.In addition,in order to drive effective memory reallocation,we need to predict the actual memory demand of a virtual machine.We find that traditional memory demand estimation methods designed for regular pages cannot be simply ported to a system adopting huge pages.How to adjust the memory of virtual machines timely and effectively according to the periodic change of memory demand is another challenge we face.This paper proposes a dynamic huge page based memory balancing system(HPMBS)for efficient memory management in a virtualized environment.We first rebuild the ballooning mechanism in order to dispatch memory in the granularity of huge pages.We then design and implement a huge page working set size estimation mechanism which can accurately estimate a virtual machine's memory demand in huge pages environments.Combining these two mechanisms,we finally use an algorithm based on dynamic programming to achieve dynamic memory balancing.Experiments show that our system saves memory and improves overall system performance with low overhead.     

Software Quality Assurance And CAD User Interfaces

The author gives an overview of software quality assurance and its relation to user interfaces for CAD systems. some of the basic concepts as well as the theoretical background and state of the art of software quality assurance are presented. A pragmatic approach to quality assurance of the software for CAD systems is presented by showing its application to a VLSI layout editor. The emphasis is on making the program reliable and robust for users.     

Danger theory based artificial immune system solving dynamic constrained single-objective optimization

In this paper, we propose an artificial immune system (AIS) based on the danger theory in immunology for solving dynamic nonlinear constrained single-objective optimization problems with time-dependent design spaces. Such proposed AIS executes orderly three modules—danger detection, immune evolution and memory update. The first module identifies whether there are changes in the optimization environment and decides the environmental level, which helps for creating the initial population in the environment and promoting the process of solution search. The second module runs a loop of optimization, in which three sub-populations each with a dynamic size seek simultaneously the location of the optimal solution along different directions through co-evolution. The last module stores and updates the memory cells which help the first module decide the environmental level. This optimization system is an on-line and adaptive one with the characteristics of simplicity, modularization and co-evolution. The numerical experiments and the results acquired by the nonparametric statistic procedures, based on 22 benchmark problems and an engineering problem, show that the proposed approach performs globally well over the compared algorithms and is of potential use for many kinds of dynamic optimization problems.