ES2395955B2 - Adaptive routing method in hierarchical networks - Google Patents

Abstract

Method of routing packets in a hierarchical direct network consisting of a plurality of routers, each with local type ports and global type ports; each port comprises a plurality of virtual channels; said routers form groups, where the different routers of the same group are interconnected by means of a connected topology using local type links joining pairs of local type ports, and the different groups are interconnected by a related topology using global type links joining pairs of Global type ports. The method is configured to employ jumps over said links according to minimum and non-minimum routes; jumps that involve non-minimal routes can be done both through global and local links. The number of virtual channels required in each local and global port is determined only by the length of a maximum allowed route that does not use local-type misrouting, using a total order in the virtual channel path, which is violated when perform a local misrouting.

Description

ADAPTIVE ROADING METHOD IN NETWORKS.

FIELD OF THE INVENTION 5 The present invention belongs to the field of communication networks ~ more specifically, it is especially applicable to the field of interconnection networks for parallel computers (multiprocessors or multicomputers).

BACKGROUND OF THE INVENTION 10 In a communications network based on packet switching, a series of clients (or compute nodes) communicate with each other by exchanging messages; Each of these messages is divided into one or more packets, which constitute the basic switching unit in the network. Each package has an origin client and one or multiple destination clients (the latter, in the case of mullicast packages). Broadly speaking, network 15 is composed of a series of routers (also known as switches, or roUlers or switches according to the English terms) that are the active elements of the network. These routers are linked through communications links, that is, cables through which electrical or optical signals are sent that carry the packets of the network. Each client connects through its network interface to one or more routers using the corresponding link (s), and in turn the routers connect to each other through other links. A router has multiple ports, to which the corresponding links are connected to other routers or clients. Customers send packets to routers, which are responsible for transporting them from one router to another until they reach the destination customer. The topology of the network is a mathematical description of the network in which the different routers and clients of the network are connected.

For communication to be possible, a router must be able to receive each packet that arrives through a certain port of entry, store it temporarily,

process it to determine the route to follow, and forward it through the corresponding exit port. For all this, the routers 10 usually have an internal structure similar to the scheme presented in Figure 1. Each Pin input port has an associated input speed ti with one or more memories (also called spark plugs or tails) 12 in which they store data corresponding to the packets that are received by that pine port These multiple buffers 12 are usually used to separate different packets according to their priority, type, or according to a block avoidance policy (as explained below). The packets stored in buffers 12 share the same physical link and input port to the switch; Therefore, when there are several of these buffers 12, they are usually called virtuous eanaJes or "buffer classes". There is a routing logic that is responsible for determining by which Pool output port it is appropriate to resend each packet of the virtual input channels 12, and if any, in which of the virtual channels of the input port of the next router you must enter the package. In turn, each port of saJida pout may or may not have a certain memory to store the packets that have to exit through that port. The connection between the buffers 12 of the pi "input ports and the Poul output ports is typically made by a crossbar 13 (sometimes translated as a cross matrix) that can join in each corunutation cycle any pairs of input buffer and Outbound port, one to each. Each pair of inbound and outbound ports is connected with a single bidirectional link. An allocator ("allocator '~) regulates the use of shared resources. Multiple packets may request the same output port, but only one of them is granted at a time. A C'allocator ") allocator may be of a split (ie separable) or non-divided (ie unified) type. In the event that arbitration over shared resources is implemented through a non-separable allocator, according to William Dally and Brian Towles in Principies and Practices o / lnterconnection Networks Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2003, the allocator allocates the P OIII output ports based on all possible routes it can follow each package in a pine input port To do this, the set of routes (POOl output ports and virtual channel) through which it can exit is calculated for each package, and all those in which there is enough room for the space are passed to the allocator package, then the allocator searches for the allocation of outputs to each package that maxImIce the router throughput in case the arbitration is implemented by a split allocator, according to William Dally and Brian Towles in P rincipIes and Practices ollnterconnection Nelworks. Morgan Kaufrnann Publishers Inc., San Francisco, CA, USA, 2003, each Pin input port chooses one of the virtual channels that have a package ready to go forward (for example, through a round-robin policy), and the package decides, among all the possible routes proJX) driven by the routing logic, the one that most interests you. Then, the selected route is passed to the mapper, which assigns the pout output ports to the applicants. In order to send data from a packet through an output port without loss of data, it is necessary that there is sufficient storage space in the buffer, queue or virtual channel 12 of the corresponding Pin input port of the next switch or router. There are two typical flow control mechanisms to manage this space in the input buffer of the following router: virtual cUI-through (Ve1) (sometimes called pass-through in Spanish) pennite the advance of W1 packet only if there is space available for store it complete; wormhole (WH) (wormhole routing, although the name in Spanish is not usually used) divides the enflits packages (flow control digit, in Spanish flow control unit), and allows as many jlits to advance as there is a gap in the following buffer. Thus, WH allows a packet to stand on the network occupying two or more virtual channels or input buffers of different consecutive routers. In fact, VCT requires that virtual buffers or channels have a capacity equal to or greater than the maximum size of a package while WH only requires that they have capacity for one or more flits. In this way, WH is usually used in environments where the area of the chip or energy consumption (generated by these buffers) is critical, such as networks within the chip. However, in system networks, it is common to use VCT as its implementation is easier. In either case, if there is not enough space in the next buffer or virtual channel, it is typically necessary to wait for the data in said buffer to advance to its destination, and space is freed. In this case, it is said that there is a dependency between one switch and the next.

In a network, interlocking (usually called deadJock according to the English language, or simply blocking) is the situation in which no packet of a given set of packets cannot move towards its destination because a cyclic dependence occurs between the resources requested for Implement this progress. For example, each packet is occupying a hole in a router's queue W13, and in order to move forward it needs to be released a hole in the corresponding tail of the next router, which in turn is waiting for a hole in a third router to be released. , etc., at the end of the day a cycle of full queues in which none of the packages can advance and a gap is never released. This situation is critical for a network, since it causes a complete shutdown of its operation that cannot be exited. To avoid this problem of deadlock, different techniques have been developed, which either detect and solve this situation (for example, discarding any of the packages that make up the cyclic dependence and releasing its "hole" in the buffer) or they do not allow it to be reached (for example, through restrictions on the routing of packets on the network that do not allow cyclic dependencies to be generated). The first techniques are called blocking resolution, and they are more frequent in networks with losses, which are those that are unreliable and do not guarantee the delivery of data at the destination (such as Ethernet). On the other hand, the techniques of the second type are called block avoidance, and are preferable in networks without losses since they do not require the retransmission of the data. The mechanisms to avoid blockages are in many cases closely related to the network topology, the flow control mechanism (VCT or WH), and the use of the different virtual channels of each input port.

A recently proposed topology for use in high-scale systems interconnection networks is called Dragonjly, described in US patent application US201O / 0049942 Al and in Technology-driven, highly-scalable dragonfiy topology published in ISeA '08: Proceedings 01 he 35th Annual Internalional Symposium on Computer Architeclure, pages 77-88, 2008, by John Kim et al., Or direct hierarchical network, described by B. Arimilli el al. in The PERCS HighPerformance Interconnect. In Proceedings 01 18th Symposium on High-Performance

lnterconnects (Hot lnterconnects 2010). IEEE, Aug. 2010. A specific case of this topology is shown in Figure 2. The general idea of this topology is to use routers 20 of high number of ports linked in "groups" 21. In the example shown in Figure 2 each Group 21 is made up of the same number of routers 20, but it doesn't have to be that way. Globally, all groups 21 are linked together. with a single link between each pair of groups, according to what is called a complete graph topology. Figure 2 shows in broken lines the global links 22. Locally, the switches of each group are also connected to each other, typically also with a complete graph topology with a single link between each pair of switches. Figure 2 shows in a continuous line the local links 23. Therefore, a group 21 is formed by a set of nearby corunators or routers 20 and by the clients of the system that are connected to them (nodes 24). All this is typically located in the same cabinet or several neighboring cabinets. The links that link corunitors of different groups are called global links 22 and typically employ optical technology, due to their greater length. The links between the switches in a group are called local links 23, and can use electrical technology due to their shorter length.

The routing mechanism of the network is what determines the route that packets follow from a source node (or, equivalently, from a source switch) to a destination node (or switch). The mechanism of encanunamiento proposed for these networks in the pennite bibliography two types of routes: i) The minimum route, which uses the only shortest route between any pair of origin and destination routers. Considering the complete graph topologies both at the local level of the groups and globally, the minimum route crosses 10 sumo three links: local -global -local. An example of a minimum route is shown in Figure 3, in which to pack a packet from the originator "O" to the destination router '' 'D' 'the packet takes a first local jump 23-1 followed by a jump global 22-1 and a second local jump 23-2. ii) A non-minimum route, or Valiant route, as described by L. G. Valiant in A scheme foc fast parallel communication. Journal on Computing, 11 (2): 350-361, 1982, in which the package is first sent to an intermediate group (different from the origin group

and destination) to balance traffic, using up to two links, local and global, and from there to the destination, using the minimum route. Therefore ~ this mechanism allows routes of maximum length 5: local -global -local -global -local. This non-minimum routing makes sense when the overall link of the corresponding minimum route is saturated, since although more links in the network are traversed, the saturated link is drawn. This routing is depicted in the example of Figure 4, in which the sequence of routers traversed is routed to route a packet from the originating router "O" to the destination router "D": The packet, which is located in a router origin "O" that belongs to a group origin Co gives a first local hop 43-1 to a router ")" of the same origin group Ca. Next, a first global jump 42-1 takes place to a node "2" belonging to an intermediate group G /. Then the package travels a second local road 43-2 until it reaches a router "3" of the same group G /. Then the packet follows a second global jump 42-2 to a router "4" belonging to the destination group GD. Finally the packet takes a local path 43-3 to the destination node "D".

In the general case, it is desirable that the routing be adapted to the circumstances of network occupation through an adaptive mechanism that selects between a minimum or non-minimum route depending on the state of the network links. The problem with these mechanisms is that, in order to make the decision to use the minimum route or a name in the router or source router, they need information on the state of the global link of the minimum route that is not necessarily connected to this source router, as in the examples of figures 3 and 4. Therefore, this decision must be made by estimating the state of the network from remote information. Among these mechanisms are, for example, UGAL, Piggybacking (PB), Credit RoundTrip Time (CRT) or Reservation (RES) proposed by Nan Jiang et al. in Indieect adaptive routing on large scale interconnection networks in ISCA '09: Proceedings 01 (he 36th annual International Symposium on Compuler Architeclure, pages 220-231, 2009 And by John Kim et al. in the aforementioned Technology-driven, highly scalable dragonfly topology In A '08: Proceedings 01the 35th annual International Symposium on Compuler Architecture, pages 77-88, 2008. The Progressive Adaptive Routing (PAR) mechanism, introduced by Nan Jiang al., Allows when a minimum route is chosen, after the first step, change to a non-minimum route starting at the current router (the second of the minimum route) and using the local information of the current router.This mechanism with traffic adaptability is interesting because it allows you to adapt the routing more fast in the presence of network traffic changes, but at the expense of longer maximum routes since it allows an additional first local jump.

The fact of making a jump through a network link that does not bring the packet to its final destination is technically called misrouting. In the previous case of non-minimum routing, the first global jump 42-1 (between routers numbered as' '' 1 '' and "2") is a global misrouting ~ that is used to circumvent a saturated global link. This saturation of global links can be consistent in a DragonfIy topology, since there is a single global link between each pair of groups, with multiple nodes in each group. When the nodes of these groups communicate with each other, the only global link that unites them tends to become saturated, and by misrouting this link can be avoided at the cost of going through a randomly intentional group. Note that, depending on the chosen group, a first local jump may be required prior to global misrouting (in Figure 4, local jump 43-1 between the routers numbered "O" and "1"). Similarly, a local misrouting is defined as a jump through a local link (therefore, it does not leave the group in which the package is located) that does not bring the package closer to its destination. The local misroUling aims to circumvent saturated local links within a group. European patent application EP2451127AI suggests the use of local misrouting in any group of the package route. Figure 5 shows an example of a non-minimal route, with a global misrouting 52-1 followed by a local misrouting 53-1 in the G • group.

The block avoidance mechanism proposed for this Dragonfly topology in Technology-driven, highly-scalable dragonfly topology in ¡SeA '08: Proceedings oJ the 35th annual Internalional Symposium a Computer Architecture, pages 77-88, 2008, by John Kim el al . and in B. Arimilli el al. in The PERCS High-Performance Interconnect in Proceedings 01 18th Symposium on High-Performance Interconnecls (Ho! Inlerconnects 2010). IEEE, Aug. 2010, is based on an original technique proposed by K. Günther in Prevention ofdeadlocks in packet-switched data transport systems in Communications. IEEE Transactions on, 29 (4): 512-524, April 1981. This mechanism prevents the occurrence of blockages based on the orderly use of so many virtual channels (Virtual Channels, Ves) in the router's input ports such as the length in jumps of the longest route pennitida in the network. The key idea is that every time a router resends a packet, the virtual channel index used for it increases. In other words, a total order relationship is imposed in the use of network resources, in this case the virtual channels in each of the different ports of entry of the different routers. This prevents interlock or deadlock, which can be demonstrated intuitively recursively: Packages in the virtual channel with the highest index are not blocked, because they are going to get used up; packets in a certain virtual channel are not blocked, because they will either be consigned, or they depend on the immediately superior that is free from blocking.

The problem with this implementation is that, in general, it requires a high number of virtual channels, which translates into a high area of silicon and a greater complexity of router design. If the nominal routing is allowed with a local -global -local -global -local route as shown in Figure 4, then 5 virtual channels are required, called I see VC4. However, by coinciding that each jump in the route always runs the same type of link, local in the case of odd jumps and global in pairs, the router implementation can be done with only 3 times in local ports and 2 You see in the global. In the case that a package follows a shorter route, it is enough to skip the channels corresponding to the jumps that do not appear in the route. In the case of using the PAR routing, introduced by Nao Jiang et al., As it allows routes of length 6, one more time is necessary, specifically in the local ports (in total, 4 local times and 2 global times). The interest that the routing mechanism allows local misrouling has been argued. However, it is clear that

This misrouting lengthens the maximum route allowed on the network, and therefore increases, according to the previous block avoidance mechanism, the number of virtual channels required. If the number of local misroutings is not restricted, an unlimited number of virtual channels are required with the previous mechanism, which is clearly

5 not implementable. Specifically, if it is limited to a maximum of one local misrouting for each group that crosses the package, the route will be extended by up to three local jumps (for the three groups that the package can go through: origin, intent and destination) which would give place 6 times for local links and 2 times for global ones.

10 In summary, there is no known routing mechanism in the state of the art that pennita the use of local misrou / ings, with complete adaptability in transit without restricting the routing and without employing a high number of virtual channels. If there is, such a mechanism would be very desirable, since it would allow to obtain a high performance (due to the local misrouting that allows to overcome saturated local links),

15 would quickly adapt to changes in the type of traffic (due to the adaptability in transit), it would use the network resources in a balanced way because of the complete adaptivity and would not use additional resources.

20 SUMMARY OF THE INVENTION

The present invention seeks to solve the aforementioned drawbacks by a routing method for direct hierarchical networks.

Specifically, in a first aspect of the present invention, a packet routing method is provided in a hierarchical direct network formed by a plurality of routers, each with a plurality of local type ports and a plurality of type ports. global, where each of the ports comprises a plurality of virtual channels, and where the routers form

30 groups, where the different routers of the same group are

interconnected by a connected topology using local type links joining pairs of local type ports, and in turn the different groups are interconnected by a connected topology using global type links joining pairs of global type ports. The method is configured to employ 5 jumps for these links according to minimum and non-minimum routes, where jumps involving non-minimum rollers can be performed both through global and local links. In addition, the number of virtual channels needed in each local and global port is determined only by the length of a maximum allowed route that does not use misrouJing of local type, using a total order

10 in the virtual channels route, which is violated when a local misrouting is performed.

In a particular embodiment, the connection between the different routers of the same group is made according to a complete graph, and the connection between the

1 5 different groups are also performed according to a complete graph, and each local port comprises only 3 virtual channels and each global port comprises only 2 virtual channels.

In a particular embodiment, for each packet located in a virtual channel of a router's port 20, the method comprises:

-

calculate at least one hop according to a minimum routing between the router in which said packet is located and the router to which the node to which said packet is directed is connected;

-

calculate at least one jump according to a non-minimum routing that

25 comprises a global misrouting, through an intermediate router group different from the group to which the originating router and the router to which the destination node of the packet is connected;

-

calculate, if a local misrouting boundary limit has not been reached and the minimum routing has calculated local-type breaks, at least one minimum local hop 00 different from those jumps calculated by the minimum routing;

-

select one of these jumps based on a determined criteria.

In the previous embodiment, the method may employ a unified allocator at each router to carry out the selection of one of said jumps to advance a packet.

Alternatively, a route is selected for each packet in each arbitration cycle by comparing the occupancy of the virtual input channel on the next router corresponding to a selected minimum route, versus the occupancy of the virtual input channels of the corresponding routers. to other routes.

Alternatively, a route is selected for each packet in each arbitration cycle by comparing the values of a plurality of containment counters, there being as many counters as output ports the router has, said counters registering the number of packets of the ports of entry whose minimum route advances through the corresponding exit port.

Alternatively, a route is selected for each packet in each arbitration cycle according to a combination of both the information obtained from the occupation of the virtual input channels of the neighboring routers and a plurality of containment counters ~ registering said counters the number of packets of the input ports whose minimum route advances through the corresponding output port.

In another particular embodiment, wormhole flow control is used in all the jumps in which the total order established for the virtual channels is respected, and cUI-through virtual flow control in the jumps in which a local misrouling is made that violates said order. total, allowing all virtual channels to have a size

less than the maximum size of the menoS package corresponding to the first virtual channel.

In another particular embodiment, the total order may be an ascending order or a descending order.

In another aspect of the invention, a hierarchical direct network is provided formed by a plurality of routers, each with a plurality of local type ports and a plurality of global type ports, where each of the ports comprises a plurality of virtual channels, where routers form groups, where different routers of the same group are

10 interconnected by means of a connected topology using local type links joining pairs of local type ports, and in turn the different groups are interconnected by a connected topography using global type links joining pairs of global type ports. The direct hierarchical network comprises means to carry out the above method.

15 As can be seen, this method of routing pennite avoidance of blockages, adaptability in transit and the use of local misrouting, without requiring more than the 3 local times and the 2 global VCs required in routing mechanisms of the prior art.

Other advantages of the invention will become apparent in the following description.

BRIEF DESCRIPTION OF THE FIGURES

In order to help a better understanding of the features of the invention, according to a preferred example of practical realization thereof, and to complement this description, a set of drawings is attached as an integral part thereof. It is illustrative and not limiting. In these drawings:

Figure I shows a schematic of a router's architecture.

Figure 2 shows an example of the Dragonf1y topology or direct hierarchical network.

5 Figure 3 shows an example of routing in a direct hierarchical network, following a minimum route between two groups.

Figure 4 shows an example of routing in a direct hierarchical network, following a Valiant route or non-minimum route between two groups, in which the 10 sequence of routers traversed is numbered.

Figure 5 shows an example of non-minimum routing with global and crazy misrouting1 in the group intentionally.

Figure 6 shows a scheme of a network router on which the routing method of the invention is implemented.

Figure 7 shows seven examples of routing between two groups and routes resulting from the routing method of the invention, from a router 20 origin O to destination D. Specifically, it is exemplified: a) Minimum route. b) First and second jump non-minimum route and then minimum route until reaching the destination. e) First jump non-minimum route and then minimum route until reaching the destination. d) First jump minimum route, then non-minimum route and last minimum route until reaching the destination. e) Same route as in case e, with local misrouting in the

25 group intentionally. f) Same route as in case e, with local misrouting in the target group. g) Same route as in case b, with local misrouting in the intermediate group.

Figure 8 shows three examples of order in the use of virtual channels, according to a possible implementation of the routing method of the invention, considering the routes used in Figures 7-b. 7-g and 7- [; The first a) has all the ascending jumps, the second b) has a unique local misrouting that violates said

ascending order and the third e) has 3 local misroutings that violate said ascending order.

DETAILED DESCRIPTION OF THE INVENTION

In this text, the term "comprises" and its variants should not be understood in an exclusive sense, that is, these terms are not intended to exclude other technical characteristics, additives, components or steps.

In addition, the terms "approximately", "substantially", "around", "" ones ", etc. should be understood as indicating values close to those terms accompanying them, since due to calculation or measurement errors, it turns out irXJ> It is possible to achieve these values with complete accuracy.

Misrouling is defined as the act of jumping through a network link that does not bring the packet closer to its final destination. In Spanish it could be called "detour", although the term English is often used.

When that misrouting is performed between routers of different groups, it is a global misrouting, which is used to circumvent a saturated global link.

When this misrouting is performed between routers of the same group, it is a local misrouting, which is used to circumvent a saturated local link within the same group.

The following preferred embodiments are provided by way of illustration, and are not intended to be limiting of the present invention. In addition, the present invention covers all possible combinations of particular and preferred embodiments indicated herein. For those skilled in the art, other objects, advantages and features of the invention will be derived partly from the description and partly from the practice of the invention.

The routing method of the invention is applicable to hierarchical direct networks, as outlined in [general one in Figure 2, where each of the routers 20 responds generally to the architecture represented in the figure

6. The network is connected by a plurality of routers 20, each of which comprises several injection and consumption ports to which compute nodes 24 are connected or can be connected. Routers 20 are grouped together by groups 21 by means of a connected topology , that is, in which there is at least one way to communicate any pair of nodes. Similarly, the different groups are interconnected through a related topology. Although in Figure 2 all groups have the same number of routers, in general different groups may have a different number of routers. Figure 2 also shows the local links 23, that is, between routers of the same group, and the global links 22, that is, between routers of different groups. Preferably, the present routing method is applicable when the connection between routers of the same group corresponds, at least, to a complete graph (also known as f1allened butterfly of 1 dimension), with at least one link between each pair of routers. In addition, in case of having additional ports on the routers there may be local links 23 for them between the same pair of routers of the same group. Also preferably, the present routing method is applicable when the connection between groups corresponds, at least, to a complete graph.

In the router's architecture, it is assumed that at least the virtual channel I see has enough capacity to host a maximum size packet hanging on the network.

Figure 6 shows a scheme of a router 60 of the network on which the routing method of the invention is implemented. Each router 60 needs three virtual channels (VeO, VC2 and VC4, referenced in the figure as 62-0, 62-2 and 62-4) on local ports 62, and two virtual channels (VCI and VC3, referenced in the figure such as 61-1 and 61-3) on global ports 61. The specific labeling of virtual channels may vary while maintaining the number of ports and the relative order. The port that communicates each computing node with a network router is called an injection port, not illustrated in Figure 6. This port does not need to be divided into virtual channels, and if an index is specified

5 for it, is irrelevant for the avoidance of blockages. For order purposes, packets in an injection port are considered to be in the virtual channel -l.

The proposed method or mechanism provides, on each router in the network, the set of routes that a packet can follow. These routes correspond to minimum 10 routes (from the current router to the destination, regardless of the route previously followed by the package), non-minimum routes that use a global misrouling to pass through an intentional group, as well as local misrouting Internal to a group. Then, some logic of the current router is responsible for selecting an option among all possible to make the advance of the package; that is to say

15 allows adaptability in transit. This logic can use information on the state of the network to select the most appropriate route. The occupation of the buffers or virtual channels of the different paths, which is derived from the credit account of the router outputs, is an example of an indicator of the network status.

20 As explained below, the routing mechanism is free of interlock. To guarantee this, the minimum and Valiant routes (non-minimum with global misrouling) follow an ascending order of indexes in the virtual channels used, which guarantees that packets can be routed to the destination using those routes without blocking. In a general case, you can follow any total order in the use of

2 5 virtual channels, not necessarily the cited ascending order. On the contrary, local misrouting violates said total order relationship, reusing the same channel in progress, or a lower one. This violation means that the advance of the packages for the routes that use local misrouting cannot be guaranteed, and this advance can only be made when there is a gap in an appropriate local link; however, in practice, this is frequent, and this is how to get around saturated local links. The proposed routing mechanism, R, is of type R: C X N 1 --- + P (C), is

say: the routing mechanism R is implemented as a function that, given a packet located in a virtual channel e of an input port of a given incarnator, and for a destination node N, returns the set of virtual channels of the ports of output P (C) through which the package can advance. Thus, R not only specifies the port through which a packet can exit, but also the virtual channel through which it must advance on the neighboring router if it leaves through that port. To calculate the possible routes to follow, R uses the identification of the current router (its index in the network and the group to which Gi belongs), the port and virtual channel in which the packet is located (called the input port and virtual input channel) as well as the routing information present in the packet metadata (the Norigen origin node, which is connected to the Eorigen router belonging to the Gorigen origin group; and the Ndestino destination node. connected to the Edestine router in the Gdestino group). This routing information can appear explicitly in the packet metadata, or they can be calculated (for example, if E and G are derived mathematically from N and the network properties, such as the number of nodes per router , routers per group, etc). In addition, we assume that the package has some flags or counters to limit the number of times that both local and global misrouting can be done, and that there are limits to the number of times that misrouting is allowed: Llocal-misrouting and L. global- misrouting CO-misrouting can refer to the number of times local misrouting is allowed either along the entire package route, or by group. Although it could be generalized, we assume L. global-misrouting: ;;:; 1, as in all previous works.

The proposed routing mechanism R can be expressed as the union of three separate routing subfunctions: R: ;;:; RminURnon-minURlocal-misr. Each of these three mechanisms returns a set of output ports and virtual channels for a packet on a given node and a given virtual channel, independent of the path previously followed by the packet. In general, for

.

reach its destination, the package can follow any of the routes provided by the routing mechanism. However, in [anointing of the network status (queue occupancy or some other indicator), the logic of the routers can select a subset of options to achieve the best performance.

5 Note that in the case of using a complete graph topology (without parallel links) both between the routers of a group and between groups, there is a single minimum route. Rmino However, if additional links have been used to take advantage of available ports on the routers , then that route will not be

10 unique.

The proposed mechanism R is fully defined if each of its three components is defined, which is done below. The following tenninology is considered: E¡ (router in which the packet is located), G¡ (group to which the router in which the packet is located), Norigen (origin node), Eorigen (router to which it is located) Norigen is connected), Gorigen (group to which Eor¡gen belongs), Ndestino (destination node), Edestino (router to which Ndestino is connected), Gdestino (group to which Edestino belongs), Eout

(set of Gi routers that have a global link that connects 20 directly with Gdestino).

• Rmin corresponds to the minimum routing of a packet from Ei to Ndestino. Thus, Rmin generates a set of routes (at least one) according to the first of the following conditions that is true:

25 a) If El = Edestino. In this case the route is given by the port that connects Ndestino. b) If G¡ = Gdestino. In this case, the routes (at least one) are given by the set of ports that directly connect Ei to Edestino. e) If Ei has at least one global link that connects it directly to 30 Gdestino. In this case the routes (at least one) are given by the

set of ports that connect directly to Gdestino

d) If G¡ * Gorigen 'Then Rmin comprises all routes (at least one)

that unite with Eaut.

e) If G¡ = Gorigen 'Rmin comprises all routes (at least one) that

5

join with Eout • but also the channel must be explicitly used

virtual see.

The virtual channel index of the output in cases a) -d) depends on the type of

port through which the package (local or global) is received and through which it has to be

forward on each router through which it passes, as well as the channel index

10

virtual in which the package is in the port of entry. If both ports

(input and output) of the current router, are of the same type (local-local or

global-global) the index is increased by two units; otherwise, it is increased

in one unit

fifteen

• Rnon-min corresponds to the non-minimum routing of a packet to

through an intentional group, without misrouling locaL Rnon-min generates a

set of routes (at least one) according to the first of the following

conditions that are true:

f) Yes G¡ '* Gorigen. Rnon-min returns the same result as Rmin.

twenty

g) If Ei '* Eor¡gen Y Ei does not have a global link that connects

directly with Gdestino. Then the package can go out by anyone

of the global ports of Ei. using the virtual channel VCl.

h) In another case, either Ei = Eorigen or Ei '* Eorigen Y also provides

of a global link that connects it directly with Gdestino. In this

25

In case the package can leave through any of the local ports of Ei

using the virtual channel I see or through any of the global ports of

Ei using the virtual channel VCl.

An alternative implementation to that described in rules f), g) h) is proposed,

30

which is more restrictive in generating Rnon-min routes with the

In order to balance the outbound traffic through the different links of the GOTigen group while minimizing the length of the routes traveled, according to the following rules (alternatives af) -h), note that i) coincides with 1): i ) If C¡ '* Correct. Rnon-min returns the same set of routes as

Term

j) If E¡ = Eorigen Y the package is in the injection port, the package can exit through any of the global links of E¡ using the virtual Vel channel.

k) If E does not have a global link that connects directly to Gdestino, then the package can exit through any of the global ports of E "using the virtual channel go !.

1) If you do have a global link that connects you directly to Gdestino, enlOnceS the package can exit through any of the local Ei ports, using the virtual channel I see.

• Rlocal-misr corresponds to the local misrouting in the target group or an intentional group. In the origin group, Rnon-min is the one that allows misrouling (global, in that case) when congestion is detected. Rlocal-misr generates its routes according to the first of the following conditions that is true: m) If Ci = Cdestino 'and also E¡ "* Edestino, And the local misrou / ings account of the package is smaller than L¡Ocal -misrouting, then Rlocal-misr comprises all the local links of Ex. n) If C¡ "* Gdestjno, C¡" * Corigen, and also Ei does not have a global link that connects with Cdestino and the local misroutings account of the package is less than Llocal-misrouting, so Rlocal-misr understands all the local Ei 'links

o) In another case, no route is generated. In both cases, the virtual channel used is the same as the one containing the

packet at the port of entry (if this is a local type) or a lower unit (if it is global).

Below are some examples of possible routes generated by the mechanism illustrated in Figure 7.

Figure 7-a shows a route from EOriaen (O) to Edestino (D) in which all the jumps are given by the minimum routing (conditions a-e). Figure 7-b shows a route from Eorigen (O) to Edestino (O). While a packet is in Eorigen, it leaves through one of its local ports returned by Rnon-min using the virtual channel I see (condition h », 71. Next, in router 1, the packet leaves through one of the global ports returned by Rnon- min, using the virtual channel Ve1 (condition h », 72. From there, the packet is routed by the minimum route to Edestino (conditions a) to ad». Figure 7 · c shows the routing from Eorigen (O) to Eaestino (D) when performing a global misrouling 73 for a package that is in one of the Eor¡gen injection ports (condition j). From there, the package is routed by the minimum route to Edestino (conditions a) ad »Figure 7-d shows a route from Eorigen (O) to Edestino (O) in which a local (not minimum) jump is made prior to a global misrouting, while a package is in Eorigen. one of the local ports 74 of Eorigen returned by Rmin using the virt channel I see (condition e ». Then. the packet being on router 1, motivated for example by congestion on the global link marked by Rmin. the packet leaves through one of its local ports returned by Rnon-min 75. using the VCO virtual channel (condition 1). Then, in router 2, the packet leaves through one of the global ports returned by Rnon-min, using the virtual channel VCI (condition k », 76. From there, the packet is routed by the minimum route to Edestino. that the two local jumps 74 and 75 are t: quivalent to have made a local misrouJing in the origin group (prior to a no minimum global jump), although the route has been generated by

Rmin YRnon-min 'Figure 7-e shows a route from Eorigen (O) to Edestino (D). The packet is routed in the same way as in Figure 7.d but with an additional local misrouting 77 in the intermediate group (condition n.) Figure 7- [shows a route from EOTigen (O) to Edestino (D). packet is routed in the same way as in figure 7.e but with an additional local mjsrouling 78 in the destination group (condition m ». Figure 7-g shows the routing from Eorigen (O) to Edestino (D). it is routed in the same way as in figure 7.b but with an additional local misrouling 79 in the intermediate group (condition n).

Figure 8 shows the order followed in the sequence of virtual channels traversed, in which the gray blocks represent the route routers. Continuous arrows represent jumps with ascending order of virtual channels, while dashed arrows represent jumps that violate said ascending order of virtual channels. Three examples are shown: a) a route that does not use local misrouting (such as the route in Figure 7-b) that follows a strictly ascending order; b) a route that uses a local misrouJing (such as the route in Figure 7-g), where the jumps corresponding to the local misrouting violate said strictly ascending order, while the rest of the jumps respect such order ~ c) a route that employs several local misroutings (such as the route in Figure 7-f), where three local jumps are used that do not increase the virtual channel index, maintaining or decreasing it with respect to the previous jump, while the rest of the jumps do increase the index used .

The criteria for choosing a specific route between the different ones allowed by the mechanism admit multiple implementations. In a non-limiting manner, these may be based, for example, on the allocation by a unified allocator, on the credits available for each exit port, or on containment counters on the exit ports. Some implementations are shown in application examples 1 to 3.

The R == RminURnon-minUR / ocal-misr routing mechanism allows traffic to be routed between any pair of origin and destination nodes in the absence of deadlock. To prove it, it is sufficient to demonstrate that there is a routing subfunction that is free of deadlock, according to William Dally and Brian Towles in PrincipIes and Practices ollnterconnection Network-s. Morgan Kaufmann Puhlishers lnc., San Francisco, CA, USA, 2003. Specifically, we will show that Rnon-min is able to route any package to the destination without blockages. For this, an invariant is initially defined, which is a property that remains constant in the network with any movement that is made. The following invariant is then defined:

Invariant 1: Given a packet in a virtual channel Vei of an input port of a router or routcr, the sum of i (the index of its virtual channel) plus its distance to the destination router is always less than or equal to 4.

The invariant is tested constructively. According to cases e) and h) or 1) it follows that local Gortgen links can only be used through the channel I see, and according to cases e), and g) and h) or j) and k), it turns out that Packages can only leave the source group through the Vel channel of a global link. Similarly, if an intermediate group is traversed, according to d), f) or i) and n) it turns out that only the local index links I can see for local misrouling and Ve2 can be used to reach Eout, and therefore , according to c) and t) or i), it turns out that packets can use Vel or Ve3 to cross the global link with which they reach the destination group. Finally, in the destination group according to b), f) or m) the packets can use any virtual channel of the local links (VeO, VC2 or VC4) to reach the destination router, where the packet is consumed.

It is enough then to consider that the diameter of the Dragonfly is 3 and the distances to the destination to verify that the invariant is true. Consider a packet at an input port of a router E¡ in a group Gi '* Gdest¡no' Then, if the router is directly connected to Gdestino, at most it will have been reached by the virtual channel VC2, and its distance to Edestino will be at most 2 (for the two jumps, global -local, that separate him from the destination). In any other G router, the distance to Edestino will be 3, but the packet will be in a virtual input channel I see (if the port is local) or Vel (if it is global). On the other hand, in the destination group Edestino is the only router that can be reached by the virtual channel VC4; the other routers are remote 1 from Edestino And are reached, at most, by the virtual channel Ve3, so that in all cases the invariant l is maintained.

From the invariant 1 the absence of deadlock can be demonstrated. A routing function R: e x N .......... P (C) is free of deadlock if it contains a routing subfunction, in this case Rnon-min. which is connected and without cycles in the extended dependency graph. Rnon-min is connected as it allows you to route any packet to the destination thanks to invariant 1: there is always a route since a packet is never in a virtual channel too high to be unable to reach the destination. On the other hand, when the model is used under cut-through virtual flow control, the extended dependency graph is reduced to the dependency graph; and since the a) -d) and g) -h) (or j) -1)) relations define a strictly increasing path of the virtual channel indices, then there are no cycles.

In addition to this implementation for Virtual Cut-through flow control, under certain conditions explained below the mechanism is applicable to networks with wormhole flow control. The jumps that violate the strictly ascending order of virtual channels generate extended dependencies between the channels involved. In the case shown in figure 8 b), a packet can stand still distributed between the virtual channels I see on the routers marked 1 and 3, and the Vel on the router 2. Therefore, the packet is occupying the virtual channel Ve ! of a router, so it may be stopping another packet that is in the view of another router; therefore, a circular dependency appears that can block the network. To avoid such blocking, it is sufficient to use flow control to see only on local virtual channels that may be the destination of a local misrouting (VeO and Ve2 only), requiring that there be room for the entire package before allowing Jacal misrouting. In this way, the proposed mechanism can work in wormhole in the general case in which an ascending order is followed in the virtual channel indices used ~ and allowing local rnisrouting only if there is room for the entire package in the destination buffer. Obviously, to use this mechanism it is necessary that the butTeres

5 corresponding to local misrouting (at least, VeO) have capacity for the maximum package size. Therefore, such implementation allows reducing the total size of the network buffers, since only a gap is required for the complete package in a single buffer.

Listed below are some examples of the application of the proposed mechanism in 10 different implementations for a better understanding of its operation.

Application example 1: In this application example, a network with a Dragonfly topology is considered in which the router arbitration is implemented by means of a non-separable (ie, unified) al / ocalor ("allocator"). This configuration takes advantage of local misrouting and routing in

15 transyl, but has the problem of not favoring the use of short routes to reduce latency and increase throughput.

Application example 2: In this application example, a network with a Dragonfiy topology is considered in which each router uses a splitter type (or separable) mapper. The selection of the route is critical to achieve a good 20 performance. In general, it is recommended that routes be as short as possible to reduce the traffic load on the network. However, in situations of saturation of the links corresponding to the minimum routes, it is more interesting to take a longer route that bypasses the saturated link. Therefore, there must be a logic that selects between one of the minimum routes provided by Rmfn, or a minimum no25 provided by Rnon-min or Rtocat-misr. One possible implementation is to compare the occupation of the buffers: If the occupation of the Selected minimum queue exceeds a certain threshold, then the choice of a non-minimum output whose occupancy is lower than that of the selected minimum queue scaled by an adjustment factor is allowed. If there is no non-minimum queue available, or the

Minimum queue occupancy selected is less than the set threshold, then the minimum route selected from those routes set by Rmin 'is used. This decision is repeated in each cycle in which the packet is still waiting, because the dispatcher did not assign the chosen output. in the previous arbitration cycle.

Application example 3: As in Example 2, a Dragonfly topology with routers with separable allocator is used. To select the minimum or non-minimum route in each jump, the following strategy is used. There is a "containment counter" for each output port. When the routes for a packet of an input port are calculated (either when entering the queue, or when it reaches the header of said input queue), the containment counter corresponding to the selected minimum output is increased, among those indicated by Rmin. This counter is decremented again when the packet manages to advance and exit the node completely. The routing logic uses the containment counters (optionally, together with the queuing status) to select at each router between one of the minimum routes indicated by Rmin or one of the routes indicated by Rnon-min or

Rtocal-misr 'A specific model could use a static threshold from which, if the minimum route selected has more containment, a random name route is selected at random. Another specific model could compare the containment of the minimum route counter selected with the average of all router counters to make this decision.

Claims (11)

l. A method of routing packets in a hierarchical direct network formed by a plurality of routers, each with a plurality of local type ports and a plurality of global type ports, where each of said ports comprises a plurality of channels virtual, where said routers form groups, where the different routers of the same group are interconnected by means of a connected topology using local type links joining pairs of local type ports, and in turn the different groups are interconnected by a related topology using links from global type joining pairs of ports of global type, the method being configured to employ jumps through said links according to minimum and non-minimum routes, where jumps involving non-minimum routes can be made both through global and local links, the method being characterized in that the number of virtual channels needed in each local and global port is determined only by the length of a maximum pennitid route that does not use misroUling of the local type, using a total order in the virtual channels path , which is violated when a local misrouting is performed.

2.

The method of claim 1, wherein the connection between the different routers of the same group is made according to a complete graph, and the connection between the different groups is also made according to a complete graph, and each local port comprises only 3 virtual channels and each global port comprises only 2 virtual channels.

2.

3.

The method of any of the preceding claims, wherein for each packet located in a virtual channel of a router port, it comprises:

-

calculate at least one hop according to a minimum routing between the router in which said packet is located and the router to which the node to which said packet is directed is connected;

-

calculate at least one hop according to a non-minimum routing comprising a global misrouting, through a group of intermediate routers different from the group to which the originating router and the router to which the destination node of the packet is connected;

-

calculate, if a determined local misrouting limit has not been reached and the minimum routing has calculated local-type jumps, at least one nominal local jump other than those jumps calculated by the minimum routing;

-

select one of these jumps based on a certain criteria.

Four.

The method of claim 3, which employs a unified allocator in each router to carry out the selection of one of said jumps to advance a packet.

5.

The method of claim 3, selecting a route for each packet in each arbitration cycle by comparing the occupancy of the virtual input channel in the next router corresponding to a selected minimum route, versus the occupancy of the virtual input channels of the routers corresponding to other routes.

6.

The method of claim 3, a route being selected for each packet in each arbitration cycle by a comparison of the values of a plurality of containment counters, there being as many counters as output ports the router has, said counters registering the number of packets of the ports of entry whose minimum route advances through the corresponding port of exit.

7.

The method of claim 3, a route being selected for each packet in each arbitration cycle according to a combination of both the information obtained from the occupation of the virtual input channels of the neighboring routers and a plurality of containment counters, registering said

5 counters the number of packets of the input ports whose minimum route advances through the corresponding output port. 8. The method of any of the preceding claims, wherein it is used wormhole or wormhole hole flow control in all jumps in which respects the total order established for virtual channels, and flow control 10 through or virtual cUl-lhrough in the jumps in which a local misrouting is done that violates said total order, allowing all virtual channels to be smaller than the maximum packet size minus those corresponding to the first virtual channel. 9. The method of any of the preceding claims, wherein said total order can be an ascending order or a descending order. 10.-A direct hierarchical network formed by a plurality of routers, each with a plurality of ports of local type and a plurality of ports of global type, where each of said ports comprises a plurality of virtual channels, where said routers form groups, where the different 20 routers of the same group are interconnected by means of a connected topology using local type links joining pairs of local type ports, and in turn the different groups are interconnected by a connected topology using global type links joining pairs of ports of global type, said direct hierarchical network being characterized by comprising means for carrying Perform the method according to any one of claims 1 to 9.