Signal routing in processor arrays

A method for determining the routing for a plurality of signals in a processor array, the processor array comprising a plurality of processor elements interconnected by a network of switches, each of the plurality of signals having a respective source processor element and at least one destination processor element in the processor array, the method comprising:

• (i) identifying a signal from a plurality of unrouted signals to route;
• (ii) identifying a candidate route for the signal from the plurality of unrouted signals from the source processor element to the destination processor element, the candidate route using a first subset of switches comprising at least one switch in the network of switches;
• (iii) evaluating the candidate route by determining whether there are offset values that allow the signal from the plurality of unrouted signals to be routed through the first subset of switches;
• and
• (iv) attempting to route the signal from the plurality of unrouted signals using one of the offset values identified in step (iii),
• wherein the signal from the plurality of unrouted signals has an associated rate of transfer that identifies how often the signal is repeated.

A method for determining the routing for a plurality of signals in a processor array, the processor array comprising a plurality of processor elements interconnected by a network of switches, each of the plurality of signals having a respective source processor element and at least one destination processor element in the processor array, the method comprising:

• (i) identifying a signal from a plurality of unrouted signals to route;
• (ii) identifying a candidate route for the signal from the plurality of unrouted signals from the source processor element to the destination processor element, the candidate route using a first subset of switches comprising at least one switch in the network of switches;
• (iii) evaluating the candidate route by determining whether there are offset values that allow the signal from the plurality of unrouted signals to be routed through the first subset of switches;
• and
• (iv) attempting to route the signal from the plurality of unrouted signals using one of the offset values identified in step (iii),
• wherein each switch in the first subset of switches has an associated routing table that includes entries for each signal to be routed through said switch during the operation of the processor array, wherein each entry for a signal in the routing table comprises a rate of transfer for the signal that identifies how often the signal is repeated, the offset at which the signal is routed and/or the number of clock cycles required to complete the transfer.

A method for determining the routing for a plurality of signals in a processor array, the processor array comprising a plurality of processor elements interconnected by a network of switches, each of the plurality of signals having a respective source processor element and at least one destination processor element in the processor array, the method comprising:

• (i) identifying a signal from a plurality of unrouted signals to route;
• (ii) identifying a candidate route for the signal from the plurality of unrouted signals from the source processor element to the destination processor element, the candidate route using a first subset of switches comprising at least one switch in the network of switches;
• (iii) evaluating the candidate route by determining whether there are offset values that allow the signal from the plurality of unrouted signals to be routed through the first subset of switches;
• and
• (iv) attempting to route the signal from the plurality of unrouted signals using one of the offset values identified in step (iii),
• wherein each switch in the first subset of switches has an associated routing table that includes entries for each signal to be routed through said switch during the operation of the processor array, wherein step (iv) comprises:
• attempting to route the signal from the plurality of unrouted signals using an offset value selected from the values identified in step (iii), such that fragmentation of the routing tables is minimised.

A method for determining the routing for a plurality of signals in a processor array, the processor array comprising a plurality of processor elements interconnected by a network of switches, each of the plurality of signals having a respective source processor element and at least one destination processor element in the processor array, the method comprising:

• (i) identifying a signal from a plurality of unrouted signals to route;
• (ii) identifying a candidate route for the signal from the plurality of unrouted signals from the source processor element to the destination processor element, the candidate route using a first subset of switches comprising at least one switch in the network of switches;
• (iii) evaluating the candidate route by determining whether there are offset values that allow the signal from the plurality of unrouted signals to be routed through the first subset of switches;
• and
• (iv) attempting to route the signal from the plurality of unrouted signals using one of the offset values identified in step (iii),
• wherein step (iii) further comprises analysing a timing of the candidate route to determine a number of clock cycles required for the signal from the plurality of unrouted signals to be routed, wherein analysing the timing of the candidate route comprises looking up the candidate route in a sustain cache that stores the number of clock cycles required for routes between different source and destination processor elements.

A method for determining the routing for a plurality of signals in a processor array, the processor array comprising a plurality of processor elements interconnected by a network of switches, each of the plurality of signals having a respective source processor element and at least one destination processor element in the processor array, the method comprising:

• (i) identifying a signal from a plurality of unrouted signals to route;
• (ii) identifying a candidate route for the signal from the plurality of unrouted signals from the source processor element to the destination processor element, the candidate route using a first subset of switches comprising at least one switch in the network of switches;
• (iii) evaluating the candidate route by determining whether there are offset values that allow the signal from the plurality of unrouted signals to be routed through the first subset of switches;
• and
• (iv) attempting to route the signal from the plurality of unrouted signals using one of the offset values identified in step (iii),
• wherein step (iii) further comprises:
• in the event that there are no offset values that allow the signal from the plurality of unrouted signals to be routed, returning to step (ii) and identifying a further candidate route, the further candidate route using a second subset of switches comprising at least one switch in the network of switches, wherein a limit is placed on the number of further candidate routes that can be considered, wherein if the limit is reached without successfully routing the signal from the plurality of unrouted signals, the method further comprises the steps of:
• (v) identifying a candidate route for the failed signal;
• (vi) identifying a competing signal by examining each switch in the candidate route;
• (vii) removing the competing signal and repeating steps (iii) and (iv) for the failed signal.