Method of improving over protocol-required scheduling tables while maintaining same

• US 20080151753A1
• Filed: 12/20/2006
• Published: 06/26/2008
• Est. Priority Date: 12/20/2006
• Status: Active Grant

• Current Assignee: Microsemi Storage Solutions, Inc (Microchip Technology Incorporated)
• Original Assignee: PMC Sierra US Inc (Microchip Technology Incorporated)
• Inventors: Wynne, John M.
• Granted Patent: US 8,462,628 B2
• Time in Patent Office: Days
• US Class Current: 370/235
• CPC Class Codes: H04L 49/254 Centralised controller, i.e. arbitration or scheduling
• CPC Class Codes: H04L 49/30 Peripheral units, e.g. input or output ports
• CPC Class Codes: H04L 49/90 Buffering arrangements

Abstract

Public scheduling tables of PCI-Express network devices are remapped into private scheduling tables having different data structures. The private scheduling tables enable the construction of parallel-processing selection engines (ones with look-ahead selection capabilities) that are more compact in size than would have been possible with use of the data structures of the public scheduling tables. In one embodiment, residual weight values are re-shuffled so as to move each winner of an arbitration round away from a winner'"'"'s proximity bar by a distance corresponding to an initial weight assigned to the winner. The initial weight can be proportional to the reciprocal of a bandwidth allocation assigned to each data source.

Claims

1. A data processing device capable of servicing plural data streams and comprising:

(a) a first scheduling table for storing first scheduling variables defining relative frequencies at which competing data streams are to be serviced by a data servicing resource, the first scheduling table having a predefined first data structure;

(b) a second scheduling table for storing second scheduling variables that are derived from the first scheduling variables, said second scheduling table having a second data structure that is substantially different from the predefined first data structure; and

(c) a selection engine that is responsive to the second scheduling variables stored in the second scheduling table and that operates to offer service opportunities to plural data stream sources in a manner which at least roughly mimics a service-offering schedule defined by the first scheduling variables of the first scheduling table.

2. The data processing device of claim 1 wherein:

(a.1) said first scheduling table defines a plurality of phases and uses corresponding ones of said first scheduling variables as identifiers to identify respective ones of the competing data streams as ones that is to be first offered service by the data servicing resource in each given phase.

3. The data processing device of claim 2 wherein:

(a.2) said first scheduling table has more than 32 active phases.

4. The data processing device of claim 1 wherein:

(a.1) said data servicing resource includes a serial data outputting means.

5. The data processing device of claim 4 wherein:

(a.2) said serial data outputting means is configurable to output serial data onto a PCI-Express serial link.

6. The data processing device of claim 1 wherein:

(a.1) said data servicing resource is reconfigurable to have different data servicing bandwidths.

7. The data processing device of claim 1 wherein:

(b.1) said second scheduling table is structured to define a plurality of said second scheduling variables as initial weights corresponding to corresponding ones of said competing data streams; and

(b.2) said second scheduling table further stores third scheduling variables whose values are functions of corresponding ones of the second scheduling variables.

8. The data processing device of claim 7 wherein:

(b.3) said second scheduling table is structured to define a plurality of fourth scheduling variables corresponding to the competing data streams and indicating at least if a corresponding source buffer of a given stream is empty.

9. The data processing device of claim 7 wherein:

(b.3) said second scheduling table is structured to define a plurality of fourth scheduling variables corresponding to the competing data streams and indicating truthfulness of the condition;

that a corresponding source buffer of a given stream is empty OR a corresponding destination buffer of the data servicing resource is full.

10. The data processing device of claim 7 wherein:

(b.3) said second scheduling table is structured to define a plurality of fourth scheduling variables corresponding to the competing data streams and defining temporary shifting values that are derived from the initial weights and are to be used for producing next values for the third scheduling variables.

11. The data processing device of claim 7 wherein:

(c.1) said selection engine treats the third scheduling variables as effective weights of corresponding ones of the competing data streams where those of the competing data streams that have relatively lower effective weights are given priority for access to the data servicing resource over those of the competing data streams that have relatively higher effective weights.

12. The data processing device of claim 11 wherein:

(c.2) said selection engine increases the effective weight of a given data stream after having granted data of the given data stream access to the data servicing resource.

13. The data processing device of claim 12 wherein:

(c.3) said increasing of the effective weight is a function of the initial weight of the given data stream that was granted said access.

14. The data processing device of claim 7 wherein:

(c.1) said selection engine includes means for keeping values of the third scheduling variables hovering at or above or around a predefined reference value.

15. The data processing device of claim 1 and further comprising:

(d) a mapper for generating said second scheduling variables from said first scheduling variables.

16. The data processing device of claim 15 wherein:

(d.1) the mapper initially generates signals defining the second scheduling variables as functions of the reciprocals of the relative frequencies at which the respective competing data streams are to be serviced by the data servicing resource in accordance with said first scheduling variables.

17. The data processing device of claim 15 wherein:

(d.1) the mapper detects changes to individual ones of the first scheduling variables in said first scheduling table and in response to a detected change, changes two corresponding ones of the second scheduling variables in said second scheduling table.

18. The data processing device of claim 15 wherein:

the first scheduling table is characterized as being relatively publicly accessible to devices external of said data processing device; and

the second scheduling table is characterized as being relatively more private and thus not accessible to one or more of said external devices.

19. A method for selectively dispatching data from plural sources for processing by a shared resource, the method comprising:

(a) maintaining a first dispatch scheduling table that is publicly accessible to at least a predefined group of schedule managers and/or overseer devices;

(b) maintaining a second dispatch scheduling table that is not publicly accessible to at least one member of said predefined group of schedule managers and/or overseer devices, where the second dispatch scheduling table has a substantially different data structure than that of the first dispatch scheduling table; and

(c) using the second dispatch scheduling table to automatically select data from respective ones of the plural sources for successive processing by the shared resource, wherein said using of the second dispatch scheduling table is such as to create an appearance of approximate adherence to a dispatch schedule defined by the first dispatch scheduling table.

20. The method of claim 19 wherein:

(a.1) said first dispatch scheduling table defines a plurality of phases and stores a corresponding set of first scheduling variables as identifiers that identify respective ones of the data sources as ones that are to be first offered service by the shared resource in each given phase.

21. The method of claim 20 wherein:

(a.2) said first dispatch scheduling table has more than 32 active phases.

22. The method of claim 19 wherein:

said shared resource includes a serial data outputting means.

23. The method of claim 22 wherein:

said serial data outputting means is configurable to output serial data onto a PCI-Express serial link.

24. The method of claim 19 wherein:

(a.1) said predefined group of schedule managers and/or overseer devices includes a first network traffic manager for a first network complex.

25. The method of claim 24 wherein:

(a.2) said predefined group of schedule managers and/or overseer devices includes a second network traffic manager for a second network complex that is operatively coupled to the first network complex.

26. The method of claim 19 wherein:

said shared resource is reconfigurable to have different data servicing bandwidths.

27. The method of claim 19 wherein:

(a.1) said first dispatch scheduling table stores a set of first scheduling variables as identifiers that identify respective ones of the data sources as ones that are to be first offered service by the shared resource in each of successive servicing phases;

(b.1) said second dispatch scheduling table is structured to store a plurality of second scheduling variables as defining initial weights assigned to corresponding ones of said competing data sources; and

(b.2) said second dispatch scheduling table is structured to further store a plurality of third scheduling variables whose values are functions of corresponding ones of the second scheduling variables.

28. The method of claim 27 and further comprising:

(d) using a parallel processing method to determine if corresponding ones of the sources that are competing for access to the shared resource have data to submit or not.

29. The method of claim 28 and further comprising:

(e) using a parallel processing method to determine if corresponding data destinations of said competing ones of the sources have capacity to receive data that can be potentially submitted from the corresponding ones of the competing sources.

30. The method of claim 27 and wherein said step of using includes:

(c.1) treating the third scheduling variables as effective weights of corresponding ones of the competing data sources where those of the competing data sources that have relatively lower effective weights are given priority for access to the shared resource over those of the competing data sources that have relatively higher effective weights.

31. The method of claim 30 and wherein said step of using further includes:

(c.2) increasing the effective weight of a given data source after having granted the given data source access to the shared resource.

32. The method of claim 31 and wherein:

(c.3) said increasing of the effective weight is a function of the initial weight of the given data source that was granted said access.

33. The method of claim 30 and wherein said step of using further includes:

(c.2) keeping values of the third scheduling variables hovering at or above or around a predefined reference value.

34. The method of claim 19 and further comprising:

(d) modifying the second dispatch scheduling table in response to changes made to the first dispatch scheduling table.

35. The method of claim 34 wherein said step of modifying includes:

(d.1) detecting changes to individual ones of first scheduling variables in said first dispatch scheduling table and in response to a detected change, changing at least two corresponding ones of second scheduling variables stored in said second dispatch scheduling table.

36. A method of controlling selective dispatching of data from plural sources to a shared resource, the method comprising:

(a) maintaining a first dispatch scheduling table that is publicly accessible to at least a predefined group of schedule managers and/or overseer devices;

(b) maintaining a second dispatch scheduling table that is not publicly accessible to at least one member of said predefined group of schedule managers and/or overseer devices, where the second dispatch scheduling table has a substantially different data structure than that of the first dispatch scheduling table;

(c) using the second dispatch scheduling table to automatically select data from respective ones of the plural sources for successive processing by the shared resource, wherein said using of the second dispatch scheduling table is such as to normally create an appearance of approximate adherence to a dispatch schedule defined by the first dispatch scheduling table; and

(d) temporarily making modifications to the second dispatch scheduling table without making corresponding changes to the first dispatch scheduling table.

37. An apparatus comprising:

(a) re-mapping means for remapping a publicly-maintained, first scheduling table that has a first data structure to thereby generate a corresponding and privately-maintained, second scheduling table that has a different second data structure, where the first and second scheduling tables are used for controlling traffic flow in a network; and

(b) a history-weighted, service offering means for opportunistically offering dispatch opportunities to traffic from different data sources of a local network device based on initial weights assigned to the data sources and based on prior service offerings made to those data sources.

38. The apparatus of claim 37 and further comprising:

(c) a local service adjuster operatively coupled to the network and to the first scheduling table for modifying the first scheduling table in response to backpressure or slack advisements received from the network.

39. The apparatus of claim 37 wherein:

(c.1) said local service adjuster is further operatively coupled to the second scheduling table for modifying the second scheduling table in response to backpressure or slack advisements received from the network.

40. The apparatus of claim 38 and further comprising:

(c) a plurality of local selection engines each dedicated to a respective one of plural and shared processing resources of the local device and each local selection engine being logically associated with a corresponding second scheduling table among plural ones of such second scheduling tables, each local selection engine modifying its corresponding second scheduling table after having granted one of the different data sources access to its respective one of the shared processing resources.

41. A manufactured instructing signal for use in a networked system having plural public scheduling tables for controlling traffic flow in the networked system, having plural private scheduling tables for controlling traffic flow in the networked system, and having plural re-mapping engines for converting scheduling data stored in the public scheduling tables into corresponding scheduling data to be stored in corresponding ones of the private scheduling tables, said manufactured instructing signal comprising:

code directed to a prespecified and instructable re-mapping engine for defining a re-mapping function to be carried out by the instructable re-mapping engine.

42. A manufactured instructing signal for use in a networked system having plural public scheduling tables for controlling traffic flow in the networked system, having plural private scheduling tables for controlling traffic flow in the networked system, having plural re-mapping engines for converting scheduling data stored in the public scheduling tables into corresponding scheduling data to be stored in corresponding ones of the private scheduling tables, and having plural selection engines interacting with corresponding ones of the private scheduling tables, said manufactured instructing signal comprising:

code directed to a prespecified and instructable selection engine for defining an interactive function to be carried out by the instructable selection engine on its corresponding private scheduling table.