Gate matrix layout revisited: Algorithmic performance and probabilistic analysis View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1989

AUTHORS

Sajal K. Das , Narsingh Deo , Sushil Prasad

ABSTRACT

We consider the gate matrix layout problem for VLSI design, and improve the time and space complexities of an existing dynamic programming algorithm for its exact solution. Experimental study indicates the requirement of enormous computation time for exact solutions of even small size matrices. We derive an expression for the expected number of tracks required to layout in gate matrix style based on a probabilistic model. A local search approximation algorithm is studied experimentally and found to perform reasonably well on average. More... »

PAGES

280-290

Book

TITLE

Foundations of Software Technology and Theoretical Computer Science

ISBN

978-3-540-52048-1
978-3-540-46872-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-52048-1_50

DOI

http://dx.doi.org/10.1007/3-540-52048-1_50

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1035530104


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of North Texas", 
          "id": "https://www.grid.ac/institutes/grid.266869.5", 
          "name": [
            "Department of Computer Science, University of North Texas, 76203\u00a0Denton, TX, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Das", 
        "givenName": "Sajal K.", 
        "id": "sg:person.012234460346.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012234460346.39"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Central Florida", 
          "id": "https://www.grid.ac/institutes/grid.170430.1", 
          "name": [
            "Department of Computer Science, University of Central Florida, 32816\u00a0Orlando, FL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Deo", 
        "givenName": "Narsingh", 
        "id": "sg:person.010274011142.47", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010274011142.47"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Central Florida", 
          "id": "https://www.grid.ac/institutes/grid.170430.1", 
          "name": [
            "Department of Computer Science, University of Central Florida, 32816\u00a0Orlando, FL, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Prasad", 
        "givenName": "Sushil", 
        "id": "sg:person.012217451543.37", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012217451543.37"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1016/s0022-0000(76)80045-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030334487"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tcad.1985.1270118", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061536459"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tcad.1987.1270248", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061536589"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/tcs.1979.1084695", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061563149"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1989", 
    "datePublishedReg": "1989-01-01", 
    "description": "We consider the gate matrix layout problem for VLSI design, and improve the time and space complexities of an existing dynamic programming algorithm for its exact solution. Experimental study indicates the requirement of enormous computation time for exact solutions of even small size matrices. We derive an expression for the expected number of tracks required to layout in gate matrix style based on a probabilistic model. A local search approximation algorithm is studied experimentally and found to perform reasonably well on average.", 
    "editor": [
      {
        "familyName": "Veni Madhavan", 
        "givenName": "C. E.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-52048-1_50", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-52048-1", 
        "978-3-540-46872-1"
      ], 
      "name": "Foundations of Software Technology and Theoretical Computer Science", 
      "type": "Book"
    }, 
    "name": "Gate matrix layout revisited: Algorithmic performance and probabilistic analysis", 
    "pagination": "280-290", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-52048-1_50"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "a93ff5d6d4efc1e7baad1d1702236d8749db5633dbd268414562c03bac75ac4b"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1035530104"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-52048-1_50", 
      "https://app.dimensions.ai/details/publication/pub.1035530104"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T14:26", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000001_0000000264/records_8669_00000265.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/3-540-52048-1_50"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/3-540-52048-1_50'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/3-540-52048-1_50'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-52048-1_50'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-52048-1_50'


 

This table displays all metadata directly associated to this object as RDF triples.

94 TRIPLES      23 PREDICATES      31 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-52048-1_50 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N297561599471452abe9047c46c5a9b19
4 schema:citation https://doi.org/10.1016/s0022-0000(76)80045-1
5 https://doi.org/10.1109/tcad.1985.1270118
6 https://doi.org/10.1109/tcad.1987.1270248
7 https://doi.org/10.1109/tcs.1979.1084695
8 schema:datePublished 1989
9 schema:datePublishedReg 1989-01-01
10 schema:description We consider the gate matrix layout problem for VLSI design, and improve the time and space complexities of an existing dynamic programming algorithm for its exact solution. Experimental study indicates the requirement of enormous computation time for exact solutions of even small size matrices. We derive an expression for the expected number of tracks required to layout in gate matrix style based on a probabilistic model. A local search approximation algorithm is studied experimentally and found to perform reasonably well on average.
11 schema:editor N7e613853b7464ba5b8c2d550d0977e5b
12 schema:genre chapter
13 schema:inLanguage en
14 schema:isAccessibleForFree false
15 schema:isPartOf N34c5d90d92db4712a87fd41a1b583f34
16 schema:name Gate matrix layout revisited: Algorithmic performance and probabilistic analysis
17 schema:pagination 280-290
18 schema:productId N516b356a9d684cc8a35983a0f15aceee
19 N7e15a6540acd4f9c991aa541985b275d
20 Nfdbdc939450c487bab7473fbd743e99d
21 schema:publisher N0985ded1e54d41b18da5994e1f266dc3
22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035530104
23 https://doi.org/10.1007/3-540-52048-1_50
24 schema:sdDatePublished 2019-04-15T14:26
25 schema:sdLicense https://scigraph.springernature.com/explorer/license/
26 schema:sdPublisher N20db4d8d3dee4afea626a95f90e7081c
27 schema:url http://link.springer.com/10.1007/3-540-52048-1_50
28 sgo:license sg:explorer/license/
29 sgo:sdDataset chapters
30 rdf:type schema:Chapter
31 N050f65aa028d43158977c9535d227a3c schema:familyName Veni Madhavan
32 schema:givenName C. E.
33 rdf:type schema:Person
34 N0985ded1e54d41b18da5994e1f266dc3 schema:location Berlin, Heidelberg
35 schema:name Springer Berlin Heidelberg
36 rdf:type schema:Organisation
37 N20db4d8d3dee4afea626a95f90e7081c schema:name Springer Nature - SN SciGraph project
38 rdf:type schema:Organization
39 N297561599471452abe9047c46c5a9b19 rdf:first sg:person.012234460346.39
40 rdf:rest N42b4d828ab4f409d8fd4fc531f48536b
41 N34c5d90d92db4712a87fd41a1b583f34 schema:isbn 978-3-540-46872-1
42 978-3-540-52048-1
43 schema:name Foundations of Software Technology and Theoretical Computer Science
44 rdf:type schema:Book
45 N42b4d828ab4f409d8fd4fc531f48536b rdf:first sg:person.010274011142.47
46 rdf:rest N6b1bf70216354f4c8c5d70a49e32c08e
47 N516b356a9d684cc8a35983a0f15aceee schema:name doi
48 schema:value 10.1007/3-540-52048-1_50
49 rdf:type schema:PropertyValue
50 N6b1bf70216354f4c8c5d70a49e32c08e rdf:first sg:person.012217451543.37
51 rdf:rest rdf:nil
52 N7e15a6540acd4f9c991aa541985b275d schema:name dimensions_id
53 schema:value pub.1035530104
54 rdf:type schema:PropertyValue
55 N7e613853b7464ba5b8c2d550d0977e5b rdf:first N050f65aa028d43158977c9535d227a3c
56 rdf:rest rdf:nil
57 Nfdbdc939450c487bab7473fbd743e99d schema:name readcube_id
58 schema:value a93ff5d6d4efc1e7baad1d1702236d8749db5633dbd268414562c03bac75ac4b
59 rdf:type schema:PropertyValue
60 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
61 schema:name Information and Computing Sciences
62 rdf:type schema:DefinedTerm
63 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
64 schema:name Computation Theory and Mathematics
65 rdf:type schema:DefinedTerm
66 sg:person.010274011142.47 schema:affiliation https://www.grid.ac/institutes/grid.170430.1
67 schema:familyName Deo
68 schema:givenName Narsingh
69 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010274011142.47
70 rdf:type schema:Person
71 sg:person.012217451543.37 schema:affiliation https://www.grid.ac/institutes/grid.170430.1
72 schema:familyName Prasad
73 schema:givenName Sushil
74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012217451543.37
75 rdf:type schema:Person
76 sg:person.012234460346.39 schema:affiliation https://www.grid.ac/institutes/grid.266869.5
77 schema:familyName Das
78 schema:givenName Sajal K.
79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012234460346.39
80 rdf:type schema:Person
81 https://doi.org/10.1016/s0022-0000(76)80045-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030334487
82 rdf:type schema:CreativeWork
83 https://doi.org/10.1109/tcad.1985.1270118 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061536459
84 rdf:type schema:CreativeWork
85 https://doi.org/10.1109/tcad.1987.1270248 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061536589
86 rdf:type schema:CreativeWork
87 https://doi.org/10.1109/tcs.1979.1084695 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061563149
88 rdf:type schema:CreativeWork
89 https://www.grid.ac/institutes/grid.170430.1 schema:alternateName University of Central Florida
90 schema:name Department of Computer Science, University of Central Florida, 32816 Orlando, FL, USA
91 rdf:type schema:Organization
92 https://www.grid.ac/institutes/grid.266869.5 schema:alternateName University of North Texas
93 schema:name Department of Computer Science, University of North Texas, 76203 Denton, TX, USA
94 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...