Dynamic circular work-stealing deque

Details Dynamic circular work-stealing deque Dynamic circular work-stealing deque

2008-03-18

2008-03-18

Kim, Matthew (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Memory configuring

C711S153000, C710S056000, C718S104000

Reexamination Certificate

active

07346753

ABSTRACT:
A deque of a local process in a memory work-stealing implementation may use one or more data structures to perform work. If the local process attempts to add a new value to its deque's circular array when the data structure is full (i.e., an overflow condition occurs), the contents of the data structure are copied to a larger allocated circular array (e.g., a circular array of greater size than the original circular array). The entries in the original, smaller-sized circular array are copied to positions in the now-active, larger-sized circular array, and the system is configured to work with the newly activated circular array. By this technique, the local process is thus provided with space to add the new value.

REFERENCES:
patent: 6145061 (2000-11-01), Garcia et al.
patent: 6401147 (2002-06-01), Sang et al.
patent: 6560619 (2003-05-01), Flood et al.
patent: 6782461 (2004-08-01), Lam
patent: 6823351 (2004-11-01), Flood et al.
patent: 2001/0056420 (2001-12-01), Steele et al.
patent: 2003/0005025 (2003-01-01), Shavit et al.
patent: 2004/0015510 (2004-01-01), Moir et al.
patent: 2004/0052135 (2004-03-01), Le
patent: 2004/0088702 (2004-05-01), Garthwaite et al.
“The Performance of Work Stealing in Multiprogramming Environments” Robert D. Blumofe and Dionisios Papadopoulos, Department of Computer Sciences, The University of Texas at Austin, May 28, 1998.
Arora, et al.; “Thread Scheduling for Multiprogrammed Multiprocessors”; Proceedings of the 10thAnnual ACM Symposium on Parallel Algorithms and Architectures (SPAA), Jun. 1998 (11 pages).

Affiliated with

Also associated with

Rating

Dynamic circular work-stealing deque does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Dynamic circular work-stealing deque, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic circular work-stealing deque will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2784057