Please use this identifier to cite or link to this item: http://localhost:80/xmlui/handle/123456789/7417
Full metadata record
DC FieldValueLanguage
dc.contributor.authorMajumder, Subhashis-
dc.date.accessioned2023-03-24T03:50:34Z-
dc.date.available2023-03-24T03:50:34Z-
dc.date.issued2004-
dc.identifier.urihttp://172.16.0.4:8085/heritage/handle/123456789/7417-
dc.descriptionhttps://doi.org/10.1142/S0218126604001854en_US
dc.description.abstractA VLSI chip is fabricated by integrating several rectangular circuit blocks on a 2D silicon floor. The circuit blocks are assumed to be placed isothetically and the netlist attached to each block is given. For wire routing, the terminals belonging to the same net are to be electrically interconnected using conducting paths. A staircase channel is an empty polygonal region on the silicon floor bounded by two monotonically increasing (or decreasing) staircase paths from one corner of the floor to its diagonally opposite corner. The staircase paths are defined by the boundaries of the blocks. In this paper, the problem of determining a monotone staircase channel on the floorplan is considered such that the number of distinct nets whose terminals lie on both sides of the channel, is minimized. Two polynomial-time algorithms are presented based on the network flow paradigm. First, the simple two-terminal net model is considered, i.e., each net is assumed to connect exactly two blocks, for which an O(n×k) time algorithm is proposed, where n and k are respectively the number of blocks and nets on the floor. Next, the algorithm is extended to the more realistic case of multi-terminal net problem. The time complexity of the latter algorithm is O((n+k)×T), where T is the total number of terminals attached to all nets in the floorplan. Solutions to these problems are useful in modeling the repeater block placement that arises in interconnect-driven floorplanning for deep-submicron VLSI physical design. It is also an important problem in context to the classical global routing, where channels are used as routing space on silicon.en_US
dc.language.isoenen_US
dc.publisherWorld Scientificen_US
dc.relation.ispartofseriesVol : 13;No : 5-
dc.subjectDesign automationen_US
dc.subjectVLSI floorplanningen_US
dc.subjectnetwork flowen_US
dc.titleON FINDING A STAIRCASE CHANNEL WITH MINIMUM CROSSING NETS IN A VLSI FLOOR PLANen_US
dc.title.alternativeJournal of Circuits, Systems and Computersen_US
dc.typeArticleen_US
Appears in Collections:Computer Science And Engineering (Publications)

Files in This Item:
File Description SizeFormat 
2004(1).doc180.5 kBMicrosoft WordView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.