 |
Description  |
|
|
BRIEF DESCRIPTION OF THE INVENTION
This invention relates generally to the scheduling of cells in a
high-bandwidth input-queued switch, for instance as used in asynchronous
transfer mode networks. More particularly, this invention describes a
rotating priority iterative matching desynchronization technique that
improves cell processing in an input-queued switch.
BACKGROUND OF THE INVENTION
Networks are widely used to allow computers to communicate with one
another. That is, a source computer uses a network to pass data to a
destination computer. The data is typically divided into cells of
information.
Networks originally evolved by relying upon a single link to communicate
between computers. Examples of the single link architecture include
Ethernet networks and Token Ring networks. The problem with a single link
architecture is that it has limited data throughput.
In view of the bandwidth problems of a single link architecture, there is
an increasing interest in arbitrary topology cell-based local area
networks, such as Asynchronous Transfer Mode (ATM) networks. In these
networks, computers are connected together by an arbitrary graph of
communication links and switches. Arbitrary topology networks offer a
number of potential advantages, including: (1) aggregate throughput that
can be much larger than that of a single link, (2) the ability to add
throughput incrementally as the workload changes by simply adding extra
links and switches, (3) improved fault tolerance by allowing redundant
paths between hosts, and (4) reduced latency because control over the
entire network is not needed to insert data.
To realize the potential advantages of arbitrary topology networks, a high
performance switch is needed to take a cell arriving on an input link and
quickly deliver it to the appropriate output link. A switch has three
components: a physical switch, a scheduling mechanism to arbitrate when
cells arrive on different inputs destined for the same output, and a
queuing mechanism at inputs or outputs to hold those cells that lose the
arbitration.
The queuing mechanism is used to store a set of incoming cells. Each
incoming cell contains data and an identifier that indicates which output
it is destined for. In the case of an ATM network, each cell has 48 bytes
of data and 5 bytes of identification information. The physical switch can
be implemented as a crossbar switch which allows any input to be routed to
any output. As known in the art, a crossbar switch may be implemented as a
matrix of transistors.
The construction of the physical switch and queuing mechanism is
straightforward. However, the construction of a scheduling mechanism is
rather complex and represents the performance bottleneck in most high
throughput switches.
It is the job of the scheduling mechanism to identify a conflict-free match
between inputs and the outputs of the switch. That is, the input cells at
the input of the switch must be matched to particular outputs of the
switch. Each input is connected to at most one output and each output is
connected to at most one input.
Ideally, the scheduling mechanism finds the maximum number of matches
between inputs and outputs. The problem with a maximum matching approach
is that it is computationally expensive. In addition, such an approach can
result in a continuously unserviced input-output connection under certain
traffic patterns. Thus, techniques have been developed to achieve a
maximal, not a maximum match. These algorithms iteratively add connections
to fill in the missing connections left by a previous iteration. Because
the connections made in previous iterations may not be removed, this
technique does not always lead to a maximum match. However, it is possible
to achieve a close approximation to the maximum for many traffic patterns.
Parallel Iterative Matching (PIM) is a successful scheduling technique that
is described in U.S. Pat. No. 5,267,235, which is expressly incorporated
by reference herein. PIM uses randomness to avoid starvation (a
continuously unserviced input cell), and to reduce the number of
iterations needed to converge on a maximal matching. PIM attempts to
quickly converge on a conflict-free match in multiple iterations where
each iteration consists of three phases. All inputs and outputs are
initially unmatched and only those inputs and outputs not matched at the
end of one iteration are eligible for matching in the next iteration. The
three phases of each iteration operate in parallel on each output and
input and are as follows:
1. Request. Each unmatched input sends a request to every output for which
it has a queued cell.
2. Grant. If an unmatched output receives any requests, it grants to only
one by randomly selecting a request uniformly over all requests.
3. Accept. If an input receives a grant, it accepts one by selecting an
output among those that granted to this output.
Note that in phase (2) of the PIM scheduling technique the independent
output schedulers randomly select a request among contending requests.
This has three effects: first it can be shown that each iteration will
match or eliminate on average at least 3/4 of the remaining possible
connections and thus the algorithm will converge to a maximal matching in
O(log N) iterations. Second, it ensures that all requests will eventually
be granted. As a result, no input queue remains continuously unserved.
Third, it means that no memory or state is used to keep track of how
recently a connection was made in the past. At the beginning of each cell
time, the match begins over, independently of the matches that were made
in previous cell times. Not only does this simplify understanding of the
algorithm, it also makes analysis of the performance straightforward since
there is no time-varying state to consider, except for the occupancy of
the input queues.
Unfortunately, there are a number of shortcomings associated with the PIM
technique. First, it is difficult and expensive to implement at high speed
because each scheduler must make a random selection among the members of a
varying input set. The varying input set must be ordered in such a manner
that the random selection process is successful. For example, suppose an
input vector can accept ten requests and there is a request at positions
3, 7, and 10. A random selection process may specify positions 1, 2, 4, 5,
6, 8, and 9 before a hit is made at a requesting position. In view of this
situation, the random selection process must be tailored according to the
varying selection set so that the random value selected corresponds to a
filled position. This ordering of data results in substantial
computational overhead. Thus, it would be highly desirable to provide a
scheduling technique with reduced computational overhead.
Another problem with the PIM technique is that it does not perform well for
a single iteration. Although the PIM technique will often converge to a
good match after several iterations, this required convergence time
affects the rate at which the switch can operate. It would be preferable
to provide a technique that converges in a single iteration.
SUMMARY OF THE INVENTION
The invention is a high-bandwidth input-queued switch that includes a set
of input queues, a rotating priority iterative matching desynchronizing
scheduler, and a crossbar switch. Each input queue includes at least one
stored cell with an output device designation signal and a data signal.
Each output device designation signal is processed by the rotating
priority iterative matching desynchronizing scheduler so that the data
signal associated with the output device designation signal is routed
through the crossbar switch to an output device specified by the output
device designation signal. The rotating priority iterative matching
desynchronizing scheduler includes a set of grant scheduler units, each of
which receives a set of device designation signals and generates an input
device grant signal on the basis of a grant scheduler priority designation
signal. The scheduler also includes a set of accept scheduling units, each
of which receives a set of input device grant signals from the grant
scheduling units, and generates a input/output match signal on the basis
of an accept scheduler priority designation signal. Each grant scheduling
unit includes a grant scheduler register that stores the grant scheduler
priority designation signal. The grant scheduler priority designation
signal is incremented when an input device grant signal results in an
input/output match signal at one of the accept scheduler units. Each
accept scheduler unit includes an accept scheduler register that stores
the accept scheduler priority designation signal. The accept scheduler
priority designation signal is incremented when the input/output match
signal is selected.
The scheduler of the invention is relatively easy to implement since each
scheduler relies upon standard components in a straightforward
configuration. In addition, the scheduler provides a highly efficient
technique for processing queued cells. The processing of the cells tends
to be evenly distributed by the scheduler as a result of a desynchronizing
effect between individual scheduling units.
BRIEF DESCRIPTION OF THE DRAWINGS
For a better understanding of the nature and objects of the invention,
reference should be made to the following detailed description taken in
conjunction with the accompanying drawings, in which:
FIG. 1 illustrates an electronic switching environment in which the
rotating priority iterative matching desynchronization apparatus of the
invention may be used.
FIG. 2 illustrates the steps associated with the rotating priority
iterative matching desynchronization method of the invention.
FIG. 3 illustrates four iterations of the processing of the method of FIG.
2.
FIG. 4 illustrates four iterations of a sub-optimal modification to the
processing of the method of FIG. 2.
FIG. 5 illustrates a single iteration of the processing of the method of
FIG. 2.
FIG. 6 is a more detailed representation of one embodiment of the apparatus
of FIG. 1.
FIG. 7 depicts one embodiment of a scheduler that may be used in accordance
with the invention.
FIG. 8 depicts an alternate embodiment of a scheduler that may be used in
accordance with the invention.
FIG. 9 is an alternate embodiment of the rotating priority iterative
matching desynchronization method of the invention.
FIG. 10 is a more detailed representation of an alternate embodiment of the
apparatus of FIG. 1.
Like reference numerals refer to corresponding parts throughout the several
views of the drawings.
DETAILED DESCRIPTION OF THE INVENTION
FIG. 1 is a general illustration of the apparatus of the invention and the
environment in which it is used. A set of computers C.sub.-- 1, C.sub.--
2, . . . , C.sub.-- N are illustrated on both sides of the figure. A set
of input queues Q.sub.-- 1, Q.sub.-- 2, . . . , Q.sub.-- N, a rotating
priority iterative matching desynchronization (RPIMD) scheduler 20, and a
crossbar switch 22 are used to form a network. The network allows each
computer C.sub.-- 1, C.sub.-- 2, . . . , C.sub.-- N to communicate with
every computer on the network. Computers C.sub.-- 1, C.sub.-- 2, . . . ,
C.sub.-- N, input queues Q.sub.-- 1, Q.sub.-- 2, Q.sub.-- N, and crossbar
switch 22 are known in the art. The present invention is directed toward
the RPIMD scheduler 20.
FIG. 2 illustrates the operations associated with the rotating priority
iterative matching desynchronization method of the invention. The first
step associated with the method is to load arriving cells into queues
(block 30). For example, computer C.sub.-- 2 in FIG. 1 loads cells into
queue Q.sub.-- 2. Queue Q.sub.-- 2 includes N input FIFOs (First In First
Out storage devices) 24.sub.-- 1 through 24.sub.-- N. There is one input
FIFO for each output device C.sub.-- 1 through C.sub.-- N. One cell is
delivered to one FIFO during a predetermined cell time slot. The N values
at the front of FIFOs 24.sub.-- 1 through 24.sub.-- N form a request
vector, as will be discussed below.
Each cell includes an output device designation signal and a data signal.
The output device designation signal (a set of bits) specifies the output
device, such as computer C.sub.-- 1. The data signal (a set of bits) is
the information that is passed to computer C.sub.-- 1.
The next step associated with the process of FIG. 2 is to request access to
the specified output devices (block 32). That is, for the N queues
(Q.sub.-- 1 through Q.sub.-- N), all cells existing at the front of a FIFO
(24.sub.-- 1 through 24.sub.-- N in each queue), request access to a
corresponding output device.
After the request for access, access is granted according to the rotating
priority iterative matching desynchronization technique of the invention
(block 34). The processing up to this point is consistent with the
processing associated with the PIM technique, which was discussed in the
background section. However, at this point in the processing, the PIM
technique establishes a grant on the basis of a random selection of the
set of requests. For example, suppose Q.sub.-- I and Q.sub.-- N each have
a single cell destined for computer C.sub.-- 2. Under the PIM technique,
the data to be sent to computer C.sub.-- 2 would be designated by randomly
selecting either the cell from queue Q.sub.-- I or the cell from Q.sub.--
N.
In contrast to the random scheme used in the PIM technique, the present
invention uses a rotating priority scheme. As its name implies, the
rotating priority scheme selects the input request with the highest
priority. Thereafter, the designation of the highest priority is
incremented, causing the highest priority element of the last iteration to
become the lowest priority element in the following iteration. This
results in a rotating priority scheme. For example, at one instance in
time the rotating priority may establish that a request at a third input
vector position is the highest priority. Thus, if a cell from queue
Q.sub.-- 1 is in the third input vector position and a cell from queue
Q.sub.-- 2 is in the fourth input vector position, then the cell from
queue Q.sub.-- 1 would be serviced first. The rotating priority would then
be incremented to the fourth input vector position. Preferably, the
incrementation step is only executed if the grant is subsequently
accepted. As will be described below, this produces a desirable
desynchronization effect between the schedulers.
The next step associated with the method of the invention is to accept
access requests according to the rotating priority iterative matching
desynchronization technique of the invention (block 36). For example,
there may be cells from Q.sub.-- 2 that have requested access to computer
C.sub.-- 1 and cells that have requested access to computer C.sub.-- 2.
Computers C.sub.-- 1 and C.sub.-- 2 may have then granted access requests
to the cells from queue Q.sub.-- 2. The accept step would select either
computer C.sub.-- 1 or C.sub.-- 2. In other words, the accept step
designates a single output from a set of available outputs. The PIM
technique randomly selects an accepted access request. In contrast, the
present invention uses a priority scheme of the type previously described.
After the highest priority element is selected, the priority is
incremented to one value beyond the accepted priority element.
The final processing step is to activate the crossbar switch (block 38).
This results in an accepted cell being transmitted to a destination
computer (C.sub.-- 1, C.sub.-- 2, . . . , C.sub.-- N). The process is then
repeated.
The general principles of the invention have now been described. Attention
will now turn to some examples of the operation of the invention in order
to underscore its efficiencies and benefits. Thereafter, attention will
turn to different options for implementing the invention.
FIG. 3 illustrates four iterations of the processing of FIG. 2. The figure
illustrates a request step corresponding to block 32 of FIG. 2, a grant
step corresponding to block 34 of FIG. 2, and an Accept step corresponding
to block 36 of FIG. 2. In this basic example, the granting of access
(block 34 of FIG. 2) is established by a simple two value rotating
priority scheme. Similarly, the acceptance of an access request (block 36
of FIG. 2) is established by a two value rotating priority scheme.
The processing during iteration 1 begins with an input i.sub.-- 1 (for
instance, the front cell of the first FIFO of Queue.sub.-- l) that
requests access to j.sub.-- 1 and also requests (for instance, the front
cell of the second FIFO of Queue.sub.-- l) access to j.sub.-- 2.
Simultaneous with the request by input i.sub.-- 1, input i.sub.-- 2
requests access to outputs j.sub.-- l and j.sub.-- 2.
After the request phase, processing proceeds to the grant phase. As shown
in the figure, the grant pointers g.sub.-- 1 and g.sub.-- 2 are each set
to 1. In view of this situation, j.sub.-- 1 grants to i.sub.-- 1 and
j.sub.-- 2 does the same, as shown in the figure.
The accept phase is controlled by the accept pointers. Accept pointers
a.sub.-- 1 and a.sub.-- 2 are each set to 1. In the accept phase, i.sub.--
1 must select between j.sub.-- 1 and j.sub.-- 2. Since the pointer
a.sub.-- 1 is set to 1, j.sub.-- 1 is selected, as shown. Now that a
selection has been made, a cell is routed from i.sub.-- 1 to j.sub.-- 1.
Processing then proceeds to a second iteration. Note that during the second
iteration the grant pointer g.sub.-- 1 has a value of 2 because j.sub.-- 1
was accepted during the processing in iteration 1, causing an
incrementation of the grant pointer g.sub.-- 1 during iteration 1. On the
other hand, j.sub.-- 2 was not accepted and therefore the grant pointer
g.sub.-- 2 remained set at 1. Similarly, accept pointer a.sub.-- 1 was
incremented to a value of 2 during iteration 1, but accept pointer
a.sub.-- 2 remained at a value of 1.
The request phase for iteration 2 is the same as the request phase for
iteration 1. In the grant phase for iteration 2, j.sub.-- 1 grants to
i.sub.-- 2, while j.sub.-- 2 grants to i.sub.-- 1. This is done because
grant pointer g.sub.-- 1 is set to a value of 2, while grant pointer
g.sub.-- 2 is set to a value of 1.
In the accept phase of iteration 2, i.sub.-- 1 accepts j.sub.-- 2, and
i.sub.-- 2 accepts j.sub.-- 1. Again, this result follows because accept
pointer a.sub.-- 1 is set to a value of 2, and accept pointer a 2 is set
to a value of 1.
The desynchronization aspect of the present invention should be noted at
this time by referring to FIG. 4. Note in FIG. 4 that the processing of
iteration 1 is the same as shown in FIG. 3. On the other hand, the
processing of iteration 2 is different because both grant pointers in
iteration 2 of FIG. 4 were incremented automatically. In contrast, in FIG.
3, only grant pointer g.sub.-- 1 was incremented because j.sub.-- 1 was
accepted in the previous accept phase. The desynchronization of grant
values leads to high processing efficiency.
Note in FIG. 4 that in the grant phase of iteration 2, both outputs
j.sub.-- 1 and j.sub.-- 2 grant to input i.sub.-- 2, whereas in FIG. 3
outputs j.sub.-- 1 and j.sub.-- 2 respectively grant to i.sub.-- 2 and
i.sub.-- 1. As can be seen in the figures, this results in two acceptances
in the accept phase of the desynchronized grant values in FIG. 3, but only
one acceptance in the accept phase of the synchronized grant values of
FIG. 4.
In view of this example, a number of general observations may be made. When
a requesting input is granted (say i.sub.-- 1 of cell 1 of FIG. 3), that
input will have the lowest priority at the assigned output in a subsequent
cycle (note in cell 2 of FIG. 3 that input i.sub.-- 1 is assigned to
j.sub.-- 2). Also, whatever input has the highest priority at an output
will continue to be granted during each successive iteration until it is
serviced. For example, in the grant phase of iteration 2 of FIG. 3, input
i.sub.-- 1 is the highest priority, and thus will continuously be granted
until it is accepted and the pointer g.sub.-- 2 is incremented.
It should also be noted that in the desynchronized technique of FIG. 3,
contention between granting outputs is avoided. Note that in the
processing of iteration 1, both outputs J.sub.-- 1 and j.sub.-- 2 granted
to input i.sub.-- 1. In the processing of iteration 2, output j.sub.-- 2
once again grants to input i.sub.-- 1. However, since grant pointer
g.sub.-- 1 was incremented, input i.sub.-- 1 is a low priority for output
j.sub.-- 1, consequently, output j.sub.-- 1 selects input i.sub.-- 1. Note
in FIG. 4 that in the processing of iteration 2, the two outputs still
contend, as they both attempt to grant to input i.sub.-- 2.
Completing now the example of FIG. 3, iteration 3 is processed as follows.
Since both inputs were served in iteration 2, both grant pointers are
incremented in iteration 3. Similarly, both accept pointers are
incremented. The requests of iteration 3 are the same as the requests of
iterations 1 and 2. In view of the position of the grant pointers, output
j.sub.-- 1 grants to input i.sub.-- 1, and output j.sub.-- 2 grants to
input i.sub.-- 2. The accept pointers establish that input i.sub.-- 1
accepts output j.sub.-- 1, while input i.sub.-- 2 accepts output j.sub.--
2. Thus, all inputs and outputs are served. This stands in contrast to the
processing in FIG. 4, where the grant phase contends for input i.sub.-- 1,
and only one input is served.
The processing of iteration 4 in FIG. 3 is the same as the processing of
iteration 2 in FIG. 3. The processing of iteration 4 in FIG. 4 once again
underscores the conflicting grant operations and the result inefficiency
as only one input is served at the accept phase.
FIG. 5 further illustrates the invention by depicting input cells i.sub.--
1 through i.sub.-- 4 from corresponding input queues. The accept and grant
pointers are all set to a value of 1. In the grant phase, outputs j.sub.--
1 and j.sub.-- 2 each grant to input i.sub.-- 1. Output j.sub.-- 3 grants
to input i.sub.-- 3. This is the only request, and therefore the grant
pointer does not have to be used. Similarly, output j.sub.-- 4 grants to
input i.sub.-- 3 because it is the only request. At the accept stage,
input i.sub.-- 1 selects j.sub.-- 1, as specified by its corresponding
accept pointer a.sub.-- 1, which is set to 1. Input i.sub.-- 3 selects
j.sub.-- 3 from the options of j.sub.-- 3 and j.sub.-- 4. That is, the
option closest to the specified pointer value is selected. The a.sub.-- 3
accept pointer is then incremented to a value of 4, one beyond the
accepted value. Accept pointer a.sub.-- 1 will also be incremented by 1
and grant pointers g.sub.-- 1 and g.sub.-- 3 will be incremented by 1
because of the match in the accept stage.
The methodology of the invention has now been fully described. Attention
presently turns to different approaches to implementing the methodology of
the invention. FIG. 6 illustrates one embodiment of a rotating priority
iterative matching desynchronization scheduler in accordance with the
invention. The figure illustrates input queues Q.sub.-- 1, Q.sub.-- 2, . .
. , Q.sub.-- N. The destination information of the first cell of each
input queue is routed by a request delivery circuit 60 to a set of grant
scheduler 62 including a set of grant scheduler units GSU.sub.-- 1,
GSU.sub.-- 2, GSU.sub.-- N. A grant scheduler unit exists for every output
device to be accessed. Thus, if the outputs are computers, a grant
scheduler is provided for each computer on the network. The request
delivery circuit merely needs to route each queued input request to a
specified grant scheduler.
The output signals from the grant schedulers (granted requests, or selected
input device grant signals) are routed to a grant delivery circuit 64. The
grant delivery circuit 64 routes the output signals to an acceptance
scheduler 66 including a set of acceptance scheduler units ASU.sub.-- 1,
ASU.sub.-- 2, . . . , ASU.sub.-- N. The output signals from the acceptance
scheduler units (accepted matches between inputs and outputs, input/output
match signals) are delivered to crossbar switch 22, which makes the
required connections between the selected inputs and the selected outputs.
The operation and control of a crossbar switch is known in the art.
FIG. 7 illustrates one embodiment of a grant scheduler unit that may be
used in accordance with the invention. Requests are received at a request
vector register 70. The request vector register 70 is N bits long, where N
corresponds to the number of input devices (for instance, computers) on
the network. Thus, there is a bit for each input device and its
corresponding grant scheduler. In the example of FIG. 7, the second,
third, fifth, and Nth bits are set to one, indicating that the second,
third, fifth, and Nth input devices are requesting a grant. The second,
third, fifth, and Nth input bits may be referred to as output device
designation signals.
The request vector register 70 is connected to a priority encoder 72. As is
known in the art, a priority encoder 72 selects as an output, an input
value, as specified by another input signal, in this case a signal from a
grant pointer register 74. Suppose the grant pointer register 74 stores a
value of 3 corresponding to the third position of the request vector
register 70. In this case, the output of the priority encoder 72 would be
the value 3. There are log.sub.2 (N) priority encoder output lines. For
example, if N equals sixteen, then there would be four output lines. Thus,
in this example, the output lines would be set as 0011 (binary 3),
indicating request vector position 3. The output of the priority encoder
may be referred to as a device grant signal.
The logic of the priority encoder 72 only selects a set request vector
register value. For example, if the value in the grant pointer register 74
was 4, then the priority encoder 72 would select the fifth value in the
request vector register 70, because the fourth value is not set (digital
low).
The output value of the priority encoder 72, the device grant signal, is
incremented (modulo N) by incrementer 76. The results of the addition are
stored in an incremented grant value register 77. The value in the
incremented grant value register 77 is written to the grant pointer
register 74, in response to an acceptance feedback signal. Returning to
FIG. 6, it can be seen that N.sup.2 lines (N scheduling units.times.N
lines for each scheduling unit) leave the accept scheduler 66
An acceptance feedback bus 68 is formed from the N lines designating each
scheduling unit. As shown in FIG. 6, the acceptance feedback bus 68
terminates in an acceptance line 69.sub.-- 1, 69.sub.-- 2, . . . ,
69.sub.-- N being attached to each grant scheduler unit. More
particularly, each acceptance line serves as an enable signal for the
incremented grant value register 77, forcing the contents of the register
into the grant scheduler register 74.
Returning to FIG. 7, the output value of the priority encoder 72 is also
conveyed to a decoder 78, a known device. The decoder has N output lines,
one of which will be set high in response to the output from the priority
encoder 72. Relying upon the previous example wherein the priority encoder
selected the fifth value in the request vector, the decoder would
interpret this binary input value (0101) and set its fifth output line
high and the remaining outputs low. Thus, the fifth output device will
have been granted.
An acceptance scheduler can be implemented using the same components. In
the case of an acceptance scheduler, the request vector register 70 would
store received input device grant signals that have been provided for a
given input. The acceptance scheduler would then select a given grant
using an acceptance scheduler priority designation register that stores an
accept scheduler priority designation signal, in a manner consistent with
the device of FIG. 7. The incremented grant value register would be
substituted with an incremented accept value register. The incremented
accept value register would be enabled by a decoder feedback line, as will
be shown below.
Those skilled in the art will appreciate that the schedulers of the present
invention are simple to implement in view of the fact that they rely upon
standard components arranged in a straightforward configuration. Since the
schedulers of the invention do not have to order the input values in a
request vector, as required to implement the PIM technique, they provide
an improvement over the schedulers of the PIM technology.
FIG. 8 is an alternate embodiment of the invention wherein a combined
scheduler unit 90 is used for both granting and accepting requests at a
request vector 70. The combined scheduler unit 90 is the same as the grant
scheduler unit of FIG. 7 except that it includes an incremented accept
value register 81, an accept scheduler priority designation register 82,
and select logic 86 to select either the value in register 74 or the value
in register 82. FIG. 8 also illustrates a logic OR gate 84 whose inputs
are connected to each of the decoder 78 output lines. During an acceptance
phase, the select logic 86 places an enable signal on line 87 for OR gate
84. As a result, if any input to the OR gate is high, then the output of
the OR gate is high, causing the incremented value in the incremented
accept designation register 81 to be loaded into accept register 82.
FIG. 9 illustrates an alternate embodiment of the methodology of the
invention. In general, the method is consistent with the method described
in relation to FIG. 2. However, the method of FIG. 2 assumed that only a
single iteration (the request, grant, and access phases) could be
performed during a cell time slot (the time between activation of the
crossbar switch 22). Generally, it is possible to perform a sequence of
iterations during a cell time slot. Thus, the method of FIG. 9 tests to
determine whether the end of a time slot has been reached or is within a
threshold range of termination (block 100). If so, the crossbar switch is
activated (block 38). If not, committed scheduling units are disabled and
another processing iteration is performed (block 102). In other words, if
a scheduling unit has derived an input/output match signal, then it is not
enabled during a subsequent iteration. As a result, only those scheduling
units that did not derive an input/output match signal are processed in a
subsequent iteration.
FIG. 10 illustrates an apparatus that can be used to execute the method of
FIG. 9. The apparatus of FIG. 10 utilizes combined scheduler units
90.sub.-- A, 90.sub.-- b, . . . , 90.sub.-- N, of the type shown in FIG.
8. In this embodiment, queued values of the type previously described are
routed to a multiplexer 110. The scheduler units 90 receive the queued
values from the multiplexer 110. In the grant phase, the grant register 74
of each scheduler unit 90 is used. The outputs from the grant phase are
routed by a routing circuit 112. The output of the routing circuit 112 can
be stored in a decision register bank 114. The values in the decision
register bank 114 are then fedback to the multiplexer 110. The schedulers
90 then process the fedback values, relying upon the acceptance register
82. If this processing results in an acceptance at a particular scheduler
unit 90, then the acceptance register 82 value is incremented in a manner
previously described. As shown in FIG. 8, the output signal from the OR
gate 84 may be used to disable the select logic 86. As a result, the
select logic does not select a priority value and no processing takes
place at the scheduling unit during subsequent iterations, effectively
removing a scheduling unit once a match has been made. After subsequent
iterations are processed in a given time slot, the crossbar switch 22 is
activated and all scheduled inputs are delivered to their designated
output device.
The basic techniques of the invention can be extended to include requests
at multiple priority levels with only a | | |
