Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2000-06-20
2003-01-14
Ellis, Kevin L. (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
Reexamination Certificate
active
06507903
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computer processing and, in particular, to parallel computer programming or processing.
2. Description of Related Art
In prior art computing using separate, non-parallel processing, the programs often share data and other services. An example of this is shown in
FIG. 1
where separate process memories
19
a,
19
b,
which may be physically separated in different memory storage, or logically separated in the same memory storage, contain global variable memory
20
a,
20
b
for data items visible to the entire process, heap memory
21
a,
21
b
for data structure, stack memory
23
a,
23
b
for function arguments, and local data items, and free memory space
22
a,
22
b
which may be utilized as needed for either heap or stack memory space. A portion of the free memory space may be designated as common memory
22
c
available to both program A,
24
a,
or program B,
24
b,
which operate in the separate process memories
19
a,
19
b,
respectively. Each program A and B can access in the process memory only in what is designated in the common area
22
c,
but cannot access other memory between the programs. A programmer utilizing the system of
FIG. 1
has relatively little assistance from the system in restricting access to data structures in common memory.
Parallel processing offers improvements in that a single program can run simultaneously different threads or independent flows of control managed by the program. Multiple threads may execute in a parallel manner, and the threads may share information in either a loosely or tightly coupled manner. An example of a parallel processing arrangement is shown in
FIG. 2
where a single process memory
119
having a common global memory
120
and a common heap space
121
contains a plurality of stack spaces
123
a,
123
b,
with a single program
124
operating a plurality of threads, with one stack per program thread. The process memory structure shown can operate any number of threads 1-N and contain any number of corresponding stacks 1-N, as shown.
Coordinated data access between threads usually requires operating system assistance (with associated penalties), such as semaphores or locks. However, in typical parallel processing applications, serialization caused by use of system services such as storage management, and coordination of access to memory often significantly reduces the attainable performance advantages of a parallel algorithm. Serialization occurs when more than one thread accesses or requests a data object or other system resource. If such a conflict occurs, only one thread has access and all other threads are denied access until the first thread is finished with the system resource. For example, the structure shown in
FIG. 2
is error-prone because heap space, which contains information that is being manipulated by the program, is subject to collision as different threads attempt to access the same data structure at the same time. When this occurs, one or more threads have to wait while the data structure is accessed by another program thread.
In current practice, memory management in parallel software is also an area where complexity and inefficiency are major drawbacks. The benefits of parallel execution can be nullified, or even degraded to where sequential execution is faster, when calls are made to allocate or free memory. This is due to current serialization techniques, which must be employed to prevent collisions when two or more flows of control, i.e., threads, attempt to obtain or free memory areas. This can significantly degrade the performance of parallel programs, forcing unnatural exercises in program design and implementation. These contortions compromise maintainability, extensibility, and are a source of errors. Worse yet, the costs associated with these problems can deter developers from even considering otherwise viable parallel solutions.
In parallel programming, as described above, each thread is assigned a specific unit of work to perform, generally in parallel, and when the work is finished, the threads cease to exist. There is a cost to create a thread, terminate a thread, and to manage a thread. The cost has both machine-cycle components and programming complexity components. The programming complexity components are a source of errors in implementation and design of the software. The prevailing paradigm in the use of threads treats the threads and data differently. There is control flow (threads), and there is data. The resulting dichotomy creates an environment which tends to place fetters on the kinds of solutions envisioned, and creates complexity and resulting error-proneness during implementation.
Bearing in mind the problems and deficiencies of the prior art, it is therefore an object of the present invention to provide a parallel processing structure which is less subject to error.
It is another object of the present invention to provide a parallel processing structure which is less subject to serialization limitations in accessing common system services such as data structures.
A further object of the invention is to provide a parallel processing structure which is less subject to serialization limitations in allocating or freeing memory.
It is another object of the present invention to provide a parallel processing structure in which there is less interaction between different threads.
It is another object of the present invention to provide a parallel processing structure which reduces cost and errors in creating, managing and terminating a thread.
Still other objects and advantages of the invention will in part be obvious and will in part be apparent from the specification.
SUMMARY OF THE INVENTION
The above and other objects and advantages, which will be apparent to one of skill in the art, are achieved in the present invention which is directed to, in a first aspect, a computer memory structure for parallel computing having a first level of hierarchy comprising a plane. The plane contains a thread which represents an independent flow of control managed by a program structure, a heap portion for data structure, a stack portion for function arguments, and local variables and global data accessible by any part of the program structure. The memory structure further has a second level of hierarchy comprising a space. The space contains two or more of the planes, with the planes in the space containing the program structure. The space further contains common data accessible by the program structure between each of the planes.
Preferably, the memory structure further has a third level of hierarchy comprising two or more of the spaces. The spaces contain the same or different program structures, and common data accessible by the program structure between each of the spaces. The program structure comprises a library of programs and further includes a function table for each space, with the function table being adapted to exchange services with the library in each space.
In a related aspect, the invention provides a computer program product for parallel computing comprising a computer usable medium having computer readable code embodied in the medium. The computer code defines a computer memory structure and includes the aforedescribed first and second levels of hierarchy, and, preferably, also the third level of hierarchy.
Another related aspect of the invention provides a method of parallel processing in which there is first provided a computer memory structure having the first and second levels of hierarchy described above. The method then includes employing a first thread managed by the program structure in a first plane in the space and accessing data in the first plane and common data between each of the planes, and employing a second thread managed by the program structure in a second plane in the space and accessing data in the second plane and common data between each of the planes. The first and second threads avoid interaction with each other except when explicitly requested by the progr
Beatty, III Harry J.
Elmendorf Peter C.
Anderson Jay H.
DeLio & Peterson LLC
Ellis Kevin L.
Peterson Peter W.
LandOfFree
High performance non-blocking parallel storage manager for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with High performance non-blocking parallel storage manager for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High performance non-blocking parallel storage manager for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3060385