Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
2005-07-12
2010-08-03
An, Meng-Ai (Department: 2195)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C718S104000, C707S999007, C710S200000, C717S100000, C717S158000, C711S145000, C711S149000
Reexamination Certificate
active
07770170
ABSTRACT:
A blocking local sense synchronization barrier is provided. The local sense variable is not processor private or global, but truly local to the synchronization barrier function. Safe deletion is provided by making sure the last operation a thread performs on a barrier is a write. Just before returning, threads increment a field that indicates the count of threads that have left the barrier. Blocking is supported such that threads spin for some interval, and when they decide to block, examine and set (if not already set) the indication of whether a thread is blocking that is to be examined by the last thread to arrive at the barrier to determine whether to set an event to release blocking threads.
REFERENCES:
patent: 5434995 (1995-07-01), Oberlin et al.
patent: 5442758 (1995-08-01), Slingwine et al.
patent: 5787272 (1998-07-01), Gupta et al.
patent: 6112222 (2000-08-01), Govindaraju et al.
patent: 6117181 (2000-09-01), Dearth et al.
patent: 6216174 (2001-04-01), Scott et al.
patent: 6223335 (2001-04-01), Cartwright et al.
patent: 6263406 (2001-07-01), Uwano et al.
patent: 6345242 (2002-02-01), Dearth et al.
patent: 6549881 (2003-04-01), Dearth et al.
patent: 6718484 (2004-04-01), Kodera
patent: 6785888 (2004-08-01), McKenney et al.
patent: 6854108 (2005-02-01), Choi
patent: 7058945 (2006-06-01), Ichinose et al.
patent: 7228545 (2007-06-01), Circenis et al.
patent: 7376744 (2008-05-01), Loaiza et al.
patent: 7487501 (2009-02-01), Silvera et al.
patent: 7512950 (2009-03-01), Marejka
patent: 7571439 (2009-08-01), Rabinovici et al.
patent: 2004/0093477 (2004-05-01), Oberdorfer
patent: 2004/0139439 (2004-07-01), Machida et al.
patent: 2004/0187118 (2004-09-01), Blainey et al.
patent: 2004/0215898 (2004-10-01), Arimilli et al.
patent: 2005/0050374 (2005-03-01), Nakamura et al.
patent: WO 99/26148 (1999-08-01), None
Zhang et al., “Busy-Wait Barrier Synchronization Using Distributed Counters With Local Sensor”, Springer-Verlag, 2003, pp. 84-98.
Domani et al., “Thread-Local Heaps for Java”, ACM, 2002, pp. 76-87.
Ball et al., “Barrier Synchronization in Java”, UKHEC Technical Report, 2003, pp. 1-30.
Anderson, T.E., “The performance of spin lock alternatives for shared-memory multiprocessors,”IEEE Transactions on Parallel and Distributed Systems, 1990, 1(1).
Ball, C., et al., “Barrier Synchronisation in Java,” ukhec.ac.uk/publications/reports/synch—java.pdf, downloaded Aug. 23, 2005, 25 pages.
Cohen, W.E., et al., Dynamic Barrier Architecture for Multi-Mode Fine-Mode Fine-Grain Parallelism using Conventional Processors: Part I: Barrier Architecture, aggregate.org/TechPub/TREE94—9/tree94—9.html, downloaded Aug. 23, 2005, 18 pages.
Han, H., et al., “Eliminating Barrier Synchronization for Compiler-Parallelized Codes on Software DSMs,” arcs.kaist.ac.kr/papers/ijpp98.pdf, downloaded Aug. 23, 2005, 19 pages.
Herlihy, M., et al., “Introduction to Multiprocessors: algorithms, data structures, and programming,” cs.brown.edu/courses/cs176/barrier.pdf, Nov. 17, 2003,Chapter 11, 203-212 and 249-252.
Kontothanassis, L., et al., “Using scheduler information to achieve optimal barrier synchronization performance,”ACM SIGPLAN Notices, Proceedings of the 4thACM SIGPLAN Symposium on Principles and Practice of parallel programming, delivery.acm.org/10.1145/160000/155339/p64-kontothanassis.pdf?key1=155339&&key2=5273305901&col1=ACM&d1=ACM&CFID=27301003&CFTOKEN=7, 1993, 28(7), 4 pages.
Mellor-Crummey, J., et al., “Algorithms for scalable synchronization on shared-memory multiprocessors,”ACM Transactions on Computer Systems(TOCS), portal.acm.org/citation.cfm?id=103729&col1=ACM&d1=ACM&CFID=27301003&CFTOKEN=77797719, 1991, 14 pages.
Rosenthal, D., et al., Using hard disks for digital preservation, citeseer.ist.psu.edu/update/440463, downloaded Aug. 23, 2005, 3 pages.
Tsafrir, D., et al., “Barrier synchronization on a loaded SMP using two-phase waiting algorithms,”International Parallel&Distributed Proceedings Symposium, citeseer.ist.psu.edu/cache/papers/cs/25763/http:zSzzSzwww.cs.huji.ac.ilzSz-feitzSzpaperszSzbarrier.pdf/tsafrir02barrier.pdf, 2002.
Clift Neill M.
Kishan Arun U.
Morrison Jonathan D.
Rector John
An Meng-Ai
Microsoft Corporation
To Jennifer N
Woodcock & Washburn LLP
LandOfFree
Blocking local sense synchronization barrier does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Blocking local sense synchronization barrier, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Blocking local sense synchronization barrier will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4150628