Optimal clustering for delay minimization

Rajmohan Rajaraman; D. F. Wong

doi:10.1145/157485.164907

Optimal clustering for delay minimization

Rajmohan Rajaraman, D. F. Wong

Office of the Provost

Research output: Chapter in book/report/conference proceeding › Conference proceeding › peer-review

38 Citations (Scopus)

Abstract

This paper addresses the problem of circuit clustering for delay minimization, subject to capacity constraints. We use the general delay model, for which only heuristic solutions were unknown. We present an optimal polynomial time algorithm for combinational circuits under this model. Our algorithm can be generalized to solve the problem under any monotone clustering constraint.

Original language	English
Title of host publication	30th ACM/IEEE Design Automation Conference - Proceedings 1993
Publisher	Association for Computing Machinery (ACM)
Pages	309-314
Number of pages	6
ISBN (Print)	0897915771, 9780897915779
DOIs	https://doi.org/10.1145/157485.164907
Publication status	Published - Jul 1993
Event	30th ACM/IEEE Design Automation Conference, DAC 1993 - Dallas, United States Duration: 14 Jun 1993 → 18 Jun 1993 https://dl.acm.org/doi/proceedings/10.1145/157485 https://ieeexplore.ieee.org/xpl/conhome/10664/proceeding

Publication series

Name	ACM/IEEE Design Automation Conference - Proceedings
ISSN (Print)	0738-100X

Conference

Conference	30th ACM/IEEE Design Automation Conference, DAC 1993
Country/Territory	United States
City	Dallas
Period	14/06/93 → 18/06/93
Internet address	https://dl.acm.org/doi/proceedings/10.1145/157485 https://ieeexplore.ieee.org/xpl/conhome/10664/proceeding

Scopus Subject Areas

General Engineering

Access to Document

10.1145/157485.164907

Cite this

@inproceedings{ee00994f6e9d4c2fa0bef7ae7872b749,

title = "Optimal clustering for delay minimization",

abstract = "This paper addresses the problem of circuit clustering for delay minimization, subject to capacity constraints. We use the general delay model, for which only heuristic solutions were unknown. We present an optimal polynomial time algorithm for combinational circuits under this model. Our algorithm can be generalized to solve the problem under any monotone clustering constraint.",

author = "Rajmohan Rajaraman and Wong, {D. F.}",

note = "This work was partially supported by the National Science Foundation under grant MIP-8909586, by an ACM SIGDA Design Automation Fellowship, and by an MCD Fellowship from the University of Texas at Austin.; 30th ACM/IEEE Design Automation Conference, DAC 1993 ; Conference date: 14-06-1993 Through 18-06-1993",

year = "1993",

month = jul,

doi = "10.1145/157485.164907",

language = "English",

isbn = "0897915771",

series = "ACM/IEEE Design Automation Conference - Proceedings",

publisher = "Association for Computing Machinery (ACM)",

pages = "309--314",

booktitle = "30th ACM/IEEE Design Automation Conference - Proceedings 1993",

address = "United States",

url = "https://dl.acm.org/doi/proceedings/10.1145/157485, https://ieeexplore.ieee.org/xpl/conhome/10664/proceeding",

}

Rajaraman, R & Wong, DF 1993, Optimal clustering for delay minimization. in 30th ACM/IEEE Design Automation Conference - Proceedings 1993. ACM/IEEE Design Automation Conference - Proceedings, Association for Computing Machinery (ACM), pp. 309-314, 30th ACM/IEEE Design Automation Conference, DAC 1993, Dallas, Texas, United States, 14/06/93. https://doi.org/10.1145/157485.164907

TY - GEN

T1 - Optimal clustering for delay minimization

AU - Rajaraman, Rajmohan

AU - Wong, D. F.

N1 - This work was partially supported by the National Science Foundation under grant MIP-8909586, by an ACM SIGDA Design Automation Fellowship, and by an MCD Fellowship from the University of Texas at Austin.

PY - 1993/7

Y1 - 1993/7

N2 - This paper addresses the problem of circuit clustering for delay minimization, subject to capacity constraints. We use the general delay model, for which only heuristic solutions were unknown. We present an optimal polynomial time algorithm for combinational circuits under this model. Our algorithm can be generalized to solve the problem under any monotone clustering constraint.

AB - This paper addresses the problem of circuit clustering for delay minimization, subject to capacity constraints. We use the general delay model, for which only heuristic solutions were unknown. We present an optimal polynomial time algorithm for combinational circuits under this model. Our algorithm can be generalized to solve the problem under any monotone clustering constraint.

UR - https://dl.acm.org/doi/proceedings/10.1145/157485

UR - https://ieeexplore.ieee.org/document/1600239

UR - http://www.scopus.com/inward/record.url?scp=0027247165&partnerID=8YFLogxK

U2 - 10.1145/157485.164907

DO - 10.1145/157485.164907

M3 - Conference proceeding

AN - SCOPUS:0027247165

SN - 0897915771

SN - 9780897915779

T3 - ACM/IEEE Design Automation Conference - Proceedings

SP - 309

EP - 314

BT - 30th ACM/IEEE Design Automation Conference - Proceedings 1993

PB - Association for Computing Machinery (ACM)

T2 - 30th ACM/IEEE Design Automation Conference, DAC 1993

Y2 - 14 June 1993 through 18 June 1993

ER -

Optimal clustering for delay minimization

Abstract

Publication series

Conference

Scopus Subject Areas

Access to Document

Other files and links

Fingerprint

Cite this