• 主题
高级搜索  >
历史搜索 清空历史
首页> 美国政府科技报告 >Finding Minimum Width for Single-Layer Channel Routing in Linear Time
【24h】

Finding Minimum Width for Single-Layer Channel Routing in Linear Time

机译：在线性时间内寻找单层信道路由的最小宽度

获取原文
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In recent years, a good deal of attention has been given to the problem of planaror single-layer wire routing for VLSI chips. Especially popular has been river routing in the restricted sense of the term, i.e., the connection of two parallel rows of corresponding points. Other works have considered routing within a rectangle placement and routing within a ring of pads or routing between very general arrangements of modules. This paper concentrates on showing that the minimum separation problem (in the rectilinear wiring model) can be solved in linear time for any single-layer channel routing problem, even with single-sided connections. In the process, this paper clearly provides a linear-time solution to the routability problem which simply asks whether a routing is possible given a fixed vertical separation as well as fixed horizontal positions of the terminals. We also briefly discuss generalization from channels to switchboxes, demonstrating, in particular, a simple routability test for switchboxes. Comparable results could be obtained fairly directly from the work of Cole and Siegel, but this paper gives a simpler exposition by concentrating on the special cases of channels and switchboxes. Detailed but concise pseudocode is provided for the channel separation problem. (kr)

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号