Data processing system having a star coupler with contention circuitry

• US 4,428,046 A
• Filed: 05/05/1980
• Issued: 01/24/1984
• Est. Priority Date: 05/05/1980
• Status: Expired due to Term

• Current Assignee: NCR Corporation (NCR Voyix Corporation)
• Original Assignee: NCR Corporation (NCR Voyix Corporation)
• Inventors: Duke, Jack R., Chari, Venu, Gersten, Shimon
• Primary Examiner(s): Thomas, James D.
• Assistant Examiner(s): Eng, David Y.
• Application Number:
  US06/146,805
• Time in Patent Office: 1,359 Days
• Field of Search: 370/80, 370/85, 370/82, 371/34, 364/200 MS File, 364/900 MS File, 340/825.19, 340/825.5, 340/825.51, 340/825.03, 455/612, 455/606, 455/607, 324/96, 350/96.15, 350/96.16, 350/96.1, 350/96.2, 350/96.3, 350/96.23, 358/901
• US Class Current: 710/116
• CPC Class Codes: G06F 13/14 Handling requests for interconnection or transfer
• CPC Class Codes: G06F 15/17337 Direct connection machines, e.g. completely connected computers, point to point communication networks coupling between buses G06F13/4004

Abstract

A data processing system having a plurality of subsystems linked by a star coupler. The star coupler includes contention circuitry for controlling the star coupler so that at any given time no more than one selected subsystem can pass a message through the star coupler. The contention circuitry uses a conventional priority encode circuit to determine the selected one of the subsystems, so that the first message to be received from one of the subsystems is the message passed or, if two or more messages are received from subsystems simultaneously, the message from the subsystem having the highest relative priority established by the priority encode circuit is the message passed. In an embodiment showing an expanded star coupler, the contention circuitry has plural first level contention circuits and a second level contention circuit, each using a conventional priority encode circuit.

Claims

1. A data processing system, comprising:

a plurality of subsystems, wherein each subsystem has an active condition when generating a message and an idle condition when no message is being generated, and wherein each subsystem generates a stream of repetitive binary bits when in its idle condition;

first transmission means associated with each subsystem for carrying messages from the associated subsystem when the associated subsystem is in its active condition, and for carrying said stream of repetitive binary signals from the associated subsystem when the associated subsystem is in its idle condition;

second transmission means associated with each subsystem for carrying messages to the associated subsystem, and for carrying said repetitive binary signals to the associated subsystem;

a star coupler for linking each first transmission means to every second transmission means so that a message from the first transmission means associated with one of said subsystems can be passed to the second transmission means associated with every subsystem, including contention circuitry in the star coupler for selecting one subsystem and controlling the star coupler so that only the messages from the first transmission means of the selected subsystem are passed through the star coupler to each second transmission means associated with every subsystem, and wherein said contention circuitry comprises means for controlling the star coupler to pass only the meassage received first in time at the star coupler, and for assigning a relative priority to each of said subsystems, for controlling the star coupler so that, if the beginning of more than one message is received simultaneously from more than one subsystem, only the message from the first transmission means associated with the subsystem having a higher assigned priority is passed to each second transmission means wherein said contention circuitry includes means for detecting the absence of a message on any first transmission means;

first gate means associated with each subsystem, each first gate means being connected to the first transmission means of its associated subsystem for receiving any message generated from its associated subsystem, and each first gate means being controlled by the contention circuitry to pass a message only when its associated subsystem has been selected by the contention circuitry;

second gate means associated with each subsystem, each second gate means being connected to every first gate means for receiving messages passed by each first gate means, each second gate means being connected to the second transmission means of its associated subsystem to pass a message thereto, each second gate means being controlled by the contention circuitry so that when one of the subsystems has been selected to have its message passed through the star coupler, each second gate means receives the message from the first gate means associated with the selected subsystem and passes the message to the second transmission means of its associated subsystem; and

third gate means associated with each subsystem, each third gate means connected between the first transmission means and the second transmission means of its associated subsystem and controlled by the means for detecting the absence of a message so that when all of the subsystems are in an idle condition, the repetitive binary signals from each subsystem are passed through the third gate means back to the same subsystem.

2. In a data processing system having a plurality of subsystems, a first transmission line associated with each subsystem for carrying messages from that subsystem, a second transmission line associated with each subsystem for carrying messages to that subsystem, and a star coupler for operatively connecting any first transmission line to every second transmission line so that a message on one first transmission line from one of the subsystems is passed to every second transmission line and goes to all of the subsystems, where two or more subsystems may each simultaneously transmit a message to its associated first transmission line to be passed through the star coupler, the improvement for preventing the superimposition of a message from one subsystem upon a message from another subsystem at the star coupler and on each second transmission line, wherein each subsystem has an active condition in which it generates a message and an idle condition in which it generates repetitive binary bits, wherein each subsystem generates beginning flag bits preceeding each message, and wherein the star coupler comprises:

a flag detection circuit associated with each of the subsystems, each flag detection circuit connected for receiving the beginning flag bits and the repetitive binary bits from the associated subsystem, and providing a FLAG signal indicating when the beginning flag bits have been received and an IDLE signal indicating when the repetitive bits have been received;

contention means responsive to the beginning flag bits from the first transmission line associated with each of the subsystems for controlling the star coupler, the contention means selecting one subsystem for controlling the star coupler so that, at any given point in time, only one message from the first transmission line of a selected one of the subsystems is passed through the star coupler to every second transmission line going to all of the subsystems, wherein the contention means comprises;

a priority encode circuit connected for receiving the FLAG signal from each flag detection circuit and in response providing address signals representing only the selected one of the subsystems and a DMND signal indicating the absence of flag bits from any of the subsystems;

a decode circuit for receiving the address signals and in response providing a SELECT signal associated with each of the subsystems indicating whether each of the subsystems is the selected one of the subsystems;

flip-flop means connected for receiving the DMND signal and the IDLE signal associated with the selected one of the subsystems, for providing a COUPLER SELECT signal for indicating the active condition of the selected one of the subsystems and the subsequent idle condition of the selected one of the subsystems; and

gate means associated to each first transmisson line and to each second transmission line, and controlled by each SELECT signal and the COUPLER SELECT signal in order to pass the message from the first transmission line associated with the selected one of the subsystems to the second transmission line associated with every one of the subsystems.

3. In a data processing system having a plurality of subsystems including at least two groups of subsystems, a first transmission line associated with each subsystem for carrying messages from that subsystem, a second transmission line associated with each subsystem for carrying messages to that subsystem, and a star coupler for operatively connecting any first transmission line to every second transmission line so that a message on one first transmission line from one of the subsystems is passed to every second transmission line and goes to all of the subsystems, where two or more subsystems may each simultaneously transmit a message to its associated first transmission line to be passed through the star coupler, the improvement for preventing the superimposition of a message from one subsystem upon a message from another subsystem at the star coupler and on each second transmission line, wherein each subsystem has an active condition in which it generates a message and an idle condition in which it generates repetitive binary bits, wherein each subsystem generates beginning flag bits preceeding each message, and wherein the star coupler comprises:

(1) a flag detection circuit associated with each of the subsystems, each flag detection circuit connected for receiving the beginning flag bits and the repetitive binary bits from the associated subsystem, for providing a FLAG signal indicating when the beginning flag bits have been received, and for providing an IDLE signal indicating when the repetitive bits have been received;

(2) a second level gate means;

(3) contention means responsive to the beginning flag bits from the first transmission line associated with each of the subsystems for controlling the star coupler, the contention means selecting one subsystem for controlling the star coupler so that, at any given point in time, only one message from the first transmission line of a selected one of the subsystems is passed through the star coupler to every second transmission line going to all of the subsystems, wherein the contention means comprises;

(3)(a) at least two first level contention circuits, with each first level contention circuit associated with one of the groups of subsystems, where each first level contention circuit comprises a priority encode circuit connected for receiving the FLAG signal from the flag detecton circuit associated with each of the subsystems in the associated group of subsystems, for generating a DMND signal indicating when one of the subsystems of the associated group of the subsystems is a first level selected subsystem, and for generating a SELECT signal for each subsystem of its group of the subsystems indicating whether each subsystem of the associated group of the subsystems is the first level selected subsystem;

(3)(b) a second level contention circuit connected for receiving the DMND signal and the SELECT signals from each first level contention circuit and further connected for receiving the IDLE signal from each flag detection circuit, where the second level contention circuit includes a priority encode circuit for generating a TSELECT signal associated with each first level contention circuit for indicating whether the first level selected subsystem and its associated group of the subsystems is to have its message passed as the selected one of the subsystems, the second level gate means being controlled by the TSELECT signal; and

(3)(c) first level gate means connected to each first transmission line and controlled by the SELECT signals from each first level contention circuit in order to pass the message from the first level selected subsystem in the group of subsystems associated with each first level contention circuit, the second level gate means being connected to receive and pass one of the messages of each first level selected subsystem from each first level gate means as message from the selected one of the subsystems.

4. In a data processing system having a plurality of subsystems, a first serial transmission line associated with each subsystem for carrying messages from that subsystem, a second serial transmission line associated with each subsystem for carrying messages to that subsystem, and a star coupler for operatively connecting each first transmission line to every second transmission line so that a message from one of the subsystems may be delivered to all of the subsystems, and wherein more than one subsystem may each simultaneously transmit a message to its associated first transmission line, the improvement wherein each subsystem has an active condition in which it generates a message and an idle condition in which it generates repetitive bits, wherein each subsystem generates beginning flag bits preceding each message, and wherein the star coupler comprises:

a flag detection circuit associated with each subsystem, including a register connected for storing bits received from the first transmission line of the subsystem and a decode circuit connected for receiving the stored bits and providing a FLAG signal when the beginning flag bits are received by the register and an IDLE signal when the repetitive bits are received by the register;

contention circuitry for controlling the star coupler so that at any given point in time only one message from the first transmission line associated with a selected one of the subsystems is passed through the star coupler to the second transmission lines associated with all of the subsystems, the contention circuitry comprising;

a priority encode circuit connected for receiving the FLAG signal from each flag detection circuit and in response providing address signals representing only the selected one of the subsystems, and providing a DMND signal indicating whether a subsystem has been selected, the priority encode circuit providing the address signals so that the selected one of the subsystems is the subsystem whose associated flag detection circuit is first in time to provide a FLAG signal to the priority encode circuit and, if the FLAG signals from two flag detection circuits are provided during the same clock cycle, is the subsystem with a higher predetermined relative priority established by the priority encode circuit;

a decode circuit connected for receiving the address signals from the priority encode circuit and in response providing a SELECT signal for each of the subsystems indicating whether each subsystem is the selected one of the subsystems; and

flip-flop means connected to the priority encode circuit, the decode circuit and the flag detection circuit for being responsive to the DMND signal, the SELECT signals, and the IDLE signals, said flip-flop means for providing a COUPLER SELECT signal, the COUPLER SELECT signal indicating the active condition of the selected one of the subsystems, and for inverting the COUPLER SELECT signal to provide a COUPLER IDLE signal;

first gate means associated with each of the subsystems, connected for receiving one of the SELECT signals, and connected to one of the first transmission lines for receiving the message from one of the subsystems, and for passing the message if that subsystem is the selected one of the subsystems;

second gate means associated with each of the subsystems, each second gate means connected to every first gate means and connected to the second transmission line of its associated subsystem, for receiving the COUPLER SELECT signal and passing the message from the selected one of the subsystems to each second transmission line; and

third gate means associated with each subsystem and connected between the first transmission line and the second transmission line of its associated subsystem, each third gate means for receiving the COUPLER IDLE signal and passing the repetitive bits between its connected first and second transmission lines when all of the subsystems are in the idle condition.