2003 Proceedings details

The high-performance computing community has developed numerous Java packages that support parallel and distributed computing. Most of these packages are designed for the typical parallel message passing and shared memory architectural paradigms. This paper presents the results of a recent study that included a web search for such packages, describes the paradigms implemented in them, and evaluates their performance on a parallel, 4-processor SMP machine using three benchmark programs that represent a mix of typical parallel applications, chosen from The Java Grande Benchmark Suite. A brief description of each package and a discussion its ease of installation and use are also provided.

This paper presents a novel development method for interactive and distributedapplications. The benefit that this method provides is that the design gives clearguidance towards the implementation. The method is based on three mainelements: a concept of synchronous active objects that is closely related to thatfound in CSP; the Java environment; and a selection of the diagrams defined byUML. This approach alleviates many of the most serious problems that areencountered when using GUI builders, which hide the application structures andso make it difficult to devise sound architectures. The final part of the paper brieflydescribes an application generator that will help a developer to implement a designwhich is developed according to the approach advocated here.

An update will be presented on the progress in establishing the Honeysuckleprogramming language [1] and its formal foundations. The latter are formallyaddressed in a paper currently under review for journal publication [2], but willbe summarised. They include formal definitions of service protocol plus servicenetwork/component (SNC) and the PSA design rule (PSADR), from which aproof of a priori deadlock-freedom emerges directly. Freedom from priority conflict(and thus inversion) is also easily guaranteed. Closure in the definition of systemand component guarantees true compositionality under both concurrency andprioritised alternation.

In this paper we propose a distributed, replicated block device for The Gridbased on the the replication algorithm of Y. Amir[1]. The end goal is to supportapplication-specified semantics, both wrt. replication strategy and the consistencymodel used for reads and writes.We list the proposed features of the Grid Block Device and discuss various methodsof implementation.

Distributed Shared Memory (DSM) has many advantages in heterogeneousenvironments, such as geographically distant clusters or The Grid. These includes:locality utilization and replication transparency. The fact that processes communicateindirectly through memory rather than directly, is giving DSM these advantages.This paper presents the design of Global PastSet (GPS) which is a DSM systemtargeted at global area networks. GPS is based on the DSM system PastSet [1] that hasbeen very effective in homogeneous cluster environments. GPS utilizes consistencycontrol migration and replication to scale in heterogeneous environments. This hasresulted in a token-based mutual exclusion algorithm that considers locality and analgorithm for locating replicas. GPS has been simulated in multi-cluster environmentswith up to 2048 nodes with very promising results.

We present tools that automatically convert a subset of machine-readable CSPscript to executable Java or C code. CSP is used to design and verify thecorrectness of large and complex systems of processes that interact only viaexplicit synchronous messages. These systems can be implemented in Javausing CTJ or JCSP, packages that add CSP-like features to Java, or in CCSP, apackage that adds similar features to standard C. Implementation of CSP systemscan be tedious and error-prone when large numbers of processes andcommunications are involved, and sorting out errors in channel naming or theordering of messages can be very time-consuming. The tools we have developedminimize such problems by converting the verified CSP descriptions ofcommunicating processes directly into Java or C code, thus guaranteeing thatchannels are correctly named and the communications occur in the proper order.This process can significantly cut development time.

This paper describes a processor and an inter-processor communications interfaceintegrated on a single chip for use in a distributed processing system. The system isbased on work of the electronic systems design and parallel processing group at theNottingham Trent University. The four main elements of the chip design areprocessor, memory, communication interface and packet routing switch all integratedunto one chip. This design is achieved by the use of the ALTERA ARM basedExcalibur system on a programmable chip (SOPC) containing an embedded processorand programmable logic. The paper describes the communication features andimplementation carried out by the research group to achieve this single chip processor.

Both Lawrence’s HCSP [1] and Smith, et al’s VCR [2] (an earlier versionappears in [3]) extend CSP [4] with representations of truly concurrent events. Previously,VCR was described using an operational semantics, while the semantics ofHCSP’s Acceptances model, like those of the predominant CSP models described byRoscoe [5] (e.g., Traces, Failures / Divergences), are denotational. We now present adenotational semantics for VCRand, in so doing, propose an extension toHCSP (andpossibly other existing CSP models) to support View-Centric Reasoning. This workbrings VCR a step closer to being drawn within Hoare and He’s Unifying Theories ofProgramming [6] for further comparisons.

Hiding is an important and characteristic part of CSP. Defining it in thepresence of priority for CSPP needs care. The ideas of overtures and hesitant offersintroduced here arise naturally in the context of Acceptances. They provide clearinsight into the behaviour of hidden processes. And particularly illuminate the originof the nondeterminism which frequently arises from hiding.Keywords: CSP; CSPP; Denotational semantics; formal methods; concurrency; parallelsystems; occam; hardware compilation; priority; hiding.

Sampling and timing is considered a responsibility of the environment ofcontroller software. In this paper we will illustrate a concept whereby anenvironmental process and multi-way events play an important role in applyingtiming for untimed CSP software architectures. We use this timing concept forbuilding our control applications based on CSP concepts and with our CSP for C++(CTC++) library. We present a concept of sampling of control applications that isorthogonal to the application. This implies global timing on the basis of timedevents. We also support traditional local timing on the based of timed processes,

This paper describes a new approach to parallel processing within thewell targetted application domain of wireless communications systems, using thepicoArrayTM. The picoArrayTM is a tiled-processor architecture, containing 430 heterogeneousprocessors, connected through a novel, compile-time scheduled interconnect.We show how the features of the picoArrayTM allow deterministic processing tobe achieved, and how the tool chain allows programming to be performed effectivelyin a combination of high level assembly language and C. By handling a wide varietyof types of processing within the picoArrayTM a single design flow can be usedto produce complex communications systems. The effectiveness of this approach isdemonstrated through the use of the picoArrayTM to build a working 3G base-station.

This paper reports on a CSP library for C++, developed over the past yearat the University of Kent. It is based on the OO-design and API of JCSP and thelightweight algorithms of KRoC occam, with extensions to exploit specific C++ capabilities(such as templates). Both user-level and operating system threads are usedto provide a range of implementation options and semantics (e.g. for managing blockingsystem calls intelligently) that run efficiently under eitherWindows or Linux. Thelibrary is presented from the user’s point of view, mainly by way of a tutorial. Implementationdetails are also outlined and some benchmark results given. The performanceof C++CSP is between that of KRoC occam and JCSP — fairly close toKRoC.

This paper aims to demonstrate that concepts from Distributed Artificial Intelligence are very useful to design concurrent systems. The BESA framework and the AOPOA methodology are introduced as tools to achieve this goal. The Behavior-oriented, Event-driven and Social-based Agent (BESA) framework combines the concepts of MultiAgent Systems with the design of concurrent systems: an agent can be constructed as a set of behaviors; the notion of behaviors can be directly applied to concurrent systems design using the Agent Oriented Programming paradigm. The internal architecture of a BESA agent integrates two important features: a modular composition of behaviors and an event dispatcher based in a select like mechanism. The Agent Oriented Programming based in an Organizational Approach (AOPOA) methodology provides a systematic procedure to build complex system based in three concepts: a hierarchical recursive decomposition of the system, a goal-oriented role identification, and an evolution of the cooperation relationships linking the system components.

We describe some more recent developments of the SPoC system. We describe a new module in the occam compiler which performs substantial simplifications of the run-time demands made by the compiled code. This has been used successfully both to target a simple PIC microcontroller and to generate input for the SMV model checker.

The Trebuchet is a hardware architecture for machines implementedfrom conventional software source programs. It is pseudo-asynchronous in that itdecouples the system clock from the computational logic, reducingelectromagnetic interference, smoothing current draw, and reducing pipelinelatency, key benefits of asynchronous designs. Performance of example programsis given.

Traditional component interaction is based on interface calls and callbacks. Such interaction can introduce integration faults, i.e., side effects at the moment of component integration. Solutions to such problems can be hard to apply, and may require drastic changes in the design of the involved components. This paper introduces Formal Contracts, a software construct that allows side-effect free component interaction, and thereby avoids the introduction of integration faults. Furthermore, via a state machine representing the inter-component contract, Formal Contracts, in addition to the static aspects, formally specify the dynamic aspects of component interaction. Formal Contracts are a pragmatic software mechanism that supports the full development cycle: from the specification and decomposition until the debugging, composition, and test of a system.

KRoC.net is an extension to KRoC supporting the distribution of occamchannels over networks, including the internet. Starting in 2001, the development ofKRoC.net has gone through a number of stages, each one making the system moreflexible, transparent and dynamic. It now enables the occam programmer to set upand close network channels dynamically. Configuration has been simplified. All occamPROTOCOLs can now be sent over network channels, without need for conversion.Many of the new dynamic features in occam have been used to improve KRoC.net.Many of the concepts in KRoC.net are similar to those in the JCSP Network Edition(JCSP.net), KRoC.net’s counterpart in the JCSP world. This paper will give an overviewover KRoC.net, its usage, its design and implementation, and its future. It willalso provide some benchmarks and discuss how the new occam features are beingused in the latest KRoC.net version.

Future wireless communication systems require novel techniques to increasethe bitrate, coverage and mobility. One of these techniques is spatial multiplexingand we have investigated the use of a CSP-based kernel in the implementation ofa spatial multiplexing testbed. It turns out that the use of the CSP-based kernel notonly provides a good way of system modeling, but also provides a very scalable softwarearchitecture for the testbed. In future, we can change several system parameterswithout changing the software architecture. With the testbed we were able to verifythe concept of spatial multiplexing in an office environment.

Closed loop control systems typically contain multitude of spatially distributed sensors and actuators operated simultaneously. So those systems are parallel and distributed in their essence. But mapping this parallelism onto the given distributed hardware architecture, brings in some additional requirements: safe multithreading, optimal process allocation, real-time scheduling of bus and network resources. Nowadays, fault tolerance methods and fast even online reconfiguration are becoming increasingly important. All those often conflicting requirements, make design and implementation of real-time distributed control systems an extremely difficult task, that requires substantial knowledge in several areas of control and computer science. Although many design methods have been proposed so far, none of them had succeeded to cover all important aspects of the problem at hand. [1] Continuous increase of production in embedded market, makes a simple and natural design methodology for real-time systems needed more then ever.

This paper presents ‘occwserv’, the occam web-server. This is a highlyconcurrent web-server, written in the occam multi-processing language, that supportsthe majority of the HTTP/1.1 protocol. Dynamic process and channel creation mechanismsare used to create scalable ‘server-farms’, each responsible for a particular webserverfunction - for example, reading client requests or running CGI processes. Thedesign of the web-server is presented, along with some early performance benchmarkresults. Although performance may appear a limiting factor (when compared to otherweb-servers such as Apache), much is gained from the simplicity and security of occam.Extending the web-server with new functionality, for example, is intuitive andlargely trivial - with the guarantees that code is free from race-hazard and aliasingerrors. An experimental non-standard addition, the OGI (occam Gateway Interface),is also presented. This provides a mechanism for dynamically loading and attachingpre-compiled occam processes to the running web-server, that can then handle oneor multiple client connections. A text-based style adventure game is examined briefly,that allows multiple clients to interact within a "multi-user dungeon" (MUD) styleenvironment.

Operating-systems are the core software component of many modern computersystems, ranging from small specialised embedded systems through to largedistributed operating-systems. This paper presents RMoX: a highly concurrent CSPbasedoperating-system written in occam. The motivation for this stems from theoverwhelming need for reliable, secure and scalable operating-systems. The majorityof operating-systems are written in C, a language that easily offers the level offlexibility required (for example, interfacing with assembly routines). C compilers,however, provide little or no mechanism to guard against race-hazard and aliasing errors,that can lead to catastrophic run-time failure (as well as to more subtle errors,such as security loop-holes). The RMoX operating-system presents a novel approachto operating-system design (although this is not the first CSP-based operating-system).Concurrency is utilised at all levels, resulting in a system design that is well defined,easily understood and scalable. The implementation, using the KRoC extended occam,provides guarantees of freedom from race-hazard and aliasing errors, and makesextensive use of the recently added support for dynamic process creation and channelmobility. Whilst targeted at mainstream computing, the ideas and methods presentedare equally applicable for small-scale embedded systems - where advantage can bemade of the lightweight nature of RMoX (providing fast interrupt responses, for example).

This paper explores the idea of the processor as an asynchronous network,called the micronet, of functional units which compute concurrently and communicateasynchronously. A micronet-based asynchronous processor exposes spatial as well astemporal concurrency. We analyse the performance of the ‘processor-as-a-network’by comparing three scheduling algorithms for exploiting Instruction Level Parallelism(ILP). Schedulers for synchronous architectures have relied on deterministic instructionexecution times. In contrast, ILP scheduling in micronet-based architectures is achallenge as it is less certain in advance when instructions start execution and whenresults become available. Performance results comparing the three schedulers are presentedfor SPEC95 benchmarks executing on a cycle-accurate model of the micronetarchitecture.

The accuracies of three equations to determine the size of populations for serial and parallel genetic algorithms are evaluated when applied to a parallel genetic algorithm that schedules tasks on a cluster of computers connected via shared bus. This NP-complete problem is representative of a variety of optimisation problems for which genetic algorithms (GAs) have been shown to effectively approximate the optimal solution. However, empirical determination of parameters needed by both serial and parallel GAs is time-consuming, often impractically so in production environments. The ability to predetermine parameter values mathematically eliminates this difficulty. The parameter that exerts the most influence over the solution quality of a parallel genetic algorithm is the population size of the demes. Comparisons here show that the most accurate equation for the scheduling application is Cantú-Paz' serial population sizing calculation based on the gambler's ruin model [1]. The study presented below is part of an ongoing analysis of the effectiveness of parallel genetic algorithm parameter value computations based on schema theory. The study demonstrates that the correct deme size can be predetermined quantitatively for the scheduling problem presented here, and suggests that this may also be true for similar optimisation problems. This work is supported by NASA Grant NAG9-140.

We use several formal methodologies for developing control applicationsat our Control Engineering research group. An important methodology we use fordesigning and implementing control software architecture is based on CSP concepts.These concepts allow us to glue multidisciplinary activities together and allow forformal stepwise refinement from design down to its implementation. This paperillustrates a trajectory and shows the usefulness of CSP diagrams for a simplemechatronic system. The simulation tool 20-SIM is used for creating the controllaws and our CTC++ package is used for coding in C++.