VLSI Placement Using Quadratic Programming and Network Partitioning Techniques

VLSI cell placement involves positioning cells within a target placement geometry while minimizing the interconnecting wire length and placement area. In this paper, the placement problem is solved using a combination of quadratic programming, circuit partitioning, clustering and greedy cell interchange heuristics. The solution of a sequence of quadratic programs and circuit partitioning problems provides the general positions of cells in high quality palcement. Computational efficiency is achieved by using an interior point method for solving the sequence of quadratic programs. A very efficient clustering heuristic is used to keep important groups of cells together as the cells are spread throughout the placement area. Numerical results on a set of benchmark circuits illustrate that this new approach produces standard cell placements that are up 17% better in wire length. 14% better in row length and up to 25 times faster than a well known Simulated Annealing placement heuristic.     

Computational algorithms for linear control systems: a brief survey

This paper presents a brief survey of computational algorithms for the analysis and synthesis of linear control systems described in the state space. An attempt is made to select the most efficient methods for analysis of the stability, controllability and observability, the reduction into canonical forms, the pole assignment synthesis and the synthesis of optimal systems with quadratic cost. Some aspects of the development of mathematical software for solving these problems are also discussed.     

Solving the quadratic assignment problem with clues from nature

This paper describes a new evolutionary approach to solving quadratic assignment problems. The proposed technique is based loosely on a class of search and optimization algorithms known as evolution strategies (ES). These methods are inspired by the mechanics of biological evolution and have been applied successfully to a variety of difficult problems, particularly in continuous optimization. The combinatorial variant of ES presented here performs very well on the given test problems as compared with the standard 2-Opt heuristic and results with simulated annealing and tabu search. Extensions for practical applications in factory layout are described.     

Convergence properties of the softassign quadratic assignment algorithm.

The softassign quadratic assignment algorithm is a discrete-time, continuous-state, synchronous updating optimizing neural network. While its effectiveness has been shown in the traveling salesman problem, graph matching, and graph partitioning in thousands of simulations, its convergence properties have not been studied. Here, we construct discrete-time Lyapunov functions for the cases of exact and approximate doubly stochastic constraint satisfaction, which show convergence to a fixed point. The combination of good convergence properties and experimental success makes the softassign algorithm an excellent choice for neural quadratic assignment optimization.     

0-1 Quadratic programming approach for optimum solutions of two scheduling problems

Two scheduling problems are considered: (1) scheduling n jobs non-preemptively on a single machine to minimize total weighted earliness and tardiness (WET); (2) scheduling n jobs non-preemptively on two parallel identical processors to minimize weighted mean flow time. In the second problem, a pre-ordering of the jobs is assumed that must be satisfied for any set of jobs scheduled on each specific machine. Both problems are known to be NP-complete. A 0-1 quadratic assignment formulation of the problems is presented. An equivalent 0-1 mixed integer linear programming approach for the problems are considered and a numerical example is given. The formulations presented enable one to use optimal and heuristic available algorithms of 0-1 quadratic assignment for the problems considered here.     

Lambda-opt neural approaches to quadratic assignment problems

In this article, we propose new analog neural approaches to combinatorial optimization problems, in particular, quadratic assignment problems (QAPs). Our proposed methods are based on an analog version of the lambda-opt heuristics, which simultaneously changes assignments for lambda elements in a permutation. Since we can take a relatively large lambda value, our new methods can achieve a middle-range search over possible solutions, and this helps the system neglect shallow local minima and escape from local minima. In experiments, we have applied our methods to relatively large-scale (N = 80 - 150) QAPs. Results have shown that our new methods are comparable to the present champion algorithms; for two benchmark problems, they are obtain better solutions than the previous champion algorithms.     

Competition Based Neural Networks for Assignment Problems

Competition based neural networks have been used to solve the generalized assignment problem and the quadratic assignment problem.Both problems are very difficult and are ε approximation complete.The neural network approach has yielded highly competitive performance and good performance for the quadratic assignment problem.These neural networks are guaranteed to produce feasible solutions.     

Evolutionary algorithm with a directional local search for multiobjective optimization in combinatorial problems

Evolutionary algorithms (EAs) are often employed to multiobjective optimization, because they process an entire population of solutions which can be used as an approximation of the Pareto front of the tackled problem. It is a common practice to couple local search with evolutionary algorithms, especially in the context of combinatorial optimization. In this paper a new local search method is proposed that utilizes the knowledge concerning promising search directions. The proposed method can be used as a general framework and combined with many methods of iterating over a neighbourhood of an initial solution as well as various decomposition approaches. In the experiments the proposed local search method was used with an EA and tested on 2-, 3- and 4-objective versions of two well-known combinatorial optimization problems: the travelling salesman problem (TSP) and the quadratic assignment problem (QAP). For comparison two well-known local search methods, one based on Pareto dominance and the other based on decomposition, were used with the same EA. The results show that the EA coupled with the directional local search yields better results than the same EA coupled with any of the two reference methods on both the TSP and QAP problems.     

On a pair of job-machine assignment problems with two stages

We consider two assignment problems in which a number of jobs are assigned to the same number of machines that operate in parallel, but in two stages. They are known as the ‘2-stage time minimizing assignment problem’ and the ‘bi-level time minimizing assignment problem’. These problems have the following characteristics in common:

• Each of the machines processes one job (non-preemptively, without help of other machines).

• The job-machine assignments are partitioned into two successive stages of parallel processing.

• The objective is to minimize the makespan, the sum of the primary and the secondary completion time.

Both problems can be solved by (a series of) assignment problems. We improve the related computational complexities by applying reoptimization. Under some conditions a quadratic complexity is derived.We introduce a parameter weighing the relative importance of the primary and the secondary cost per time unit. The parametric problems can be solved, for all parameter values simultaneously, within the same reduced time complexity bounds.

Scope and purpose

As it is often important to solve problems quickly, it is essential to reduce the computational complexity of available algorithms, as far as possible. We consider two problems which arise when parallel scheduling is done in two successive stages; they can be tackled by solving a series of linear assignment problems. We show that they can be solved more efficiently, using properties of the classical linear assignment problem.In practice, the cost per time unit in the two stages need not be equal. A parameter controlling the ratio between these costs defines a parametric version of each problem. The algorithms of reduced time complexity can be extended to these parametric problem versions.     

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.     

二次分配问题的改进粒子群优化算法

粒子群优化算法已经成功地应用于求解连续域问题,但是对于离散域问题的求解,尤其涉及组合优化问题的研究和应用还很少。二次分配问题本身是一个离散域问题,因此,使用粒子群算法求解二次分配问题是一个新的研究方向。文章引入交叉策略和变异策略对粒子群优化算法进行改造,使得粒子群优化算法可以用来解决二次分配问题。     

Enhancing optimal feeder assignment of the multi-head surface mounting machine using genetic algorithms

The problem of minimizing the time required to populate a printed circuit board using a multi-head surface mounting machine is considered in this paper. The multi-head surface mounting machine is becoming increasingly popular due to its merit of picking or placing multiple components simultaneously in one pick-and-place operation, which reduces much portion of the assembly time. The complexity of the optimization problem of minimizing the assembly time results in that acquiring its desired solution is difficult. The total assembly time depends on two optimization problems: feeder assignment problem and pick-and-place sequencing problem. Although these two problems are interrelated, they are solved, respectively. Feeder assignment problem is one crucial problem of affecting surface mounting machine's productivity directly. Optimal feeder assignment can decrease sum of time of moving along slots, moving from slot to PCB and moving from PCB to slot for placement heads griping components after predetermining pick-and-place sequence. For it is of a combinatorial nature and NP-hard, there is no exact algorithm for it. As an efficient and useful procedure for solving the combinatorial optimization problems, the genetic algorithm with specific crossover and mutation operators is proposed in this paper. The running results show that the proposed method performs better than the conventional methods.     

The ‘Idiot’ crash quadratic penalty algorithm for linear programming and its application to linearizations of quadratic assignment problems

ABSTRACT

We provide the first meaningful documentation and analysis of the ‘Idiot’ crash implemented by Forrest in Clp that aims to obtain an approximate solution to linear programming (LP) problems for warm-starting the primal simplex method. The underlying algorithm is a penalty method with naive approximate minimization in each iteration. During initial iterations an approach similar to augmented Lagrangian is used. Later the technique corresponds closely to a classical quadratic penalty method. We discuss the extent to which it can be used to obtain fast approximate solutions of LP problems, in particular when applied to linearizations of quadratic assignment problems.     

Optimal Control of an Elliptic-Parabolic System with Conjugation Conditions

New optimal control problems for distributed systems described by initial boundary-value problems are considered in the paper for an elliptic-parabolic equation with conjugation conditions and quadratic cost functions. Theorems of existence of a unique optimal control are proved for all the considered cases.     

面向并行负载平衡的数据剖分技术*

对传统的数据剖分技术和负载平衡对大规模并行计算性能的影响进行了综述,介绍了目前典型的几何剖分方法和图剖分方法的特点,并分析比较各种剖分算法及常用剖分软件包(ParMETIS、Zoltan、JOSTLE等)在实际应用中的优缺点,深入探讨了数据剖分技术是如何对超大规模数值模拟计算任务进行高效划分以解决负载平衡问题的,以期为开展并行计算研究和并行性能优化的研究人员提供参考。     

A mass assignment based ID3 algorithm for decision tree induction

A mass assignment based ID3 algorithm for learning probabilistic fuzzy decision trees is introduced. Fuzzy partitions are used to discretize continuous feature universes and to reduce complexity when universes are discrete but with large cardinalities. Furthermore, the fuzzy partitioning of classification universes facilitates the use of these decision trees in function approximation problems. Generally the incorporation of fuzzy sets into this paradigm overcomes many of the problems associated with the application of decision trees to real-world problems. The probabilities required for the trees are calculated according to mass assignment theory applied to fuzzy labels. The latter concept is introduced to overcome computational complexity problems associated with higher dimensional mass assignment evaluations on databases. ©1997 John Wiley & Sons, Inc.     

Load Balancing and Data Locality in Adaptive Hierarchical N-Body Methods: Barnes-Hut,Fast Multipole,and Radiosity

Hierarchical N-body methods, which are based on a fundamental insight into the nature of many physical processes, are increasingly being used to solve large-scale problems in a variety of scientific/engineering domains. Applications that use these methods are challenging to parallelize effectively, however, owing to their nonuniform, dynamically changing characteristics and their need for long-range communication. In this paper, we study the partitioning and scheduling techniques required to obtain effective parallel performance on applications that use a range of hierarchical N-body methods. To obtain representative coverage, we first examine applications that use the two best methods known for classical N-body problems: the Barnes-Hut method and the fast multipole method. Then, we examine a recent hierarchical method for radiosity calculations in computer graphics, which applies the hierarchical N-body approach to a problem with very different characteristics. We find that straightforward decomposition techniques which an automatic scheduler might implement do not scale well, because they are unable to simultaneously provide load balancing and data locality. However, all the applications yield very good parallel performance if appropriate partitioning and scheduling techniques are implemented by the programmer. For the applications that use the Barnes-Hut and fast multipole methods, simple yet effective partitioning techniques can be developed by exploiting some key insights into both the methods and the classical problems that they solve. Using a novel partitioning technique, even relatively small problems achieve 45-fold speedups on a 48-processor Stanford DASH machine (a cache-coherent, shared address space multiprocessor) and 118-fold speedups on a 128-processor simulated architecture. The very different characteristics of the radiosity application require a different partitioning/scheduling approach to be used for it; however, it too yields very good parallel performance.     

支持平台设计方法的系统芯片协同设计环境

面向基于平台的设计方法,开发了系统芯片软／硬件协同设计环境YH—PBDE．在描述YH-PBDE的总体结构之后,详细介绍了该环境中的三个设计层次与二次映射过程,重点论述了YH—PBDE中基于约束任务流图的系统建模方法、具有初始信息素的蚂蚁寻优软硬件划分算法和基于层次有向无环图的设计约束分配方法．结合具有录音功能的MP3播放器芯片的系统级设计方法,说明了在YH—PBDE中进行系统芯片软硬件协同设计的过程。     

基于二次分配问题的混合蚁群算法

二次分配问题是组合优化领域中经典的NP-hard问题之一,应用广泛。在对二次分配问题进行分析的基础上,提出了一种求解该问题的混合蚁群算法。该算法通过在蚁群算法中引入遗传算法的2-交换变异算子,增强了算法的局部搜索能力,提高了解的质量。实验结果表明,该算法在求解二次分配问题时优于蚁群算法和遗传算法。     

Pole assignment with output feedback

For pole assignment with output feedback, appropriate partitioning of the coefficient matrix of the system numerator transfer function matrix leads to simplified design equations to solve for the vectors of the unity rank output feedback matrix. This concept is applied to derive the pole placement equations for the proportional-derivative output feedback dynamic compensator. The simplicity of the design procedure is illustrated with a numerical example.