U.S. patents available from 1976 to present.
U.S. patent applications available from 2005 to present.

Icon_funbox Bizarre Patents

Patent No. 5926874

Automatic Bed Maker

An automatic bed maker which uses the expansion of inflatable bladder to straighten, align, and tuck-in bed-cover assembly.

Newsletter  PatentStorm News

Make the Most of PatentStorm

See this month's Top Inventors and Most Cited Patents.

Stay on top of the latest patents by subscribing to an RSS feed.

Got questions? Ask a Patent Expert!

Registered users: Manage your profile, comments and alerts.

 

US Patent 6353829 - Method and system for memory allocation in a multiprocessing environment

US Patent Issued on March 5, 2002
Estimated Patent Expiration Date: Icon_subject December 23, 2018Estimated 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.
loading...


View Patent Images (PDF)
(Registered users only)

Abstract

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

Inventors

Assignee

Application

No. 221657 filed on 12/23/1998

US Classes:

707/100, DATABASE SCHEMA OR DATA STRUCTURE712/203, Multiprocessor instruction712/233Branching (e.g., delayed branch, loop control, branch predict, interrupt)

Field of Search

707/100, DATABASE SCHEMA OR DATA STRUCTURE712/203, Multiprocessor instruction712/233Branching (e.g., delayed branch, loop control, branch predict, interrupt)

Examiners

Primary: Lintz, Paul R.

Attorney, Agent or Firm

US Patent References

4819234, Operating system debugger
Issued on: 04/04/1989
Inventor: Huber
4872167, Method for displaying program executing circumstances and an apparatus using the same
Issued on: 10/03/1989
Inventor: Maezawa, et al.
5168554, Converting trace data from processors executing in parallel into graphical form
Issued on: 12/01/1992
Inventor: Luke
5301325, Use of stack depth to identify architechture and calling standard dependencies in machine code
Issued on: 04/05/1994
Inventor: Benson
5333280, Parallel pipelined instruction processing system for very long instruction word
Issued on: 07/26/1994
Inventor: Ishikawa, et al.
5450575, Use of stack depth to identify machine code mistakes
Issued on: 09/12/1995
Inventor: Sites
5504932, System for executing scalar instructions in parallel based on control bits appended by compounding decoder
Issued on: 04/02/1996
Inventor: Vassiliadis, et al.
5533192, Computer program debugging system and method
Issued on: 07/02/1996
Inventor: Hawley, et al.
5557761, System and method of generating object code using aggregate instruction movement
Issued on: 09/17/1996
Inventor: Chan, et al.
5564051, Automatic update of static and dynamic files at a remote network node in response to calls issued by or for application programs
Issued on: 10/08/1996
Inventor: Halliwell, et al.
5581764, Distributed computer network including hierarchical resource information structure and related method of distributing resources
Issued on: 12/03/1996
Inventor: Fitzgerald, et al.
5594864, Method and apparatus for unobtrusively monitoring processor states and characterizing bottlenecks in a pipelined processor executing grouped instructions
Issued on: 01/14/1997
Inventor: Trauben
5598560, Tracking condition codes in translation code for different machine architectures
Issued on: 01/28/1997
Inventor: Benson
5632032, Cross address space thread control in a multithreaded environment
Issued on: 05/20/1997
Inventor: Ault, et al.
5652889, Alternate execution and interpretation of computer program having code at unknown locations due to transfer instructions having computed destination addresses
Issued on: 07/29/1997
Inventor: Sites
5712996, Process for dividing instructions of a computer program into instruction groups for parallel processing
Issued on: 01/27/1998
Inventor: Schepers
5754855, System and method for managing control flow of computer programs executing in a computer system
Issued on: 05/19/1998
Inventor: Miller, et al.
5768592, Method and apparatus for managing profile data
Issued on: 06/16/1998
Inventor: Chang
5768891, Exhaust system with scavenging venturi
Issued on: 06/23/1998
Inventor: Wagner
5774721, Method of communication between processors in a distributed processing system having a host processor and at least one object oriented processor
Issued on: 06/30/1998
Inventor: Robinson
5787245, Portable debugging service utilizing a client debugger object and a server debugger object
Issued on: 07/28/1998
Inventor: You, et al.
5805892, Method of and apparatus for debugging multitask programs
Issued on: 09/08/1998
Inventor: Nakajima
5812811, Executing speculative parallel instructions threads with forking and inter-thread communication
Issued on: 09/22/1998
Inventor: Dubey, et al.
5826265, Data management system having shared libraries
Issued on: 10/20/1998
Inventor: Van Huben, et al.
5867643, Run-time data type description mechanism for performance information in an extensible computer system
Issued on: 02/02/1999
Inventor: Sutton
5877766, Multi-node user interface component and method thereof for use in accessing a plurality of linked records
Issued on: 03/02/1999
Inventor: Bates, et al.
5887166, Method and system for constructing a program including a navigation instruction
Issued on: 03/23/1999
Inventor: Mallick, et al.
5901315, Method for debugging a Java application having native method dynamic load libraries
Issued on: 05/04/1999
Inventor: Edwards, et al.
5903730, Method of visualizing results of performance monitoring and analysis in a parallel computing system
Issued on: 05/11/1999
Inventor: Asai, et al.
5913925, Method and system for constructing a program including out-of-order threads and processor and method for executing threads out-of-order
Issued on: 06/22/1999
Inventor: Kahle, et al.
5953530, Method and apparatus for run-time memory access checking and memory leak detection of a multi-threaded program
Issued on: 09/14/1999
Inventor: Rishi, et al.
5961639, Processor and method for dynamically inserting auxiliary instructions within an instruction stream during execution
Issued on: 10/05/1999
Inventor: Mallick, et al.
5966539, Link time optimization with translation to intermediate program and following optimization techniques including program analysis code motion live variable set generation order analysis, dead code elimination and load invariant analysis
Issued on: 10/12/1999
Inventor: Srivastava
5978902, Debug interface including operating system access of a serial/parallel debug port
Issued on: 11/02/1999
Inventor: Mann
6002872, Method and apparatus for structured profiling of data processing systems and applications
Issued on: 12/14/1999
Inventor: Alexander, III, et al.
6002879, Method for performing common subexpression elimination on a rack-N static single assignment language
Issued on: 12/14/1999
Inventor: Radigan, et al.
6009269, Detecting concurrency errors in multi-threaded programs
Issued on: 12/28/1999
Inventor: Burrows, et al.
6029005, Method for identifying partial redundancies in a new processor architecture
Issued on: 02/22/2000
Inventor: Radigan
6049671, Method for identifying and obtaining computer software from a network computer
Issued on: 04/11/2000
Inventor: Slivka, et al.
6058493, Logging and reproduction of automated test operations for computing systems
Issued on: 05/02/2000
Inventor: Talley
6059840, Automatic scheduling of instructions to reduce code size
Issued on: 05/09/2000
Inventor: Click, Jr.
6072952, Method and apparatus for coalescing variables
Issued on: 06/06/2000
Inventor: Janakiraman
6094716, Register renaming in which moves are accomplished by swapping rename tags
Issued on: 07/25/2000
Inventor: Witt
6101524, Deterministic replay of multithreaded applications
Issued on: 08/08/2000
Inventor: Choi, et al.
6112293, Processor configured to generate lookahead results from operand collapse unit and for inhibiting receipt/execution of the first instruction based on the lookahead result
Issued on: 08/29/2000
Inventor: Witt
6151701Method for reconstructing debugging information for a decompiled executable file
Issued on: 11/21/2000
Inventor: Humphreys, et al.

Foreign Patent References

  • 0422945 EP. 04/20/1991
  • 0455966 EP. 11/20/1991
  • 0537098 EP. 04/20/1993
  • 0855648 EP. 07/20/1998
  • 0864979 EP. 09/20/1998
  • 2307760 GB. 06/20/1997

International Class

G06F 017/30

Comments

No comments for this page
 
 
Forgot password?
Register here