Refer Proceedings details

%T RT\-DOS \-\- A real\-time distributed operating system for transputers
%A M. Tayh, M. Bor, M. Benmaiza, M. R. Eskicioglu
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X This paper describes the design philosophy of a real\-time
   operating system, RT\-DOS, and its architecture. RT\-DOS is
   a generic name given to a prototype operating system, which
   is a fully\-distributed, message\-based system designed to
   run on a network of transputers. The main objective of
   RT\-DOS is to provide a dynamically reconfigurable work
   platform that adapts to dynamic changes in workloads, allows
   system maintainability and dynamic upgrading, and increases
   system reliability and availability.

%T On the Feasibility of Run\-Time Process Migration in Multi\-transputer Machines
%A Peter Jones, Hojung Cha
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X A number of techniques for the amelioration of message
   transport costs in networked multiprocessor machines have
   been explored. Among these are established approaches such
   as (i) software implementation of message through routing
   systems, (ii) run\-time installation of point\-to\-point
   physical connections between otherwise remote processors and
   (iii) pre\-load manipulation of the machine topology to
   bring communicating processors close together. A further
   technique is proposed. This technique requires the run\-time
   transport of processes, between processors, in order to
   reduce the distance over which communication must take
   place. This paper investigates the feasibility of such an
   approach for multi\-transputer machines and indicates ways
   in which it can be implemented in practice.

%T Broadcast communication in fault tolerant multicomputer systems
%A K. Gresser
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X Fault tolerance can be achieved by means of redundancy.
   Multicomputer architectures allow duplicated tasks to run on
   multiple processors. In this paper we focus on multicomputer
   systems consisting of a small number of processors (4 to
   16). Fault tolerance instrumented in the operating system
   level tolerates hardware faults. This type of fault
   tolerance is known as software implemented fault tolerance.
   The information exchange of the computers requires a
   powerful communication system with fault tolerance
   properties. Since no standard system meets all requirements
   a new design was necessary. This paper describes concept,
   hardware, firmware and performance of the transputer based
   broadcast communication system (BCS).

%T Transputer performance issues using the trollius operating system
%A James R. Jr. Beers, Ros Leibensperger, Moshe Braner, David Fielding
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X The Trollius Opeiating System for distributed multicomputer
   offers different types of message\-passing services,
   incorporating different amounts of overhead. Each of the
   operating system activities required for interprocess
   communication is designed as an individual module or layer.
   The different types of Trollius communication can be
   accessed by turning operating system services on or off, or
   by directly utilizing different layers of
   communication.Basically, there are three layers of internode
   communication. The network layer can be used from any node
   to any other node; the data link layer is for
   nearest\-neighbor communication; and Ihe physical layer uses
   the hardware in the most efficient way possible, but
   requires exclusive use of the link. A separate level, the
   kernel level, is used for intranode communication. Operating
   system services that can be turned on or off include
   buffering and virtual circuits.Two different types of
   benchmarks are used to evaluate the performance of the
   different types of Trollius message\-passing. The first type
   calculates message\-passing lime as the sum of the limes
   required for each individual service or component of Ihe
   process. The decrease in message\-passing lime obtained when
   turning off services can ihus be easily measured. The second
   benchmark measures throughput, the amount of information
   that can be sent from one node to another in a given amount
   of time, for different layers of message\-passing, utilizing
   different sendees. This is the more accurate measure when
   series of messages are sent from one node to another. The
   throughput measurements demonstrate the value of the
   physical layer and of virtual circuits.

%T High performance event and I/O handling on the transputer
%A R. G. Harley, D. C. Levy, A. W. M. Hemme, M. R. Webster
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X If transputers are to be used in high performance control
   applications it is essential that the I/O and event handling
   capabilities of the transputer are well understood. This
   requires insight into the hardware architecture and the low
   level language (guy code) of the transputer. The interface
   between the transputer executing the corresponding control
   process, and the external event generating devices can be
   divided into two main processes, namely interrupt or event
   handling and the I/O or data handling. For maximum
   performance these processes must be handled as quickly and
   efficiently as possible. Some of the issues involved in
   using occam to establish an interrupt handler are discussed
   in [1]. This paper extends that work to show how better
   performance and multiple event handling can be obtained
   efficiently. Several methods of achieving this real world
   interface are examined and, based on an actual design, the
   paper concludes with some recommendations to make the event
   handler more efficient.

%T Evaluation of two systems for distributed message passing in transputer networks
%A N. N. Avramov, A. E. Knowles
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X While special chips for message transfer in
   multi\-transputer machines do not yet exist, there are
   several software solutions which may be used. Dynamic link
   reconfiguration is fastest but requires additional switching
   hardware and a sophisticated common bus to control requests
   from all network nodes. Through\-routing of messages via the
   network is slower but the method is applicable to any
   transputer network. This paper makes a comparison between
   two through\-routing solutions for distributed message
   passing and shows how the parameters of a software
   implementation influence the communication throughput.
   Several conclusions about the improvement of particular
   through\-routing software are made and the results of the
   experimental performance evaluation under different
   conditions are given.

%T An environment for transputer CPU load measurements
%A Giuseppe de Pietro, Umberto Villano
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X In a multiprocessor system an uneven load balancing can
   usually dramatically reduce the performance of the parallel
   program running on it Hence it is of paramount importance to
   be able to estimate the CPU and communication loads of every
   task before the program is actually executed so that the
   optimal application partitioning can be found. In this paper
   the problem of CPU load measurement is tackled, and a
   measurement environment is illustrated in which the
   processes to be allocated to the processors in the network
   are run in quasi\-concurrence on a single Transputer. A
   technique based on active process list manipulation makes it
   possible to perform a fairly accurate measurement of the CPU
   activity of the parallel processes in the application using
   the Transputer internal tinier as a reference clock.

%T An operating environment for control systems
%A K. C. J. Wijbrans, H. G. Tillema, André W. P. Bakkers, Albert L. Schoute
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X This article describes an operating environment for control
   systems. This operating environment contains the basic
   layers of a distributed operating system. Typical for this
   operating environment is that it is designed according to
   the needs of control systems. To do this, first the general
   requirements of a controller have been investigated. Based
   on the requirements posed by controllers as they can be
   found in complex systems, the requirements of the operating
   environment have been derived. This operating environment
   has been implemented on transputers. To test the performance
   of the operating environment, performance indicators were
   chosen and performance measurements were carried out for
   several different strategies. Due to the demanding nature of
   real\-time control systems, special attention has been paid
   to an efficient implementation of a basic kernel.

%T LiBRA \-\- A load balancing tool for a reconfigurable parallel computer
%A Sanjay Tambwekar, U. S. Shukla, A. Paulraj
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X Load balancing in MIMD message\-passing parallel computers
   is essential to make efficient use of the system resources
   and reduce the program runtime. For parallel computers that
   also provide topological ^configurability, it is necessary
   for the load balancing strategy to not only find an optimum
   distribution of tasks to processors, but also to determine
   the best\-suited interconnection pattern for the processors.
   In this paper, we present an off\-line tool, LiBRA, that
   will assist in automating the process of load balancing. The
   user specifies his problem in terms of a computation graph
   and the machine characteristics. LiBRA uses simulated
   annealing with an automatic annealing schedule to generate
   the optimal configuration.

%T Fault tolerant computing with transputers and occam
%A L. J. M. Nieuwenhuis, G. D. Blom
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X In this paper the results of a case study with Transputers
   and Occam for a systematic approach of fault tolerant
   computing is presented. An arbitrary Transputer system can
   be transformed into a fault tolerant version without using
   additional special hardware. Fault tolerance is based on
   software implemented replication. The fault tolerant version
   consists of copies of the original system. Processes on the
   original Transputers can automaticly be transformed into
   versions which can be executed by the Transputers of the
   fault tolerant system. The reliability of the resulting
   system is optimal and performance optimizing properties of
   the original system are preserved.

%T The Development of occam: types, classes and sharing
%A Geoff Barrett
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X The proposed extensions to the occam* language are aimed at
   providing • a more comprehensive type system• support
   for a modular programming style• a facility for sharing
   between processes.The type system is similar to that of many
   modern programming languages but with a careful treatment of
   union types and without recursive types.Although it is
   possible to describe shared objects in occam2, the required
   idiom has an implementation whose complexity is linear in
   the number of users. By introducing a special sort of shared
   bus of channels, this problem can be overcome.The class
   system is designed in such a way as to allow for separate
   compilation and alien code classes to be used in occam
   programs with little overhead and to provide some of the
   abstraction mechanisms which have been recognised as
   beneficial in object\-oriented languages.There are also a
   number of new language features which do not significantly
   change the nature of the language but which do enhance its
   general expressiveness.The first part of this paper presents
   proposed changes to the occam2 reference manual ([1]). The
   second part is a commentary on the decisions which had to be
   made in order to produce the proposal. The section numbers
   of the manual changes correspond to the section numbers of
   the occam2 reference manual where a \[rs] denotes a change
   to an existing section and a letter denotes the insertion of
   a new section.

%T Combining configuration and allocation
%A Dong-Hui Du, Guy Vidal-Naquet
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X This paper describes a method which makes hardware
   configuration transparent to Occam/Transputer users by doing
   automatic configuration of Transputer networks and
   allocation of programs. Some heuristic algorithms of
   combining network configuration with task allocation have
   been put forward. From an Occam program and an initial
   network topology, these algorithms construct a network
   topology which fits best the structure of the program, and
   allocate the program on the network so that its completion
   time is minimized.

%T Towards a distributed implementation of occam
%A Mark Debbage, Mark Hill, Denis A. Nicole
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X Progress has been made in providing a reasonable distributed
   implementation of the occam language. Primarily, this has
   involved the development of a routing kernel with a latent
   channel connection retaining occam syntax. Channel semantics
   are maintained by a message acknowledgement scheme and
   unrestricted message lengths. This provides the user with
   the potential for fully connected process communication
   without restrictions on node valencies or explicit PLACEment
   of any hard links.In addition the user program has been
   severed from any dependency on the topology by allowing
   multiple configuration level PROCESSORS to map onto a single
   transputer. Thus the user code can be run on any network
   which has been configured for the virtual channel
   router.Further development of the system has allowed us to
   implement the dynamic primitives that will be required by a
   compiler for distributed full occam. These include dynamic
   channel creation, remote procedure calls and facilities for
   moving channel ends.

%T Cayley graphs and transputer network configuration
%A Ian R. East, Sabah Jassim
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X The nature and use of Cayley graphs in understanding network
   topology design will be explained. The hypercube topology
   will be presented in group\-theoretic form as an
   illustration and its isomorphism with tori, up to order
   four, will be shown. It will also be shown how to use the
   Cayley graph formulation to scalably configure a hypercube
   (with node process independent of identity within network).
   Lastly, we discuss the application of the Cayley formalism
   to infer and investigate new topologies which exhibit
   superior scaling of size and density to that of the
   hypercube, but which retain degree four and hence are
   suitable for transputer networks.

%T Cooperative priority scheduling in occam
%A Johan P. E. Sunter, K. C. J. Wijbrans, André W. P. Bakkers
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X In this paper a scheduler for variable priority scheduling
   is presented. This scheduler assumes that the processes
   being scheduled cooperate with the scheduler. This
   cooperation introduces some latency in the scheduling of the
   processes. Analytic expressions describing the effect of
   this latency are derived. A variable priority scheduler was
   implemented and results from actual program executions are
   given. These results show that the scheduler can be used to
   schedule control algorithms with simple sequential processes
   with sample frequencies not higher than 2 kHz.

%T Implementation of real\-time scheduling algorithms in a transputer environment
%A Ole Caprani, Jens E. Kristensen, Claus Mørk, Henrik Bo Pedersen, Finn R. Rasmussen
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X A variety of real\-time scheduling algorithms is considered.
   Each algorithm is implemented on the transputer either in
   pure Occam or in Occam supplied with a few low level
   assembly procedures to manipulate the workspace queues. The
   algorithms used are non\-preemptive non\-priority
   scheduling, time\-sliced non\-priority scheduling,
   preemptive fixed priority scheduling (rate\-monotonic
   scheduling) and preemptive dynamic priority scheduling
   (deadline scheduling). Furthermore, it is shown how access
   to shared data can be scheduled to meet time constraints.
   All the implemented scheduling algorithms have been assessed
   through experiments in order to estimate the overhead
   introduced.

%T Multi\-priority scheduling for transputer\-based real\-time control
%A Peter H. Welch
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X A major requirement of real\-time control applications is a
   set of cyclic processes — one for each
   "control\-law". Each process must be
   managed so that it completes each cycle within a fixed time.
   The rate at which each process cycles will be constant, but
   will generally be different for different processes.Current
   transputer hardware provides very fast pre\-emptive
   scheduling for two static priority levels, with
   "round\-robin" management within each
   level. This is not sufficient to manage securely more than
   one such control\-law per transputer — even at very low
   processor loadings. Efficient classical solutions (e.g.
   "rate\-monotonic" or
   "deadline" scheduling) require multiple
   and time\-varying priorities.This paper shows how to
   implement such solutions simply, and with an acceptable
   level of overhead, on the existing (and future) generation
   of transputer. Other promising scheduling methods are
   discussed. All solutions are expressed in occam with no
   assembler inserts and no security rules violated — the
   intended applications are safety\-critical! Real performance
   figures are reported.Finally, a method of proving (or
   dis\-proving) the security of any particular set of process
   loadings, operating under any particular scheduling
   algorithm, is described.

%T Transputers and routers: Components for concurrent machines
%A David May, Peter Thompson
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X A transputer is a complete microcomputer integrated in a
   single VLSI chip. Each transputer has a number of
   communication links, allowing transputers to be
   interconnected to form concurrent processing systems. The
   transputer instruction set contains Instructions to send and
   receive messages through these links, minimising delays in
   inter\-transputer communication. Transputers can be directly
   interconnected to form specialised networks, or can be
   interconnected via routing chips. Routing chips are VLSI
   building blocks for interconnection networks: they can
   support system\-wide message routing at high throughput and
   low delay.

%T Predictable response times and portable hard real\-time systems with TRANS\-RTXc on the Transputer
%A Eric Verhulst, Hans Thielemans
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X The transputer is a flexible processor, very well suited for
   applications where modularity and distributed operation are
   prime requirements, like in process control. Nevertheless,
   its basic FIFO\-scheduling algorithm, makes its application
   for real\-time processing quite difficult. This problem has
   now been solved by the development of a preemptive
   scheduling algorithm. This algorithm was used to port an
   existing real\-time kernel to the Transputer. In addition,
   by taking account of the specific nature of the Transputer,
   much better performance and flexibility have been obtained.

%T Prototyping transputer applications
%A E. Hart, S. Flavell
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X The design is discussed of a toolset capable of estimating
   the performance of a transputer application at the design
   stage, prior to detailed code being available. The
   Transim/Gecko package from the Polytechnic of Central London
   is discussed in detail as an example of such a toolset. The
   methodology of the package is discussed, its input language,
   output format and the transputer scheduling model to which
   it adheres. An example is described of a real transputer
   application where the tool has been successfully used to
   improve performance.

%T Diffusion limited aggregation: An example of real\-time parallelisation
%A D. R. Morse, A. M. Welch, Peter H. Welch
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X The simulation of the growth of Diffusion\-Limited
   Aggregates (DLA) is representative of a class of
   \[rs]shared\[rs] data\-structure computations that does not
   yield to traditional parallelisation methods (such as
   \[rs]farming\[rs], \[rs]geometric decomposition\[rs] and
   \[rs]data\-flow\[rs]). The difficulty is that the shared
   data\-structure is large and evolving, the required access
   to it from each processor is random and very high, and the
   computation per access is very low. These conditions also
   make these problems most unsuitable for shared\-memory
   parallel computers.This paper presents a parallelisation
   technique that does give linear speed\-up for this problem
   (at least, for up to 32 transputers). The
   cost\-effectiveness of the solution compares favourably with
   those published that use vector\-processing machines.The
   success of the parallelisation depends on real\-time issues
   associated with keeping each worker transputer sufficiently
   up\-to\-date with all its colleagues. Some
   \[rs]quasi\-relativistic\[rs] effects need to be taken into
   account as well!The speed\-ups achieved through this
   parallelisation are used to investigate the effect of
   various parameters (such as stride length and background
   drift) on the kind of DLA growth that is obtained. These
   studies would not be practical without the savings in time
   that have been realised from a parallel implementation of
   the DLA simulation.Finally, we characterise the features of
   those applications for which this parallelisation method is
   relevant.

%T A formal top\-down developement method for occam programs
%A Donal Roantree, Maurice Clint
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X This paper describes a formal development method for
   mathematical applications in occam. Refinement rules form
   the basis of the method. A traces model is defined and used
   to give a formal semantics to occam. The rules are proved
   sound with respect to this semantics.

%T An assessment of the use of occam for dependable real\-time systems
%A A. Burns, A. J. Wellings, Hussein S. M. Zedan
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X As occam based technology matures, and more transputer
   implementations evolve, new application domains will open
   up. This in turn will place fresh requirements on the
   language. In some instances occam, in its current form, will
   be unsuitable and language changes will be inevitable. This
   is, of course, at odds with producing a
   "standard" and "stable"
   language definition.The purpose of this paper is to identify
   the outstanding issues that must be discussed in the short,
   medium or long\-term, if occam (and the transputer) is to be
   used for a wide range of dependable real\-time applications
   in current and future systems. Our approach is to start with
   application requirements, from these to indicate occam
   problem areas and then, if appropriate, offer potential
   solutions. The areas considered are those associated with
   hard real\-time, software reliability, mode changes, dynamic
   change management and fault management.

%T Memory access synchronization in series expansion methods of parallel image reconstruction
%A W. J. Nowinski
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X The paper is concerned with parallel image reconstruction.
   The background of parallel image reconstruction has been
   briefly reviewed. Parallel formulations of series expansion
   methods expressed in occam exploiting projection and ray
   parallelisms have been presented. Two types of mapping of
   the projection space onto the image space influencing a
   simultaneous memory access have been defined. Finally,
   several ways of synchronizing the activities of processes
   when accessing the memory have been discussed.

%T Distributing matrix eigenvalue calculations over transputer arrays
%A Tim Hopkins, Barry Vowden
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X We discuss the parallel numerical solution of the matrix
   eigenvalue problem for real symmetric tridiagonal matrices.
   Instances occur frequently in practice. Two implementations
   of the Sturm sequence algorithm on transputer arrays are
   described. For the first the maximum size of matrices which
   may be accommodated is restricted by the amount of local
   memory available. The second implementation removes this
   constraint but requires an increased execution time.

%T Parallel panel methods
%A Alan G. Chalmers, Steven P. Fiddes, Derek J. Paddon
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X The nature of panel methods makes parallelisation difficult,
   unless effective methods can be found that minimise the
   number of messages required to calculate the interaction of
   all panels in the problem domain. Here, we use a minimal
   path configuration of processors to give an effective
   solution and show its performance superiority over a
   solution obtained from a ring configuration of processors. A
   detailed description of the numerical model and the
   numerical methods that are used for a typical panel method
   problem is given.The importance of balancing the message
   generating parts of an algorithm are established by
   examining the influence matrix set\-up time and the matrix
   solution time. The scalability and maximum performance
   characteristics of the algorithm and system configuration
   are analysed and reported.

%T Shared virtual memory on transputers via the data diffusion machine
%A Sanjay Raina, David H. D. Warren, James Cownie
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X The Data Diffusion Machine (DDM) is a novel multiprocessor
   architecture which is scalable to an arbitrary number of
   processors and at the same time provides a shared virtual
   address space. There is no fixed home location for data \-
   instead data migrates from one processor to another on
   demand. A cache coherence protocol maintains memory
   consistency allowing replication, migration and replacement
   of data.In order to evaluate the DDM we are developing an
   emulator on the Meiko Computing Surface. This paper
   describes the DDM emulator together with additional support
   to turn the emulator into a platform for running real shared
   memory applications. We describe how the bus based snoopy
   protocol of the DDM can be modified to suit point\-to\-point
   interconnection networks.

%T Am interactive graphical debugger for occam programs
%A N. Abdennadher, J. C. Angue
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X Parallel programs are usually described informally, and
   these descriptions are implemented on parallel computer
   systems. When the program does not work correctly, it is
   difficult to detect the semantic error: deadlock,
   starvation, etc ... We propose in this paper an interactive
   graphical debugger of parallel programs written in OCCAM and
   executed and developed on Transputer Network which is
   implemented on IBM PC motherboard. The debugger provides the
   programmer a graphical representation of the dynamic
   behaviour of the OCCAM programs.

%T Virtualising communication in the C\-NET high level programming environment
%A Jean_Marc Adamo, J. Bonneville, C. Bonello
%E Hussein S. M. Zedan
%B OUG\-13: Real\-Time Systems with Transputers
%X A tool for virtualising communication on the SuperNode
   machine is presented. The tool provides four facilities:
   virtual interprocessor communication channels, Transputer
   links multiplexing, link load\-balancing, and consistent
   termination of aborted interprocessor communication.

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.