|
A diagram is worth a thousand lines of code
February 09, 2009
URL:http://www.drdobbs.com/parallel/multi-core-oo-part-2/213401553
John Gross is chief engineer and Jeremy Orme chief architect at Connective Logic Systems. They can be contacted at [email protected] and [email protected], respectively.
This five-part article introduces Blueprint, a technology developed Connective Logic Systems (where we work) that provides an alternative approach to multi-core development. The Blueprint toolset is built on the premise that we actually have no problem understanding complex concurrency -- until we project it into the one-dimensional world of text. For this reason, a visual representation is much easier to work with than its textual equivalent. There are some cases where text is obviously more intuitive -- such as parallelizing data-parallel loops. In these cases, technologies such as Microsoft's Task Parallel Library (TPL) and Intel's Threaded Building Blocks, can be intuitive and productive. For more background information, see Part 1.
Blueprint provides a means of separating an application's concurrency logic from its algorithmic/business logic, and uses a specialized visual programming paradigm to deal with the concurrency aspects. This allows descriptions to include branching and merging information in a way that textual equivalents alone do not support. In the concurrency domain, statement "order" is replaced by "connectivity", but the algorithmic/business domain remains sequential and is decoupled from its scheduling; see Figure 1.
Blueprint presents application developers with a high-level object-oriented (OO) view of the world, meaning it:
This could therefore be a single machine, and/or a heterogeneous network of machines. This means that applications can be built for any process configuration without the need to modify program logic.
Asynchronously executing class instances can be joined together in any way, provided that the prototypes at each end are compatible. Adjacent classes synchronize through their connections. They can be archived and re-used through a visual drag-drop-and-connect metaphor; see Figure 2.
Blueprint has the concept of "colonies" -- a network of compute nodes in which any node can process any task -- which allows additional slave machines to be recruited and/or retired at any stage of application execution without loss of data (Scale-on-Demand). In addition, the runtime scheduler supports task prioritization, and Blueprint applications will execute preemptively at network scope. This gives the resulting applications an implicit distributed real-time capability.
In this article, we examine the rationale for choosing visual over textual in the concurrency domain and looks at how Blueprint uses its diagrammatic approach to bring additional capabilities to developer's existing multi-core toolboxes.
Anyone who has played football (American, Australian, Rugby, or Soccer) knows that you need to keep track of each other player on the field, as well as the ball, the referee, and yourself. Likewise, each musician in an orchestra must synchronize with the conductor and each other musician. It therefore seems that many people are actually very good at dealing with concurrency.
However, although most of us can "see" any number of written sentences at the same time, few of us could "read" more than one sentence at the same time. Even the most experienced stock market traders would probably be challenged by three or more simultaneous telephone calls; our linguistic skills (textual and verbal) appear to be more or less sequential.
This should not be surprising because linguistic meaning is heavily dependent on word order, and so "watching" a football match is a very different experience from listening to it on the radio, or reading about it in a paper. Films can usually tell stories in less time than books because apart from anything else, the information bandwidth is higher (but of course that does not necessarily make it a more satisfying aesthetic experience!).
Few would disagree that the best way to express an FFT or Matrix inversion algorithm is almost certainly textual; VHDL is now used by electronics engineers for the domains in which it is appropriate. In the same way that the electronics industry now adopts a hybrid visual/textual approach, software engineering can also benefit from the same specializations.
Few people would disagree that GUIs are best developed using graphical drag-and-drop metaphors, class designers are also making increased use of visual semantics, but equally few people would try to use pictures to describe a recursive quick-sort algorithm. TPL, TBB, and Blueprint are clearly not mutually exclusive.
Conventional text programs derive much of their "meaning" through their statement ordering, whereas an electronic circuit diagram derives equivalent meaning through its connectivity (which can branch and merge). In the specific cases where statement order doesn't matter, then there is typically potential for concurrent execution.
Most text languages are primarily concerned with algorithmic logic (usually branching on particular data values) and don't have an intuitive way of expressing concurrency in general, particularly the more complex irregular dependencies like "f3 can be executed when f1 and f2 complete, but f1 can't be executed while f0 is executing".
Whilst Parallel-For, Map-Reduce, and other existing mechanisms can address "regular" parallelism in an effective "bottom-up" manner, the "futures" approach to irregular problems that involve more than half a dozen concurrent threads of execution can be difficult to conjure with.
Consider this pseudo-C example function:
T8 f0( T1 t1, T2 t2 )
{
T3 t3; T4 t4; T5 t5; T6 t6; T7 t7; T8 t8;
t3 = f1 ( t1 );
t4 = f2 ( t2 );
t5 = f3 ( t2 );
t6 = f4 ( t3, t4, t5 );
t7 = f5 ( t3, t4 );
t8 = f6 ( t6, t7 );
return t8;
}
If you analyze the code in the function and assume for now that these functions have no relevant side-effects, then you can produce an informal dependency diagram such as Figure 4.
In Figure 4:
In this informal example:
Functions become executable when all of their inputs are collected. So in this example, the f4 function cannot execute until f1, f2, and f3 have all executed, but the order in which they complete doesn't concern f4. Anecdotally at least, most people would appear to be able to appreciate the logical dependency, and hence logical concurrency from Figure 4 more rapidly and readily than they could from the sequential text that it represents.
More importantly, information concerning the data objects, and the operations performed by the functions f1...f6, is not required in order to do this; likewise, the data objects and functions that operate on them are not concerned with scheduling. This highlights the fact that at a high enough level of abstraction, algorithmic logic and scheduling logic are separable -- and in this instance, one is textual and the other visual.
The concurrency description is localized rather than being dispersed across the application, and is uncluttered by algorithmic information that is not relevant to concurrency. When we combine the two descriptions we have a concurrent description that makes no assumptions about its target hardware (this will be addressed later). Figure 5 shows a formal, machine translatable, Blueprint implementation of the informal dependency diagram.
Among other things, the symbolism disambiguates branching and merging. Branching typically infers "sharing" but could equally well mean "competing"; merging may infer "collection" (wait for all), but could also mean "multiplexing" (wait for any). It also addresses issues like destructive/non-destructive reads and so on. Figure 5 illustrates how the symbolism uses "event operators" (e.g., collectors and distributors) to precisely describe the required execution constraints.
The translator compiles the diagrams into runtime calls, in the same way that high level language compilers generate assembler/object code, but since developer code and generated code are separated, the details of the generated code are not relevant to the developer. Because locks and other synchronization mechanisms are machine managed, their granularity is not limited by what humans can conjure with; the generated code is therefore able to lock at a very fine granularity and minimize effects due to Amdahl's law.
What Blueprint's visual approach aims to do is separate an application's scheduling logic from its algorithmic/business logic. It replaces "order" with "connectivity" and thus exposes concurrency in a way that avoids "reading". In particular, it allows for branching and merging operations to be unambiguously specified, which in turn allows the scheduling logic to be decomposed into simultaneously visible, but independently analyzable, strands of execution. The order with which your eyes scan a Blueprint circuit is only important if you are trying to extract some particular information such as data-flow or event-flow; the parallelism and dependencies can be seen at a glance (the branching and merging is obvious).
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.