Conditional carry scheduler for round robin scheduling

Details Conditional carry scheduler for round robin scheduling Conditional carry scheduler for round robin scheduling

1992-12-30

1994-10-18

Olms, Douglas W.

Multiplex communications

Wide area network

Packet switching

3642426, 395725, 370 8511, H04L 1240, G06F 1300

Patent

active

053575121

ABSTRACT:
A conditional carry scheduling unit that performs a scheduler carry operation for a round robin scheduler that schedules communication among a plurality of clients who compete to use a shared resource. Each client asserts a request bit to request use of the shared resource, and receives a grant bit from the round robin scheduler that is asserted when the client is scheduled to use the shared resource. The conditional carry scheduling unit includes a plurality of 2-bit carry generation units that operate in parallel. Within each of the 2-bit carry generation units except the initial carry generation unit, two conditional output signals are produced and supplied to a multiplexer tree. The initial carry generation unit assumes a carryin bit of zero, and outputs its carryout bit to the multiplexer tree which determines the actual carries and supplies them back to the carry generation units. Each carry generation unit includes a second multiplexer tree to select the carryout bits (the "SC result bits") from each bit position. If the carryout bit from the final carry generation unit is zero, then the SC result bits for the initial operation provide the grant word for the current scheduling cycle, but if the carryout bit is one, the above scheduler carry operation is repeated assuming a carryin bit of one. To increase speed of operation, parallel branches may be provided, so that two scheduler carry operations can be performed in parallel and the correct grant word selected after the carryout bit is known.

REFERENCES:
patent: 4375639 (1983-03-01), Johnson, Jr.
patent: 4449183 (1984-05-01), Flahive et al.
patent: 4499538 (1985-02-01), Finger et al.
patent: 4536839 (1985-08-01), Shah et al.
patent: 4669079 (1987-05-01), Blum
patent: 4763122 (1988-08-01), Franaszek
patent: 4924380 (1990-05-01), McKinney et al.
patent: 4964034 (1990-10-01), Jaskowiak
patent: 5072363 (1991-12-01), Gallagher
patent: 5179705 (1993-01-01), Kent
patent: 5276635 (1994-01-01), Naini et al.
Bertsekas, Dimitri and Gallager, Robert, "Data Networks", Prentice-Hall, Inc., 1987, pp. 258-270.
Haldar, S. and Subramanian, D. K., "Fairness in Processor Scheduling in Time Sharing Systems", pp. 4-18.
Hennessy, John L., and Patterson, David A., "Computer Architecture A Quantitative Approach", Morgan Kaufman Publishers, Inc., 1990, pp. A-2 through A-3, A31-A39.
Lee, K. C., "A Variable Round-Robin Arbiter for High Speed Buses and Statistical Multiplexers", IEEE, 1991, pp. 24-29.
Sharma, D. K. and Ahuja, S. R., "A First-Come First-Serve Bus-Allocation Scheme Using Ticket Assignments", The Bell System Technical Journal, vol. 60, No. 7, Sep. 1981, pp. 1257-1269.
Vernon, Mary K. and Manber, Udi, "Distributed Round-Robin and First-Come First-Serve Protocols and their Application to Multiprocessor Bus Arbitration", SCIC, Mar. 1988, pp. 10-18.

Affiliated with

Also associated with

Rating

Conditional carry scheduler for round robin scheduling does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Conditional carry scheduler for round robin scheduling, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Conditional carry scheduler for round robin scheduling will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2378095