Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


ucin1006804309.pdf (795.6 KB)

ETD Abstract Container

Abstract Header

HEURISTICS AND EXPERIMENTAL DESIGN FOR FPGA ROUTING ALGORITHMS

GAO, LI
http://rave.ohiolink.edu/etdc/view?acc_num=ucin1006804309

Abstract Details

2001, MS, University of Cincinnati, Engineering : Computer Science.
Chairperson of the Supervisory Committee:Professor Carla Purdy Department of Electrical and Computer Engineering and Computer Science Many of the problems arising in electronic design automation are NP-hard and require heuristic algorithms, which can only be analyzed and compared through experiments. Unfortunately, it is often unclear to experimenters if enough data has been gathered, what statistics to run, and how to visualize results. The purpose of this paper is to demonstrate a general experimental design procedure for heuristics evaluation and a new evaluation tool developed by B. Billups and this author to help with the data analysis and visualization. To demonstrate this procedure and tool, sorting algorithms are implemented and compared as a short example. Then the FPGA routing is selected as a target NP-hard problem to discuss, and three heuristic algorithms, PathFinder, Frontier and VPR430, are statistically compared based on the experimental data collected using careful experimental design. As part of this work we also discuss in detail how to measure the processor time for an algorithm. Result! s show that VPR430 and Frontier are proven to be significantly faster than PathFinder but with loss of some performance. PathFinder gives the best solution but it takes much longer time than other two algorithms. These results are consistent with the results in the literature, but provide a more detailed analysis of these three algorithms and show the effect of more thorough experimentation.
Dr. Carla Purdy (Advisor)
77 p.
Computer Science
HEURISTICS; FPGA; CPU TIME MEASUREMENT; EXPERIMENTAL DESIGN

Recommended Citations

Citations

  • GAO, L. (2001). HEURISTICS AND EXPERIMENTAL DESIGN FOR FPGA ROUTING ALGORITHMS [Master's thesis, University of Cincinnati]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1006804309

    APA Style (7th edition)

  • GAO, LI. HEURISTICS AND EXPERIMENTAL DESIGN FOR FPGA ROUTING ALGORITHMS. 2001. University of Cincinnati, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ucin1006804309.

    MLA Style (8th edition)

  • GAO, LI. "HEURISTICS AND EXPERIMENTAL DESIGN FOR FPGA ROUTING ALGORITHMS." Master's thesis, University of Cincinnati, 2001. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1006804309

    Chicago Manual of Style (17th edition)

ucin1006804309
867
© 2001, all rights reserved.
This open access ETD is published by University of Cincinnati and OhioLINK.