NDLI: Monotone bipartitioning problem in a planar point set with applications to VLSI

Content Provider	ACM Digital Library
Author	Bhattacharya, Bhargab B. Pan, Peichen Dasgupta, Parthasarathi Nandy, Subhas C.
Copyright Year	2002
Abstract	A new problem called monotone bipartitioning of a planar point set is identified which is found to be useful in VLSI layout design. Let $\textit{F}$ denote a rectangular floor containing a set $\textit{A}$ of $\textit{n}$ points. The portion of a straight line formed by two points from the set $\textit{A}$ is called a line segment. A monotone increasing path $(\textit{MP})$ in $\textit{F}$ is a connected and ordered sequence of line segments from the bottom-left corner of $\textit{F}$ to its top-right corner, such that the slope of each line segment is nonnegative, and each pair of consecutive line segments share a common point of $\textit{A}.$ An $\textit{MP}$ is said to be maximal $(\textit{MMP})$ if no other point in $\textit{A}$ can be included in it preserving monotonicity. Let $A^{L}$ denote the subset of $\textit{A}$ corresponding to the end points of the line segments in an $\textit{MMP},$ $\textit{L}.$ The path $\textit{L}$ partitions the set of points $AA^{L}$ into two subsets lying on its two sides. The objective of monotone bipartitioning is to find an MMP L, such that the difference in the number of points in these two subsets is minimum. This problem can be formulated as finding a path between two designated vertices of an edge-weighted digraph (the weight of an edge being an integer lying in the range [-n, n]), for which the absolute value of the algebraic sum of weights is minimized. An $\textit{O}(\textit{n}×$ $\textit{e})$ time algorithm is proposed for this problem, where $\textit{e}$ denotes the number of edges of the graph determined from the geometry of the point set. The monotone bipartitioning problem has various applications to image processing, facility location, and plant layout problems. A related problem arises while partitioning a VLSI floorplan. Given a floorplan with $\textit{n}$ rectangular blocks, the goal is to find a monotone staircase channel from one corner of the floor to its diagonally opposite corner such that the difference in the numbers of blocks lying on its two sides is minimum. The problem is referred to as the staircase bipartitioning problem. The proposed algorithm for a point set can be directly used to solve this problem in $O(n^{2})$ time. However, an improved $\textit{O}(\textit{n})$ time algorithm is reported for this special case. This leads to an $\textit{O}(\textit{n}$ log $\textit{n})$ time algorithm for hierarchical decomposition of a floorplan with a sequence of staircase channels. Staircase bipartitioning has many applications to channel and global routing.
Starting Page	231
Ending Page	248
Page Count	18
File Format	PDF
ISSN	10844309
e-ISSN	15577309
DOI	10.1145/544536.544537
Volume Number	7
Issue Number	2
Journal	ACM Transactions on Design Automation of Electronic Systems (TODAES)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2002-04-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Complexity of algorithms Floorplanning Partitioning Routing Very large scale integration (VLSI)
Content Type	Text
Resource Type	Article
Subject	Computer Graphics and Computer-Aided Design Computer Science Applications Electrical and Electronic Engineering

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Buffer planning as an Integral part of floorplanning with consideration of routing congestion

Bus-driven floorplanning

Hierarchical partitioning of VLSI floorplans by staircases

MARS-a multilevel full-chip gridless routing system

An evaluation of bipartitioning techniques

Consistent floorplanning with hierarchical superconstraints

Non-tree routing [VLSI layout]

Single-layer global routing

Geometric bipartitioning problem and its applications to VLSI

Monotone bipartitioning problem in a planar point set with applications to VLSI

Similar Documents

Buffer planning as an Integral part of floorplanning with consideration of routing congestion

Bus-driven floorplanning

Hierarchical partitioning of VLSI floorplans by staircases

MARS-a multilevel full-chip gridless routing system

An evaluation of bipartitioning techniques

Consistent floorplanning with hierarchical superconstraints

Non-tree routing [VLSI layout]

Single-layer global routing

Geometric bipartitioning problem and its applications to VLSI

Monotone bipartitioning problem in a planar point set with applications to VLSI