| Author | Lalinthip Tangjittaweechai |
| Note | A dissertation submitted in partial fulfillment of the requirements for the
degree of Doctor of Philosophy in
Microelectronics and Embedded Systems |
| Publisher | Asian Institute of Technology |
| Abstract | The shortest path algorithm and the longest path algorithm are two of the crucial algorithms in many applications. Their applications span in almost all areas in
computing. VLSI in particular is one area that benefits from such algorithms. The
shortest/longest path algorithm is usually called thousands or millions of iterations until a good and feasible solution is obtained. Hence, substantial amount of time in many VLSI algorithms is spent during this shortest/longest path calculation. In this dissertation, we focus on parallel computing paradigm to speed up the calculation of the shortest path and the longest path algorithms. General-Purpose computing on Graphics Processing Unit (GPGPU) computing paradigm which utilizes hundreds or thousands of
graphics cores to perform computation in parallel is employed to speed up the
shortest/longest path algorithm. The first part of our dissertation is to propose an
algorithm solving the shortest path problem. We propose a parallel single-pair shortest path based on Dijkstra’s shortest path algorithm using bidirectional search technique on GPGPU. We double the throughput by traversing the graph from both source and target using parallel Dijkstra’s algorithm simultaneously. We also introduce the early termination case and the search pruning to enhance the performance of the algorithm. Our implementation can speedup nearly 2x over a parallel method that performs a single
parallel search from the source to all other nodes on the GPGPU with the early
termination once the shortest path from the specific source to the specific target has been specified. The second part of our dissertation is to propose an algorithm solving the longest path problem. A retiming-based timing analysis is proposed in this section and it is based on the Bellman-Ford algorithm solving the longest path problem. The algorithm works with cyclic graphs. We integrate this retiming-based timing analysis with GPGPU into a min-cut based placer to evaluate its performance. The results show that we can achieve up to 24× runtime improvement with the average of 8×. |
| Year | 2016 |
| Type | Dissertation |
| School | School of Engineering and Technology (SET) |
| Department | Department of Industrial Systems Engineering (DISE) |
| Academic Program/FoS | Microelectronics (ME) |
| Chairperson(s) | Mongkol Ekpanyapong; |
| Examination Committee(s) | Huynh Trung Luong;Krit Athikulwongse;Weng-Fai, Wong ; |
| Scholarship Donor(s) | Royal Thai Government;AIT Fellowship; |
| Degree | Thesis (Ph.D.) -- Asian Institute of Technology, 2016 |