Multiplex communications – Network configuration determination
Reexamination Certificate
1999-05-18
2004-01-20
Hsu, Alpus H. (Department: 2665)
Multiplex communications
Network configuration determination
C370S390000, C370S401000, C370S405000, C370S406000, C370S409000, C370S445000, C709S238000, C712S012000
Reexamination Certificate
active
06680915
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a configuration for interconnecting a plurality of processors on multicomputer or a mesh computer capable of achieving its high speed via a parallel processing on operations by connecting the plurality of processors in a mesh architecture, and communication method for the same. In particular, the present invention relates to a distributed computing system using virtual buses adapted for urgent messages or broadcasting messages transmitting a message to different computers at the same time as well as a point-to-point communication and enabling high speed processing on a large amount of the parallel simulations, real-time programs, or the like by introducing virtual buses into the connection architectures among the processors, and data communication method for the same.
2. Description of the Prior Art
In general, the art of computer is tendentious to a miniaturization and high speed in virtue of semiconductor technologies, thereby providing multicomputer or mesh like and achieving high speed by interconnecting a plurality of processors to effect parallel processing.
The performance of the above-mentioned multicomputer greatly depends on the connection mode among the processors. The representative connection modes for configuring the multicomputer are a point-to-point link connection mode shown in the accompanying
FIG. 1 and a
bus connection mode shown in the accompanying FIG.
2
.
First, the point-to-point link connection mode shown in the accompanying
FIG. 1
is an example for one dimensional array form connected by point-to-point links. To be brief, each of a plurality of unit computer in a certain array can transmit different messages at the same time since the respective links can independently effect the communications. Accordingly, the point-to-point link connection mode has the advantage of high communication network throughput.
On the other hand, in case of processing broadcasting messages in the point-to-point link connection mode shown in the accompanying
FIG. 1
, the link connection mode has the problem in which the throughput of communication network is abruptly reduced because it occupies many links at the same time. Moreover, since the link connection mode must sequentially occupy the required links, it would take long time necessary for communications.
Unlike the above-mentioned point-to-point link connection mode, the bus connection mode can effectively transmit urgent messages or broadcasting messages. The bus connection mode shown in
FIG. 2
is an example for one dimensional array connected by buses capable of multi-accessing.
To be brief, since urgent message or broadcasting message is directly connected to a destination node computer only once bus request without passing through router of the intermediate path, it would take short time even when transmitting broadcasting message.
On the other hand, in unicast communication among the neighboring unit computers, the bus connection mode must occupy all the buses in a certain array, only one message can be processed in that array at the same time, thereby degrading the communication throughput.
Consequently, because the prior arts of typical connection modes have both conflicting merits and demerits, recently, a method for configuring multicomputer taking only their merits have been proposed. The typical methods include the technologies disclosed in U.S. Pat. No. 4,933,936 and the References(Reference 1 to Reference 3) as set forth below:
Reference 1: Q. Stout, Mesh-connected Computers with Broadcasting, IEEE Trans. Computers, C-32(9):826-830, September 1983.
Reference 2: M. Serrano and B Parhami, Optimal Architecture and Algorithms for Mesh-connected Parallel Computers with Separable Row/Column Buses, IEEE Trans. Parallel and Distributed Systems, 4(10):1073-1079, October 1993.
Reference 3: J. Duato, F. Silla, and S. Yalamanchili, A High Performance Router Architecture for interconnection Networks, 1996 International Conference on Parallel Processing, pp I-61-68, 1996.
To be brief on the above U.S. Pat. No. 4,933.936 and the References, the U.S. Pat. No. 4,933.936 describes on separate two physical network configurations, in which the broadcasting message is transmitted through the bus network and other messages are transmitted through the communication link of other path according to the types of communications via separate two communication paths in distributed environments.
Also, the Reference 1 describes on the effect(the reduction of performance time) obtainable upon adding a network for broadcasting to mesh computer, the Reference 2 describes on a method for performing semigroup and prefix computations by only a minimum network resource without a loss due to the complexity of the time in the computer connected in mesh architecture having row and column bus.
Finally, the Reference 3 describes on the architecture of router for transmitting data by adopting a wave pipelining transmission technique and thus forming a circuit with link from source node to destination node in unicast communication.
Referring to the above U.S. Pat. No. 4,933,936 and the References, they have the architecture comprising separate two communication networks as shown in the accompanying
FIGS. 3 and 4
.
FIG. 3
illustrates one dimensional array, and
FIG. 4
illustrates the architecture of two dimensional mesh communication network having physical row and column bus. Each of nodes(N) shown in
FIG. 4
is comprised of four channels connected to 16-bit shared buses (CBa to CBd and RBa to RBd) and a 16-bit unidirectional link(L). In this case, the respective nodes must have a switch for a point-to-point link and a transceiver for driving bus lines, however, there is the problem in which the speed of bus is slower than that of the point-to-point link due to fan-out limitation of the bus transceiver.
Therefore, in the above U.S. Pat. No. 4,933,936 and the prior arts disclosed in the References, the broadcasting messages and unicast transmission messages have been processed through each of separate two communication networks connected to one unit computer. Accordingly, this method would be expected to effectively use the resource of communication network only when the traffic of communication network is evenly distributed to separate two communication network.
However, when the traffic of communication network is concentrated into one type of communication network, the entire communication networks are in saturation even if other types of communication network can afford to process messages. Namely, because the bandwidth allocation to two communication networks is predefined in the design phase of communication network regardless of the types of task to perform, the problem in which the resources of communication network are wasteful has been arisen in most of programs expect for some defined application programs having communication pattern adapted for the assigned bandwidth.
SUMMARY OF THE INVENTION
Therefore, in order to overcome the problems encountered with the prior art, the object of the present invention is to provide a distributed computing system using virtual buses adapted for urgent messages or broadcasting messages transmitting a message to different computers at the same time as well as a point-to-point communication and enabling high speed processing on a large amount of the parallel simulations, real-time programs, or the like by introducing virtual buses into the connection architectures among the processors, and data communication method for the same.
In accordance with the present invention, the object is accomplished by providing a distributed computing system of one dimensional architecture having a predetermined number of routers, the connection among the respective routers being made in a point-to-point link, the respective routers being connected to each processor, the respective routers comprising: means for forming a direct data transmission path between an input terminal and an output terminal corresponding to the array di
Choi Jong Hyuk
Kim Bong Wan
Park Kyu Ho
Hsu Alpus H.
Korea Advanced Institute of Science and Technology
LandOfFree
Distributed computing system using virtual buses and data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distributed computing system using virtual buses and data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed computing system using virtual buses and data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3248741