Accelerating Physical design Algorithms using CUDA

The intricate domain of chip design encompasses the creation of intricate blueprints for integrated circuits (ICs). Algorithms, pivotal in this realm, assume the role of optimizing IC performance and functionality. This thesis delves into the utilization of algorithms within chip design, spotlighting their potential to amplify design process efficiency and efficacy. Notably, this study undertakes a comprehensive comparison of algorithmic performances on both Central Processing Units (CPUs) and Graphics Processing Units (GPUs). A cornerstone application of algorithms in chip design lies in logic synthesis, which transmutes a high-level circuit description into a silicon-compatible, low-level representation. By minimizing gate requisites, curtailing power consumption, and bolstering performance, algorithms serve as architects of optimized logic synthesis. Furthermore, the arena of physical design harnesses algorithms to translate logical designs into physically realizable layouts on silicon wafers. This involves meticulous considerations like routing congestion and power efficiency. Furthermore, this thesis adopts a thorough approach by extensively exploring the implementation intricacies of two pivotal physical design algorithms. The Kernighan-Lin Partitioning Algorithm is prominently featured for optimizing Placement and Partitioning, while Lee’s Algorithm provides valuable insights for enhancing Routing. Through a meticulous comparison of dataset efficiency and run-time across both hardware platforms, noteworthy insights have emerged. In KL Algorithm, datasets categorized as small (with sizes < 105), the CPU demonstrates a 1.2X faster processing speed compared to the GPU. However, as dataset sizes surpass this threshold, a distinct trend emerges: while GPU run times remain relatively consistent, CPU run times undergo a threefold increase at select points. In the case of Lee’s Algorithm, the CPU demonstrated superior execution time despite having fewer cores and threads than the GPU. This can be attributed to the inherently sequential nature of Lee’s Algorithm, where each element depends on the preceding one, aligning with the CPU's strength in handling sequential tasks. This thesis embarks on a comprehensive analytical journey, delving into the nuanced interplay between these contrasting aspects.