Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1998-10-15
2002-11-26
Banankhah, Majid (Department: 2156)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S225000, C713S167000
Reexamination Certificate
active
06487579
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to a method for coordinating the execution of cooperating processes that access a common object in a parallel processing environment.
2. Description of the Related Art
Explicit parallel programming is characterized in that the programmer must specify how a plurality of cooperating processes coordinate their execution. Dependent on the computer architecture used, this coordination occurs by:
Synchronization in the case of processes with a common address space. Synchronization prevents common data from being accessed at the wrong time.
Communication between processes with distributed address space. Communication makes data between such processes available (at the right time).
In order to utilize the advantages of these two computer architectures, either communication (for distributed architectures) or synchronization (for architectures with a common address space) is offered as programming means in parallel programming models and parallel programming languages.
The support of what is referred to as the distributed shared memory is known from Bill Nitzberg, Virginia Lo: Distributed Shared Memory: A Survey of issues and Algorithms IEEE COMPUTER, vol. 24, no. Aug. 8, 1991 and is based on the fiction that an inaccessible memory can be accessed (automatic data migration then occurs). There is a great number of programming models for distributed memories in addition to this general operating system approach that refine this idea. For example, Emerald as disclosed in Distribution and Abstract Types in Emerald, IEEE Transactions on Software Engineering SE 13, Jan. 1, 1987 distinguishes between reading and writing. In reading or writing accesses, objects are migrated according to obvious semantics onto the machine that needs them. None of these approaches is conceived for shared memories. An overview of these and similar models or, respectively, languages can be found in H. Bal, J. Steiner, A. Tanenbaum: Programming Languages for Distributed Computing Systems ACM Computing Surveys, September 1989
SUMMARY OF THE INVENTION
An object underlying the invention is comprised in providing a method that enables a uniform programming model for both synchronization and communication architectures. This and other objects and advantages of the invention are achieved by a method for coordinating the execution of processes cooperating with one another that access a common object, wherein: each common object is declared as coordinator object and access patterns that determined sequences of accesses of the cooperating processes onto the coordinator object are allocated to it; a sequence of types of access (access types) is recited in the access pattern; given execution of the processes, the coordinator object determines whether an access to the common object is present and, in this case, determines on the basis of the access pattern whether the access can be implemented or must be postponed until the access of another process has ended.
With the assistance of what are referred to as coordinator objects, the method can replace explicit coordination commands with a static declaration of allowable sequences of accesses, as a result whereof the dynamic executive behavior of the cooperating processes can be influenced. This approach of parallel programming leads to more comfort and portability than in conventional parallel programming without deteriorating the efficiency. Coordinator objects, thus, are passive objects on which the active processes operate.
Identical accesses are referred to with the term access type below. For example, writing accesses belong to one access type, reading accesses to another access type.
The underlying idea of the coordinator objects is thereby as follows: Parallel programmers indicate access patterns for commonly used objects (data). An access pattern describes what sequences of accesses of the cooperating processes to a common object are possible. This shall be explained with reference to writing and reading accesses to a common object. In this case, a distinction can be made between writing and reading accesses and objects that are ready to be read after which writing accesses can be specified. Conversely, objects that are again ready to be written after which reading accesses can also be specified. The patterns can generally be defined by counters that either log the accesses of all processes in common or the accesses of each individual process.
Corresponding to the indicating access patterns, a program behavior arises that implicitly leads to synchronization or communication (triggered by specific access sequences). For example, writing operations are delayed in the read status (i.e. the corresponding processes are put to sleep, ie., temporarily halted). When switching into the write status, the sleeping processes are awakened; they then behave exactly as though they had not yet even attempted their access. The behavior is oppositely identical in the write status. This execution usually occurs iteratively, i.e. the writing and the reading status alternate repeatedly with one another.
The critical idea of the coordinator objects is thus that a run time behavior that is characterized by automatic synchronization or communications is achieved by a priori indicated properties of objects. Accesses to coordinator objects modify the normal program behavior insofar as memory accesses can be delayed—or, expressed differently: Corresponding to the specified access patterns, processes are blocked given accesses to coordinator objects and are re-awakened at a suitable point in time.
Developments of the invention are provided when the access pattern specifies whether a plurality of accesses per access type are handled with priority before an access of another access type. Preferably, the accesses of an access type are implemented in strict succession in order to avoid conflicts. The coordinator object can be informed that no instances of conflict occur given successive processing of the accesses of one access type, so that the accesses need not be strictly implemented. The number of accesses per access type are, in one embodiment, counted with a counter and an access of another process or of another access type is allowed when the allowable number of accesses per access type is reached. One access type covers writing accesses and the other access type covers reading accesses. In a preferred embodiment, the coordinator object can switch into the write status or into the read status, and the initial status is a write status. The switching of the coordinator object from one status into the other status is initiated by a switch condition that can be set by a keyword. The switch condition can be set such that a plurality of accesses of one access type must be met. Alternately, the switch condition can be set such that a total number of accesses by different processes must be met. Yet another alternative, the switch condition can be set such that the accesses of a group of processes must be met. The switch condition is determined by the process.
The coordinator object is realized as a central control program that is specified dependent on respective application. The control program administers accesses that cannot be processed yet in a waiting set. A waiting set is generated in the control program for each access type. The next access to be processed can be selected from a waiting set. Preferably, one waiting queue is prioritized, so that the accesses of this waiting queue are processed first.
In general, a local memory that cannot be addressed by other processes is allocated to each process. Given distributed memory, the control program sees to it for processes for which access is allowed that data consistent with the coordinator data are stored in their local memory.
REFERENCES:
patent: 5404529 (1995-04-01), Chernikoff et al.
patent: 5680452 (1997-10-01), Shanton
Butler et al., “Monitors, Messages, and Clusters: The P4 Parallel Programming System”, Parallel Computing 20, 1994, pp. 547-564.
M. H
Knopp Jürgen
Reich Matthias
Banankhah Majid
Siemens Aktiengesellschaft
Staas & Halsey , LLP
LandOfFree
Process for coordinating the course of cooperating processes... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Process for coordinating the course of cooperating processes..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Process for coordinating the course of cooperating processes... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2958091