Actors and ScalPL, again

I begin this post by noting that the price of the Scalable Planning book (describing ScalPL) has now been reduced to $24.95.  This is likely as cheap as you can expect to see it for some time, just barely recouping costs, and about 40% of what it sold for a little over a year ago.  So now's your chance.  (The ebook version is waiting until I am certain I can produce a quality version, including the fairly significant math notation in chapter 10.)

Some time ago, I commented on a video by Carl Hewitt regarding the Actor model (primarily theoretical aspects), and I may still comment on that further... but this post is regarding another video on actors,  from a recent Halmstad Colloquium, by Hewitt's former (many years ago) student, Gul Agha, who wrote a book on the subject in 1986, and who has since has been a professor at UIUC.  (I've had the pleasure benefiting from Gul's gracious hospitality on a few occasions over the years.)  This particular talk regards more practical matters relating to the Actor model, with the benefit of significant hindsight.  Dr. Agha seems honest here about how some implementations have fudged the rules, and how those who haven't fudged them have paid some performance penalties.

First, in three slides, Agha summarizes some of Actors' important characteristics, and explains their merits. In the first (at 5:18), Actors are described as concurrent (with one another), communicating with asynchronous message passing and no shared state.  In the next slide (at 8:40), he outlines basic principles, specifically: Encapsulation (of state by an actor), fairness (a.k.a. liveness, a guarantee that each sent message will eventually be received), location transparency (the independence of an actor's behavior from its physical location), and mobility (apparently related to the location actually being flexible during execution).  In the third slide (at 18:10), Agha brings this all down to how an Actor is typically implemented:  as "encapsulated state + behavior ('methods') + thread of control + mailbox".

Some of the merits are argued to be decreased complexity (with message interleavings being the only potential source of nondeterminism), tolerance of communication latency (the possibility of "hiding" message latency with other computation during transport), and portability (with actor addresses being independent of location or platform).  State encapsulation within an actor is likened to data hiding, a mainstay of software engineering (and OO programming).  The model is also said to facilitate mobility (which I assume means during execution).

Some of those benefits are actually not so clear to me.  For example, regarding the fairness constraint facilitating correctness:  The Actor model permits the creation of unlimited number of messages to be directed to an actor, but then also requires that every message be eventually handled (by that actor).  This implies that, regardless of how quickly an actor can handle each message, it may not be fast enough to satisfy the model's requirements.  That's a problem:  Even beyond the requirement cited by Agha of unbounded queuing, the queue could actually grow infinitely (unless the parallelism can grow infinitely).  I won't venture into the case when an actor doesn't terminate, and how/if this is formally different than an actor just refusing to handle more messages and violating fairness.

Also, while location-independent addressing (of actions) may aid mobility, mobility can actually be thwarted by the fact that an actor can maintain an unlimited and unobvious amount of persistent internal state, even while the actor is not active (i.e. while awaiting another message).  It means there are essentially two kinds of state to be moved around, in completely different ways and under different circumstances:  The state within a message, and that within an actor.  And moving intra-actor state, especially to another kind of processor architecture, can be difficult at best.

Even some of the cited merits have corresponding drawbacks.  For example, while data hiding is an important software engineering principle (in sequential programming), part of the state hidden within an actor is the set of actors with which that actor may communicate.  So the entire communication and control topology of the program is hidden within actors -- and that is actually completely antithetical to engineering principles of structured systems.  And since there is no limitation on the size or persistence of the state within an actor, the only way to characterize that hidden state (including the state representing the actors with which it may communicate) is in terms of the sequence of all of the messages that the actor has ever received throughout its history.  This makes the propagation and transformation of state during an execution very difficult to track without knowing a lot about (and keeping track of) what's happening inside of each actor.

Dr. Agha also mentions the significant overhead associated with the required "by value" messages (with payload), which is avoidable in other models for communication between co-located procedures, in cases where they could just share access to a common area ("by reference").  Agha suggests a potential solution where static analysis could theoretically determine when an actual message transfer (copy) could be avoided, implementing sharing under the covers. This static analysis is much easier said than done, and something which has been proposed for decades with other models (e.g. Linda) while never very successfully implemented (without hardware support).

These issues are hardly new.  When I was devising the F-Nets computational model around 1990 (see chapter 10 of the Scalable Planning book for a rewrite of my 1991 dissertation), it was already addressing many of these drawbacks, seen in most message-passing programs, with the rest (and others) addressed by its more complete language, ScalPL (Scalable Planning Language), shortly thereafter.  (Described in the same book and many posts in this blog.)  And, ScalPL retains the advantages of Actors cited above, but in addition:

• ScalPL more cleanly handles data hiding by offering two kinds of "plans" (i.e. program fragments), called "tactics" and "strategies".  Tactics, which are essentially functions or methods implemented with traditional sequential programming languages, have short-lived activations/evaluations ("actons"), and don't hide or maintain any state between activations; Strategies, are graphically built in ScalPL itself of other plans (tactics and strategies), and are generally long-lived and do maintain/hide state internally, in "resources".  Since strategies have clean interfaces, with just a few simple additional constructs, they also serve as classes and their instances (objects).
• The stateless and functional nature of tactics in ScalPL, together with the clear graphical representation (within strategies) of how they interact with resources and therefore with each other, makes the flow of both state and control clear, to both the human and automated analyst, allowing optimizations for efficient data sharing and/or migration without delving into the innards of the tactic implementations.  These features make ScalPL potentially the closest representation to structured programming available in the concurrent/parallel world.  It is essentially an executable software engineering diagram.
• Those same ScalPL resources also serve to preserve state (as necessary) for tactics between activations, with negligible overhead.  Since ScalPL strategies are composed only of these resources and other subplans (tactics and strategies) which access them, everything is ultimately built from just resources and tactics, leading to true mobility:  Everything that might need to be moved is either a tactic (which is stateless, and therefore basically constant data, between activations), a resource (which is designed for mobility, acting as a message when necessary), or a strategy (which is ultimately composed of the previous two).
• Fairness in ScalPL takes the form "if a tactic is continuously activateable, then it eventually will activate".  Unlike Actors, since resources -- i.e. the connections between tactics -- are not (in essence) queues, data results of one component generally can't pile up unboundedly to be forced upon non-ready downstream tactics.  Instead, upstream components must wait (i.e. won't be activateable) for downstream results to be consumed unless circumstances permit queuing (explicitly or implicitly) of prior results.
• In the video, Dr. Agha mentions the merits of sharing a thread among multiple actors, as an optimization, as opposed to one actor per thread.  In ScalPL, since tactics (actons) are atomic and maintain no state between activations, they are short-lived "threadlets", and an implementor is not even tempted to devote a long-lived thread to each one.

And with ScalPL, that's all with no mailboxes (or locks) to mess with, and an underlying formal computational model (similar to Petri nets), all while offering the other advantages claimed here for actors.  And although the tactics in ScalPL are described here as "atomic" and "functional", this does not imply overheads associated with checkpointing and roll-back, or the use of functional languages (e.g. lacking "update in place" semantics).  As the ScalPL book explains, the default execution model can be about as efficient as a standard function call, and implemented in your favorite imperative language.

I will be happy to receive information from, or engage in discussion with, those who find my observations here unfounded.  I find the Actors model an important step in the progress of our knowledge of parallelism, in part because it can be used to describe so many traditional message-passing programs which possess its basic attributes.  (The same cannot be said for ScalPL:  It does not pretend to explain existing programs developed without knowledge of the model.)  That said, I do hope that today's increased hardware technology and available parallelism are matched by advances in programming technologies.

Scalable Planning (ScalPL) Book Price Reduced

I figure the early early adopters have had their chance, so I've reduced the price of my book, "Scalable Planning: Concurrent Action from Elemental Thinking," from $65 to $45 for the later early adopters!  And if you use the 20% discount code available at elepar.com (before it goes away), that's actually more like $36 -- about half the original price.  Plenty more info about the book on this blog and at the elepar website.  Questions and feedback are welcome.

Video of ScalPL presentation to the Zissou Society

The motto "Keep Portland Weird" even applies to computer languages, if "weird" can mean "eclectic" -- just witness The Zissou Society for Programming Language Exploration... or pdxlang for short.  How eclectic? Well, Haskell would be considered practically a mainstream language here in Portland, so probably wouldn't qualify.  Anyway, ScalPL (as described on this blog and the Scalable Planning book) was deemed weird... um, I mean eclectic enough to merit a presentation (immediately following a presentation on m4) last Thursday.  And here is the screen capture of that presentation.

This was my first attempt at screen cap, so it's not perfect.  Also, due to time constraints, the OO concepts at the end aren't especially well covered:  Look for another vid later to do a better job on that.  But if you are looking for a pretty thorough intro on what ScalPL is all about, here's a 72-minute presentation, followed by a 10-minute Q&A.  (No significant background in parallel processing is assumed.)

Feedback here is welcome.

ScalPL and the Sequential Prison

A former colleague (and his associates) recently referred me to this video/slide presentation:  Ivan Sutherland, The Sequential Prison, at the SPLASH 2011 conference.  I met Dr. Sutherland once some months ago at an alumni event at Portland State University, and understood that there was an overlap in our work, but this presentation provided an opportunity to understand how much.

The talk contains few very concrete or completely novel recommendations, but even it its generality, it's worth a listen, and it is clear that the speaker and I are on the same wavelength more often than not.  He discusses his intuition that the form of our traditional human and computer languages, together with specific words in them, affect our approach to problem solving as a sequential endeavor, and that a more picture-oriented language would help to avoid this "sequential prison" that we've locked ourselves into.  When questioned later about functional languages, he mentions how much they seem to be built around the concept of sequences, and how this also affects the tendency to build and process things serially.

As might be apparent from my work described on this blog, I agree with all of that.  Even things we don't agree on exactly, we agree on vaguely.  For example, in the parallel (or concurrent) world, he prefers the term "configuration" over "program".  While I, also, tend to avoid terms like program and algorithm as being too sequential in heritage, I use the term "plan" in general and "strategy" as a more specific form of plan.  Ivan seems to suggest that picture-oriented languages might require multiple simple forms to convey a single concept in enough specificity to facilitate execution, while my work in ScalPL concentrates on a single, rather technically annotated form, in part as an alternative to the complexities I've seen in the multi-view forms of UML and the like.  Whether ScalPL (or more specifically, my ScalPL diagrams) are meaningful and easy to read, whether they would "leap into" Dr. Sutherland's mind as he requests, I can't say, but I do think they capture the spirit:  Pipelines do look like pipelines, concurrency does look like concurrency -- to me, anyway -- as he requests.  Other representations (such as he requests) are (can be) assembled by the planning tools.


His discussion starting at 30 minutes or so is very descriptive of ScalPL, though he seems to be addressing primarily hardware.  In fact, the sort on page 279 of my Scalable Planning book (here, to the left) seems (to me) to be exactly the sort that he seems to describe there, but where he describes it as an instruction, it is here a ScalPL strategy.  The first question (in Q&A near the end of the video) relates to the difference between hardware and software, with the old impression that the software and hardware are different beasts, that software is too dynamic, too fluid, too soft, to draw the same way we do with hardware. I have not found that to be the slightest problem in my work.

Of course, his discussion of standardization is also well taken.  ScalPL is available.

How ex-treme is exa-scale?

[I drafted this some months ago, but for some reason didn't post it. It still looks good to me, so here goes.]

At the SC12 conference in November, I attended a couple of BoFs (Birds of a Feather meetings) regarding exascale. The first, an Open Community Runtime (OCR) for Exascale, was helpful in providing pointers, such as to this website which in turn points to slides, which in turn led me to sites for Intel's Concurrent Collectives (CnC) (including UTK) and University of Delaware Codelets/Runnemede work. But I found myself wincing at some of the things said during the BoF, and after looking at these sites and documents, I admit to being disappointed and, frankly, frustrated. This perhaps became even more pronounced in the second BoF, Resilience for Extreme-scale High-performance Computing. (In hindsight, there are others I wish I had caught.)

First, I would contend that even if we were to come up with a design for The Correct Programming Model(tm) and The Correct Runtime Support(tm) today, it could still realistically take until 2020* or so to develop the appropriate software, support, migration, software engineering techniques (debugging, tracing, patterns, methodologies, libraries, etc.) to make them useful. So there's no time to lose. And from what I was seeing, these groups are not only a long way from having The Correct design, in some ways they seem to be actually going back into history. More specifics about that in an upcoming blog entry.

(*As I write this, I find that the 2020 goal may be more like 2022, but my argument still holds.)

Second, in order to come up with The Correct design, we must understand the critical constraints, not saddle ourselves with non-critical ones and unwarranted assumptions. This is where people like Seymour Cray (starting with "a clean sheet of paper") and Steve Jobs (whether considered a visionary, big thinker, or "tweaker") excelled. Instead, in these meetings, I was hearing "requirements" such as the ability to run MPI programs effectively, or the desirability (necessity?) to use checkpoint/restart to achieve resilience. Even if backwards compatibility may be desirable in some cases, and existing practice may be a useful jumping off point, we will get nowhere by using them to guide the design.


Third, but strongly related to the above, it struck me that I was seeing lots of familiar faces in these BoFs, mostly from my days (a decade+ ago) on the MPI2 Forum. And while reconnecting with former colleagues is part of what the SC conferences are all about, using a standards-based approach is almost certainly not the best way to make significant advances in technology. New approaches will be required to achieve the goals, and standards for those can be established only after those goals are attained. (I could further argue that existing standards have artificially interfered with our progress in this field in other ways, but I'll save that rant for another day, except to say that standards committees are constantly bombarded with the reminder that their job is to standardize existing practice, often while maintaining compatibility with previous versions of the standard. That's not the recipe for quantum leaps!)

So what is the most effective way to achieve the exascale software goals? One might take a hint from Seymour Cray, in the link above: "Shunning committees, he felt that the best computers were the ones where a single architect offered a unified vision. After the machine had been delivered, it was then appropriate, Mr. Cray felt, to listen to feedback from customers and, if necessary, start over from 'a clean sheet of paper.'" I claim that there is no reason to assume that the same wouldn't also be true for software.

In other words, try some big ideas, in multiple (at least two) stages, assume that you may not succeed in the early (e.g. first) attempt, but will learn a lot nonetheless, and integrate what you learn into later stages. That is, in fact, how we fashioned the strategy for NASA's Information Power Grid (back when I had some influence there)... before that plan was apparently revised (and discarded?).

Of course, it could be argued that this "think big with master architect" approach is precisely that which was applied in DARPA's HPCS program, by funding individual companies and allowing them full control over their product/proposal. It could also be argued that that program (has) had limited success (though I would hardly call it a failure). And to those arguments, I would counter that the goals that were not conservative were underspecified. There was little advantage to the participants adding more objectives than those provided by the sponsors, and in fact, disadvantages, in that their competitors for the funds would then be working toward simpler goals.

If failure is not an option, then the goals are too conservative. Consider the manned lunar program: HUGE goals, and a really concrete way to measure if we'd achieved them or not. We were proud to meet them, but it was by no means assured. The exascale project has set some very high hurdles regarding power consumption/energy and reliability/resilience, which seem to fit into this model, but again, at least the goals I've seen on programmability are either conservative or vague or both. Of course, in a political climate, failure to meet a goal can be painful. And where there is public money, there is (and should be) politics.


And, like the moon landing, the trade-off between expense and benefits of attempting to meet (or actually meeting) the goals is a separate issue from whether the goals can be met at all, and the balance is not necessarily clear-cut. If the US government is the customer, they must decide how much it is worth to them, and other participants must decide if it fits their business (and/or research) model. The manned space program was run from within the government. Such a model seems unlikely today.

How about data movement? (For real, this time.)

In the previous post, I addressed the kinds of inherent constraints that an F-Net (and/or ScalPL) plan imposes (and does not impose) on data movement.  The question then becomes how to turn these constraints into an implementation:  Sooner or later, the decision to move or not move each data item must be made to meet the constraints, and something must make those decisions.

The most basic way to meet the constraints is by assigning all the computations (actons) to one processor, putting all the data (resources) into its local memory, and executing the whole thing sequentially.  Unlike some other models (like most message passing) with semantics that intrinsically impose additional copying and/or data movement, or that require context switching between heavyweight address spaces, this sequential execution of F-Nets requires little if any overhead over a native sequential expression of the same computation, either for data movement/copying or context switching. In F-Nets, if a sub-computation/acton is going to complete at all, it can always be executed to completion before moving on to any other subcomputation/acton, and there is no need to save transient/intermediate state in this case.  So the only need for more heavyweight context switching is when an acton diverges ("infinitely loops") or appears it may do so. (Most message passing requires data copying or movement even in a sequential environment, because both the sender and receiver are assumed to have their own mutable copy of the message after the communication, and may both be required to make progress for the overall computation to progress.)

But in the more common case where we want an F-Net/ScalPL plan to exploit the parallelism of a platform, how best to decide how (and when) to embed the plan (program or strategy) onto that platform?  In the good old days, parallel programmers made several assumptions about both the platform and the algorithm to simplify this embedding process:  We assumed that the platform consisted of a fixed number of heterogeneous, dedicated, fault-free general-purpose processors connected with a predictable, regular communication topology.  We also often modeled the application/plan as a set (and usually a sequence) of parallelized steps ("epochs", phases) such as array operations, where each potentially-concurrent operation in a step took about as long as any other operation in that step to complete.  Based on such assumptions, it was sometimes viable to statically map the computations and their associated data onto the processors in the platform.

Under those same assumptions, an F-Net or ScalPL plan can also be statically embedded on a platform in similar ways.  Rather than assigning resources to processors (as some languages might assign array elements under an "owner computes"-like rule), it makes far more sense to assign the computations themselves -- i.e. actons -- to processors, by annotating their contexts.  Another approach is to assign each control state of each resource to a processor.  In either of these cases, the constraint (implied in the F-Net itself) that the content state of a resource must be colocated with the acton during execution, is assumed, and annotations which suggest conflict to this can be resolved in a number of sensible ways (e.g. majority rules).  In ScalPL, by allowing these annotations to include the index values supplied by so-called "dup bindings", such embeddings can be a function of the array elements processed, so are no less expressive than those in HPF, etc.

Even so, just as can crop up in deep subroutine calls in HPF, the hierarchical and dynamic nature of ScalPL means that different (perhaps recursive) activations of the same plan (strategy, program) may be best assigned to different parts of the platform, yet preferably related to the embedding of their parent activation in sensible ways -- so static labeling of contexts isn't necessarily sufficient.  This can be at least partially addressed by a simplified parameter passing -- i.e. providing special (integer) variables in child plans which are set equal to the annotation of the context in the parent, and which the child can then use (e.g. in mathematical expressions) when annotating its own contexts.

Even better is to consider representing the overall embedding as a two-step process, the first as mapping the computations to an abstract platform, which is considered to have easily-understood internode properties, and the second as mapping that abstract platform to a concrete/actual one to hopefully preserve as many of those properties as possible.  My work has focused on an abstract platform (AP) representation of nodes addressed by finite sequences of non-negative integers, allowing the AP topology to be interpreted in a number of ways -- e.g. as a sequence/cycle (e.g. if just single integers), or a rectangular grid (e.g. if tuples of integers), or a tree (e.g. with zero-length sequence representing the root, any other sequence representing a descendant of all nodes addressed by its prefix sequences).  The annotation/parameter passing described in the previous paragraph can now be of these sequences, instead of integers, with the child able to append new suffixes to the sequence it was passed.  Mapping of the AP to the actual platform can be manual or automated, based on various assumptions. A common shorthand is to assign all nodes having the same prefix to a particular actual processor, which can be interpreted as assigning an entire row or column (if the AP is considered a grid) or subtree (if the AP is considered a tree) to that node.  (People who are accustomed to HPF and similar embedding languages may feel it lacks constructs for transpose, etc., but (a) these would be handled in embedding to the AP, not mapping the AP to the actual architecture, and (b) such a transpose, if necessary at all, is imposed by mapping the pre-transpose computations and post-transpose computations to appropriate nodes, since mappings effectively change between steps rather than within them.)

But that leaves two important points.  The first is that the traditional simplifying assumptions for parallel static embedding (summarized in the third paragraph, above) are virtually all unrealistic these days.  Applications for concurrency are no longer confined to scientific and/or matrix operations, so their concurrency is no longer regular in shape or uniform in subcomputation duration.  And this irregularity, together with increased concurrency, makes it less practical to devote entire machines (or portions thereof) to specific applications, so node sharing (yielding variable loads) must also be accommodated.  And as platforms grow ever larger, it becomes less practical to make them heterogeneous and fault-free. The bottom line is that static embedding becomes all but impractical:  These embedding decisions must be made at runtime, in real time.  Using the two-step process mentioned above, only the mapping of the AP to the concrete platform must be dynamically determined.

And the second point, related to the first, is that making such dynamic embedding decisions on a fine-grained basis is also impractical.  This is another reason for facilitating non-trivial, large-granularity subcomputations as the basis for embedding.  And that, in turn, requires that these subcomputations be  more flexible and expressive than traditional data flow-- e.g. allowed to produce multiple results (to each potentially be directed to different downstream subcomputations), and results which affect only parts of larger data structures.  This is a prime motivation behind the structural properties which have been endowed upon actons (the subcomputations) in F-Nets/ScalPL.  Because these actons are typically entire subcomputations/subprograms in themselves, the embedding decisions within an acton to a single processor (to memory, registers, logical units, etc.) to carry them out can be performed statically and locally, such as by compiler, or if necessary, by OoO scheduling within the processor. These local, lightweight decisions are, by now, well understood.

So that is the answer to how data movement is determined within an F-Nets/ScalPL plan (i.e. strategy, potentially consisting of sub-strategies, ultimately down to actons):  This balance, between explicit parameterized embedding of a strategy/plan to an Abstract Platform, dynamic (or, in restricted cases, static) embedding of the AP to a concrete platform, and traditional compiler/processor scheduling of processor resources for each acton within the strategy/plan.  The book goes into some depth in describing an entity known as The Director, and how it can efficiently determine when to move data. There is also significant discussion on how to optimize the movement of data depending on architecture type (e.g. shared vs distributed memory) and the form of the strategy (e.g. with multiple readers of a single resource, readers and writers, etc.)

What about data movement?

I received a recent question from someone quite familiar with the fields of high-performance computing and data flow, so I figured others might share his same concerns, and answering here might kill more birds than a personal reply.  (Just in case there are privacy concerns, I'll not cite his precise name or words.)

It included statements with which I wholeheartedly agree -- e.g. that data movement is very expensive in modern compute environments (e.g. relative to local computation).  He says that the F-Net model doesn't say anything about when and where data should move, which he says is required of any modern model.

It is, in fact, a central goal of F-Nets (and ScalPL) to put as few constraints as possible on how and when data might move in order to carry out the specified plan (aka execute the program, evaluate the mapping or calculation) -- but enough constraints so that the plan can be efficiently implemented on different platforms (e.g. shared and distributed memory) by knowing (in advance, when possible) when colocation of data and program/plan fragments must occur.  Even the term "data movement" might be confusing here, in that the model doesn't preclude moving parts of the plan itself instead of the data upon which those parts operate -- but those, too, can be considered as data during movement.  F-Nets/ScalPL is all about expressing (without overexpressing) those constraints -- i.e. the kinds of access each subcomputation (acton) will need to which data (resources), and (assuming that each subcomputation (acton) is to be statically evaluated without migration) the data and program fragments that need to be colocated for this to occur.  It is designed to be neither too much nor too little information.

One can be forgiven for assuming that satisfactory forms of portable algorithmic expression already exist, e.g. functional or dataflow languages.  As a brief overview: Languages and models fall broadly into control flow and data flow camps, where the former defines what gets to evaluate next based on a program counter (the functions called or objects invoked/messaged), and the latter defines it based on which data is available to compute with.  Functional languages are closely related to dataflow languages, but the interpretation of a variable is slightly different, as simply a shorthand for an entity like a numeric value or subfunction, rather than a dynamic entity which becomes filled/defined or not.  Traditional parallel constructs (e.g. messages or shared memory) are often sort of a hybrid between control and data flow, where there are several locusts of control ("threads") that are selectively intentionally blocked when necessary to wait for data to become available (from another thread).

Data flow approaches are traditionally facilitated by single-assignment variables (or arcs) that change state to signify when data is available there for use by downstream calculation.  (Lazy and non-strict evaluation can allow evaluation to progress even when some of the potentially-needed data isn't available.)  But as indicated by the nomenclature, the variables can be assigned to only once (or simply used/considered as shorthand for another expression), in essence ignoring a central feature of virtually all computing hardware, including those in nature:  Mutable memory, the ability to change the contents or character of something stored without changing where it is stored.  As a result, when only part of a large datum is being altered in these languages, the entire result must be defined in terms of the entire previous value -- very unlike what needs to actually happen internally for any efficiency. That is, assignment to a data flow variable has nothing much to do with updating storage, but rather with signaling the availability of the data to some part of the program. Because this signaling is integrated into the assignment, it is impossible (or unnatural) to signal availability without assignment, or to assign without signaling availability.

These shortcomings are not always obvious in examples.  For example, functions (or algorithms) which are primarily mathematical in nature (e.g. produce a single deterministic result from many arguments), and which don't benefit by partial assignment and/or update in place don't really need anything more that traditional data flow.  However, in real world programming, operations often produce multiple results, perhaps each destined for different downstream computations, and each of those results often provides only part of an overall datum, a datum which may be partially or completely updated by several computations during its lifetime -- plus, any particular datum might best be updated on a first-come first-served basis, rather than some deterministic order.  These are not so natural for data flow languages and/or approaches.

F-Nets and ScalPL overcome these constraints fairly directly by providing separate constructs for the control state (i.e. accessibility) and the content state (i.e. content) of a variable.  The control state is related to the flow of control, and content state, the flow of data, and like traditional data flow models, both are related to the variable (called a resource), rather than to an independent control flow.   By allowing manipulation of control state and content state explicitly and independently, flexibility, efficiency, and portability ensue.

It does introduce some complications.  Can a single construct still really represent either broadcast (or multicast) and shared readers?  How about buffering on distributed systems while avoiding extra overhead of queuing in shared memory?  Read and write locks?  (Can making an extra copy be made semantically and syntactically identical to blocking writers waiting for readers to finish?)  And all in the presence of non-terminating functions and Turing undecidability?  And while hiding latency on platforms and applications where that applies?  It takes some finesse in definitions, but it can all be done, and these fine points are the essence of F-Nets.

OK, fine, even assuming I've convinced you that F-Nets/ScalPL is a great portable representation, it still begs the original question:  How, when, and by what, does the issue of data movement actually get settled?  I'll address some of that in the next entry.  (A more complete explanation is in chapters 4 and 5 of the book.)

SC12: Exascale holy grail?

I recently returned from the SC12 (Supercomputing 2012) conference.

As last year, GPUs were a big topic of discussion, but this time, much of the novelty, magic, and infatuation seemed to have worn off, leaving more practical "how to" questions and concerns.  The other big talk of the conference (for many of us) was "exascale", the challenge being mounted by the government (DOE/NNSA) to build an exascale computer by 2020 or so.

There are a few major challenges here, some which may be downright impossible to meet.  The goal is not just to put together something that can theoretically deliver an exaflops -- that is 1,000,000,000,000,000,000 flops (floating point operations per second), a thousand petaflops, a million teraflops, etc. -- on some theoretical application.  It is also to be able to power it ("energy" goal, sic), program it, keep it running ("resilience" goal), and ensure that applications/hardware/OS all work together ("co-design" goal).  In other words, it must be (in some sense) practical, to someone.

Even just attaining the energy goal -- to power the machine with 20MW -- seems nearly impossible, in that it must be 20-50 times more efficient per flop than what we've got now.  Bill Dally (now of NVIDIA) argued (in an exhibit talk) how we/they could possibly reach that goal by continuing current technology trends, but even then, only under some pretty optimistic assumptions.  He illustrated that the power drain on current computers is not so much in the arithmetic units, but the data movement, especially to and from memory, but also just to register files, etc.  In his own keynote, William Harrod of DOE publicly doubted Dally's reasoning that evolutionary approaches will be sufficient, and it seems clear that even if we can get Dally's predicted performance efficiency in the raw hardware, he didn't adequately factor in the overhead for resilience or runtime support to exploit parallelism (e.g. to enforce runtime dependences).

Harrod's keynote was also interesting in its honesty, that there was probably no market for this machine other than the US government.  For that reason, he said that the government would have to invest big bucks, but he seemed unsure of how much, or how much support there was with this congress and in this economic climate to invest/grant it.  Still, he suggested that such a machine had commercial drivers:  For example, if you take 1/1000 of the machine, you could put a petaflops in a closet, which many businesses might find useful.  I would make a few observations here:

1. Harrod's claim that there will be no market seems eerily reminiscent of T. J. Watson's quote of 1958, "I think there is a world market for about five computers."  But perhaps Harrod wasn't claiming there would never be a market, just that market forces would not be enough to drive development of this computer on the government's desired timeline.
2. There are market forces for some of the goals, but not all of them.  For example, meeting the energy and co-design goals will help even with a smaller (1 petaflops) systems.  But resilience, for example, will be wasted on a smaller system.  If an N-machine system (e.g. a system of 1000 1-petaflops machines) is considered to fail when any one of the machines fails, then to reach any particular reliability (say less than f probability of failure within 1 time unit), the N machines must individually have a much higher reliability independently (less than 1-(1-f)^N probability of failure in that same time unit).  Perhaps the government grants should focus primarily on these unique factors which are unlikely to pay off for anybody but the government.
3. I was also somewhat disappointed by where and how government funding was intended (and was apparently already, in the Fast Forward program) to be invested, primarily in large companies and universities, but I am willing to accept that I misunderstood, or that this could change over time.

I will post more on this topic, primarily because some information from BOFs (Birds of a Feather meetings) at the conference suggests that groups currently addressing these exaflops goals aren't fully understanding the challenges before them, and are therefore failing to react adequately, in my opinion, hanging onto failed and outdated approaches in hopes that exaflops will look much like current platforms.  Perhaps needless to say, I also believe that approaches outlined in the my Scalable Planning book (e.g. ScalPL) do directly address these challenges, even more than I suggested previously.

Actors vs ScalPL tactics: Hidden state vs WYSIWYG

I stumbled into a video via Google+ the other day, an informal discussion with Carl Hewitt explaining "The Actor Model (everything you wanted to know, but were afraid to ask)".  This seemed a good opportunity to refresh my memory from when I looked in the late 80s, to catch up with any newer changes/additions, and to compare Actors with F-Nets.  I also consulted the Wikipedia entry, and a paper which Dr. Hewitt recommended in the comments section.  (I did not consult much of the more extensive written documentation, like Hewitt's and/or Agha's books, so I do not pretend to be fully up on all aspects of this work.)

The basis of the abstract model is that an actor, upon receiving a message, can do three things:  Create more actors, send messages to actors it knows, and designate what it (the actor with this address) is to do with the next message it receives.  And, from what I could ascertain, an actor knows the addresses of other actors it creates, as well as any addresses that it receives in messages, plus (presumably?) its own address.

From my own work, it seems clear what at least some of the intent is:  Abstractly, to make immaterial the order in which the actor performs any/all of those activity components (creations, sends, and new behavior specifications). That's a worthwhile benefit, and leads to (some) separation of specification from implementation:  Any implementation which does those same things in response to the same messages, regardless of the order or timing of those things relative to one another, is effectively equivalent in a system, and conversely, an actor can be considered as a function from the history of all the messages it has received so far to the set of new actors created and new messages sent as a result of the most recent message.  (The "new behavior" component is not immediately observable:  It just further defines that function -- i.e. the new actors and messages it should produce when given even more message history.)  And because the actor's receipt of a message is essentially atomic, and the actor's behavior in response to that message is functional, that entire "receipt+sends+creations" collection can also be considered abstractly as one atomic action.

Those are nice attributes.  But they pale in comparison to what ScalPL (and the F-Nets model upon which it is based) offers along similar lines.  Perhaps that shouldn't be surprising:  Actors predates ScalPL, and apparently even its ancestors.  In ScalPL, an actor would correspond roughly to a plan, and a plan, in turn, is either a strategy or a tactic.  For the remainder of this entry, I'll primarily limit my discussion to tactics.

A ScalPL tactic can be made to react to any number of specific resources becoming ready (e.g. containing "input"):  There's no advantage to making that exactly one (like the actor model, considering the receipt of a message as being equivalent to a resource becoming available), but no harm in making it one, either.   Like an actor, a tactic can also be specified as a function, but unlike an actor, not (generally) a function of the history of messages it has received; instead, a function of the data ("input messages" in actor-speak) it's observing right now, specifying the results ("output messages") it will produce right now as a response.  In other words, it's pretty much just your normal everyday function, with no hidden state.  In fact, the data a tactic observes (i.e. its inputs) and that it produces (its outputs) can be (all or part) on the very same resources (think "variables" or "files"), so the specification of an input-to-output transformation for a particular resource can just be a specification of the changes (i.e. updates) that need to be performed to the contents of that resource.  That should look very familiar:  It's the way ordinary imperative programs generally deal with memory, observing (reading) and updating (writing) all or part of it in place, instead of sending messages around from place to place.  (The semantics of inter-tactic communication in ScalPL/F-Nets is carefully designed to be easily and efficiently implementable as messages, too, if the situation calls for it, but that is a detail generally unimportant to the planner/programmer.)

Of course, if one wants to make a tactic with behavior that (like an actor) depends upon its history as well as its new/current input(s), it's easy to do:  Just consider/use one or more resources as the salient parts of its history, and have the tactic observe and update those resources as it does others containing inputs and outputs. (No, it would not really be equivalent to restricting actors to also be functional, and just constantly sending their history back to themselves in messages:  Actor messages have different, heavier semantics than ScalPL resource updates.)

To bring this home, consider you have a person (or even a robot), and you know that its behavior in response to its environment at any one time is a combination of its nature (how it was built) and nurture (everything that's ever happened to it in the past).  Even if you know how it began (i.e its nature), and what its current environment is like, unless you also know its nurture (entire history), you have little idea how it will currently respond to its environment.  That's the actor case -- or, for that matter, most imperative programming in general, as I hope to address later.  In the tactic case, its nature does not change and there is no nurture component:  If you know what the tactic was (and therefore still is), and what its environment is, you know how it will behave.  There's no hidden state (e.g. history), it's very WYSIWYG (What You See Is What You Get).

As for creating other tactics (the way an actor creates other actors):  A ScalPL tactic does not create other tactics first-hand, for some of the same WYSIWYG reasons that tactics don't depend on history.  That is, all relationships in ScalPL are intended to be illustrated/visualized/specified in its visual representation, rather than hidden inside of one or more tactics.  So if a tactic is meant to become active at some point, it and its (eventual) relationship to other tactics and resources is specified (graphically) from the beginning.  The effect of creating (activating) a tactic results (again, in a clear diagrammatic fashion) from another tactic altering a resource they have in common, thereby awakening the until-then quiescent tactic.  (It the potential relationships aren't known from the beginning, there are ways to create those relationships, too, within strategies, just as there are ways to hide history within one, but that's for another post.)

I can (and probably will) discuss the Actors video further in this blog, but the main thing I hope you get from this specific post is that ScalPL incorporates a WYSIWYG approach to (a) how a plan will behave now in response to its current environment, (b) where it might get its inputs from, (c) where its results might be felt, and (d) what other plans might be activated as a result.  Unlike Actors, ScalPL does not hide information like the above within a the tactic (e.g. in terms of its accumulated state over history, including the addresses that it knows or uses), is not limited to a message model, and it is not limited to one input per tactic activation.

Video summary of the Scalable Planning book (intro chapter)

A 13-minute description of the book (summarizing the first chapter).

From near the end...

"The Scalable Planning book isn't your typical parallel programming textbook, but it is built with that use in mind.  If you don't know anything about programming, that's OK:  It introduces all terminology, and avoids too much lingo.  But if you are using it to teach or to self-learn parallel programming, you should ask yourself:  Should concurrency concepts be taught the same way they were 30 years ago?  Programming curricula these days rarely start with machine language and assembler:  Should today's parallel programming curricula be saddled with their analogs, message passing, semaphores, and locking?  Here, my answers are no:  There are chapters to cover the lower-level mechanisms if you want to go there, but the focus here is on higher-level concepts, on constructing correct, portable, understandable, efficient programs (plans), leaving the low-level details to others.  As a result, it is organized much like other sequential programming texts, with chapters on topics like structured programming, object-oriented principles, arrays and dynamic resource allocation, and formal methods, but in a concurrent context."

ScalPL for exaFLOpS

I stumbled into this interesting video, "Jack Dongarra: On the Future of High Performance Computing", from the recent SPEEDUP Workshop at ETH Zurich.  I listen to Jack at almost every chance I get, and if you want to know where the very highest performing machines are going in the next 20 years, he tells you here.  I highly recommend watching the whole talk.

On slide 15 (starting at about 30:35 in), he lays out some of the critical issues he sees for peta and exascale computing.  At risk of copyright infringement, I'm going to list his six bullets here:

• Synchronization-reducing algorithms
• Communication-reducing algorithms
• Mixed Precision methods
• Autotuning
• Fault resilient algorithms
• Reproducibility of results

ScalPL (Scalable Planning Language, explained in this blog and the new book) addresses five of these six points.  (The one it doesn't address: "Mixed Precision methods".  After hearing him speak on that topic last year at SC11, it looks too closely aligned with the algorithm itself and numerical analysis/methods work to benefit much from within the runtime system.)

To be fair, it appears that Dr. Dongarra is often referring to algorithm development to address many of these issues, but tools and runtime can offer significant leverage. For example, virtually all of ScalPL is centered around expressing the algorithm in a platform-independent format so that synchronization and communication can be dynamically optimized and reduced to the minimum required by the algorithm and platform themselves.  That addresses the first two points.  For the autotuning point, (1) "actons" (processes, threads) within ScalPL are functional, and can therefore be independently profiled and modeled to predict their behavior for optimal scheduling, and (2) the scheduling of those actons in a "strategy" (network) can be traced/instrumented efficiently (after static analysis) to help such analyses.

ScalPL really kicks in for the last two points.  It can theoretically help with fault detection (e.g. by comparing results of duplicate executions), but that aspect will likely be more effectively addressed via hardware.   However, when faults are detected, ScalPL provides (through a technique called supplemental re-execution in the book) a means of preserving the work that has been done, with no global checkpoint/restart, and limited data redundancy to emulate safe storage (for resource contents).  And as for reproducibility of results, the book contains an entire chapter examining the implications of determinism and ways to guarantee it, even categorizing types of nondeterminism.

Later in this same talk, at about 35:30, Dongarra talks some about using a DAG (directed acyclic graph) of dependences between tasks to dynamically schedule the larger problems.  This is specifically what ScalPL is made for.  (The book generally just refers to the DAGs as "computations".)  In fact, I mentioned in a recent blog post that even homogeneous machines can benefit from dynamic dataflow scheduling instead of static synchronized "loop at a time" scheduling.  (I was going to call it "fork-join parallelism" in that post, as Jack does in his talk, but web references to that term often confuse it with a form of recursion.)  Dongarra's talk here illustrates exactly what I was talking about.

(I might mention that Dongarra and I have been on parallel paths on these issues for quite awhile.  Back in the late 80s, he and Danny Sorensen were working on a tool called SCHEDULE to facilitate such DAG-related scheduling, while Robbie Babb and I were working on LGDF/Large Grain Data Flow to help automatically generate such DAGs in an architecture-independent fashion.  Both his work in this video, and ScalPL in my book, seem to be natural progressions of each of those.)

I guess the point I'm hoping to get across here is that ScalPL's best days are ahead of it.  It is here to address the issues of the coming decades of computing.

Scalable Planning Language (ScalPL) = F-Nets + ...

I recently described F-Nets, as well as some reasons I preferred that model to serve as the basis for concurrent/parallel programming.  But I obviously didn't think it was sufficient on its own, or I would have stopped there. So, just what is ScalPL, and how is it different (superior to) F-Nets for programming?  It starts with F-Nets, and adds...

---

Modularity
Instead of activating just tactics within a context, in ScalPL an entire F-Net fragment (i.e. a network of tactics and resources) called a strategy can activate within a context.  In other words, a strategy combines other constructs into a single entity/module, and ScalPL defines how the activity (resulting from its activation) interfaces to its context's surroundings (via the role bindings on that context). Among other things, this means that we can create a module (strategy) to behave any way we like with regards to patterns of accepting inputs or producing outputs, or maintaining internal state, or acting (non)atomically or (non)deterministically, rather than being tied to only atomic deterministic modules (i.e. tactics).

First Class Modules
Together, tactics and strategies are called plans.  And since plans (before they are activated) are just a form of static data/information, they can be stored on resources.  Instead of labeling a context with the plan that is to be activated within it, a strategy can be asked to activate the plan that is present on one of its resources.

Clean Termination, Atomic Activation
Since strategies can activate, they should also be able to terminate -- so that they can be reactivated (cleanly) or something else can activate in the same context.  Also, it should be easy to control the activation of a strategy the same way as for a tactic, and in particular, to make it easy to activate a strategy atomically.  ScalPL addresses both of these in simple, logical ways.

Object Orientation (Class Based)
Since a strategy is a first-class entity encapsulating both behavior (i.e. contexts containing plans) and state (i.e. resources), and having a well-defined interface, it is almost an object.  However, to truly be an object, it needs to be able to carry its state with it as it is activated in different contexts, so ScalPL introduces instantiation levels (and instantiation) for resources.  With these, and a few methodologies to deal with them wisely, ScalPL becomes an object-oriented language, with meta-classes.

Arrays
Inherent in the F-Net model is an assumption that each context is statically bound to a fixed set of resources, and while that may be theoretically sufficient, it doesn't  practically.  At the same time, allowing the role bindings to be determined after activation re-introduces all sorts of complications (with deadlock, etc.) that the F-Nets execution model cleared up.  ScalPL bridges the gap on this by introducing array resources (i.e. sets of resources, each an element of the array, addressable via indices) and a method of specifying which resource elements to which a context is to bind as part of the activation itself.

Data Concurrency/Parallelism
Having arrays isn't enough for data concurrency:  For that, one needs a way to scale the amount of concurrency with the number of elements being processed.  ScalPL provides ways to duplicate/clone contexts, and how many plans they should activate collectively (e.g. one among them all, or one each).

Dynamic Resource Allocation
Since there is no specified spatial relationship between different elements of a resource array (since they could even end up on completely different processors), and the initial control and content state of each resource element is known before/until it is accessed, resource arrays can be (and are, by default) infinite in size, and only those elements actually accessed (and modified) are actually tracked.  This means that elements can be allocated only as they accessed (i.e. bound to).

---

Each of these properties conforms roughly to chapters in the Scalable Planning book.

Of course, many sequential OO programming languages have the above constructs and/or properties, and a typical approach to constructing a concurrent language is to start there and augment it with concurrent constructs.  That doesn't usually work very well.  Here, we've instead started with a simple computational model (F-Nets) that properly handles the concurrency issues, and have then built it into a complete language.

Why F-Nets

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.

F-Nets, the essence of ScalPL

I've been wanting to explain here why I get excited about ScalPL (Scalable Planning Language), to compare it with other approaches, etc.  But to do that, I first need to assume that the reader knows what ScalPL is, even those who haven't read the book.  Fortunately, ScalPL can be separated into its foundational (fairly simple) computational model, called F-Nets (short for function networks), and then the other stuff built on top of that (object-oriented model, arrays, data concurrency, etc.), and I really only need to explain F-Nets to convey many of ScalPL's merits.  I'd like to just convey the raw "what" behind F-Nets in one post (here), leaving the "why"s to become clearer in later posts.  Although I presented most of the facets of F-Nets a month ago from a different angle, I'll subsequently use this post as the definitive "quick and complete description" of F-Nets for future reference.  So without further ado, in a dozen paragraphs...

---

An F-Net consists of two main kinds of entities: Resources and tactics.  A resource, represented graphically by a rectangle (sometimes with other decorations), is a container -- it is capable of holding something static, which is (unsurprisingly) called its content, or more technically, its content state.  For computers, you can think of a resource roughly like a variable, and its content as its current value.  So, each has an initial content state (either declared or default), and a content domain (like a data type) which describes the kinds of content it can hold.

A tactic is a description of what to do to some resources, so it can be considered as a program (subprogram, function, method, etc.).  And like a program, which can be run (or executed) to become a process (an active entity "doing its thing"), a tactic can be activated (executed) to become an acton (also an active entity "doing its thing").

A construct called a context, represented graphically by a circle, signifies an association between a tactic and a set of resources, by labeling the circle with the name of the tactic, and drawing lines from the circle to the rectangles representing those resources.  Multiple contexts in the F-Net can be labeled with the same tactic name.  The connecting lines, called role bindings, are uniquely labeled (explicitly or implicitly, by labeling the resource instead), and these labels/names are used by any acton in that context (i.e. resulting from activating the associated tactic) to designate the resources.  The behavior of an acton -- i.e. the alterations it makes to the content of its resources via these role bindings -- is completely determined by the tactic from which the acton springs (i.e. the tactic's description of what to do) and the original contents of those resources when the tactic activates into an acton. In other words, a tactic can be regarded as a function which translates/maps the contents of its resources (as identified by those role binding names) when it activates, to the final contents of those same resources when the activated tactic (i.e. acton) finishes.  And since a tactic can be regarded as a function, then a context can be regarded as specifying an application of that function relative to a specific set of resources. And an acton can be regarded as an evaluation of that application of that function.

Technically, it's possible to get by without specifying much more, just letting the tactics activate atomically (e.g. one at a time) randomly or continuously.  In fact, what's been described here so far is already very similar to a computational model developed years ago by K. M. Chandy and J. Misra called UNITY (or similarly Dijkstra's Guarded Commands) where the guards would be built into the tactics.  However, restricting/specifying the circumstances under which each tactic can activate is generally really useful for both understanding and efficiently implementing the F-Net, so there's another piece of the puzzle:  In addition to content state, each resource also has another changeable attribute, called its control state, represented as a color, initially green for each resource.  And, each of the role bindings (lines) connecting a context to a resource also has an associated set of (static) colors, represented as colored dots (called access dots) shown between the end of role binding and the resource rectangle.  Now the activation rule is:  A tactic can activate in a context if and only if all of the context's resources have a control state matching one of the access dots on the role binding connecting that resource with the context.  And, when a tactic does activate, in addition to accessing (e.g. observing, updating, or replacing) the content of its resources, the acton also assigns a new control state (color) to each resource, thereby (perhaps) allowing other tactics (e.g. associated with other contexts) to activate.

That covers when a tactic can activate into a tactic, but must it ever do so?  The liveness rule answers that question:  If a tactic can activate, then it must, within a finite amount of time -- or, another tactic using at least one of the same resources (and meeting the normal activation criteria) must.  In other words, if something can happen, it will/must, as long as something else doesn't interfere.

That is the essence of F-Nets, but there are a few other notations and minor rules which make them more portable, easily understood, and efficient.

• First, we put arrowheads (called permissions) on all role bindings to designate whether an acton in that context might observe/read the contents of that resource (arrowhead on the circle/context end) and/or will always replace/rewrite the contents of that resource (arrowhead on the resource end).  A role binding with no arrowheads means that the acton won't touch the content state (though it will still assign it a new control state), and arrowheads on both ends signify the other options -- i.e. that the acton might only change parts of the control state, or might only sometimes replace the entire control state. The four combinations of arrowheads are called observe, replace, nodata, and update permission, respectively (i.e. context end, resource end, neither end, both ends).
• Then, just as arrowheads help to represent what the actons might do to the resources' content states, we use colored dots inside of the resource rectangles to represent what the actons might do to their control states.  That is, near where each role binding connects to the rectangle (with access dots), we put one or more colored dots (called, unsurprisingly, new control state dots) inside the rectangle to represent the new control states that the corresponding acton might assign to that resource.  It is also common to add a legend inside the left end of the resource rectangle showing each color that the resource might ever assume (i.e. its control domain) and what that color symbolizes.

So now, just by looking at the F-Net, you can tell, to a large extent, how each acton might affect, or be affected by, the content and control states of the resources to which it is bound (attached) by role bindings.  The control states make an F-Net act very much like a Petri Net, in that regard.

But there is one more loose end.  If tactics can be considered as programs or functions (specifically what theorists call partial recursive functions), complexity theory tells us that we may not be able to tell, with any amount of analysis, whether an acton (once it has been activated from a tactic) will ever finish accessing the content of any particular resource, or assign it a new control state.  (This is true even if the acton has already been cranking away for an arbitrary amount of time.)  This messes up the idea that we can activate just one tactic at a time:  If one gets stuck, we'd never get around to activating any other tactics, but we might also never be able to know if we can just give up on it, because it might eventually do more if we just give it more time.

The essence of getting around this issue is by simply considering a resource which an acton never finishes with as having a special control state (called bottom or ⊥) represented by no color at all (often shown as black).  Because its can be so hard (or impossible) to figure whether any particular acton will eventually finish accessing any particular one of its resources, it is also generally assumed that any resource could end up with this bottom control state, so it's as though there is an implicit bottom (black) dot added to every set of new control state dots.  However, technically speaking, whether an acton will or will not finish up with any particular resource is still completely determined by its tactic and the initial content of its resources, so even with this so-called augmented control domain, we can still at least abstractly consider each tactic as a (total) functional mapping.  And we can freely allow one tactic to activate even before others have finished, as long as we don't let a subsequent tactic activation use a resource that a previous one (i.e. acton) hasn't finished with yet.

And that brings us to one final rule, called the predictability rule, which greatly increases the efficiency and portability of F-Nets in common cases.  It says simply:  If all of the new control state dots for a role binding have the same color, and that role binding has either observe or nodata permission (i.e. there is no arrowhead on the resource end of the role binding), then we call the role binding predictable, which we take to mean that there is not an implied new control state dot of bottom.  That is, predictable role bindings always finish up.  And because they always finish up, and they don't alter (update or replace) their content state, and they have only one choice for new control state, we know the final content and control state of the associated resource the moment the tactic is activated, even before it has finished up.

---

OK, that's F-Nets in a nutshell.  There are other things I could get into, like just how to express tactics in traditional programming language, or how to represent F-Nets textually.  There are also other constructs and abstractions: For example, role bindings really represent (surprise!) bindings for things called roles, and there are ways to a make role bindings branch, etc.  But relatively speaking, those extras are all just window dressing.  F-Nets serve as only the most basic foundation of ScalPL, which altogether has much more functionality, power, and expressiveness than F-Nets, but F-Nets alone are plenty enough to explain many of the advantages of ScalPL over many other approaches.  And now onto the beauty of this approach...

So why parallel (instead of concurrent)?

My last blog entry focused on the ongoing confusion between parallelism and concurrency.  At the very least, I hope I convinced you that parallelism is a subset of concurrency -- i.e. that all parallel programming is also concurrent programming.  So, what, specifically, are parallel programmers trying to achieve beyond concurrency, and why?

A little history is in order.  Parallel programming emerged in an age where the number of practical architectures/platforms for supporting concurrency was limited, as was the technology for programming them.  By and large, these platforms consisted of a handful to hundreds of identical (homogeneous) sequential processors tied together with a uniform communication network, to support either a shared memory or message passing paradigm.   Typically, the entire platform (or some well-defined portion of it, in an approach called space-sharing) was devoted to running one program at a time.

To make the most of these exclusively-allocated processors while reining in complexity, approaches like SPMD (Single Process Multiple Data) or SIMD (Single Instruction Multiple Data) were used to program these machines, where the same instructions (or at least identical programs) ran on several processors at the same time, but with each processor operating on a different part of a larger data set (or parameter space).  Programs were often written using an approach called loop-level (or data) parallelism, where all processors were started on some part of a task (e.g. to process some data structure) at about the same time, generally to deliver their contributions to some specific processor at one time when finished.  This was often at least partially facilitated by assigning different parts of large data structures (typically arrays) to different processors, signifying where operations to those structure elements would be performed. Communication was optimized for these so-called "collective" cases so that information could be efficiently distributed to and/or collected from all the processors at once.  A program consisted of one or more of these collective distribute-compute-collect steps.

Software tools and languages facilitated this approach, using either SIMD languages (like Thinking Machines' C*) on specialized architectures, or more commonly (to whatever extent feasible), executing different iterations of a normally-sequential loop on different processors concurrently instead of in their default/native sequential order, using new languages (or extensions to traditional sequential ones) like HPF and OpenMP.  Tools such as The Force, BSP (Bulk Synchronous Parallel), and collective operations in MPI also supported this collective-execute-and-collect paradigm.  All-in-all, this assumption that a program had an entire, well-defined, homogeneous machine all to itself, and that the programmer was largely responsible for exploiting that machine (in part by optimizing the scheduling of operations on its different processors) to speed up the result, came to be considered as "parallel programming".

Fast forward to the present (and, if you like, future).  Processors are ubiquitous.  Communication is ubiquitous.  PCs, tablets, and even phones have multicore chips (i.e. multiple processors). GPUs (Graphics Processor Units) that were originally intended for, well, graphics are being retargeted for more general computation in cases where there is a good application/architecture match.  Our music, pictures, documents, etc. are often stored and processed in "the cloud", along with web searches and apps, on perhaps thousands of individual (generally PC-sized) machines handling perhaps millions of requests from different users. The number of processors in these larger platforms (e.g. in the cloud) together with the rate of technology advancement make the economics of homogeneity restrictive:  Rather than replacing the entire platform at one time when parts go bad or are outdated, it's often more economically feasible to replace them piecemeal, with the technology of the day, but this leads to a hodgepodge of different technologies and characteristics.  Virtually all the assumptions of traditional parallel computing are out the window, and with them, the effectiveness of traditional parallel programming approaches.

But it's worse than that.  Even if platforms were still largely uniform collections of homogeneous processors in a uniform topology and roughly uniform latency (memory access time) -- and some still are -- those traditional parallel programming approaches would still be suboptimal, as they always were.  First, the goal of high-level programming (and algorithms) from their very inception has been to divorce the correctness/viability of the program/algorithm from the architecture used to implement it, and these parallel programming approaches fail that, often being dependent both on the number of processors and the latency and semantic characteristics of their interconnection (e.g. message passing, NUMA or UMA shared memory).  Second, limiting concurrent expression to fork-join or one-loop-at-a-time execution often forgoes the opportunity to fully exploit the available processors, such as when multiple loops or a loop and other less parallel sections could execute concurrently:  These approaches were largely chosen as a quick-and-dirty way of reining in complexity, and do not fit all computational needs, being relatively unsuitable for a large class of programs (e.g. employing software pipelining or other kinds of functional decomposition).  Concurrency can scale with data without expressing it as "non-looping loops".  And third, the time for any program to achieve a solution includes the time it must wait around for a platform to become available for the program to even start running, which goes way up if an entire machine must be dedicated to one application at a time (or even space-shared between them).

So then, what, really, is the motivation for using these limited parallel programming approaches over concurrent ones?  I would claim: Primarily laziness.  Laziness in developing truly flexible expressive ways of representing concurrency algorithmically, independent of platform, that encompass loop-level parallelism as well as other kinds of concurrency, and in developing the necessary systems software (or middleware) and methodologies to have the resulting programs run (and share platforms) efficiently.

A programmer should be revealing the available concurrency in their program, their algorithm, and the platform (hardware and system software and middleware) should exploit that, in the context of the current conditions, including the availability of processors and other load on those processors.  If a human needs to inject some guidance, some high level knowledge, to facilitate that algorithm-to-platform mapping, then fine, but let it be in a separate step, rather than within the expression of the algorithm itself.  We've been fully accustomed to having that algorithm/platform independence in sequential programming for decades.  It's time to get real in the concurrent world -- and I would argue that approaches like Scalable Planning Language (ScalPL) allow us to do just that.