AN ENHANCED SIMULATED ANNEALING APPROACH FOR CYLINDRICAL, RECTANGULAR MESH, AND SEMI-DIAGONAL TORUS NETWORK TOPOLOGIES NORAZIAH BINTI ADZHAR A thesis submitted in fulfilment of the requirements for the award of the degree of Doctor of Philosophy (Mathematics) Faculty of Science Universiti Teknologi Malaysia NOVEMBER 2015 iii To my beloved father and mother, To my family and friends, To all muslim ummah. iv ACKNOWLEDGEMENT All praise is to Allah , the truth and the only God deserved of All Praises and Submissions. Peace and blessing to the blessed and chosen prophet, Muhammad ﷺ, who is the messenger and the teacher of truth. There is no power except by the power of Allah and I humbly return my acknowledgement that all knowledge belongs to Allah. I thank Allah for granting me this opportunity to broaden my knowledge in this field. Nothing is possible unless He made it possible. A lot of work, time, effort and energy were place upon this research. Nonetheless, the journey going through the process of becoming learned and experienced individual, with more courage and perseverance was a very tough one. First and foremost I would like to express my deepest appreciation to my supervisor, Prof. Dr. Shaharuddin Salleh for unchallenged patient, for exhausted support and for always believe in me. His extensive knowledge and guidance have been of great help throughout the process from the initial stage, all the way through to the end. I acknowledge, appreciate, and return the love and support of my family, without whom I would be lost. To En. Adzhar and Pn. Maisarah, thank you very much for your continuous support. May Allah bless all of you. My very special thanks goes to Pn. Farhana binti Johar for words of encouragement and for solving technical problems I faced with computer program promptly. Last but not least, special thanks to Ministry of Education for the scholarship given and Universiti Teknologi Malaysia for supporting part of this research. My sincere appreciation is to all colleagues and others who have help me in any ways either direct and indirectly. Thank you all. v ABSTRACT A multiprocessing system has processor-memory modules in a network which is always referred to as net. In many cases, the modules are placed in a regular arrangement such as rectangular grid, bus, star and hypercube. In this research, we proposed one conceptual model and two network topologies for routing the elements of the network. In the first model, a static single-row network was transformed into a dynamic three-dimensional cylindrical model. This new routing model has its axis perpendicular to single-row planes, which gives the advantage of allowing unlimited connections between the pairs of elements based on the program requirements. The single-row routings in each network were produced optimally using the earlier model called Enhanced Simulated Annealing for Single-row Routing (ESSR). In the second part of this research, mesh network topology which consists of an array of square cells was proposed as our routing platform to achieve a complete automatic routing. The problem was further split into two cases; first, a fully gridded network to minimize the number of layers and second, the obstacle avoidance network model. Dijkstra‟s shortest path algorithm was used to provide the shortest path for each net. The arrangement was further refined using a simulated annealing method. From this technique, the minimum number of layers was produced to complete the routing with lower energy level and to provide the best path if it exists, with the presence of obstacles. The last part of this research is an extension of our previous work, where a more scalable and regular network called semi-diagonal torus (SD-Torus) network was used as a routing platform instead of the mesh network. The performance of SD-Torus network was much better compared to torus and mesh networks in terms of energy level and the number of routed nets. The network topology performed complete routing up to 81 nodes with 80 nets in 99 network size. This technique maximizes the number of nets through the minimum energy. The simulations for each network are developed using Microsoft Visual C++ 2010 programming language. vi ABSTRAK Sebuah sistem multipemprosesan terdiri daripada pasangan modul prosesor- memori dalam sebuah rangkaian yang sering dirujuk sebagai jaring. Dalam kebanyakan kes, modul ini disusun dalam susunan yang tetap seperti grid segi empat tepat, bus, torus dan hiperkiub. Dalam penyelidikan ini, kami mencadangkan satu model konseptual dan dua topologi rangkaian bagi menghalakan setiap elemen di dalam rangkaian. Dalam model yang pertama, sebuah rangkaian baris tunggal yang bersifat statik telah dijelmakan menjadi sebuah model silinder tiga dimensi yang dinamik. Model laluan yang baharu ini mempunyai paksinya serenjang kepada satah baris tunggal yang mempunyai kelebihan untuk membenarkan jumlah sambungan tanpa had bagi setiap pasangan elemen, bergantung kepada keperluan program. Laluan baris tunggal bagi setiap rangkaian dihasilkan secara optimum melalui program terdahulu yang dipanggil Simulasi Penyepuhlindapan yang dipertingkatkan bagi Laluan Baris Tunggal (ESSR). Dalam bahagian yang kedua bagi kajian ini, rangkaian topologi mesh yang terdiri daripada susunan sel segi empat sama dicadangkan menjadi landasan laluan bagi mencapai laluan automatik yang lengkap. Masalah ini kemudiannya dibahagikan kepada dua kes, kes pertama, model bergrid penuh untuk meminimumkan bilangan lapisan dan kes kedua, model penghindaran halangan. Algoritma laluan terpendek Dijkstra diguna pakai untuk menghasilkan laluan terpendek bagi setiap jaring. Susunan setiap jaring pula ditapis lagi menggunakan kaedah simulasi penyepuhlindapan. Daripada teknik ini, lapisan minimum dapat dihasilkan bagi melengkapkan laluan dengan tahap tenaga yang lebih rendah dan juga memberi laluan terbaik jika wujud walaupun dengan kehadiran halangan. Bahagian terakhir penyelidikan ini merupakan lanjutan kepada kajian terdahulu kami, di mana rangkaian yang lebih mudah diskalakan dan beraturan tetap yang dinamakan Rangkaian Torus Separuh Perpenjuru (SD-Torus), digunakan sebagai landasan laluan menggantikan rangkaian mesh. Prestasi rangkaian SD-Torus adalah lebih baik dibandingkan dengan rangkaian torus dan mesh dari segi tahap tenaga dan bilangan jaring yang dihalakan. Topologi rangkaian ini melaksanakan laluan lengkap sehingga 81 nod dengan 80 jaring di dalam rangkaian bersaiz 99. Teknik ini memaksimumkan jumlah sambungan jaring melalui tahap tenaga yang minimum. Simulasi bagi setiap rangkaian dibina menggunakan bahasa pengaturcaraan Microsoft Visual C++ 2010. TABLE OF CONTENTS CHAPTER TITLE PAGE DECLARATION ii DEDICATION iii ACKNOWLEDGEMENTS iv ABSTRACT v ABSTRAK vi TABLE OF CONTENTS vii LIST OF FIGURES xi LIST OF TABLES xv LIST OF SYMBOLS xvii LIST OF APPENDIX xix 1 INTRODUCTION 1 1.1 Research Background 1 1.2 Motivation 6 1.3 Problem Statement 6 1.4 Research Problems 7 1.5 Research Objectives 8 1.6 Scope of the Study 8 1.7 Significance of Findings 8 1.8 Research Workflow 9 1.9 Thesis Outline 13 2 LITERATURE REVIEW 15 2. 1 Introduction to Electronic Design Automation (EDA) 15 2. 2 Mathematical Model 17 2. 3 Routing in PCB/VLSI Design 19 2. 4 Single-row Routing Problem 20 2. 5 Global Routing Problem 22 2.5.1 Global Routing Methods 24 2. 6 The Single-source Shortest Path problem 25 2.6.1 Eigenvalue of an Adjacency Matrix 27 2.6.2 Breadth-first Search Method 29 2.6.3 Example on BFS 29 2.6.4 Dijkstra‟s Algorithm 32 2.6.5 Example of Dijkstra‟s Algorithm 34 2.6.6 Proof of Correctness of Dijkstra‟s Algorithm 36 2.6.7 Related Algorithms 37 2.6.8 Applications of Dijkstra‟s Algorithm 40 2. 7 Exact Method and Approximate Method 41 2.6.1 Simulated Annealing Technique 41 2. 8 Interconnection Networks 43 2.8.1 Network-on-Chip Topologies 43 2. 9 Conclusion 47 3 THREE-DIMENSIONAL CYLINDRICAL MODEL FOR SINGLE-ROW DYNAMIC ROUTING 49 3.1 Introduction 49 3.2 Problem Background 51 3.3 Energy Level Diagram and Graphical Realization 53 3.4 Enhanced Simulated Annealing for Single-row Routing (ESSR) 56 3.5 Multi Connection of Pins Using the Cylindrical Model 59 ix 3.5.1 Maximum Possible Net Ordering 59 3.6 The Dynamic SA-CM Model 65 3.7 Simulation Results 69 3.8 Conclusion 71 4 SEQUENTIAL GLOBAL ROUTING PROBLEM IN VLSI DESIGN 73 4.1 Introduction 73 4.2 Problem Statement 77 4.3 Mathematical Model 78 4.4 The Impact of Net Ordering on Global Routing 80 4.5 Heuristics Improvement 81 4.5.1 Simulated Annealing Method 82 4.5.2 Initial Algorithm for Routing 82 4.5.3 Routing Algorithm 83 4.5.4 Greedy Method 85 4.6 Layers for The Minimization Model 87 4.6.1 Simulation Results 88 4.7 Obstacle-Avoiding Problem 97 4.7.1 Simulation Results 199 4.8 Conclusion 104 5 SEMI-DIAGONAL TORUS NETWORK FOR GENERAL PURPOSE NETWORKING APPLICATIONS 105 5.1 Introduction 105 5.2 Problem Statement 108 5.3 Mesh and Torus Network Topologies 109 5.3.1 Mesh Network Topologies 109 5.3.2 Torus Topologies 110 x 5.4 Semi-Diagonal Torus Network 111 5.4.1 Topological Properties 112 5.4.2 Network Diameter 113 5.4.3 Number of Communication Links in a Network 115 5.4.4 Topological Properties Comparison 118 5.5 SA-SDT Routing Network 118 5.6 Simulation Results 120 5.6.1 Comparison Between Network Topologies 121 5.6.2 Comparison Between Simulated Annealing and Greedy Method 126 5.7 Conclusion 128 6 CONCLUDING REMARKS AND FURTHER WORK 130 6.1 Summary of Findings 130 6.2 Suggestions for Further Research 134 REFERENCES 135 Appendix 148 xi LIST OF FIGURES FIGURE NO. TITLE PAGE 1.1 The demand for electronic circuits during vacuum-tube era and during the invention of transistor and ICs. 2 1.2 The chip scope and the sequence of technologies in circuit integration. 3 1.3 Evolution on bus on-chip communications. 4 1.4 A 44mesh NoC topology. 5 1.5 Research workflow. 12 2.1 General flow of physical design. 16 2.2 The single-row routing terminologies . 21 2.3 (a) Partitioned layout into nn rectangular array. (b) Resource modeling. (c) Global-routing graph. 23 2.4 Previous approach on sequential global routing. 24 2.5 A connected graph. 26 2.6 Graph to be explored using breadth-first search method. 30 2.7 The neighbors of vertex 1 have been explored and queued up. 30 2.8 Current status of BFS progress. Next entries in the queue list are vertex 5 and vertex 6. 31 2.9 The BFS tree constructed from graph shown in Figure 2.6. 31 2.10 The connected graph. 34 2.11 The schematic illustration for the justification of Lemma 2.1. 36