Sponsor
Portland State University. Department of Electrical Engineering
First Advisor
Malgorzata Chrzanowska-Jeske
Date of Publication
11-5-1993
Document Type
Thesis
Degree Name
Master of Science (M.S.) in Electrical and Computer Engineering
Department
Electrical Engineering
Language
English
Subjects
Heuristic programming, Computer algorithms
DOI
10.15760/etd.6469
Physical Description
1 online resource (2, v, 72 p.)
Abstract
As the Application-Specific Integrated Circuit(ASIC) technology develops to the trend of high density and modulization, the ASIC device market has been dominated gradually by the more complex Erasable Programmable Logic Devices (EPLDs) and the Field Programmable Gate Array(FPGAs) instead of the ordinally Programmable Logic Devices(PLDs). Meanwhile, the design automation system for such programmable devices has also moved from schematic entry design to high level hardware description language entry design. Usually, the whole design automation process consists of three phrases, the high level hardware description language compiler, the logic synthesis stage and the layout synthesis stage. Though the layout synthesis stage contains placement and routing, for some highly restricted connection architecture devices, placement and routing have to be considered together as a fitting problem. This thesis concentrated on the utilization of the Heuristic methods, which can be described as vertex ordering and global vertices number estimation, on an Architecture-Driven Partitioning fitting algorithm. The test results showed that the heuristic algorithm can beat the comparable algorithm in several fields. These prove the correctness of our heuristic methods and they can be used to guide the future work on the fitting problem of other similar programmable devices.
Rights
In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
Persistent Identifier
https://archives.pdx.edu/ds/psu/26594
Recommended Citation
Gao, Tongjun, "Vertex Ordering for a Partitioning-based Fitting Algorithm for an EPLD Device" (1993). Dissertations and Theses. Paper 4585.
https://doi.org/10.15760/etd.6469
Comments
If you are the rightful copyright holder of this dissertation or thesis and wish to have it removed from the Open Access Collection, please submit a request to pdxscholar@pdx.edu and include clear identification of the work, preferably with URL