# Patent

## Title
Heterogeneous channel capacities in an interconnect

## Abstract

Systems and methods involving construction of a system interconnect in which different channels have different widths in numbers of bits. Example processes to construct such a heterogeneous channel NoC interconnect are disclosed herein, wherein the channel width may be determined based upon the provided specification of bandwidth and latency between various components of the system.

## Background
BACKGROUND
1. Technical Field
Methods and example embodiments described herein are generally directed to interconnect architecture, and more specifically, to network on chip system interconnect architecture.
2. Related Art
The number of components on a chip is rapidly growing due to increasing levels of integration, system complexity and shrinking transistor geometry. Complex System-on-Chips (SoCs) may involve a variety of components e.g., processor cores, DSPs, hardware accelerators, memory and I/O, while Chip Multi-Processors (CMPs) may involve a large number of homogenous processor cores, memory and I/O subsystems. In both systems the on-chip interconnect plays a key role in providing high-performance communication between the various components. Due to scalability limitations of traditional buses and crossbar based interconnects, Network-on-Chip (NoC) has emerged as a paradigm to interconnect a large number of components on the chip.
NoC is a global shared communication infrastructure made up of several routing nodes interconnected with each other using point-to-point physical links. Messages are injected by the source component and are routed from the source components to the destination over multiple intermediate nodes and physical links. The destination component then ejects the message and provides it to the destination component. For the remainder of the document, terms ‘components’, ‘blocks’ hosts' or ‘cores’ will be used interchangeably to refer to the various system components which are interconnected using a NoC. Terms ‘routers’ and ‘nodes’ will also be used interchangeably. Without loss of generalization, the system with multiple interconnected components will itself be referred to as ‘multi-core system’.
There are several possible topologies in which the routers can connect to one another to create the system network. Bi-directional rings (as shown in FIG. 1(a)) and 2-D mesh (as shown in FIG. 1(b)) are examples of topologies in the related art.
Packets are message transport units for intercommunication between various components. Routing involves identifying a path which is a set of routers and physical links of the network over which packets are sent from a source to a destination. Components are connected to one or multiple ports of one or multiple routers; with each such port having a unique ID. Packets carry the destination's router and port ID for use by the intermediate routers to route the packet to the destination component.
Examples of routing techniques include deterministic routing, which involves choosing the same path from A to B for every packet. This form of routing is oblivious of the state of the network and does not load balance across path diversities which might exist in the underlying network. However, such deterministic routing may be simple to implement in hardware, maintains packet ordering and may be easy to make free of network level deadlocks. Shortest path routing minimizes the latency as it reduces the number of hops from the source to destination. For this reason, the shortest path is also the lowest power path for communication between the two components. Dimension-order routing is a form of deterministic shortest path routing in 2D mesh networks.
FIG. 2 illustrates an example of XY routing in a two dimensional mesh. More specifically, FIG. 2 illustrates XY routing from node ‘34’ to node ‘00’. In the example of FIG. 2, each component is connected to only one port of one router. A packet is first routed in the X dimension till the packet reaches node ‘04’ where the x dimension is same as destination. The packet is next routed in the Y dimension until the packet reaches the destination node.
Source routing and routing using tables are other routing options used in NoC. Adaptive routing can dynamically change the path taken between two points on the network based on the state of the network. This form of routing may be complex to analyze and implement and is therefore rarely used in practice.
A NoC may contain multiple physical networks. Over each physical network, there may exist multiple virtual networks, wherein different message types are transmitted over different virtual networks. In this case, at each physical link or channel, there are multiple virtual channels; each virtual channel may have dedicated buffers at both end points. In any given clock cycle, only one virtual channel can transmit data on the physical channel.
NoC interconnects often employ wormhole routing, wherein, a large message or packet is broken into small pieces known as flits (also referred to as flow control digits). The first flit is the header flit which holds information about this packet's route and key message level info along with payload data and sets up the routing behavior for all subsequent flits associated with the message. Zero or more body flits follows the head flit, containing the remaining payload of data. The final flit is tail flit which in addition to containing the last payload also performs some bookkeeping to close the connection for the message. In wormhole flow control, virtual channels are often implemented.
The physical channels are time sliced into a number of independent logical channels called virtual channels (VCs). VCs provide multiple independent paths to route packets, however they are time-multiplexed on the physical channels. A virtual channel holds the state needed to coordinate the handling of the flits of a packet over a channel. At a minimum, this state identifies the output channel of the current node for the next hop of the route and the state of the virtual channel (idle, waiting for resources, or active). The virtual channel may also include pointers to the flits of the packet that are buffered on the current node and the number of flit buffers available on the next node.
The term “wormhole” plays on the way messages are transmitted over the channels: the output port at the next router can be so short that received data can be translated in the head flit before the full message arrives. This allows the router to quickly set up the route upon arrival of the head flit and then opt out from the rest of the conversation. Since a message is transmitted flit by flit, the message may occupy several flit buffers along its path at different routers, creating a worm-like image.
Based upon the traffic between various end points, and the routes and physical networks that are used for various messages, different physical channels of the NoC interconnect may experience different levels of load and congestion. The capacity of various physical channels of a NoC interconnect is determined by the width of the channel (number of physical wires) and the clock frequency at which it is operating. Various channels of the NoC may operate at different clock frequencies. However, all channels are equal in width or number of physical wires. This width can be determined based on the most loaded channel and the clock frequency of various channels.
SUMMARY
Aspects of the example implementations may include a method, involving determining and/or adjusting a width for each of a plurality of channels in a network on chip (NoC) based on at least one performance objective for the each of the plurality of channels or a maximum data flow of the each of the plurality of channels, such that at least one of the plurality of channels has a different width than at least another one of the plurality of channels.
Additional aspects of the example implementations may further include a computer readable storage medium storing instructions for executing a process, involving determining and/or adjusting a width for each of a plurality of channels in a network on chip (NoC) based on at least one performance objective for the each of the plurality of channels or a maximum data flow of the each of the plurality of channels, such that at least one of the plurality of channels has a different width than at least another one of the plurality of channels.
Additional aspects of the example implementations may further include a system, which includes a width adjustment module configured to determine and/or adjust a width for each of a plurality of channels in a network on chip (NoC) based on at least one performance objective for the each of the plurality of channels or a maximum data flow of the each of the plurality of channels, such that at least one of the plurality of channels has a different width than at least another one of the plurality of channels.



BRIEF DESCRIPTION OF THE DRAWINGS
FIGS. 1(a) and 1(b) illustrate examples of Bidirectional ring and 2D Mesh NoC Topologies.
FIG. 2 illustrates an example of XY routing in a related art two dimensional mesh.
FIGS. 3(a) and 3(b) illustrates an example of a ring and 2D mesh NoC with asymmetric channel widths/sizes as indicated by the link widths, in accordance with an example implementation.
FIG. 4 illustrates an example of router architecture with asymmetric input and output channel widths, in accordance with an example implementation.
FIG. 5 illustrates an example of a communication sequence from a source node to the destination node with various combinations of channel widths along the path, in accordance with an example implementation.
FIG. 6 illustrates an example of the flow graph constructed to determine the maximum traffic over a channel which will determine the width of the channel, in accordance with an example implementation.
FIG. 7 illustrates a flowchart for determining channel widths in a heterogeneous NoC, in accordance with an example implementation.
FIG. 8 illustrates an example implementation of a NoC with physical and virtual channels, in accordance with an example implementation.
FIG. 9 illustrates a computer/server block diagram upon which the example implementations described herein may be implemented.



DETAILED DESCRIPTION
Complex traffic profiles in a SoC can create uneven load on various channels of the interconnect that connects various components of the SoC. Example embodiments described herein are based on the concept of constructing interconnect with heterogeneous channel capacities (number of wires) for a specified inter-block communication pattern in the system. An example process of the automatic construction of the NoC interconnect is also disclosed.
The load on various channels of NoC interconnect depends upon the rate at which various components are sending messages, the topology of the NoC interconnect, how various components are connected to the NoC nodes, and the path various messages are taking in the NoC. Channels may be uniformly sized in number of wires across the entire NoC to avoid the reformatting of messages within the NoC nodes as they travel over various channels. In such cases case, to avoid congestion, all channels may be sized based on the most loaded channel in the NoC. Load balancing of channels can be performed by routing messages over less loaded paths, which reduces the non-uniform loading of various channels and therefore the maximum load. However, there is limited flexibility in choosing different paths. Route paths can have a variety of restrictions such as using shortest path, using minimal turn, or lack of path diversity between various components. Therefore, in most SoCs, channels remain non-uniformly loaded, and using the highest channel load to determine the global NoC channel width leads to increased area, power and interconnect cost.
Unlike related art systems, NoC interconnects that use homogeneous channel width in number of wires, example implementations disclosed herein are directed to an interconnect design in which various channels may have a different number of wires, leading to non-uniform channel width and/or bandwidth capacities. The channel bandwidth requirement can be determined by computing the maximum data bandwidth that is expected on the channel, based on the traffic profile. If some channels have different width based on their bandwidth requirements, various nodes within the NoC may have to reformat messages as messages traverse between two channels of different widths. A single message flit may need to be sub-divided into multiple smaller flits, or multiple message flits may need to be merged together to form a larger message flit. For example, a single 128-bit flit coming on a 128-bit input channel may have to be broken into two flits of 64-bit each as it goes from a 128-bit channel to 64-bit channel.
An example of such a heterogeneous channel NoC interconnect is shown in FIGS. 3(a) and 3(b). FIG. 3(a) shows a 6-node ring interconnect with heterogeneous channel widths, in accordance with an example implementation. The four processor components, proc1, proc2, proc3, and proc4 are connected to the two memory components mem1 and mem2. The channels in this interconnect are of two widths, 64-bit (1 unit) and 128-bit (2 units). Routers connecting components A, B, C and F to the NoC have various input and output channels of different width as shown and they may need to reformat the messages as they travel across channels of different width. FIG. 3(b) shows a 9-node mesh interconnect organized in a 3×3 topology, in accordance with an example implementation. Here 6 processors proc1, . . . proc6 are connected to 3 memory components mem1, . . . mem3, and the routers connected to components A, B, C, D, E, and F have channels of unequal widths.
FIG. 4 shows the architecture of a 5-port router that has various input and output channels of different width, in accordance with an example implementation. In the example of FIG. 4, the channel width and the corresponding buffer widths are indicated by the width of the link, which varies from 64-bit (1 unit) to 256-bit (4 units). The flit reformatting is performed based upon the input and output channel widths. For example, when a 128-bit (2 units) flit arrives on a 128-bit channel and is written into the 128-bit buffer, the flit can be transmitted to either a 64-bit, 128-bit or 256-bit output channel, as illustrated in the diagram. The router node reformats the message accordingly by dividing a large flit into multiple smaller flits, or combining multiple flits of a single message into a single larger flit based upon the input and output channel widths. In the example of FIG. 4, reformatting is performed within a single message, and not across multiple messages. However, reformatting of multiple messages coming from same source and going to the same destination may also be performed. Depending upon the message arrival pattern, such opportunities may become rare in a large network.
In such a NoC with heterogeneous channel widths, the message reformatting that occurs within the NoC nodes is kept transparent from the end components. Thus, if the destination host is expecting messages of 128-bit flits, then the NoC is maintained such that after several segmentation and reassembly operations along the route, the message is delivered as 128-bit flits to the final destination. Therefore, the channels are sized so that all end-to-end channel widths from end host perspective remain consistent to the original homogeneous interconnect. For example, between a pair of 128-bit transmitting and receiving hosts, the interconnect may reduce the channel to 64-bit or smaller along the route, and increases back to 128-bit at the egress transmit channel of the router at the final destination host.
A few examples of such consistent channel width conversion are shown in FIG. 5, in accordance with an example implementation. Path 500 shows a path with the homogeneous 128-bit (2 units) channel widths between source and destination components. Path 501 shows the path between the hosts wherein the channel width is kept the same at the end hosts. However along the path, the channel width is first increased from 2 units at the source to 4 units, then to 8 units and then reduced back to 4 units and then to 2 units at the destination. In path 502, the channel width along the paths are increased from 2 units at the source to 8 units, then reduced to 1 unit, then increased to 4 units and then reduced back to 2 units at the destination. While the channel widths are heterogeneous within the NoC, the end-to-end channel width between all communicating host pairs may need to remain consistent.
The end-to-end channel width consistency is maintained even when source and destination hosts have different transmit and receive channel widths. For example when a 64-bit transmit channel host sends message to 128-bit receive channel hosts, the message upon delivery is made to be 128-bit flits, even if the message is up- and down-converted along the route.
The width of various channels in the NoC may be determined not only by the bandwidth requirements of all messages traversing over the channel, but also by the latency requirements. Making a channel wider, thus allocating higher channel bandwidth, may not necessarily increase the throughput if channels are already wider than average data rate needed. However, making the channel wider may reduce the latency under a non-uniform traffic distribution. The minimum channel width may thereby be determined as at least equal to the data throughput of all flows that go over the channel.
To determine the minimum width of a channel, all source and destination pairs are listed whose messages are transmitted over the channel. The user may provide the data rates of all these messages to allow the system to size the channel by adding the data rates of all messages. If the data rates of the messages are not provided, and the data transmit and receive rates of all components are known, alternate implementations may be utilized to determine the minimum channel width (or maximum sustained data rate) in a complex system with complex traffic profile.
For example, consider four processors and two memories and shared memory computer environment, in which any processor can talk to any memory. Assume that the peak transmit rate of the processors is 64-bit/second and peak receive rate of the memories is 64-bit/second. In such an environment, a processor can send some fraction of the data to one memory and the remaining fraction to the other, or can entirely communicate with just one memory. Depending upon the communication pattern, a processor can transmit at a 64-bit/second rate.
Therefore, with four processors a NoC with 256-bit/sec peak channel throughput may be designed. However, in this example, the aggregate rate of communication can never exceed 128-bit/second, which is the aggregate receive capacity of the two memories. The load on various channels also depends upon the interconnect topology, routes, and the connection locations of the various components.
Assume the four processors and two memories are connected using a bi-directional ring, as shown in FIG. 3(a). Between the two routes available, assume the shortest route is always selected, breaking ties by choosing the clockwise route. Regardless of which processor talks to which combination of memories in which fraction in this example, the peak load on the channels between routers connected to components C and D, D and E, E and F will never exceed 64-bit/second (1 unit). Furthermore, there will be a communication pattern for which the channels between components F and A, A and B, B and C will experience load of 128-bit/second (2 units).
In a more complex system and communication pattern, it may become challenging to determine the peak data rate on various channels, for the minimum needed channel width may be computed. Described below is process which can be used to determine the peak data rate at any given channel of the NoC interconnect, in accordance with an example implementation.
All pairs of components which send messages over a channel are used to construct a directed flow or bipartite graph which involves of all source components on the left hand side and the destination components on the right hand side. Then, the source and destination components are connected with directional edges. The capacity of an edge is the maximum rate at which the source components can send data to the destination components along this route. The capacity cannot exceed the peak transmit rate of the source and peak receive rate of the destination. Subsequently two more components are added to the graph, one at the far left as S and one at the far right as D in the graph. The leftmost component is then connected to the list of source components on the left with directed edges, one for each source components. The capacity of these edges is the peak transmit rate of the source components. The list of destination components on the right are then connected to the rightmost edge with directed edges, one from each destination component. The capacity of these edges is the peak receive rate of the destination components. FIG. 6 shows such a graph for some channel, assuming that 5 sources transmit messages to 4 destinations as shown by the middle edges over the channel.
Once such a directed flow graph is constructed for the given channel, the flow diagram of FIG. 7 can be utilized to determine the width of each channel. At 700, the channels of the NoC are placed in a queue. At 701, a check is conducted to see if the queue is empty. If the queue is empty then the procedure ends. If the queue is not empty, the procedure proceeds to 702 to pick and remove the channel at the head of the queue. Based on the selected channel, the maximum flow is computed from component S of the bi-partite graph to component D at 703. Graph algorithms in the related art may be utilized for computing the maximum flow in directed flow graphs. The maximum data load on the channel will not exceed the maximum flow. The channel can then be sized accordingly to ensure that the channel has enough bandwidth regardless of the traffic distribution. The channel width may be further increased to reduce latency, or the channel width reduced, e.g., to save cost, depending on the specified performance objective. This procedure is then repeated for every channel in the NoC.
In an interconnect that contains both virtual and physical channels, different virtual channels can be sized differently; while the physical channel width will be same as the width of the widest virtual channel. An example implementation of such as system is shown in FIG. 8, In the example of FIG. 8, multiple virtual channels at the input are contending for the output physical channel via router arbitration logic. Based upon the maximum flow graph analysis, the maximum bandwidth requirement of the various virtual channels can be obtained. However, the virtual channels may not be sized at this value if all of the virtual channels time shares with the physical channel, (e.g. a system where any single virtual channel will be sending data only for a fraction of time).
For example, if there are two virtual channels on a physical channel, and each virtual channel needs a minimum of 64 bits/cycle of bandwidth, then the virtual channels cannot be sized at 64-bits each. If they are sized as such, then each of the virtual channels will receive only 32-bits/cycle of bandwidth assuming that they share the physical channel equally. To ensure that both virtual channels at least 64-bit/cycle of data bandwidth, they need to be sized at 128-bits each (assuming that they share the physical channel equally).
If there are large numbers of virtual channels sharing a physical channel, and each virtual channel has a different minimum bandwidth requirement, then it is non-trivial to size the virtual channels so that all of them meet their bandwidth requirements. In an example implementation, the problem is mapped to standard linear optimization or linear programming problem. We can then utilize a standard linear programming solution to derive the virtual channel widths in such scenarios.
For example, assume that n virtual channels (VC1, VC2, . . . VCn) are sharing a physical channel, and their minimum bandwidth requirement is (B1, B2, . . . Bn). Thus, the total bandwidth requirement at the physical channel is ΣBi for i=1 to n. Let si indicate the width of VCi. Clearly for all i=1 to n, si>B. The width of the physical channel is max(for i=1 to n, si). Assuming that VCi wins a fi fraction of times during arbitration, the bandwidth received by VCi is fi×si, which must be ≧Bi, the required bandwidth. Since all VCs share the physical channel Σfi≦1. Thus the following sets of linear constraints must be satisfied at all times:
si≧Bi for all i=1 to n.
fi×si≧Bi for all i=1 to n.
0≦fi≦1 for all i=1 to n.
Σfi≦1 for i=1 to n.
The buffer cost of the channel with virtual channel widths si is Σsi. If the design goal is to minimize the buffer cost, then the objective function is to minimize Σsi. If the design goal is to minimize the number of wires, then the objective function max(for i=1 to n, si) can be minimized, which is the physical channel width. If the goals are different, then alternative objective functions may be constructed. At this point, a standard linear programming algorithm can be used to solve the problem and get the values of si, the width of various virtual channels that meets the constraints and minimizes/maximizes the objective function.
An example implementation therefore includes mapping the virtual and physical channel sizing problem to the standard linear programming optimization method, by listing of constraint inequalities, and constructing an objective function based upon the optimization goal.
FIG. 9 illustrates an example computer system 900 on which example embodiments may be implemented. The computer system 900 includes a server 905 which may involve an I/O unit 935, storage 960, and a processor 910 operable to execute one or more units as known to one of skill in the art. The term “computer-readable medium” as used herein refers to any medium that participates in providing instructions to processor 910 for execution, which may come in the form of computer-readable storage mediums, such as, but not limited to optical disks, magnetic disks, read-only memories, random access memories, solid state devices and drives, or any other types of tangible media suitable for storing electronic information, or computer-readable signal mediums, which can include transitory media such as carrier waves. The I/O unit processes input from user interfaces 940 and operator interfaces 945 which may utilize input devices such as a keyboard, mouse, touch device, or verbal command.
The server 905 may also be connected to an external storage 950, which can contain removable storage such as a portable hard drive, optical media (CD or DVD), disk media or any other medium from which a computer can read executable code. The server may also be connected an output device 955, such as a display to output data and other information to a user, as well as request additional information from a user. The connections from the server 905 to the user interface 940, the operator interface 945, the external storage 950, and the output device 955 may via wireless protocols, such as the 802.11 standards, Bluetooth® or cellular protocols, or via physical transmission media, such as cables or fiber optics. The output device 955 may therefore further act as an input device for interacting with a user.
The processor 910 may execute one or more modules. The width adjustment module 911 is configured to determine and/or adjust a width for each of a plurality of channels in a network on chip (NoC) based on at least one performance objective for the each of the plurality of channels or a maximum flow of the each of the plurality of channels, such that at least one of the plurality of channels has a different width than at least another one of the plurality of channels. The width adjustment module 911 may be further configured to determine the maximum flow of the each of the plurality of channels from an application of a maximum flow algorithm on a graph of data traffic of the plurality of channels. The width adjustment module 911 may be further configured to determine the width of each of the plurality of channels by applying linear programming to determine the width that meet the at least one performance objective while minimizing at least one specified cost function, and to apply linear programming by constructing a list of constraints for meeting virtual and physical channel performance requirements. The width adjustment module may also be configured to determine at least one objective function for each of the at least one performance objective based on the list of constraints.
The message reformatter module 912 may be configured to construct a message reformatter between connected ones of the plurality of channels having differing widths, and to adjust flits of a message between the connected ones of the plurality of channels having differing widths. The message reformatter module 912 may also be configured to construct the message reformatters such that all source and destination end host pairs of the NoC maintain end-to-end message size and message format consistency.
Furthermore, some portions of the detailed description are presented in terms of algorithms and symbolic representations of operations within a computer. These algorithmic descriptions and symbolic representations are the means used by those skilled in the data processing arts to most effectively convey the essence of their innovations to others skilled in the art. An algorithm is a series of defined steps leading to a desired end state or result. In the example embodiments, the steps carried out require physical manipulations of tangible quantities for achieving a tangible result.
Moreover, other implementations of the example embodiments will be apparent to those skilled in the art from consideration of the specification and practice of the example embodiments disclosed herein. Various aspects and/or components of the described example embodiments may be used singly or in any combination. It is intended that the specification and examples be considered as examples, with a true scope and spirit of the embodiments being indicated by the following claims.

## Claims

1. A method, comprising:
determining a width for each of a plurality of virtual channels in a network on chip (NoC) comprising a plurality of hosts interconnected by a plurality of physical wires to form the plurality of virtual channels, based on at least one NoC performance objective for the each of the plurality of virtual channels or a maximum data flow of the each of the plurality of virtual channels, such that at least one of the plurality of virtual channels has a different width than at least another one of the plurality of virtual channels; and
providing a message reformatter between connected ones of the plurality of virtual channels, wherein the provided message reformatter is configured to adjust flits of one or more messages between the connected ones of the plurality of virtual channels;
wherein the determining the width of each of the plurality of virtual channels based on the at least one NoC performance objective further comprises applying linear programming to determine the width that meets the at least one NoC performance objective, wherein the applying linear programming further comprises constructing a list of constraints for meeting virtual and physical channel performance requirements, and wherein at least one objective function is derived for each of the at least one NoC performance objective based on the list of constraints.

2. The method of claim 1, wherein the provided message reformatter is configured to adjust the one or more messages such that all source and destination end host pairs of the NoC maintain end-to-end message size and message format consistency.

3. The method of claim 1, wherein the maximum data flow of the each of the plurality of virtual channels is determined from an application of a maximum flow algorithm on a graph of data traffic of the plurality of virtual channels.

4. The method of claim 1, wherein the applying linear programming is further based on minimizing at least one specified cost function.

5. The method of claim 1, wherein the at least NoC one performance objective comprises a latency requirement, and wherein shortest path routing is applied to the plurality of virtual channels to meet the latency requirement.

6. A non-transitory computer readable medium storing instructions for executing a process, comprising:
determining a width for each of a plurality of virtual channels in a network on chip (NoC) comprising a plurality of hosts interconnected by a plurality of physical wires to form the plurality of virtual channels, based on at least one NoC performance objective for the each of the plurality of virtual channels or a maximum data flow of the each of the plurality of virtual channels, such that at least one of the plurality of virtual channels has a different width than at least another one of the plurality of virtual channels, and
providing a message reformatter between connected ones of the plurality of virtual channels, wherein the provided message reformatter is configured to adjust flits of one or more messages between the connected ones of the plurality of virtual channels;
wherein the determining the width of each of the plurality of virtual channels based on the at least one NoC performance objective further comprises applying linear programming to determine the width that meets the at least one NoC performance objective, wherein the applying linear programming further comprises constructing a list of constraints for meeting virtual and physical channel performance requirements, and wherein at least one objective function is derived for each of the at least one NoC performance objective based on the list of constraints.

7. The non-transitory computer readable medium of claim 6, wherein the provided message reformatter is configured to adjust the one or more messages such that all source and destination end host pairs of the NoC maintain end-to-end message size and message format consistency.

8. The non-transitory computer readable medium of claim 6, wherein the maximum data flow of the each of the plurality of virtual channels is determined from an application of a maximum flow algorithm on a graph of data traffic of the plurality of virtual channels.

9. The non-transitory computer readable medium of claim 6, wherein the applying linear programming is based on minimizing at least one specified cost function.

10. The non-transitory computer readable medium of claim 6, wherein the at least one NoC performance objective comprises a latency requirement, and wherein the instructions further comprise applying shortest path routing to the plurality of virtual channels to meet the latency requirement.

11. A system, comprising:
a width adjustment module configured to determine a width for each of a plurality of virtual channels in a network on chip (NoC) comprising a plurality of hosts interconnected by a plurality of physical wires to form the plurality of virtual channels, based on at least one NoC performance objective for the each of the plurality of virtual channels or a maximum data flow of the each of the plurality of virtual channels, such that at least one of the plurality of virtual channels has a different width than at least another one of the plurality of virtual channels; and
a message reformatter module configured to provide a message reformatter between connected ones of the plurality of virtual channels, wherein the provided message reformatter adjusts flits of one or more messages between the connected ones of the plurality of virtual channels;
wherein the width adjustment module is configured to determine the width of each of the plurality of virtual channels based on the at least one NoC performance objective by applying linear programming to determine the width that meets the at least one NoC performance objective, wherein the width adjustment module is configured to apply linear programming by constructing a list of constraints for meeting virtual and physical channel performance requirements, and wherein at least one objective function is derived for each of the at least one NoC performance objective based on the list of constraints.

12. The system of claim 11, wherein the provided message reformatter is configured to adjust one or more messages such that all source and destination end host pairs of the NoC maintain end-to-end message size and message format consistency.

13. The system of claim 11, wherein the maximum flow of the each of the plurality of virtual channels is determined by the width adjustment module from an application of a maximum flow algorithm on a graph of data traffic of the plurality of virtual channels.

14. The system of claim 11, wherein the width adjustment module is configured to apply linear programming based on minimizing at least one specified cost function.