Load-balancing queues employing LIFO/FIFO work stealing

Details Load-balancing queues employing LIFO/FIFO work stealing Load-balancing queues employing LIFO/FIFO work stealing

2006-09-05

2006-09-05

An, Meng-Al T. (Department: 2195)

Electrical computers and digital processing systems: virtual mac

Task management or control

Process scheduling

C710S200000

Reexamination Certificate

active

07103887

ABSTRACT:
In response to source code that represents instructions for dynamically allocating memory to objects, a compiler/interpreter produces instructions that implement a garbage collector. The garbage collector operates in garbage-collection cycles, which include parallel-execution operations such as locating reachable objects. Each thread maintains a respective task queue onto which it pushes identifiers of objects thus found and from which it pops those identifiers in order to begin the tasks of locating the further objects to which objects specified by the thus-popped identifiers refer. A thread's access to its respective task queue ordinarily occurs on a last-in, first-out basis, but the access mode switches to a first-in, first-out basis if the number of task-queue entries exceeds a predetermined threshold.

REFERENCES:
patent: 4482956 (1984-11-01), Tallman
patent: 4584640 (1986-04-01), MacGregor et al.
patent: 4775932 (1988-10-01), Oxley et al.
patent: 4912629 (1990-03-01), Shuler, Jr.
patent: 4989134 (1991-01-01), Shaw
patent: 5088036 (1992-02-01), Ellis et al.
patent: 5241673 (1993-08-01), Schelvis
patent: 5274804 (1993-12-01), Jackson et al.
patent: 5355483 (1994-10-01), Serlet
patent: 5410722 (1995-04-01), Cornaby
patent: 5446901 (1995-08-01), Owicki et al.
patent: 5577246 (1996-11-01), Priddy et al.
patent: 5692185 (1997-11-01), Nilsen et al.
patent: 5692193 (1997-11-01), Jagannathan et al.
patent: 5893121 (1999-04-01), Ebrahim et al.
patent: 5930807 (1999-07-01), Ebrahim et al.
patent: 5950205 (1999-09-01), Aviani, Jr.
patent: 6047295 (2000-04-01), Endicott et al.
patent: 6052699 (2000-04-01), Huelsbergen et al.
patent: 6081665 (2000-06-01), Nilson et al.
patent: 6192517 (2001-02-01), Agesen et al.
patent: 6226653 (2001-05-01), Alpern et al.
patent: 6240422 (2001-05-01), Atkins et al.
patent: 6249793 (2001-06-01), Printezis et al.
patent: 6253215 (2001-06-01), Agesen et al.
patent: 6286016 (2001-09-01), Heller et al.
patent: 6289360 (2001-09-01), Kolodner et al.
patent: 6304949 (2001-10-01), Houldsworth
patent: 6314436 (2001-11-01), Houldsworth
patent: 6314478 (2001-11-01), Etcheverry
patent: 6317756 (2001-11-01), Kolodner et al.
patent: 6321240 (2001-11-01), Chilimbi et al.
patent: 6338073 (2002-01-01), Houldsworth et al.
patent: 6341293 (2002-01-01), Hennessey
patent: 6374339 (2002-04-01), Iivonen
patent: 6377984 (2002-04-01), Najork et al.
patent: 6381735 (2002-04-01), Hunt
patent: 6411964 (2002-06-01), Iyer et al.
patent: 6415302 (2002-07-01), Garthwaite et al.
patent: 6427154 (2002-07-01), Kolodner et al.
patent: 6434575 (2002-08-01), Berry et al.
patent: 6480862 (2002-11-01), Gall
patent: 6493730 (2002-12-01), Lewis et al.
patent: 6526422 (2003-02-01), Flood et al.
patent: 6542911 (2003-04-01), Chakraborty et al.
patent: 6560619 (2003-05-01), Flood et al.
patent: 6571260 (2003-05-01), Morris
patent: 6651101 (2003-11-01), Gai et al.
patent: 6671707 (2003-12-01), Hudson et al.
patent: 6763452 (2004-07-01), Hohensee et al.
patent: 2001/0000821 (2001-05-01), Kolodner et al.
patent: 2001/0047361 (2001-11-01), Martin et al.
patent: 2001/0049726 (2001-12-01), Comeau et al.
patent: 2002/0052926 (2002-05-01), Bush et al.
patent: 2002/0073103 (2002-06-01), Bottomley et al.
patent: 2002/0095453 (2002-07-01), Steensgaard
patent: 2003/0005025 (2003-01-01), Shavit et al.
patent: 2003/0005029 (2003-01-01), Shavit et al.
patent: 2004/0088702 (2004-05-01), Garthwaite et al.
Leslie Lamport, Providing the Correctness of Multiprocess Programs, IEEE Transaction on Software Engineering, vol. SE-3, No. 2, Mar. 1977, pp. 125-143.
Adity, et al., “Garbage Collection for Strongly-Typed Languages using Run-Time Reconstruction”, ACM, 1994, 16-20.
Appel, “Simple Generational Garbage Collection and Fast Allocation”, Software Practice and Experience, 19(2), 1989, 171-183.
Arora, et al., “Thread Scheduling for Multiprogrammed Multiprocessors”, Dept. of Computer Science, Uni. of Texas, 1998, Austin.
Baker, “List Processing in Real Time on a Serial Computer”, Communications of the ACM 21, Apr. 1978, 280-294.
Bibolet, et al., “Asynchronous Service Routine Invocation with Safely Serialized Work Queue”, IBM Tech. Disclosure Bulletin, vol. 25, No. 8, Jan. 1983, IBM Corp.
Blelloch, et al., “On Bounding Time and Space for Multiprocessor Garbage Collection”, Computer Science Department, Carnegie Mellon University, date unknown.
Blumofe, “Scheduling Multithreaded Computations by Work Stealing”, University of Texas, 1998, Austin.
Boehm, “Simple Garbage Collector-Safety”, ACM, May 1996, 89-98.
Chase, et al., “Analysis of Pointers and Structures”, Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, Jun. 20-22, 1990, 296-310, White Plains, NY.
Cohen, “Garbage Collection of Linked Data Structures”, ACM, Computing Surveys, vol. 13, No. 3, Sep. 1981, 341-367.
Courtemanche, “MultiTrash, a Parallel Garbage Collector for MultiScheme”, Thesis for MIT, 1986.
Courts, “Improving Locality of Reference in a Garbage-Collecting Memory Management System”, Communications of the ACM, vol. 31, No. 9, Sep. 1988, 1128-1138.
Craig, et al., “nanoPortean: Scalable System Software for a Gigabit Active Router”, IEEE INFOCOM 2001, 2001, 51-59.
Demers,e t al., “Combining Generational and Conservative Garbage Collection: Framework and Implementations”, In Conf. Rec. of 17th Annual ACM Symposium, Jan. 1990, 261-269, ACM Notices.
Doligez, et al., “Portable Unobtrusive Garbage Collection for Multiprocessor Systems”, Association forComputing Machinery, 1994.
Endo, T., et al., “A Scalable Mark-Sweep Garbage Collector on Large-Scale Shared-Memory Machines”, Proceedings of the 1997 ACM/IEEE Supercomputing 97 Conference, Nov. 15-21, 1997, San Jose, CA.
Halstead, “Implementation of Multilisp: Lisp on a Multiprocessor”, MIT, Lab. for Computer Science, 1984, Cambridge.
Hickey, et al., “Performance Analysis of On-the-Fly Garbage Collection”, Communication of the ACM, vol. 27, No. 11, Nov. 1984, 1143-1154.
Holzle, Urs, “A Fast Write Barrier for Generational Garbage Collectors”, Workshop on Garbage Collection in Object Oriented Systems, Oct. 1993.
Hudak, et al., “Garbage Collection and Task Deletion in Distributed Applicative Processing Systems”, ACM, 1982, 168-178.
Ichiyoshi, et al., “A Shared-Memory Parallel Extension of KLIX and Its Garbage Collection”, Proceedings of GCS '94 Workshop on Parallel Logic Programming, 1994, 113-126.
Jones and Lins, “Garbage Collection: Algorithms for Automatic Dynamic Memory Management”, 1996, 165-179, John Wiley and Sons, NY.
Karlsson, “Resume of Martin Karlsson, Internet Document, Online!, p. 1, line 22; line 27”, <http://user.it.uu.se/(martink/> Retrieved on Oct. 30, 2002, May-Aug. 1999.
Massalin, et al., “A Lock-Free Multiprocessor OS Kernel, Dept. of Computer Science”, Columbia University Technical Report No. CUCS-005-91, Jun. 19, 1991.
Moon, “Garbage Collection in a Large Lisp System”, Conference Record of the 1984 ACM Symposium on LISP and Functional Programming, Aug. 1984, 235-246, Austin, TX.
Patel, et al., “A Model Completion Queue Mechanisms Using the Virtual Interface API”, IEEE, 2000, 280-288.
Revesz, “Parallel Graph-Reduction With a Shared Memory Multiprocessor System”, Proceedings of the International Conference on Computer Languages, Mar. 1990, New Orleans, LA.
Rudalics, “Distributed Copying Garbage Collection”, ACM, 1986, 364-372.
Valois, “Lock-Free Data Structures, Internet Document: Doctor of Philosophy/Thesis, Online!, p. 27, line 13”, .cs.rpi.edu/pub/caloisj/thesis.ps.gz, May 1995.
Washabaugh, et al., “Incremental Garbage Collection of Concurrent Objects”, IEEE, 1990, 21-30.
Wilson, “Uniprocessor Garbage Collection Techniques

Affiliated with

Also associated with

Rating

Load-balancing queues employing LIFO/FIFO work stealing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Load-balancing queues employing LIFO/FIFO work stealing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Load-balancing queues employing LIFO/FIFO work stealing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3538189