Multiplex communications – Communication techniques for information carried in plural... – Combining or distributing information via time channels
Reexamination Certificate
2000-10-05
2004-05-25
Nguyen, Chau (Department: 2661)
Multiplex communications
Communication techniques for information carried in plural...
Combining or distributing information via time channels
C370S380000, C327S407000
Reexamination Certificate
active
06741616
ABSTRACT:
BACKGROUND
1. Field of the Invention
The present invention relates to the design of digital circuits. More specifically, the present relates to a method and an apparatus for asynchronously routing data within a circuit between multiple sources and multiple destinations.
2. Related Art
It is often necessary in computing and communication equipment to send data from many sources to many destinations. This need appears in the central processing unit of computer systems where information may flow: from a register file to any one of a number of arithmetic or logical elements or to a memory controller; from one arithmetic element to another; or from an arithmetic element or memory controller to the register file. This need also appears in the input-output systems of computers where information must flow between and among various units including processors, memories and secondary storage devices.
One common means for providing this service is known as a data bus. A bus consists of a number of wires that extend between all communicating units; there is generally one, but sometimes there are two or more wires per bit of information to be sent at any one time. Each unit that wishes to send data places its value on the data bus so that any of the receiving units may receive it. Such bus structures have been widely used both inside central computing elements and in the input-output systems for computers.
There are a number of drawbacks to such a bus structure. First, each destination must attach some transistors to the bus in order to sense its state, and because there are many destinations, these sensing transistors collectively represent a large electrical load. Second, each source must attach driving transistors to the bus to use when that source is to provide data for the bus, and even though all but one such drive transistor per bus wire is shut off when the bus changes state, the many inactive drive transistors connected to the bus also place considerable electrical load on the wires in the bus. Third, the bus wires themselves tend to be physically long and thus intrinsically represent further electrical load. The combined load on the bus wires from drivers, receivers and the wires themselves results in communication paths that are generally slow in comparison with other logical structures. Furthermore, only a single piece of information can flow per bus cycle, which limits the achievable communication rate.
One alternative to bus structure is the cross-bar switch. For each bit of communication, a cross-bar switch provides a grid of conductors that may be thought of as “horizontal” and “vertical,” wherein each source drives a horizontal conductor and each destination senses the state of a vertical conductor. At each intersection of the conductors in the cross-bar, a transistor or other switching element can connect the horizontal and vertical wires that meet there. This grid structure is repeated for as many bits as are to be transmitted at any one time.
The cross-bar switch has several advantages over the bus structure. First, each source drives only the capacitive load on the horizontal wire, which amounts to one receiving switch mechanism per destination. The many drivers that would have to be connected to each wire in a bus structure are here replaced by a single driver on the source wire. Because this driver drives only the source wire and its switches, it can be as large as desired, and can thus drive its load very quickly. Moreover, the wire for each destination has a load of only one sensing transistor, though it may be connected to many inactive intersection switches. Thus, the cross-bar switch divides the inherent loading in a simple bus into two parts, the horizontal wire pathway, and the vertical wire pathway, thereby speeding up the flow of information.
A further advantage of the cross-bar switch is that it can deliver several pieces of information concurrently. Several different sources can each deliver information to several different destinations at the same time provided no two sources and no two destinations are the same, because each such communication uses a different switch to connect its horizontal source wire to its vertical destination wire. That is, two or more switches may be active at any one time provided that no two switches in the same row or in the same column are active.
The disadvantage of the cross-bar switch lies in its large number of switching transistors. While each bit of the bus structure has only one drive element per source and one receiving element per destination, the number of switch points in a cross-bar switch is the product of the number of sources and the number of destinations. Not only do these many switch points require chip area and consume power, but also they require control information. The difficulty of controlling so many switches turns out to be a disadvantage in implementation.
A second alternative to the bus structure is to use point-to-point wiring between each source and each destination. Point-to-point wiring is returning to more common use in modern systems because it simplifies the electrical properties of the transmission lines used. In a point-to-point system, each destination must be prepared to receive signals along transmission lines that begin at each source, so that the number of receivers at each destination equals the number of sources. Similarly, each source must be able to send information to each destination. Thus, the number of sending and receiving mechanisms required is the same as the number of switch points in the cross-bar switch. The point-to-point mechanism is merely a physical rearrangement of the cross-bar switches, wherein the horizontal and vertical wires in the cross-bar have become very short, and each switch at an intersection is replaced by a transmission line running from one source to one destination.
The point-to-point mechanism can be very fast. However, like the cross-bar it suffers from the need for a great deal of control information. Moreover, it is generally hard to find space for the large number of transmission lines required.
A third alternative to simple busses is to use some kind of network interconnection scheme. The Ethernet for example, is essentially a bus structure that uses itself for control, and transmits data serially. Other networks, including those with complex computer-controlled switches are well-known and widely used. Such switches appear, for example, in the Internet. Generally, however, their control is very complex and their throughput is much less than that of an equivalent bus structure.
SUMMARY
The present invention provides high throughput through a tree-structured multiplexing-and-amplifying system. Because the stray capacitance of any wire in commonly used circuitry (such as CMOS) can store data, it is possible to store many values in a multiplexer tree structure and additional values in an amplification tree structure. The present invention uses this storage to permit several communications to proceed concurrently in different parts of the structure. A new communication can be launched as soon as the wires it requires are no longer needed for the previous communication.
Instead of using a single-level bus structure, one embodiment of the present invention uses a multiple-level structure. Consider, for example, a single-level bus structure for 64 sources and 32 destinations. Each of the 64 sources must have suitable drive transistors that can put data onto the bus. Thus, the drive structure to the bus is, in effect, a multiplexer with 64 inputs. Similarly, each of the 32 destinations must have a sensing transistor connected to the bus so that any of them can accept data values from the bus. Thus, the output structure is, in effect, a 32-way fan-out from the bus to the 32 destinations.
In CMOS technology, multiplexers with many inputs can be broken into tree structures of multiplexers with fewer inputs. Although such tree structures of multiplexers contain more levels of logic than a single multiplexer, they can nevertheless be faster because each level
Coates William S.
Jones Ian W.
Sutherland Ivan E.
Nguyen Chau
Park Vaughan & Fleming LLP
Sun Microsystems Inc.
Wahba Andrew
LandOfFree
Switch fabric for asynchronously transferring data within a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Switch fabric for asynchronously transferring data within a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Switch fabric for asynchronously transferring data within a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3256658