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...
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...
Optimum design of grillage systems using harmony search algorithm
Erdal, Ferhat; Saka, Mehmet Polat; Department of Engineering Sciences (2007)
Harmony search method based optimum design algorithm is presented for the grillage systems. This numerical optimization technique imitates the musical performance process that takes place when a musician searches for a better state of harmony. For instance, jazz improvisation seeks to find musically pleasing harmony similar to the optimum design process which seeks to find the optimum solution. The design algorithm considers the displacement and strength constraints which are implemented from LRFD-AISC (Loa...
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.