Abstracts for Charles J. Alpert's Publications

Click on title for the full manuscript in PostScript format.

C. J. Alpert and A. Devgan, " Wire Segmenting for Improved Buffer Insertion", 34th ACM/IEEE Design Automation Conference, Anaheim, June 1997, pp. 588-593 (193K).

[Abstract] Buffer insertion seeks to place buffers on the wires of a signal net to minimize delay. Van Ginneken [14] proposed an optimal dynamic programming solution (with extensions proposed by [7][8][9][12] such that at most one buffer can be placed on a single wire. This constraint can hurt solution quality, but it may be circumvented by dividing each wire into multiple smaller segments. This work studies the problem of finding the correct number of segments for each wire in the routing tree. Too few segments yields sub-par solutions, but too many segments can lead to excessive run times and memory loads. We derive new theoretical results for computing the appropriate number of buffers (and hence wire segments) which motivate our new wire segmenting algorithm. We show that using wire segmenting as a precursor to buffer insertion produces solutions within a few percent of optimal, while using only seconds of CPU time.

C. J. Alpert, J.-H. Huang and A. B. Kahng, " Multilevel Circuit Partitioning", 34th ACM/IEEE Design Automation Conference, Anaheim, June 1997, pp. 530-533 (90K).

[Abstract] Recent work [2][5][11][12][14] has illustrated the promise of multilevel approaches for partitioning large circuits. Multilevel partitioning recursively clusters the instance until its size is smaller than a given threshold, then unclusters the instance while applying a partitioning refinement algorithm. Our multilevel partitioner uses a new technique to control the number of levels in the matching-based clustering phase and also exploits recent innovations in classic iterative partitioning [7][10]. Our heuristic outperforms numerous existing bipartitioning heuristics, with improvements ranging from 6.9 to 27.9% for 100 runs and 3.0 to 20.6% for just 10 runs (while also using less CPU time).

C. J. Alpert, T. Chan, D. J.-H. Huang, I. Markov and K. Yan, " Quadratic Placement Revisited", 34th ACM/IEEE Design Automation Conference, Anaheim, June 1997, pp. 752-757 (294K).

[Abstract] The ``quadratic placement'' methodology is rooted in [6][14][16] and is reputedly used in many commercial and in-house tools for placement of standard-cell and gate-array designs. The methodology iterates between two basic steps: solving sparse systems of linear equations, and repartitioning. This work dissects the implementation and motivations for quadratic placement. We first show that (i) Krylov subspace engines for solving sparse systems of linear equations are more effective than the traditional successive over-relaxation (SOR) engine [15] and (ii) order convergence criteria can maintain solution quality while using substantially fewer solver iterations. We then discuss the motivations and relevance of the quadratic placement approach, in the context of past and future algorithmic technology, performance requirements, and design methodology. We provide evidence that the use of numerical linear systems solvers with quadratic wirelength objective may be due to the pre-1990's weakness of min-cut partitioners, i.e., numerical engines were needed to provide helpful hints to min-cut partitioners. Finally, we note emerging methodology drivers in deep-submicron design that may require new placement approaches to the placement problem.

C. J. Alpert, T. F. Chan, D. J.-H. Huang, A. B. Kahng, I. L. Markov, P. Mulet and K. Yan, " Faster Minimization of Linear Wirelength for Global Placement", Proceedings International Symposium on Physical Design, Napa Valley, April 1997, pp. 4-11 (232K).

[Abstract] A linear wirelength objective more effectively captures timing, congestion, and other global placement considerations than a squared wirelength objective. The GORDIAN-L cell placement tool [16] minimizes linear wirelength by first approximating the linear wirelength objective by a squared wirelength objective, then executing the following loop -- (1) minimize the current objective to yield some approximate solution, and (2) use the resulting solution to construct a more accurate objective -- until the solution converges. In this paper, we first show that the GORDIAN-L loop can be viewed as a special case of a new algorithm that generalizes a 1937 iteration due to Weiszfeld [19]. Specifically, we formulate the Weiszfeld iteration using a regularization parameter to control the tradeoff between convergence and solution accuracy; the GORDIAN-L iteration is equivalent to setting this regularization parameter to zero. Next, we describe two more recent numerical methods, the Primal Newton iteration and the Primal-Dual Newton iteration, that improve upon the Weiszfeld iteration. Our Primal-Dual Newton iteration stably attains quadratic convergence and at a much faster rate than Weiszfeld, making it a superior choice for implementing a placer such as GORDIAN-L, or for any linear wirelength optimization.

C. J. Alpert and S.-Z. Yao, "Spectral Partitioning: the More Eigenvectors the Better", to appear in Proceedings of the 32nd ACM/IEEE Design Automation Conference, 1995 (184K).

[Abstract] A spectral partitioning method uses the eigenvectors of a graph's adjacency or Laplacian matrix to construct a geometric representation (e.g., a linear ordering) which is then heuristically partitioned. We map each graph vertex to a vector in d-dimensional space, where d is the number of eigenvectors, such that these vectors constitute an instance of the vector partitioning problem. When all the eigenvectors are used, graph partitioning exactly reduces to vector partitioning. This result motivates a simple ordering heuristic that can be used to yield high-quality 2-way and multi-way partitionings. Our experiments suggest the vector partitioning perspective opens the door to new and effective heuristics.

C. J. Alpert and A. B. Kahng, "A General Framework for Vertex Orderings, With Applications to Clustering", IEEE/ACM Intl. Conf on Computer Aided Design, 1994, pp. 63-67 (191K).

[Abstract] We present a general framework for the construction of vertex orderings for netlist clustering. Our WINDOW algorithm constructs an ordering by iteratively adding the vertex with highest attraction to the existing ordering. Variant choices for the attraction function allow our framework to subsume many graph traversals and clustering objectives from the literature. The DP-RP method of [3] is then applied to optimally split the ordering into a k-way clustering. Our approach is adaptable to user-specified cluster size constraints. Experimental results for clustering and multi-way partitioning are encouraging.

C. J. Alpert and A. B. Kahng, "Multi-Way Partitioning Via Spacefilling Curves and Dynamic Programming", Proc. 31st ACM/IEEE Design Automation Conference, 1994, pp. 652-657 (317K).

[Abstract] Spectral geometric embeddings of a circuit netlist can lead to fast, high quality multi-way partitioning solutions. Furthermore, it has been shown that d-dimensional spectral embeddings (d > 1) are a more powerful tool than single-eigenvector embeddings (d = 1) for multi-way partitioning [2] [4]. However, previous methods cannot fully utilize information from the spectral embedding while optimizing netlist-dependent objectives. This work introduces a new multi-way circuit partitioning algorithm called DP-RP. We begin with a d-dimensional spectral embedding from which a 1-dimensional ordering of the modules is obtained using a spacefilling curve. The 1-dimensional ordering retains useful information from the multi-dimensional embedding while allowing application of efficient algorithms. We show that for a new Restricted Partitioning formulation, dynamic programming efficiently finds optimal solutions in terms of Scaled Cost [4] and can transparently handle user-specified cluster size constraints. For 2-way ratio cut partitioning, DP-RP yields an average of 45% improvement over KP [4] and EIG1 [6] and 48% improvement over KC [2].

C. J. Alpert and A. B. Kahng, "Geometric Embeddings for Faster (and Better) Multi-way Netlist Partitioning", Proc. 30th ACM/IEEE Design Automation Conference, 1993, pp. 743-748 (168K).

[Abstract] We give new, effective algorithms for k-way circuit partitioning in the two regimes of k << n and k = Theta(n), where n is the number of modules in the circuit. We show that partitioning an appropriately designed geometric embedding of the netlist, rather than a traditional graph representation, yields improved results as well as large speedups. We derive d-dimensional geometric embeddings of the netlist via (i) a new "partitioning-specific" net model for constructing the Laplacian of the netlist, and (ii) computation of d eigenvectors of the netlist Laplacian; we then apply (iii) fast top-down and bottom-up geometric clustering methods.

C. J. Alpert, T. C. Hu, J. H. Huang, and A. B. Kahng, "A Direct Combination of the Prim and Dijkstra Constructions for Improved Performance-Driven Global Routing", Proc. IEEE Intl. Symp. Circuits and Systems, 1993, pp. 1869-1872 (182K).

[Abstract] Motivated by analysis of distributed RC delay in routing trees, we propose a new tree construction for performance-driven global routing which directly trades off between Prim's minimum spanning tree algorithm and Dijkstra's shortest path tree algorithm. This direct combination of two objective functions and their corresponding optimal algorithms contrasts with the more indirect "shallow-light" methods of [2,4,10]. Our method achieves routing trees which satisfy a given routing tree radius bound while using less wire than previous methods. Detailed simulations show that this wirelength savings translates into significantly improved delay over both the method of [2] and standard MST routing in both IC and multi-chip module (MCM) interconnect technologies.

C. J. Alpert and A. B. Kahng, " A Hybrid Multilevel/Genetic Approach for Circuit Partitioning", Fifth ACM/SIGDA Physical Design Workshop , April 1996, pp. 100-105 (201K).

[Abstract] We present a genetic circuit partitioning algorithm that integrates the Metis graph partitioning package [15] originally designed for sparse matrix computations. Metis is an extremely fast iterative partitioner that uses multilevel clustering. We have adapted Metis to partition circuit netlists, and have applied a genetic technique that uses previous Metis solutions to help construct new Metis solutions. Our hybrid technique produces better results than Metis alone, and also produces bipartitionings that are competitive with previous methods [20] [18] [6] while using less CPU time.

C. J. Alpert and A. B. Kahng, " Simple Eigenvector-Based Circuit Clustering", to appear in IEEE Intl. Symp. on Circuits and Systems, Atlanta, May 1996 (102K).

[Abstract] Clustering has proven effective in improving the quality of VLSI netlist partitioning and placement algorithms. A wide variety of clustering schemes have been proposed, including random walks [13], iterative matching [7], and fairly complicated spectral techniques [1] [8]. Like [1] and [8], we use eigenvectors to compute a clustering, but do so in the simplest, most obvious manner. Our algorithm first computes a d-digit code for each module v_i according to the signs of the ith entries in a set of d eigenvectors. Then, modules with the same code are assigned to the same cluster. Despite its simplicity, this new clustering algorithm is strongly motivated by theoretical results for both spectral bipartitioning [6] and multi-dimensional vector partitioning [4]. The algorithm also has linear time complexity (not including the eigenvector computation) and is at least as effective as previous clustering algorithms in terms of two-phase Fiduccia-Mattheyses bipartitioning.

C. J. Alpert and A. B. Kahng, " Splitting Orderings into Multi-Way Partitionings to Minimize the Maximum Diameter", to appear in Journal of Classification (447K).

[Abstract] Many algorithms can find optimal bipartitions for various objectives including minimizing the maximum cluster diameter (``min-diameter''); these algorithms are often applied iteratively in top-down fashion to derive a partition consisting of k clusters, with k > 2. Bottom-up agglomerative approaches are also commonly used to construct partitions, and we discuss these in terms of worst-case performance for metric data sets. Our main contribution derives from a new restricted partition formulation that requires each cluster to be an interval of a given ordering of the objects being clustered. Dynamic programming can optimally split such an ordering into a partition for a large class of objectives that includes min-diameter. We explore a variety of ordering heuristics and show that our algorithm, when combined with an appropriate ordering heuristic, outperforms traditional algorithms on both random and non-random data sets.

C. J. Alpert and A. B. Kahng, " Multi-Way Partitioning Via Geometric Embeddings, Orderings, and Dynamic Programming", IEEE Transactions on CAD, 14(11), 1995, pp.1342-1358 (610K).

[Abstract] This paper presents effective algorithms for multi-way partitioning. Confirming ideas originally due to Hall [27], we demonstrate that geometric embeddings of the circuit netlist can lead to high-quality k-way partitionings. The netlist embeddings are derived via the computation of d eigenvectors of the Laplacian for a graph representation of the netlist. As [27] did not specify how to partition such geometric embeddings, we explore various geometric partitioning objectives and algorithms, and find that they are limited because they do not integrate topological information from the netlist. Thus, we also present a new partitioning algorithm that exploits both the geometric embedding and netlist information, as well as a Restricted Partitioning formulation that requires each cluster of the k-way partitioning to be contiguous in a given linear ordering. We begin with a d-dimensional spectral embedding and construct a heuristic 1-dimensional ordering of the modules (combining spacefilling curve with 3-Opt approaches originally proposed for the traveling salesman problem). We then apply dynamic programming to efficiently compute the optimal k-way split of the ordering for a variety of objective functions, including Scaled Cost [12] and Absorption [44]. This approach can transparently integrate user-specified cluster size bounds. Experiments show that this technique yields multi-way partitionings with lower Scaled Cost than previous spectral approaches [2] [12] [25].

C. J. Alpert and A. B. Kahng, " A General Framework for Vertex Orderings, With Applications to Circuit Clustering", IEEE Transactions on VLSI Systems, 4(2), 1996, pp. 240-246 (278K).

[Abstract] Vertex orderings have been successfully applied to problems in netlist clustering, for system partitioning and layout [2] [20]. We present a vertex ordering construction that encompasses most reasonable graph traversals. Two parameters -- an attraction function and a window -- provide the means for achieving various graph traversals and addressing particular clustering requirements. We then use dynamic programming [2] to optimally split the vertex ordering into a multi-way clustering. Our approach outperforms several clustering methods in the literature in terms of three distinct clustering objectives [5] [8] [22]. The ordering construction, by itself, also outperforms existing graph ordering constructions [2] [3] [17] [19] for this application. Tuning our approach to ``meta-objectives'', particularly clustering for two-phase Fiduccia-Mattheyses bipartitioning [9], remains an open area of research.

Charles Alpert's Home Page