FAST CONSTRAINT GRAPH GENERATION ALGORITHMS FOR VLSI LAYOUT COMPACTION

1994-04-14
TORUNOGLU, IH
ASKAR, M
Three new fast constraint graph generation algorithms, PPSS-1D, PPSS-1Dk and PPSS-2D, are presented for VLSI layout compaction. The algorithms are based on parallel plane sweep shadowing (PPSS). The PPSS-1D algorithm improves the time spent on searching processes from O(N/spl circ/1.5) to O(G*N) with extra O(G) memory where G is independent of N. PPSS-1Dk, the successor to PPSS-1D, eliminates the possibility of generation of unnecessary constraints using extra O(k*G) memory. PPSS-2D improves the O(NlogN) sorting time required by PPSS to O(NlogN/logG). The experimental results show the superiority of each algorithm to the PPSS algorithm on time complexity bases.

Suggestions

An Efficient Parallel Solution Framework for the Linear Solution of Large Systems on PC Clusters
Kurç, Özgür (Tsinghua University Press, 2008-10-01)
In this paper, a parallel solution framework for the linear static analysis of large structures on PC clusters is presented. The framework consists of two main steps: data preparation and parallel solution. The parallel solution is performed by a substructure based method with direct solvers. The aim of the data preparation step is to create the best possible substructures so that the parallel solution time is minimized. An actual structural model was solved utilizing both homogeneous and heterogeneous PC c...
Derivation and analysis of near field tofar field transformation algorithm for spherical scanning
Korkmaz, Hülya; Koç, Seyit Sencer; Department of Electrical and Electronics Engineering (2019)
This thesis focuses on the improvement of a far field transformation algorithm of spherical near field scanning by using different quadrature techniques for numerical integration process. In this thesis, spherical vector wave expansion of E field is studied and numerical calculation for expansion coefficients of E field is performed. In the scope of this study quadrature techniques like Gauss, Trapezoid and Simpsons are investigated and advantages and disadvantages of these techniques are discussed. A decis...
Fast Algorithms for Digital Computation of Linear Canonical Transforms
Koc, Aykut; Öktem, Sevinç Figen; Ozaktas, Haldun M.; Kutay, M. Alper (2016-01-01)
Fast and accurate algorithms for digital computation of linear canonical transforms (LCTs) are discussed. Direct numerical integration takes O.N-2/time, where N is the number of samples. Designing fast and accurate algorithms that take O. N logN/time is of importance for practical utilization of LCTs. There are several approaches to designing fast algorithms. One approach is to decompose an arbitrary LCT into blocks, all of which have fast implementations, thus obtaining an overall fast algorithm. Another a...
An adaptive, energy-aware and distributed fault-tolerant topology-control algorithm for heterogeneous wireless sensor networks
Deniz, Fatih; Bagci, Hakki; KÖRPEOĞLU, İBRAHİM; Yazıcı, Adnan (2016-07-01)
This paper introduces an adaptive, energy-aware and distributed fault-tolerant topology control algorithm, namely the Adaptive Disjoint Path Vector (ADPV) algorithm, for heterogeneous wireless sensor networks. In this heterogeneous model, we have resource-rich supernodes as well as ordinary sensor nodes that are supposed to be connected to the supernodes. Unlike the static alternative Disjoint Path Vector (DPV) algorithm, the focus of ADPV is to secure supernode connectivity in the presence of node failures...
A new approach to multivariate adaptive regression splines by using Tikhonov regularization and continuous optimization
TAYLAN, PAKİZE; Weber, Gerhard Wilhelm; Ozkurt, Fatma Yerlikaya (2010-12-01)
This paper introduces a model-based approach to the important data mining tool Multivariate adaptive regression splines (MARS), which has originally been organized in a more model-free way. Indeed, MARS denotes a modern methodology from statistical learning which is important in both classification and regression, with an increasing number of applications in many areas of science, economy and technology. It is very useful for high-dimensional problems and shows a great promise for fitting nonlinear multivar...
Citation Formats
I. TORUNOGLU and M. ASKAR, “FAST CONSTRAINT GRAPH GENERATION ALGORITHMS FOR VLSI LAYOUT COMPACTION,” 1994, p. 577, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/66139.