US5867649A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Dance/multitude concurrent computation
Assignee: Multitude Corp
•
Filing: 1996-01-23
•
Granted: 1999-02-02
•
Expires: 2016-01-23
Abstract
Abstract This invention computes by constructing a lattice of states. Every lattice of states corresponding to correct execution satisfies the temporal logic formula comprising a Definitive Axiomatic Notation for Concurrent Execution (DANCE) program. This invention integrates into a state-lattice computational model: a polymorphic, strong type system; visibility-limiting domains; first-order assertions; and logic for proving a program correctness. This invention includes special hardware means for elimination of cache coherency among other things, necessary to construct state-lattices concurrently. The model of computation for the DANCE language consisting of four, interrelated, logical systems describing state-lattices, types, domains, and assertions. A fifth logical system interrelates the other four systems allowing proofs of program correctness. The method of the present invention teaches programs as temporal formulas satisfied by lattices of states corresponding to correct execution. State-lattices that are short and bushy allow application of many processors simultaneously thus reducing execution time.
Inventors
- 👤 Brian Ralph Larson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 10:02
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/30; G06F8/31; G06F8/314
Claims Analysis
Total Claims: 9
Claim 1
Independent Claim
106 words
A method of operating a plurality of computing means comprising the steps of: (a) transforming a temporal logic formula into machine executable form; (b) loading the machine executable form for the temporal logic formula and data to be manipulated into said plurality of computing means; and (c) constructing a lattice to satisfy said temporal logic formula, the lattice having a plurality of nodes, each node representing a state value that is a value of a program variable at a given moment, the plurality of nodes being interconnected by directed arcs, each directed arc representing a change in state affected by a computation associated with that arc.
Claim 2
Independent Claim
106 words
A method of operating a plurality of computing means comprising the steps of: (a) transforming a temporal logic formula into machine executable form; (b) loading the machine executable form for the temporal logic formula and data to be manipulated into said plurality of computing means; and (c) constructing a lattice to satisfy said temporal logic formula, the lattice having a plurality of nodes, each node representing a state value that is a value of a program variable at a given moment, the plurality of nodes being interconnected by directed arcs, each directed arc representing a change in state affected by a computation associated with that arc.
Claim 3
Dependent Claim
27 words
The method of claim 1 wherein the state values are elements of strong types, including either constructed types or types defined using existential and bounded universal quantification.
Claim 4
Dependent Claim
19 words
The method of claim 1 wherein visibility of said program variables in a particular state is restricted to domains.
Claim 5
Dependent Claim
24 words
The method of claim 1 in which the state values may occupy computing means located in disparate geographical locations utilizing remote procedure call semantics.
Claim 6
Dependent Claim
18 words
The method of claim 1 and further including the step of proving correctness of the lattice construction automatically.
Claim 7
Dependent Claim
18 words
The method of claim 1 and further including the step of proving correctness of the lattice construction manually.
Claim 8
Dependent Claim
157 words
A computing system comprising: (a) a plurality of computing means operatively coupled by an interconnection network means for communicating with one another, the network means including means for performing global memory access routing, request combining and response decombining; (b) each of the computing means having an instruction set including combinable operations and write back capability; (c) the computing means further having a virtual memory address translation mechanism for enforcing access constraints for segments or pages of memory, said constraints being selected from the group consisting of: (i) memory shared, but no caching allowed, (ii) memory protected and temporary exclusive caching with processor indicated write back, (iii) discretionary memory access controls with exclusive demanded authorization user access rights, (iv) mandatory memory access controls in which a user may read values at an assigned security level or lower, write values at said assigned security level or higher, and only invoke combinable operations on values at the assigned security level.
Claim 9
Dependent Claim
157 words
A computing system comprising: (a) a plurality of computing means operatively coupled by an interconnection network means for communicating with one another, the network means including means for performing global memory access routing, request combining and response decombining; (b) each of the computing means having an instruction set including combinable operations and write back capability; (c) the computing means further having a virtual memory address translation mechanism for enforcing access constraints for segments or pages of memory, said constraints being selected from the group consisting of: (i) memory shared, but no caching allowed, (ii) memory protected and temporary exclusive caching with processor indicated write back, (iii) discretionary memory access controls with exclusive demanded authorization user access rights, (iv) mandatory memory access controls in which a user may read values at an assigned security level or lower, write values at said assigned security level or higher, and only invoke combinable operations on values at the assigned security level.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-02-01 | 2002-08-03 | 2003-02-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-02-01 | 2006-08-03 | 2007-02-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-02-01 | 2010-08-03 | 2011-02-02 | $7700.00 | Window Closed / Lapsed |