Accuracy and fidelity of fast net length estimates
| Autor: | Joseph L. Ganley |
|---|---|
| Rok vydání: | 1997 |
| Předmět: |
Very-large-scale integration
Mathematical optimization Heuristic (computer science) media_common.quotation_subject Rectilinear Steiner tree Fidelity Steiner tree problem symbols.namesake Hardware and Architecture Hardware_INTEGRATEDCIRCUITS symbols Electrical and Electronic Engineering Routing (electronic design automation) Heuristics Algorithm Software Statistic media_common Mathematics |
| Zdroj: | Integration. 23:151-155 |
| ISSN: | 0167-9260 |
| DOI: | 10.1016/s0167-9260(97)00019-9 |
| Popis: | Most popular tools for VLSI placement rely on some type of local search algorithm to iteratively refine a given placement solution. In such algorithms, it is necessary to evaluate the total amount of routing that a given placement will require. Typially, rectilinear Steiner tree heuristics are used to estimate the routing length of a placement. When evaluating heuristics, researchers typically focus on their ```absolute`` accuracy, i.e., how nearly optimal are their solutions? However, here a more pertinent statistic is their ```relative accuracy``, i.e. how likely is it that a given heuristic will agree with the optimum on which of two instances has the shorter routing? In this paper, we experimentally evaluate four popular net length estimation heuristics, with respect to both their absolute and relative accuracy as well as their speed. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect