Apparatus and method for achieving reduced overhead mutual...

Details Apparatus and method for achieving reduced overhead mutual... Apparatus and method for achieving reduced overhead mutual...

1996-11-01

2001-04-17

Banankhah, Majid (Department: 2151)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

Least weight routing

Reexamination Certificate

active

06219690

ABSTRACT:

TECHNICAL FIELD
This invention relates to computer systems and more particularly to a reduced overhead mutual-exclusion mechanism that provides data coherency and improves computer system performance.
BACKGROUND OF THE INVENTION
Data coherency is threatened whenever two or more computer processes compete for a common data item that is stored in a memory or when two or more copies of the same data item are stored in separate memories and one item is subsequently altered. Previously known apparatus and methods for ensuring data coherency in computer systems are generally referred to as mutual-exclusion mechanisms.
A variety of mutual-exclusion mechanisms have evolved to ensure data coherency. Mutual-exclusion mechanisms prevent more than one computer process from accessing and/or updating (changing) a data item or ensure that any copy of a data item being accessed is valid. Unfortunately, conventional mutual-exclusion mechanisms degrade computer system performance by adding some combination of procedures, checks, locks, program steps, or complexity to the computer system.
Advances in processor and memory technology make it possible to build high-performance computer systems that include multiple processors. Such computer systems increase the opportunity for data coherency problems and, therefore, typically require multiple mutual-exclusion mechanisms.
When multiple processors each execute an independent program to accelerate system performance, the overall system throughput is improved rather than the execution time of a single program.
When the execution time of a single program requires improvement, one way of improving the performance is to divide the program into cooperating processes that are executed in parallel by multiple processors. Such a program is referred to as a multitasking program.
Referring to
FIG. 1A
, multiple computers
10
are interconnected by an interconnection network
12
to form a computer system
14
.
FIG. 1B
shows that a typical one of computer
10
includes N number of processors
16
A,
16
B, . . . , and
16
N (collectively “processors
16
”). In computer
10
and computer system
14
, significant time is consumed by intercommunication. Intercommunication is carried out at various levels.
In computer
10
, at a processor memory interface level, processors
16
access data in a shared memory
18
by transferring data across a system bus
20
. System bus
20
requires a high-communication bandwidth because it shares data transfers for processors
16
. Computer
10
is referred to as a multiprocessor computer.
In computer system
14
, at an overall system level, computers
10
each have a shared memory
18
and interconnection network
12
is used only for intercomputer communication. Computer system
14
is referred to as a multicomputer system.
The high threat to data coherency in multicomputer and multiprocessor systems is caused by the increased competition among processors
16
for data items in shared memories
18
.
Ideally, multicomputer and multiprocessor systems should achieve performance levels that are linearly related to the number of processors
16
in a particular system. For example,
10
processors should execute a program
10
times faster than one processor. In a system operating at this ideal rate, all processors contribute toward the execution of the single program, and no processor executes instructions that would not be executed by a single processor executing the same program. However, several factors including synchronization, program structure, and contention inhibit multicomputer and multiprocessor systems from operating at the ideal rate.
Synchronization: The activities of the independently executing processors must be occasionally coordinated, causing some processors to be idle while others continue execution to catch up. Synchronization that forces sequential consistency on data access and/or updates is one form of mutual exclusion.
Program structure: Not every program is suited for efficient execution on a multicomputer or a multiprocessor system. For example, some programs have insufficient parallelism to keep all multiple processors busy simultaneously, and a sufficiently parallel program often requires more steps than a serially executing program. However, data coherency problems increase with the degree of program parallelism.
Contention: If processor
16
A competes with processor
16
B for a shared resource, such as sharable data in shared memory
18
, contention for the data might cause processor
16
A to pause until processor
16
B finishes using and possibly updating the sharable data.
Any factor that contributes to reducing the ideal performance of a computing system is referred to as overhead. For example, when processors
16
A and
16
B simultaneously request data from shared memory
18
, the resulting contention requires a time-consuming resolution process. The number of such contentions can be reduced by providing processors
16
with N number of cache memories
22
A,
22
B, . . . , and
22
N (collectively “cache memories
22
”). Cache memories
22
store data frequently or recently executed by their associated processors
16
. However, processors
16
cannot efficiently access data in cache memories
22
associated with other processors. Therefore, cached data cannot be readily transferred among processors without increased overhead.
Incoherent data can result any time data are shared, transferred among processors
16
, or transferred to an external device such as a disk memory
24
. Thus, conventional wisdom dictates that computer performance is ultimately limited by the amount of overhead required to maintain data coherency.
Prior workers have described various mutual-exclusion techniques as solutions to the data coherence problem in single and multiprocessor computer systems.
Referring to
FIG. 2
, Maurice J. Bach, in
The Design of the UNIX Operating System,
Prentice-Hall, Inc., Englewood Cliffs, N.J., 1986 (“Bach”) describes single processor and multiprocessor computer implementations of a UNIX® operating system in which a process
30
has an asleep state
32
, a ready to run state
34
, a kernel running state
36
, and a user running state
38
. Several processes can simultaneously operate on shared operating system data leading to operating system data coherency problems. Bach solves the operating system data coherency problem by allowing process
30
to update data only during a process state transition
40
from kernel running state
36
to asleep state
32
. Process
30
is inactive in asleep state
32
. Data coherency is also protected by using data “locks” that prevent other processes from reading or writing any part of the locked data until it is “unlocked.”
Referring again to
FIG. 1
, Lucien M. Censier and Paul Feautrier, in “A New Solution to Coherence Problems in Multicache Systems, ”
IEEE Transactions on Computers,
Vol. C-27, No. 12, December 1978 (“Censier and Feautrier”) describe a presence flag mutual-exclusion technique. This technique entails using data state commands and associated state status lines for controlling data transfers among N number of cache memory controllers
50
A,
50
B, . . . , and
50
N (collectively “cache controllers
50
”) and a shared memory controller
52
. The data state commands include shared read, private read, declare private,.invalidate data, and share data. Advantageously,.no unnecessary data invalidation commands are issued and the most recent (valid) copy of a shared data item can quickly be found. Unfortunately, cache memory data structures must be duplicated in shared memory controller
52
and costly nonstandard memories are required. Moreover, performance is limited because system bus
20
transfers the data state commands.
A. J. van de Goor, in
Computer Architecture and Design,
Addison-Wesley Publishers Limited, Workingham, England, 1989, classifies and describes single path, single data (“SPSD”); single path, multiple data (“SPMD”); multiple path, single data (“MPSD”); and multiple path, multiple data (“MPMD”)computer system architectures

Affiliated with

Also associated with

Rating

Apparatus and method for achieving reduced overhead mutual... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Apparatus and method for achieving reduced overhead mutual..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for achieving reduced overhead mutual... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2482850