Partial connection-aware topology synthesis for on-chip cascaded crossbar network

Minje Jun, Deumji Woo, Eui Young Chung

Research output: Contribution to journalArticlepeer-review

17 Citations (Scopus)


The crossbar (also called bus matrix) solution is known as one of the most effective communication architectures for modern high-performance embedded systems. To make it even more effective, several topology synthesis methods have been proposed. They mostly generate a crossbar network in a cascaded fashion under the assumption that each crossbar switch is fully connected (i.e., each input has a connection to every output). This assumption often limits optimizing the area efficiency and/or performance of the network due to the unnecessary connections inside the crossbar switches. Some existing methods marginally improve their synthesis results by eliminating the unnecessary connections after the synthesis step. Such postprocessing approaches make sense since considering partially connected crossbar switches earlier in the synthesis flow can greatly increase the optimal topology search space, thereby increasing the runtime. However, the result from these postprocessing techniques is typically far inferior to that from the exhaustive search. In this work, we tackle such limitations of previous methods by introducing a heuristic method based on iterative switch merging. To the best of authors' knowledge, none of previous methods consider the partial connection of crossbar switches in the middle of the topology synthesis. Our experimental results prove the effectiveness of the proposed method by showing up to 30.35 percent of area saving against those methods that consider the partial connection only in a postprocess. The results also show the superiority of the proposed method against the existing topology synthesis methods, showing up to 49.09 percent area saving and synthesis time reduction by several orders of magnitude.

Original languageEnglish
Article number5601703
Pages (from-to)73-86
Number of pages14
JournalIEEE Transactions on Computers
Issue number1
Publication statusPublished - 2012

Bibliographical note

Funding Information:
This work was supported in part by Technology Innovation Program (Industrial Strategic technology development program, KI002168, Development of Configurable Device & SW Environment) funded by the Ministry of Knowledge Economy (MKE, Korea), by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (2010-0025423), and by the IDEC (IC Design Education Center). D. Woo was with the School of Electrical and Electronic Engineering, Yonsei University, 134 Sinchon-dong, Seodaemun-gu, Seoul 120-749, Korea.

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics


Dive into the research topics of 'Partial connection-aware topology synthesis for on-chip cascaded crossbar network'. Together they form a unique fingerprint.

Cite this