Communications: electrical – Continuously variable indicating – With meter reading
Reexamination Certificate
1999-01-22
2002-06-25
Zimmerman, Brian (Department: 2735)
Communications: electrical
Continuously variable indicating
With meter reading
C340S870030, C710S044000, C710S107000, C710S111000, C710S116000, C710S119000, C710S120000, C710S123000, C710S244000
Reexamination Certificate
active
06411218
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to data processing and, more particularly, to systems for selecting devices for time-sharing resources in a data-processing context. A major objective of the present invention is to optimize time-sharing among devices sharing a common resource.
Much of modern progress is associated with the development of computers. Much of the attraction of computers lies in the myriad of uses to which they can be put. This flexibility is due both to the variety of software that they can run and to the variety of hardware that can be connected to extend a computer's functionality.
Computer buses provide a common connection standard for hardware devices and a common data pathway that can be time-shared by the devices so that they can communicate with each other and the host system. Typically, bus controllers allocate the data pathway of a bus in response to device requests.
Early buses, e.g., the industry standard bus (ISA), managed the actual communication between devices. However, higher-performance buses permit a suitable device to manage its communications over the bus. In this bus-mastering situation, the bus controller simply selects the device to be the temporary bus master.
As buses become capable of managing more devices, and as more devices become connected to a single bus, the frequency of conflicting requests for bus resources increases. Accordingly, the bus controller must incorporate some system for managing conflicting requests. The following discussion applies most directly to bus-mastering systems in which various devices can present conflicting requests for control of the bus. However, it can be extrapolated to other situations, such as selection of the originating device for a communication, in which one device of many must be selected.
A basic approach to device selection is to rank devices according to some priority scheme and select the device with the highest priority. For example, devices requesting bus control are given a higher priority than buses that are not making such a request. When only one device is requesting control, it can be selected. When two devices are requesting control, priority can be given to the one who has made the request for the longest time, or the one with the highest priority data type to be transferred. (Devices can have requests with different pendencies because the requests can be ignored while another device is completing its turn as bus master.)
Where there are multiple criteria for selecting a device, the criteria themselves must be prioritized. A standard method of expressing this prioritization is to assign each criterion respective bit positions in a numerical priority value. The most important criterion is assigned to the most significant bit positions, and less important criteria are assigned respectively less significant bit positions. When a selection is to be made, the priority values can be input to a “priority encoder”, which simply selects the device associated with the highest priority value.
A typical priority encoder is designed to select a single device even when two or more devices share the highest priority value. In this case, the combinational logic constituting the priority encoder effectively ranks the devices (according to the encoder inputs with which they are associated) and selects the device with the highest ranking among those devices sharing the highest priority. In other words, the device with the highest implicit ranking is selected among those with the highest explicit ranking. Thus, the incorporation of the implicit ranking by the priority encoder ensures that a selection can be made in any situation.
In the course of the present invention, it was determined that the selection scheme implemented by such priority encoders is not, in general, optimal. Since optimizing computer resources is an important performance issue, a more optimal device selection scheme is desired.
SUMMARY OF THE INVENTION
Innovation often begins by looking at old things in a new way. To understand the present invention, it is helpful to move from an implementation-specific conceptualization of the device-selection process to a more functional conceptualization. In the latter case, the arbitrary rankings are treated as part of a combined device-specific and arbitrary-ranking priority value. For example, the lowest ranking device can be assigned an arbitrary-ranking value of 0, the next lowest ranking device can be assigned a value of 1, the next lowest ranking device can be assigned a value of 10 (binary notation), and so on to the highest-ranking device.
Adding leading zeroes as necessary (e.g., 000, 001, 010, 011, 100) to achieve equal bit-string lengths for the arbitrary-ranking values, the arbitrary-ranking values can be concatenated to the right of the device-specific priority values conventional input to a priority encode to form the combined priority values. Since the arbitrary rankings are unique, no two devices can have the same combined-priority values. Thus, the combined-priority values allow for unambiguous selection of the highest-priority device.
Each combined-priority value is a concatenation of a device-specific value and an arbitrary-ranking value. Each device-specific value is a function (simple or combinational) of one or more units of data pertaining to the respective device; accordingly, device-specific values can change over time as new device-specific data is received. For example, a device-specific value can change when a device asserts a request for control of a bus. Conventionally, an arbitrary-ranking value is assigned independent of such device-specific data and remains fixed.
In the course of the present invention, and in terms of this conceptualization, it was recognized that the fixed arbitrary rankings biased selection in favor of devices with higher arbitrary-ranking values to the relative exclusion of devices with lower arbitrary-ranking values. It was also recognized that, while the bias might be negligible where priority conflicts are the exception rather than the rule, this bias can be significant where, as is increasing the case, conflicts are the rule rather than the exception. In general, the resulting bias impairs system performance where the excluded device becomes a “bottleneck” that slows other devices depending on its contributions.
The present invention provides for variable arbitrary rankings so that the relative time-averaged arbitrary rankings can be controlled. In many cases, they can be controlled to make them more uniform. However, a surprising advantage of the invention is that it permits any desired distribution of time-averaged arbitrary rankings to be implemented. Thus, if it is desired that one device win priority conflicts involving equal device-specific values two-thirds of the time over a second device, this can be arranged by selecting a corresponding scheme for varying arbitrary-ranking values.
The present invention provides for random and pseudo-random selections of arbitrary-ranking values. However, just as it sometimes happens that a randomly tossed coin turns up “heads” 100 times in a row, it can also happen that a device is excluded from selection for an unduly extended time when random selection is used. Accordingly, the present invention also provides various round-robin schemes for varying arbitrary-ranking values that reduce the likelihood of such anomalies.
In the case of the round-robin schemes, the changes in arbitrary rankings can be determined as a function of the device that is selected. In such a case, the selected device (which is presumably taking its turn in controlling a bus) can be assigned a lowest arbitrary ranking (to favor devices that have not been serviced for a while). In this case, an arbitrary ranking can be determined in part, but not completely, by device-specific data for the respective device. Alternatively, the round robin can be derived independently of the selections. In the latter case, the round robin can function as a pseudo-random ranking generator.
To minimize the time a
Dalencourt Yves
Zawilski Peter
Zimmerman Brian
LandOfFree
Priority-encoding device selection using variable arbitrary... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Priority-encoding device selection using variable arbitrary..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Priority-encoding device selection using variable arbitrary... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2922433