Distributed least choice first arbiter

Details Distributed least choice first arbiter Distributed least choice first arbiter

2006-02-28

2006-02-28

Kizou, Hassan (Department: 2662)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S462000

Reexamination Certificate

active

07006501

ABSTRACT:
A distributed arbiter prioritizes requests for resources based on the number of requests made by each requester. Each resource gives the highest priority to servicing requests made by the requester that has made the fewest number of requests. That is, the requester with the fewest requests (least number of choices) is chosen first. Resources may be scheduled sequentially or in parallel. If a requester receives multiple grants from resources, the requester may select a grant based on resource priority, which is inversely related to the number of requests received by a granting resource. In order to prevent starvation, a round robin scheme may be used to allocate a resource to a requester, prior to issuing grants based on requester priority.

REFERENCES:
patent: 3676846 (1972-07-01), Busch
patent: 4648029 (1987-03-01), Cooper et al.
patent: 4760521 (1988-07-01), Rehwald et al.
patent: 5301279 (1994-04-01), Riley et al.
patent: 5550815 (1996-08-01), Cloonan et al.
patent: 5560016 (1996-09-01), Fiebrich et al.
patent: 5564062 (1996-10-01), Meaney et al.
patent: 5577035 (1996-11-01), Hayter et al.
patent: 5617575 (1997-04-01), Sakakibara et al.
patent: 5742594 (1998-04-01), Natarajan
patent: 5821875 (1998-10-01), Lee et al.
patent: 5835491 (1998-11-01), Davis et al.
patent: 6023732 (2000-02-01), Moh et al.
patent: 6029217 (2000-02-01), Arimilli et al.
patent: 6069573 (2000-05-01), Clark et al.
patent: 6072772 (2000-06-01), Charny et al.
patent: 6111886 (2000-08-01), Stewart
patent: 6160812 (2000-12-01), Bauman et al.
patent: 6370148 (2002-04-01), Calvignac et al.
patent: 6449283 (2002-09-01), Chao et al.
patent: 6473103 (2002-10-01), Bailey et al.
patent: 6487213 (2002-11-01), Chao
patent: 6570873 (2003-05-01), Isoyama et al.
patent: 6580720 (2003-06-01), Francis et al.
patent: 6667955 (2003-12-01), Blanc et al.
patent: 0 463 943 (1992-01-01), None
patent: 0 868 054 (1998-09-01), None
patent: 1 096 387 (2001-05-01), None
patent: WO 00/29956 (2000-05-01), None
Chun, Mainwaring et al., “Virtual Network Transport Protocols for Myrinet”, Computer Science Division University of California at Berkeley, Aug. 20, 1997, pp. 1-14.
Scott, Steven L., “Synchronization and Communication in the T3E Multiprocessor”, Cray Research, Inc., 1996, pp. 26-36.
Mainwaring and Culler, “Active Message Applications Programming Interface and Communication Subsystem Organization”, Draft Technical Report, Computer Science Division University of California at Berkeley, Technical Report UCB CSD-96-918, Oct. 1996, pp. 1-45.
Kai Y. Eng, Michael G. Hluchyj, and Yu-Shuan Yeh, “A Knockout Switch for Variable-Length Packets,” IEEE Journal on Selected Areas in Communications, vol. SAC-5, No. 9, Dec., 1987, pp. 1426-1435.
Martin Collier and Tommy Curran, “Path Allocation in a Three-Stage Broadband Switch with Intermediate Channel Grouping,” INFOCOM '93, Proceedings Twelfth Annual Joint Conference of the IEEE Computer and Communications Societies, Networking: Foundation for the Future, IEEE, vol. 3, Mar. 28-Apr. 1, 1993, pp. 927-934.
Martin Collier and Tommy Curran, “Cell-Level Path Allocation in a Three-Stage ATM Switch,” Communications, 1994, iCC 94, SUPERCOMM/ICC '94, Conference Record, Conference on Serving Humanity Through Communications, IEEE International, vol. 2, May 1-5, 1994, pp. 1179-1183.
Boden, Cohen et al., “Myrinet: A Gigabit-per-Second Local Area Network”, IEEE 1995, pp. 29-36.
Tamir and Chi, “Symmetric Crossbar Arbiters for VLSI Communication Switches”, IEEE Transactions on Parallel and Distributed Systems, vol. 4, No. 1, 1993, pp. 13-27.
Kronenberg, Levy et al., “VAXclusters: A Closely-Coupled Distributed System”, ACM Transactions on Computer Systems, vol. 4, No. 2, May 1986, pp. 130-146.
Dally, William J., “Virtual-Channel Flow Control”, IEEE 1990, pp. 60-68.
Chun, Mainwaring et al., “Virtual Network Transport Protocols for Myrinet”, IEEE vol. 18, No. 1, 1998, pp. 52-63.
Pakin, Kararncheti et al., “Fast Messages: Efficient, Portable Communication for Workstation Clusters and MPPs”, IEEE 1997, pp. 60-73.
Karol, Hluchyj et al., “Input Versus Output Queueing on a Space-Division Packet Switch”, IEEE 1987, pp. 1347-1356.
Scott and Thorson, “The Cray T3E Network: Adaptive Routing in a High Performance 3D Torus”, HOT Interconnects IV, Stanford University, Aug. 15-16, 1996, pp. 1-10.
Mainwaring and Culler, “Design Challenges of Virtual Networks: Fast, General-Purpose Communication”, ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPOPP), Atlanta, GA, May 4-6, 1999.
Sun Microsystems, Inc., “The Sun Enterprise Cluster Architecture Technical White Paper”, 1997, pp. 1-74.
IBM, “JES2 Introduction”, Document No. GC28-1794-02, Third Edition, 1997, pp. 1-51.
ANSI, “Information Technology—Scheduled Transfer Protocol (ST)”, T11.1/Project 1245-D/Rev. 3.6, Jan. 31, 2000, pp. 1-97.

Affiliated with

Also associated with

Rating

Distributed least choice first arbiter does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Distributed least choice first arbiter, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed least choice first arbiter will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3651902