Chapter 5
Concurrent Communicating Sequential
Processes
The extended Parallel Data Processing Model
Parallel Data Processing 146
The original CSP Model 146
Inter-Process Communication and Synchronization 155
The extended CCSP Model 157
Signal Flow Diagrams, CSP, and Petri-Nets 167
CSP Programming Languages 169
The mRTL Programming Language 169
The ConPro Programming Language 171
Hardware Architecture 184
Software Architecture 189
Further Reading 190
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
146
This chapter introduces a parallel multi-process model with global shared
resources and the ConPro programming language used for the design of par-
allel data processing systems, e.g., the agent processing platforms presented
in this book, specifically suitable for application-specific System-on-Chip (SoC)
architectures and designs.
5.1 Parallel Data Processing
Embedded systems used for the control, for example, in Cyber-Physical-
Systems (CPS), perform the monitoring and control of complex physical pro-
cesses using applications running on dedicated execution platforms in a
resource-constrained manner. SoC designs are preferred to achieve high min-
iaturization and low-power applications. Traditionally, program-controlled
multiprocessor architectures are used for the execution platform with very
limited parallelization capabilities, but application-specific digital logic gains
more importance, which can enable parallel data processing.
Concurrency has great impact on the system and data processing behav-
iour concerning latency, data throughput, and power consumption. Streaming
and functional data processing requires fine-grained concurrency on the data
path level, however, reactive control systems (for example serving communi-
cation tasks) require coarse-grained concurrency on control path level.
The behavioural level usually describes the functional behaviour of the full
design interacting with the environment. Most applications and data process-
ing are modelled on algorithmic behavioural level using some kind of
imperative programming language.
The following introduction of a process-based data processing model is
required and used
1. For the implementation of the agent-behaviour (activities and transi-
tion);
2. For the implementation of the agent processing platform.
5.2 The original CSP Model
The Communicating Sequential Processes model (CSP, introduced by C.
Hoare [HOA85]) is a common computational model for parallel and distrib-
uted computing used extensively in the last decades. The CSP model is
basically state-based, composing the state of a computational system in pro-
cesses with a control and data state. Each process performs the processing
with a sequence of instructions modifying the state of the process.
The CSP model is very attractive in parallel software development (multi-
threaded programming models) and for hardware design due to the proxim-
ity to finite state machines and Register-Transfer (RTL) architectures. The
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
5.2 The original CSP Model 147
state-based ATG/AAPL agent behaviour model can be easily mapped on the
CSP model.
One major aspect of the CSP model is the capability to compose complex
parallel and distributed systems with a set of processes by using process con-
structors providing the design of arbitrary nested sequential and parallel
processes.
Furthermore, CSP is a language based on process algebra for describing
and modelling interaction between processes, e.g., communication. There-
fore, it can be used to analyse the system behaviour of parallel and
distributed systems.
There are basically three different process classes distinguished by their
composition operation and execution behaviour [PARSYS]:
Process
A process p is an active execution unit associated with a data and control
state. The behaviour of the control state of a process can be modelled with
State-Transition Graphs (STG). The data state consists of the current values
of all storage variables assigned to a process. The control state is associat-
ed by a particular action performed by the process, i.e., the execution of an
instruction. Each process has an abstract process execution state PS with a
state from the set PS{START, RUN, BLOCKED, STOP}, which can be affected by
other processes. Possible processing state transitions are given by Defini-
tion 5.1, which depends on the external process environment and the be-
haviour of other processes.
Def. 5.1 Allowed process execution state transitions
STARTRUN
RUNBLOCKED
BLOCKEDRUN
BLOCKEDSTOP
RUNSTOP
This means a process must be activated by an event x, performing the ex-
ecution state transition
STARTRUN, for example, based on a communica-
tion with another process. Process blocking is a result of an event
participation, and a process is blocked (halted) until an event occurs. The
termination of a process results in the execution state transition
(RUN|BLOCKED)STOP, and can have different reasons: Normal termination,
exceptional termination (a fault occurs), or external termination controlled
by another process.
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
148
Multiprocess Sets
A set of processes P consists of multiple distinct processes p
1
, p
2
, ..., which
is written P={p
1
, p
2
, ..}. The processes interact with each other following
specific rules and orders, discussed below. The set can be considered as
being a meta process encapsulating the contained processes.
Events
An event is commonly related to input and output operations and the hap-
pening of an event requires the satisfaction of a condition cond (e.g., the
availability of data), which is indicated with an identifier prefixed with
x(cond), or in short form x. There is an empty event (true) or in short
form , which can happen at any time.
Process Blocking
It was assumed that a process is activated (started), performs data process-
ing, and terminates. Without any external communication and inter-pro-
cess synchronization a process will always pass through the process state
sequence STARTRUNSTOP. But inter-process communication will intro-
duce wait conditions for a process that will block (suspend) the process ex-
ecution until an event occurs and the condition is satisfied (e.g., change of
data).
In this case, a process will pass through an extended process state se-
quence in the form of STARTRUNBLOCKRUNBLOCK..STOP.
Process blocking is a fundamental concept enabling the synchronization of
multiple process systems and requires engaging of process in events, writ-
ten formal:
p
1
á x
1
(cond
1
) á p
2
á x
2
(cond
2
) ..
Elementary Processes
An elementary process is an atomic process executing one atomic instruc-
tion without interruption. An elementary process must be started
(activated) and terminates after the execution of the instruction. An ele-
mentary process is equal to a process set p={i}.
The instruction of an elementary process can modify the data or the con-
trol state of a program.
Sequential Processes
A sequential process is composed of a sequence of elementary processes
(instructions) I={i
1
, i
2
,..} of elementary statements i ST={st
1
, st
2
,..} execut-
ed in the given order. There are pure computational statements (changing
the data state of a process, e.g., assignments) and control statements
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
5.2 The original CSP Model 149
changing the control state (the currently active process instruction) of the
process (i.e., branches and loops), which is illustrated in Figure 5.1, and for-
mally given in Definition 5.2.
Therefore, the activation of an elementary process (i.e., an instruction) can
be conditional and depends on the evaluation of computed or external da-
ta. Process alternation and process flow choices are discussed later.
Fig. 5.1 Process flow: Instructions can be considered as being elementary and atomic
processes; a sequential composition activates a process chain one after one.
Def. 5.2 Sequential Process Composition Constructor p
seq
(; operator) and the execu-
tion timing model enclosed in `a and denoted with x
giving the execution
time point or interval of a sub-process. [
á: process transition, à: temporal
flow]
Composition
p
seq
: {p
1
, p
2
, ..} p
1
; p
2
; p
3
; p
4
; ..
p
seq
: {i
1
, i
2
, ..} p
1
={i
1
}; p
2
={i
2
} ; p
2
={i
3
}; p
4
={i
4
} ..
Process Flow Behaviour
p
seq
: {p
1
, p
2
, ..} á p
1
á á p
2
á á ..
Timing Model
`
p
1
={i
1
}
1
à p
2
={i
2
}
2
à p
3
={i
3
} ... a
with
1
<
2
<
3
< ..
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
150
The execution of a sequential process p
seq
={p
1
, p
2
, .., p
n
} starts the first pro-
cess p
1
of the sequence. After the termination of this sub-process, the next
process p
2
is activated by an empty event. The sequential process p
seq
ter-
minates if the last sub-process p
n
has terminated.
Control State
Each elementary statement i ST of a sequential process p
seq
is related to
a state s
i
of a set of control states s S={s
1
, s
2
,..}. The values of all data var-
iables of a process create the data state D of a process, a multidimensional
vector D=[v
1
, v
2
,..].
There is a set of transitions T with t
1,2
:s
1
,
s
2
| cond between states of a
sequential process activating instruction processes, which can depend on
the satisfaction of preconditions cond related to process data. All states
and transitions create a state-transitions graph STG =
S , T, where the
transitions are the edges of the graph connecting transitions. An example
is shown in Figure 5.2.
Fig. 5.2 An imperative program fragment (GCD computation algorithm) and the rela-
tion to a state-transition graph and the sequential process. Each elementary
instruction is assigned to a control state. Pure decision states (i.e., S4) can be
further compacted with the previous control state (i.e., S3).
x
i1s1
:=32;
y
i2s2
:=16;
WHILE
i3s3
x<>yDO
IF
i4s4
x<yTHEN
x
i5s5
:=x‐y;
ELSE
y
i6®s6
:=y‐x;
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
5.2 The original CSP Model 151
Interruption and Restart
A sequential process p can be interrupted by another process q, written as
p^q, which does not depend on a regular termination of the process p. Fur-
thermore, a sequential process can be restarted, either performed explic-
itly by another process, introducing the concept of looping or iteration,
written as p, or implicitly due to a catastrophic failure. Restarting of pro-
cesses enables the implementation of procedures that can be executed re-
peatedly.
Parallel Processes
A parallel process consists of a composition of processes executed concur-
rently that can be elementary, sequential, and other parallel processes.
Initially, these processes execute without any coordination except the
start and termination of each individual process, shown in Figure 5.3, and
formally defined in Definition 5.3.
It is expected that multiple processes execute concurrently that they inter-
act with each other. The interaction introduces events that can be consid-
ered as being checkpoints. These checkpoints require some simultaneous
participation of the processes. There is an alphabet of events for each
process. Thus, the union of event sets of processes implement the co-ordi-
nation and synchronization of a set of processes, for example:
(p k q) = p q
Def. 5.3 Parallel Process Composition (|| operator) and the corresponding timing
model
Composition
p
par
: {p
1
, p
2
, ..} p
1
k p
2
k p
3
k p
4
k ..
Process Flow Behaviour
p
par
: {p
1
, p
2
, ..} á (p
1
k p
2
k p
3
k p
4
k ..) á ..
Timing Model
`p
1
a = ( i
1,1
1,1
à i
1,2
1,2
à i
1,3
1,3
à i
1,4
1,4
, .. )
[
1,1
,
1,n
]
`p
2
a = ( i
2,1
2,1
à i
2,2
2,2
à i
2,3
2,3
à i
2,4
2,4
, .. )
[
2,1
,
2,n
]
`p
3
a = ( i
3,1
3,1
à i
3,2
3,2
à i
3,3
3,3
à i
3,4
3,4
, .. )
[
3,1
,
3,n
]
with `p
1
a
[
1
,
n
] =
[
1,1
,
1,n
]
[
2,1
,
2,n
]
[
3,1
,
3,n
] ...
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
152
Fig. 5.3 Control flow of the parallel process execution: the process flow is forked and
after all processes are terminated joined again (all processes are encapsu-
lated in a meta process).
Dynamic Process Creation and Process Forking
Processes can be contained in a meta process (explained below) or can be
created by a process performing forking of a child process, either a copy of
the parent or a new (totally different) process. After a child process was
forked, the parent and the child processes are executed in parallel. The
termination of the new compound process may depend on the termina-
tion of both processes, but the parent process is not waiting for the
termination of the child process. The fork operation can create a new pro-
cess dynamically at run-time, or statically only starting the child process
that was already instantiated (important for resource-limited designs), and
it acts as a dynamic process flow forking with a final joining.
Def. 5.4 Parallel Process Composition using Forking (
operator). The parent or main
(master) process p
A
creates a subordinated process p
B
.
Process Alternation
A process alternation selector allows the observation of multiple events,
e.g., blocking IO statements, considered as being elementary processes. If
one of the statements, for example, containing a blocking access of a
channel, is ready, the statement is executed and an associated process is
started handling this event, shown in Figure 5.4, and defined formally in
Definition 5.5.
Composition
p
fork
: {p
A
, p
B
} p
B
p
A
p
A
k p
B
Process Flow Behaviour
p
fork
: {p
A
, p
B
} áp
A
á fork á (p’
A
k p
B
á
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
5.2 The original CSP Model 153
Def. 5.5 Process Choice Alternation (Handler p
Hi
waits for the execution of a blocked
IO process p
IOi
):
Fig. 5.4 Process alternation flow. A process observes multiple blocking IO processes,
e.g., the reading of channels, by using an alternation, finally executing a
handler.
Composition
p
choice, general
: {p
1
, p
2
, p
3
, ..} p
1
| p
2
| p
3
..
p
choice,event
: {p
IO1
, p
IO2
, .. , p
H1
, p
H2
, .} p
H1
: p
IO1
| p
H2
: p
IO2
..
Process Flow Behaviour
p
choice
: {p
IO1
, p
IO2
, .. , p
H1
, p
H2
, ..}
(io
1
á p
IO1
á p
H1
| (io
2
á p
IO2
á p
H2
| ..
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
154
The process alternation constructor ensures the mutual exclusion in the
case more than one IO event occurs (i.e., ready IO statements). Only one
IO statement process is activated at any time, queueing other pending IO
processes that are ready. The process alternation acts as a conditional
fork in the process flow.
Process Flow and Meta Processes
Processes can be encapsulated and grouped in a meta process. In the
above definitions p
par
, p
seq
, p
fork
are meta processes, for example. The
starting of the meta process starts the process control flow inside the
meta process. The meta process terminates iff all processes have termi-
nated (see Figure 5.5), and implicates fork and join operations of the
process control flow (i.e., the flow of process activation).
The process flow is the control flow on process level, which is different from
the control flow on instruction level, though it can depend on it. The pro-
cess flow has its origin in the process control state and the process control
operation set, which modifies the process state.
In principle, there are three four basic situations in the process flow:
1. A terminated process activates implicitly one next process in a
sequence;
2. The process flow forks and starts multiple processes of a group;
3. The process flow joins the termination of the group of processes;
4. A process starts (fork) or stop explicitly a process.
Fig. 5.5 Examples of meta processes and process forking at run-time. The process flow
contains fork and join planes (multi-threading).
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
5.3 Inter-Process Communication and Synchronization 155
Process Interleaving
Process interleaving, written as p
1
jjj p
2
jjj p
3
.., is a fundamental method to
enable resource sharing and resolving of the resource competition arising
with the concurrent access of shared global resources by multiple processes.
Interleaved processes execute concurrently as long as they do not access
shared resources, otherwise they are executing as sequential processes.
5.3 Inter-Process Communication and Synchronization
Parallel execution of processes require synchronization regarding their con-
trol flow and the possibility to exchange data. Process synchronization occurs
if the progress of computation of one process depends on the state of other
processes. The simplest synchronized inter-process communication is the
activation (starting) and joining (waiting for termination) of processes. Syn-
chronization requires the concept of process blocking, that means the
interruption of the control flow of a process until an event occurred.
There are two kinds of process interaction requiring synchronization:
1. Competition Concurrent access of shared resources;
2. Cooperation Distribution, exchange, and merging of data.
Channel-based Communication. The original CSP model uses channels with a
handshake behaviour for the data exchange and the synchronization (co-ordi-
nation) of processes. A queue is the extension of a channel with a buffer
consisting of cells, that is some kind of shared data memory resource. Since
the original CSP do not allow concurrent access of shared resources, or more
precisely there may no be competition, there may be only one writer and one
reader process accessing a channel.
The principle usage of queues by processes is shown in Figure 5.6. Without
concurrent access of a queue, there is one reader and one writer process.
A channel or a queue can be considered as an abstract data type object that
is accessed by applying a read or write operation, explained in Definition 5.6,
which is parametrizable by the data type () of the queue elements and the
maximal number of stored data elements (size). A special case is a queue with
size=1, providing a fully handshake data transfer between two processes
(four-phase acknowledge).
Channel: The invariant to be always satisfied is composed of the conditions: 1. If
there is no pending write operation, a read operation is blocked, 2. If there is no
pending read operation, a write operation is blocked. A channel is fully
synchronous.
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
156
Queue: The invariant to be always satisfied is composed of the conditions: 1. If the
queue is empty, a read operation is blocked, 2. If the queue is full, a write opera-
tion is blocked. A queue is semi-synchronous.
The algorithmic description of the queue behaviour is given in Algorithm 5.1.
Def. 5.6 Channel-based communication. A channel offers a read and a write operation
for the coordinated exchange of data between processes.A read or write state-
ments is treated as a sequential process.
Alg. 5.1 Queue object operations and synchronization (with data type
) in pseudo-
notation. It is assumed that two processes p
1
and p
2
uses the queue (one
reading, one writing)
objectspecificationQUEUE=
PARAMETER={=<datatype>,size:integer}
STATES={EMPTY,FULL,FILLED}
operationwrite(x):(process,)unit
operationread:process
objectbehaviourQUEUE=
VAR=state:STATES,QD:array[size]of
operationwrite(p,x)is
Ifstate=FULLThenBlock(p)untilstateFULL
evalx,QD=[y,z,..]QD=[x,y,z,..]
If|QD|=sizeThenstate:=FULLElsestate:=FILLED
operationread(p)return(x)is
Ifstate=EMPTYThenBlock(p)untilstateEmpty
evalQD=[..,y,x]QD=[..,y],x
If|QD|=0Thenstate:=Emptyelsestate:=FILLED
Short Notation
V:=C.read() C?V
C.write() C!
V:=Q.read() Q?V
Q.write() Q!
with a channel C (or queue Q with N buffer cells) and a variable V.
Process Flow Behaviour
(C?V; p) k (C!; q) á p k q
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
5.4 The extended CCSP Model 157
Fig. 5.6 Inter-Process Communication with Queues (or channels)
5.4 The extended CCSP Model
The original CSP model did not consider concurrency of multiple processes
accessing a shared object with arising competition conflicts. The extended
CSP model includes shared objects with access competition, which is resolved
by atomic guarded actions applied to these objects. Global objects, for exam-
ple, memory or synchronization objects, can be accessed by multiple
processes concurrently without a violation of the object and process consist-
ency. Invariants of objects and processes are preserved by using a Mutex
scheduler resolving concurrency and competition by serialization (basically
equal to process interleaving).
The principle multiprocess system architecture is shown in Figure 5.7. The
system consist of a set of processes that access global shared objects by
applying guarded operations.
It can be shown that the extended Concurrent CSP (CCSP) model can be
efficiently mapped on hardware and software level implementations, as
already proven in [BOS11A], [BOS10A], and [BOS13A] by different case studies
including protocol stacks and agent processing platforms.
Global objects are accessed by a set of guarded operations (methods). A
global object can be treated as a monitor locking the access to the resource by
calling an operation applied to the object, for example, the read and write
operations of memory objects or the lock and unlock operations of Mutex
synchronization objects.
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
158
Fig. 5.7 Multi-Process model with global shared objects and concurrent access
The following subsections introduce some important synchronization
objects and their operational semantic used in the CCSP model.
5.4.1 Atomic Registers
Concurrency and competition of multiple processes accessing a resource
requires conflict resolution functions and objects. One common basic object
used in the context of concurrent competition resolution enabling composi-
tion of higher-level synchronization objects is the atomic register, which
insures consistent behaviour with multiple readers and writers, illustrated in
Figure 5.8, based on [RAY13].
Constraints and behaviour:
1. A read or write operation op accessing an atomic register appears as
executed at one specific time point (op).
2. The time point of the execution of a read or write operation lies guar-
anteed inside the interval (op
S
) (op) (op
E
), where op
S
is the start-
ing time and op
E
the finishing time of the operation request (from the
point of view of the process).
3. For two different operations it is always satisfied:
(op
1
) (op
2
)
4. Each read operation returns the value from the temporal nearest write
operation execution in the past.
P P P
O O
P P P
Multi-Process Model
P: Sequential Process
O: Shared Object
-: Atomic Guarded
Action
(Communication)
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
5.4 The extended CCSP Model 159
Fig. 5.8 Atomic register: time-line of multiple partially or fully temporal overlapping
read and write operations and the real execution (three concurrent processes
P1,P2,P3).
In the case of a concurrent access an atomic register behaviour is equal to
the behaviour of a non-atomic register with strict sequential operational
access (process interleaving)!
+ The serialization of concurrent access of shared resources is the pre-
ferred approach used throughout this work to resolve the competition conflict
in multiprocess systems based on mutual exclusion, discussed in the next
sections.
5.4.2 Atomic Statements
For the implementation and satisfaction of mutual exclusion not only
atomic registers are required, but also atomic statements. Though a mutual
exclusion object (the Mutex) is used to make a sequence of statements
atomic, e.g., non interruptible, special atomic statements are required on the
processing architecture level. Some examples are test and set operations sup-
ported by microprocessors.
In the following section non-ordered atomic statement sequences are
denoted by
| i
1
, i
2
, .. |,
those executions may not be interrupted, that means, the statements inside
the bounded block must be executed within one time step.
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
160
5.4.3 Mutex
A mutual exclusion lock is used to protect and synchronize concurrent
access of shared objects or program blocks accessing non-atomic objects like
data structures. A Mutex can be in one of two states s{LOCKED, FREE}, see Fig-
ure 5.9. A Mutex is an object accessed by the two operations acquire and
release. If the Mutex object is already locked, a process trying to acquire the
lock will be blocked using the Block operation and the process control will be
stored in a waiter list. If the Mutex is released by the owner, the next waiting
process is scheduled. The algorithm is summarized in Definition 5.7. It
assumes the control of the execution of processes by using the BLOCK and
WAKEUP operation.
Mutex Invariant to be always satisfied: Maximal one process may be the owner of
the lock and can pass the acquire operation without blocking.
Def. 5.7 Mutex object signature and behaviour with a FIFO scheduler (pseudo-
notation)
objectspecificationMUTEX=
STATES={LOCKED,FREE}
operationacquire:processunit
operationrelease:processunit
objectbehaviourMUTEX=
VAR=atomicstate:STATES
atomicWAITERS:processlist
operationacquire(p)is
Ifstate=LOCKEDThen
evalp,WAITERS=[..]WAITERS=[..,p]
Block(p)
state:=LOCKED
operationrelease(p)is
IfWAITERS[]Then
evalWAITERS=[q,..]WAITERS=[..],q
WAKEUP(q)
Else
state:=FREE
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
5.4 The extended CCSP Model 161
Fig. 5.9 State change of a Mutex object by applying the acquire and release operation.
The scheduling policy used to release blocked processes has significant
effect on the overall multiprocess system behaviour, and eventually on the
computational progress. Two different scheduling policies are considered: a
dynamic FIFO and a strict static process priority driven approach:
Process Priority Scheduling
This scheduler serves and releases blocked processes waiting for a re-
source request execution in a strict order based on unique static process
priorities assigned at compile or run-time. This scheduler is not starvation
free, but can be implemented in hardware with the lowest resource re-
quirements by using a mutual exclusive conditional branch based on com-
binatorial logic (state-free) [BOS10A] [BOS11A].
FIFO Scheduling
This scheduler serves and releases blocked processes waiting for a re-
source request execution in the first-in first-out order. This scheduler is
starvation free, but has much higher resource requirements and is state-
based. Software implementations should always use FIFO schedulers to
guarantee fair scheduling.
5.4.4 Semaphore
A Semaphore object is a guarded counter with the following features:
1. Invariant S.counter 0 is always satisfied
2. The Semaphore counter is initialized with a non-negative value s
0
3. There are two operations {up, down} which modify the counter.
4. Extended invariant is always satisfied: S.counter = s
0
+ #S.up - #S.down
with #S.up and #S.down being the number of up and down operation
calls.
Only the down operation can block (lock) a requesting process iff the coun-
ter is zero. A process executing the up operation will release the waiting
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
162
blocked process without changing the counter value effectively in this case. A
Semaphore is mainly used for cooperation management in multiprocess sys-
tems, for example, deployed in producer-consumer systems. A Semaphore
can be implemented using a Mutex object, shown in Definition 5.8, basically
implementing a Monitor object discussed in Section 5.4.8.
Each synchronization object is a shared global resource itself and always
requires the resolution of the competition conflict, here realized with the
Mutex and serialization scheduler.
A typical application of Semaphores used for the synchronization and co-
ordination in producer-consumer systems is shown in Figure 5.10.
Def. 5.8 Semaphore object signature and behaviour with a FIFO scheduler (pseudo-
notation, | ..| denotes a guarded atomic statement execution)
objectspecificationSEMA=
operationdown:processunit
operationup:processunit
operationinit:integerunit
objectbehaviourSEMA=
VAR=WAITERS:processlist
L:objectMUTEX
counter:natural
operationdown(p)is
L.acquire(p);
Ifcounter=0Then
evalp,WAITERS=[..]WAITERS=[..,p]
|L.release(p),Block(p)|
Else
counter:=counter‐1
L.release(p)
operationup(p)is
L.acquire(p);
Ifcounter=0WAITERS[]Then
eval
WAITERS=[q,..]WAITERS=[..],q
WAKEUP(q)
Else
counter:=counter+1
L.release(p)
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
5.4 The extended CCSP Model 163
Fig. 5.10 Producer-Consumer example using Semaphores FREE and BUSY implement-
ing a synchronized buffer.
5.4.5 Event
An event object is used to temporal synchronize a group of processes.
There is a group of processes P
a
waiting for an event. Until the event is sig-
nalled by a process p
s
P
a
, all processes of P
a
are blocked. If the event is
signalled all processes of P
a
are released at once. There are two operations
{await, wakeup}, explained in Definition 5.9. The event is not starvation free.
The event get lost if the event is raised before the processes perform the wait-
ing for the event. To avoid this starvation risk, an event memory (latch) can be
added, which is set if a wake-up operation meets an empty waiters list that is
reset by the first process executing the await operation.
Def. 5.9 Event object signature and behaviour (pseudo-notation, |..| denotes a
guarded atomic statement execution)
objectspecificationEVENT=
operationawait:processunit
operationwakeup:processunit
objectbehaviourEVENT=
VAR=WAITERS:processlist
L:objectMUTEX
event:boolean
operationawait(p)is
L.acquire(p);
IfnoteventThen
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
164
evalp,WAITERS=[..]WAITERS=[..,p]
|L.release(p),Block(p)|
Else
eventfalse;
L.release(p)
operationwakeup(p)is
L.acquire(p);
IfWAITERS[]Then
{qWAITERS}doWAKEUP(q)
Else
eventtrue;
WAITERS[]
L.release(p)
5.4.6 Barrier
A barrier is similar to the event object, and it is a rendezvous object used by
a group of processes. In contrast to the event is the barrier self-synchronizing.
The size N of the process group P must be known in advance. The first N-1
processes will be blocked until the last process joins the group and releases
all waiting processes. There is only one operation await.
Def. 5.10 Barrier object signature and behaviour (pseudo-notation, |..| denotes a
guarded atomic statement execution)
objectspecificationBARRIER=
PARAMETER={N:integer}
operationawait:processunit
objectbehaviourBARRIER=
VAR=WAITERS:processlist
L:objectMUTEX
count:natural
operationawait(p)is
L.acquire(p);
count++;
Ifcount<NThen
evalp,WAITERS=[..]WAITERS=[..,p]
|L.release(p),Block(p)|
Else
{qWAITERS}doWAKEUP(q)
count0;
L.release(p)
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
5.4 The extended CCSP Model 165
5.4.7 Timer
A Timer is similar to the Event object, too. The event is raised by an internal
timer, which can be activated periodically or only one time.
Def. 5.11 Timer object signature and behaviour (pseudo-notation, |..| denotes a
guarded atomic statement execution)
objectspecificationTIMER=
MODE={once,interval}
PARAMETER={mode:MODE,timeout:integer}
operationawait:processunit
operationstart:unit
operationstop:unit
objectbehaviourTIMER=
VAR=WAITERS:processlist
L:objectMUTEX
time:integer
operationawait(p)is
L.acquire(p);
evalp,WAITERS=[..]WAITERS=[..,p]
L.release(p);
Block(p)
operationstartis
L.acquire(p);
timeGlobalTime()+timeout;
WAITERS[];
ptimer.start();
L.release(p)
operationstopis
L.acquire(p);
{qWAITERS}doWAKEUP(q);
WAITERS[];
ptimer.stop();
L.release(p)
processptimer
is
waitforGlobalTimetime;
L.acquire(p);
{qWAITERS}doWAKEUP(q);
WAITERS[];
Ifmode=intervalThen
timeGlobalTime()+timeout;
L.release(p);
ptimer.start();
Else
L.release(p);
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
166
5.4.8 Monitor
In contrast to the previously introduced objects, the monitor object is basi-
cally a programming paradigm and high-level construct, rather a
synchronization object that is implemented directly on hardware or software
level.
Mutex and Semaphores are low-level synchronization objects and the
acquire/release or up/down operations must be used accordingly and bal-
anced, otherwise deadlock or starvation effects can occur.
Monitors implement synchronization on a higher abstraction level of a pro-
gramming language and provide automatic locking without the risk of
deadlocks or starvation, shown in Figure 5.11.
A Monitor encapsulates data and operations on programming level and
ensure the mutual exclusion. It satisfies that almost one process is active
within an operation of a Monitor and satisfies the invariance (consistency) of
the Monitor data. A Monitor uses event variables to enable process interleav-
ing under preservation of a predicate, the invariant of a monitor [PARSYS].
Fig. 5.11 A Monitor is used to auto-synchronize the mutual exclusive access of an object
by applying operations.
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
5.5 Signal Flow Diagrams, CSP, and Petri-Nets 167
5.5 Signal Flow Diagrams, CSP, and Petri-Nets
Signal flow, a common data processing model in digital signal processing
applications, can be transformed immediately to a pipelined CSP process-
channel architecture. Petri-nets are used for an intermediate representation
in the final synthesis of CSP systems implementing the behaviour of the signal
flow diagram.
Figure 5.12 shows an example for the composition of a signal flow diagram
of a PID controller. An explanation can be found in Section 13.1
The signal flow diagram is first transformed into an S/T Petri Net rep-
resentation, which is shown in Figure 5.13. Functional blocks are mapped to
transitions, and states represent data that is exchanged between those func-
tional blocks. The partitioning of functional blocks to transitions of the net can
be performed at different composition and complexity levels. The signal flow
diagram from Figure 5.12 was partitioned using complex blocks (merging low-
level blocks like multipliers and adders) to reduce communication complexity
(and data processing latency).
The Petri Net is then used 1. To derive the communication architecture; and
2. To determine an initial configuration for the communication network. Func-
tional blocks with a feedback path require the injection of initial tokens in the
appropriate states (not required in the example).
Fig. 5.12 Composition and modelling of a digital control system with signal flow dia-
gram [BOS11B]
ADC DACPID
K
K
I
Z
-1
Z
-1
1 -
Z
-1
(1- )K
D
S
S'
U
-1
K
Z
-1
Z
-1
Z
-1
K
I
K
D
K
D
X
A
1
Z
-1
S
A
2
E
U
F
UD
UI
UK
E
E
USX
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
168
Fig. 5.13 Mapping of the signal flow diagram to a Petri Net and mapping of Petri Net to
communication channels and sequential processes using the ConPro pro-
gramming language [BOS11B].
States of the net are mapped to buffered communication channels and
transitions are mapped to parallel and concurrently executing processes -
each with sequential instruction processing - using the ConPro programming
language, introduced in the next section, shown in Figure 5.13, too.
Data sets are represented by tokens that are passed between the pro-
cesses by the communication channels. A process can consume and process
only one token each time. Queues can be used instead of channels (that can-
not store more than one data set token), releasing processes immediately
after they transferred a token to a queue, and prevent the waiting for the con-
sumer of a token.
Forked states indicate concurrency in the Petri Net flow. Exploring concur-
rency in signal flow diagrams using Petri Nets reduces latency for the
complete computation of one data set, starting with the reading of a new data
set by the first block, and ending by the writing of the computed output by the
last block of the computational system. Also, pipe-lining can improve the
throughput of data set streaming significantly, offered inherently by the Petri
Net representation.
F
X
E
P I D
channel c_x:int[12] with model=buffered;
channel c_s:int[12] with model=buffered;
channel c_e1,c_e2,c_e3:int[12] ...
channel c_u1,c_u2,c_u3:int[12] ...
process p_i:
begin
reg t1,t2,z1,z2: int[DATAWIDTH4];
always do
begin
t1 <- c_e2;
t1 <- z1, z1 <- t1;
t1 <- t1 * KI;
t1 <- t1 asr 4;
t2 <- t1 + z2,
z2 <- t2;
c_u2 <- t2;
end;
end;
U
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
5.6 CSP Programming Languages 169
5.6 CSP Programming Languages
There are several programming languages related to the CSP model. The
original CSP model is available in the OCCAM programming language [OCC95].
The OCCAM programming languages supports sequential, parallel, and alter-
nate process constructors, which can be nested arbitrarily. An OCCAM
program can be executed on one or multiple processors, originally related to
the Transputer architecture [IVI99]. The OCCAM programming model does not
support true concurrency and shared object access with competition. Due to
the lack of suitable programming languages for high-level synthesis related to
the extended CCSP model, the ConPro programming language was designed,
close to the CCSP model [BOS11A][BOS10A].
5.7 The RTL Programming Language
The parallel programming language Conpro, which is introduced in the next
section, maps sequential processes on RTL process blocks consisting of a
Finite-State Machine (FSM) and a register-based data path. The behaviour of
an RT process block is specified with an intermediate representation, given by
the RTL language introduced in this section (based on [BAR73]). This lan-
guage can be seen as a core language to model and understand the
behaviour of the extended concurrent CSP programming model.
Operation Description
r expr
Assignment of the value to a register.
i
1
; i
2
; i
3
; ...
Sequential execution of statements.
i
1
, i
2
, i
3
, ... ;
Parallel execution of statements (limited
to non-blocking statements, i.e., assign-
ments)
branch s
An unconditional branch to a different
instruction related to the state s before or
after this statement.
branch cond:s
Conditional branch if the condition is sat-
isfied, otherwise the next instruction is
executed.
Tab. 5.1 Minimal symbolic parallel programming language that can be immedi-
ately synthesized to hardware RT architectures (
: computational
expression).
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
170
An example deriving the RTL specification from the OCCAM programming
language is shown in Example 5.1.
Ex. 5.1 A
RTL specification derived from an OCCAM program
OCCAM
[100]INTData:
INTMean:
SEQ
Mean:=0
SEQIndex=0FOR100
Mean:=Mean+Data[Index]
Mean:=Mean/100
RTL
processmain{
s1:Index0,Mean0;
s2:branch(Index=100):s6;
s3:MeanMean+Data[Index];
s4:IndexIndex+1;
s5:branchs2;
s6:MeanMean/100;
}
s:
An instruction label assigning a state to
an instruction.
oop(arg
1
,arg
2
,...)
Procedural application of an operation to
a global shared object with optional argu-
ments.
r (oop(arg
1
,arg
2
,...))
Functional application of an operation to
a global shared object with optional argu-
ments returning a value.
process p {
i
1
; i
2
; i
3
; ...
}
Definition of a named process composi-
tion. A process p is treated as an object,
too, supporting start and stop opera-
tions.
Operation Description
Tab. 5.1
Minimal symbolic parallel programming language that can be immedi-
ately synthesized to hardware RT architectures (
: computational
expression).
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
5.8 The ConPro Programming Language 171
The relationship of the
RTL instruction to the previously introduced pro-
cess algebra and the process flow behaviour of the RTL instructions is given
below (
: Synchronisation and scheduling point).
5.8 The ConPro Programming Language
Concurrency is modelled explicitly on the control path level with processes
executing a set of instructions sequentially, initially independent of any other
process. Parallel composition is available on programming level but is static at
run-time to enable the synthesis of SoC designs with static resources. That
means the number of processes is fixed at design and compile time.
Inter-Process Communication (IPC) provides process synchronization with
different objects (Mutex, Semaphore, event, timer) and data exchange
between processes using queues or channels, based on the CSP model. More
fine-grained concurrency is provided on data path level using bounded blocks
executing several instructions (only data path, e.g., data assignments) in one
time unit. Block level parallelism can be enabled explicitly or implicitly
explored by a basic block scheduler.
Hardware blocks, modelled on hardware level (VHDL), can be accessed from
the programming level by two methods:
1. Using an object-orientated programming approach with methods
2. Using a signal component structure interface and signals
The first approach treats all hardware blocks, including IPC, as abstract data
type objects (ADTO) with a defined set of methods accessible on process level
(at run-time) and on top-level (only applicable with configuration methods, for
example, setting the time interval of a timer). The bridge between the hard-
ware and ConPro programming model is provided by the External Module
Interface (EMI).
A signal component structure can be used to instantiate and access exter-
nal hardware blocks and to create the top-level hardware port interface of the
ConPro design. Signals are interconnection elements without a storage model.
Process Flow Behaviour
r á {r } á
i
1
;i
2
;.. á {i
1
} á á {i
2
} á ..
i
1
,i
2
,.. á {i
1
} k {i
2
}.. á
oop() á {oop()} á guard(op) á
branchcond:s á (cond á {i
n+1
} | cond á {i
s
} ) á
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
172
They provide only an interface to external hardware blocks. Signals are used
in component structures, too.
The ConPro programming model is a common source for hardware and
alternatively software synthesis, reusing the same program source for differ-
ent implementations, shown in Figure 5.14 on the left side. The EMI
programming paradigm is a central part of this multi-target implementation
synthesis by encapsulating and abstracting hardware blocks, for example, IPC
and communication objects. Most EMI objects can be specified by a hardware
(VHDL) behaviour and an operational equivalent and complementary software
model, without compromising the programming level, shown in Figure 5.14 on
the right side.
In Figure 5.16 (see page 181) the ConPro programming language block
structure and the composition of top-level module designs using these blocks
are summarized.
Fig. 5.14 Left: The ConPro programming model as a common source for hardware and
alternatively software synthesis. Right: Hardware Interfaces from program-
ming level, (a) Signal Interface, (b) EMI
P
ConPro
P P P
O O
P P P
Multi-Process Model
P: Sequential Process
O: Shared Object
-: Atomic Guarded
Action (Communication)
HW SW
Synthesis
HW: Hardware
SW: Software
EMI: External Module
Interface
RTL: Register-Transfer
Logic
FSM: Finit-State Machine
P O
O
P O
EMI
RTLRTL
RTLRTL
P
S S S
P P
Signal Interface
P
O O O
P P
External Module
Interface
EMI
EMI
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
5.8 The ConPro Programming Language 173
5.8.1 Process Composition
Processes are the main execution units of a ConPro design module. A pro-
cess executes a set of instructions in a sequential order. Processes
communicate with each other and the environment by using shared objects
(Inter-process communication IPC). There is sequential and parallel process
composition on control and data path level using bounded blocks, shown in
Figure 5.15.
Parallel process composition on control path level is flat and provides only
coarse-grained concurrency. Parallel process composition on data path level
inside a process is fine-grained, but is limited to non-blocking statements not
affecting the control path of a process.
The ConPro programming language supports named processes defined on
the top-level only, in contrast, for example, to the OCCAM programming
model, which allows embedded and nested parallel and sequential process
constructors anywhere.
A process definition consists of a header defining the unique process name
and the process body defining local object definitions (types, data and some
abstract objects) and sequence of statements.
Processes are abstract objects, too. Thus, there is a set of methods {start,
stop, call} which can be applied to process objects (identifiers). They are con-
trolling the state of a process.
Fig. 5.15 Different levels of concurrency and process composition in ConPro
ConPro Process Composition
Parallel Composition
Control Path Data Path
Process Bounded Block
process P1
begin ..
end;
process P2 ..
process P3 ..
process P1
begin
ibb1, ibb2,
i
bb3, ..;
end;
P1 || P2 || ..
pibb1 ||
p
ibb2 || ..
Sequential Composition
process P1
begin
i1;
i
2; ..
end;
Control Path
Instructions
pi1 ;
p
i2 ; ..
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
174
A process must be started by another process explicitly by using the start
method, which starts the process concurrently (asynchronous call). A process
can be started synchronously by using the call method, which suspends the
calling process until the called process terminates. Each process can be
stopped asynchronously by using the stop method. There is only one main
process, which is started automatically at start-up. To simplify the definition of
a set of processes, parametrizable process arrays can be defined, sharing the
same process body definition, which are replicated to different and independ-
ent physical processes.
Shared program functions and procedures are implemented with sequen-
tial processes, too. Function processes are started by a calling process by
using the call method applied to the function process object, which suspends
the calling process until the function process has terminated. An additional
function call wrapper is attached to a function process to serialize concurrent
function calling (Mutex scheduler).
Def. 5.12 ConPro process definition and control using object method applications. Pro-
cesses are objects that can be parametrized (i.e., synthesis parameters).
5.8.2 Data Storage Objects
True bit-scalable data types (TYPE ) and storage objects (subset of TYPE
) are supported. The data width can be chosen in the range =1-64 Bit. A data
storage object is specified and defined by a cross product of types ().
Storage objects can be read in expressions and can be modified in
assignments.
processpname:
begin
definitions
statements
end[withparameter=value];
arraypaname:process[N]
begin
definitions
statements
end[withparameter=value];
...
pname.start();
pname.stop();
pname.call();
paname.[index].start();
...
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
5.8 The ConPro Programming Language 175
Registers are single storage elements either used as a shared global object
or as a local object inside a process. In the case of a global object, the register
provides concurrent read access (not requiring a Mutex guarded scheduler)
and exclusive Mutex guarded write access. If there is more than one process
trying to write to the register, a Mutex guarded scheduler serializes the write
accesses. There are two different schedulers available with static priority and
dynamic FIFO scheduling policies.
Variables are storage elements inside a memory block either used as a
shared global object (the memory block itself) or as a local object inside a pro-
cess. A variable always provides exclusive Mutex guarded read and write
access by the memory block to which it belongs.
Different variables concerning both data type and data width can be stored
in one or different memory blocks, which are mapped to generic RAM blocks.
Address management is done automatically during synthesis and is transpar-
ent to the programmer. Direct address references or manipulation (aka
pointers) are not supported.
The memory data width, always having a physical type logic/bit-vector, is
scaled to the largest variable stored in memory. To reduce memory data
width, variables can be fragmented, that means a variable is scattered over
several memory cells.
Different memory blocks can be created explicitly, and variables can be
assigned to different blocks.
Queues are storage elements with FIFO data transfer order and synchro-
nized inter-process communication objects, too. They are always used as
shared global objects. Queues and channels can be read directly in expres-
sions and can be used on the left-hand side of assignments like any other
storage object.
Channels are similar to queues. But they can be buffered (behaviour like a
queue with one cell, depth is 1) or unbuffered (providing only a handshake
data transfer).
Def. 5.13 ConPro data storage and signal object definitions and data types with
optional parametrization (DT: Data type, width: bit width including sign bit,
[..]: optional)
regname:DT[withparameter=value];
varname:DT[inblockname];
blockname;
signame:DT;
queuename:DT[withdepth=value];
channelname:DT[withdepth=value];
TYPEDT={logic,logic[width],int[width],bool,char
}
TYPEOT={reg,var,sig,queue,channel}
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
176
Register, variables, queues, and channels can be defined for product types
(arrays and structures), and sum types (enumeration types).
5.8.3 Signals and Components
Signals are interconnection elements without a storage model. They pro-
vide an interface to external hardware blocks. Signals are used in component
structures, too.
Signals can be used directly in expressions like any other storage object.
Signals can be read in expressions, and a value can be assigned using the
assignment statement, Reading a signal returns the actual value of a signal,
but writing to a signal assigns a new value only for the time the assignment
statement is executed (active), otherwise a default value is assigned to the sig-
nal. Therefore, there may be only one assignment for a signal.
Signals are non-shared objects, and have no access scheduler. Only one
process may assign values to a signal (usually using the waitfor statement),
but many processes may read a signal concurrently. Additionally, signals can
be mapped to register outputs using the map statement. The definition of a
signal object is shown in Definition 5.13.
5.8.4 Arrays and Structure Types
Arrays can be defined for storage and abstract object types, shown in Defi-
nition 5.14. Arrays can be selected with static (index known at compile time)
and dynamic selectors (variable expressions).
Def. 5.14 ConPro array definition and array element access (size: number of array
elements)
A structure type definition contains only data types (DT), and no object
types (OT). There are three different subclasses of structures for different pur-
poses, formally described in Definition 5.15:
Multi-Type Structure
The generic structure type binds different named structure elements with
different data types to a new user defined data type, the native product
type.
arrayAS:OT[size]ofDT[withparameter=value];
arrayAO:objectobj[size][withparameter=value];
arrayAO:process[size]ofbegin..end
[withparameter=value];
...AS.[index]...
...AO.[index].method...
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
5.8 The ConPro Programming Language 177
Bit Structure
This structure sub-class provides a bit-index-name mapping for storage ob-
jects. All structure elements have the same data type. The bit-index is either
a one bit value or a range of bits. This structure type provides the symbolic/
named selection of parts of vector data types (for example, logic vector or
integer types) and specified the bit access of object data.
Component Structure
This structure defines hardware component ports, either of a ConPro mod-
ule top-level port, or of an embedded hardware component (modelled on
hardware level). This structure type can only be used with component ob-
ject definitions. The component type has equal behaviour like the signal
type.
Def. 5.15 ConPro structure type definitions and element selection
In the case the object type of a structure instantiation is a register, just N
independent registers are created. In the case of a variable object type, N
objects are stored in a RAM block. Arrays from structure types can be cre-
ated. For each structure element a different array is created. Hardware
component port types are defined with structures, too, with the difference
DefineanewstructuretypewithadatatypeDTspecificationfor
eachelement:
typeST:{
E1:DT;
E2:DT;
...
};
reginstance:ST;
DefineanewcomponentstructuretypewithdatatypeDT
andsignaldirectionDIRspecificationforeachelement.
typeCT:{
portE1:DIRDT;
portE2:DIRDT;
...
};
Defineanewbitstructuretypewithbit‐widthspecification
foreachelement.
typeBT:{
E1:width;
E2:width;
...
};
Accessoftypeobjectelements
...
obj.elem...
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
178
that for each structure element the direction of the signal must be speci-
fied. Some care must be taken for the direction: if the component is in low-
er hierarchical order (an embedded external hardware component), the
direction is seen from the external view of the hardware component.
If the component is part of the top-level port interface of a ConPro module,
it must be seen from the internal view.
5.8.5 Exceptions and Handling
The ConPro programming model supports the concepts of exception signals
and exception handling with statements. Exceptions provide the only way to
leave a control structure, for example loops, conditional branches or func-
tions itself. Exception are abstract signals, which can be raised anywhere and
caught within a try‐with exception handler environment, either within the
process/function where the exception was raised, or outside. Thus, excep-
tions are automatically propagated along a call path of processes and
functions using exception state registers if they are not caught within the rais-
ing process/function.
Def. 5.16 ConPro definition of exceptions and exception handlers
5.8.6 Functions and Procedures
A function definition consists of a unique function name identifier, the func-
tion parameter interface, and the function body with statements. The function
body consists of local object definitions (types, data and some abstract
objects) and an instruction sequence.
Definition of an exception
exceptionE;
Raising of an exception (inside processes)
...
raiseE;...
Catching of raised exceptions
tryIwith
begin
whenE1:I1;
whenE2:I2;
...
end;
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
5.8 The ConPro Programming Language 179
Each function parameter and the set of return value parameters are han-
dled like registers. Only call-by-value semantic is supported. Values of
function arguments are copied to the respective parameters before the func-
tion call, and return values are copied after function call has finished. Within
the function body, all parameters and the (named) return parameter can be
used in assignments and expression like any other register. There is no return
statement. The last value assigned to the return parameter is automatically
returned.
There are two different types of functions: in-lined and shared. The in-lined
function type is handled like a macro definition. Each time a function is
applied (called), the function call is replaced by the function body, and all func-
tion parameters are replaced by the function arguments (including return
value parameters). Shared functions are implemented using a sequential pro-
cess and the call method with an additional function call wrapper. Each time a
shared function is called the argument values are passed to the function
parameters (global registers), and the return value(s) are passed back, if any.
Def. 5.17 ConPro definition and application of functions and procedures
5.8.7 Modules
A ConPro design hierarchy consists of a behavioural module level (Module-
B) containing global (shared) objects and processes. A module is mapped to a
circuit component with a top-level hardware port interface. Structural mod-
ules (Module-S) can be composed of behavioural modules with optional
internal interconnect components. Each process (and process level) consists
of local (non-shared) objects and a process instruction sequence, specifying
the control and data flow. Abstract object types are implemented with
abstract object modules (Module-O).
Behavioural modules implement objects and processes. A behavioural
module is defined by the source code file itself. Actually there is only one
module hierarchy level, the main module. More source code files can be
functionfname(p
1
:DT,p
2
:DT,..)[return(r
1
:DT,..)]:
begin
definitions
instructions
end;
pname();procedurecall
pname(i,1);
yfname1(x);functioncallreturningavalue
{y1,y2}fname2(x);functioncallreturningtwovalues
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
180
included using an include statement. There are two kinds of behavioural mod-
ules: a module embedding objects and processes, and modules providing
access and implementation of abstract data type objects (ADTO). These are
mainly inter-process communication and synchronization objects, for exam-
ple Mutex, semaphore, timer and some communication links. Each ADTO
module to be used must be opened using the open statement.
Structural modules are used to build System-On-Chip (SoC) circuits from
behavioural modules.
Def. 5.18 ConPro definition of structural modules and structural composition
DesigntoplevelIOportdefinition:
typetop_io_type:{
portS1:DIRDT;
};
componentTOP:top_io_type;
exportTOP;
Defineanewstructuralmodulewithspecifiedname:
moduleMS
begin
import
component
structtype
mapping
end;
Importofbehaviouralmodulesandinstantiationofcomponents
(ciruits):
importMB;
componentC1,C2,..:MB;
Definesandinstantiateaportinterfaceofinterconnect
componentwithinitialsignalmapping:
typeICT:{port...};
componentIC:ICT:=
{
C1.TOP.S1,
C1.TOP.S2,...
C2.TOP.S1,...
};
Internalinterconnectusingmappingstatements:
IC.S1>>IC.S2;
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
5.8 The ConPro Programming Language 181
The definition of the structural composition using IO port structures, com-
ponent instantiations, and module block is shown in Definition 5.18. The
structural composition aids the designing of complex SoC circuits by reusing
multi-process blocks.
5.8.8 The ConPro Building Blocks
The overall ConPro design hierarchy and the compositional blocks are
shown in Figure 5.16. Top-level modules are composed of process definitions,
global objects (storage, synchronization, communication), and user-defined
types, and finally top-level interface ports connecting processes and objects
with outside world. The structural composition can embed hardware blocks
on top-level by using components. Processes are composed of instructions
and local storage objects.
Fig. 5.16 ConPro Design Hierarchy and Compositional Blocks Diagram
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
182
5.8.9 Control and Data Processing Statements
Data Processing
Data processing is performed by evaluating expressions and storing com-
putation results in registers or variables using assignments. An assignment
statement has a target data object (register, variable, or a signal), the left-hand
side (LHS), and an expression, the right-hand side (RHS), which can be arbi-
trarily nested and consists of arithmetic, relational, and boolean operations
with operands accessing registers, variables, or signals. As like in traditional
imperative programming models, there is a strict sequential order: first the
RHS is evaluated, and then the result is stored, which is commonly ensured by
an appropriate hardware model in the data path and can be processed in one
control state. Assignments can only be used in process body blocks.
Def. 5.19 ConPro computational statements (assignment and expressions)
Bounded Blocks
Instruction blocks can be used to bind instructions, either part of a control
statement like a branch, or used to define a sub-process with a sequential or
parallel execution model. Instruction can be parametrized, attaching specific
processing or synthesis settings, shown in Definition 5.20.
Def. 5.20 ConPro Sequential and Parallel Process Constructor using blocks.
Assignment
var x: DT; | reg x: DT; | sig x: DT;
x <- expression;
Micro-Sequential timing model: result=Eval(expression) ; Write(x, result)
Expressions
expression ::= value | expression operator expression .
operator ::= + - * / % land lor lnot band bor bnot lsl lsr .
beginseq.sub‐process[begin]parallelsub‐pro.
i
1
;i
1
,i
2
,i
3
,..
i
2
;[end][withbind];
..
endwith[parameter=valueand..];
Parameters: { bind, unroll, schedule, inline, ..}
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
5.8 The ConPro Programming Language 183
Conditional Branches
Two different conditional branches exist: a mutual branch (if-then-else)
based on a boolean condition, and multi-case branch matching values with
the outcome of an expression evaluation (match-with-when). Mutual
branches can be chained (if-then-else-if) offering a prioritized and ordered
conditional branching. In contrast, the multi-case branch can be parallelized in
the control and data path regarding the evaluation of the matching condition,
offering a branch with constant processing time for each case matching.
Def. 5.21 ConPro Branches
Loops
The following loops are offered by the programming model, with the syntax
defined below. In addition to common loop statements there are special
loops addressing the requirements in parallel process systems with event-
based client-server/request-service operational semantic and the handling of
hardware logic signals.
Counting Loop [for-do]
A counting loop repeats the instruction execution of the loop body
with an incrementing or decrementing loop variable. The number of
loop iterations can be given by static or dynamic limit values (regis-
ters, variables). Loops can be completely unrolled. On top-level, the
for-loop can be used to generate an unrolled sequence of top-level
instructions, for example, mapping instructions using arrays. Top-
level for-loops will always be unrolled, therefore the unroll parameter
is unnecessary
Conditional Loop [while-do]
The loop body is executed as long as a boolean expression evaluates
to the value true.
ifcondtheni
cond=true
[elsei
cond=false
];
matchexprwith
begin
whenv
1
:i
expr=V1
;
whenv
2
,v
3
,..:i
expr=v2expr=v3
..;
..
[whenothers:i
others
;]
end;
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
184
Unconditional Loop [always-do]
The loop body is executed repeatedly without any condition. Used in
event-based service processes. An unconditional loop can only be ter-
minated by stopping the process or by raising an exception.
Constant Delay [wait-for-time]
The process can be suspended (delayed) exactly for a specified
amount of clock cycles or time units.
Conditional await [wait-for-condition]
This statement blocks the process until a boolean expression is true.
In the case the expression is false and the wait statement is blocked,
signal assignments can be applied optionally for this time. The
expression generally operates on global signals or registers that may
not be guarded.
Constant clock cycles application [wait-for-time-with]
For a specified number of clock cycles simple expressions can be eval-
uated and assigned to signals. A signal on the LHS in an assignment
holds a value only for one clock cycle. A signal in this apply statement
holds the value for N clock cycles. Outside the application statement
the signal must be assigned with a default value. This can be specified
optionally in the apply statement
Def. 5.22 ConPro Loops
5.9 Hardware Architecture
The previously introduced extended CCSP model can be directly imple-
mented and mapped on microchip level [BOS11A][BOS10A].
forx=ato|downtob[stepv
s
]doi
loop
;
whileconddoi
loop
;
alwaysdoi
loop
;
waitfortime;
waitforcond;
waitfortimewithi
0
;
waitforcondwithi
0
[elsei
1
];
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
5.9 Hardware Architecture 185
5.9.1 Processes
Each ConPro process is implemented on hardware level with a Finite State
Machine (FSM) and a Register-Transfer Level (RTL) architecture of the data
path, finally creating an interconnected multi-FSM architecture.
Fig. 5.17 Hardware architecture of a sequential ConPro process and interconnect to
global objects (
: state transition network, S: control state register,
: combi-
natorial data path,
: transitional data path)
The program flow of the instructions of a ConPro process are mapped on a
control flow and states of the FSM, shown in Figure 5.17, with an additional
start and end state for each process. Complex instructions are split into multi-
ple states. The data path is divided into a pure combinational and a
transitional part with registers. The first one accesses local (read only) and
global objects (read, write, and control access). Access of global resources is
always guarded by the access scheduler (mutual exclusion lock) of the shared
object. A request signal (RE/WE or CALL) is activated in the data path. A guard
signal GD is read and evaluated by the finite state machine transition network.
The actual state, accessing the object, is hold until the guard signal changes to
low level (happening only for one clock period to avoid race conditions).
Shared program functions and procedures are implemented with sequen-
tial processes, too.
5.9.2 Modules
All hierarchical modules, processes, objects, and instantiated hardware
components are merged into one (flat) SoC design with one top-level port
interface, shown in Figure 5.18.
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
186
Fig. 5.18 ConPro Hierarchical Block Architecture with Interconnection.
5.9.3 Mutex Scheduler
Access of shared objects must be guarded inherently by a Mutex using a
mutual exclusion scheduler. This scheduler is responsible to serialize concur-
rent access. The scheduler is connected with all processes accessing the
resource. A process activates a request (REQ), and waits for the release of the
guard (GD), which unblocks the process signalling the grant of the resource,
shown in Figure 5.19.
Fig. 5.19 Scheduler Block Architecture and process interconnect
SCHEDULER
REQ-1 GD-1 REQ-2 GD-2 REQ-N GD-N
REQ GD
PRO-1
REQ GD
PRO-2
REQ GD
PRO-N
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
5.9 Hardware Architecture 187
There are two different schedulers available:
Static Priority Scheduler [default]
This is the simplest scheduler and requires the lowest amount of hardware
resources. Each process ever accessing the resource gets a unique ordered
priority. If there are different processes accessing the resource concurrent-
ly, the scheduler always grants access to the process with the highest prior-
ity. There is a risk of race conditions using this scheduling strategy.
Commonly, the order of processes appearing in the source code deter-
mines their priority: the first process gets the highest priority, the last the
lowest. A scheduled access requires at least two clock cycles.
Dynamic FIFO Scheduler
The dynamic scheduler provides fair scheduling using a process queue.
Each process requesting the resource and looses the competition is stored
in a FIFO ordered queue. The oldest one in the queue is chosen by the
scheduler if the resource is released by the previous owner. The dynamic
scheduler avoids race conditions, but requires much more hardware re-
sources.
The algorithms for both schedulers are defined in Definitions 5.23 and 5.24.
Def. 5.23 Static Priority Scheduler: From/to process i:{REQ-i,GD-i}, from/to shared
resource block:{ACT,ACK}. A process-i request activates REQ-i, and if the
resource is not locked, the request is granted to the next process in the if-then-
else cascade. If the request is finished, then ACK is activated and releases the
locked object and releases GD-i for this respective process indicating that the
request is finished.
LoopDo
ACTFalse;
gd{GD‐1,GD‐2,..}DogdTrue;
IfREQ‐1LOCKEDThen
LOCKEDTrue;
ACTTrue;StartServiceforProcess1
ElseIfREQ‐2LOCKEDthen
LOCKEDTrue;
ACTTrue;StartServiceforProcess2
...
ElseIfACKREQ‐1LOCKEDThen
GD‐1False;
LOCKEDFalse;
ElseIfACKREQ‐2LOCKEDThen
GD‐2False;
LOCKEDFalse;
...
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
188
Def. 5.24 Dynamic Queue Scheduler: From/to process i:{REQ-i,GD-i}, from/to shared
resource block:{ACT,ACK}. A process-i request activates REQ-i, and if the
resource queue is empty or this process is at head of the queue, the request is
granted to the process in the if-then-else cascade. If the request is finished,
then ACK is activated and removes the process from the resource queue and
releases GD-i for this respective process indicating that the request is finished.
LoopDo
ACTFalse;
gd{GD‐1,GD‐2,..}DogdTrue;
IfREQ‐1LOCKED=[]PRO‐1‐LOCKEDThen
LOCKED[PRO‐1];
PRO‐1‐LOCKEDTrue;
OWNERPRO‐1;
ACTTrue; StartServiceforProcess1
ElseIfREQ‐
2LOCKED=[]PRO‐2‐LOCKEDThen
LOCKED[PRO‐2];
PRO‐2‐LOCKEDTrue;
OWNERPRO‐2;
ACTTrue;StartServiceforProcess2
...
ElseIfREQ‐1LOCKED[]PRO‐1‐LOCKEDThen
LOCKEDLOCKED@[PRO‐1];AppendProcess
1toQueue
PRO‐1‐LOCKEDTrue;
ElseIfREQ‐2LOCKED[]PRO‐2‐LOCKEDThen
LOCKEDLOCKED@[PRO‐2];AppendProcess2toQueue
PRO‐2‐LOCKEDTrue;
...
ElseIfREQ‐1Head(LOCKED)=PRO‐1OWNERPRO‐1Then
ACT
True; StartServiceforProcess1
OWNERPRO‐1;
ElseIfREQ‐2Head(LOCKED)=PRO‐2OWNERPRO‐2Then
ACTTrue; StartServiceforProcess2
OWNERPRO‐2;
...
ElseIfACKHead(LOCKED)=PRO‐1Then
GD‐1False;
PRO‐1‐LOCKED
False;
OWNERNONE;
LOCKEDTail(LOCKED);
ElseIfACKHead(LOCKED)=PRO‐2Then
GD‐2False;
PRO‐2‐LOCKEDFalse;
OWNERNONE;
LOCKEDTail(LOCKED);
...
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
5.10 Software Architecture 189
5.9.4 Functions
Shared functions are implemented with processes and an additional func-
tion scheduler guarding the concurrent access of functions and function
parameter. Input and output parameters of functions are implemented with
global registers.
Fig. 5.20 Shared function call using a Mutex scheduler to serialize concurrent function
access by different processes.
The control flow (part of the state diagram of each process) for a function
call is shown in Figure 5.20.
5.10 Software Architecture
In addition to the derivation of the proposed hardware architecture model
there is the possibility to derive a software model with equal operational and
functional behaviour.
Each ConPro process is implemented on software level with a light-weighted
process (thread), finally resulting in a multi-threaded program with a shared
memory model. Global objects are implemented with thread-safe Mutex-
guarded global functions. ConPro functions can be implemented with thread-
safe re-entrant functions without the necessity of a Mutex scheduler.
Different back-ends exists for the C or OCaML programming language. Most
ConPro objects and process statements can be directly implemented in soft-
ware, except hardware blocks, signals, and statements using signals.
process :: other
process :: function
instruction1 functioncall instruction3
start
Mutex guard
parameters
p1
p2
...
functionblock end
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
Chapter 5. Concurrent Communicating Sequential Processes
190
5.11 Further Reading
1. C. A. R. Hoare, Communicating Sequential Processes. 2004.
2. R. Milner, The space and motion of communicating agents. Cambridge
University Press, 2009, ISBN 9780521738330
3. R. Milner, A Calculus of Communicating Systems, Vol. 92, L. Springer,
1986.
4. R. Milner, Communicating and Mobile Systems: the Pi-Calculus. Cam-
bridge University Press, 1999, ISBN 0521643201
5. D. Sangiorgi and D. Walker, The Pi-Calculus: A Theory of Mobile Processes.
Cambridge University Press, 2001, ISBN 0521781779
6. G. Jones, Programming in OCCAM. 1985.
S. Bosse, Unified Distributed Sensor and Environmental Information Processing with Multi-Agent Systems
epubli, ISBN 9783746752228 (2018)
