ThinkArt Lab Animation: A.T. Kelemen© November 12, 1998 Dr. Rudolf Kaehr
1 Polycontextural Strategy towards the Challenge of Parallelism
Living systems are not based on expensive exploitation of nature. They are naturally non-expensive but highly complex. Complexity in contrast to complication (=nowadays complexity) is a strategy of nature that is not repeated in science. Science behaves quite non-natural in thinking and replicating natural systems.
Robert Rosen has introduced as a first step into a more natural science of the natural, the distinction between simple and complex systems.
Today's reality of computing isn't mirrored properly in the framework of mono-contextural concepts, models and methods. To realize parallelism, it would be much more strait forward to understand that parallelism is a quite special case of interactivity between more or less autonomous systems.
Interactivity is well understood in the framework of poly-contextural systems. Therefore I propose that parallelism is a special case of polycontexturality.
Parallelism comes in computer science in many incarnations. In this study I will start with a quite vague notion of parallelism and I will restrict this notion mainly to software concepts and programming languages. Standard examples for functional and logical programming are introduced for the purpose of deconstruction and introduction of a new understanding of parallelism as guided by poly-contextural strategies. This new understanding of parallelism as interaction of autonomous systems is not in conflict with the well known approaches to handle parallelity. In contrary, the poly-contextural approach is seen as a complexion of complementary strategies enriching the field of parallelisms.
1.1 Parallelism in hierarchies
Parallelism in classical systems is obviously defined by its operations and equations. The operations and functions can have to property of being parallelized. The head of the basic module, or the abstract algebra in which this functions are defined is not involved in the procedure of parallelism. Neither the main function which heads the parallelized child functions. The head of the algebra and the main function is hierarchizing the construct of parallelism. In this sense parallelism occurs only secondary and involved in a hierarchy of the whole structure. This approach is reasonable because parallelism is involved here in solving a well-defined problem and delivering a well-defined solution, and parallelism is considered only as a tool or method to solve the problem more economically than in a linear setting.
Diagramm 46
Procedure of parallelism
It seems to be of no value to think about a distribution of the problem and the solution statement during the procedure of parallelism. The main task and its solution is unique and a distribution of it would only be a repetition of the same problem at different places. In other words, parallelism in combinatory logic based programming languages is limited to the parallelism of the strict combinators. The non-strict combinators, like S, K, I are not involved in this type of parallelisms.
Diagramm 47
Basic Modul e
For CL, the basic module is reduced to: contexture is 1, super-operator is ID, and name is Combinatory Logic, sorts are one, the entities E, with constants K, S, and opn is *, and eqns are "=". And parallelism is concerned only in respect of operations and equations. In contrast, poly-contextural parallelism is distributing the whole concept of abstract algebra with its head and body over different places.
Diagramm 48
Logical structure of a parallel graph reduction machine
"A task is executed by an agent. Typically an agent will be implemented by a physical processor. Agents are concrete pieces of hardware (we can point to one!), whereas a task is a virtual object (a piece of work to be done). An agent is employed if it is executing a task. An unemployed agent will look for a task to execute in the task pool which contains all the tasks awaiting execution."
"Synchronization between tasks is mediated entirely through the graph, so that the tasks do not communicate directly with each other at all." Peyton, p. 414
Obviously the reduction of the S commbinator, Sxyz = (xz) (yz), gives the key for parallelsim in classical systems. The graph reduction of Sxyz is shown in the diagram.
Parallelity in CL-based programming languages is at first depending on the combinator S. The graph gives the logical structure of the formula.
Is there any parallelity involved with the other main combinator, K? Obviously not: Kxy = x is reducing (xy) to (x). This process doesn't show any possibility of parallelism.
Remark. From a PCL point of view, which is dealing with complexities, and where terms are complex and in some sense ambigue, the reduction opens up the question, to which x of the other, but same x´s of the complexion are we reducing? The intra-contextural understanding of the rule Kxy = x asks for an additional identity relation ID, which rules the process of staying in the contexture and not leaving it. In analogy, K can reduce at once into different contextures, K(3)xy = (x, x, x) depending on the super-operator BIF. Every action or transition of a system is involved into the question of a contextural staying/leaving-decision.
"We have seen that functional languages can form a basis for parallel programming.
(i) Graph reduction is an inherently parallel activity. At any moment the graph may contain a number of redexes and it is very natural to reduce the simultaneously.
(ii) Graph reduction is an inherently distributed activity. A reduction is a (topologically) local transformation of the graph, and no shared bottleneck (such as an environment) need be consulted to perform a reduction.
(iii) All communications mediated trough the graph. This gives a very simple model of the way in which concurrent activities cooperate, and it is a model in which we have considerable confidence (because it is the same as our sequential implementations!)
(iv) The entire state of the computation at any moment is well defined - it is the current state of the graph.
Graph reduction gives us a rocked-solid model of parallel computation which can underpin the complexities of a parallel machine." Peyton Jones, p. 413
Also functional programming languages are not inherently sequential as conventional imperative languages but in principle parallel, in order to produce interesting results the program must contain algorithmic parallelism.
This inherent parallelism of functional languages offers to program parallelism with the means of the language itself without the need of adding new operators of parallelism.
This concept is widely known and has been explicitly studied by S.L. Peyton Jones, Kevin Hammond and Hans-Wolfgang Loidl.
To exploit algorithmic parallelism in mono-contextural parallel functional programming languages like parallel HASKELL two main operators are additionally introduced: the operators par and seq.
Simulating parallelism in the framework of poly-contextural systems has to deal with this two operators.
The parallel operators par and seq in GranSim
For example in the expression
let
squares = [ i^2 | i <--- [1..n] ]
in
squares `par` sum squares
the list of squares will be produced by one thread (the producer) and the result sum will be computed by another thread (the consumer). Note that this producer-consumer structure of the algorithm is solely determined by the data-dependencies in the program. All the programmer has to do is to annotate a named subexpression (in this example squares), which should be computed in parallel. Thread placement, communication and whether the thread should be created at all are up to the runtime-system.
parfib :: Int --> Int
parfib 0 = 1
parfib 1 = 1
parfib n = nf2 `par` (nf1 `par` (nf1+nf2+1))
where nf1 = parfib (n-1)
nf2 = parfib (n-2)
The drawback of this program is the blocking of the main task on the two created child-tasks. Only when both child tasks have returned a result, the main task can continue. It is more efficient to have one of the recursive calls computed by the main task and to spark only one parallel process for the other recursive call. In order to guarantee that the main expression is evaluated in the right order (i.e. without blocking the main task on the child task) the seq annotation is used:
parfib :: Int --> Int
parfib 0 = 1
parfib 1 = 1
parfib n = nf2 `par` (nf1 `seq` (nf1+nf2+1))
where nf1 = parfib (n-1)
nf2 = parfib (n-2)
T