KR101800320B1 - Network on chip system based on bus protocol, design method for the same and computer readable recording medium in which program of the design method is recorded - Google Patents

Abstract

According to an embodiment of the present invention, a bus protocol based network on chip system design method comprises the steps of: (a) designing an address network topology based on a bus protocol address for a network on chip system comprising a plurality of nodes and a router ; And (b) designing a data network topology dependent on a router of the address network topology, based on the address network topology.

Description

TECHNICAL FIELD [0001] The present invention relates to a network-on-chip system based on a bus protocol, a method for designing the same, and a computer readable recording medium on which a program for designing the same is recorded. OF THE DESIGN METHOD IS RECORDED}

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a bus-protocol-based network-on-chip system, a design method thereof, and a computer- The present invention relates to a bus-protocol-based network-on-chip system, a method of designing the same, and a computer-readable recording medium on which a program for designing the method is recorded.

With the increasing number of cores and IPs in the Multi-Processor SoC (MPSoC), on-chip interconnect structure design is becoming important. In the case of the conventional bus structure, scalability is limited due to the bottleneck as the number of connected components increases. In order to solve this problem, Network-on-Chip (NoC), which is advantageous for parallel processing and scalability, is attracting attention as a promising interconnection architecture technology.

However, due to the absence of the standardized NoC protocol and compatibility of legacy IP designed with existing bus protocol, the performance of NoC is not utilized properly. Especially, the NoC design focused on scalability requires optimization process to verify design and meet deadline for display IP which is very sensitive to delay time and application requiring real time processing.

The delay time at NoC is directly related to the number of hops (i.e., nodes) over which the data passes. Therefore, to minimize the delay time, a router allocation technique using a bipartite graph, a topology synthesis method using a path calculation based on a MCF (Multicastity Flow), an alternative path generation method using a link addition method, and a message scheduling And a method for improving the delay time. However, although these conventional techniques suggest a design method reflecting the characteristics of the path and the link, there is no proposal for a method for optimizing the transaction delay time of the bus protocol in the bus protocol compatible NoC.

Korean Patent No. 10-1077539 (Registered on October 21, 2011)

The present invention aims at minimizing the delay time increase problem by designing the data network topology and the address network topology separately in designing a bus-protocol compatible network-on-chip system.

According to an embodiment of the present invention, a bus protocol based network on chip system design method comprises the steps of: (a) designing an address network topology based on a bus protocol address for a network on chip system comprising a plurality of nodes and a router ; And (b) designing a data network topology dependent on a router of the address network topology, based on the address network topology.

A bus protocol based network-on-chip system according to another embodiment of the present invention includes a plurality of nodes and a plurality of routers, wherein the plurality of nodes and the plurality of routers are connected to an address network topology and a data network topology separately designed Wherein the data network topology is designed to be subordinate to a router of the address network topology based on a bus protocol address.

The present invention achieves minimization of the number of nodes in the address network topology by designing the address network topology and the data network topology for IP based on the bus protocol, and solves the path conflict problem in the data network topology where the data transmission amount is relatively large Thereby ensuring path diversity.

Accordingly, performance improvement (i.e., delay time reduction) of a network-on-chip system using an IP configured based on a bus protocol can be achieved, and design time can be shortened.

1 is a structural diagram of a network-on-chip system according to an embodiment of the present invention.
FIGS. 2 to 4 are schematic diagrams illustrating an address network topology designing step in a network-on-chip system design according to an exemplary embodiment of the present invention.
5 is a flowchart of a method of designing a network-on-chip system according to an embodiment of the present invention.
FIG. 6 is a flowchart illustrating an address network topology design step according to an embodiment of the present invention.
FIG. 7 is a flowchart illustrating a data network topology design step according to an embodiment of the present invention.

Hereinafter, embodiments of the present invention will be described in detail with reference to the accompanying drawings, which will be readily apparent to those skilled in the art. The present invention may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein. In order to clearly illustrate the present invention, parts not related to the description are omitted, and similar parts are denoted by like reference characters throughout the specification.

Throughout the specification, when a part is referred to as being "connected" to another part, it includes not only "directly connected" but also "electrically connected" with another part in between . Also, when an element is referred to as "comprising ", it means that it can include other elements as well, without departing from the other elements unless specifically stated otherwise.

A method for designing a network-on-chip system based on a bus protocol according to an embodiment of the present invention can be performed by a computer device, and can be executed by a processor executing a computer program for designing a network on-chip system stored in a memory. At this time, the computer device may be implemented by various devices or portable terminals. Here, the computer device includes, for example, a notebook computer, a desktop computer, a laptop computer, and the like, each of which is equipped with a web browser (WEB Browser) (International Mobile Telecommunication) -2000, Code Division Multiple Access (CDMA) -2000, W-CDMA (W-CDMA), Wireless Broadband Internet (Wibro), LTE (Long Term Evolution) A smart phone, a tablet PC, and the like.

Hereinafter, an embodiment of the present invention will be described in detail with reference to the drawings.

Referring to FIG. 1, an embodiment of the present invention includes a plurality of nodes 100 (that is, a core) and a router 200, and the address network topology and the data network topology may be separately designed. In this case, the address network topology is a network topology for transmitting IP address information and control information based on a bus protocol, and a data network topology is a network topology for transmitting substantial data other than address addresses and control information.

At this time, each of the nodes 100 has unique IP addresses (IP1 to IP8) based on a bus protocol and is organized in a hierarchical structure through the router 200 in the address network topology. In addition, data network communication is performed through connection with the input port 300 and the output port 400 of the data network. Each node 100 may be compatible with an address and data network topology via a network interface (NI).

As described above, according to the embodiment of the present invention, the address network and the data network are separated from each other and designed in a heterogeneous topology, thereby minimizing the delay time of the system operation and shortening the design time.

The heterogeneous topology design problem to provide this effect results in the problem of finding the TG () function of the following equation.

Here, G (V, E) is a communication trace graph value indicating communication between the nodes 100, V denotes a node 100, and e denotes a communication in which the node 100 transmits data do. U denotes a node 100 and an IP, R denotes a router 200 in the topology, F denotes a node 200 in the topology, AT denotes an address network topology graph, A connection between the router 100 and the router 200 or a connection between the router 200 and the router 200. [ DT denotes a data network topology graph value, U denotes a node 100 and IP, C denotes a cross-bar in the corresponding topology, F denotes a core, It represents the connection between crossbars or the connection between crossbars.

At this time, the TG () function must satisfy the following three conditions.

As a first condition, the TG () function should be configured to minimize the total number of nodes 100 since the delay time in the address network is mainly influenced by the number of nodes 100 that must go through operation. The equation for the total number of nodes 100 is as follows.

Here, BW (e _{i , j} ) denotes a bandwidth of communication transmitted from the i-node 100 to the j-th node 100, and CV (e _{i, j} ) denotes a maximum data amount that can be transmitted in one communication And hops (e _{i, j} ) denotes the number of nodes 100 going through the communication from the i-th node 100 to the j-th node 100.

As a second condition, the TG () function should design the data network topology in such a way as to minimize the number of overlapped communications on each link to minimize path conflicts in the data network.

As a third condition, since the address network has address information, the routing of the data network must be controlled in the address network. In this case, the routers 200 in the address network must be able to distribute and control the data network.

The network-on-chip system according to an embodiment of the present invention is designed based on the TG () function to satisfy the three conditions described above.

Hereinafter, a method of designing a network-on-chip system based on a bus protocol for satisfying the above three conditions will be described in detail with reference to FIG. 2 to FIG.

First, referring to FIG. 5, a method of designing a network-on-chip system according to an embodiment of the present invention includes two steps.

That is, after designing the address network topology based on the bus protocol address (S100), the process proceeds to step S200 of designing the data network topology based on the address network topology.

First, a method of designing an address network topology will be described with reference to FIGS. 2 to 4 and FIG.

The address network topology design step is performed to allocate a node 100 for each router 200 so that the total traffic between the plurality of nodes 100 in the network-on-chip system is minimized (e.g., less than a predetermined value) do.

At this time, the allocation of the node 100 to the router 200 can be performed through the topology technique based on the tree structure. The tree topology is a typical topology that can provide a scalable solution while optimizing the number of nodes 100. The tree topology is hierarchically structured. Since the number of hops increases every time communication is passed from the node 100 to the upper router 200 and from the upper router 200 to the uppermost router 200 one level at a time, Reducing the communication through the upper level is a very effective design method for reducing the total number of hops. The number of hops of the tree topology can be derived by the following equation.

The LHe _{i, j} is e _i, the level of the upper router 200, which has passed _j, LLe _{i, j} represents the level of the sub-router 200.

First, a plurality of nodes 100 are grouped so that the total communication amount is minimized (S110). At this time, the nodes 100 may be grouped based on a Communication Trace Graph (CTG) value indicating information about a communication route or a communication amount between the nodes 100. In particular, when the CTG is divided into a plurality of graphs and mapped to a tree topology, the communication divided into different subgraphs passes through the upper router 200, and thus the number of hops may increase. Accordingly, the nodes 100 can be grouped through an algorithm based on a balanced graph partitioning in order to minimize traffic.

Specifically, first, a plurality of node 100 structures of the type shown in FIG. 2 are assumed. In this case, the arrow indicates communication between nodes 100, for example, node 100 1 means transmitting data to node 100 (6). Then, grouping is performed as shown in FIG. At this time, a communication route (i.e., an external edge) generated to connect the groups due to the communication routes established between the respective nodes 100 is generated between the groups. For example, a group including nodes 100, 1, 2, and 6 has three outer edges for a group including nodes 100, 9, 10, At this time, the grouping is performed so that the outer edges are minimized, that is, the outer edges are smaller than the outer edges when randomly grouped. In the case of FIG. 3, grouping may be performed centering on node 100 6, since node 100 6 has as many communication routes as possible to other node 100. In addition, the grouping is performed so that the group including the node 100 having the largest amount of communication (i.e., the node 100 having the number of communication routes equal to or greater than the predetermined number) includes the smaller number of nodes 100 May be grouped. For example, the number of nodes 100 in a group to which a node 100 having a very large amount of traffic belongs may be one to two, and the number of nodes 100 in another group may be three or more.

Subsequently, each router 200 is assigned to each group, and the upper router 200 is assigned to the lower router 200 (S120).

In order to generate the tree topology that minimizes the total communication amount between the nodes 100, a graph that minimizes the expression (2) according to the number (n) of all the nodes 100 and the number (p) The router 200 can be allocated through division.

That is, since the uppermost router 200 does not have a link to the upper router 200 higher than the upper router 200, the lower router 200 connectable to the uppermost router 200 generates (p, 1 + p / n) . On the other hand, the lowest router 200 for the lower router 200 can be generated by (p-1, 1 + (p-1) / n) - graph partitioning. At this time, the number of maximum nodes 100 arranged in one lowest router 200 is expressed by Equation (4) below.

The graph partitioning is performed until the number of nodes 100 included in each lower router 200 becomes equal to or smaller than p-1. As a result, a tree structure in which nodes 100 of p-1 or less are connected to the leaf router 200 Based orthopedic topology can be constructed. Accordingly, the node 100, the lower router 200a, and the upper router 200b shown in FIG. 4 can be configured.

Then, optimization of the tree structure topology is performed (S130). Specifically, the router 200 to which the node 100 is not connected removes it. Alternatively, the integrable leaf routers 200 are integrated into one leaf router 200. For example, the combination of the router 200 and the node 100 having the number of the routers 200 equal to or greater than the number of the nodes 100 is integrated into one router 200 and a combination of the nodes 100 .

Thus, the address network topology design based on the bus protocol is completed through the above-described method.

Next, a data network topology design method will be described in detail with reference to FIG.

The data network topology is designed to be sequentially performed for each router 200 from one router 200 to the last router 200. At this time, a network topology based on the Venice topology is designed for each router 200. Data networks must ensure diversity of paths in order to minimize path conflicts. For this purpose, a data network design capable of distributed control is required. Therefore, a Benes topology based data network design should be accompanied.

First, a venue topology is created for a router 200 (S210). The Venice topology at this time is the Venice topology with n inputs and outputs.

Meanwhile, the generated Venice topology is divided into two sub-Venice topologies (S220). For example, a subnetwork topology with n / 2 inputs / outputs can be divided into two subnetwork topologies. (n = 2a, a is a natural number)

Then, the input port 300 of the data network and the output port 400 of the data network are mapped to the Venice topology (S230). That is, the number of matches between the input of two sub-Venice topologies and the data network input port 300 and the number of matches between the output of two sub-Venice topologies and the data network output port 400 can be derived. And performs matching on the cases.

Then, it is determined whether the cross-bar cost is minimized (S240). The crossbar switch refers to a connection structure that is organized for input and output connection on the network. Step S240 is performed to remove unnecessary crossbar switches and to derive the most cost effective mapping structure.

If it is not the minimum cost, the mapping combination between the input and output of the Venice topology and the input port 300 and the output port 400 of the data network is changed to the number of other cases (S250).

If the step S240 is reached, it is determined whether the sub-Venice topology is 2 x 2 (the number of inputs and outputs is two) (S260). If not, the sub-Venice topology is divided to perform sub- Steps S220 and S260 are repeated until the size becomes 2 x 2.

If the Venice topology is completed with respect to one router 200, it is determined whether there is another router 200 in which the Venice topology has not yet been generated (S270). If another router 200 remains, steps S210 and S260 are repeated for the other router 200 (S280).

In this way, for the entire router 200, by creating a stage for the data network input port 300 and the output port 400 when a Venice topology dependent on each router 200 is created, (S290).

One embodiment of the present invention may also be embodied in the form of a recording medium including instructions executable by a computer, such as program modules, being executed by a computer. Computer readable media can be any available media that can be accessed by a computer and includes both volatile and nonvolatile media, removable and non-removable media. The computer-readable medium may also include computer storage media. Computer storage media includes both volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer readable instructions, data structures, program modules or other data.

While the methods and systems of the present invention have been described in connection with specific embodiments, some or all of those elements or operations may be implemented using a computer system having a general purpose hardware architecture.

It will be understood by those skilled in the art that the foregoing description of the present invention is for illustrative purposes only and that those of ordinary skill in the art can readily understand that various changes and modifications may be made without departing from the spirit or essential characteristics of the present invention. will be. It is therefore to be understood that the above-described embodiments are illustrative in all aspects and not restrictive. For example, each component described as a single entity may be distributed and implemented, and components described as being distributed may also be implemented in a combined form.

The scope of the present invention is defined by the appended claims rather than the detailed description and all changes or modifications derived from the meaning and scope of the claims and their equivalents are to be construed as being included within the scope of the present invention do.

100: node 200: router
300: Data network input port
400: Data network output port

Claims (14)

A bus protocol based network on chip system design method performed by a computer device,
(a) designing an address network topology based on a bus protocol address, for a network-on-chip system comprising a plurality of nodes and a router; And
(b) designing a data network topology dependent on a router of the address network topology, based on the address network topology,
The step (a)
(a-1) grouping the plurality of nodes into a plurality of groups based on information on a communication route between the plurality of nodes; And
(a-2) assigning a router to each group so that the plurality of groups and a plurality of routers are mapped to each other. The method according to claim 1,
The step (a)
And allocating a node for each router such that the total amount of communication between the plurality of nodes in the network-on-chip system is less than a predetermined value. 3. The method of claim 2,
The step (a)
A network-on-chip system design method based on a bus protocol, wherein the plurality of nodes are allocated to each router in a tree structure-based topology scheme. 3. The method of claim 2,
The step (a)
A method for designing a network-on-chip system based on a bus protocol, designed through an algorithm based on balanced graph partitioning. delete The method according to claim 1,
The step (a-1)
Wherein the grouping is performed such that the number of communication routes generated to connect the plurality of groups due to the communication route established between the plurality of nodes is smaller than the number of communication routes when the number of communication routes is arbitrarily grouped. System design method. The method according to claim 1,
The step (a-1)
Wherein the group including the nodes having the number of communication routes equal to or greater than the predetermined number is grouped to include a smaller number of nodes than the other groups. The method according to claim 1,
The step (a)
(a-3) assigning an upper router to each router after the step (a-2);
(a-4) removing a router to which a node is not connected; And
(a-5) a step of creating a router and a node combination by integrating a combination of routers and nodes having a number of routers equal to or greater than the number of nodes, . The method according to claim 1,
The step (b)
Wherein the data network topology is designed sequentially for each router from one router to the last router. 10. The method of claim 9,
The step (b)
A network-on-chip system design method based on a bus protocol, wherein each router is designed with a network topology based on a Venice topology. 11. The method of claim 10,
The step (b)
(b-1) Designing a Venice topology with n inputs and outputs, and dividing into two sub-Venice topologies with n / 2 inputs and outputs; (n = 2a, a is a natural number) and
(b-2) mapping the input port of the data network and the output port of the data network to the Venice topology, and selecting a mapping when the least cost among the plurality of mapping cases is selected;
Based on the bus protocol. 12. The method of claim 11,
The step (b)
(b-3) repeating the steps (b-1) and (b-2) with respect to the sub-Venice topology after the step (b-2), until the number of inputs and outputs becomes two ; And
(b-4) generating a data network input port and an output port to which the plurality of nodes are connected. A computer program for executing a method for designing a network-on-a-chip system based on a bus protocol according to any one of claims 1 to 4 and 6 to 12. In a bus-protocol-based network-on-chip system,
A plurality of nodes and a plurality of routers,
Wherein the plurality of nodes and the plurality of routers are connected to a separately designed address network topology and a data network topology,
The address network topology includes:
A plurality of groups are grouped into a plurality of groups based on information on a communication route between the plurality of nodes and a router is assigned to each group so that the plurality of groups and the plurality of routers are mapped to each other,
Wherein the data network topology is designed to be subordinate to a router of the address network topology based on a bus protocol address.

Images