Refer Proceedings details

%T The advancements of transputers and occam
%A Janet Edwards, Philip Lawson
%E Janet Edwards
%B Proceedings of WoTUG\-14: Occam and the Transputer\-Current Developments
%X In our eagerness to promote Occam and Transputers on the
   World stage, we must not forget that the now common place
   jargon of the Occam User Group may be very new to those
   practitioners that are entering this realm for the first
   time. For the benefit of students, old and young alike, who
   have missed out on the hype that surrounded the transputer
   in the 1980s, what follows should provide a brief insight
   into this complex field. Beyond introducing the current
   transputer hardware and Occam software, a glimpse of things
   to come is provided by a pre\-release view of the IMS T9000
   transputer and the next generation of the Occam language.
   This overview concludes with a short pr\[`e]cis of each of
   the papers that contributed to this, the 14th World Occam
   and Transputer User Group technical meeting.

%T Aspects of database machine design using the H1, C104 and Occam91
%A Jon Kerridge, Richard J. Oates
%E Janet Edwards
%B Proceedings of WoTUG\-14: Occam and the Transputer\-Current Developments
%X In this paper we explore the design of a database machine
   that is already being implemented using T series transputers
   to determine the benefits of using the T9000 series
   transputer togeher eith its associated routing chip, the
   C104, and occam91. The language occam91, a superset of
   occam2, contains language features that directly support the
   exploitation of hardware features that have been
   incorporated into the T9000 transputer. We briefly introduce
   the underlying design of the database machine. The way in
   which the C104 routing chips can be used is then described
   in conjunction with a planar approach to the interconnection
   of nodes in the machine. Finally, we give fragments of
   occam91 that demonstrated how its features can be used in
   two different parts of the database machine. The first
   application considers the problems of allocating resources
   to a user query and the second looks at how recovery
   features can be specified.

%T Performance of post\-game analysis on transputers
%A Johan P. E. Sunter, André W. P. Bakkers
%E Janet Edwards
%B Proceedings of WoTUG\-14: Occam and the Transputer\-Current Developments
%X In this paper the performance of a Post\-Game Analysis
   system is studied. For this purpose several simple cases
   have been designed. These cases consist of a number of
   processes which have to be distributed over a network of
   transputers. The final distributions for these cases are
   compared to the optimal ones, which can be easily derived
   for these simple cases. Performance measures considered
   include the number of iterations required to reach the final
   distribution, and the overhead caused by monitoring the
   program behaviour.

%T Strategies for workload distribution
%A Iain Phillips, Peter C. Capon
%E Janet Edwards
%B Proceedings of WoTUG\-14: Occam and the Transputer\-Current Developments
%X If large distributed systems, such as transputer networks,
   are to be exploited fully, effective workload distribution
   strategies are required. For such systems to be successfully
   scalable, decision making in such strategies will need to be
   both dynamic and distributed. The choice of strategy depends
   on many factors, including the size and topology of the
   network together with the nature of the application. The
   success of any particular strategy is measured by comparing
   the time taken to execute the application on many processors
   with the time taken on few processors.

%T A process migration harness for dynamic load balancing
%A S. A. Baker, K. R. Milner
%E Janet Edwards
%B Proceedings of WoTUG\-14: Occam and the Transputer\-Current Developments
%X In order to attain high efficiency and maximum throughput
   from MIMD architectures, it is necessary to have a balanced
   load with all processors being utilised. If the optimum
   program configuration is data\-dependent, the process
   distribution will have to be performed at run time, i.e.
   dynamically. A message\-passing harness has been developed
   with a process migration capability for dynamic
   loca\-balancing on transputer\-based machines. This paper
   describes the process migration harness and the way in which
   it is integrated with the user\[rs]s application, gives a
   brief survey of the types of dynamic load balancing
   algorithm currently under investigation and concludes with
   some preliminary performance results.

%T A simple parallel algebraic multigrid
%A Guy Robinson
%E Janet Edwards
%B Proceedings of WoTUG\-14: Occam and the Transputer\-Current Developments
%X This paper describes an "algebraic
   multigrid" scheme which can be applied to a wide
   range of matrix based problems. Multigrid schemed offer
   significant gains in both numerical performance and runtimes
   compared to conventional solvers. The equations for the
   hierachy of grids are generated solely from the equation for
   the fine mesh without generating the intermediate grids or
   relying on geometrical features of the fine mesh. The
   development of the code for distributed memory Multiple
   Instruction Multiple Data architectures is detailed. The
   numerical and run time performance is described for simple
   linear equation sets and as a linear solver for coupled
   equations as part a 3D computational fluid dynamics code.

%T Fast fourier transform on transputers
%A Aman Khan, Nelson Stephens
%E Janet Edwards
%B Proceedings of WoTUG\-14: Occam and the Transputer\-Current Developments
%X The fast evaluation of the Discrete Fourier Transform on a
   system with a large number of transputers is considered. The
   implementation uses a configuration of the transputers which
   leads to a very high performance. The design and
   implementation incorporate several new features. Tables of
   this performance, in terms of actual times and speed\-up as
   the number of data points and transputers vary, are
   presented. Implementation aspects of the radix\-2 and higher
   radix DFT in one and two dimensions are considered. The
   timings are compared with those for other computers and
   found to be favourable.

%T A new adaptive algorithm for the solution of systems of linear equations
%A Rudnei Dias da Cunha, Tim Hopkins
%E Janet Edwards
%B Proceedings of WoTUG\-14: Occam and the Transputer\-Current Developments
%X We present a comparison between serial and parallel
   implementations of some iterative methods to solve systems
   of linear equations. The basic vector arithmetic operations
   used in the implementations are discussed with respect to
   its parallelization. The iterative methods considered are
   the Adaptive SOR (A\-SOR), the Steepest\-descent (G), an
   adaptive version of the steepest\-descent method (A\-G), the
   Richardson\[rs]s Optimum\-Extrapolated (RF\-OE), and the
   Conjugate Gradient (CG).

%T Simulation of optical systolic and neural network using occam
%A D. J. Evans, K. G. Margaritis
%E Janet Edwards
%B Proceedings of WoTUG\-14: Occam and the Transputer\-Current Developments
%X This paper describes the simulation of optical processors
   for performing optical systolic and neural net algorithms.
   Occam is used as a simulation langugage and each component
   of the optical processor is defined as an occam process.

%T Developement methods and occam
%A David M. Gee, Barry P. Worrall, W. D. Henderson
%E Janet Edwards
%B Proceedings of WoTUG\-14: Occam and the Transputer\-Current Developments
%X Existing structured methods for real\-time systems are
   critically reviewed with respect to their suitability for
   direct implementation in occam without transformation. All
   are found to have weaknesses in some respects; consequently
   new notations are proposed. Use of these within an
   appropriate tool framework could assist in the automatic
   generation of occam code.

%T A general\-purpose parallel programming environment
%A Mark Debbage, Mark Hill, Denis A. Nicole
%E Janet Edwards
%B Proceedings of WoTUG\-14: Occam and the Transputer\-Current Developments
%X A parallel programming environment has been developed which
   is superior to many available systems on current generation
   transputers. The core of the package is a packet router
   which delivers asynchronous datagrams around arbitrary
   networks. The router is guaranteed not to deadlock provided
   that higher levels do not violate the eager\-readership
   edict. This eager0readership can be guaranteed by the use of
   communication protocols which ensure that packets are never
   sent to a destination which has insufficient buffer space
   available. The router has been implemented in C and is
   applicable to a wide number of loosely coupled
   multiprocessing architectures. The current implementation
   has been optimised for transputer networks, on which it
   achieves impressive communications performance. The
   implementation of a virtual channel protocol within occam
   semantics on such a router is discussed. This forms the
   basis of version 2.0 of the popular Virtual Channel Router
   (VCR) package. The user interface to these channels is the
   conventional occam syntax for communications but with the
   configuration restriction of four channel\-pairs per
   processor eliminated. The virtual channels provided by this
   package can be exploited from other languages through the
   appropriate Inmos Toolset.

%T Repeatable execution of occam programs
%A Umberto Villano
%E Janet Edwards
%B Proceedings of WoTUG\-14: Occam and the Transputer\-Current Developments
%X Parallel programs are intrinsically non\-deterministic, and
   therefore the techniques of cyclical debugging that are
   commonly used for sequential programs are not suitable for
   parallel ones. This paper proposes a method for guaranteeing
   the repeatability of occam program behaviour. Saving
   information on the ALT guards selected at run\-time allows
   program replay. i.e. makes it possible to re\-execute the
   program following the same instruction path whatever the
   speed at which each component process is executed. This
   enables the software developer to use tools such as
   debuggers and intrusive monitors to help identify program
   errors. After a discussion on the possible implementations
   of the proposed technique, a prototype tools that allows the
   replat of occam programs within TDS is briefly described.

%T A Software Developement Environment for Parallel Image Processing: Implementation techniques and issues
%A D. Crookes, Philip J. Morrow, I. McClatchey, T. Rafferty
%E Janet Edwards
%B Proceedings of WoTUG\-14: Occam and the Transputer\-Current Developments
%X A program development environment has been designed for
   building transputer based image processing systems. The
   system has two main components: a library of (parallelised)
   image processing operations, and a graphical user interface.
   After introducing the user interface, the paper concentrates
   on the implementation techniques and issues involved in
   constructing the environment. The main implementation areas
   considered are: a flexible and highly parameterised library
   of image processing routines; the provision of a
   communications shell which utilises the underlying
   parallelism without the user having to be concerned about
   it; and the extensibility of the environment by adding new
   components to the library.

%T Integration of Classification and Evaluation Procedures in the Implementation of Parallel Image Analysis Algorithms
%A P. Brittan, M. C. Fairhurst
%E Janet Edwards
%B Proceedings of WoTUG\-14: Occam and the Transputer\-Current Developments
%X The requirements of adaptability and high performance often
   dictate a parallel processing approach for cost\-effective
   algorithm implementation in many real\-time applications of
   image classification. The aim of this paper is twofold.
   First it seeks to illustrate that by giving careful
   consideration to the conceptual architecture of the image
   classifier and its implementation base levels of performance
   can be achieved. Second, it will discuss the principal
   features of implementing multi\-layer classifier algorithms,
   performance evaluation processes, and high\-speed data
   handling required for evaluation, over an array of
   transputers.

%T On the serialisation of parallel programs
%A Peter H. Welch, G. R. Ribeiro Justo
%E Janet Edwards
%B Proceedings of WoTUG\-14: Occam and the Transputer\-Current Developments
%X This paper argues that one of the key techniques for making
   the most efective use of multi\-processor architectures is
   the serialisation of parallel code! Parallel algorithms are
   presented as having strong engineering merits that will form
   the natural basis for systems design in the future.
   Parallelisation of serial code is regarded as having only
   short\-term value (for "dusty\-decks",
   whose correctness cannot be verified) as well as being
   mathematically intractable. Serialisation, on the other
   hand, is much easier to automate and can be profitably
   employed today. Several serialising transforms for occam
   processes are presented and applied to various simulation
   and image compression tasks.

%T Application of occam to biological sequence comparisons
%A Shane S. Sturrock, Ian Salmon
%E Janet Edwards
%B Proceedings of WoTUG\-14: Occam and the Transputer\-Current Developments
%X One of the major uses of computers by molecular biologists
   is the alignment of protein or DNA sequences. Since the
   structure and function of proteins and DNA cannot be
   predicted directly from sequence data alone, the most useful
   procedure is to compare unknown sequences against a database
   of known sequences. Those with a high degree of homology are
   likely to have similar properties. At present, the databases
   are growing exponentially with doubling in around 20 months.
   Consequently, comparisons are taking proportionately longer
   to complete. We have applied various sequential comparative
   algorithms within a farming harness constructed in occam
   from a pipeline of transputers. The design of the farming
   harness for optimum link communication is discussed. The
   advantage our method offers is scalability; an important
   consideration as the databases multiply in content. The
   ability to tailor the algorithm to work on various size
   networks of transputers also allows the user to weigh time
   considerations against the total cost of the system. Our
   present implementation can perform around 600 comparisons
   per second between a query sequence of 50 residues and a
   database using 64 worker processors.

%T Implementing an Active Chart Parser on a Transputer Network
%A Janet Edwards, John H. Connolly
%E Janet Edwards
%B Proceedings of WoTUG\-14: Occam and the Transputer\-Current Developments
%X Active chart parsing is a well\-known technique for the
   syntactic analysis of natural language. This paper is
   concerned with the parallel implementation of the relevant
   algorithm in Occam\-2 on a Transputer network. Different
   parallelisation strategies are compared, and it is concluded
   that better results are obtained by splitting the grammar
   associated with the parser than by decomposing the algorithm
   itself.

%T A Scalable Communication Network for a Parallel Database Machine
%A David Walter, Jon Kerridge
%E Janet Edwards
%B Proceedings of WoTUG\-14: Occam and the Transputer\-Current Developments
%X The IDIOMS parallel database machine has at its kernel a
   scalable communications structure. The scalability is
   fundamental to the database machine because it is intended
   that the parts which are joined together by the
   communications network can be added to as demands on the
   database machine change. The network must be scalable both
   in terms og the number of user processes which can be
   supported, and, in order to meet the performance
   requirements of large systems, it should be possible to
   scale up the bandwidth of the network by adding further
   communication processors. The structure of a node in the
   network is described in terms of itsccam behavior which
   shows how node control is achieved by a control process that
   manipulates a set of flags by means of channel
   communications. The network is shown to be free from the
   possibility of deadlock. Finally, the performance and
   operational characteristics of the network are discussed and
   it is shown that the network is ideally suited for parallel
   database operation.

%T Parallel Scan Line algorithm for Hidden Surface Elimination
%A Julian C. Highfield
%E Janet Edwards
%B Proceedings of WoTUG\-14: Occam and the Transputer\-Current Developments
%X With the general availability of general purpose parallel
   computers, there is a need to reconsider scan conversion
   algorithms with respect to their parallel implementation.
   This paper considers MIMD parallel implementation of two
   versions of the scan conversion algorithm, one the common
   edge table optimisation, and one not. Their suitability for
   parallel implementation is investigated and their relative
   performance in multi\-processor systems is measured using
   polygonal scene descriptions of between 150 and 2600
   polygons. Dependence upon the size of scene description is
   measured and results are extrapolated to larger scene
   descriptions. It is shown that scan conversion algorithms
   may be efficiently parallelised. It is also shown that the
   edge table optimisation, while appropriate to the single
   processor case, becomes useless at around twenty processors,
   and would actually be a disadvantage in the limiting case of
   one processor per scan line.

%T Processor Independant and Extendable Routing System using a Cyclic Routing Algorithm
%A P. A. Shallow
%E Janet Edwards
%B Proceedings of WoTUG\-14: Occam and the Transputer\-Current Developments
%X PIERS is a deadlock free virtual routing system developed
   for distributed concurrent applications. It deliberately
   exploits the advantages gained by allowing cycles to occur
   in the channel dependency graph and incorporates the cycles
   into the routing algorithm. It directly interfaces with the
   user\[rs]s application and uses the existing OCCAM channel
   primitives. The paper describes how this cyclic
   routingalgorithm operates and how deadlock is averted. It
   describes how the routing system is implemented, presents
   the performance figures obtained and summarises the network
   configuration utility written to integrate the communication
   harness with the user\[rs]s application.

%T Deterministic Message Routing for Safety\-Critical Applications
%A Peter R. Croll
%E Janet Edwards
%B Proceedings of WoTUG\-14: Occam and the Transputer\-Current Developments
%X This paper considers a technique of message passing which
   can be applied in the development of parallel programs for
   safety\-critical applications. The routing algorithm used to
   ensure that messages will always be able to meet hard
   real\-time constraints and yet cope with some degree of
   hardware failure. This paper will firstly introduce the
   routing algorithm, it will indicate what properties can be
   proved about deterministic message passing and describe how
   the algorithms cope with hardware failure. From this, the
   details of possible solutions that the new T9000 family can
   offer will be presented.

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.