Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-05-06
2003-06-17
Nguyen, Chau (Department: 2663)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S468000
Reexamination Certificate
active
06580719
ABSTRACT:
FIELD OF INVENTION
This invention generally relates to the field of queuing systems, and more particularly to the determination of worst case latency (WCL).
BACKGROUND OF THE INVENTION
In a queuing system there are typically a number of channels which can access system resources. As the system resources are shared, only one channel at a time can be granted access. If there are multiple contending access requests of different channels, a pre-defined schematics is employed in prior art queuing systems to select one of the requesting channels for granting of the system resources. After grant the selected requesting channel is the master of the system resources during a certain time slot which can be of fixed or variable length. After the time slot another requesting channel is selected from the waiting queue for grant according to the schematics. Such a schematics typically is implemented in an bus arbiter or scheduler.
Such queuing systems can be found in multi processor systems where a plurality of processors is coupled to the same bus which can only service one processor at a time. Another field of application is in the field of micro controllers. A micro controller has a number of input/output channels which can access the common system resources of the micro controller to perform different kinds of calculations and transformations according to the needs of the technical environment. Micro controllers are used in a wide field of applications, for example in automobile electronics, control electronics of household appliances, control systems of chemical factories as well as in mobile telephone systems.
In such applications the channels connected to the micro controller serve to interact with the real world technical environment. To comply with the needs of the technical environment each channel has to have a minimum band width to ensure proper operation of the technical system. In such a system it is highly desirable to guarantee a minimum channel band width also under worst case operating conditions to prevent failure.
To facilitate the design of a queuing system a method for determining the worst case latency (WCL) has to be employed. The more accurate such a method is, the more effective the common system resources of the resulting queuing system can be used by the requesting channels. From the “Modular micro controller family TPU Time processor Unit”, Reference Manual, published by Motorola, Inc., especially appendix C a method of estimating worst-case service latency in a queuing system relying on a scheduler which applies a priority scheme with priority passing rules is known. No method has been available to exactly determine the worst-case latency with mathematical exactness and without having to add security margins.
It is therefore an object of the invention to provide an improved method for determining a number of accesses granted to requesting channels in a queuing system as well as an improved computer program for carrying out such a method and an apparatus being designed accordingly.
SUMMARY OF THE INVENTION
This and other problems are solved by the invention basically by applying the features laid down in the independent claims. Preferred embodiments are given in the dependent claims.
The inventions allows to determine a number of access granted to requesting channels during WCL of a selected channel of the system. This number of access can be used for different purposes during the system design. In particular, the duration of the WCL itself can be determined based on this number of access according to the invention.
The invention is particularly advantageous in that it allows to carry out the calculation of the worst case service latency automatically by means of a computer. This allows to investigate a large number of different timing scenarios in order to optimize the queuing system for the particular needs of the technical environment.
Further the method of the invention yields accurate results so that it is not necessary to add security margins in the system to guarantee minimal band width for all channels. As a consequence an apparatus which is designed accordingly features improved utilization of the system resources and thereby allows more accurate control or faster operating speed of the overall technical system according to it's field of use.
BRIEF DESCRIPTION OF THE DRAWING
FIG. 1
shows a schematic block diagram of an apparatus which has a queuing system in accordance with the principles of the invention;
FIG. 2
shows an ordered list of priorities which is used in the scheduler of the apparatus of
FIG. 1
;
FIG. 3
shows two sequences of time slots to determine a worst time slot for an access request;
FIG.
4
-
FIG. 8
show sequences of time slots and the associated number of time slots during WCL;
FIG. 9
shows a table which lists the amounts of slots in WCL for different amounts of active high priority channels for the case of high and middle priority requesting channels;
FIG. 10
shows a flow chart of one embodiment of the method for determining a number of accesses granted during WCL;
FIG. 11
shows a mathematical model as an alternative to carrying out the method of
FIG. 10
;
FIG. 12
shows mathematical model similar to the mathematical model of
FIG. 11
to model the information contained in the table of
FIG. 13
;
FIG. 13
shows a table similar to the table of
FIG. 9
for the case that all priorities are present;
FIG. 14
shows a table similar to the table of
FIG. 13
for the case of the WCL of the middle-priority channel as well as the associated mathematical model;
FIG. 15
shows a table similar to the table of
FIG. 14
for the case of the WCL of the low-priority channel as well as the associated mathematical model;
FIG. 16
shows the assignment of channels to functions and their corresponding priorities;
FIG. 17
shows two examples of function state flow charts;
FIG. 18
shows the calculation of the WCL based on state execution times of the functions; and
FIG. 19
is a flow chart illustrating one embodiment of the invention to determine the WCL.
REFERENCES:
patent: 5311513 (1994-05-01), Ahmadi et al.
patent: 5313641 (1994-05-01), Simcoe et al.
patent: 5418967 (1995-05-01), Simcoe et al.
patent: 5434848 (1995-07-01), Chimento et al.
patent: 5528766 (1996-06-01), Ziegler et al.
Modular Micro Controller Family TPU Time Processor Unit; Reference Manual; Published by Motorola, Inc.; Chapter 3; pp. 3-1 to 3-7.
“Time clustered access for maximizing bandwidth utilization via windows of asynchronous arrival”, IBM technical disclosure bulletin, vol. 37, No. 8, Aug. 1994, New York, US, pp 201-214, XP000456391, see whole document.
Tamir et al: “Symmetric crossbar arbiters for VLSI dommunication switches”, IEEE Transactions on parallel and distributed systems, vol. 4, No. 1, Jan. 1993, US, pp 13-27, XP000381322, see p. 19, col. 2—p. 20, col. 1.
Modular Microcontroller Family “TPU, Time Processor Unit Reference Manual”, Rev.2, by Motorola, Inc. 1993, Appendix C, pp C-1 to C-20.
Artamonov Andrey
Makevev Sergej
Soboleva Marianna
Soja Richard
George Keith M.
Motorola Inc.
Nguyen Chau
LandOfFree
Method for determining the number of accesses granted during... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for determining the number of accesses granted during..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for determining the number of accesses granted during... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3102117