TRANSACTION SELECTOR EMPLOYING TRANSACTION QUEUE GROUP PRIORITIES IN MULTI-PORT SWITCH

• US 20080069130A1
• Filed: 09/16/2006
• Published: 03/20/2008
• Est. Priority Date: 09/16/2006
• Status: Active Grant

• Current Assignee: ARM Finance Overseas Limited (SoftBank Group Corp.)
• Original Assignee: MIPS Technologies Incorporated (Wave Computing, Inc.)
• Inventors: Jensen, Michael Gottlieb
• Granted Patent: US 7,990,989 B2
• Time in Patent Office: Days
• US Class Current: 370/412
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/6215 Individual queue per QOS, rate or priority
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling

Abstract

An apparatus for selecting one of a plurality of transaction queues from which to transmit a transaction out of a port of a switch. The apparatus includes a group indicator, for each of the queues, for indicating which one of a plurality of groups of the queues the queue belongs to. The apparatus also includes a group priority indicator, for each group of the plurality of groups, for indicating a priority of the group, the priority indicating a priority for transmitting transactions of the queues of the group relative to other groups of the plurality of groups. The apparatus includes selection logic, coupled to the group indicators and the priority indicators, configured to select a queue of the queues, for transmitting out of the port a transaction thereof, based on the group indicators and the group priority indicators.

Claims

1. An apparatus for selecting one of a plurality of transaction queues from which to transmit a transaction out of a port of a switch, the apparatus comprising:

a group indicator, for each of the plurality of transaction queues, for indicating which one of a plurality of groups of the plurality of transactions queues said transaction queue belongs to;

a group priority indicator, for each group of said plurality of groups, for indicating a priority of said group, said priority indicating a priority for transmitting transactions of the plurality of transaction queues of said group relative to other groups of said plurality of groups; and

selection logic, coupled to said group indicators and said priority indicators, configured to select a transaction queue of the plurality of transaction queues, for transmitting out of the port a transaction thereof, based on said group indicators and said group priority indicators.

2. The apparatus as recited in claim 1, wherein said selection logic is configured to select said transaction queue from of a group of the plurality of groups whose group priority indicator indicates a highest of said group priorities containing one of the plurality of transaction queues that has a transmittable transaction.

3. The apparatus as recited in claim 2, further comprising:

a transmittable indicator, coupled to said selection logic, for each transaction queue of the plurality of transaction queues, for indicating whether said transaction queue has a transmittable transaction.

4. The apparatus as recited in claim 2, further comprising:

a round-robin generator, coupled to said selection logic, for each group of said plurality of groups, for generating a round-robin indicator indicating which transaction queue of the plurality of transaction queues of said group is next in order for transmitting a transaction thereof out of the port;

wherein said selection logic is further configured to select said transaction queue based on said group indicators, said group priority indicators, and said round-robin indicators.

5. The apparatus as recited in claim 4, wherein said selection logic is further configured such that if said group of the plurality of groups whose group priority indicator indicates a highest of said group priorities containing one of the plurality of transaction queues that has a transmittable transaction includes more than one transaction queue that has a transmittable transaction, then said selection logic selects a transaction queue of said more than one transaction queue that said round-robin indicator of said group indicates is next in order for transmitting.

6. The apparatus as recited in claim 1, wherein said group priority indicator for each group of said plurality of groups is changeable each clock cycle to indicate a different priority of said group for transmitting transactions of the plurality of transaction queues of said group relative to said other groups of said plurality of groups.

7. The apparatus as recited in claim 1, further comprising:

group priority generation logic, coupled to generate said group priority indicator for each group of said plurality of groups.

8. The apparatus as recited in claim 7, wherein for each said group of said plurality of groups, said group priority generation logic changes said priority for transmitting transactions of the plurality of transaction queues of said group relative to other groups of said plurality of groups approximately each clock cycle.

9. The apparatus as recited in claim 8, wherein said group priority generation logic changes said priority in a manner further qualified by whether the port transmits a transaction during each said clock cycle.

10. The apparatus as recited in claim 8, wherein said group priority generation logic generates said group priorities in a predetermined pattern over a period of clock cycles.

11. The apparatus as recited in claim 10, wherein said predetermined pattern causes each group of said plurality of groups to have a different aggregate priority over said period of clock cycles from the other groups of said plurality of groups.

12. The apparatus as recited in claim 11, wherein said predetermined pattern causes each group of said plurality of groups to have a higher said group priority than its next lowest adjacent aggregate priority group of said plurality of groups in a ratio of approximately 2:

1.

13. The apparatus as recited in claim 10, wherein N is a number of said plurality of groups, wherein M is a 0-based group number of each group, wherein said group priority generation logic generates said group priorities such that each group is a highest of said group priorities approximately 2̂

M clock cycles out of every approximately 2̂

N clock cycles.

14. The apparatus as recited in claim 8, wherein each time said group priority generation logic changes said priority, if a number of transmittable ones of the plurality of transaction queues in said group is greater than one, and if said priority of said group is a highest of said group priorities having a group with a transmittable transaction queue, then said group priority generation logic refrains from changing said priority for at least a number of clock cycles equal to said number of transmittable ones of the plurality of transaction queues in said group.

15. The apparatus as recited in claim 14, wherein said group priority generation logic generates said group priorities in a predetermined pattern over a period of clock cycles, wherein said predetermined pattern causes each of said transmittable ones of the plurality of transaction queues in said group to have a different aggregate priority over said period of clock cycles from the plurality of transaction queues of the other groups of said plurality of groups.

16. The apparatus as recited in claim 15, wherein said predetermined pattern causes each group of said plurality of groups to have a higher said group priority than its next lowest adjacent aggregate priority group of said plurality of groups in a ratio of approximately (2*D):

E, wherein D is said number of transmittable ones of the plurality of transaction queues in said group, wherein E is a number of transmittable ones of the plurality of transaction queues in said next lowest adjacent aggregate priority group.

17. The apparatus as recited in claim 7, wherein said group priority generation logic generates N said group priority indicators for N said plurality of groups, wherein each of said N group priority indicators specifies a different priority of N priorities.

18. The apparatus as recited in claim 1, wherein the transactions comprise a command to write data to a device coupled to the port.

19. The apparatus as recited in claim 18, wherein the transactions further comprise said data to be written to said device coupled to the port.

20. The apparatus as recited in claim 1, wherein the transactions comprise a command to read data from a device coupled to the port.

21. The apparatus as recited in claim 1, wherein the transactions comprise data to be written to a device coupled to the port in response to a previous transaction received by the port from said device to read said data from another device coupled to another port of the switch.

22. A method for selecting one of a plurality of transaction queues from which to transmit a transaction out of a port of a switch, the method comprising:

grouping the plurality of transaction queues into a plurality of groups;

specifying a transmit priority for each of the plurality of groups; and

selecting for transmitting one of the plurality of transaction queues from one of the plurality of groups having a highest of the transmit priorities that includes at least one of the plurality of transaction queues having a transmittable transaction, in response to said grouping and said specifying the transmit priorities.

23. The method as recited in claim 22, further comprising:

maintaining a round-robin order among the plurality of transaction queues within each of the plurality of groups; and

selecting for transmitting one of the plurality of transaction queues from one of the plurality of groups having a highest of the transmit priorities that includes at least one of the plurality of transaction queues having a transmittable transaction and that is next in the round-robin order among the at least one of the plurality of transaction queues having a transmittable transaction in the group, in response to said grouping and said specifying the transmit priorities and said maintaining the round-robin order.

24. The method as recited in claim 22, wherein said specifying the transmit priorities comprises specifying different transmit priorities for the plurality of groups approximately each clock cycle.

25. The method as recited in claim 22, wherein said grouping the plurality of transaction queues into the plurality of groups comprises grouping the plurality of transaction queues into different groups approximately less frequently than every 50 clock cycles.

26. A port in a switch for transmitting transactions from a plurality of transaction queues in a prioritized but fair manner, comprising:

a port interface, configured to transmit transactions; and

a transaction selector, coupled for selecting the plurality of transaction queues for transaction transmission, said transaction selector comprising;

a group indicator, for each transaction queue of the plurality of transaction queues, for indicating which one of a plurality of groups of the plurality of transaction queues said transaction queue belongs to;

a group priority indicator, for each group of said plurality of groups, for indicating a priority of said group, said priority indicating a priority for transmitting transactions of the plurality of transaction queues of said group relative to other groups of said plurality of groups; and

selection logic, coupled to said group indicators and said priority indicators, configured to select a transaction queue of the plurality of transaction queues, for transmitting out the port a transaction thereof, based on said group indicators and said group priority indicators.

27. The port as recited in claim 26, wherein said transaction selector comprises:

a policy manager, for generating said group indicators and said group priority indicators; and

a transaction scheduler, coupled to receive said group indicators and said group priority indicators.

28. The port as recited in claim 27, wherein said policy manager is configured to generate said group priority indicators having different values approximately each clock cycle.

29. The port as recited in claim 27, wherein said transaction selector comprises:

a round-robin generator, for each group of said plurality of groups, configured to generate a round-robin vector for said group for use by said selection logic in transmitting said transactions.

30. The port as recited in claim 29, wherein said policy manager is configured to generate said group indicators having different values approximately less frequently than every 50 clock cycles, thereby enabling said round-robin generators and said selection logic to effectively maintain fair selection of said transactions within each of said plurality of groups.

31. A computer program product for use with a computing device, the computer program product comprising:

a computer usable storage medium, having computer-readable program code embodied in said medium, for providing an apparatus for selecting one of a plurality of transaction queues from which to transmit a transaction out of a port of a switch, said computer-readable program code comprising;

first program code for providing a group indicator, for each of the plurality of transaction queues, for indicating which one of a plurality of groups of the plurality of transactions queues said transaction queue belongs to;

second program code for providing a group priority indicator, for each group of said plurality of groups, for indicating a priority of said group, said priority indicating a priority for transmitting transactions of the plurality of transaction queues of said group relative to other groups of said plurality of groups; and

third program code for providing selection logic, coupled to said group indicators and said priority indicators, configured to select a transaction queue of the plurality of transaction queues, for transmitting out of the port a transaction thereof, based on said group indicators and said group priority indicators.

32. A method for providing an apparatus for selecting one of a plurality of transaction queues from which to transmit a transaction out of a port of a switch, the method comprising:

providing computer-readable program code describing the switch core, the program code comprising;

first program code for providing a group indicator, for each of the plurality of transaction queues, for indicating which one of a plurality of groups of the plurality of transactions queues said transaction queue belongs to;

second program code for providing a group priority indicator, for each group of said plurality of groups, for indicating a priority of said group, said priority indicating a priority for transmitting transactions of the plurality of transaction queues of said group relative to other groups of said plurality of groups; and

third program code for providing selection logic, coupled to said group indicators and said priority indicators, configured to select a transaction queue of the plurality of transaction queues, for transmitting out of the port a transaction thereof, based on said group indicators and said group priority indicators; and

transmitting the computer-readable program code as a computer data signal on a network.

33. A switch, comprising:

a network; and

a plurality of ports, each coupled to receive transactions from other of said plurality of ports via said network, each of said ports comprising;

a port interface, configured to transmit said transactions to a device coupled to said port;

a plurality of transaction queues, configured to receive said transactions from said network wherein each of said plurality of transaction queues belongs to a group of one of a plurality of groups wherein each of said plurality of groups has a priority for transmitting transactions relative to other groups of said plurality of groups; and

a transaction selector, coupled to said port interface and to said plurality of transaction queues, configured to select a transaction queue of the plurality of transaction queues for transmitting out the port a transaction thereof based on said groups and said priorities.

34. The switch as recited in claim 33, wherein said network comprises a cross-bar network.

35. The switch as recited in claim 33, wherein said transaction selector for at least two of said plurality of ports of the switch is configured to prescribe a different policy for selecting the plurality of transaction queues for transaction transmission than other of said plurality of ports.

41. The apparatus as recited in claim 35, wherein said selection logic comprises:

a plurality of greater-than-or-equal comparators, coupled to receive said transmit values for the N transaction queues, and to generate an indication of said one of the N transaction queues having a transmit value greater than or equal to any of the N transaction queues left thereof in said N-bit input vectors.

42. The apparatus as recited in claim 41, wherein said selection logic comprises:

a tree of muxes, coupled to said comparators and coupled to receive said N transactions, configured to select said one of said N transactions corresponding to said one of the N transaction queues indicated by said indication generated by said plurality of greater-than-or-equal comparators.

43. The apparatus as recited in claim 35, wherein said corresponding transaction is transmittable if said corresponding one of the N transaction queues is non-empty.

44. The apparatus as recited in claim 35, wherein said corresponding transaction is transmittable if said corresponding one of the N transaction queues is unblocked from transmitting transactions.

45. The apparatus as recited in claim 35, wherein the transactions are received from other ports of the switch associated with corresponding ones of the N transaction queues.

68. The switch as recited in claim 33, wherein said transaction selector comprises:

a group indicator, for each transaction queue of the plurality of transaction queues, for indicating which one of a plurality of groups of the plurality of transaction queues said transaction queue belongs to.

69. The switch as recited in claim 68, wherein said transaction selector further comprises:

a group priority indicator, for each group of said plurality of groups, for indicating a priority of said group, said priority indicating a priority for transmitting transactions of the plurality of transaction queues of said group relative to other groups of said plurality of groups.

70. The switch as recited in claim 69, wherein said transaction selector comprises:

selection logic, coupled to said group indicators and said priority indicators, configured to select a transaction queue of the plurality of transaction queues, for transmitting out the port a transaction thereof, based on said group indicators and said group priority indicators.

36. An apparatus for selecting one of N transaction queues from which to transmit a transaction out of a port of a switch, the N transaction queues each being in one of G groups, each of the G groups having a priority, the priority being one of P priorities, the apparatus comprising:

G round-robin vectors, corresponding to the G groups, each having N bits corresponding to the N transaction queues, each being a 1-bit left-rotated and subsequently sign-extended version of an N-bit input vector, said input vector having a single bit true corresponding to a last one of the N transaction queues selected for transmitting in a corresponding one of the G groups;

N G-input muxes, each coupled to receive a corresponding one of said N bits of each of said G round-robin vectors, each configured to select for output one of said G inputs specified by the corresponding transaction queue'"'"'s group; and

selection logic, coupled to receive a transaction from each of the N transaction queues and to select for transmitting out the port one of said N transactions corresponding to one of the N transaction queues having a transmit value greater than or equal to any of the N transaction queues left thereof in said N-bit input vectors;

wherein said transmit value of each of the N transaction queues comprises a least-significant bit equal to said corresponding G-input mux output, a most-significant bit that is true if said corresponding transaction is transmittable, and middle bits comprising the priority of the transaction queue'"'"'s group.

37. The apparatus as recited in claim 36, wherein the priority of each of the G groups is dynamically updatable among the P priorities.

38. The apparatus as recited in claim 36, further comprising:

G round-robin circuits, coupled to receive said G input vectors, and configured to generate said G round-robin vectors, and coupled to provide said G N-bit input vectors to said N G-input muxes.

39. The apparatus as recited in claim 38, wherein each of said G round-robin circuits corresponding to the G groups comprises:

a storage element configured to store said input vector;

wherein if said one of said N transactions selected by said selection logic is in a group other than said corresponding group, then said storage element retains a current value of said input vector;

wherein if said one of said N transactions selected by said selection logic is in said corresponding group, then said storage element receives a new value of said input vector.

40. The apparatus as recited in claim 38, wherein each of said G round-robin circuits corresponding to the G groups comprises:

a sign-extender, coupled to sign-extend said 1-bit left-rotated N-bit input vector to generate said corresponding round-robin vector.

46. A method for selecting one of N transaction queues from which to transmit a transaction out of a port of a switch, the N transaction queues each being in one of G groups, each of the G groups having a priority, the priority being one of P priorities, the method comprising:

generating G round-robin vectors, corresponding to the G groups, each having N bits corresponding to the N transaction queues, each being a 1-bit left-rotated and subsequently sign-extended version of an N-bit input vector, the input vector having a single bit true corresponding to a last one of the N transaction queues selected for transmitting in a corresponding one of the G groups;

for each of the N transaction queues, receiving a corresponding one of the N bits of each of the G round-robin vectors, and selecting as a round-robin bit one of the G received corresponding one of the N bits of each of the G round-robin vectors specified by the corresponding transaction queue'"'"'s group; and

receiving a transaction from each of the N transaction queues, and selecting for transmitting out the port one of the N transactions corresponding to one of the N transaction queues having a transmit value greater than or equal to any of the N transaction queues left thereof in the N-bit input vectors;

wherein the transmit value of each of the N transaction queues comprises a least-significant bit equal to the round-robin bit of the transaction queue, a most-significant bit that is true if the corresponding transaction of the transaction queue is transmittable, and middle bits comprising the priority of the transaction queue'"'"'s group.

47. The method as recited in claim 46, further comprising:

dynamically updating the priority of each of the G groups among the P priorities.

48. A switch port for transmitting transactions from N transaction queues, each of the N transaction queues being in one of G groups, each group having a priority, the priority being one of P priorities, wherein a subset of the N transaction queues may have a transmittable transaction in a selection cycle, the port configured to transmit transactions of the N transaction queues in a round-robin fashion within each of the G groups independent of the other G groups, comprising:

G round-robin circuits, each for generating an N-bit round-robin vector for a corresponding one of the G groups, wherein said N-bits correspond to the N transaction queues, each of said G round-robin circuits comprising;

a first input, for receiving a first corresponding N-bit value specifying which of the N transaction queues was last selected in said group to transmit a transaction;

a second input, for receiving a second corresponding N-bit value, each of said N bits being false if said corresponding transaction queue has a transmittable transaction and is in said group;

a barrel incrementer, coupled to receive said first and second inputs, configured to 1-bit left-rotatively increment said second value by said first value to generate a sum; and

combinational logic, coupled to said barrel incrementer, configured to generate from said sum and said second value said N-bit round-robin vector specifying which of the N transaction queues is selected next from which to transmit a transaction;

N G-input muxes, each coupled to receive a corresponding one of said N bits of each of said G round-robin vectors, each configured to select one of said G inputs specified by the group of the corresponding transaction queue as a round-robin bit for said associated transaction queue; and

selection logic, coupled to said N G-input muxes, configured to select one of the N transaction queues for transmitting a transaction thereof out of the port, wherein said selection logic selects said one of the N transaction queues having said round robin bit set, having a transmittable transaction, and being in a group having said priority a highest of the P priorities having one of the plurality of transaction queues with a transmittable transaction.

71. The switch port of claim 48, wherein only one of said N bits corresponding to said last selected transaction queue is true.

72. The switch port of claim 71, wherein said round-robin vector comprises a Boolean AND of said sum and an inverted version of said second value.

73. The switch port of claim 72, wherein only one of said N bits corresponding to said next selected one of the N transaction queues is true.

49. A method for generating a round-robin bit for use in selecting one of N transaction queues for transmitting a transaction out a port of a switch, the N transaction queues each being in one of G groups, each group having a priority, the priority being one of P priorities, wherein a subset of the N transaction queues may have a transmittable transaction in a selection cycle, the method comprising:

generating G N-bit round-robin vectors each for a corresponding one of the G groups, wherein the N-bits correspond to the N transaction queues, said generating each of the G N-bit round-robin vectors comprising;

receiving a first corresponding N-bit value specifying which of the N transaction queues was last selected in the group to transmit a transaction;

receiving a second corresponding N-bit value, each of the N bits being false if the corresponding transaction queue has a transmittable transaction and is in the group;

1-bit left-rotatively incrementing the second value by the first value to generate a sum; and

generating from the sum and the second value the N-bit round-robin vector specifying which of the N transaction queues is selected next to transmit a transaction; and

for each of the N transaction queues, receiving a corresponding one of the N bits of each of the G round-robin vectors, and selecting as the round-robin bit for the corresponding transaction queue one of the G received bits specified by the group of said transaction queue.

74. The method of claim 49, wherein only one of the N bits corresponding to the last selected transaction queue is true.

75. The method of claim 74, wherein the round-robin vector comprises a Boolean AND of the sum and an inverted version of the second value.

76. The method of claim 75, wherein only one of the N bits corresponding to the next selected one of the N transaction queues is true.

50. A bifurcated selector for transmitting transactions out a port of a switch from a plurality of transaction queues, the selector comprising:

a transaction scheduler, configured to transmit transactions of the plurality of transaction queues out the port;

a policy manager, for prescribing a scheduling policy of the plurality of transaction queues; and

an interface, coupling said policy manager to the transaction scheduler, said interface comprising;

first signals, for said transaction scheduler to receive from said policy manager a group indicator for each of the plurality of transaction queues for indicating one of a plurality of groups to which the transaction queue belongs; and

second signals, for said transaction scheduler to receive from said policy manager a priority for each of said plurality of groups, wherein said transaction scheduler transmits said transactions out of the port based on said group priorities and said group indicators; and

third signals, for said policy manager to receive transaction transmission information for each of the plurality of transaction queues, wherein said policy manager updates said group indicators based on said transaction transmission information, wherein said transaction transmission information comprises an indication of which of the plurality of transaction queues a transaction was transmitted from.

51. The selector as recited in claim 50, wherein each clock cycle said transaction scheduler selects which of the plurality of transaction queues from which to transmit said transactions out of the port, based on said group priorities and said group indicators.

52. The selector as recited in claim 50, wherein said policy manager updates said group priorities based on said transaction transmission information.

53. The selector as recited in claim 50, wherein said policy manager updates said group priorities in a periodic and interleaved manner.

54. The selector as recited in claim 50, wherein said priority of each of said plurality of groups comprises one of a plurality of predetermined priority levels.

55. The selector as recited in claim 50, wherein said transaction scheduler is non-customer-modifiable.

56. The selector as recited in claim 50, wherein said policy manager is customer-modifiable.

57. The selector as recited in claim 50, wherein said policy manager updates said group priorities approximately each clock cycle.

58. The selector as recited in claim 50, wherein said policy manager updates said group indicators approximately less frequently than every 50 clock cycles.

59. The selector as recited in claim 50, wherein the switch includes a switch core, wherein said switch core includes said transaction scheduler and excludes said policy manager.

60. The selector as recited in claim 59, wherein said switch core is synthesizable.

61. The selector as recited in claim 59, wherein said switch core is reusable for a plurality of customers.

62. The selector as recited in claim 50, wherein said transaction scheduler is configured to select at least one of the plurality of transaction queues for which a transmittable transaction has been fetched by the processor, and which has a highest priority specified by said group priorities and said group indicators, from which to issue a transaction.

63. The selector as recited in claim 62 wherein if more than one transaction queue in said group which has said highest priority specified by said group priorities and said group indicators has a transmittable transaction, said transaction scheduler is configured to select one of said more than one transaction queue in a round-robin manner.

64. The selector as recited in claim 50, wherein said interface further comprises:

fourth signals, for said policy manager to communicate to said transaction scheduler for each of the plurality of transaction queues whether to block issuing of transactions for the transaction queue.

65. The selector as recited in claim 50, wherein said interface further comprises:

a clock signal, from said transaction scheduler to said policy manager.

66. A method for transmitting transactions out a port of a switch from a plurality of transaction queues, the method comprising:

signaling, during a first clock cycle, by a policy manager to a transaction scheduler a group indicator for each of the plurality of transaction queues for indicating one of a plurality of transaction queue groups to which the transaction queue belongs, and a group scheduling priority for each of the plurality of groups;

transmitting a transaction out the port, during a second clock cycle, by the transaction scheduler from one of the plurality of transaction queues, in response to said signaling the group indicators and the group scheduling priorities; and

signaling, during a third clock cycle subsequent to the first clock cycle, by the transaction scheduler to the policy manager an indication whether the transaction scheduler transmitted a transaction from each of the plurality of transaction queues.

67. The method as recited in claim 66, further comprising:

signaling by the policy manager to the transaction scheduler an indication for each of the plurality of transaction queues whether to block transmitting transactions for the transaction queue; and

stopping said transmitting by the transaction scheduler transactions from each of the plurality of transaction queues signaled by the policy manager to block transmitting transactions.