Crossing Distribution Problem in Two Regions Using Binary Indexed Tree

Abstract

t An Integrated Circuit (IC) is a set of electronic components on a small plate of semiconductor material, called Printed Circuit Board (PCB). On the two layers of PCB, these components are interconnected by conductive pathways (nets), which can cross each others creating crossings. Crossing makes the current pass on the board incorrectly. In order that, some Vertical Interconnect Access (VIAs) are used to avoid crossings. However, each VIA takes particular area of the PCB, then number of VIAs in each region on the board are limited by a number called quota. The IC layout design is locating electronic components and routing nets on the very small area of PCB. In the IC layout design process, the whole board is divided into several small regions. After that, components and nets are assigned into them. The crossing distribution problem (CDP) is to find a nets order on each boundary as to minimize the total number of crossings and to satisfy the quotas in each small region on PCB. Researches on CDP have been started from 1989. Until now, it is still a complicated problem. To reduce the complexity, the CDP is decomposed into several small subproblems, using several assumptions. In the scope of this thesis, by using Binary Indexed Tree data structure, we propose an O(n log n) time algorithm for the CDP for two-terminal nets in two regions, where n is number of nets. This subproblem is basic, but it has important role for solving the whole Crossing Distribution Problem. Our study is directly superior to the previous ones [Song and Wang, 1999] and [Yu and Lee, 2004]. Keywords: VLSI, crossing distribution problem, two regions, detailed routing, two-terminal net, binary indexed tree