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

University Of Wisconsin-Madison, Madison WI

Investigators

Abstract

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.