Papers

The following papers, presented at previous WoTUG conferences, are available in full text here. Some are by reference to the author's site, while others are stored on this server.

WoTUG-20

Publication Information:

WoTUG 20: Parallel Programming and Java
IOS Press,
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands. ISBN 80 5199 336 6

Title:	Scriptic: Parallel Programming in Extended Java
Authors:	Andre van Delft
Abstract:	Scriptic is an expression based extension to the Java programming language, targeted at user interfaces, simulations and parallel computing on shared memory systems. The extras are mainly founded on the theory of Process Algebra: constructs for non-deterministic choice, parallelism and communica-tion. By default, these parallel constructs have interleaving seman-tics, rather than multi-threading or forking. Specific Java code fragments may run in their own threads or handle events from the windowing system. This makes interactive applications such as arcade games execute as fast as corresponding plain Java versions. GUI components such as buttons and menu items are enabled and disabled when applicable, without additional programming. This paper covers an example application in Scriptic, an overview of the language constructs, the implementation, originality, previous work and current work.
Bibliography:

Title:	Higher-Order Concurrency in Java
Authors:	Erik D. Demaine
Abstract:	In this paper we examine an extension to Hoare's Communicating Sequential Processes model called higher-order concurrency, proposed by Reppy. In this extension, communication algorithms (or events) are first-class objects and can be created and manipulated dynamically. In addition, threads are automatically garbage collected and channels are first-class, that is, they can be passed over other channels. We describe the design of a Java package that implements the main features of higher-order concurrency, with similar ease-of-use to Reppy's Concurrent ML system. Our implementation can be easily extended to use a distributed system, which is a major limitation with Concurrent ML. We also hope to bring the idea of higher-order concurrency to a wider audience, since it is extremely powerful and flexible, but currently only well known to the programming-languages community.
Bibliography:

Title:	A Tool for Proving Deadlock Freedom
Authors:	J.M.R. Martin and S.A.Jassim
Abstract:	We describe a tool, programmed in Java, for the formal verification of the absence of deadlock and livelock in networks of CSP processes. The innovative techniques used scale to very large models, unlike the exhaustive state-checking method employed by other tools.
Bibliography:	wotug20	Full Text:	PostScript

Title:	Expanding the Message Passing Library Model with Nested Parallelism
Authors:	C. Rodriguez, F. Sande, C. Leon, F. Garcia
Abstract:	A synchronous extension to the library model for message passing (Inmos, C, PVM, Parmacs, MPI etc.) is presented. This extension, provides a comfortable expression of nested parallelism from inside the message passing model. Furthermore of being a valuable tool for the presentation and teaching of parallel algorithms, the computational results prove that an efficiency similar to or even better than one obtained designing and implementing algorithms using the native language can be obtained.
Bibliography:	wotug20	Full Text:	PostScript, PDF

Title:	How to Design Deadlock-Free Networks Using CSP and Verificatin Tools
Authors:	J.M.R. Martin and S.A.Jassim
Abstract:	The CSP language of C.A.R. Hoare originated as a blackboard mathematical notation for specifying and reasoning about parallel and distributed systems. More recently, sophisticated tools have emerged which provide automated verification of CSP-specified systems. This has led to a tightening and standardisation of syntax. This paper outlines the syntax and semantics of CSP as it is now used and then describes how to design CSP networks, which are guaranteed to be free of deadlock, through a succession of increasingly complex worked examples, making use of the verification tool Deadlock Checker.
Bibliography:	wotug20	Full Text:	PostScript

WoTUG-21

Publication Information:

WoTUG 21: Architectures, Languages and Patterns for Parallel and Distributed Applications
IOS Press,
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands. ISBN 80 5199 391 9

Title:	PAR and STARTP Take the Tanks.
Authors:	Øyvind Teig
Abstract:	The article describes how SPoC (Southampton Portable occam Compiler) has been used - together with hand-written C - in Autronica's new GL-100 radar-based fluid level gauge. The final C-code is running on a Texas TMS320C32 DSP. Some 26000 lines of C-code have been automatically generated from the occam sources. SPoC's non-preemptive scheduling filled our needs with a few exceptions. The main problem has been aligning occam 2 and ANSI-C data abstractions. A realtime system based on language support of high-level concurrency abstractions (as opposed to separate real-time kernel and use of library calls without direct language support) is soon to monitor worldwide charging and discharging of oil-tankers.
Bibliography:	wotug21	Full Text:	HTML

Title:	Parallel Graph Coloring using JAVA
Authors:	Thomas Umland
Abstract:	In this paper a parallel, pipeline oriented version of a well-knownsequential graph coloring heuristic is introduced. Runtime and speedup results of an implementation in JAVA on a four processor machine are presented anddiscussed.
Bibliography:	wotug21	Full Text:	PostScript, PDF

WoTUG-22

Publication Information:

WoTUG 22: Architectures, Languages and Techniques for Concurrent Systems
IOS Press,
Nieuwe Hemweg 6B
1013 BG Amsterdam
The Netherlands. ISBN 80 5199 480 X

Title:	Legacy of the Transputer
Authors:	R. Ivimey-Cook
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.
Bibliography:	wotug22	Full Text:	PostScript, PDF

Title:	BSP Modelling of Two-Tiered Parallel Architectures
Authors:	J.M.R. Martin and A.V.Tiskin
Abstract:	In recent years there has been a trend towards using standard workstation components to construct parallel computers, due to the enormous 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.
Bibliography:	wotug22	Full Text:	PostScript, PDF

Title:	Another side of SPoC: occam's ALTer ego dissected with PC-lint
Authors:	Øyvind Teig
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.
Bibliography:	wotug22	Full Text:	HTML

Title:	Supercomputing Resource Management - Experience with the SGI Cray Origin 2000
Authors:	K. M. Measures, J. M. R. Martin and R. C. F. McLatchie
Abstract:	The Oxford Supercomputing Resource Center OSC was established in April 1998 to provide high-performance computing services to a consortium of Oxford University research groups. The main computer resource, and 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 topica (including parallel computing itself). In this paper we shall describe the queueing and accounting mechanisma we have developed to facilitate effective use of this powerful resource. We shall also describe innovative work in progress to optimise the performance of the machine, using simulation and genetic algorithms.
Bibliography:	wotug22	Full Text:	PostScript, PDF