SHF:Small:Parallel ILP-Based Global Routing on A Grid of Multi-Cores

如果没有自动化集成数十亿纳米级组件的工具，今天的电子系统设计是不可能的。植入iPhone的“大脑”。随着技术向更小更强大的移动设备发展，这些工具需要像它们帮助设计的系统一样快速发展——实际上更快，因为纳米级组件不仅在数量上增长，而且在尺寸上缩小，随之而来的是新的挑战。为了改进现有的设计辅助工具，一个新的机会窗口出现了，因为一个更强大但更实惠的计算平台的出现：多核计算机网络一起工作，就好像它是一个巨大的机器。通过利用这个平台，提出的研究调查了传统上被认为太耗时的替代设计自动化策略。这项研究的重点是改进设计过程中一个重要的步骤，即全局路由，在这个步骤中，设计者计划如何在芯片上连接数十亿纳米级组件。在设计周期的后续阶段，该计划会显著影响许多问题的严重性，但必须快速完成。在网格提供的大规模并行性的帮助下，该研究旨在证明一种称为整数规划的计算技术的使用，这种技术以前被认为对于全局路由来说过于耗时，可以帮助生成明显更高质量的解决方案，同时满足实际的运行时要求。研究的成功完成有助于电子产品以更低的设计成本更快地推向市场，从而使企业更强大，从而可以在科技领域开展新项目，从而创造更多就业机会。

Design of today's electronic systems would not be possible without the tools that automate the process of integrating billions of nano-scale components--e.g. into the "brain" of an iPhone. As technology advances towards mobile devices that are smaller yet more powerful, these tools need to evolve as fast as the systems that they help design--in fact faster, because the nano-scale components not only grow in numbers but also shrink in size, bringing along with them new challenges.To improve existing design-aid tools, a new window of opportunity has arisen due to the emergence of a more powerful yet affordable computational platform: a network of multi-core computers working together as if it were one enormous machine. By leveraging this platform the proposed research investigates alternative design automation strategies which traditionally were deemed to be too time-consuming. The focus of the research is to improve an important step of the design process known as global routing, the step in which designers plan how the billions of nano-scale components will be interconnected on the chip. This planning can significantly impact the severity of many issues in subsequent stages of the design cycle, yet it has to be done quickly. With the aid of large-scale parallelism provided by grids, the research aims to demonstrate that the use of a computational technique called integer programming, which was previously viewed as too time-consuming for global routing, can help generate significantly higher quality solutions while meeting practical runtime requirements.Successful completion of the research contributes to faster delivery of electronic products to market with lower design cost, resulting in stronger businesses that can initiate new projects in the technology sector, and hence in the creation of more jobs.