Browse Prior Art Database

Efficient And Fair Multiplexing On Transputers

IP.com Disclosure Number: IPCOM000102164D
Original Publication Date: 1990-Oct-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 4 page(s) / 129K

Publishing Venue

IBM

Related People

Kaiserswerth, M: AUTHOR [+2]

Abstract

This article suggests an efficient procedure for multiplexing the outputs of multiple transputer processes to a single channel.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Efficient And Fair Multiplexing On Transputers

       This article suggests an efficient procedure for
multiplexing the outputs of multiple transputer processes to a single
channel.

      Problem: Multiplexing the outputs of multiple transputer
processes to a single channel, e.g., physical transputer link, may be
an expensive (and even unfair) operation when multiplexing is
implemented

                            (Image Omitted)

 using a "replicated
ALT" construct which is provided by several high-level programming
languages used on transputers.

      The compilers translate the ALT construct to a search through
the list of all input guards in the construct.  The difficulty is
that the programmer cannot use channels as queues.  Languages for
programming transputers do not allow two or more processes to output
to the same channel.  On the transputer the execution fails whenever
two processes become simultaneously blocked, having executed output
to the same channel.  This is caused by the second output on the
channel corrupting the data structure that represents the channel.

      In the sequel, another implementation of multiplexing is
described in which the execution time is independent of the number of
data sources and the service is fair. Solution:

      The priority scheduling implemented by the transputer allows a
fast solution to the above problem.  In the proposed procedure all
the producers signal their readiness by output on the same channel,
but priority scheduling is used to ensure that two producers are
never blocked on the channel at the same time.

      A new process, called the "queue server", is inserted between
the producers and the consumer (see Fig. 1) to implement the desired
queue of suspended producers.

      The queue server maintains a circular array of process indices
(or, equivalently, channel indices); the array records the identities
of the producers that are suspended waiting for an output operation
to the consumer.  The identity of the next available producer is
passed to the consumer whenever the consumer becomes ready.  The
consumer then uses a simple input operation (as opposed to the
replicated ALT construct in the previous solution) to receive the
data item from the producer.

      The queue server executes at a high priority and is always
either executing or ready to receive input from the channel
"to.queue".  It follows that two producers (which execute at a low
priority) cannot be...