WoTUG - The place for concurrent processes

Refer Proceedings details


%T Concurrency in Industry (Wot, no CSPs?)
%A Johan P. E. Sunter
%E Peter H. Welch, André W. P. Bakkers
%B Communicating Process Architectures 2000
%X Within an international company such as Philips, systems are
   made from the very small to the extremely large. And
   although parallelism is an important aspect of system
   architecture, it is often overlooked. Due to the wide
   variety of systems, parallelism presents itself in many
   different shapes, requiring different design approaches.
   What approaches have been chosen in the past, and do they
   have something in common? Can we learn from them how to do
   it better? What do we need in the future?


%T Parallel Algorithms for Deadlock and Livelock Analysis of Concurrent Systems
%A Jeremy M. R. Martin, Yvonne Huddart
%E Peter H. Welch, André W. P. Bakkers
%B Communicating Process Architectures 2000
%X Conventional model\-checking techniques for analysing
   concurrent systems for deadlock or livelock are hampered by
   the problem of exponential state explosion: the overall
   number of global states that needs to be checked may grow
   exponentially with the number of component processes in the
   system. The state\-of\-the\-art commercial tool FDR provides
   deadlock and livelock analysis but it is limited at present
   to analysing systems of up to one hundred million global
   states. The Deadlock Checker tool is capable of analysing
   very much larger systems by taking certain short\-cuts. But
   this is achieved at the cost of incompleteness \-\- there
   are certain deadlock\-free and livelock\-free networks that
   may not be proven so using that tool. Here we investigate a
   different approach. We present parallelised model\-checking
   algorithms for deadlock and livelock analysis and describe
   their implementation. The techniques are found to scale well
   running either on a conventional supercomputer or on a PC
   cluster.


%T The Automated Serialization of Concurrent CSP Scripts using Mathematica
%A Weiyang Zhou, G. S. Stiles
%E Peter H. Welch, André W. P. Bakkers
%B Communicating Process Architectures 2000
%X This report discusses the design and implementation of a
   package of Mathematica\-based tools for serializing scripts
   describing the behavior of concurrent systems in CSP. Under
   some conditions, serialization can yield code that is more
   efficient than multi\-process versions and can better meet
   processor constraints. Under most conditions concurrent
   design is easier and more reliable so we prefer to design
   concurrently and only implement serially when necessary. The
   tools include a set of definitions and procedures to
   automatically change concurrent code to serial code.
   Conversions of the following step laws have been implemented
   thus far: external choice, generalized parallel, and
   alphabetized parallel; additional laws will be implemented
   in the next month or so. The tools support the input of the
   more formal typeset notation of CSP, which makes the script
   writing intuitive, and can convert the typeset version to
   the machine\-readable version required by software such as
   FDR. The correctness of the conversions has been checked
   with the FDR package. This package should be of use to both
   those regularly working on concurrent systems and those
   learning CSP.


%T CSP Design Model and Tool Support
%A H. J. Volkerink, Gerald H. Hilderink, Jan F. Broenink, W.A. Veroort, André W. P. Bakkers
%E Peter H. Welch, André W. P. Bakkers
%B Communicating Process Architectures 2000
%X The CSP paradigm is known as a powerful concept for
   designing and analysing the architectural and behavioural
   parts of concurrent software. Although the theory of CSP is
   useful for mathematicians, the programming language occam
   has been derived from CSP that is useful for any engineering
   practice. Nowadays, the concept of occam/CSP can be used for
   almost every object\-oriented programming language. This
   paper describes a tree\-based description model and
   prototype tool that elevates the use of occam/CSP concepts
   at design level and performs code generation for the level
   of implementation in Java, C/C++, and machine\-readable CSP.
   The tool is a kind of browser that is able to assist modern
   workbenches (like Borland Builder, Microsoft Visual C++ and
   20\-SIM) with coding concurrency. The tree description model
   can be used to browse through the generated source code. The
   tool will guide the user through the design trajectory using
   supporting messages and several semantic and syntax rule
   checks. The machine\-readable CSP can be read by FDR,
   enabling more advanced analysis on the design. Early
   experiments with the prototype tool show that the browser
   concept, combined with the tree description model, enables a
   user\-friendly way to create a design using the CSP concepts
   and benefits. The design tool is available from our URL,
   http://www.rt.el.utwente.nl/javapp.


%T Distributed Computing using Channel Communications in Java
%A Andreas Ripke, Alastair R. Allen, Y. Feng
%E Peter H. Welch, André W. P. Bakkers
%B Communicating Process Architectures 2000
%X Various methods of connecting CSP channels to external
   software systems are examined. The aim is to facilitate the
   implementation of distributed heterogeneous systems using
   channel communication. The paper concentrates on TCP/IP
   connections in a Java environment. The approaches used are:
   custom protocol; object serialization stream protocol;
   Remote Method Invocation (RMI); Common Object Request Broker
   Architecture CORBA). Practical systems are described and
   compared.


%T A Comparison of Linda Implementations in Java
%A George Wells, Peter Clayton, Alan G. Chalmers
%E Peter H. Welch, André W. P. Bakkers
%B Communicating Process Architectures 2000
%X This paper describes the implementation of an extended
   version of Linda in Java. The extensions have been made with
   a view to increasing the efficiency of the underlying
   communication mechanisms and the flexibility with which data
   may be accessed, particularly in the area of distributed
   multimedia applications. The system is compared with two
   other recent implementations of Linda for Java: JavaSpaces
   from Sun Microsystems, and TSpaces from IBM. The comparison
   is performed both qualitatively, comparing and contrasting
   the features of the systems, and quantitatively, using a
   simple communication benchmark program and a ray\-tracing
   program to assess the performance and scalability of the
   different systems for networks of workstations.


%T Conditional Communication in the Presence of Priority
%A Gerald H. Hilderink, Jan F. Broenink
%E Peter H. Welch, André W. P. Bakkers
%B Communicating Process Architectures 2000
%X In this paper the behavior of conditional communication in
   the presence of priority will be described. In the theory of
   CSP, conditional communications are expressed by a
   (external) choice construct (also known as the alternative
   construct) by which the choice of one communication out of a
   set of communications is non\-deterministic. In practice,
   some communication can be more important than others, so
   that, the choice is deterministic. Therefore, one can
   distinguish two prioritized alternative constructs; a
   symmetric alternative construct (ALT) and an asymmetric
   alternative construct (PRIALT). Current formal semantics and
   implementations of the ALT and PRIALT are based on the
   priorities of communication and not related to the
   surrounding priorities of communicating processes. This can
   result in a structural mismatch that can cause performance
   problems. In this paper a practical solution for realizing
   fair and unfair conditional communication in the presence of
   the PAR and the PRIPAR will be discussed.


%T Steering High\-Performance Parallel Programs: a Case Study
%A P. J. Love, Jeremy M. R. Martin
%E Peter H. Welch, André W. P. Bakkers
%B Communicating Process Architectures 2000
%X Computational steering is the ability to visualise the data
   from a computation in progress and to modify the future
   behaviour of the computation in response to this. It is
   often perceived as being something very difficult to
   implement, especially for parallel computations. However,
   given a good visualisation environment, we have found that
   this is not necessarily the case. We have sought to dispel
   this myth, using a very simple model which makes it easy to
   \[rs]wire\-up\[rs] an existing MPI parallel program for
   steering. New insights may quickly be gained by continually
   monitoring and guiding the progress of computational
   simulations, that were perhaps previously analysed only in
   their final state.


%T A Self\-Configuring Distributed Kernel for Satellite Networks
%A Scott Cannon, Larry Denys
%E Peter H. Welch, André W. P. Bakkers
%B Communicating Process Architectures 2000
%X The Space Software Laboratory is developing a
   self\-configuring distributed kernel to be used on future
   satellite missions. The completion of this system will allow
   a network of heterogeneous processor nodes to communicate
   and broadcast in a scalable, self\-configuring manner. Node
   applications software will be transparent to the underlying
   network architecture, message routing, and number of network
   nodes. Nodes may halt or be reset and later rejoin the
   network. The kernel will support in\-flight programming of
   individual nodes.


%T A Cruise Control in occam based on an Implementation of KRoC on the Philips 8051 Microcontroller
%A Frank T. M. van Vugt, André W. P. Bakkers
%E Peter H. Welch, André W. P. Bakkers
%B Communicating Process Architectures 2000
%X This paper summarises the results of the realisation of a
   Cruise Control system in occam using an implementation of
   the Kent Retargettable occam Compiler (KRoC) on the Philips
   8051 microcontroller. The increase in complexity of systems
   designed comes with difficulties that can probably be
   overcome using concurrent programming languages. occam is
   such a language, originally developed for use with
   transputers. The KRoC initiative allows one to translate the
   transputer assembly produced from a program written in occam
   into the assembly of another processor. In this case, it was
   implemented for the Philips 8051 microcontroller, which is
   an 8\-bits processor. The design and realisation in occam of
   the Cruise Control system of Yourdon demonstrate its proper
   functioning. The generated code is tested using a real\-time
   in\-circuit 8051 emulator and special hardware to represent
   car and interface. The design process using occam is
   compared to a regular solution using a language like C.
   Since this port is the first of its kind inasmuch as it is
   not targeting \[rs]large\[rs] processors like the SPARC,
   important conclusions can be drawn regarding the power of
   the CSP\-concept. The port is not complete yet, future work
   on it is recommended.


%T Synchronisation in a Multithreaded Processor
%A Shondip Sen, Henk Muller, David May
%E Peter H. Welch, André W. P. Bakkers
%B Communicating Process Architectures 2000
%X A multithreaded architecture exploits instruction level
   parallelism by interleaving instructions from disjoint
   thread contexts. As each thread executes within its own
   instruction stream with private data (the context
   registers), there is no interdependency between instructions
   from different threads. This allows high resource
   utilisation of a super scalar pipelined processor at a very
   low cost, in terms of complexity and silicon area. A new
   synchronisation mechanism for a multithreaded architecture
   is outlined. Two new instructions have been introduced to
   perform one to one and n\-way synchronisation. The operation
   allows synchronisations to be requested and actioned
   efficiently on chip in as little as four clock cycles.
   Barriers and CSP style channels can easily be constructed
   with this new synchronisation instruction. A brief
   examination of performance of this multithreaded
   architecture shows that the optimum number of contexts per
   multithreaded processing element is four, based on test
   programs.


%T Blocking System Calls in KRoC/Linux
%A Frederick R. M. Barnes
%E Peter H. Welch, André W. P. Bakkers
%B Communicating Process Architectures 2000
%X This paper describes an extension to Kent Retargetable occam
   Compiler (KRoC), which enables the execution of a blocking
   call, without blocking the occam\-kernel. This allows a
   process to make a blocking system call (eg, read, write),
   without blocking processes running in parallel with it.
   Blocking calls are implemented using Linux clones which
   communicate using shared memory, and synchronise using
   kernel level semaphores. The usefulness of this is apparent
   in server applications with a need to handle multiple
   clients simultaneously. An implementation of an occam
   web\-server is described, which uses standard TCP sockets
   via an occam socket library. The web\-server comes with the
   ability to execute CGI scripts as well as dispensing static
   pages, which demonstrates some level of OS process
   management from within occam. However, this mechanism is not
   limited to blocking in the Linux kernel. On multi\-processor
   machines, the clones are quite free to be scheduled on
   different processors, allowing computationally heavy
   processing to be performed aside the occam world, but still
   with a reasonable level of interaction with it. Using them
   in this way provides a coarse\-grained level of parallelism
   from within the fine\-grained occam world.


%T Post\-Mortem Debugging in KRoC
%A David C. Wood, Frederick R. M. Barnes
%E Peter H. Welch, André W. P. Bakkers
%B Communicating Process Architectures 2000
%X A simple post\-mortem debugging facility has been added to
   KRoC, to identify and locate run\-time errors, including
   deadlock. It has been implemented for the SPARC/Solaris and
   i386/Linux versions of KRoC.


%T An Experiment with Recursion in occam
%A David C. Wood
%E Peter H. Welch, André W. P. Bakkers
%B Communicating Process Architectures 2000
%X An experimental version of KRoC has been written that
   implements recursion in occam, using Brinch Hansen\[rs]s
   algorithm for allocating activation records. It shows that
   efficient parallel recursion is possible in occam


%T Using Java for Parallel Computing \- JCSP versus CTJ
%A Nan C. Schaller, Gerald H. Hilderink, Peter H. Welch
%E Peter H. Welch, André W. P. Bakkers
%B Communicating Process Architectures 2000
%X Java provides support for concurrent and parallel
   programming throughthreads, monitors and its socket and
   Remote Method Invocation (RMI) classes.However, there have
   been many concerns expressed about the way in which
   thissupport is provided, e.g., [1][2], citing problems such
   as improper implementation ofmonitors and difficulty of
   programming with threads. Hoare’s CommunicatingSequential
   Processes (CSP) [3][4][5] model fully specifies thread
   synchronizationand is based on processes, compositions, and
   channel communication. It provides amathematical notation
   for describing patterns of communication using
   algebraicexpressions and contains formal proofs for
   analyzing, verifying and eliminatingundesirable conditions,
   such as race hazards, deadlocks, livelock, and
   starvation.Two independent research efforts provide a CSP
   based process\-oriented designpattern for concurrency
   implemented in Java: Communicating Sequential Processesfor
   Java (JCSP) [6] and Communication Threads in Java (CTJ) [7].
   In this paper, wecompare these two packages, looking at the
   philosophy behind their development,their similarities,
   their differences, their performance, and their use.


%T occam on Field Programmable Gate Arrays \- Optimising for Performance
%A Roger M. A. Peel, Barry M. Cook
%E Peter H. Welch, André W. P. Bakkers
%B Communicating Process Architectures 2000
%X This paper shows how the parallel occam code for a graphics
   application has been compiled to run on a Field Programmable
   Gate Array (FPGA). This application has stringent timing
   constraints, and many optimisations to the sequencing of
   operations and occam constructs have been employed to meet
   them. In particular, two crucial pipelined processes are
   shown to operate with no control overhead despite containing
   parallel and looping constructs and channel communications.


%T libcsp \- a Building mechanism for CSP Communication and Synchronisation in Multithreaded C Programs
%A Rick D. Beton
%E Peter H. Welch, André W. P. Bakkers
%B Communicating Process Architectures 2000
%X A C library is described which exists to support
   synchronisation and communication in the CSP model using the
   Posix Threads API as its basis. This differs from other
   notable approaches (e.g. [Moores:1999]) in that it uses
   Posix Threads. Whilst this approach has drawbacks, its main
   achievement is being easily adopted by people already
   familiar with Posix Threads and being useful to a wide range
   of target platforms.


%T CSP: Arriving at the CHANnel Island (an Industrial Practitioner\[rs]s Diary: in Search of a New Fairway)
%A Øyvind Teig
%E Peter H. Welch, André W. P. Bakkers
%B Communicating Process Architectures 2000
%X This paper is a non\-academic hands\-on log of practical
   experiences of software engineering problems, where the
   process leading to the decision to use CSP to program
   real\-time systems is on trial. A new and hopefully
   objective decision process is instigated. What we have
   previously learnt by using CSP in embedded real\-time
   process control is used as subjective basis (or bias?) for
   the new process. The conclusion seems to be that CSP should
   be sufficiently future\-proof to justify its use even in new
   projects. The term CSP is here used as shorthand for both
   the CSP language proper and different implementations of
   subsets.


%T Native JCSP \- the CSP for Java library with a Low\-Overhead CSP Kernel
%A James Moores
%E Peter H. Welch, André W. P. Bakkers
%B Communicating Process Architectures 2000
%X The JCSP library provides a superior framework for building
   concurrent Java applications. Currently, CSP is a collection
   of classes that uses the standard Java Threads mechanism to
   provide low\-level facilities such a process scheduling and
   synchronization. The overheads of using Java Threads can be
   quite large though, especially for synchronization and
   context switching. This paper begins by describing various
   options for increasing performance, and then how the
   standard Java threads work. The integration of the
   low\-overhead CCSP run\-time system into a Linux\-based Sun
   JDK 1.2.1 Java Virtual Machine is then described. This
   integration provides the low\-level support required to
   dramatically increase the performance of the JCSP
   library\[rs]s model of concurrency. The paper then looks at
   the problem of maintaining backward compatibility by
   preserving the functionality of the existing threads
   mechanism on which much legacy code depends. The paper
   finishes by looking at the performance displayed by the
   current prototype JVM and contrasting it with the
   performance of both Green (co\-operatively scheduled) and
   Native (operating\-system scheduled) Java Threads.


%T Formal Analysis of Concurrent Java Systems
%A Peter H. Welch, Jeremy M. R. Martin
%E Peter H. Welch, André W. P. Bakkers
%B Communicating Process Architectures 2000
%X Java threads are synchronised through primitives based upon
   monitor concepts developed in the early 1970s. The semantics
   of Java\[rs]s primitives have only been presented in natural
   language \-\- this paper remedies this with a simple and
   formal CSP model. In view of the difficulties encountered in
   reasoning about any non\-trivial interactions between Java
   threads, being able to perform that reasoning in a formal
   context (where careless errors can be highlighted by
   mechanical checks) should be a considerable confidence
   boost. Further, automated model\-checking tools can be used
   to root out dangerous states (such as deadlock and
   livelock), find overlooked race hazards and prove
   equivalence between algorithms (e.g. between optimised and
   unoptimised versions). A case study using the CSP model to
   prove the correctness of the JCSP and CTJ channel
   implementations (which are built using standard Java monitor
   synchronisation) is presented. In addition, the JCSP
   mechanism for ALTing (i.e. waiting for and, then, choosing
   between multiple events) is verified. Given the history of
   erroneous implementations of this key primitive, this is a
   considerable relief.


If you have any comments on this database, including inaccuracies, requests to remove or add information, or suggestions for improvement, the WoTUG web team are happy to hear of them. We will do our best to resolve problems to everyone's satisfaction.

Copyright for the papers presented in this database normally resides with the authors; please contact them directly for more information. Addresses are normally presented in the full paper.

Pages © WoTUG, or the indicated author. All Rights Reserved.
Comments on these web pages should be addressed to: www at wotug.org

Valid HTML 4.01!