5276231
Open-ended robust design of analog filters using genetic programming
Most existing research on robust design using evolutionary algorithms (EA) follows the paradigm of traditional robust design, in which parameters of a design solution are tuned to improve the robustness of the system. However, the topological structure of a system may set a limit on the possible robustness achievable through parameter tuning. This paper proposes a new robust design paradigm that exploits the open-ended topological synthesis capability of genetic programming to evolve more robust systems. As a case study, a methodology for automated synthesis of dynamic systems, based on genetic programming and bond graph modeling (GPBG), is applied to evolve robust low-pass and high-pass analog filters. Compared with a traditional robust design approach based on a state-of-the-art real-parameter genetic algorithm (GA), it is shown that open-ended topology search by genetic programming with a fitness criterion rewarding robustness can evolve more robust systems with respect to parameter perturbations than what was achieved through parameter tuning alone, for our test problems.
14747412
Adaptive Hierarchical Fair Competition (AHFC) Model For Parallel Evolutionary Algorithms
The HFC model for parallel evolutionary computation is inspired by the stratified competition often seen in society and biology. Subpopulations are stratified by fitness. Individuals move from low-fitness to higher-fitness subpopulations if and only if they exceed the fitness-based admission threshold of the receiving subpopulation, but not of a higher one. The HFC model implements several critical features of a competent parallel evolutionary computation model, simultaneously and naturally, allowing rapid exploitation while impeding premature convergence. The AHFC model is an adaptive version of HFC, extending it by allowing the admission thresholds of fitness levels to be determined dynamically by the evolution process itself. The effectiveness of the Adaptive HFC model is compared with the HFC model on a genetic programming-based evolutionary synthesis example.
8637956
Dense and Switched Modular Primitives for Bond Graph Model Design
This paper suggests dense and switched modular primitives for a bond-graph-based GP design framework that automatically synthesizes designs for multi-domain, lumped parameter dynamic systems. A set of primitives is sought that will avoid redundant junctions and elements, based on preassembling useful functional blocks of bond graph elements and (optionally) using a switched choice mechanism for inclusion of some elements. Motivation for using these primitives is to improve performance through greater search efficiency and thereby to reduce computational effort. As a proof of concept for this approach, an eigenvalue assignment problem, which is to find bond graph models exhibiting minimal distance errors from target sets of eigenvalues, was tested and showed improved performance for various sets of eigenvalues.
612951
Exploring Multiple Design Topologies Using Genetic Programming And Bond Graphs
To realize design automation of dynamic systems, there are two major issues to be dealt with: open-topology generation of dynamic systems and simulation or analysis of those models. For the first issue, we exploit the strong topology exploration capability of genetic programming to create and evolve structures representing dynamic systems. With the help of ERCs (ephemeral random constants) in genetic programming, we can also evolve the sizing of dynamic system components along with the structures. The second issue, simulation and analysis of those system models, is made more complex when they represent mixed-energy-domain systems. We take advantage of bond graphs as a tool for multi- or mixed-domain modeling and simulation of dynamic systems. Because there are many considerations in dynamic system design that are not completely captured by a bond graph, we would like to generate multiple solutions, allowing the designer more latitude in choosing a model to implement. The approach in this paper is capable of providing a variety of design choices to the designer for further analysis, comparison and trade-off. The approach is shown to be efficient and effective in an example of open-ended real-world dynamic system design application, a printer re-design problem.
9574067
The Hierarchical Fair Competition (HFC) Framework for Sustainable Evolutionary Algorithms
Many current Evolutionary Algorithms (EAs) suffer from a tendency to converge prematurely or stagnate without progress for complex problems. This may be due to the loss of or failure to discover certain valuable genetic material or the loss of the capability to discover new genetic material before convergence has limited the algorithm's ability to search widely. In this paper, the Hierarchical Fair Competition (HFC) model, including several variants, is proposed as a generic framework for sustainable evolutionary search by transforming the convergent nature of the current EA framework into a non-convergent search process. That is, the structure of HFC does not allow the convergence of the population to the vicinity of any set of optimal or locally optimal solutions. The sustainable search capability of HFC is achieved by ensuring a continuous supply and the incorporation of genetic material in a hierarchical manner, and by culturing and maintaining, but continually renewing, populations of individuals of intermediate fitness levels. HFC employs an assembly-line structure in which subpopulations are hierarchically organized into different fitness levels, reducing the selection pressure within each subpopulation while maintaining the global selection pressure to help ensure the exploitation of the good genetic material found. Three EAs based on the HFC principle are tested - two on the even-10-parity genetic programming benchmark problem and a real-world analog circuit synthesis problem, and another on the HIFF genetic algorithm (GA) benchmark problem. The significant gain in robustness, scalability and efficiency by HFC, with little additional computing effort, and its tolerance of small population sizes, demonstrates its effectiveness on these problems and shows promise of its potential for improving other existing EAs for difficult problems. A paradigm shift from that of most EAs is proposed: rather than trying to escape from local optima or delay convergence at a local optimum, HFC allows the emergence of new optima continually in a bottom-up manner, maintaining low local selection pressure at all fitness levels, while fostering exploitation of high-fitness individuals through promotion to higher levels.
8610229
System-Level Synthesis of MEMS via Genetic Programming and Bond Graphs
Initial results have been achieved for automatic synthesis of MEMS system-level lumped parameter models using genetic programming and bond graphs. This paper first discusses the necessity of narrowing the problem of MEMS synthesis into a certain specific application domain, e.g., RF MEM devices. Then the paper briefly introduces the flow of a structured MEMS design process and points out that system-level lumped-parameter model synthesis is the first step of the MEMS synthesis process. Bond graphs can be used to represent a system-level model of a MEM system. As an example, building blocks of RF MEM devices are selected carefully and their bond graph representations are obtained. After a proper and realizable function set to operate on that category of building blocks is defined, genetic programming can evolve both the topologies and parameters of corresponding RF MEM devices to meet predefined design specifications. Adaptive fitness definition is used to better direct the search process of genetic programming. Experimental results demonstrate the feasibility of the approach as a first step of an automated MEMS synthesis process. Some methods to extend the approach are also discussed.
6735188
Efficient model update for general link-insertion networks
Link insertion has been proposed as a means of incremental design to improve performance robustness of linear passive networks. In clock network design, links can be inserted between subnetworks to reduce the variability of clock skews introduced by process and environmental fluctuations, thereby improving the network's immunity to PVT variations. Under these scenarios, it is desired to incrementally compute a reduced-order model for the updated network in order to efficiently evaluate the effectiveness of link insertions. In this paper, we present an efficient model update scheme for general link-insertion networks. By updating the Krylov projection subspace used in model order reduction, the proposed scheme can efficiently compute a reduced-order model for the network with inserted links. More generally, we extend the proposed approach to consider the merging of a (small) multiple-input linear network with a much larger network. We demonstrate the usage of the proposed technique for clock networks and general RLC circuits with an arbitrary number of link insertions as well as the more general case where the inserted links are in the form of a linear network
10278111
Compiler-directed instruction cache leakage optimization
Excessive power consumption is widely considered as a major impediment to designing future microprocessors. With the continued scaling down of threshold voltages, the power consumed due to leaky memory cells in on-chip caches will constitute a significant portion of the processor's power budget. This work focuses on reducing the leakage energy consumed in the instruction cache using a compiler-directed approach.We present and analyze two compiler-based strategies termed as conservative and optimistic. The conservative approach does not put a cache line into a low leakage mode until it is certain that the current instruction in it is dead. On the other hand, the optimistic approach places a cache line in low leakage mode if it detects that the next access to the instruction will occur only after a long gap. We evaluate different optimization alternatives by combining the compiler strategies with state-preserving and state-destroying leakage control mechanisms.
56583323
Exploiting level sensitive latches in wire pipelining
Wire pipelining emerges as a new necessity for global wires due to increasing wire delay, shrinking clock period and growing chip size. Existing approaches on wire pipelining are mostly based on edge triggered flip-flops. In this paper, we demonstrate the advantages of using level sensitive latches in terms of both latency and area cost. The input-output timing coupling and the strict short path constraint for latches demand additional design elaborations compared with flip-flops. New approaches are proposed in this work to solve these difficulties so that the advantages of latches can be fully utilized. In particular, a deferred delay padding technique is developed to correct short path violations with the minimal extra cost. These techniques are integrated with a dynamic programming based concurrent synchronous element and repeater insertion framework. Experimental results confirm the advantages of using latches as well as effectiveness of our algorithms.
15946403
FPGA-based Vector Processing for Matrix Operations
A programmable vector processor and its implementation with a field-programmable gate array (FPGA) are presented. This processor is composed of a vector core and a tightly coupled five-stage pipelined RISC scalar unit. It supports the IEEE 754 single-precision floating-point standard and also the efficient implementation of some sparse matrix operations. The processor is implemented on the Xilinx XC2V6000-5 FPGA chip. To test the performance, the W-matrix sparse solver for linear equations is realized. W-matrix was first proposed for power flow analysis and is prone to parallel computing. We show that actual power matrices with up to 1723 nodes can be dealt with in less than 1.1ms on the FPGA. A comparison with a commercial PC indicates that the vector processor is competitive for such computation-intensive problems
11408697
Path-Based Buffer Insertion
Along with the progress of very-large-scale-integration technology, buffer insertion plays an increasingly critical role on affecting circuit design and performance. Traditional buffer insertion algorithms are mostly net based and therefore often result in suboptimal delay or unnecessary buffer expense due to the lack of global view. In this paper, we propose a novel path-based-buffer-insertion (PBBI) scheme which can overcome the weakness of the net-based approaches. We also discuss some potential difficulties of the PBBI approach and propose solutions to them. A fast estimation on buffered delay is employed to improve the solution quality. Gate sizing is also considered at the same time. Experimental results show that our method can efficiently reduce buffer/gate cost significantly (by 71% on average) when compared to traditional net-based approaches. To the best of our knowledge, this is the first work on path based buffer insertion and simultaneous gate sizing.