Search

We present a technology mapping procedure in which an area-delay trade-off curve is constructed at each node using matches found for different decompositions of the node. This information is used effectively to find implementations that meet delay constraints while reducing area. The procedure combines state-of-the-art mapping procedures, in which a graph covering is applied to a special graph structure which succinctly encodes many representations. Major challenges were avoiding memory explosion and finding good cost estimations. The combined procedure outperforms the best result among any of the procedures used separately.

Often, and certainly in the early stages of a design, the knowledge about delays is imprecise. Stochastic programming is not an adequate means to account for this imprecision. Not only is a probability distribution seldom a correct translation of the designer's delay knowledge, it also leads to inefficient algorithms. In this paper possibilistic programming is proposed for handling the retiming problem where delays are modelled as (triangular) possibilistic numbers. Beside the capability of optimizing the most possible clock cycle time and generating its possibility distribution, it allows for trade-offs between reducing clock cycle time and chances for obtaining worse solutions. It is shown that the computational complexity is the same as for retiming with exact circuit delays.

In this paper a fast algorithm for placing modules is presented. It gradually transforms a graph structure into a highly packed placement. The positioning of the modules is such that subsequent wiring procedures can be kept simple and total interconnection length can be relatively small. Restrictions on the shapes of the concerned modules are much weaker than those imposed by algorithms with for the rest comparable potency. In an example the algorithm is applied to bipolar integrated circuits with one wiring layer.

In chapter 5 we derived that the probability that an annealing chain has s as its current state will go asymptotically to δ(s, t), the corresponding value of the equilibrium density. Nothing was said however about how fast these probabilities will approach the equilibrium density. Yet it is necessary to know a priori when the actual density is close enough to the equilibrium density to change the value of the control parameter and to start with another chain. In this chapter we want to address that problem.

In this chapter we review the matrix theory used in this book. The purpose of the first section is to introduce the notation and to call to memory results derived in any core curriculum with a basic matrix theory course. The other three sections are small excursions to obtain theorems often not included in such a course. First the fact that every matrix is similar to a matrix in pseudo-diagonal normal form is established. It is the pivotal theorem in the convergence proof for annealing chains which is given in chapter 3. Another fact used in that proof is Gershgorin’s theorem. Its statement and proof is at the end of the third section. That section is mainly devoted to the convergence of matrix expressions and since norms are useful concepts in that context they are introduced there. That section completes the preparation for the next chapter. The definite integral obtained in the fourth section of this chapter is not used before chapter 6. It is included in this chapter because its derivation heavily depends on matrix theory, and quadratic forms in particular.

The main goal of this chapter is to obtain the result at the end of section 6.3 which is part of the basis for the initialization of annealing as described in section 8.1. On the way to this result we formally define some density functions that are going to be used in chapter 7. After all this effort to obtain theorem 6.14 it is only a small step to the special case of the central limit theorem of section 6.4. This chapter is therefore the background of much that is in chapter 7 and the proof of theorem 8.2. The presentation there is such that it can be read without going through the details of this chapter. These results are achieved by using the characteristic function of a random variable. In section 6.1 this function is defined and some of its more important properties are derived.

1 The Annealing Algorithm: A Preview.- 1.1 Combinatorial optimization.- 1.2 Moves and local minima.- 1.3 Hill climbing.- 1.4 Simulated annealing.- 1.5 Applications.- 1.6 Mathematical model.- 1.7 Discussion.- 2 Preliminaries from Matrix Theory.- 2.1 Matrices. Notation and basic properties.- 2.2 Pseudo-diagonal normal forms.- 2.3 Norms and limits of matrices.- 2.4 Quadratic forms.- 2.5 Discussion.- 3 Chains.- 3.1 Terminology.- 3.2 Linear arrangement, an example.- 3.3 The chain limit theorem.- 3.4 Reversible chains.- 3.5 Discussion.- 4 Chain Statistics.- 4.1 Density Functions.- 4.2 Expected values.- 4.3 Sampling.- 4.4 Maximum likelyhood densities.- 4.5 Aggregate functions.- 4.6 Discussion.- 5 Annealing Chains.- 5.1 Towards low scores.- 5.2 Maximal accessibility.- 5.3 The acceptance function.- 5.4 Properties of annealing chains.- 5.5 Discussion.- 6 Samples from Normal Distributions.- 6.1 Characteristic functions.- 6.2 Quadratic forms and characteristic functions.- 6.3 Sampling distributions.- 6.4 Asymptotic properties of sampling distributions.- 6.5 Discussion.- 7 Score Densities.- 7.1 The density of states.- 7.2 Weak control.- 7.3 Strong control.- 7.4 Three parameter aggregates.- 7.5 Discussion.- 8 The Control Parameter.- 8.1 Initialization.- 8.2 Decrements in the control parameter.- 8.3 A stop criterion.- 8.4 Proper convergence.- 8.5 Discussion.- 9 Finite-Time Behavior of the Annealing Algorithm.- 9.1 Rate of convergence of chains.- 9.2 Minimum number of iterations.- 9.3 Finite-time optimal schedules.- 9.4 Discussion.- 10 The Structure of the State Space.- 10.1 Chain convergence.- 10.2 The topography of the state space.- 10.3 The set of moves.- 10.4 Global convergence.- 10.5 Discussion.- 11 Implementation Aspects.- 11.1 An implementation.- 11.2 The selection function.- 11.3 Other speed-up methods.- References.

Many problems that arise in practice are concerned with finding a good or even the best configuration or parameter set from a large set of feasible options. Feasible means that the option has to satisfy a number of rigid requirements. An example of such an optimization problem is to find a minimum weight cylindrical can that must hold a given quantity of liquid. Assuming the weight of the empty can to be proportional to its area, the problem can be formulated as finding the dimensions of a cylinder with a volume c, and the smallest possible perimeter: minimize $$ 2\pi rh + \pi {r^2} $$ while $$ \pi {r^2}h = C $$ and r > 0 The formulation consists of a function to be minimized, the objective function, and a number of constraints. These constraints specify the set of feasible options, in this case the parameter pairs (r,h) that represent cylinders with radius r, height h, and volume c. Feasibility requirements are not always given as explicit constraints. In this example the volume constraint could have been substituted into the objective function.