Graph partitioning problem for multiple-chip design

Yao Ping Chen, Ting Chi Wang, D. F. Wong

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this paper, we introduce a new graph partitioning problem that stems from a multiple-chip design style in which there is a chip library of chips containing predesigned circuit components (e.g. adders, multipliers etc) which are frequently used. Given an arbitrary circuit data flow graph, we have to realize the circuit by appropriately choosing a set of chips from the chip library. In selecting chips from the chip library to realize a given circuit, both the number of chips used and the interconnection cost are to be minimized. Our new graph partitioning problem models this chip selection problem. We present an efficient solution to this problem.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE International Symposium on Circuits and Systems
PublisherPubl by IEEE
Pages1778-1781
Number of pages4
ISBN (Print)0780312813
StatePublished - Jan 1 1993
EventProceedings of the 1993 IEEE International Symposium on Circuits and Systems - Chicago, IL, USA
Duration: May 3 1993May 6 1993

Publication series

NameProceedings - IEEE International Symposium on Circuits and Systems
Volume3
ISSN (Print)0271-4310

Other

OtherProceedings of the 1993 IEEE International Symposium on Circuits and Systems
CityChicago, IL, USA
Period5/3/935/6/93

Fingerprint

Networks (circuits)
Data flow graphs
Adders
Costs

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Cite this

Chen, Y. P., Wang, T. C., & Wong, D. F. (1993). Graph partitioning problem for multiple-chip design. In Proceedings - IEEE International Symposium on Circuits and Systems (pp. 1778-1781). (Proceedings - IEEE International Symposium on Circuits and Systems; Vol. 3). Publ by IEEE.

Graph partitioning problem for multiple-chip design. / Chen, Yao Ping; Wang, Ting Chi; Wong, D. F.

Proceedings - IEEE International Symposium on Circuits and Systems. Publ by IEEE, 1993. p. 1778-1781 (Proceedings - IEEE International Symposium on Circuits and Systems; Vol. 3).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Chen, YP, Wang, TC & Wong, DF 1993, Graph partitioning problem for multiple-chip design. in Proceedings - IEEE International Symposium on Circuits and Systems. Proceedings - IEEE International Symposium on Circuits and Systems, vol. 3, Publ by IEEE, pp. 1778-1781, Proceedings of the 1993 IEEE International Symposium on Circuits and Systems, Chicago, IL, USA, 5/3/93.
Chen YP, Wang TC, Wong DF. Graph partitioning problem for multiple-chip design. In Proceedings - IEEE International Symposium on Circuits and Systems. Publ by IEEE. 1993. p. 1778-1781. (Proceedings - IEEE International Symposium on Circuits and Systems).
Chen, Yao Ping ; Wang, Ting Chi ; Wong, D. F. / Graph partitioning problem for multiple-chip design. Proceedings - IEEE International Symposium on Circuits and Systems. Publ by IEEE, 1993. pp. 1778-1781 (Proceedings - IEEE International Symposium on Circuits and Systems).
@inproceedings{35a7ab7619dd415eb8b8ce5f91850306,
title = "Graph partitioning problem for multiple-chip design",
abstract = "In this paper, we introduce a new graph partitioning problem that stems from a multiple-chip design style in which there is a chip library of chips containing predesigned circuit components (e.g. adders, multipliers etc) which are frequently used. Given an arbitrary circuit data flow graph, we have to realize the circuit by appropriately choosing a set of chips from the chip library. In selecting chips from the chip library to realize a given circuit, both the number of chips used and the interconnection cost are to be minimized. Our new graph partitioning problem models this chip selection problem. We present an efficient solution to this problem.",
author = "Chen, {Yao Ping} and Wang, {Ting Chi} and Wong, {D. F.}",
year = "1993",
month = "1",
day = "1",
language = "English (US)",
isbn = "0780312813",
series = "Proceedings - IEEE International Symposium on Circuits and Systems",
publisher = "Publ by IEEE",
pages = "1778--1781",
booktitle = "Proceedings - IEEE International Symposium on Circuits and Systems",

}

TY - GEN

T1 - Graph partitioning problem for multiple-chip design

AU - Chen, Yao Ping

AU - Wang, Ting Chi

AU - Wong, D. F.

PY - 1993/1/1

Y1 - 1993/1/1

N2 - In this paper, we introduce a new graph partitioning problem that stems from a multiple-chip design style in which there is a chip library of chips containing predesigned circuit components (e.g. adders, multipliers etc) which are frequently used. Given an arbitrary circuit data flow graph, we have to realize the circuit by appropriately choosing a set of chips from the chip library. In selecting chips from the chip library to realize a given circuit, both the number of chips used and the interconnection cost are to be minimized. Our new graph partitioning problem models this chip selection problem. We present an efficient solution to this problem.

AB - In this paper, we introduce a new graph partitioning problem that stems from a multiple-chip design style in which there is a chip library of chips containing predesigned circuit components (e.g. adders, multipliers etc) which are frequently used. Given an arbitrary circuit data flow graph, we have to realize the circuit by appropriately choosing a set of chips from the chip library. In selecting chips from the chip library to realize a given circuit, both the number of chips used and the interconnection cost are to be minimized. Our new graph partitioning problem models this chip selection problem. We present an efficient solution to this problem.

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

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

M3 - Conference contribution

AN - SCOPUS:0027266191

SN - 0780312813

T3 - Proceedings - IEEE International Symposium on Circuits and Systems

SP - 1778

EP - 1781

BT - Proceedings - IEEE International Symposium on Circuits and Systems

PB - Publ by IEEE

ER -