Networking Reference
In-Depth Information
allow both x+ and x- movement without restricting later directions, the deadlock avoidance rule is
modified to (x+, x-, y+, z+ then y+, y-, z+ then z+, z-). Thus, free movement is preserved. Note that
missing or broken X links may induce a non-minimal route when a packet is routed via the global
table (since only y+ and z+ are “safe”). With this rule, packets using the global table will prefer to
move in the X direction, to get to their correct global region as quickly as possible. In the absence
of any broken links, routes between compute nodes can be generated by moving in x dimension,
then y, then z. Also, when y=Y max , it is permissible to dodge y- then go x+/x-. If the dimension is
configured as a mesh — there are no y+ links, for example, anywhere at y=Y max then a deadlock
cycle is not possible.
In the presence of a faulty link, the deadlock avoidance strategy depends on the direction
prescribed by dimension order routing for a given destination. In addition, toroidal networks add
dateline restrictions. Once a dateline is crossed in a given dimension, routing in a higher dimension
(e.g., X is “higher” than Y ) is not permitted. Routing rules for X links
When x+ or x- is desired, but that link is broken, y+ is taken if available. This handles crossing from
compute nodes to service nodes, where some X links are not present. If y+ is not available, z+ is
taken. This z+ link must not cross a dateline. To avoid this, the dateline in Z is chosen so that there
are no nodes with a broken X link and a broken y+ link. Although the desired X link is available,
the routing algorithm may choose to take an alternate path when the node at the other side of the X
link has a broken y+ and z+ link (note the y+ might not be present if configured as a mesh), then an
early detour toward z+ is considered. If the X link crosses a partition boundary into the destination
partition or the current partition matches the destination partition and the current Y matches the
destination Y coordinate, route in z+ instead. Otherwise, the packet might be boxed in at the next
node, with no safe way out. Routing rules for Y links
When the desired route follows a Y link that is broken, the preference is to travel in z+ to find a
good Y link. If z+ is also broken, it is feasible to travel in the opposite direction in the Y dimension.
However, the routing in the node in that direction must now look ahead to avoid a 180 degree turn
if it were to direct a packet to the node with the faulty links. When the desired Y link is available,
it is necessary to check that the node at that next hop does not have a z+ link that the packet might
prefer (based on XYZ routing) to follow next. That is, if the default direction for this destination in
the next node is z+ and the z+ link is broken there, the routing choice at this node would be changed
from the default Y link to z+. Routing rules for Z links
When the desired route follows a z+ link that is broken, the preference is to travel in y+ to find a
good z+ link. In this scenario, the Y link look ahead is relied up to avoid the node at y+ from sending
Search MirCeyron ::

Custom Search