FAST CONSTRAINT GRAPH GENERATION ALGORITHMS FOR VLSI LAYOUT COMPACTION

Date

1994-04-14

Author

TORUNOGLU, IH
ASKAR, M

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

147
views

0
downloads

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.

Subject Keywords

Very Large Scale Integration , Compaction , Shadow Mapping , Topology , Solid Modeling , Sorting , Fabrication , Humans , Time Factors , Binary Trees

URI

https://hdl.handle.net/11511/66139

Collections

Department of Mining Engineering, Conference / Seminar

Suggestions

OpenMETU
Core

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...
Robust feature space separation for deep convolutional neural network training Sekmen, Ali; Parlaktuna, Mustafa; Abdul-Malek, Ayad; Erdemir, Erdem; Koku, Ahmet Buğra (2021-11-01) This paper introduces two deep convolutional neural network training techniques that lead to more robust feature subspace separation in comparison to traditional training. Assume that dataset has M labels. The first method creates M deep convolutional neural networks called {DCNNi}i=1M" role="presentation">{DCNNi}Mi=1. Each of the networks DCNNi" role="presentation">DCNNi is composed of a convolutional neural network (CNNi" role="presentation">CNNi) and a fully connected neural network (FCNNi" role="pre...
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.