WoTUG - The place for concurrent processes

Refer Proceedings details

%T PEDFLOW \- A System for Modelling Pedestrian Movement using occam
%A Jon Kerridge, N. McNair
%E Barry M. Cook
%B Proceedings of WoTUG\-22: Architectures, Languages and Techniques for Concurrent Systems
%X Road traffic modelling and simulation is currently well
   provided with a variety of packages dealing with the minute
   detail of road layouts from single isolated junction models
   to complete network simulations. There has also been much
   work in developing assignment models to optimise traffic
   signal sequences. The same is not true in the pedestrian
   modelling arena. With the exception of models dealing with
   railway and airport concourses and models of pedestrian
   movements around sports stadia there is very little support
   for the planner or designer of the pedestrian urban
   environment. The system discussed in this paper provides
   some insights as to the reasons for this and describes a
   highly parallel microscopic model called PEDFLOW (PEDestrian
   FLOW) which attempts to remedy the situation. The model
   operates on a grid size that is equivalent to the space
   occupied by a person at rest. The major difference between
   vehicular and pedestrian movement is that the former really
   has only one degree of freedom, forwards, whereas a
   pedestrian has unlimited two\-dimensional degrees of
   freedom. Vehicular travel is governed by a large number of
   laws and regulations that make it much easier to model.
   Within the pedestrian urban environment there are very few
   laws and regulations and those that do apply are related to
   interactions with vehicles. The design of PEDFLOW is
   discussed and it is shown how the complex behavioural rules
   governing pedestrian movement are captured. The parallel
   architecture underlying the model is described and it shows
   how the maximum possible parallelism is achieved among all
   the moving pedestrians at any one time. The performance of
   the model is then presented and uses to which the model is
   being put are then briefly presented.

%T Another Side of SPoC: occam\[rs]s ALTer Ego Dissected with PC\-lint
%A Øyvind Teig
%E Barry M. Cook
%B Proceedings of WoTUG\-22: Architectures, Languages and Techniques for Concurrent Systems
%X 26500 lines of Standard C (ANSI C) generated from occam
   sources by the Southampton Portable occam Compiler (SPoC)
   has been analysed by the static analysis tool PC\-lint. The
   target machine is a TMS320C32 DSP where all (the supported)
   C\\[rs]s primitive data types are mapped to 32 bit read and
   writes. This architecture stretches "ANSI"
   C quite a bit, but the "portable" occam
   compiler promised to handle it. Even if we had experienced
   no problems with the generated code and it compiled with all
   error handling enabled, we had to insert some 15\-20
   different global PC\-lint filters plus local filters via
   in\-line C in the occam sources. This was in addition to the
   base\-level filters we also used for hand\-written C. It
   kept PC\-lint quiet, for individual C files as well as
   "global wrap up". By discussing each
   individual filter we arrive at the conclusion that none hid
   errors in the generated C. The analysis revealed a few
   points where the occam language definition could have been
   made stricter. We would like to PC\-lint the generated
   sources with fewer messages disabled \- changes to SPoC are
   therefore suggested. Altogether SPoC seems to have passed
   this test quite well. Even if we have no expertise to modify
   the (open) SPoC sources, this report could be considered as
   contributing to a prospective "Bazaar"
   development model \- to bring forward an even more robust
   compiler for a portable and perhaps prospering occam

%T A Proposal for an Operating System for a Multi\-Processor StrongARM System
%A E. W. K. Liew, Brian C. O'Neill, Adam K. L. Wong, S. Clark, P. D. Thomas, R. Cant
%E Barry M. Cook
%B Proceedings of WoTUG\-22: Architectures, Languages and Techniques for Concurrent Systems
%X This paper describes real\-time software features to support
   parallel processing. Synchronized channel communications are
   implemented as a basic operating system function for a
   distributed memory multi\-processor StrongARM system.
   Inter\-processor communications are handled using the ICR
   C416 packet router switch, which makes the system scalable.
   The system will provide a considerable layer of software
   abstraction and support to the end\-users for developing
   their applications. The kernel layers, inter\-process
   communications, control flow of application software, and
   the stages involved in application development for
   end\-users, are described here. Some performance
   considerations are briefly discussed.

%T BSP Modelling of Two Tiered Architectures
%A Jeremy M. R. Martin, Alex V. Tiskin
%E Barry M. Cook
%B Proceedings of WoTUG\-22: Architectures, Languages and Techniques for Concurrent Systems
%X In recent years there has been a trend towards using
   standard workstation components to construct parallel
   computers, due to the enourmous costs involved in designing
   and manufacturing special\-purpose hardware. In particular
   we can expect to see a large population of SMP clusters
   emerging in the next few years. These are local\-area
   networks of workstations, each containing around four
   parallel processors with a single shared memory. To use
   such machines effectively will be a major headache for
   programmers and compiler\-writers. Here we consider how
   well\-suited the BSP model might be for these two\-tier
   architectures, and whether it would be useful to extend the
   model to allow for non\-uniform communication behaviour.

%T Supercomputing Resource Management \- Experience with the SGI Cray Origin 2000
%A Jeremy M. R. Martin, R. C. F. McLatchie, K. M. Measures
%E Barry M. Cook
%B Proceedings of WoTUG\-22: Architectures, Languages and Techniques for Concurrent Systems
%X The Oxford Supercomputing Centre OSC was established in
   April 1998 to provide high\-performance computing services
   to a consortium of Oxford University research groups. The
   main computer resource, an 84\-processor SGI Cray Origin
   2000 known as Oscar, is being deployed in a wide variety of
   research studies covering biological, medical, chemical,
   mathematical, physical and engineering topics (including
   parallel computing itself). In this paper we shall
   describe the queueing and accounting mechanisms we have
   developed to facilitate effective use of this powerful
   resource. We shall also describe innovative work in progress
   to optimise the performance of this machine, using
   simulation and genetic algorithms.

%T Java Joins IEEE\-1355 in the Home Network
%A Barry M. Cook, N. H. White
%E Barry M. Cook
%B Proceedings of WoTUG\-22: Architectures, Languages and Techniques for Concurrent Systems
%X Issues concerning Home networks are discussed. The two main
   areas are the physical connections used and the
   communications protocols required. Of the physical
   connections available the IEEE\-1355 family is addressed in
   particular. The software protocol proposed consists of
   embedding device drivers within the device itself. The
   device uploads its driver to one or many intelligent units.
   This approach is achieved here by using Java bytecode. It is
   argued that this mechanism eliminates the need for a
   pre\-determined all\-encompassing protocol, provides a
   simple and future\-proof system and ensures that home
   networks can be quite literally plug and play.

%T An Algorithm for Caching Software to Configurable Hardware
%A J. D. Campbell
%E Barry M. Cook
%B Proceedings of WoTUG\-22: Architectures, Languages and Techniques for Concurrent Systems
%X In the same fashion that a memory cache arranges for machine
   instructions and data that are frequently accessed to
   operate from high speed memory, the functionality cache
   installs hardware implementations of frequently executed
   code sequences in reconfigurable hardware. Code sequences
   become candidates for instantiation as hardware if the
   benefits outweigh the costs over some accounting period.
   Algorithms are provided for converting sequences of stack
   manipulations characteristic of executable Java programs
   into systolic processing circuitry and mapping that
   machinery into networks of FPGAs (Field Programmable Gate

%T CSP/occam on Shared Memory Multiprocessor Workstations
%A Kevin Vella, Peter H. Welch
%E Barry M. Cook
%B Proceedings of WoTUG\-22: Architectures, Languages and Techniques for Concurrent Systems
%X This paper outlines the design and performance of a system
   for executing occam programs on multiprogrammed shared
   memory multiprocessor workstations. In particular, a fast
   SMP scheduler that executes process code generated by the
   standard KRoC compiler (originally designed for
   uniprocessors) is described; new wait\-free
   multiprocessor\-safe algorithms for both committed and
   alternative CSP channel communication operations are
   presented; a technique for allowing surplus processors to
   idle altruistically under a multiprogrammed regime is
   outlined. The run\-time performance of the system is
   measured under a range of process granularities on one to
   four processors, using a synthetic benchmark. The
   performance of two real applications, namely Quickersort and
   matrix multiplication, is then analysed in some detail.
   Finally, alternative scheduling strategies to further
   improve the scalability of the system under conditions of
   very fine process granularity are proposed.

%T User\-Defined Data Types and Operators in occam
%A David C. Wood, James Moores
%E Barry M. Cook
%B Proceedings of WoTUG\-22: Architectures, Languages and Techniques for Concurrent Systems
%X This paper describes the addition of user\-defined monadic
   and dyadic operators to occam, together with some libraries
   that demonstrate their use. It also discusses some
   techniques used in their implementation in KRoC for a
   variety of target machines.

%T CCSP \- A Portable CSP\-Based Run\-Time System Supporting C and occam
%A James Moores
%E Barry M. Cook
%B Proceedings of WoTUG\-22: Architectures, Languages and Techniques for Concurrent Systems
%X CCSP is a highly portable run\-time system that conforms to
   the ideas of CSP and supports both the C and occam
   programming languages. Its aim is to further the use of the
   CSP mind\-set in both industrial and academic applications.
   The run\-time system implements a useful and efficient
   subset of the basic CSP constructs. It allows occam\-style
   designs to be programmed in C, thereby allowing full use of
   the optimisation phases of standard C compilers. It supports
   the KRoC occam system for Linux/PC platforms. In addition, a
   number of features have emerged from industrial
   collaboration as essential for soft real\-time systems in
   the real world. These include: prioritised scheduling with
   32 priority levels, integration of communications hardware
   to provide support for distributed processing, and access to
   a highly accurate real\-time clock. This paper discusses the
   high level structure and functionality of the features

%T Hard and Soft Priority in CSP
%A Adrian E. Lawrence
%E Barry M. Cook
%B Proceedings of WoTUG\-22: Architectures, Languages and Techniques for Concurrent Systems
%X Parallel systems which include priority can experience
   conflicts when two concurrent processes assign different
   priorities to the same actions. There are at least two ways
   to resolve the difficulty: one is to halt; the other is to
   declare a draw and allocate all the offending actions the
   same priority. In CSPP these are called respectively hard
   and soft priority. Originally CSPP included only hard
   priority. Here we extend the language to include soft
   priority as well. The Acceptances semantics which is used to
   define CSPP does not require modification: it captures both
   soft and hard behaviours.

%T Legacy of the Transputer
%A Ruth Ivimey-Cook
%E Barry M. Cook
%B Proceedings of WoTUG\-22: Architectures, Languages and Techniques for Concurrent Systems
%X The Inmos transputer was more than a family of processor
   chips; it was a concept, a new way of looking at system
   design problems. In many ways that concept lives on in the
   hardware design houses of today, using macrocells and
   programmable logic. New Intellectual Property (IP) design
   houses now specialise in the market the transputer
   originally addressed, but in many cases the multi\-threaded
   software written for that hardware is still designed and
   written using the techniques of the earlier sequential
   systems. The paper discusses the original aims of the
   transputer as a system design component, how they have been
   addressed over the intervening decades and where we should
   be focussing our thoughts for the new millennium.

%T Occam on Field Programmable Gate Arrays \- Steps towards the Para\-PC
%A Barry M. Cook, Roger M. A. Peel
%E Barry M. Cook
%B Proceedings of WoTUG\-22: Architectures, Languages and Techniques for Concurrent Systems
%X At the April 1998 WoTUG conference (WoTUG\-21), it was
   reported that ST Microelectronics was ceasing production of
   most of the transputer family and its associated serial link
   components. The possibility of WoTUG members producing
   transputer\-like devices to emulate many of the
   transputer\\[rs]s parallel processing and communication
   concepts was aired. The authors left this meeting with the
   challenge of designing and implementing their own
   transputer, preferably to be built in Field Programmable
   Gate Array (FPGA) devices rather than custom or semi\-custom
   silicon, for ease of prototyping and for flexibility of
   modification and
   re\-use.</p><p> One year later,
   this paper outlines the progress that has been made. Rather
   than just producing processor logic using the standard logic
   design methods, the authors have written a compiler that
   translates occam into a number of output formats that can be
   fed to various logic implementation packages. Occam programs
   may, however, be joined to logic modules designed in a
   conventional fashion, using synchronised channels in the
   usual manner. In addition to the DS\-Link interface that was
   announced by 4\-Links at WoTUG\-21, an OS\-Link module has
   been designed by the authors, and both of these may provide
   external communication interfaces between occam\-based
   hardware and the outside
   world.</p><p> Although in their
   early stages, this paper illustrates several designs that
   show how occam may be used to specify small processors
   suitable for mapping onto FPGAs. It also shows how occam is
   an ideal fast prototyping mechanism for peripheral
   interfaces that connect to INMOS Links.

%T A Distributed Real Time Java System Based on CSP
%A Gerald H. Hilderink, Jan F. Broenink, André W. P. Bakkers
%E Barry M. Cook
%B Proceedings of WoTUG\-22: Architectures, Languages and Techniques for Concurrent Systems
%X Real\-time embedded systems in general require a reliability
   that is orders ofmagnitude higher than what is presently
   obtainable with state of the art C programs. Thereason for
   the poor reliability of present day software is the
   unavailability of a formalismto design sequential C
   programs.The use of the CSP channel concept not only
   provides a formal base for inherentlyconcurrent real\-time
   embedded system design it also adds a parallel dimension to
   objectoriented programming that is easily understood by
   programmers.The CSP channels as implemented in Java replaces
   the hazardous use of multi threadedprogramming with an
   unambiguous design concept that is easy to reason about.
   Multithreaded programming is completely removed from the
   programmer who is merelyrequired to program small sequential
   tasks that communicate with each other via theseCSP
   channels. The channel concept that has been implemented in
   Java deals with singleandmulti processor environments and
   also takes care of the real\-time priority
   schedulingrequirements. For this, the notion of priority and
   scheduling have been carefullyexamined and as a result it
   was reasoned that both priority and scheduling code should
   beattached to the communicating channels rather than to the
   processes. Moreover in theproposed system, the notion of
   scheduling is no longer connected to the operating systembut
   has become part of the application instead. One has to get
   used to the idea that manyschedulers may be running in
   different parts of a program. The software implementationof
   the Java channel class may be obtained through:

%T Communicating Threads for Java
%A Jan F. Broenink, André W. P. Bakkers, Gerald H. Hilderink
%E Barry M. Cook
%B Proceedings of WoTUG\-22: Architectures, Languages and Techniques for Concurrent Systems
%X The Java * thread model provides support for multithreading
   within the language and runtime system of Java. The Java
   synchronization and scheduling strategy is poorly specified
   and turns out to be of unsatisfactory real\-time
   performance. The idea of Java is to let the underlying
   operating system specify the synchronization and scheduling
   principles. This may possibly result in different behavior
   on different operating systems whereas Sun claims Java to be
   system independent – "write once, run
   everywhere". In this paper we present a
   comprehensive specification for a new thread model for the
   Java platform.The theory of CSP fully specifies the behavior
   of synchronization and scheduling of threads at a higher
   level of abstraction, which is based on processes,
   compositions and synchronization primitives. The CSP concept
   is well thought\-out and has been proven to be successful
   for realizing concurrent software for real\-time and
   embedded systems. The Communicating Threads for Java (CTJ)
   packages that is presented in the paper provides a reliable
   CSP/thread model for Java. The CTJ software is available
   from our URL http://www.rt.el.utwente.nl/javapp.

%T Fine Grain Parallel Processing on Commodity Platforms
%A R. W. Dobinson, P. D. V. van der Stok, Marcel Boosten
%E Barry M. Cook
%B Proceedings of WoTUG\-22: Architectures, Languages and Techniques for Concurrent Systems
%X We present a tight integration of a user\-level thread
   scheduler and a zero\-copy messaging system that has been
   designed and optimized for scalable and efficient
   fine\-grain parallel processing, on commodity platforms,
   with support for fault\-tolerance. The system delivers most
   of the performance of the underlying communication hardware
   to a multi\-threaded application level, while introducing
   little CPU overhead. This is demonstrated by a performance
   analysis of an implementation using off\-the\-shelf
   commodity products: PCs, running the Linux operating system,
   equipped with Fast and Gigabit Ethernet network interface

%T CSP for Java: Multithreading for All
%A André W. P. Bakkers, G. S. Stiles, Peter H. Welch, Gerald H. Hilderink
%E Barry M. Cook
%B Proceedings of WoTUG\-22: Architectures, Languages and Techniques for Concurrent Systems
%X Many internet, real\-time and embedded applications are most
   naturally designed using concurrency. Unfortunately, the
   design of concurrent (multithreaded) programs has the
   reputation of being extremely difficult and dangerous, due
   to the possibility of deadlock, livelock, race hazards, or
   starvation \- phenomena not encountered in single\-threaded
   programs. Lea [1] emphasizes concern for the apparent
   difficulty: "Liveness considerations in concurrent
   software development introduce context dependencies that can
   make the construction of reusable components harder than in
   strictly sequential settings." Two approaches he
   suggests for design sound tedious and perhaps risky:
   "Top\-down (safety first): Initially design methods
   and classes assuming full synchronization (when applicable),
   and then remove unnecessary synchronization as needed to
   obtain liveness and efficiency...Bottom up (liveness first):
   Initially design methods and classes without concern for
   synchronization policies, then add them via composites,
   subclassing, and related layering techniques..."
   Both suggest lengthy sessions of patching and testing until
   the application appears to work as desired. Even those
   intimately connected with Java seem reluctant to employ more
   than a single thread. The Swing documentation states
   "If you can get away with it, avoid using threads.
   Threads can be difficult to use, and they make programs
   harder to debug. In general, they just aren\\[rs]t necessary
   for strictly GUI work, such as updating component
   properties" [2]. Oaks and Wong [3], also associated
   with Sun, are more positive, but note that
   "Deadlock between threads competing for the same
   set of locks is the hardest problem to solve in any threaded
   program. It\\[rs]s a hard enough problem, in fact, that we
   will not solve it or even attempt to solve it."
   Later they state "Nonetheless, a close examination
   of the source code is the only option presently available to
   determine if deadlock is a possibility..." and add
   that no tools exist for detecting deadlock in Java
   programs. We feel, however, based on fifteen years of
   experience, that concurrent approaches are the best way to
   design most programs. Done properly (e.g., using CSP [4])
   this results in better understanding of the problem and the
   solution, and leads to much cleaner implementations. A
   tremendous amount of work has been done on and with CSP in
   recent years, and the present state of the language and the
   tools offers the Java programmer excellent facilities for
   the design and analysis of multithreaded programs.
   Furthermore, Java designs based on CSP class libraries can
   now be verified against formal specifications and checked
   for deadlock and livelock with CASE tools \- prior to
   implementation. We present the CSP model (processes,
   channels, events, networks) and its binding into (100% Pure)
   Java through the CSP class libraries developed at Kent [5]
   and Twente [6]. We describe some of the tools associated
   with CSP (e.g., FDR [7]) and demonstrate, in several
   practical applications, their use for checking
   specifications and proving the absence of deadlock. We
   emphasize that CSP concepts are easy to understand and apply
   and that the engineering benefits they confer on system
   design and implementation are significant for both
   real\-time and non\-real\-time multithreaded systems.

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!