CN114266216A

CN114266216A - A method to minimize chip layout line length

Info

Publication number: CN114266216A
Application number: CN202111002016.2A
Authority: CN
Inventors: 韩志杰; 付银赟; 李�杰; 杜晓玉
Original assignee: Henan University
Current assignee: Henan University
Priority date: 2021-08-30
Filing date: 2021-08-30
Publication date: 2022-04-01
Anticipated expiration: 2041-08-30
Also published as: CN114266216B

Abstract

The invention relates to the technical field of chip layout embedding, and discloses a method for minimizing the length of a chip layout line, which comprises the following steps: s1, the common structure of the chip is a linear array and a grid, and the interconnection network is represented by a graph G (V, E), wherein V is a vertex set and represents a communication node; e is an edge set which represents a physical link, nodes of the physical link are coded according to a certain rule by analyzing the structural characteristics of Cube-Connected Cycles (CCC), and mapping relations between the CCC and the vertex and the edges of the linear array and the grid structure are respectively found, so that an n-dimensional Cube connecting ring (CCC (k, n) can be embedded in the linear array and the grid with the minimum line length, wherein k is more than or equal to n); the length of the embedded wire is obtained in the later period, so that the communication delay in the network is effectively reduced, the utilization rate of the processor is improved, and important theoretical guidance and practical application value are provided for the design of the interconnection network and the quantitative analysis and evaluation of the network performance.

Description

Method for minimizing chip layout line length

Technical Field

The invention relates to the technical field of chip layout embedding, in particular to a method for minimizing the length of a chip layout line.

Background

With the development of science and technology, the requirement of processing mass data on the computing power of a processor is higher and higher. As an integrated circuit architecture, a Network-on-chip (Network-on-chip) can provide high performance interconnects between processors, with the core idea describing the communication between processors on a chip. The connection mode between communication nodes in the system is defined by a topological structure, and the performances of the network in terms of bandwidth, transmission delay, expandability and the like depend on the topological structure to a great extent. Due to the limitation of chip area, the wire length and layout become important factors affecting the network performance such as transmission delay and throughput. The solution of the place and route problem can be classified as a graph embedding problem.

Embedding is not only related to the ability of the structure to simulate other structures, but the length of the wire after embedding also affects the communication between different communication nodes. The existing network-on-chip structure mainly comprises a grid structure, a surrounding structure, a honeycomb structure and the like, the structure is simple, the realization is easy, and researchers can embed structures such as a hypercube structure, a local torsional cube structure and the like into a linear array and a grid to obtain the corresponding minimum line length so as to improve the performance of the network.

The hypercube network plays an important role in graph embedding, and has good symmetry, low diameter and strong connectivity. The CCC structure is a variation of the hypercube, where each node in the hypercube is replaced by a set of nodes, which form a ring, and k links in the hypercube connected to the same node are allocated to h nodes in the ring, aiming to reduce the number of links per node and improve the system performance. Thus, the CCC (h, k) contains h × 2^kEach node using an address (c, p) (0. ltoreq. c.ltoreq.2)^k1,0 ≦ p ≦ h-1), where c represents to which ring the node belongs and p represents the position of the node in the ring. Besides, the CCC structure has good symmetry and regularity and is widely applied. There are all the lengths of the turns in the CCC, which is close to a double-turn when n is odd and close to a double-turn when n is even. CCC is well suited to meet most of the requirements of the basic principles of network design, and therefore it becomes one of the popular topologies for parallel processing.

In conclusion, it is an important research direction to embed a network with good performance into a network-on-chip structure to improve the network performance, so that the minimization of the line length of the chip layout has important theoretical guidance and practical significance.

Disclosure of Invention

Technical scheme (I)

In order to achieve the purpose, the invention provides the following technical scheme: a method of minimizing chip layout line length, comprising the steps of:

s1, the common structure of the chip is a linear array and a grid, and the interconnection network is represented by a graph G (V, E), wherein V is a vertex set and represents a communication node; e is an edge set which represents a physical link, nodes of the physical link are coded according to a certain rule by analyzing the structural characteristics of Cube-Connected Cycles (CCC), the mapping relations between the CCC and the peaks and edges of the linear array and the grid structure are respectively found, and finally an n-dimensional Cube connecting ring (CCC (k, n), wherein k is more than or equal to n) can be embedded into the linear array and the grid by the minimum line length and comprises 2ⁿCircles, each circle containing k vertices, the method discusses the case where n-k;

s2, embedding n-dimensional cube communication circle CCC (n, n) into linear array P (n × 2)ⁿ) Let f: v (CCC (n, n)) → V (P (n × 2)ⁿ) Denotes an embedding, numbering CCC (n, n) periodically according to the recursive construction process of the hypercube, P (n × 2)ⁿ) The vertex in (1, 2, K, n x 2)ⁿLet f (v) be lex (v) for any v ∈ CCC (n, n);

s3, embedding the n-dimensional cube communication circle CCC (n, n) into the grid M (n, 2)ⁿ) Let p: v (CCC (n, n)) → V (M (n, 2)ⁿ) Represents an embedding, the first row in the grid being 0 to 2 from left to rightⁿ-1 is numbered, line i is from left to right according to (i-1)2ⁿ，(i-1)2ⁿ+1，K，i×2ⁿ-1 is numbered, where i ═ 0, 1, K, n-1, for any u ∈ CCC (n, n),

wherein u ═ u (u)_n-1L u₀J) (j is more than or equal to 0 and less than or equal to n), then

Preferably, the embedding in step S1 is specifically: mapping from one topology to another topology, an embedding of graph G to graph H is represented as a single ray of graph G to graph H, and the method discusses embedding CCC (n, n) into a linear array and a mesh, that is, finding the mapping relationship between CCC (n, n) and the vertex and edge of the linear array and the mesh respectively, so that the line length is the shortest for the linear array and the mesh after mapping.

Preferably, the linear array in step S2 is specifically: p (nx 2)ⁿ) Is represented by having n × 2ⁿA linear array of vertices, wherein vertices V (P (n × 2) of the linear arrayⁿ))＝{1,2,K,n×2ⁿEdge E of the linear array (P (n × 2)ⁿ))＝{(i,i+1)|i∈[1,n×2ⁿ-1]}。

Preferably, in step S2, the CCC (n, n) is numbered periodically according to the recursive construction process of the hypercube, specifically: hypercube (Q)_n) The recursive constitution of (c) is expressed as: q₁＝k₂,

Wherein K₂Is a second order complete graph, Q_nU-u of two vertexes_n-1L u₁u₀And v ═ v_n-1L v₁v₀The two-dimensional structure is numbered in a way of one dragon clockwise from (0,0) on the basis that the recursion construction mode of the CCC is consistent with that of the hypercube if and only if u and v have different coordinates, and the vertexes of the CCC are numbered in a three-dimensional and above two-dimensional recursion mode.

Preferably, in step S3, the grid structure specifically includes: an M x n grid M (M, n) is represented by an M x n matrix,

wherein V (M) ═ fα_ijI is more than or equal to 1 and less than or equal to m, and j is more than or equal to 1 and less than or equal to n }, when i is more than or equal to 1 and less than or equal to m and j is more than or equal to 1 and less than or equal to n-1, (alpha)_i,j,α_i,j+1) E (M), when k is more than or equal to 1 and less than or equal to m-1 and l is more than or equal to 1 and less than or equal to n, (alpha)_k,l,α_k+1,l)∈E(M)。

(II) advantageous effects

The invention provides a method for minimizing the length of a chip layout line, which has the following beneficial effects:

the invention discloses a method for minimizing the wire length of chip layout, which can effectively reduce the communication delay in the network and improve the utilization rate of a processor by solving the wire length after embedding in the later period, and has important theoretical guidance and practical application value for the design of interconnection networks and the quantitative analysis and evaluation of network performance.

Drawings

Fig. 1 is a schematic diagram of a periodic encoding mode of CCC (3,3) that needs to be embedded in a linear array when n is 3 in the present invention;

FIG. 2 shows a linear array P (3X 2) of the present invention³) The encoding method of (3) and the schematic connection diagram after embedding the CCC (3, 3);

fig. 3 is a schematic diagram of a periodic encoding manner of CCC (3,3) required to be embedded into a grid when n is 3 in the present invention;

FIG. 4 shows a grid M (n, 2) according to the present inventionⁿ) The coding method of (1).

Detailed Description

The technical solutions in the embodiments of the present invention will be clearly and completely described below with reference to the drawings in the embodiments of the present invention, and it is obvious that the described embodiments are only a part of the embodiments of the present invention, and not all of the embodiments. All other embodiments, which can be derived by a person skilled in the art from the embodiments given herein without making any creative effort, shall fall within the protection scope of the present invention.

As shown in fig. 1 to 4, the present invention provides a technical solution: a method of minimizing chip layout line length, comprising the steps of:

s1, the common structure of the chip is a linear array, a grid, the interconnection network is represented using graph G (V, E),where V is a set of vertices representing communication nodes; e is an edge set which represents a physical link, nodes of the physical link are coded according to a certain rule by analyzing the structural characteristics of Cube-Connected Cycles (CCC), the mapping relations between the CCC and the peaks and edges of the linear array and the grid structure are respectively found, and finally an n-dimensional Cube connecting ring (CCC (k, n), wherein k is more than or equal to n) can be embedded into the linear array and the grid by the minimum line length and comprises 2ⁿCircles, each circle containing k vertices, the method discusses the case where n-k;

the embedding is specifically as follows: mapping from one topology structure to another topology structure, wherein an embedding of a graph G to a graph H is represented as a single ray from the graph G to the graph H, the method discusses the embedding of CCC (n, n) into a linear array and a grid, namely, finding the mapping relation between the CCC (n, n) and the vertex and edge of the linear array and the grid respectively, so that the line length is the shortest for the linear array and the grid after mapping;

the linear array is specifically as follows: p (nx 2)ⁿ) Is represented by having n × 2ⁿA linear array of vertices, wherein vertices V (P (n × 2) of the linear arrayⁿ))＝{1,2,K,n×2ⁿEdge E of the linear array (P (n × 2)ⁿ))＝{(i,i+1)|i∈[1,n×2ⁿ-1]}；

Numbering CCC (n, n) periodically according to the recursion composition process of the hypercube, specifically: hypercube (Q)_n) The recursive constitution of (c) is expressed as: q₁＝k₂,

Wherein K₂Is a second order complete graph, Q_nU-u of two vertexes_n-1L u₁u₀And v ═v_n-1L v₁v₀The two-dimensional structure is numbered clockwise according to a dragon mode from (0,0) on the basis that the recursion forming mode of the CCC is consistent with that of a hypercube if and only if u and v have different coordinates, and the vertexes of the CCC are numbered in three-dimensional and above according to two-dimensional recursion;

The grid structure specifically is: an M x n grid M (M, n) is represented by an M x n matrix,

wherein v (m) ═ { α_ijI is more than or equal to 1 and less than or equal to m, and j is more than or equal to 1 and less than or equal to n }, when i is more than or equal to 1 and less than or equal to m and j is more than or equal to 1 and less than or equal to n-1, (alpha)_i,j,α_i,j+1) E (M), when k is more than or equal to 1 and less than or equal to m-1 and l is more than or equal to 1 and less than or equal to n, (alpha)_k,l,α_k+1,l)∈E(M)。

It is noted that, herein, relational terms such as first and second, and the like may be used solely to distinguish one entity or action from another entity or action without necessarily requiring or implying any actual such relationship or order between such entities or actions. Also, the terms "comprises," "comprising," or any other variation thereof, are intended to cover a non-exclusive inclusion, such that a process, method, article, or apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, article, or apparatus.

Although embodiments of the present invention have been shown and described, it will be appreciated by those skilled in the art that changes, modifications, substitutions and alterations can be made in these embodiments without departing from the principles and spirit of the invention, the scope of which is defined in the appended claims and their equivalents.

Claims

1. A method for minimizing the length of a chip layout line, comprising the following steps:

S1. The common structures of chips are linear arrays and grids. A graph G(V, E) is used to represent the interconnection network, where V is the vertex set, which represents the communication node; E is the edge set, which represents the physical link. By analyzing the cube According to the structural characteristics of the connected cycle (Cube-ConnectedCycles, CCC), the nodes are coded according to certain rules, and the mapping relationship between the CCC and the linear array and the vertices and edges of the grid structure is found respectively, so that in the linear array and grid, It can embed an n-dimensional cube-connected circle (CCC(k,n), k≥n) with the minimum line length, including 2 ⁿ circles, each circle contains k vertices, this method discusses the case of n=k;

S2. Embed the n-dimensional cubic connected circle CCC(n,n) into the linear array P(n× ²ⁿ ), let f: V(CCC(n,n))→V(P(n× ²ⁿ )) represent An embedding, which periodically numbers CCC(n,n) according to the recursive formation process of the hypercube, and numbers the vertices in P(n×2 ⁿ ) according to 1, 2, K, n×2 ⁿ as lex , for any v∈CCC(n,n), let f(v)=lex(v);

S3. Embed the n-dimensional cubic connected circle CCC(n,n) into the grid M(n, ²ⁿ ), let p: V(CCC(n,n))→V(M(n, ²ⁿ )) represent An embedding, the first row in the grid is numbered from 0 to 2 ⁿ -1 from left to right, and the i-th row is numbered from left to right as (i-1)2 ⁿ , (i-1)2 ⁿ +1, K , i×2 ⁿ -1 are numbered, where i=0, 1, K, n-1, for any u∈CCC(n,n),

where u=(u _n-1 Lu ₀ ,j)(0≤j≤n), then

2. A method for minimizing the length of a chip layout line according to claim 1, wherein the embedding in the step S1 is specifically: mapping from one topology to another topology, graph G to graph An embedding of H is represented as an injective from graph G to graph H. This method discusses the embedding of CCC(n,n) into linear arrays and grids, that is, finding CCC(n,n) and linear arrays and grids respectively. The vertices and edges are mapped so that the line length is the shortest for linear arrays and grids after mapping.

3 . The method for minimizing the length of chip layout lines according to claim 1 , wherein the linear array in step S2 is specifically: P(n×2 ⁿ ) means that there are n×2 ⁿ Linear array of vertices, where the vertices of the linear array V(P(n×2 ⁿ ))={1,2,K,n×2 ⁿ } and the edges of the linear array E(P(n×2 ⁿ ))={ (i,i+1)|i∈[1,n× ²ⁿ -1]}.

4. The method for minimizing the chip layout line length according to claim 1, wherein in the step S2, the CCC(n,n) is periodically numbered according to the recursive formation process of the hypercube , specifically: the recursive composition of the hypercube (Q _n ) is expressed as: Q ₁ =k ₂ ,

where K ₂ is a complete graph of second order, and the two vertices in Q _n u=u _n-1 Lu ₁ u ₀ and v=v _n-1 L v ₁ v ₀ are connected by an edge if and only if u , v has a different coordinate, the recursive composition of CCC is consistent with the hypercube, on this basis, the two-dimensional structure is numbered clockwise from (0,0) in a one-stop manner, and the three-dimensional and above are recursive to CCC according to two-dimensional Vertices are numbered.

5 . The method for minimizing chip layout line length according to claim 1 , wherein in the step S3 , the grid structure is specifically: an m×n grid M(m,n) 5 . Represented by an m×n matrix,

where V(M)={α _ij |1≤i≤m,and 1≤j≤n}, when 1≤i≤m,and 1≤j≤n-1, (α _i,j ,α _{i, j+1} )∈E(M), when 1≤k≤m-1, and 1≤l≤n, (α _k,l ,α _k+1,l )∈E(M).