17.1 INTRODUCTION

The basic idea of analytical placement consists of first placing the cells optimally in terms of an appropriate netlength estimation (but without considering disjointness constraints) and then working toward disjointnesss. For the second step, we can distinguish two main approaches. One method consists of modifying the objective function in small steps to force cells to move away from each other. Such force-directed approaches will be described in Chapter 18. In this chapter, we consider methods that reduce overlaps by recursive partitioning of the chip area and the set of cells to be placed. This partitioning is done in such a way that no subregion of the chip area contains more cells than fit into it. Consequently, when the regions are small enough, the cells will be spread over the chip area.

Such an analytical placer is illustrated in Figure 17.1. The large objects are preplaced macros. The first picture shows a placement of the movable cells with minimum squared netlength (with many overlaps). Then, in each partitioning step, the regions and the sets of cells are divided into four parts, indicated by different gray scales. We will explain the details later in this chapter.

Figure 17.1: First six steps of an analytical placer.

Analytical placement is based on the ability to minimize netlength efficiently. Therefore, we first discuss this in Section 17.2. We define various measures for netlength and show how to minimize linear and quadratic netlengths. For reasons that we will discuss,...