$\Phi $-functions for complex 2D-objects

Within two-dimensional cutting and packing problems with irregular shaped objects, the concept of -functions has been proven to be very helpful for several solution approaches. In order to construct such -functions a previous work, in which so-called primary objects are considered, is continued. Now -functions are constructed for pairs of objects which can be represented as a finite combination (union, intersection, complement) of primary objects which allows the handling of arbitrary shaped objects by appropriate approximations of sufficient accuracy.Received: October 2002, Revised: October 2003, AMS classification: 65K05, 90C26, 90B06All correspondence to: Guntram Scheithauer     

Parallelizing Tabu Search on a Cluster of Heterogeneous Workstations

In this paper, we present the parallelization of tabu search on a network of workstations using PVM. Two parallelization strategies are integrated: functional decomposition strategy and multi-search threads strategy. In addition, domain decomposition strategy is implemented probabilistically. The performance of each strategy is observed and analyzed. The goal of parallelization is to speedup the search in finding better quality solutions. Observations support that both parallelization strategies are beneficial, with functional decomposition producing slightly better results. Experiments were conducted for the VLSI cell placement, an NP-hard problem, and the objective was to achieve the best possible solution in terms of interconnection length, timing performance (circuit speed), and area. The multiobjective nature of this problem is addressed using a fuzzy goal-based cost computation.     

Evaluating Parallel Simulated Evolution Strategies for VLSI Cell Placement

Simulated Evolution (SimE) is an evolutionary metaheuristic that has produced results comparable to well established stochastic heuristics such as SA, TS and GA, with shorter runtimes. However, for optimization problems with a very large set of elements, such as in VLSI cell placement and routing, runtimes can still be very large and parallelization is an attractive option for reducing runtimes. Compared to other metaheuristics, parallelization of SimE has not been extensively explored. This paper presents a comprehensive set of parallelization approaches for SimE when applied to multiobjective VLSI cell placement problem. Each of these approaches are evaluated with respect to SimE characteristics and the constraints imposed by the problem instance. Conclusions drawn can be extended to parallelization of SimE when applied to other optimization problems.      

Geometric quadrisection in linear time, with application to VLSI placement

We consider the following problem: given a set of points in the plane, each with a weight, and capacities of the four quadrants, assign each point to one of the quadrants such that the total weight of points assigned to a quadrant does not exceed its capacity, and the total distance is minimized.

This problem is most important in placement of VLSI circuits and is likely to have other applications. It is NP-hard, but the fractional relaxation always has an optimal solution which is “almost” integral. Hence for large instances, it suffices to solve the fractional relaxation. The main result of this paper is a linear-time algorithm for this relaxation. It is based on a structure theorem describing optimal solutions by so-called “American maps” and makes sophisticated use of binary search techniques and weighted median computations.

This algorithm is a main subroutine of a VLSI placement tool that is used for the design of many of the most complex chips.     

Pole placement controllers for linear time-delay systems with commensurate point delays

This paper investigates the exact and approximate spectrum assignment properties associated with realizable output-feedback pole-placement type controllers for single-input single-output linear time-invariant time-delay systems with commensurate point delays. The controller synthesis problem is discussed through the solvability of a set of coupled diophantine equations of polynomials. An extra complexity is incorporated to the above design to cancel extra unsuitable dynamics being generated when solving the above diophantine equations. Thus, the complete controller tracks any arbitrary prefixed (either finite or delaydependent) closed-loop spectrum. However, if the controller is simplified by deleting the above mentioned extra complexity, then the robust stability and approximated spectrum assignment are still achievable for a certain sufficiently small amount of delayed dynamics. Finally, the approximate spectrum assignment and robust stability problems are revisited under plant disturbances if the nominal controller is maintained. In the current approach, the finite spectrum assignment is only considered as a particular case to the designer‘s choice of a (delay-dependent) arbitrary spectrum assignment objective.     

A survey of surface mount device placement machine optimisation: Machine classification

The optimisation of a printed circuit board assembly line is mainly influenced by the constraints of the surface mount device (SMD) placement machine and the characteristics of the production environment. This paper surveys the characteristics of the various machine technologies and classifies them into five categories (dual-delivery, multi-station, turret-type, multi-head and sequential pick-and-place), based on their specifications and operational methods. Using this classification, we associate the machine technologies with heuristic methods and discuss the scheduling issues of each category of machine. We see the main contribution of this work as providing a classification for SMD placement machines and to survey the heuristics that have been used on different machines. We hope that this will guide other researchers so that they can subsequently use the classification or heuristics, or even design new heuristics that are more appropriate to the machine under consideration.     

Layout Driven Selection and Chaining of Partial Scan Flip-Flops

In an era of sub-micron technology, routing is becoming a dominant factor in area, timing, and power consumption. In this paper, we study the problem of selection and chaining of scan flip-flops with the objective of achieving minimum routing area overhead. Most of previous work on partial scan has put emphasis on selecting as few scan flip-flops as possible to break all cycles in S-graph. However, the flip-flops that break more cycles are often the ones that have more fanins and fanouts. The area adjacent to these nodes is often crowded in layout. Such selections will cause layout congestion and increase the number of tracks to chain the scan flip-flops. To take layout information into consideration, we propose a matching-based algorithm to solve the problem. First, an initial placement will be performed before scan flip-flops are selected. Then, iteratively, a matching-based algorithm taking the current layout into account is proposed to select and chain the scan flip-flops. Experimental results show that, on the average, our algorithm can reduce 8.1% area overhead as compared with the previously proposed methods that do not utilize the layout information in flip-flop selection.     

On Using Tabu Search for Design Automation of VLSI Systems

Tabu search is a meta-heuristic problem solving technique that, when applied carefully, provides near optimal solutions in a very short time. In this paper, we have described the use of tabu search for solving problems related to very large scale integrated (VLSI) circuit design automation. Specifically, we have demonstrated the use for VLSI circuit partitioning and placement. We present a tabu search based circuit bi-partitioning technique that partitions circuits with the goal of minimizing the size of the cutset between the partitions. Then, we use tabu search techniques along with force directed placement techniques to accomplish the physical placement of VLSI circuits on regular two-dimensional arrays with the goal of minimizing the placement time. We use empirical data from partitioning and placement of benchmark circuits to test our techniques. Our methods show improvement when compared to partitioning techniques from the literature and commercially available placement tools. Relative to the literature, our tabu search bi-partitioning technique improves on the best known minimum cuts for several benchmark circuits. Relative to commercially available computer aided design tools, our tabu search based placement approach shows dramatic (20×) speedup in execution time without negative impact on the quality of the solution.