CA1280497C - Switching element for self-routing multistage packet- switching interconnection networks - Google Patents

Abstract

Abstract A switching element for self-routing, multistage, packet-switching, interconnection networks which comprise: an input unit, composed of as many sections ( IMA, IMB) as there are elements inputs, each section comprising a FIFO memory (FIFA, FIFB) for packet buffering; a switch (SW) associated with a control unit (SCU) which, for each packet to be forwarded, sets up a requested connection for that packet between one input and one or more outputs of the element (ECP), based on a routing tag associated with each packet and comprising a first and a second portion relative to normal routing and to broadcasting in the different stages of the network (RC), and solves possible routing conflicts between packets simultaneously arriving at different inputs; and an output unit, composed of as many sections (RUO, RUl) as there are element outputs and performing the functions necessary for correct packet forwarding toward a destination.
The control unit (SCU) of the switch (SW) is arranged to handle broadcasting of a packet independently of all other elements (ECP) in the same stage, to allow broadcasting to a number of destinations, not limited to a power of 2, (for an element with two inputs and two outputs) and cooperates with the memory (FIF) storing the packet to be broadcast in such a way that broadcast-ing does not give rise to internal blocking in the network (RC).
The control unit (SCU) moreover solves routing conflicts to set an upper bound to packet residence time within the network.

Description

```` 12~ 7 This invention relates to packet-switching interconnec-tion networks and, more particularly, to a packet-switching element for a self-routing, multistage, interconnection network.

It is known that a wide group of multistage, packet-switching, interconnection networks each include networks comprising a plurality of identical elements connected so that any network output may be reached from any input. Examples of such networks are the so called omega, delta, Benes, and the like, networks. In self-routing networks, the elements:

(a) analyze the tab identifying the destination of a packet and consequently route the packet toward the appropriate output;
(b) solve possible routing conflicts; and (c) buffer packets which cannot be immediately forwarded because of routing conflicts or unavailability of a subsequent networ]c stage or of a subsequent destination device.

Function (c) is generally performed to set an upper bound to the residence time of a packet in the network, which increases network efficiency.

In some applications, for instance within parallel pro-cessing structures which implement distributed algorithms or in telecommunications networks, other functions are desirable, such as the ability to broadcast a message to a plurality of destina-tions. Therefore, the ability to connect one input element with a plurality of outputs is necessary in these applications. A
network consisting of elements having this ability is disclosed in an article by H. J. Siegel and R. J. McMillen entitled "The multistage cube: a versatile interconnection network", IEEE
Computer, December 1981, page 65 - 76. The network disclosed in this article consist of elements having 2 inputs and 2 outputs, ~28~a9~
.

each comprising a switch with a control unit that, based on the information contained in the routing tag, sets up the appropriate connections between one input and one or many outputs. In the case of a plurality of outputs the connection may be set up either with two outputs whose addresses are in a given relation-ship, or with a greater number of outputs, provided that such a number is a power of 2. This implies that, in each network stage, all elements traversed by a message must have the same configuration. This limits the network efficiency as a number of destination devices might not receive information or might receive information which is not of interest and is then to be eliminated. Moreover the article does not indicate how internal blocking of the network can be avoided when information is broad-cast or how an upper bound might be set to the residence time in the network.

These problems are solved by a switching element according to this invention. This switching element allows broadcasting to be effected without permanent internal blocking of the network occurring and allows any number of destinations (even a numher which is not a power of the element output number) to be reached. The switching element also includes means for solving routing conflicts in such a way that an upper limit is set to the packet residence time in the network.
According to the invention~ there is provided a packet-switching element for self-routing, multistage, interconnection networks allowing broadcasting of packets which are forwarded through the network, the packet switching element having inputs and outputs and comprising:

an input unit, having as many sections as there are inputs of the packet-switching element, each section comprising a FIFO memory for buffering of each packet prior to forwarding each packet toward the output;

2~30~9~7 a switch associated with a control unit which, for each packet to be Eorwarded, sets up a requested connection for that packet between one input and one or more outputs of the packet switching element based on information contained in a routing tag associated with each packet and comprising a first portion for normal routing and a second portion for broadcasting in each different network stage, and which solves possible routing con-flicts between packets simultaneously arriving at different inputs an output unit, comprising as many sections as there are outputs of the packet-switching element and performing the functions necessary for correctly forwarding each packet toward a destination;
wherein the control unit of the switch comprises control logic means which, upon detection of a broadcasting request, evaluate the possibility of accepting the request by comparing a first parameter, related to the number of destina-tions to which a packet is to be broadcast, and a second para-meter, related to the position o the stage to which the packet-switching element forms part of amongst the stages where broad-castin~ is requested, and indicating the maximum number of net-work outputs which potentially may be seized for broadcasting of a particular message, which accept the broadcasting request if the first parameter is greater than or equal to the second one, which generate, if the request is accepted, a broadcast signal for communicating this condition to the FIFO memory storing the packet to be broadcast, and which generate at least one modified routing tag which is sent through one of the outputs of a packet-switching element affected by the broadcasting, the broadcasting request being processed in a packet-switching element within a stage, independently of the processing of other broadcasting requests in other elements in the same stage; and wherein the FIFO memory of each input unit section comprises broadcasting means, for carrying out the broadcasting ~280497 of a packet, in the presence of the broadcast signal generated by the control unit if a broadcasting request is accepted, through a plurality of consecutive readings of the same packet.

Broadcasting of a packet by a plurality of consecutive readings of the packet is the manner by which internal blocking of the network is avoided.

An embodiment of the invention is described, by way of example only, with reference to the following drawings in which:

Fig. 1 is schematic representation of a parallel processing structure employing an interconnection network consisting of packet-switching elements;
Fig. 2 is a block diagram of a packet-switching element;

Fig. 3 is a diagram illustrating a message broadcasting algorithm;

Fig. 4 is a diagram of the operation of a logic network of an input unit;

Fig. 5 is a detailed scheme of a logic network of an output unit of an element;

Fig. 6 is an operation diagram of a control unit of the logic network shown in Fig. 5;
Fig. 7 is a constructional scheme of one FIFO memory;

Figs. 8 and 9 are operation diagrams of two logic networks of the FIFO memory shown in Fig. 7;
Fig. 10 is a block diagram of a switch control unit;

()497 Fig. 11 is a block diagram of a routing tag processing circuit in the switch control unit; and Figs. 12 to 15 are detailed schemes of some of the circuits shown in Fig. ll.

Fig. l illustrates a parallel processing structure comprising a plurality of processing units El, E2...En which mutually exchange variable length messages through a self-routing, multistage, packet-switching, network RC. The packet-switching network RC consists of a plurality of identical switchelements ECP which are the subject matter of this invention. By way of example only, in the following description these elements ECP are described as each having two inputs and two outputs.
~ach element ECP routes each packet received by it towards an element in a subsequent stage or toward a network output (or toward two elements or outputs, in case of broadcasting), to solve the routing conflicts and to temporarily store packets that cannot be forwarded immediately. Moreover, elements ECP allow connection of one input with either one output or a plurality of outputs (broadcasting) of the network RC. In broadcasting, each element ECP may operate independently of all other elementS in the same stage, so that the number of users reached by a message need not be a power of 2.

The messages forwarded through the network consist of a number of packets which, in the most general case, each comprise:
a tag consisting of two bit groups, one of which, a normal trans-mission tag, contains the actual routing information and the other, a broadcast transmission tag, contains the broadcasting inormation; a word indicating the packet length; a variable number of data words; and, a check word (cyclic redundancy code) for checking the proper network operation. The normal transmis-sion tag bit may have a logic value of 0 or l and indicates the element output channel on which the message is to be forwarded, while, a broadcast transmission tag bit having a value of 1 indicates a broadcasting request. The two bit groups are present , `` ~Z19~97 simultaneously. Bits having equal positions in the two groups relate to the same stage.

~ eferring to Fig. 2, each switching element ECP
comprises: two input buses IDA, IDB and two output buses UDO, UDl, with each bus having a sufficient number of wires to allow parallel transmission of all the bits in a packet word; a switch SW with its control unit SCU; an input unit consisting of two identical sections (one for each of the two input buses IDA, IDB), and an output unit also consisting of two identical sections RU0, RUl, associated with the output buses UDO, UDl respectively; and two internal data buses BDA, BDB, connecting the two input sections with the switch SW; and two internal data buses and DBO, DBl connecting the switch SW with the output sections RUO, RUl. In the following description, final letters A, B of the reference labels denote devices and signals relating to one or the other input, and final digits 0, l denote elements associated with one or the other output. Where no risk of confusion exists, the final character of each reference symbols is omitted.
Each input section comprises a logic network (IMA and IMB, respectively) and a buffer (FIFA and FIFB, respectively).
Each logic network IM controls writing of the data arriving at the element ECP through the buses IDA, IDB, into its buffer FIF, until the buffer is filled, and manages the handshake protocol with any upstream device (eg. an element ECP of a preceding network stage).

The buffers FIF are first-in, first-out (FIFO) memories temporarily storing packets which cannot be immediately forwarded to the subsequent stage. Moreover, under the control of the control logic unit SCU, the buffers allow broadcasting of a message, through two consecutive message readings. In this way, broadcasting may be performed without permanent network blocking when variable length messages are handled in the network.

LZ3~ 97 The structure of the parallel packet switch SW is well known in the art and does not require a detailed description;
however an example can be found in "Introduction to VLSI
systems", by C. Mead, L. Coway, Addison Wesley Publishing Company, page l58.

The control unit SCU of the switch SW functions to:
analyze routing requests contained in a normal routing tag; set up accordingly the connection between the input buses BDA, BDB
and the output buses DBl, DB2 of the switch SW (one input with one of the outputs, each input with a respective output, or one input with both outputs in two subsequent stages); solve routing conflicts to establish an upper bound to the residence time of a packet in the network; and manage the message broadcasting algorithm in a manner independent of all other elements in the stage.

When a conflict occurs, the identity of the message being delayed is stored and, at a subsequent conflict concerning a previously delayed message, the output channel is made avail-able for it. Thus any message can lose only one conflict (in theexemplary embodiment of a 2 x 2 element), and this limits not only the overall transit delay through the network but also the delay variance for the different packets.

The broadcasting algorithm is based on the principle of allowiny a message to be broadcast to any number of destinations (even other than a power of 2), the positions of which depend on the positions and the number of the stages where broadcasting is to occur. In a given network stage, the broadcasting request is accepted if a first parameter, related to the number of destina-tions to which the message is to be broadcast, is greater than or equal to a second parameter, related to the position, in the net-work of the stage the element is part of (and more particularly to the position of the stage among those where broadcasting is to occur). The second parameter indicates the maximum number of .2~ 97 stage outputs which may potentially be seized for message broad-casting.

For example, consider an operation in a network stage j. Let BRD = b(n)...b(j)...(bl) be the broadcast transmission tag; BUM, BU(M-l)...BUl be the m bits at logic level l in the broadcast transmision tag BRD; TAB be the normal transmission tag; TUM, TU(M l)...TUl be the bits that, in ~AG, correspond with bits BUM...BUl of BRD. Clearly, the bits TU (i) of TAG relating to the stages where broadcasting is to occur are not significant Eor routing, as the message is to be routed over both outputs.
After forcing bit TUM high (logic l), if it is not yet high, the bits TU(i) are utilized to form a binary number Tc= l, TU(M-l) ...TUl which forms ~he first parameter. The original value of bit TUM is used to route the message after evaluation of the possibility of broadcasting, as is disclosed hereinafter. If stage j is the k-th stage where broadcasting is requested (l ~ k ~ m), the second parameter is 2k. Therefore, broadcasting is effected only if Tc - 2k >~ 0. The value of the difference Tc - 2k is used to build a modified normal transmission tag which is sent over one of the two output channels (namely, the one identified by the complement of bit TUM) while the original normal transmission tag is sent over the other channel. If the difference value is negative, a normal transmission is effected over the output channel identiEied by the complement of the bit TUM leaving the normal transmission tag unchanged. As a result of the above algorithm, considering the set of 2m processing units E (fig. l), the addresses of which coincide in the n - m bits of BRD which are 0, it is possible to broadcast a message to the first or the last Tc + l processing units in that set (the units with the least or the greatest addresses, respectively) depending on the value of the bit TUM. The algorithm is imple-mented, for a given message, independently of any other message dealt with in the same network stage.

An exemplary application of the above algorithm is shown in Fig. 3 for a 4-stage network, for a message in which the ~28(~97 tag portions TAG and BRD (shown at T, B respectively) are 1000 and 1101, respectively. Hence the bits in Tc are 100 and broad-casting concerns five outputs. It can be appreciated that the tag portions TAG at the outputs from the elements in which broad-casting is carried out and the addresses of the five network out-puts meet the conditions above.

Referring to Fig. 2, each output unit (RUO, RUl) per-forms all the functions relating to forwarding a packet to the destination device(s). Besides setting up the connection with the device(s) and hence managing the handshake protocol, each output unit (RUO, RUl) also identifies the length of the packet to be transmitted and generates or checks, or both, the cyclic redundancy code. As far as the redundancy code is concerned, in a preferred embodiment of the invention, the code is generated in the first stage of the network RC (Fig. 1), is checked in the intermediate stages and is checked and eliminated in the last stage. To provide for this procedure, the output unit receives signals denoting whether it belongs to the first network stage, or to an intermediate stage or to the last stage. The redundancy code may already be present in the packets input to the network.
In this case, all the stages act as intermediate stages and carry out only the check. In applications where the redundancy code need not be used, this information is made available to the out-put unit which is then freed Erom a number of operations.
Each section of the output unit is described schematic-ally and comprises:

a logic network OM (OMO, OMl) which controls the output unit and communicates with the other devices of the element ECP;
an output register RL of the element ECP;

a counter CN, which loads the word which codes the packet length and which counts, under the control of the logic network OM, the number of transmitted words; and ~28(1~L9~
a circuit CRC for generating or checking, or both, the cyclic redundancy code. This circuit essentially comprises a register and a combinatory network of EX-OR gates which implements the particular polynomial chosen for the code. If data are trans-mitted in parallel (e.g. with an 8-bit parallelism), then, advan-tageously, the code is computed in parallel. A possible embodimentis disclosed in "Error Detecting Logic For Digital Computers", b~
F. F. Sellers, M. Y. Sao, L~W. Bearnson, McGraw-Hill Book Company, page 258.

The structure of each of the buffers FIF, the control units SCU, the output sections RU, and the locig networks OM is disclosed in greater detail with reference to Figs. 5 to 15.
Also, the meaning of the various signals shown in Fig. 2 will become apparent from the description of these blocks which also describes the timing signals for the different blocks. Only a state diagram is given for the logic network IM as the circuit design of a network operating according to the state diagram would be clear to those skilled in the art.
The operation of the logic network IM of the input unit is now disclosed with reference to Fig. 4. The network IM
receives the Eollowing signals:

25 (a) REQIN, which is emitted by the logic network OM (Fig. 2) of an output unit section RU of an upstream stage or by a processing unit E (Fig. 1) to indicate the existence of a data word to be sent to the switching element the network IM is part oE; and (b) FPI, which is emitted by the memory FIF (Fig. 2) to indicate that the memory is full.

The network IM emits the following signals:
(a) ACKIN, which is sent to the device which has issued the signal REQI~ to confirm availability for data reception;
and ~L280~97 (b) LOAD, which is sent to the memory FIF to control writing of data into the memory.

In this description, it is assumed that the signals are active when they are at a logic value of 1. In correspondence with the various states or state transition, the logic values of the different input signals are given in the same order as the signals are listed above. AS usual, the symbol "X" denotes the "don't care" condition. The same representation modalities are followed for the other state diagrams.

The logic network IM is initially in an idle state Al where it remains, whatever the value of REQIN, if the memory is full (X, 1) or if no request arrives (O, X). If the memory is not full, IM leaves the idle state Al if forwarding of a data word is requested, and enters an active state Bl generating signals LOAD and ACKIN. IM goes back to the idle state Al when data loading is over and REQIN iS reset to 0. The signal ACKIN
remains active as long as IM is in the active state Bl, as it is also used to "freeze" the data present at the input of memory FIF
for the time necessary to write into the memory.

Fig. 5 shows in greater detail the structure of a section RU of the output unit. Blocks CRC, CN and RL are the same as shown in Fig. 2. The remaining circuits form block OM of Fig. 2 and include:

(i) a sequential control logic network OMC;

(ii) a first group of flip-flops and gates (FF2, FF3, FF4 AND1) for synchronizing the output unit with the switch control unit and managing hand-shakes with the switch control unit for the transfer packet words. The specific functions of the elements of this group will become apparent hereinafter;

,..... ~: .

~ ~.2~()497 (iii) a second group of flip-flops and gates (FF5, FF6, FF8, AND2, ~ND3, NORl, MXl) associated with counter CN and block CRC to take into account the possibility of, dif-ferent lengths of packet words, the presence or absence of the check word and the position of the stage, within the network, which the element ECP is part of, in order to COUtlt the number of words to be transmitted and to forward to the control unit SCU (Fig. 2) any possible error signals. The functions of the elements of this group will become apparent from the description of the operation of the control logic network; and, (iv) a third group of flip-flops and gates (FF7, ORl) for data output synchronization.

A further multiplexer MX2 is provided to send through the output bus UD either the data present on bus DB or the check word generated by CRC. No reference symbol has been allotted to the various inverters necessary to take into account the logic level required by certain flip-flop inputs. To simplify the drawing, the general reset signal and the flip-flop inputs/out-puts which are not of interest for the operation are not shown.
Where a ~uantitative time indication is necessary, reference is made to a clock signal having a period of 50 ns.

Logic network OMC is described with reference to the state diagram of Fig. 6. The combinatory portion of the logic network OMC, due to the complexity of the operations carried out, is made by a programmable logic array.

Management of the dialogue between the output section RU and switch control unit SC, is allotted to circuits (namely the first group of flip-flop and logic gates) external to OMC and SCU in order to avoid excessive burdening of the structure of these units. The dialogue protocol is based upon a command (START), which starts message transmission, generated by SCU, and an end-of-message signal (FCSCU) generated by OMC. The flip-flop ` ~280~97 FF2 causes the signal FCSCU to remain high for only one period of the clock signal CK. The signal FCSCU is also converted into a signal ABSTART by flip-flop FF3. The signal ABSTART, through flip-flop FF4 and gate ANDl, enables transfer of signal START to OMC thus making the signal START impulsive.

The logic network OMC receives the following signals:

(a) signals FSTG, LSTG, denoting that the element ECP forms part of the first or the last network stage, respect-ively. These signals are also combined by gate NORl to indicate that the stage is an intermediate stage (INTSTG) while their logic product, effected by gate AND2, is a signal (NO CRC) indicating that the messages in the particular application do not contain the redun-dancy word;

(b) signal START, already mentioned;

(c) signal FC, which is an end-of-count signal generated by the counter CN and utiliæed by OMC to detect that all the words in a message have been transmitted. Signal FC iS fed to OMC through a multiplexer MXl controlled by the signal INTSTG. Signal FC iS the carry-out sig-nal of the counter CN for the elements in the first or the last network stage or Eor applications which do not use the check word, while in the case of an intermedi-ate network stgae, signal FC is the carry-out of count-er CN delayed by one cycle period in flip-flop FF6. In effect, when FC is delayed, the message present on bus DB comprises one more word (the cyclic redundancy code) which is missing in the other cases;

(d) signal FNV, which is fed through switch SW by buffer FIF (Fig. 2) of the input unit section connected with that section of the output unit, and which indicateS
that the buffer itself is not empty .i: ., :~ . , . .

9~

(e) signal ACKOUT, acknowledging data receipt by the down-stream device (this signal corresponds to signal ACKIN
issued by IM, Fig. 2); and, (f) signal SECBYTE, indicating the presence of a second byte in the packet length word.

The logic network OMC emits the following signals:

(a) signal LOADCT, which is sent to the counter CN to cause loading of the message length word and is issued when, depending upon internal timing signals of ~U, logic network OMC recognizes the presence of that word on bus DB. The signal LOADCT also clears flip-flop FF6 and presets flip-flop FF3, and is converted into signal SECBYTE through a T-type flip-flop FF8.

(b) signal DECR, which is sent to the counter CN to decre-ment by l its contents after transmission of each word of the message. This signal also constitutes the clock signal for FF6;

(c) signal FCSCU, already mentioned, which is generated by OMC after reception of signal FC;

25 (d) signal UNLOAD, which, after reception of a word, is sent through the switch SW to the buffer FIF with which RU is connected to start reading of the subsequent word;

30 (e) signal REQOUT, informing a downstream device that there is a message to be transmitted (the signal corresponds to signal REQUIN entering IM, Fig. 2);

(f) signal CLCRC, sent to CRC to reset it contents. This signal is also the clock signal for flip-flop FF5 - 14 - ~.

~28~7 ~.

(reset by NO CRC) emitting signal ERRCRC indicating an unsuccessful check by CRC; and, (g) signal OUTCRC, switching multiplexer MX2 to forward to UD, at the end of a message, the word generated by CRC
when the elements ECP form part of the first network stage.

The state diagram of Fig. 6 is now described.

Upon activation of the system, logic network OMC is made to enter its initial (idle) state A2 by a general reset signal (not shown), and remains in this state until the arrival of the signal START keeping signal CLCRC active. Upon the arrival of the signal START, logic network OMC enters state B2 if signal ACKOUT
is 0. Signal ACKOUT indicates the availability of the subsequent device to receive a new data word, in this case the first word of a message. Signals UNLOAD and REQOUT are emitted and signal CLCRC
is kept active in this transition. Signal REQOUT is kept active as long as the logic network OMC remains in state B2. BesideS
signalling the presence of data to be sent downstream, the logic network OMC holds, in output register RL, the word present at that instant on bus DB, to ensure its stability as long as required by the input/output protocol. Signal UNLOAD is on the contrary kept active for a single clock signal period and causes the reading, in the suitable memory FIF (Fig. 2), of the subsequent word to be transmitted, if that word is already available. Due to the simul-taneous generation of these two signals, reading of a new word in memory FIF takes place simultaneously with the dialogue with the downstream device for sending it the preceding word. This optim-izes the working cycle.

The logic network OMC remains in state B2 as long assignal ACKOUT is 0. When ACKOUT becomes l, the logic network OMC
enters state C2 (wait for FNV), resetting signals REQOUT and CLCRC. In state C2, the logic network waits for the reset of signal ACKOUT and the arrival of signal FNV indicating that memory ~ 9 2~9~
FIF is not empty. These are the two conditions allowing the trans-mission of the subsequent word, which is the message length. If these conditions are met, OMC re-enters state B2 if signal SECBYTE
is 0, or enters state H2 (wait for ACKOUT) if SECBYTE is l. What-ever the transitionl signals UNLOAD, REQOUT and LOADCT are emitted.
The signal LOADCT causes the loading, in the counter CN (Fig. 5), of the value of the message length. From that instant on, with siynal CLCRC=0, signal UNLOAD acts on circuit CRC generating and/or checking the cyclic redundancy code, causing the storage of the par~ial result of the computation of the redundancy code.

In state H2, the logic network OMC waits for ACKOUT to become active and keeps REQOUT active. When ACKOUT arrives, four different operations are possible depending on the valves of signals FSTG, LSTG and FC.
If signal FC is not l when ACKOUT becomes l, the message has yet to end, and there are other words to be transmitted. The logic network then enters state G2 for transmission of the subse-quent word and emits command DECR to the counter CN, which there-fore always indicates the serial number of the subsequent word tobe transmitted. In this way, the logic network OMC detects, as early as possible the "end of message" condition and communicates it to SCU (figO 2) so that SCU can exploit it for its operations.
Also, the logic network OMC detects the time during which transmis-sion of the last word of a message by the output unit takes place.In state G2, the logic network OMC waits for condition ACKOUT=l, FNV=l, as in state C2, and then begins the transmission of a new word and re-enters state H2. During this transition, only signals REQOUT and UNLOAD are only generated to proceed with the normal transmission cycle if FC=0 (the subsequent word to transmit is not the last) or if the element ECP is part of the last network stage.
However, if FC-l and the element ECP is not part of the last net-work stage, or if the redundancy code is not provided for, the logic network OMC generates a signal FCSCU to inform SCU (fig. 2) that the message transmission ends with the current word.

~LZ !3~497 If signal FC is l when ACKOUT becomes 1, the next state of the logic network OMC depends on FSTG and LSTG. More particu-larly if:

(a) the element ECP is part of the first network stage (FSTG=l, LSTG=0), then the logic network OMC enters state L2 (CRC generation) activating command OUTCRC
which sets multiplexer MX2 to transfer the redundancy code to output bus UD, since the redundancy code is to be generated and queued to the other words of the message only in the first network stage. The logic network OMC remains in this state until ACKOUT is reset, then it begins code transmission, activates the relevant signal REQOUT and enters state M2 (wait for ACKOUT CRC), where the acknowledgment signal relating to the redundancy code is waited from downstream devices. As soon as ACKOUT becomes l, the message transmission is ended and the logic network OMC re-enters its initial state A2, activating signal CLCRC
in order to be ready for the transmission of a new message;

(b) the element ECP is part of the last stage of the net-work (FSTG=0, LSTG=l), the logic network OMC enters state J2 (CRC elimination) without generating commands.
In this state, the presence in memory FIF (Fig. 2) of the redundancy code is checked and, in the affirmative, the code is eliminated by passing a command UNLOAD to memory FIF without transferring the datum to output bus UD. At the same time, the end of the transmission (FCSCU=l) is signalled to SCU. Signals UNLOAD, FCSCU
are generated during the return to initial state A2, together with CLCRC; or (c) the element ECP is part of an internal network stage (FSTG=0, LSTG=0) or the network does not use the redundancy code (FSTG=l, LSTG=1), then the logic net-2a()~97 work OMC re-enters its initial state A2, activating signal CLCRC.

With reference to Fig. 7, the buffer FIF functionally comprises:

(a) a memory matric MF (which by way of e~ample has a capacity of 64 8-bit words), having reading and writing pointers PL, PS;

10 (b) a logic network LFS generating signal FPI indicating that memory MF is full; and, (c) a logic network LFC which manages the operation of the reading pointer to avoid both idle times and reading of non-significant data, signals to logic network OMC
(Fig. 5) of the relevant output section, the presence of a valid datum on bus BD, and solves possible access conflicts to the same cell of MF by an input and an output section of the element.
Matrix MF, which is to be accessed in pipeline from two diferent paths to allow simultaneous reading and writing opera-tions on different cells, is advantageously a two-port memory, with separate input/output buses (bus ID, BD respectively) and an explicit reading command (READ) obtained either from signal UNLOAD or from a signal CREAD emitted by a control unit FCU of LFC with modalities which are described hereinafter.

The management of matric MF as a FIFO memory is by a circular-buffer addressing techni~ue realized by pointers PL an PS. These pointers comprise a counter CT which, under the hypo-thesis that MF stores 64 words, is a 6-bit counter, a decoupling register RD and a decoder DEl for decoding the 6 bits of the counter to select the row concerned by the demanded operation.
The components of the pointers are shown only for reading pointer PL. PL also comprises a second counter CTD, which is used in an ~Z~30~97 alternate manner with CT Eor broadcast transmission, and a multi-plexer MX3 to connect either counter to RD.

The presence of a two fold reading pointer is an archi-tectural solution allowlng broadcasting oE a message by sending it in sequence to both output gates. The first transmission of the whole message (controlled by CTD) and its retransmission (control-led by CT) follow each other in sequence and, from a theoretical point of view, can be considered as a sequence of two normal (non-~roadcast) transmissions. I-t is to be noted that no particular configuration of switch SW is demanded by this particular imple-mentation of the broadcast transmission. Besides, simultaneously with the management of a broadcast transmission relevant to one of the two input channels, another compatible transmission which also may be a broadcast transmission, can take place.
Register RD is decoupled to allow the counter and the decoder of each pointer to operate in pipeline, and thus to allow the contemporary emission of a memory reading/writing command and a counter increment signal. Therefore, reading/writing is carried out on cell N of MF while the counter is already switching to N+l, thus preparing the address of the next cell to be accessed. In the reading pointer, register RD also allows superposition of the counter and decoder switching delays and is necessary to ensure a certain minimum time for decoding operations. In fact, data 2S request signal ~NLOAD would require, as an operation sequence, first the counter increment and then the new datum reading. Were these operations carried out in subsequent times, too short a time would be left for decoding the counter output signal before the reading operation. This problem does not exist when writing, since the loading signal LOAD would require the inverse sequence (writing of a new datum, counter increment) which does not impose time requirements on the address decoding different from those already imposed by the desired reading/writing frequency (for instance, an operation every l00 ns, with the exemplary value of the clock signal considered here).

~L28l:)4~37 By examining in greater detail the pointer structure, counter CT is incremented by a signal INCRD which consists of either signal UNLOAD or a signal INCT emitted by control unit FCU. A multiplexer MX4, controlled by a signal SELB, which is generated by FCU, supplies CT with either signal. Signal INCT
increments CT independently of the presence of signal UNLOAD
coming from logic network OM (Fig. 2). This is necessary when a datum is written into the empty FIFO memory, as both the reading in MF and the corresponding increment of pointer CT are to be controlled by signals directly generated by LCF (CREAD and INCT
respectively) because, under these conditions, the operation cannot be controlled by signal UNLOAD, which is not generated when signal FNV indicating "non-empty memory" is 0.

Counter CTD is incremented by the same signal INCRD as CT and when a broadcast transmission is desired, it loads the contents of the latter upon receiving a signal DEFOIS, emitted by the control unit SCU of switch SW (Fig. 2). To this aim, signal DEFOIS is converted into a pulse of suitable duration by the circuit composed oE flip-flop FF9 and FE'l0 (the latter being clocked by CK) and gate AND3, enabled by CK~ The same signal DEFOIS forms the selector for MX3 and is input to a further flip-flop FFll, where it is delayed, clocked by CK. The flip-flop FFll generates at iks complement output a signal DEFOISD which is sup-plied to CT to disable its counting during a broadcast transmis-sion.

The address emitted by CT or CTD is loaded in RD uponreceiving signal CK.

The devices of the writing pointer PS operate analogous-ly to the devices of the reading pointer PL in a non-broadcast`
transmision. However, in this case the counter increment command is signal LOAD emitted by IM (Fig. 2)o The contents of counters CT and CTD are respectively supplied to two comparators CU, CUD, which are part of a logic L2~30497 network LFS. The comparators also receive the contents of the counter of the writing pointer PS, and emit a signal ~hich is l when the values present at both inputs are equal. The comparator outputs are connected to the two inputs of a multiplexer MX5, transferring to the output the result of the comparison made by the comparator connected to the counter active at that moment (CT
for normal transmission or retransmission of a message to be broadcast, CTD for the first transmission of a message to be broadcast). The select signal for positioning MX5 on the input connected to CUD is signal DEFOIS transferred to MX5 via the true output of FFll. The complemented output signal of MX5 is a signal EQUC which is transferred to logic network FCU which uses it for generating signal FNV, indicating a non-empty FIFO memory (valid datum), to be sent to unit SCU (Fig. 2) and, through SW, to the relavent logic network OM. The signal FNV is present at the out-put of a flip-flop FFl30 The output signal of CU (signal EQU) is also sent to logic network FSU of LFS which, on the basis of this signal and of the signal LOAD, generates signal FPI. The operation of FSU will be described hereinbelow, with re~erence to Fig. 8.

As shown in Fig. 8, FSU is a 2-state logic network. It remains in its first state (A3, idle) until the arrival of a sig-nal LOAD, whatever the logic value of EQU. Upon receiving the signal LOAD from IM, FSU enters its second state (B3, EQU check) to check, at the subsequent clock signal pulse, the value of EQU.
If EQU is 0, FSU re-enters its initial state; however, if EQU is l, signal FPl is emitted and is kept active as long as the EQU
value remains l.
It is worth noting that the signal EQU, which is design-ed to generate the "full memory" signal FPI, is always obtained as a result of the comparison between the pointer counter and the counter CT (Fig. 7). During the first transmission of a message to be broadcast, counter CT is "frozen" and determines the limit address for writing in MF. In fact, if the value indicated by CT

.2a~497 is exceeded, data which have been already transmitted are cancel-led, but are used again for the second transmission. Consequent-ly, the length of a message to be broadcast cannot exceed the capacity of MF, but this is not a severe limitation.

Returning to Fig. 7, block LFC comprises a control unit FCU and a set of logic circuits interfacing LFC with the other elements of FIF or with the outside.

Unit FCU receives the following signals:

(a) signal DEFPLA, a pulse signal indicating broadcast transmission; and, (b) signals LOAD, UNLOAD, and EQUC, already described.

It emits the following signals:

(a) signal SELB, already described;
(b) signal SELC, which updates signal FNV;

(c) signal CREAD, generating the reading command for MF, when reading is controlled by LFC, and controlling the updating of FNV~by SELC; and (d) signal INCT, already described.

Signal DEFPLA iS obtained from signal DEFOIS with modal-3~ ities similar to those by which the loading command for CTD is obtained from DEFOIS~ Signal CREAD is fed to one of the two in-puts of a gate OR2 which also receives signal UNLOAD. The output of OR2 is connected to an input of a gate AND4, which is enabled, in the absence of SELC (as indicated by inverter INV2), to gener-ate signal READ, and through a timing element or latch L6 to agate AND5 enabled by CK to control the updating of FNV.

-' ~LZ~ 7 The drawing also shows further timing elements or latches Ll...L5, determining suitable time phases for signals INCRD, UNLOAD, READ, EQUC, and EQU. L6 properly times the clock signal for FFl3~

5The operation of FCU will be now described with refer-ence to the diagram of Fig. 9.

Unit FCU is initially in a state A4, corresponding to the condition of empty memory MF. In this condition the addresses generated by both pointers PL, PS coincide and a non significant datum is present on the output bus BD of memory matrix MF. Thus signal FNV (valid datum signal) is 0. FCU remains in the initial state until it detects a loading in MF of the input section (LOAD
signal coming from IM, Fig. 2, becoming l). Then FCU enters state ~4 (first datum in the memory) emitting signals SELB and CREAD.
Signal SELB acts on multiplexer MX4, therefore the reading pointer increment is controlled by FCU. Since SELC=0 (and consequently SELC=l), signal C~EAD can be transferred to L3 through AND4 to control the reading of the datum just loaded into MF, and this operation is carried out in the subsequent cycle. The same signal CREAD, through L6 and AND5, causes signal SELC to be transferred to FFl3 and output as a signal oE valid datum FNV.

At the subsequent cycle of CK, FCU enters state C4 (last datum). In effect, owing to the hypotheses made, two data to be loaded in MF can never arrive in adjacent cycles of CK. In the transition B4-> C4, control signal SELB is ~ept present to slave memory reading to LFC, and INCT is emitted to increment counter CT
and cause it to point the next cell to be read in MT. The next cell, in this case, does not yet contain any significant datum.
Also signal SELC is emitted and consequently the next signal UNLOAD coming from OM and supplied to FFl3 through L2, OR2, L6 and AND5 resets FNV.

35FCU remains in state C4 as long as a single valid datum is present in MF. As soon as a signal LOAD arrives from IM, or a 8~49'7 signal UNLOAD arrives from OM, FCU enters a new state. If signal UNLOAD arrives first, MF becomes empty again and FCU re-enters state A4. If signal LOAD arrives first, MF contains more than one datum and FCU enters state D4. If a signal LOAD and a signal UNLOAD arrive at the same time, this means that the datum present at the output of MF (the only datum present in the memory matrix) has been already used by the output unit which now requires the next datum! and this datum is presently being written into MF by IM. This arises when a pipeline operation is attempted on the same memory cell. Such a conflict is solved as signal SELC, active as long as FCU remains in state C4, inhibits through INV2 and AND4 the reading of the memory matrix while resetting FNV. As a result of the reading operation, OM receives from BD a non-sigificant datum associated with a signal FNV=0. FCU re-enters s~ate B4 and activates signal CREAD, which during the subsequent cycle commands a reading operation in MF. Consequently, the new datum is trans-ferred to the output bus and the presence of a valid datum is signalled. At the subsequent step FCU, re-enters state C4 repeat-ing the already-described cycle.

State D4 corresponds to a condition in which several data are present in MF. This is a state in which FCU is basically in-active. Since MF contains at least two data, there is no longer a possibility of conflict between the pointers and the operations on MF are carried out in a parallel and non-synchronized wa~ by both IM and OM. In order to detect when MF again stores a single datum, which demands a new active intervention of FCU, FCU enters state E4 (reading of the last but one datum) whenever it detects the presence of a reading without a simultaneous writing (UNLOAD= l, LOAD=n). In state E4, FCU takes into consideration the signal EQU
obtained as a result of the comparison between the addresses gener-ated by the two pointers. If EQU becomes l in the cycle subsequent to the UNLOAD event, then MF contains only a last valid datum, while the reading pointer already addresses an empty cell. FCU
then re-enters state C4. Otherwise, FCU re-enters state D4 without carrying O-lt any operation.

~LZ80497 .
In any state of FCU, if DEFPLA becomes l, indicating the broadcast transmission, FCU enters state D4. In fact for message retransmission, FCU operates as if MF contained more than one datum, independently of the extent to which the memory is filled at the end of the first transmission. From a logic point of view MF contains at least all the data of the message to be retransmit-ted.

Referring to Fig. l0, which represents control unit SCU
of switch SW, BD' and BD" denote the input and output sections of internal data channel BD of Fig. 2. The control unit SCU
comprises:

(a) a finite-state automation (or control logic means) SCUBRD, the input/output signals of which are specified hereinafter and the operation listing of which is given in Appendix l;

(b) a control logic means MANET which processes the routing tags. In the case oE a broadcast transmission request ln its stage, MANET operates on the tag bits of the computing algorithm previously described to determine the possibility or impossibility of carrying out the transmission and, in the afEirmative, modifies the tag.
The structure of MANET is described hereinafter, with reference to Figures 12 to 15;

(c) two registers RTMOD and RT, which store the tag modified by MANET and the original tag present on bus BD', respectively;
(d) a multiplexer MX6 having three inputs connected to BD', RTMOD and RT, respectively, and an output connected to BD". The multiplexer MX6 is controlled by a pair of bits Sl and S0, the first of which indicates whether data or the routing tag are to be transferred to BD", while the second, in the case of tag forwarding, ~80~
indicates from which of the two registers the tag is to be extracted;

(e) a first flip-flop FFl4 which stores the routing conflict result;

(f) a second flip-flop FFl5 which stores a double transmis-sion of a broadcast message condition; and, (g) a further pair of flip-flops FFl6, FFl7, of which FFl6 emits bit Sl, while Ffl7, upon receiving signal UNLOAD, causes Sl to switch after tag transmission.

Logic SCUBRD and flip-flop FFl4 are common to both channels. However, the other elements are associated with each switch input channel, only one being represented in the Figure for sake of simplicity. In the Figure, the bit which is of interest to SCUBRD in each of the two tag portions is denoted by the refer-ence symbol already used for the whole tag portion.

Logic SCUBRD receives the following signals:

~a) TAG(A, B) which is a bit oE the normal transmission tag indicating on which output channel the message coming from input channel A or B, respectively, is to be routed at the stage. By way of example, it is supposed that values 0 and l of TAG correspond respectively to routing on channels 0 and l. Since transmission is effected in parallel, bit TAG is present on a wire of BD' which is different from stage to stage. In any stage j, the proper wire is selected through a multiplexer (not shown) controlled by a signal coding stage number j;

(b) BRD(A, B) which is a bit of the broadcast transmission tag indicating, when it has a value of l, a broadcast transmission request in the stage from one of the input ~2130~9~
channels. Bit BRD is extracted from bus BD' in the same way as TAG;

(c) signal FNV(A, B) which is a valid datum signal for one of the input channels;

(d) signal FCSCU(0, 1) which is a signal indicating trans-mission end on output channel 0 or l, respectively;

(e) signal DEFOIS(A, B) which is a signal indicating the necessity of repeating the transmission to broadcast the message present on one of the input channels;

(f) signal FFPR which is a priority signal generated by FFl4 and used to solve routing conflicts. The logic value of FFPR indicates the channel from which the message delayed at the preceding conflict came;

(g) signal TUM(A, B) which is a bit of the normal transmis-sion tag corresponding to bit BUM(A, B) in the broadcast transmission tag. Bit TUM is extracted from the tag by MANET and supplied to SCUBRD to decide the routing upon a broadcast transmission request; and, (h) signal MINUS(A, B) which is a signal supplied by MANET
and indicating the negative result of the subtraction Tc-2k effected in order to decide whether or not broad-cast transmission from the relevant input channel is to be carried out.

The output signals of control logic SCUBRD are:

(a) signal SWSET, a control signal for switch SW. SWSET=0 means e.g. straight connection through the switch (in-puts Ap B connected with outputs 0 9 l, respectively; see Fig. 2) and SWSET=l means exchange connection (inputs A, B connected with outputs l, 0, respectively);

(b) signal START(0, 1), a signal activating one of the out-put units;

(c) signal TOGGLE, a signal switching flip-flop FF14. It is set whenever SCUBRD delays the transmission of a message owing to a routing conflict;

(d) signal TOBR(A, B), a signal indicating the beginning of a broadcast transmission phase. This signal is convert-ed into signal DEFOIS by Elip-flop FF15 and into bit Sl by fl ip-flop FF16;

(e) signal ENREG(A, B), a signal enabling the writing into the two registers RTMOD and RT of the tag for the cor-responding input channel; and, (f) signal ABMOD(A, B), a signal forming control bit SO of the multiplexer MX6.

The operating principles of SCUBRD ar briefly illustrat-ed in order to point out the most typical features. The detailed algorithm description of the operation of SCUBRD is given in ~ppendix 1. The description in Appendix 1 is a version in text form of the state diagram which is not illustrated because, owing to the very high number of states, transitions between states and conditions originating such transitions, the diagram would be difficult to understand.

The starting state of the operations of SCUBRD is the idle state A5 (WAIT). It is a consequence of element initializa-tion and whenever the element itself has no message to transmit.In this state, logic SCUBRD analyzes the transmission request (normal or broadcast transmission) which can be presented by the element input units. In the absence of requests, SCUBRD remains in state WAIT. If there are one or more routing requests, SCUBRD
operates differently depending on the type of request. For sim-plicity of description, normal and broadcast transmissions are ~.zao~97 considered separately, even if the two transmission types can co-exist.

When logic SCUBRD recognizes a normal transmission request, indicated by signal FNVA or FNVB being l, it analyzes the routing bit (TAGA or TAGB) relevant to the stage it forms part of.
If the request arrives from only or.e channel, only bit TAG rele-vant to that channel is significant. SCUBRD enters one out of states B5, C5, D5 or E5 depending on which channel the request comes from and the demanded switch position, setting signal SWSET
to the proper value and activating signal START relevant to the desired output channel. If both signals FNVA and FNVB are l, bits TAGA and TAGB are compared to ascertain whether the two transmis-sions are compatible, i.e. whether the two messages are to be for-warded on different channels. If the two bits TAGA and TAGB are different, the two transmissions are compatible and SCUBRD enters state F5 or state G5, depending on the requested switch position, and starts the operations on both output channels. If the two transmissions are incompatible, SCUBRD enters one of the four states B5, C5, D5 or E5, as in the case of single request, depend-ing on which message is allotted priority by flip-flop FFl~ and which output port is to be engaged by the message. During the transition, corresponding to transmitting one message while delay-ing the other, signal TOGGLE is activated which causes storage of the identity of the channel from which the delayed message came in FFl4, so that a subsequent conflict, if any, is solved in its favour. The choice of the message to be delayed at the first con-flict is generally random and depends on the state taken by flip-flop FFl4 during the initialization phase.

In states B5, C5, D5, E5, F5, G5, the operating princi-ple of ~CUBRD is the same, but the operations are initiated by the reception of signals FCSCUO or FCSCUl (from the logic networks OMO; OMl controlling output channels 0 and l, respectively) which indicate that the preceding message has been completely transmit-ted on the relevant channel. Then SCUBRD examines the signals TAG
and FN~ relevant to the input unit section no longer concerned in ~Z8049~
the transmission and establishes a new input/output connection, activating the necessary START signals, setting the switch by means of SWSET and effecting transition toward a convenient state, or it returns to the idle state WAIT.

It is to be appreciated that, when SCUBRD iS in one of the states characterized by a single active input-output connec-tion (states B5, C5, D5, E5), it constantly checks by analyzing the relevant signals TAG and FNV, if a routing request occurs on the inactive input channel. If the routing request is compatible with the conection already existing, SCUBRD iS immediately satis-fied and SCUBRD enters a double-transmission state (F5 or ~5). If the routing request is in conflict with the existing connection, the message is delayed and the identity of the channel it comes from is stored in FFl4 to give priority to the message when the request is analysed again.

In the case of a broadcast transmission request, in which case the bit BRD of the relevant stage is l, the operations carried out by SCUBRD are more complex, since two phases are provided. These operations are:

l) checking oE the admissibility of the broadcast transmis-sion request, based on the previously described algorithm, the computations of which are carried out by M~NET; and, 2) controlling the broadcast transmission as a sequence of two normal transmissions, as already explained in con-nection with the description of the FIFO memories.
If the broadcast request is identified while in the idle state, SCUBRD enters one of two checking states in which the validity of the request is checked (BRFROMA or BRFROMB) according to the value of bit TUM. This bit identifies the output channel on which the message is to be transmitted even though the broad-casting request is not admissible for the element ECP considered.
During the transition from one state to the other, loading of the two registers RT and RTMOD is enabled through signal ENREG(A, B).

_ 30 -`` ~.Z8~)49~
RTMOD stores the result of the subtraction of parameter 2k from number Tc, the bits of which are scattered inside the routing tag as mentioned before. In the checking states, signal MINUS coming from MANET is considered. If MINUS is l (Tc-2k < 0), then broad-casting is not possible and SCUBRD enters a state corresponding to normal transmission on the channel indicated by complemented bit TUM. If MINUS is 0, then the transmission is handled as the first step of a broadcast transmission and SCUBRD re-enters the same state by activating the flag "broadcast transmission started" for the given input channel (TOBRA or TOBRB at l for input A or input B, respectively) and positioning MX6, for tag transmission, on the input connected to register RT (signal ABMOD=0).

The broadcast transmission request for a given input channel requires the second transmission phase and this is stored in flip-flop FFl5. Whenever a transmission ends, SCUBRD checks the state o~ this flip-flop (inputs DEFOIS(A/B), where DEFOI5=l indicates that the second transmission phase is still to occur) and acts accordingly, by positioning MX6 to transmit, as a tag, the modified tag and by switching signal SWSET so that the trans-mission takes place on the other output channel.

If, in the idle state of SCUBRD (WAIT), the broadcasttransmission request simultaneously appears on both input channels, a priority choice is made based on the value of flip-flop FFl4. However, this flip-flop is not switched in order that the alternate priorit~ mechanism, which is valid for normal trans-missions, is not affected. Therefore, in the case of routing conflicts between messages to be broadcast, this corresponds to allotting a random priority to the messages.
In the case where a broadcast transmission request occurs while a normal transmission is taking place, (SCUBRD in states B5, C5, D5, E5) SCUBRD operates as follows: the end of the pending transmission (signalled by FCSCUO or FCSCUl, as the case may be) is awaited and then the possibility of effecting the broadcast transmission is analyzed by the same procedure disclosed `~ ~Z80497 for state WAIT. This is possible for all the cases with the exception of a new broadcast transmission request appearing during the second phase of a preceding broadcast transmission (case in which the requests identified by code PRIMOBR(A,B) coexist with the requests identified by code SECONBR(B,A) under the conditions specified in the part CASE of the above states, see Appendix l).
In this case, first the second phase of the preceding transmission is allowed to end and then the new broadcast transmission request is served. In all the other cases logic SCUBRD enters state BRFROM ~A/B) and then it serves the broadcas-t transmission request.

If a broadcast transmission request appears while SCUBRD
is in state F5 or G5, i.e. in one of the state corresponding to two simultaneous normal transmissions, logic SCUBRD enters one out of states B5, C5, D5, E5; namely the state allowing the transmis-sion still in progress to end regularly. This state is the one in which signal SWSET Iceeps the same value and the signal START, relevant to the output port which is still active, is kept l.

Fig. ll shows the structure of block MANET. It compris-es a priority encoder PE, two bit extractors EBl, EB2, a bit re-combining device RB, a logic-arithmetic unit ALU, a multiplexer MX7 with n inputs (n = bit number in each of the tag portions, e.g. 4) and one output, a register FFT storing bit TUM to be sent to logic SCUBRD, and an n-output decoder DE2. The priority en-coder PE analyzes the broadcast transmission tag BRD and generates a binary number which codes, with a logic value of l (bit BUM) the position occupied, in BRD, by the most significant bit. The coded value is sent to MX4 as a control signal to select the correspond-ing bit TUM of the normal transmission tag and to send the bit TUM
to register FFT, where it is kept available for logic SCUBRD, and to decoder DE2, which emits a bit pattern de in which only one bit has a predetermined logic value. The position of this bit in the pattern identifies the position of bit BUM. For reasons depending on the structure of the recombining device RB, the logic value of this identifying bit should be 0.

```` ~L;~:8~497 The bit extractor EBl extracts, from the normal trans-mission tag TAG, bits TUM, TU(M-l)...TU(l), forces bit TUM to 1, and shifts it to the right (towards the less significant posi-tions) together with bits TU(M-l)...TUl, to form a number Tc.
Extractor EBl then re-emits the bits of TAG which are used in RB.
Forcing TUM to 1 is necessary to allow the unit ALU to operate correctly The structure of EBl is explained in detail with refer-ence to Fig. 12.

The bit extractor EB2 receives the bits of the broadcast transmission tag BRD and the signal j coding the number of the stage and generates the number k which was described while des-cribing the broadcast algorithm.

The logic arithmetic unit ALU executes the subtraction Tc - 2k and emits a new bit pattern NTc, representing the subtrac-tion result, and the signal MINUS which is supplied to logic SCUBRD which, as said, uses it to decide whether or not to begin a broadcast transmission cycle.

The bit recombining device RB receives the bits of the normal transmission tag TAG, the bits NTc and the bits de emitted by the decoder DE2 and, if necessary, substitutes the bits of NTc for those of Tc, letting bit TUM remain unchanged. The bits emit-ted by the decoder DE2 are the information necessary to let bit TU~ be transmitted unchanged.

With reference to Fig. 12, the bit extractor EB1, here disclosed by way of example for the case in which TAG and BRD
comprise 4 bits each, comprises a triangular matrix MDE of switch-ing circuits DEC, preceded by a group POA of OR-AND-OR gates.
This group POA identifies the position occupied by the bit TUM and sets this bit to 1 for the construction of number Tc. To this aim, bits t(3)...t(0) of TAG are each supplied to an input of a LZa~49'7 respective OR gate POR3~PORO gate POR3 receives bit b( 3) of BRD at a second input, while gates POR2~o~PORO receive a bit bt2)...b(0) respectively of BRD through an AND gates PA2...PA0 respectively, enabled through an inverter IV2~ IV0 respectively if none of the more si~nificant bits b is l: the latter informa-tion is supplied by cascaded OR gates POR32 and POR21~

The matrix MDE of circuits DEC is controlled by bits b(i), extracts from the bits t(i) the bits which form number Tc, and emits these bits compacted towards the least significant bits.

A matrix similar to MDE forms extractors EB2~ Here the gate group POA is not necessary, as Eorcing the most significant bit to l is not required.

Each switching circuit DEC has two data inputs (Ide, Pin), two date outputs (Ude, Pou) and a control input (Ice), at which it receives the suitable bit of BRD~ which is the same for all circuits in a column. The data input Ide is connected to the output Udb of the preceding circuit (with reference to the direc-tion input-output of EBl) in the same row of MDE or to the output of a respective OR gate POR3...POR0 for the first circuit in a row. The data input Pin is connected to the output Pou of the circuit in the preceding row of the same column, or to logic value 0 (ground) for the first row of switching circuits DEC.
As shown in Fig. 13, each circuit DEC consists of two multiplexers MX8 and MX9 with two inputs and one output, both con-trolled by the same bit b(i). For instance when bit b(i) is l, the input l of MX8 and MX9 is connected to the output and vice 3Q versa. The outputs of MX8 and MX9 form the outputs Ude and Pou respectively of the circuit. A select input S of each multiplexer is connected to Ice, and the data inputs of each multiplexer are each connected to either Pin or Ide bu-t to the opposite input of each multiplexer. For instance, Pin is connected to input 0 of MX8 and input l of MX9, and vice ~ersa for Ide. Thus, for a given ~ 34 ~

-` ~Z8~)~9'7 value of the select bits, the two multiplexers connect different inputs to their outputs.

The operation of circuit DEC can be deduced from Fig.
13. Depending on the value of the control input Ice, where the suitable bit of BRD is present, the circuit performs either a downward shift or a propagation along the same row. More particu-larly, if Ice = 0, the signal present on the input Ide propagates to the output Pou, and the logic 0, present on input Pin, propag-ates to the output Ude. If Ice = 1, the input Ide propagates to the output Ude and the input Pin propagates to the output Pou, the lat~er being unused. Therefore, matrix MDE performs a downward shift whenever a bit b(i) is 0, so that the bits of Tc are actual-ly compacted at its output.

With reference to Fig. 14, the recombining device RB
comprises, still considering the case of 4 bits for each tag por-tion:

(a) a trian~ular matrix MDR with 4 rows and 4 columns of switching circuits RIC which carry out, on bits ct(i) of NTc, a dual operation with respect to that performed by circuits DEC of MDE on the bits of TAG;

(b) a bank of three elements Tal, Ta2, TA3, implementing a TALLY operation on the three possible subpatterns of bits in BRD, ie., a first subpattern containing the least significant bit and the other two obtained by add-ing atthe left the bit or, respectively, the two bits of immediately higher weight. The TALLY function is con-ventional and counts the number of bits at 1 present in a bit pattern, and expresses this number in a completely decoded manner. The structure of a circuit carrying out this function is described, for example in the already-cited book by Mead and Conway, pages 78 ff. The outputs of the elements TA, combined one by one with the bits of BRD in AND gates, are sent as control signals to -" ~LZ8~)49~7 elements RIC of MDR. Only the AND gate associated with TAl is shown and is denoted ABT. The outputs of TA are indicated by tt(ll)...tt(33): the first number indi-cates the size of the subpattern on which the TALLY
function has been applied and is coincident with the row index of matrix MDR, while the second number indicates the number of bits at 1 located in the analyzed sub-pattern an is coincident with the column index of matrix MDR. The output, which indicates that all the bits are 0 (which ought to be supplied to elements RIC of the first column of MDR), is unused, since this information is unnecessary to correctly locate bit ct(0). This bit can simply move upward along the first matrix column and then propagate along the proper row in the circuit RIC
controlled by the first bit at 1 in BRD; and (c) a bank of 4 multiplexers MXUB... MXUO each having two in-puts and one output. Each multiplexer MXU(i) has an in-put connected to the output of a row of MDR, receives bit t(i) at the other input and, on the basis of the value of the logic AND between bit b(i) and the corres-ponding output de(i) oE DE2 (Fig. 11), emits, as a new bit of TAG either the signal present at the output of the relevant row of matri~ MDR or the old bit t(i).

Each circuit RIC has two data inputs Idr and Sin, two outputs Udr and Sou and a control input Icr. Each data input Idr is connected to an output Udr of the preceding block (with refer-ence to the direction input-output of RB) in the same row of MDE
or to ground if the circuit RIC is in the first column. Each data input Sin is connected to an output Sou of the circuit placed in the row below in the same column, or it receives one of the bits ct of NTc. The control signals of the individual elements RIC are obtained, as described, by a logic AND between bits b(i) of BRD
and the results of the TALLY functions, except for the first column, the circuits of which are directly controlled by bits b(i).

~L;28049~
Each switching circuit RIC consists (Fig. 15) of two multiplexers M~10, MXll each having two inputs and one output.
The outputs of the multiplexers (MXl0, MXll) form the outputs Udr and Sou of the circuit. The inputs of both multiplexers are con-nected to Idr and Sin in the same opposite manner as the multi-plexers (MX8 and MX9) in the switching circuit DEC. More particu-larly, if the bit present at the control input is 0, a connection between Sin and Sou and between Idr and Udr is set up, while if the control hit is l a connection between Idr and Sou and between Sin and Udr is set up. By this arrangement the least significant bit ct(0) of NTc propagates toward MXUO if b(0) is l. Otherwise, it is shifted upward along the first column of the matrix to the row corresponding to the first bit b at l, and then it follows a horizontal trajectory in the matrix to the input of the output multiplexer MXU of that row. The second bit ct(l) propagates horizontally if b(l) and tttll) are l (and hence if also b(0) was l). Otherwise it is shifted upward to the row corresponding to the second bit b at l and then it propagates horizontally, and so on for the following bits of NTc, until there are no longer bits at 1 in BRD. Under these conditions, the function of the output signals of the elements TA is evident, the signal of each indicat-ing how many preceding bits in BRD are l. In the multiple~ers MXU, bits ct(i), supplied by MDR, replace the bits of TAG corres-ponding to bits b(i) at 1, with the only exception of the bit corresponding to TUM. In fact, supposing that bit de(i) corres-ponding to BUM is 0, the control bit of the multiplexer in the corresponding row in RB is 0 and hence TUM is let through un-changed. The same holds for all the rows for which bit b is at 0.

It is clear that the described embodiment has been given only by way of a non-limiting example and, by modifications which are within the normal ability of the skilled in art, the invention can be applied to networks of a different type or to elements having a different number of inputs and outputs.

" 1280~97 This appendix contains the SCUBRD program in ASMA
language. To assist understanding of the program, the following remarks should be noted:
(a) the terms contained in paragraph "MACRO" identify the logical expressions determining state transitions. In these expressions, symbol "!" denotes the NOT function, "&" the AND function, and "¦" the OR function;
(b) the operations carried out in a given state are identified by the state name ~ollowed by " ". The end of each opera-tion is denoted by " ". For the states with several transition possibilities, labels "CASE", "ENDCASE" are provided after " 1l and before " ", respectively, and the logic expression, the active outputs and the next state (GOTO...) are given for each transition. The action out-puts common to all transitions of a state are listed out-side the CASE. For the states with only one transition possibility, only the list of the active outputs and the next state are given; and (c) symbol "~" indicates comments concerning the state.

Whilst the inputs/outputs are shown here in small letters, they appear in capLtal letters in the drawings.

INPUTS: fnva, taga, brda, tuma, fnvb, tagb, brdb, tumb, m;nusa, minusb, fcscuO, fcscul, defo;sa, defoisb, ffpr;
OUTPUTS: swset, startO, startl, toggle, tobra, tobrb, enrega, enregb, abmoda, abmodb;
STATES: A5 (WAIT), B5, C5, D5, E5, F5, G5, brfroma, brfromb, verso_B5, verso C5, verso 05, verso E5, verso G5, verso F5;
MACRO: nopa := !fnva&!defoisa, nopawa := !fnva, trua := fnva&!taga&!brda&!defoisa, truawa := fnva&!taga~'brda, trda := fnva&taga&!brda&!defoisa, trdawa := fnva&taga~!brda, brawa := fnva&brda, ~8C~9~
primobra := brda&fnva~!defoisa, seconbra := defoisa, 1 nopb := !fnvb&!defoisb, nopbwa := !fnvb, trub := fnvb&!tagb&!brdb&!defoisb, trubwa := fnvb&!tagb&!brdb, trdb := fnvb&tagb&!brdb&!defoisb, trdbwa := fnvb&tagb&!brdb, brbwa :- fnvb&brdb, pr;mobrb := brdb&.'nvb&!defoisb, seconbrb := defoisb;
WAIT
CASE
truawa&trubwa&ffpr:
swset := 1;
startO := 1;
toggle := 1;
GOTO B5;
nopawa&trubwa:
swset := 1;
startO := 1;
GOTO B5;
trdawa&trdbwa&ffpr:
start1 := 1;
toggle := 1;
GOTO C5;
nopawa&trdbwa:
start1 := 1;
GOTO C5;
truawa&trdbwa:
startO := 1;
s.tart1 := 1;
GOTO G5;
trdawa&trubwa:
swset := l;
startO := 1;
startl := l;

.:~
:0 - 39 -~80497 1 GOTO F5;
truawa&nopbwa:
startO := 1;
GOTO E5;
truawa&trubwa&!ffpr:
startO := 1;
toggle := 1;
GOTO E5;
trdawa&trdbwa&!ffpr:
swset := 1 startl := l;
toggle := l;
GOTO D5;
trdawa&nopbwa:
swset := l;
startl := 1;
GOTO D5;
nopawa&nopbwa:
GOTO wait;
brawa&!brbwa:
enrega := l;
. GOTO brfroma;
brawa&brbwa&ffpr:
enrega := l;
GOTO brfroma;
brawa&brbwa&!ffpr:
enregb :=1;
~ GOTO brfromb;
brbwa&!brawa:
enregb :=li GOTO brfromb;
ENDCASE

B5 # fif b transmits over channel 0; swset := 1 CASE
35trua&trub&fcscuO&!ffpr:
startO := l;
8 toggle := 1;
GOTO E5;

~8~)497 1 trua&nopb&fcscuO:
startO := 1;
GOTO E5;
trda&trdb&fcscuo&ffpr:
. startl := 1;
toggle := l;
GOTO C5;
nopa&trdb&fcscuO:
start1 := 1;
GOTO C5;
trua&trdb&fcscuO:
startO := 1;
- start1 := 1;
GOTO G5;
trda&!fcscuO ¦
trda&trub&fcscuO:
swset := 1;
startO := 1;
start1 := 1;
GOTO F5;
nopa&nopb&fcscuO:
GOTO wa;t;
trda&trdb&fcscuO&!ffpr:
swset := 1;
start1 := 1;
toggle := 1;
. GOTO D5;
trda&nopb&fcscuO:
swset := 1;
startl := 1;
GOTO D5;
trua&!fcscuO&ffpr ¦
trua&trub&fcscuO&ffpr:
swset := 1;
startO := 1;
toggle := 1;
GOTO B5;
trua&!fcscuO&!ffpr ¦

" ~LZ~0~97 1 seconbra&!fcscuO ¦
nopa&!fcscuO ¦
nopa&trub&fcscuO:
swset := 1;
startO := l;
GOTO B5;
primobra&fcscuO&!seconbrb:
enrega := 1;
GOTO brfroma;
: 10 primobra&fcscuO&seconbrb:
tobrb := l;
swset := O;
GOTO verso C5;
primobra&!fcscuO:
swset := 1;
startO := 1;
GOTO B5, seconbra&fcscuO&(nopb¦trub):
tobra := l;
GOTO verso E5;
seconbra&fcscuO&trdb:
tobra := l;
swset := O;
startl := l;
GOTO verso G5;
seconbra&fcscuO&primobrb:
tobra := l;
swset := O;
GOTO verso E5;
seconbra&fcscuO&seconbrb:
tobra := l;
tobrb := l;
GOTO verso G5;
: primobrb~fcscuO&!primobra:
enregb :=1;
GOTO brfromb;
seconbrb&fcscuO&(nopa¦trda):
O ~ tobrb := l;

o -- 4 2 Z8()4~7 1 GOTO verso_C5;
seconbrb&fcscuO~trua:
tobrb := 1;
swset := Oi startO := 1;
GOTO verso G5;
ENDCASE

C5 # f;f b trarsmits over channel 1; swset := O
CASE
trua&trub&fcscul&ffpr:
swset := 1;
startO := 1;
toggle := 1;
l5 GOTO B5;
nopa&trub&fcscu1:
swset := 1;
startO := 1;
GOTO B5;
trua&trub&fcscul&!ffpr:
startO := 1;
toggle := l;
GOTO E5;
trua&nopb&fcscu1:
startO := 1-GOTO E5;
trua&!fcscu1 ¦
trua&trdb&fcscu1:
startO := 1;
start1 := 1;
GOTO G5;
trda&trub&fcscu1:
swset := 1;
startO := 1;
start1 := 1;
GOTO F5;
trda&trdb&fcscu1&!ffpr:
~ swset := 1;
~- start1 := 1;
c~
~D -- 4 3 ~L2~30~7 1 - toggle := 1;
GOTO D5;
trda&nopb&fcscu1:
swset := l;
startl := 1;
GOTO D5;
nopa&nopb&fcscu1:
GOTO wa;t;
trda&!fcscu1&ffpr ¦
trda&trdb&fcscu1&ffpr:
start1 := 1;
toggle := l;
GOTO C5;
seconbra&!fcscu1 ¦
trda&!fcscu1&!ffpr ¦
nopa&!fcscu1 ¦
nopa&trdb&fcscul:
start1 := 1;
GOTO C5;
primobra&fcscul&!seconbrb:
enrega := 1;
GOTO brfroma;
primobrb&fcscul&!primobra:
enregb :=1;
GOTO brfromb;
$

# end of portion common to all states and # with outputs independent of the present state #

primobra&fcscul&seconbrb:
tobrb := 1;
swset := 1;
GOTO verso_B5;
primobra&!fcscul:
swset := 0;
start1 := 1;
8 GOTO C5;

O seconbra&fcscu1&(nopb¦trdb):
o 8~97 1 tobra := 1;
GOTO verso_D5;
seconbra&fcscu1&trub:
tobra := 1;
swset := 1;
startO := 1;
GOTO verso_F5;
seconbra&fcscu1&pr;mobrb:
tobra := 1;
swset := 1;
GOTO verso D5;
seconbra&fcscu1&seconbrb:
tobra := 1;
tobrb := 1;
GOTO verso F5;
seconbrb&fcscul&(nopa¦ trua):
tobrb := 1;
GOTO verso B5;
seconbrb&fcscu1&trda:
tobrb := 1;
swset := 1;
start1 := 1;
GOTO verso F5;
ENDCASE

D5 # fif a transmits over channel 1; swset := 1 CASE
trua&trub&fcscul&!ffpr:
startO := 1;
toggle := 1;
GOTO E5;
trua&nopb&fcscu1:
startO := 1;
GOTO E5;
trua&trdb&fcscu1:
startO := 1;
start1 := 1;
GOTO G5;
a trub&!fcscu1 ¦

8~497 1 trda&trub&fcscul:
swset := 1;
startO := 1;
start1 := 1;
GOTO F5;
nopa&nopb&fcscu1:
GOTO wait;
trua&trub&fcscu1&ffpr:
swset := 1;
startO := 1;
toggle := 1;
GOTO 85;
nopa&trub&fcscu1:
swset := 1;
startO := 1;
GOTO B5;
nopa&trdb&fcscu1:
start1 .:= 1;
GOTO C5;
trda&trdb&fcscu1&ffpr:
start1 := 1;
toggle := 1;
GOTO C5;
trdb&!fcscu1&!ffpr ¦
trda&trdb&fcscul&!ffpr:
swset := l;
startl := 1;
-toggle := 1;
GOTO D5;
trdb&!fcscu1&ffpr ¦
seconbrb&!fcscu1 ¦
nopb&!fcscu1 ¦
trda&nopb&fcscu1:
swset := 1;
start1 := 1;
GOTO D5;
~ primobra&fcscul&!primobrb:
a enrega := 1;

.,,., ., 8~)497 1 GOTO brfroma;
primobrb&fcscu1&!seconbra:
enregb :=1;
GOTO brfromb;

5 #
# end of portion common to all states and # w;th outputs independent of the present state #

primobra&fcscu1&seconbrb:
tobrb := 1;
swset := O;
GOTO verso_B5;
primobrb&!fcscu1:
swset := 1;
start1 := 1;
GOTO D5;
seconbra&fcscul&(nopb¦ trub):
tobra := l;
GOTO verso E5;
seconbra&fcscul&trdb:
tobra := 1;
swset := O;
start1 := 1;
GOTO verso G5;
seconbra&fcscul&primobrb:
tobra := l;
swset := O;
GOTO verso D5;
seconbra&fcscul&seconbrb:
tobra := 1;
tobrb := 1;
GOTO verso_G5;
seconbrb&fcscul&tnopa¦ trda):
tobrb := 1;
GOTO verso C5 seconbrb&fcscu1&trua:
:0 tobrb := 1;
O swset := 0;

o -- 4 7 12~04g7 1 startO := 1;
GOTO verso_G5 ENDCASE

5 E5 # fif a transmits over channel 0; swset := O
CASE
trua&trub&fcscuO&ffpr:
swset := 1;
startO := 1;
toggle := 1;
GOTO 85;
nopa&trub&fcscuO:
swset := 1;
startO := 1;
GOTO C5;
trda&trub&fcscuO:
swset := 1;
startO := 1;
start1 := 1;
GOTO F5;
trda&trdb&fcscuO&ffpr:
start1 := 1;
toggle := 1;
GOTO C5;
nopa&trdb&fcscuO:
startl := 1;
GOTO C5;
trdb&!fcscuO ¦
trua&trdb&fcscuO:
startO := 1;
start1 := 1;
GOTO G5;
trda&trdb&fcscuO&!ffpr:
swset := 1;
start1 := 1;
toggle := 1;
GOTO D5;
trda&nopb&fcscuO:
swset := 1;

~Z80497 1 startl := 1;
- GOTO D5;
nopa&nopb&fcscuO:
GOTO wait;
trub&!fcscuO&!ffpr ¦
trua&trub&fcscuO&!ffpr:
startO := 1;
toggle := 1;
GOTO E5;
trub&!fcscuO&ffpr ¦
seconbrb&!fcscuO ¦
nopb&!fcscuO ¦
trua&nopb&fcscuO:
startO := 1;
GOTO E5;
pr;mobra&fcscuO&!primobrb:
enrega := 1;
GOTO brfroma;
primobrb&fcscuO&!seconbra:
enregb :=1;
GOTO brfromb;
#

# end of port;on common to all states and # with outputs independent of the present state 25 #
primobra&fcscuO&seconbrb:
tobrb := 1;
sws~t := 1i GOTO verso_B5;
primobrb~!fcscuO:
swset := O;
startO := 1;
GOTO verso ES;
seconbra&fcscuO&(nopb¦ trdb):
tobra := 1;
GOTO verso D5;
seconbra&fcscuO&trub:
~- tobra := 1;
Q

~LZ8~497 ., ~ , 1 swset := 1;
startO := 1;
GOTO verso F5;
seconbra&fcscuO&primobrb:
tobra := 1;
swset := 1;
GOTO verso E5;
seconbra&fcscuO&seconbrb:
tobra := 1;
tobrb := 1;
GOTO verso F5;
seconbrb&fcscuO&(nopa¦ trua):
tobrb := 1;
GOT0 verso B5;
seconbrb&fcscuO&trda:
tobrb := 1;
swset := 1;
start1 := 1;
GOTO verso F5;
ENDCASE

F5 # f;f a transm;ts over channel 1, fif b over channel 0; swset := 1 CASE
trua&!fcscuO&fcscu1&ffpr ¦
trua&trub&fcscuO&fcscul&ffpr:
swset := 1;
startO := 1;
toggle := 1;
GOTO B5;
trua&!fcscuO&fcscu1&!ffpr ¦
seconbra&!fcscuO&fcscu1 ¦
nopa&!fcscuO&fcscu1 ¦
; nopa&trub&fcscuO&fcscu1:
swset := 1;
startO := 1;
GOTO B5;
g trda&trd~&fcscuO&fcscu1&ffpr:
a start1 := 1;

~ - 50 -.

1 toggle := 1;
GOTO C5;
nopa&trdb&fcscuO&fcscu1:
start1 := 1;
GOTO C5;
trua&trub&fcscuO&fcscul&!ffpr:
startO := 1;
toggle := 1;
GOTO E5;
trua&nopb&fcscuO&fcscu1:
startO := 1;
GOTO E5;
trdb&fcscuO&~fcscu1&!ffpr ¦ .
trda&trdb&fcscuO&fcscu1&!ffpr:
swset := 1;
start1 := 1;
toggle := 1;
GOTO D5;
trdb&fcscuO&!fcscu1&ffpr ¦
seconbrb~fcscuO&!fcscu1 ¦
nopb&fcscuO&!fcscu1 ¦
trda&nopb&fcscuO&fcscu1:
swset := 1;
start1 := 1;
GOTO D5;
nopa&nopb&fcscuO&fcscul:
GOTO wait;
trua&trdb&fcscuO&fcscu1:
startO := 1;
start1 := 1;
GOTO G5;
!fcscuO&!fcscu1 ¦
trda&!fcscuO&fcscu1 ¦
trub&fcscuO&!fcscu1 ¦
trda&trub&fcscuO&fcscu1:
. swset := 1;
g startO := 1;
a start1 := 1;

1 GOTO F5;
primobra&fcscuO&fcscu1&!
(seconbrb¦ primobrb):
enrega := 1;
GOTO brfroma;
pr;mobra&fcscuO&fcscu1&pr;mobrb&ffpr:
enrega := 1;
GOTO brfroma;
pr;mobra&fcscuO&fcscu1&pr;mobrb&!ffpr: -enregb :=1;
GOTO brfromb;
pr;mobrb&fcscuO&fcscu1&!
(seconbra¦pr;mobra):
. enregb :=1;
GOTO brfromb;
#

# end of port;on common to all states and # w;th outputs ;ndependent of the present state #
pr;mobra&fcscuO&fcscul&seconbrb:
tobrb := 1;
GOTO verso C5;
pr;mobra&!fcscuO&fcscul:
swset := 1;
startO := 1;
GOTO B5;
primobrb&fcscuO&!fcscul:
swset := 1;
start1 := 1;
GOTO D5;
seconbra&fcscuO&fcscu1&(nopb¦trub):
tobra := 1;
GOTO verso E5;
seconbra&fcscuO&fcscu1&trdb:
tobra := 1;
swset := O;
2 start1 := 1;
a GOTO verso G5;

lZ80497 1 seconbra&fcscuO&fcscu1&pr;mobrb:
tobra := 1;
swset := O;
GOTO verso E5;
seconbra&fcscuO&fcscul&seconbrb:
tobra := 1;
tobrb := 1;.
GOTO verso G5;
seconbrb&fcscuO&fcscu1&(nopa¦ trda):
tobrb := 1;
GOTO verso_C5;
seconbrb&fcscuû&fcscu1&trua:
tobrb := 1;
swset := O;
startO := 1;
GOTO verso G5;
ENDCASE

G5 # f;f a transmits over channel 0, fif b over channe~ 1; swset := O
CASE
trda&trub&fcscuO&fcscu1:
swset := l;
startO := 1;
startl := 1;
GOTO F5;
trua&trub&fcscuO&fcscu1&ffpr:
swset := 1;
startO := 1;
toggle := 1;
GOTO B5;
nopa&trub&fcscuO&fcscu1:
swset := 1;
startO := 1;
GOTO B5;
trda&fcscuO&!fcscu1&ffpr ¦
trda&trdb&fcscuO&fcscu1&ffpr:
start1 := 1;
a toggle := 1;
, ~ - 53 -:}

GOTO C5;
trda&fcscuO&!fcscu1&!ffpr ¦
seconbra&fcscuO&!fcscul ¦
nopa&fcscuO&!fcscul nopa&trdb&fcscuO&fcscu1:
start1 := 1;
GOTO CS;
trda&trdb&fcscuO&fcscu1&!ffpr:
swset := 1;
start1 := 1;
toggle :- 1;
GOTO D5;
trda&nopb&fcscuO&fcscu1:
swset := 1;
. start1 := 1;
GOTO D5;
trub&!fcscuO&fcscu1&!ffpr ¦
trua&trub&fcscuO&fcscu1&!ffpr:
startO := 1;
toggle := 1;
GOTO E5;
trub&!fcscuO&fcscu1&ffpr ¦
seconbrb&!fcscuO&fcscu1 ¦
nopb&!fcscuO&fcscu1 ¦
trua&nopb&fcscuO&fcscu1:
startO := 1;
GOTO E5;
nopa&nopb&fcscuO&fcscu1:
GOTO wait;
!fcscuO&!fcscu1 ¦
trua&fcscuO&!fcscu1 trdb&!fcscuO&fcscu1 ¦
trua&trdb&fcscuO&fcscu1:
startO := 1;
start1 := 1;
GOTO G5;
o pr;mobra&fcscuO&fcscu1&!
O (seconbrb¦ pr;mobrb): .
m .0 ~ 5 4 1 enrega := 1;
GOTO brfroma;
pr;mobra&fcscuO&fcscu1&primobrb&ffpr:
enrega := 1;
GOTO brfroma;
primobra&fcscuO&fcscu1&primobrb&!ffpr:
enregb :=1;
GOTO brfromb;
primobrb&fcscuO&fcscu1~!
; 10 (seconbra¦primobra):
enregb :=1;
GOTO brfromb;
#
# end of port;on common to all states and 15 # with outputs ;ndependent of the present state #
pr;mobra&fcscuO&fcscu1&seconbrb:
tobrb := 1;
swset := 1;
~ 20 GOTO verso B5;
;~ pr;mobra&fcscuO&!fcscu1:
swset := O;
start1 := l;
GOTO C5;
primobrb&!fcscuO&fcscul:
swset := O;
startO := 1;
GOTO E5;
seconbra&fcscuO&fcscul&(nopb¦ trdb):
tobra := 1;
GOTO verso ~5;
seconbra&fcscuO&fcscul&trub:
tobra := 1;
swset := 1;
startO := l;
GOTO verso F5;
0 seconbra&fcscuO&fcscu1&primobrb:
~O
tobra := 1;

. .; :

1 swset ~
GOTO verso_D5;
seconbra&fcscuO&fcscu1&seconbrb:
tobra := 1;
tobrb := 1;
GOTO verso F5;
seconbrb&fcscuO&fcscu1&(nopa¦ trua):
tobrb := 1;
GOTO verso B5;
seconbrb&fcscu0&fcscu1&trda:
tobrb := 1;
swset := 1;
start1 := 1;
GOTO verso F5;
ENDCASE

brfroma abmoda := 1;
CASE
!minusa&tuma:
tobra :=1;
GOTO verso 05;
!m;nusa&!tuma:
tobra :=1;
GOTO verso E5;
m;nusa&tuma:
A GOTO verso D5;
m;nusa&!tuma:
GOTO verso E5;
ENDCASE

30brfromb abmodb := 1;
CASE
!minusb&tumb:
tobrb :=1;
: GOTO verso B5;
!m;nusb&~tumb tobrb :=1;
GOTO verso C5;
minusb&tumb:
~ GOTO verso B5;

12~30497 1 minusb&!tumb:
GOTO verso_C5;
ENDCASE

5 verso B5 startO := l;
startl := O;
swset := 1;
GOTO B5;
1 o verso-c5 startO := O;
start1 := 1;
swset := O;
GOTO C5;
verso_D5 startO := O;
start1 := 1;
swset := 1;
GOTO D5;

verso E5 startO := 1;
startl := O;
swset := 0;
GOTO E5;
verso F5 startO := 1 startl := 1 swset := 1;
GOTO F5;

startO := 1;
start1 := 1;
swset := 0;
GOTO G5;

ENDSCUBRD

Claims (14)

1. A packet-switching element for a self-routing, multi-stage, interconnection network allowing broadcasting of packets which are forwarded through the network, the packet-switching element having inputs and outputs and comprising:

an input unit having as many sections as there are in-puts of the packet-switching element, each section comprising a FIFO memory for buffering of each packet prior to forwarding each packet toward the output;

a switch associated with a control unit which, for each packet to be forwarded, sets up a requested connection for that packet between one input and one or more outputs of the packet-switching element based on information contained in a routing tag associated with each packet and comprising a first portion for normal routing and a second portion for broadcasting in each dif-ferent network stage, and which solves possible routing conflicts between packets simultaneously arriving at different inputs; and an ouput unit comprising as many section as there are outputs of the packet-switching element and performing the func-tions necessary for correctly forwarding each packet toward a destination;

wherein the control unit comprises control logic means which, upon detection of a broadcasting request, evaluate the possibility of accepting the request by comparing a first para-meter, related to the number of destinations to which a packet is to be broadcast, and a second parameter, related to the position of the stage to which the packet-switching element forms part of amongst the stages where broadcasting is requested, and indicat-ing the maximum number of network outputs which potentially may be seized for broadcasting of a particular message, which accept the broadcasting request if the first parameter is greater than or equal to to second one, which generate, if the request is accepted, a broadcast signal for communicating this condition to the FIFO memory storing the packet to be broadcast, and which generate at least one modified routing tag which is sent through one of the outputs of a packet-switching element affected by the broadcasting, the broadcasting request being processed in a packet-switching element within a stage, independently of the processing of other broadcasting requests in other elements in the same stage; and wherein the FIFO memory of each input unit section comprises broadcasting means for carrying out the broadcasting of a packet, in the presence of the broadcast signal generated by the control unit if a broadcasting request is accepted through a plurality of consecutive readings of the same packet.

2. An element according to claim 1 in which, in case of a two-input and two-output element, the first parameter is a binary number obtained by extracting from the first tag portion of the routing tag the bits relevant to the stages wherein broadcasting is requested, by compacting these bits toward the least signifi-cant positions, and by forcing the most significant bit of the first tag portion to 1, and the second parameter is given by 2k, where k is the serial number of the stage the packet-switching element forms part of in the sequence of stages wherein broad-casting is requested.

3. An element according to claim 2 in which the modified tag is obtained by replacing, in the first tag portion of the routing tag, the bits used for building up the first parameter, with the exception of the most significant bit, by the bits storing the result of the subtraction between the first and second parameters.

4. An element according to claim 1 in which the control unit of the switch comprises:

first control logic means associated with each input of the switch and arranged to effect subtraction between the first and second parameters, to generate a signed signal indicating whether or not the subtraction gives a negative result, and to build up the modified tag;

a first and second register associated with each input of the switch, storing the modified tag and the routing tag, respectively;

a first multiplexer for associating either the modified tag or the routing tag with a packet which has been switched; and a second control logic means which sets up the connec-tions between the inputs and the outputs of the switch by utiliz-ing the routing tag, the signed signal indicating the sign of the result of the subtraction, and the most significant bit of the first portion of the routing tag used in forming the first para-meter, which controls the first multiplexer to supply the switch, in a time phase intended for tag transmission, with the content of the first or the second register, which stores the condition of broadcast transmission of a packet, in case the corresponding request is accepted, and which controls forwarding of each packet to the destination(s) of the section(s) of the output units concerned.

5. An element according to claim 4 in which the first control logic means comprises:

a first bit extractor, which receives the bits forming the first and second tag portions of the routing tag and builds up the first parameter;

a second bit extractor, which receives the bits of the second tag portion of the routing tag and a first bit pattern indicating the serial number of the network stage the element forms part of and which generates a second bit pattern represent-ing the serial number of the network stage in the sequence of stages where broadcasting is requested;

an arithmetic-logic unit receiving the first parameter and the second bit pattern forming the serial number of the stage, calculating the second parameter, effecting the subtrac-tion between the first and second parameters and emitting on a first output the numerical result of the subtraction and the signed signal indicating the sign of the subtraction;

a priority encoder receiving the bits forming the second tag portion of the routing tag and supplying a third bit pattern coding the position of the most significant bit among those which, in the second tag portion, have a first logic value indicating a broadcasting request;

a decoder, connected to the output of the priority encoder, generating a fourth bit pattern where a single bit has a predetermined logic value and indicates, by its position, the position of the most significant bit in the second tag portion among those having the first logic value;

a bit recombining device receiving the bits of both tag portions of the routing tag, the numerical result of the subtrac-tion and the fourth bit pattern, and emitting the modified tag;

a second multiplexer, controlled by the third bit pattern and selecting, out of the bits of the first tag portion of the routing tag, the most significant bit amongst those used to build up the first parameter; and a third register, arranged to store and keep available for the second control logic means the bit selected by the second multiplexer.

6. An element according to claim 5 in which the first and second bit extractors each comprises a triangular matrix of first switching circuits, the matrix rows of the first bit extractor each associated with one bit of the first tag portion of the routing tag and the matrix rows of the second bit extractor associated with one bit of the first bit pattern, the matrix columns of both extractors each associated with one bit of the second tag portion of the routing tag, each first switching circuit having a first input and a first output which are con-nected to forward toward the output of the bit extractor the bit of the first tag portion of the routing tag or of the first bit pattern, respectively, associated with the row the first switch-ing circuit forms part of, when the bit of the second tag portion associated with the column the first switching circuit forms part of has the first logic value, and a second input and a second output between which a logic value complementary to the first logic value propagates when the column the first switching circuit forms part of has the complementary logic value.

7. An element according to claim 5 in which each of the first switching circuits comprises:

a third multiplexer which has a first and a second in-put connected to the first and the second input, respectively, of the first switching circuit and an output connected to the first output of the first switching circuit, which receives as a control signal a bit of the second tag portion of the routing tag and which establishes the connection between the first input and the output of the first switching circuit when the control bit has the first logic valve;

a fourth multiplexer which has a first and a second input connected to the second and the first input of the first switching circuit, respectively, and an output connected to the second output of the first switching circuit, which receives as a control signal the same bit of the second tag portion of the routing tag as the third multiplexer and which establishes the connection between the first input and the output of the first switching circuit when the control bit has a logic value which is complementary to the first logic value.

8. An element according to claim 6 in which the first bit extractor further comprises a group of logic gates identifying the position of the most significant bit among those used to build up the first parameter and which forces the logic value of the most significant bit to 1, the outputs of the gate group con-nected to the first circuit of a respective row of the matrix of first switching circuits.

9. An element according to claim 5 in which the bit re-combining device comprises:

a bank of counting circuits, the number of which is equal to the number of bits of the second tag portion of the routing tag diminished by one unit, each counting circuit count-ing the bits which have the first logic value in a respective group of bits comprising at least one bit of the second tag por-tion, and emitting an output signal indicating in a decoded way the result of the counting, and a first group consisting of the least significant bit of the second tag portion, while each sub-sequent group is obtained by progressively adding a more signifi-cant bit, up to a last group consisting of all the bits of the second tag portion, with the exception of the most significant bit;

a triangular matrix of second switching circuits, the rows of which each are associated with a bit of the first and second tag portions of the routing tag and the columns of which are associated with a bit of the numerical result of the subtrac-tion between the first and second parameters, each second switch-ing circuit having a first input and a first output which are connectable to cause the bit of the result of the subtraction to propagate along the column the circuit is part of, when a control signal, consisting of the bit of the second tag portion associat-ed with the row the circuit is part of for circuits in the first matrix column or consisting of the logic product between the bit in the second tag portion and an output signal of the counting circuits for circuits in the other matrix columns, has a logic value complementary to the first logic value, each second switch-ing circuit further having a second input and a second output which, when the control signal has the first logic value, are connected respectively to the first output and to the first input allowing the logic value corresponding to ground to propagate along the matrix column and the bit of the subtraction result to propagate along the row of the triangular matrix of second switching circuits; and a bank of multiplexers which are each associated with a row of the triangular matrix of second switching circuits, which each have two inputs which receive respectively the signal present at the output of the associated row of the triangular matrix of second switching circuits and a bit of the first tag portion of the routing tag, and which receive as a control signal the logic product between corresponding bits of the second tag portion of the routing tag and of the fourth pattern, each multi-plexer transferring to the output the signal supplied by the respective matrix row if the bit of the second tag portion indi-cates a broadcasting request and is not the most significant bit, and each transferring to the output a bit of the first tag por-tion of the routing tag under all the other conditions.

10. A element according to claim 9 in which each of the second switching circuits comprises:

a fifth multiplexer which has a first and a second in-put connected to the inputs of the first and second switching circuits, respectively, and an output connected to the output of the second switching circuit, and which establishes a connection between its first input and the output, when the control signal has the first logic value; and a sixth multiplexer which has a first and a second in-put connected to the inputs of the first and second switching circuits, respectively, and an output connected to the first out-put of the second switching circuit, and which establishes a con-nection between its second input and the output, when the control signal has a logic value complementary to the first logic value.

11. An element according to claim 1 in which, in the case of elements having two outputs, the means that in the FIFO memory of the input unit allows a plurality of consecutive readings of a same packet for broadcast transmission comprises a pair of read-ing address counters, incremented by the same advance signal, the first counter loading the count of the second counter in corres-pondence with the arrival of the broadcast signal emitted by the switch control unit to indicate that the reading to be carried out is the first reading of the broadcast transmission, while the second counter remains disabled as long as the advance signal is present, the outputs of the two counters being connected to the two inputs of a multiplexer which outputs, as a reading address, the count of the first counter or of the second in the presence of absence, respectively, of the broadcast signal emitted by the control unit of the switch.

12. An element according to claim 1 in which the control unit of the switch further comprises a memory device which, in the case of a routing conflict, stores the identity of the input of the element in which a packet is delayed, in order to prevent the delayed packet from being further delayed at a subsequent conflict concerning it.

13. An element according to claim 1, in which the element further comprises, in each section of the output unit, means which, for each packet to be forwarded through the network, in the first network stage, generates a check word for checking the transmission regularity and transmits the check word after packet word transmission, and in any subsequent stage, checks the cor-rectness of the check word, and in the last stage checks the cor-rectness of the check word and eliminates it before transmission of the packet, and means which, for the stages in which check word correctness is checked, delays, by a time period equal to one word transmission period, a signal indicating the end of packet forwarding on the element output.

14. An element according to claim 13 in which the check word is a cyclic redundancy code computed in parallel.