Browse Prior Art Database

Shared Variable Support using Optimistic Execution

IP.com Disclosure Number: IPCOM000116797D
Original Publication Date: 1995-Nov-01
Included in the Prior Art Database: 2005-Mar-31
Document File: 6 page(s) / 210K

Publishing Venue

IBM

Related People

Childs, PL: AUTHOR [+6]

Abstract

A method for virtual time execution with variables shared between two or more communicating sequential processes is disclosed. The technique disclosed here clusters and encapsulates shared variables within an implicit process.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 29% of the total text.

Shared Variable Support using Optimistic Execution

      A method for virtual time execution with variables shared
between two or more communicating sequential processes is disclosed.
The technique disclosed here clusters and encapsulates shared
variables within an implicit process.

      Many languages used for hardware description and general
purpose programming share variables between two or more processes.
Examples include Very High Speed Integrated Circuit (VHSIC) Hardware
Description Language (VHDL) (1), Verilog (2), and concurrent dialects
of C++ (3).  The presence of shared variables in programs presents a
challenge to efficient parallel execution, especially if parallel
execution is to achieve results equivalent to a serial execution of
the same program.

      A means has been disclosed (4) of executing Communicating
Sequential Process (CSP) programs which helps to decouple execution
of processes, and thus would tend to improve parallel execution.  His
technique is variously referred to as Optimistic, Virtual Time or
Time Warp execution.  This disclosure will subsequently refer to the
technique as optimistic execution.

      In order to preserve the semantics of a sequential execution
during a parallel execution, optimistic execution assumes there is a
global logical time domain in which execution ordering constraints
can be defined.  Each process has a Local Time (LT), expressed in the
logical time domain, and used to order evaluation within the process
and communication between processes.  A Global Virtual Time (GVT)
denotes the earliest local time of any process.  A distinct real time
domain, sometimes known as wall-clock time, is used to refer to the
order in which hardware processors actual execute instructions.

      Under optimistic execution, each process progressively
processes the messages at later points in logical time assuming that
it will not receive any message with the logical time less than the
logical time of these messages.  Such an execution continues until
the process is notified that the execution was based on an invalid
assumption.  Notification of an invalid assumption takes the form of
a message arriving at the process either with the logical time less
than the logical time of the executed messages(s) or a message
indicating that the executed message at a particular logical time
should be cancelled.

      In response to notification of an invalid assumption, the
process must be prepared to rollback both its state and all of the
messages sent by the process, to the state present before the
(invalid) assumption was made.  Message rollback occurs by sending an
anti-message for each message which must be rolled back.
Conceptually
messages and anti-messages combine to eliminate each other.

      In order to minimize the overhead associated with executing
processes using optimistic execution, (physical) processes created
during source code analysis or static elaboration a...