Informatica

The performance of a computer network is commonly measured by the maximum minimum time required to move a certain amount of data between any 2 nodes in the network. Due to the advances in technology, certain links in the network may be upgraded, for instance to optical fibre links, so that better performance can be achieved. In this paper, we study the LINK UPGRADE problem for networks. We first show that the LINK UPGRADE problem is NP-complete. We also show that, a closely related problem, the MINIMUM COST LINK UPGRADE problem is NP-complete even if the underlying topology of the network is a linear array. However, for certain classes of networks, the LINK UPGRADE problem can be solved in polynomial time. For general networks, we provide effective heuristics for the above problems.

In this paper, we present an effective performance driven placement with global routing algorithm for macro cells. Our algorithm uses a hierarchical, divide and conquer, quad-partitioning approach. The quad-partitioning routine uses the Tabu Search technique. Our algorithm uses the concept of proximity of regions to approximate the interconnection delays during the placement process. In addition, our algorithm can handle modules whose positions are fixed or are restricted to a particular subregion on the layout frame. Our experimental results indicate the superiority of our placement method in terms of quality of solution and run time when compared to Lin and Du (1990).