Now that I've provided a short and sweet description of the F-Nets computational model, here are some reasons I think the F-Net model serves as an excellent starting point for concurrent programming (and specifically why I used it as the basis of ScalPL).
Architecture-Independent Communication
The memory model in F-Nets (expressed in the semantics of its resources) does not restrict or favor how data gets moved from one place to another, such as message passing or shared memory (or something in between). There is no assumption that data will be copied (with the commensurate overhead) as a byproduct of communication, as with message passing, nor is there any need to mess with (and wait for) locks, as with shared memory. Runtime systems can often dynamically trade off copying with blocking to optimize performance.
Variable Granularity
In large part because of the flexible and efficient communication model, there is virtually no penalty for using the same memory model for static data. As a result, if communicating entities are colocated, from a granularity perspective they essentially merge into one entity. This allows the granularity of the application to naturally increase (i.e. concurrency to shrink) to match the available concurrency in the platform.
Latency Tolerance
As in data flow models, the processing model together with the memory model does not dictate when data must be somewhere, or even specifically where it should be. It only states (or strongly suggests) what data and code must be together in one place before computation can occur. Data movement can all take place between tactic activations, rather than during them, so latency can be made to overlap with other computation within the runtime/scheduling system, and computation in progress never needs to stall waiting for data to arrive, consuming resources and perhaps interfering with other progress.
Language Independence
The processing and communication model ask nothing of the underlying computer language except to do what virtually all already do -- i.e. express a deterministic mapping (e.g. subroutine) from the initial values within some set of data structures (generally passed as arguments) to the final values within some (perhaps overlapping, perhaps identical) set of data structures (also generally arguments). Well, there is one other minor requirement: That the subroutine also assign a transition (color, control state, or name) to each of those data structures/arguments, which is easily done by adding a simple statement for that purpose to almost any imperative language. In fact, this makes F-Nets/ScalPL a fine mechanism for combining different languages in the same application.
Formal Semantics
Because of the simplicity of the memory model, and the fact that tactics are deterministic and each operate on a fixed set of resources, the model is easily described in terms of functions and sets, both axiomatically and operationally, without delving into the internal semantics of the language used to implement tactics. (Denotational semantics of the language would be used to define the precise function association with each tactic.)
Independence of Specification & Implementation
And because any implementation of a tactic which expresses a desired function is equivalent in terms of the semantics, the precise way it does it, and specifically the order or timing in which any implementation accesses (or declares a new control state for) different resources, is immaterial.: Implementors can code to a high-level specification, with significant latitude. That's very different than other approaches to concurrency, where the ordering of operations can mean the difference between (say) deadlock and none.
Structured Concurrency
Sequential computer languages are generally called structured if it the physical structure of the program (e.g. its indentation) immediately suggests (or restricts the possibilities for) its execution. More specifically, the program fairly obviously represents a folded up form of its possible executions. F-Nets are the extension of these same principles to the concurrent world.
Tamed Nondeterminism
Some concurrent languages (e.g. functional) don't permit the expression of nondeterminism. Others do, but in such an undisciplined way that it can easily "creep" into programs unintentionally, and regardless of how it gets there, it's hard to tell how it will affect the overall execution. There are clear ways to recognize possible nondeterminism within F-Nets, not only to ensure that the programmer has an opportunity to exclude it if desired, but also to optimize tracing to minimize overhead for so-called "instant replay" debugging. And even when there is nondeterminism, the semantics still allow for the analysis of the execution as a collection of functional evaluations.
I would challenge the reader to find another basis for concurrency which has all of these advantages.
No comments:
Post a Comment