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