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.