We present a very fast area router for multichip module (MCM) design. Given a set of nets and a routing area, the router repeatedly selects two layers from top to bottom and routes as many nets as possible until all the nets are routed. The router uses a line sweep technique and a simple net selection algorithm. By employing efficient data structures and a novel priority scheme, the routing can be completed in time almost proportional to the size of the routing area. When applied to the benchmark circuits, the proposed router generated comparable routing results 23 times faster on the average than the previously reported fastest and effective router. When compared with the previously reported best routing result achiever, our router produced slightly worse results but ran 102 times faster on the average. Its effectiveness and ultra fast computation time make this router ideally suited for the next generation of large scale MCM designs.

Article A simple and effective greedy multilayer router for MCMs Share on Authors: Young-Jun Cha Electronics and Telecommunications Research Institute, Taejon, Korea Electronics and Telecommunications Research Institute, Taejon, KoreaView Profile , Chong S. Rim Department of Computer Science, Sogang University, Seoul, Korea and Electrical Engineering Department, University of Maryland, College Park, MD Department of Computer Science, Sogang University, Seoul, Korea and Electrical Engineering Department, University of Maryland, College Park, MDView Profile , Kazuo Nakajima Electrical Engineering Department, University of Maryland, College Park, MD Electrical Engineering Department, University of Maryland, College Park, MDView Profile Authors Info & Claims ISPD '97: Proceedings of the 1997 international symposium on Physical designApril 1997 Pages 67–72https://doi.org/10.1145/267665.267686Online:01 April 1997Publication History 10citation161DownloadsMetricsTotal Citations10Total Downloads161Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Conventional full search block matching algorithm (BMA) for motion estimation is computationally intensive and the resulting hardware cost is very high. In this paper, we present an efficient BMA using a 16:1 subsampling technique, and describe its hardware design. The algorithm reduces the number of pixels in calculating the mean absolute difference at each search location, instead of reducing the search locations. The algorithm is an extension of the BMA with 4:1 subsampling proposed by Lin and Zaccarin (1993) such that the amount of computation is reduced by a factor of 4 (16 compared to the full search BMA) while producing similar performance. The algorithm can efficiently be designed into a hardware for real-time applications.

With a logic circuit as an input, the transistors in the circuit are first placed on a sea-of-gates template by a newly developed simulated annealing placement method. The transistors are then interconnected as required using the wires available in two metal layers. For this, we developed a novel three phase routing strategy which consists of global routing, channel routing and final detailed routing. The shape of the generated cells is a rectangle with adjustable width and height. The areas of the cells are minimum and the use of the second metal wires is minimized. Experimental results for many test circuits are very satisfying and the time needed is acceptable.>

In an approach recently proposed for the yield enhancement of programmable gate arrays (PGA's), an initial placement of a circuit is first obtained using a standard technique such as simulated annealing on a defect-free PGA. In the next step, this placement is reconfigured so that the circuit is mapped onto the defect-free portion of a defective PGA chip with the same architecture. We first formulate the reconfiguration aspect of this approach as a problem of shifting pebbles on a graph. We present efficient reconfiguration algorithms for this pebble shift problem. Using these algorithms as heuristics, we develop a yield enhancement system not only for PGA's, but also for programmable Wafer Scare Integrated (WSI) processor arrays. We evaluate the heuristic algorithms using the measures of routability and total wire length of the reconfigured placement of the circuit. Based on this evaluation, we establish proper reconfiguration strategies.>

The vertex- (respectively, edge-) deletion graph bipartization problem is the problem of deleting a set of vertices (respectively, edges) from a graph so as to make the remaining graph bipartite. This paper first shows that the vertex-deletion graph bipartization problem has a solution of size k or less if and only if the edge-deletion graph bipartization problem has a solution of size k or less, when the maximum vertex degree is limited to three. This immediately implies that (1) the vertex-deletion graph bipartization problem is NP-complete for cubic graphs, and (2) the minimum vertex-deletion graph bipartization problem is solvable in polynomial time for planar graphs when the maximum vertex degree is limited to three. It is then proved that the vertex-deletion graph bipartization problem is NP-complete for planar graphs when the maximum vertex degree exceeds three. Using this result, it is finally shown that the via minimization problem, which arises in the design of integrated circuits and printed circuit boards, is NP-complete even when the maximum “junction” degree is limited to four.

In the past, several heuristic algorithms were developed for the topological via minimization problem. It was very recently shown to be NP-hard even for the two-layer channel routing case with two-terminal nets only. The authors show that if no local net exists in a channel, this problem is solvable in O(kn/sup 2/) time even for k layers, where n is the number of two-terminal nets. As an extension of this case, they consider the problem for the case of k-layer circular channel routing in which no local net exists and present an O(n/sup 2k+1/) time algorithm.>