Synthesis of On-Chip Interconnection Structures: From Point-To-Point Links to Networks-on-Chip

Alessandro Pinto, Luca Carloni and Alberto L. Sangiovanni-Vincentelli

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2006-147
November 14, 2006

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-147.pdf

Packet-switched networks-on-chip (NOC) have been advocated as the solution to the challenge of organizing efficient and reliable communication structures among the components of a system-on-chip (SOC). A critical issue in designing a NOC is to determine its topology given the set of point-to-point communication requirements among these components. We present a novel approach to on-chip communication synthesis that is based on the iterative combination of two efficient computational steps: (1) an application of the k-Median algorithm to coarsely determine the global communication structure (which may turned out not be a network after all), and a (2) a variation of the shortest-path algorithm in order to finely tune the data flows on the communication channels. The application of our method to case studies taken from the literature shows that we can automatically synthesize optimal NOC topologies for multi-core on-chip processors and it offers new insights on why NOC are not necessarily a value proposition for some classes of application-specific SOCs.


BibTeX citation:

@techreport{Pinto:EECS-2006-147,
    Author = {Pinto, Alessandro and Carloni, Luca and Sangiovanni-Vincentelli, Alberto L.},
    Title = {Synthesis of On-Chip Interconnection Structures: From Point-To-Point Links to Networks-on-Chip},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2006},
    Month = {Nov},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-147.html},
    Number = {UCB/EECS-2006-147},
    Abstract = {Packet-switched networks-on-chip (NOC) have been advocated as the solution to
the challenge of organizing efficient and reliable communication structures
among the components of a system-on-chip (SOC). 
A critical issue in designing a NOC is to determine its topology given the set
of point-to-point communication requirements among these components. 
We present a novel approach to on-chip communication synthesis that is based on
the iterative combination of two efficient computational steps: 
(1) an application of the k-Median algorithm to coarsely determine the global 
communication structure (which may turned out not be a network after all), and a
(2) a variation of the shortest-path algorithm in order to finely tune the
data flows on the communication channels. 
The application of our method to case studies taken from the literature 
shows that we can automatically synthesize optimal NOC topologies for multi-core
on-chip processors and it offers new insights on why NOC are not
necessarily a value proposition for some classes of application-specific SOCs.}
}

EndNote citation:

%0 Report
%A Pinto, Alessandro
%A Carloni, Luca
%A Sangiovanni-Vincentelli, Alberto L.
%T Synthesis of On-Chip Interconnection Structures: From Point-To-Point Links to Networks-on-Chip
%I EECS Department, University of California, Berkeley
%D 2006
%8 November 14
%@ UCB/EECS-2006-147
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-147.html
%F Pinto:EECS-2006-147