WoTUG - The place for concurrent processes

BibTeX Proceedings details

BibTex html text dump of PaperDB database.

PaperDB is GPL Software, see: http://paperdb.sourceforge.net.

  title = "{PEDFLOW} - {A} {S}ystem for {M}odelling {P}edestrian {M}ovement using occam",
  author= "Kerridge, Jon and McNair, N.",
  editor= "Cook, Barry M.",
  pages = "1--18",
  booktitle= "{P}roceedings of {W}o{TUG}-22: {A}rchitectures, {L}anguages and {T}echniques for {C}oncurrent {S}ystems",
  isbn= "90 5199 480 X",
  year= "1999",
  month= "mar",
  abstract= "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."
  title = "{A}nother {S}ide of {SP}o{C}: occam's {ALT}er {E}go {D}issected with {PC}-lint",
  author= "Teig, Øyvind",
  editor= "Cook, Barry M.",
  pages = "19--36",
  booktitle= "{P}roceedings of {W}o{TUG}-22: {A}rchitectures, {L}anguages and {T}echniques for {C}oncurrent {S}ystems",
  isbn= "90 5199 480 X",
  year= "1999",
  month= "mar",
  abstract= "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\'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 language."
  title = "{A} {P}roposal for an {O}perating {S}ystem for a {M}ulti-{P}rocessor {S}trong{ARM} {S}ystem",
  author= "Liew, E. W. K. and O'Neill, Brian C. and Wong, Adam K. L. and Clark, S. and Thomas, P. D. and Cant, R.",
  editor= "Cook, Barry M.",
  pages = "37--46",
  booktitle= "{P}roceedings of {W}o{TUG}-22: {A}rchitectures, {L}anguages and {T}echniques for {C}oncurrent {S}ystems",
  isbn= "90 5199 480 X",
  year= "1999",
  month= "mar",
  abstract= "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."
  title = "{BSP} {M}odelling of {T}wo {T}iered {A}rchitectures",
  author= "Martin, Jeremy M. R. and Tiskin, Alex V.",
  editor= "Cook, Barry M.",
  pages = "47--56",
  booktitle= "{P}roceedings of {W}o{TUG}-22: {A}rchitectures, {L}anguages and {T}echniques for {C}oncurrent {S}ystems",
  isbn= "90 5199 480 X",
  year= "1999",
  month= "mar",
  abstract= "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. "
  title = "{S}upercomputing {R}esource {M}anagement - {E}xperience with the {SGI} {C}ray {O}rigin 2000",
  author= "Martin, Jeremy M. R. and McLatchie, R. C. F. and Measures, K. M.",
  editor= "Cook, Barry M.",
  pages = "57--66",
  booktitle= "{P}roceedings of {W}o{TUG}-22: {A}rchitectures, {L}anguages and {T}echniques for {C}oncurrent {S}ystems",
  isbn= "90 5199 480 X",
  year= "1999",
  month= "mar",
  abstract= "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. "
  title = "{J}ava {J}oins {IEEE}-1355 in the {H}ome {N}etwork",
  author= "Cook, Barry M. and White, N. H.",
  editor= "Cook, Barry M.",
  pages = "67--76",
  booktitle= "{P}roceedings of {W}o{TUG}-22: {A}rchitectures, {L}anguages and {T}echniques for {C}oncurrent {S}ystems",
  isbn= "90 5199 480 X",
  year= "1999",
  month= "mar",
  abstract= "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. "
  title = "{A}n {A}lgorithm for {C}aching {S}oftware to {C}onfigurable {H}ardware",
  author= "Campbell, J. D.",
  editor= "Cook, Barry M.",
  pages = "77--86",
  booktitle= "{P}roceedings of {W}o{TUG}-22: {A}rchitectures, {L}anguages and {T}echniques for {C}oncurrent {S}ystems",
  isbn= "90 5199 480 X",
  year= "1999",
  month= "mar",
  abstract= "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
  title = "{CSP}/occam on {S}hared {M}emory {M}ultiprocessor {W}orkstations",
  author= "Vella, Kevin and Welch, Peter H.",
  editor= "Cook, Barry M.",
  pages = "87--120",
  booktitle= "{P}roceedings of {W}o{TUG}-22: {A}rchitectures, {L}anguages and {T}echniques for {C}oncurrent {S}ystems",
  isbn= "90 5199 480 X",
  year= "1999",
  month= "mar",
  abstract= "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."
  title = "{U}ser-{D}efined {D}ata {T}ypes and {O}perators in occam",
  author= "Wood, David C. and Moores, James",
  editor= "Cook, Barry M.",
  pages = "121--146",
  booktitle= "{P}roceedings of {W}o{TUG}-22: {A}rchitectures, {L}anguages and {T}echniques for {C}oncurrent {S}ystems",
  isbn= "90 5199 480 X",
  year= "1999",
  month= "mar",
  abstract= "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."
  title = "{CCSP} - {A} {P}ortable {CSP}-{B}ased {R}un-{T}ime {S}ystem {S}upporting {C} and occam",
  author= "Moores, James",
  editor= "Cook, Barry M.",
  pages = "147--169",
  booktitle= "{P}roceedings of {W}o{TUG}-22: {A}rchitectures, {L}anguages and {T}echniques for {C}oncurrent {S}ystems",
  isbn= "90 5199 480 X",
  year= "1999",
  month= "mar",
  abstract= "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
  title = "{H}ard and {S}oft {P}riority in {CSP}",
  author= "Lawrence, Adrian E.",
  editor= "Cook, Barry M.",
  pages = "169--197",
  booktitle= "{P}roceedings of {W}o{TUG}-22: {A}rchitectures, {L}anguages and {T}echniques for {C}oncurrent {S}ystems",
  isbn= "90 5199 480 X",
  year= "1999",
  month= "mar",
  abstract= "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. "
  title = "{L}egacy of the {T}ransputer",
  author= "Ivimey-Cook, Ruth",
  editor= "Cook, Barry M.",
  pages = "197--211",
  booktitle= "{P}roceedings of {W}o{TUG}-22: {A}rchitectures, {L}anguages and {T}echniques for {C}oncurrent {S}ystems",
  isbn= "90 5199 480 X",
  year= "1999",
  month= "mar",
  abstract= "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."
  title = "{O}ccam on {F}ield {P}rogrammable {G}ate {A}rrays - {S}teps towards the {P}ara-{PC}",
  author= "Cook, Barry M. and Peel, Roger M. A.",
  editor= "Cook, Barry M.",
  pages = "211--228",
  booktitle= "{P}roceedings of {W}o{TUG}-22: {A}rchitectures, {L}anguages and {T}echniques for {C}oncurrent {S}ystems",
  isbn= "90 5199 480 X",
  year= "1999",
  month= "mar",
  abstract= "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\'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. "
  title = "{A} {D}istributed {R}eal {T}ime {J}ava {S}ystem {B}ased on {CSP}",
  author= "Hilderink, Gerald H. and Broenink, Jan F. and Bakkers, Andr\`{e} W. P.",
  editor= "Cook, Barry M.",
  pages = "229--242",
  booktitle= "{P}roceedings of {W}o{TUG}-22: {A}rchitectures, {L}anguages and {T}echniques for {C}oncurrent {S}ystems",
  isbn= "90 5199 480 X",
  year= "1999",
  month= "mar",
  abstract= "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:
  title = "{C}ommunicating {T}hreads for {J}ava",
  author= "Broenink, Jan F. and Bakkers, Andr\`{e} W. P. and Hilderink, Gerald H.",
  editor= "Cook, Barry M.",
  pages = "243--262",
  booktitle= "{P}roceedings of {W}o{TUG}-22: {A}rchitectures, {L}anguages and {T}echniques for {C}oncurrent {S}ystems",
  isbn= "90 5199 480 X",
  year= "1999",
  month= "mar",
  abstract= "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."
  title = "{F}ine {G}rain {P}arallel {P}rocessing on {C}ommodity {P}latforms",
  author= "Dobinson, R. W. and Stok, P. D. V. van der and Boosten, Marcel",
  editor= "Cook, Barry M.",
  pages = "263--276",
  booktitle= "{P}roceedings of {W}o{TUG}-22: {A}rchitectures, {L}anguages and {T}echniques for {C}oncurrent {S}ystems",
  isbn= "90 5199 480 X",
  year= "1999",
  month= "mar",
  abstract= "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 cards."
  title = "{CSP} for {J}ava: {M}ultithreading for {A}ll",
  author= "Bakkers, Andr\`{e} W. P. and Stiles, G. S. and Welch, Peter H. and Hilderink, Gerald H.",
  editor= "Cook, Barry M.",
  pages = "277--279",
  booktitle= "{P}roceedings of {W}o{TUG}-22: {A}rchitectures, {L}anguages and {T}echniques for {C}oncurrent {S}ystems",
  isbn= "90 5199 480 X",
  year= "1999",
  month= "mar",
  abstract= "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\'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\'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!