Method and system for memory allocation in a multiprocessing environment
Patent 6353829 Issued on March 5, 2002. Estimated Expiration Date: December 23, 2018. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.
A method and system for allocating memory. The computer system on which the memory allocation system executes may support the simultaneous execution of multiple threads. Under control of a thread, the memory allocation system first identifies a bin associated with blocks ("lockers") of memory large enough to satisfy a memory allocation request. When the identified bin has a free locker, the memory allocation system searches a circular list of headers associated with the identified bin for a collection of lockers ("warehouse") that contains a locker that is available to be allocated. The memory allocation system allocates the found available locker to satisfy the request. If, however, the allocated bin has no free lockers, the memory allocation system allocates a warehouse with lockers large enough to satisfy the memory allocation request. The memory allocation system then adds a warehouse header for the allocated warehouse to a circular list of warehouse headers associated with the identified bin. The memory allocation system allocates a locker from the newly allocated warehouse to satisfy the memory allocation request.
Other References
Smith, Burton, "The End of Architecture," Keynote Address Presented at the 17th Annual Symposium on Computer Architecture, Seattle, Washington, May 29, 1990. p 1-5
Richard Korry et al., "Memory Management in the Tera MTA System," 1995. p 1-11
Smith, Burton, "Opportunities for Growth in High Performance Computing," Nov., 1994. p 1-3
Gail Alverson et al., "Processor Management in the Tera MTA System," 1995. p 1-14
Major System Characteristics of the TERA MTA, 1995. p 1-7.
Touzeau, Roy F., "A Fortran Compiler for the FPS-164 Scientific Computer," Proceedings of the ACM SIGPLAN '84 Symposium on Compiler Construction, SIGPLAN Notices 19(6):48-57, Jun. 1984.
Linton, Mark A., "The Evolution of Dbx,"USENIX Summer Conference, Jun. 11-15, 1990. p 211-220.
David Callahan and Burton Smith, A Future-Based Parallel Language for a General-Purpose Highly-Parallel Computer, Languages and Compilers for Parallel Computing, MIT Press, 1990. p 1-31.
David Callahan et al., "Improving Register Allocation for Subscripted Variables," Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation, White Plains, New York, Jun. 20-22, 1990. p 53-65.
Adelberg, Brad et al., "The Strip Rule System for Efficiently Maintaining Derived Data," Sigmod Record, Association for Computing Machinery, New York, vol. 26, No. 2, Jun. 1, 1997. p 147-158.
Surajit, Chaudhuri and Umeshwar Dayal, "An Overview of Data Warehousing and OLAP Technology," Sigmod Record, Association for Computing, New York, vol. 26, No. 1, Mar. 1997. p 65-74.
Agrawal, Gagan and Joel Saltz, "Interprocedural Data Flow Based Optimizations for Compilation of Irregular Problems," Annual Workshop on Languages and Compilers for Parallel Computing, 1995. p 465-479.
Callahan, David, "Recognizing and Parallelizing Bounded Recurrences," Aug. 1991. unnumbered.
D.H. Bailey et al., "The NAS Parallel Benchmarks--Summary and Preliminary Results," Numerical Aerodynamic Simulation (NAS) Systems Division, NASA Ames Research Center, California, 1991. p 158-165
Robert Alverson et al, "The Tera Computer System,"Proceedings of 1990 ACM International Conference on Supercomputing, Jun. 1990. p 1-6
Gail Alverson et al., "Scheduling on the Tera MTA," Job Scheduling Strategies for Parallel Processing, 1995. p 1-20
Smith, Burton, The Quest for General-Purpose Parallel Computing. p 1-18
Briggs, Preston and Keith D. Cooper, "Effective Partial Redundancy Elimination," ACM SIGPLAN Notices, Association for Computing Machinery, New York, vol. 29, No. 6, Jun. 1, 1994. p 159-170
Click, Cliff, "Global Code Motion, Global Value Numbering," ACM SIGPLAN Notices, Association for Computing Machinery, New York, vol. 30, No. 6, Jun. 1, 1995. p 246-257
Sreedhar, Vugranam C. and Guang R. Gao, "Incremental Computation of Dominator Trees," ACM SIGPLAN Notices, Association for Computing Machinery, New York, vol. 30, No. 3, Mar. 1, 1995. p 1-12
Galarowicz, Jim et al., "Analyzing Message Passing Programs on the Cray T3E with PAT and VAMPIR," Research Report, "Online!", May 1998. p 1-21
Anderson, Jennifer, et al., "Continuous Profiling: Where Have All The Cycles Gone?," Operating Systems Review, ACM Headquarters, New York, vol. 31, No. 5, Dec. 1, 1997
Anderson, Gail et al., "Tera Hardward-Software Cooperation," Proceedings of Supercomputing 1997, San Jose, California, Nov. 1997. 20 pages
Jack W. Davidson and David B. Whally, "Reducing the Cost of Branches by Using Registers," Proceedings of the 17th Annual Symposium on Computer Architecture, Seattle, Washington, May 28-31, 1990. p 182-191
Jens Knoop et al., "The Power of Assignment Motion," ACM SIGPLAN '95 Conference on Programming Language Design and Implementation, La Jolla, California, Jun. 18-21, 1995. p 233-245
Hiralal Agrawal, "Dominators, Super Blocks and Program Coverage," 21st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, Portland, Oregon, Jan. 17-21, 1994. p 25-34
Tomas Lang and Miquel Huguet, "Reduced Register Saving/Restoring in Single-Window Register Files," Computer Architecture News, vol. 14, No. 3, Jun. 1986. p 17-26
Kenneth J. Goldman, "Introduction to Data Structures," 1996 (retrieved from Internet, http://www.cs.wustl.edu{kjg/CS101_SP97/Notes?DataStructures/structures. html p 1-17
Ashwin Ram and Janak H. Patel, "Parallel Garbage Collection Without Synchronization Overhead," 12th Annual Symposium on Computer Architecture, Jun. 17, 1985. p 84-90
H. Hayashi et al., "ALPHA: A High Performance Lisp machine Equipped with a New Stack Structure and Garbage Collection System," 10th Annual International Symposium on Computer Architecture, 1983. p 342-348
Tera MTA, Principles of Operation, Nov. 18, 1997. p 1-245
Ji Minwen et al, Performance Measurements for Multithreaded Programs, SIGMETRICS '98, ACM, 1998, pp. 161-170
Jonathan E. Cook and Alexander L. Wolf, "Event Based Detection of Concurrency," SIGSOFT '98 ACM, 1998, pp. 34-45
Jenn-Yuan Tsai et al., "Performance Study of a Concurrent Multithreaded Processor," IEEE, 1998, pp. 24-35
"Method of Tracing Events in Multi-Threaded OS/1 Applications," IBM Tech. Disclosure Bulletin, Sep. 1993, pp. 19-22
Priyadarshan Kolte and Mary Jean Harrold, "Load/Store Range Analysis for Global Register Allocation," ACM-SIGPLAN, Jun. 1993. p 268-277
George Lal and Andrew W. Appel, "Iterated Register Coalescing," ACM Transactions on Programming Languages and Systems, vol. 18, No. 3, May 1996, pp. 300-324
Fred C. Chow and John L. Hennessy, "The Priority-Based Coloring Approach to Register Allocation," ACM Transactions on Programming Languages and Systems, vol. 12, No. 4, Oct. 4, 1990, pp. 501-536
Preston Briggs et al., "Coloring Heuristics for Register Allocation," Department of Computer Science, Rice University, Houston, Texas, Jun. 1989. p 279-284
Preston Briggs et al., "Coloring Register Pairs," ACM Letters on Programming Languages and Systems, vol. 1, No. 1, Mar. 1992, pp. 3-13
SangMin Shim and Soo-Mook Moon, "Split-Path Enhanced Pipeline Scheduling for Loops with Control Flows," IEEE, Dec. 2, 1998. p 93-102
David Callahan and Brian Koblenz, "Register Allocation via Hierarchical Graph Coloring," Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design and Implementation, Toronto, Canada, Jun. 26-28, 1991. p 192-20
December 23, 2018. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.
