Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
2006-11-14
2006-11-14
An, Meng-Al T. (Department: 2195)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
C718S100000, C711S117000
Reexamination Certificate
active
07137116
ABSTRACT:
A method and system for performing a task on a computer is provided, in which the procedure is organized into multiple stages. Each stage of the task has an associated sub-task. Requests for the procedure are represented by “work packets” that stored in a holding area at each stage, such as a stack or a queue, until it is advantageous for a processor to execute them. Each work packet contains data and/or instructions for performing the sub-task of the stage. When a processor is available, it finds a stage having unexecuted work packets and executes a batch of work packets by repeatedly performing the sub-task of the stage. This repeated execution of a sub-task allows a processor to maximize its native time-saving mechanisms, such as cache. The invention may advantageously be used as an alternative to conventional thread-based programming.
REFERENCES:
patent: 5452447 (1995-09-01), Nelson et al.
patent: 5485609 (1996-01-01), Vitter et al.
patent: 5517662 (1996-05-01), Coleman et al.
patent: 5524242 (1996-06-01), Aida et al.
patent: 5553305 (1996-09-01), Gregor et al.
patent: 5566321 (1996-10-01), Pase et al.
patent: 5768515 (1998-06-01), Choquier et al.
patent: 5796954 (1998-08-01), Hanif et al.
patent: 5828880 (1998-10-01), Hanko
patent: 6003066 (1999-12-01), Ryan et al.
patent: 6088044 (2000-07-01), Kwok et al.
patent: 6119145 (2000-09-01), Ikeda et al.
patent: 6230190 (2001-05-01), Edmonds et al.
patent: 6263358 (2001-07-01), Lee et al.
patent: 6266708 (2001-07-01), Austvold et al.
patent: 6298382 (2001-10-01), Doi et al.
patent: 6330583 (2001-12-01), Reiffin
patent: 6330643 (2001-12-01), Arimilli et al.
patent: 6425021 (2002-07-01), Ghodrat et al.
patent: 6496871 (2002-12-01), Koyama et al.
patent: 6505229 (2003-01-01), Turner et al.
patent: 6633897 (2003-10-01), Browning et al.
Gosling, James, et al., “The Java Language Specification,”Addison Wesley, (1996).
Ailamaki, Anastassia G., et al., “DBMSs On A Modern Processor: Where Does Time Go?,” in theProceedings of the 25thInternational Conference on Very Large Data Bases, (Sep. 1999), pp. 266-277, Edinburgh, Scotland, UK.
Nikhil, Arvind and Rishiyur S., “I-Structure: Data Structures for Parallel Computing,”ACM Transactions on Programming Languages and Systems, vol. 11 (4):598-632, (Oct. 1989).
Banga, Gaurav, et al., “Scalable Kernel Performance for Internet Servers Under Realistic Loads,” in theProceedings of the USENIX 1998 Annual Technical Conferenc; New Orleans, LO, (1998), pp. 1-12.
Blelloch, Guy E., et al., “Space-Efficient Scheduling of Parallelism with Synchronization Variables,” inProceedings of the 9thAnnual ACM Symposium on Parallel Algorithms and Architectures (SPAA); Newport, Rhode Island, (1997), pp. 12-23.
Cao, Q., et al., “Detailed Characterization of a Quad Pentium Pro Server Running TPC-D,” inProceedings of the International Conference on Computer Design(ICCD); Austin, TX, (Oct. 1999), pp. 108-115.
Chilimbi, Trishul, M., et al., “Cache-Conscious Structure Definition,” in theProceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and Implementation(PLDI); Atlanta, GA, (May 1999),, pp. 13-24.
Chilimbi, Trishul, M., et al., “Cache-Conscious Structure Layout,” in theProceedings of ACM SIGPLAN '99 Conference on Programming Languages Design and Implementation(PLD); Atlanta, GA, (May 1999), pp-.12,.
Eickemeyer, Richard, J., et al., “Evaluation of Multithreaded Uniprocessors for Commercial Application Environments,” inProceedings of the 23rdAnnual International Symposium on Computer Architecture; Philadelphia, PA, (May 1996), pp. 203-212,.
Freeh, Vincent, W., et al., “Distributed Filaments: Efficient Fine-Grain Parallelism on a Cluster Of Workstation,” inProceedings of the First USENIX Symposium on Operating Systems Design and Implementation(OSDI); Monterey, CA, (Nov. 1994), pp. 201-213.
Harel, D., et al., “On the Development of Reactive Systems,” inLogics and Models of Concurrent Systems, vol. F13, K.R. Apt, Ed. Berlin: Springer-Verlag (1985), pp. 477-498.
Jayasimha, Jay, et al., “Thread-based Cache Analysis of a Modified TPC-C Workload,” inProceedings of the Second Workshop on Computer Architecture Evaluation Using Commercial Workload; Orlando, FL. (1999).
Keeton, Kimberly, et al., “Performance Characterization of a Quad Pentium Pro SMP Using OLTP Workloads,” inProceedings th e25th Annual International Symposium on Computer Architecture; Barcelona, Spain, vol. 26(3):15-26, (Jun. 1998).
Lamarca, Anthony, et al., “The Influence of Caches on the Performance of Heaps,”The ACM Journal of Experimental Algorithmics, (1997), pp. 1-32.
Lo, Jack, L., et al., “An Analysis of Database Workload Performance on Simultaneous Multithreaded Processors,” inProceedings of the 25thAnnunal International Symposium on Computer Architecture, Barcelona, Spain, vol. 26(3):39-50, (Jun. 1998).
Maltzahn, Carlos, et al., “Performance Issues of Enterprise Level Web Proxies,” in Proceedings of the1997 ACM Sigmetrics International Conference on Measurement and Modeling of Computer Systems; Seattle, WA, (Jun. 1997), pp. 13-23.
Morris, Robert, et al., “The Click Modular Router,” inProceedings of the 17thACM Symposium on Operating Systems Principles(SOSP'99); Charleston, South Carolina, vol. 33(5):217-231 (Dec. 1999).
Pai, Vivek, S., et al., “Flash: An efficient and portable Web Server,” inProceedings of the 1999 USENIX Annual Technical Conference; Monterey, CA, (Jun. 1999), pp. 199-212.
Pettis, Karl, et al., “Profile Guided Code Positioning,” inProceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation; White Plans, NY., (Jun. 1990),Sigplan Notices, vol. 25(6):16-27.
Philbin, James, et al., “Thread Scheduling for Cache Locality,” inProceedings of the 7thInternational Conference on Architectural Support for Programming Languages and Operating systems(ASPLOS VII); Cambridge, MA, (Oct. 1996), pp. 60-71.
Ranganathan, Parthasarathy, et al., “Performance of Database Workloads on Shared-Memory Systems with Out-of-Order Performance,” in theProceedings of the 8thInternational Conference on Architectural Support for Programming Languages and Operating Systems(ASPLOS VII); San Jose, CA., (Oct. 1998), pp. 307-318.
Torrellas, Josep, et al., “Optimizing the Instruction Cache Performance of the Operating System,”IEEE Transactions on Computers. vol. 47(12):1363-1381, (Dec. 1998).
Wand, Mitchell, “Continuation-Based Multiprocessing,” inProceedings of the 1980 LISP Conference; Stanford University, Palo Alto, CA, (Aug. 1980), pp. 19-28.
Hill, Mark, D., et al., “Evaluating Associativity in CPU Caches,”IEEE Transactions on Computers; vol. 38(12):1612-1630, (1989).
Lee, Edward, A., et al., “Dataflow Process Network,”Proceedings of the IEEE; vol. 83(5):773-799, (May 1995).
Mogul, Jeffrey, C., et al., “The Effect of Context Switches on Cache Performance,” in Proceedings of the Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, Santa Clara, CA, (Apr. 1991), pp. 75-85.
Najjar, Walid A., et al., “Advances in the dataflow computational Model,” Parallel Computing, vol. 25, (1999).
Perl, Sharon, et al., “Studies of Windows NT Performance Using Dynamic Execution Traces,” inProceedings of the 2ndUSENIX Symposium on Operating Systems Design and Implementation(OSDI); vol. 30, Special Issue (1996), Seattle, WA, (Oct. 1997).
Rosenblum, Mendel, et al., “The Impact of Architectural Trends on Operating System Performance,”Copper Mountain Resort, CO., (Dec. 1995), pp. 285-298.
Acar, Umut, A., et al., “The Data Locality of Work Stealing,” inProceedings of the Twelfth Annual ACM Symposium on Parallel Algorithms and Architectures(SPAA 2000); Bar Harbor,
Larus James R.
Parkes Michael A
Ali Syed J
An Meng-Al T.
Microsoft Corporation
Microsoft Corporation
LandOfFree
Method and system for performing a task on a computer does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for performing a task on a computer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for performing a task on a computer will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3663504