Source: http://www.google.com/patents/US5388220?dq=6,163,776
Timestamp: 2016-09-29 03:20:32
Document Index: 173019475

Matched Legal Cases: ['art 24', 'art 20', 'art 21', 'arts 22', 'art 23', 'art 22', 'art 20', 'art 21', 'arts 22', 'art 23', 'art 20', 'art 21', 'art 22', 'art 22', 'art 22', 'art 22', 'art 22']

Patent US5388220 - Parallel processing system and data transfer method which reduces bus ... - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inPatentsA parallel processing system consists of a plurality of processor elements and a network for connecting the processor elements to each other. The processor elements include a processor, a memory and a data transfer apparatus, all connected to a common bus. The data transfer apparatus includes three buffers,...http://www.google.com/patents/US5388220?utm_source=gb-gplus-sharePatent US5388220 - Parallel processing system and data transfer method which reduces bus contention by use of data relays having plurality of buffersAdvanced Patent SearchTry the new Google Patents, with machine-classified Google Scholar results, and Japanese and South Korean patents.Publication numberUS5388220 APublication typeGrantApplication numberUS 07/853,249Publication dateFeb 7, 1995Filing dateMar 18, 1992Priority dateMar 19, 1991Fee statusLapsedAlso published asUS5519880Publication number07853249, 853249, US 5388220 A, US 5388220A, US-A-5388220, US5388220 A, US5388220AInventorsIchiro OkabayashiOriginal AssigneeMatsushita Electric Industrial Co., Ltd.Export CitationBiBTeX, EndNote, RefManPatent Citations (3), Non-Patent Citations (6), Referenced by (16), Classifications (7), Legal Events (5) External Links: USPTO, USPTO Assignment, EspacenetParallel processing system and data transfer method which reduces bus contention by use of data relays having plurality of buffers
US 5388220 AAbstract
A parallel processing system consists of a plurality of processor elements and a network for connecting the processor elements to each other. The processor elements include a processor, a memory and a data transfer apparatus, all connected to a common bus. The data transfer apparatus includes three buffers, while a data relay includes two buffers. In data transfer from a processor element to another processor element, a data is relayed in a third processor element only with use of a buffer, or a write/read operation is not performed in the third processor element. Then, the overhead is decreased and the transfer capability is improved. Further, the data transfer apparatus does not access the common bus, so that the width of the bus can be increased, and the processing performance of the processor can be improved.
1. A data transfer apparatus for transmitting data between a memory means and a network comprising at least one data relay, said data transfer apparatus comprising:a first input/output port for transmitting and receiving data from the memory means, a second input/output port for transmitting and receiving data from the network, a third input/output port for transmitting and receiving data from the network, a first buffer connected between the first and second input/output ports for storing data to be transmitted from the memory means to the network, a second buffer connected between the first and third input/output ports for storing data to be transmitted from the network to the memory means, a third buffer connected between the second and third input/output ports for passing data between the second and third input/out ports without accessing the memory means; a tag generator for adding a tag to data received from the memory means; a tag transformer coupled between the third input/output port and the third buffer, for transforming the tag of data transmitted between the third input/output port and the third buffer; a memory address generator for generating an address when data is received from the network by the first input/output port and for counting the number of times data is sent from the memory means to the first input/output port; a counter for counting the number of times data is sent from the first input/output port to the memory means; a first selector for extracting a part of data sent from the second buffer as an address and for selecting the address with an address generated by the address generator, said selected address being sent to the external means when data is received by the first input/output port from the external means; a first relay address generator for generating an address when data is sent from the second input/output port to the network; a second relay address generator for generating an address when data is sent from the network by the third input/output port; a second selector for selecting between the output of the first buffer and a part of the output of the third buffer when data is sent from the second input/output port to the network; and a third selector for selecting the output of the first relay address generator when data is sent from the first buffer and for selecting an address portion of the data stored in the third buffer when data is sent from the third buffer. 2. A data transfer apparatus according to claim 1, wherein said tag generator adds information as a tag to data received from the memory means, said information comprising:a control information part for deciding the kind of data received; a plurality of relay address parts for showing addresses of relays to be used for data relay in the order of data relay; and a memory address part for showing a final address for writing the data. 3. A data transfer apparatus for transmitting data between a memory means and a network comprising at least one data relay, said data transfer apparatus comprising:a first input/output port for transmitting and receiving data from the memory means, a second input/output port for transmitting and receiving data from the network, a third input/output port for transmitting and receiving data from the network, a first buffer connected between the first and second input/output ports for storing data to be transmitted from the memory means to the network, a second buffer connected between the first and third input/output ports for storing data to be transmitted from the network to the memory means, a third buffer connected between the second and third input/output ports for passing data between the second and third input/out ports without accessing the memory means; a tag generator for adding a tag to data received from the memory means; a tag transformer coupled between the third input/output port and the third buffer, for transforming the tag of data transmitted between the third input/output port and the third buffer; a memory address generator for generating an address when data is received from the network by the first input/output port and for counting the number of times data is sent from the memory means to the first input/output port; a counter for counting the number of times data is sent from the first input/output port to the memory means; a first selector for extracting a part of data sent from the second buffer as an address and for selecting the address with an address generated by the address generator, said selected address being sent to the external means when data is received by the first input/output port from the external means; a second selector for selecting between the output of the first buffer and a part of the output of the third buffer when data is sent from the second input/output port to the network; and a third selector for selecting the output of the first relay address generator when data is sent from the first buffer and for selecting an address portion of the data stored in the third buffer when data is sent from the third buffer. 4. A data transfer apparatus according to claim 3, wherein said tag generator adds information as a tag to data received from the memory means, said information comprising:a control information part for deciding the kind of data received; a plurality of relay address parts for showing addresses of relays to be used for data relay in the order of data relay; and a memory address part for showing a final address for writing the data. 5. A data transfer apparatus for transmitting data between a memory means and a network comprising at least one data relay, said data transfer apparatus comprising:a first input/output port for transmitting and receiving data from the memory means, a second input/output port for transmitting and receiving data from the network, a third input/output port for transmitting and receiving data from the network, a first buffer connected between the first and second input/output ports; a second buffer connected between the first and third input/output ports; a third buffer connected between the second and third input/output ports; a tag generator for adding a tag to data received from the memory means; a tag transformer, connected between the third input/output port and the third buffer, for transforming a tag part of data which flows between the third input/output port and the third buffer; a memory address generator for generating an address when data is received from the network by the first input/output port and for counting the number of times data is sent from the memory means to the first input/output port; a counter for counting the number of times data is sent from the first input/output port to the memory means; a first selector for extracting a part of data outputted from the second buffer as an address and for selecting the address with an address generated by the address generator, said selected address being sent to the external means when data is received by the first input/output port from the external means; a first relay address generator for generating an external address when data is sent from the second input/output port to the external means; a second relay address generator for generating an external address when data is received from the external means to the third input/output port; a second selector for selecting between the output of the first buffer and a part of the output of the third buffer when data is sent from the second input/output port to the external means; a third selector for selecting the output of the first relay address generator when data is sent from the first buffer and another part of the output of the third buffer when data is sent from the third buffer; a fourth selector for selecting between the output of the second buffer and a part of the output of third buffer; and a fifth selector for selecting the output of the second relay address generator when data is sent from the second buffer and for selecting another part of the output of the third buffer when data is sent from the third buffer. 6. A data transfer apparatus according to claim 5, wherein said tag generator adds information as a tag to data received from the memory means, said information comprising:a control information part for deciding the kind of data received; a plurality of relay address parts for showing addresses of relays to be used for data relay in the order of data relay; and a memory address part for showing the final address for writing the data. 7. A data transfer apparatus for transmitting data between a memory means and a network comprising at least one data relay, said data transfer apparatus comprising:a first input/output port for transmitting and receiving data from the memory means, a second input/output port for transmitting and receiving data from the network, a third input/output port for transmitting and receiving data from the network, a first buffer connected between the first and second input/output ports; a second buffer connected between the first and third input/output ports; a third buffer connected between the second and third input/output ports; a tag generator for adding a tag to data received from the first input/output port; a tag transformer, connected between the third input/output port and the third buffer, for transforming a tag part of data which flows between the third input/output port and the third buffer; a memory address generator for generating an address when data is received from the network by the first input/output port and for counting the number of times data is sent from the memory means to the first input/output port; a counter for counting the number of times data is sent from the first input/output port to the memory means; a first selector for extracting a part of data sent from the second buffer as an address and for selecting the address with an address generated by the address generator, said selected address being sent to the external means when data is received by the first input/output port from the external means; a second selector for selecting between a part of the output of the first buffer and a part of the output of the third buffer when data is sent from the second input/output port to the external means; a third selector for selecting between another part of the output of the first buffer and another part of the output of the third buffer; a fourth selector for selecting between a part of the output of the second buffer and a part of the output of the third buffer; and a fifth selector for selecting between another part of the output of the second buffer and another part of the output of the third buffer. 8. A data transfer apparatus according to claim 7, wherein said tag generator adds information as a tag to data received from the memory means, said information comprising:a control information part for deciding the kind of data received; a plurality of relay address parts for showing the addresses of relays to be used for data relay in the order of data relay; and a memory address part for showing the final address for writing the data. Description
The present invention relates to a parallel processing system, or specifically to the communication between processor elements in a parallel processing system.
A data transfer apparatus 5' is shown in FIG. 2, wherein an input/output port 17a' is connected to one of the memory 4', in FIG. 1 while input/output ports 17b', 17c' are connected to the network 2' of FIG. 1.
Data flow from the input/output port 17a' to 17b' is as follows: An address 50a' is sent from a memory address generator 12a' via a selector 18a' to the memory 4', and a data 51a' is taken via the input/output port 17a' into the buffer 7' (memory read). Next, an address 50b' is sent by a relay address generator 15a' to the network 2', and a data 5lb' is sent via the input/output port 17b'.
Data flow from the input/output port 17c' to 17a' is as follows: An address 50c' is sent by a relay address generator 15b' to the network 2', and a data 51c' is taken via the input/output port 17c' to be written in a buffer 9'. Next, an address 50a' is sent by a memory address generator 12b' via the selector 18a' to the memory 4' and a data 51a' is sent from the buffer 9' to the memory 4' (memory write). Controllers 16a', 16b' monitor buffer statuses 52a', 52b'.
A data relay 6' of FIG. 1 is shown in FIG. 3, wherein a data 51b' is stored in a buffer 10'. A controller 31a' controls a read/write of the buffer 10'. Decoders 30a', 30b' monitor addresses 50b', 50c', and make tri-state buffers 32a', 32b' enable when the decoders 30a', 30b' are accessed, to pass buffer statuses 52a', 52b' to the external. The buffer statuses 52a', 52b' relate to "buffer full" as to write and "buffer empty" as to read.
FIG. 4 illustrates a prior art data transfer method. This shows an example of the network 2' (see FIG. 1) of complete crossbar network. A number on the order of data transfer is displayed in each block of data relay apparatuses 6a'-6p'. That is, in a first step, four processor elements 1a', 1b', 1c' and 1d' send a data to data relays 6a', 6e', 6i' and 6m', respectively, at the same time. In the next step, the processor element 1a', 1b', 1c' and 1d' send a data to data relays 6b', 6f', 6j' and 6n', respectively, at the same time. Further data transfer is performed similarly. When data are transferred to the final column of data relays 6d', 6h', 6l' and 6p', the data transfer is performed again by returning to the first column of the data relays. After the first step is completed, the processor element 1a' can receive data via the data relay 6a'.
However, in the above-mentioned parallel processing system, a processing element used for relay stores data in a memory once and reads it again. Therefore, the overhead at the processing element is large. Further, a bus neck happens due to memory access, so that the performance of the processor becomes low.
Finally, FIGS. 5(a) and 5(b) show the structure of a second prior art parallel processing system disclosed in detail in CPSY 89-1 of a computer system symposium of the Institute of Electronics, Information and Communication Engineers, wherein processing units (PU) are connected like a mesh, as shown in FIG. 5(a). As shown in FIG. 5(b), each processor unit PU consists of a CPU 71, a local memory 72 and a peripheral LSI 73, all connected to a common bus. Further, it has four ports 75a-75d, and communicates with another processor unit via a connection memory 74a, 74b which is a 2-port RAM.
On the other hand, in the second parallel processing system, the data transfer is very fast when all the processing units communicate with the neighboring processing units at the same time, whereas the data transfer with a distant processing unit is slow. The distance between arbitrary processing units is N at maximum and N/2 on the average, in a system of N�N of processing units. This system is also not advantageous when a communication request of respective processing units happens randomly and when the extension to another network is needed.
A parallel processing system according to the present invention comprises: a plurality of processor elements including a processor, a memory and a data transfer apparatus, which data transfer apparatus including first, second and third buffers; and a network for connecting processor elements in order to transfer data between two processor elements directly or indirectly via one or more processor elements for relay. The data transfer apparatus in a processor element which sends a data in the data transfer stores a data from a memory or a processor in the first buffer and sends the data to the network. The processor element for relay receives the data from the network in the third buffer and sends the data to the network. The data transfer apparatus in a processor element which receives a data in the data transfer writes the data from the network in the second buffer and writes the data in the memory or the processor.
Then, a memory read/write is not conducted in data relays. Therefore, the overhead at the data relays is reduced and the transfer performance in improved. Further, because the data transfer apparatus does not access the bus, the bus width is broadened and the performance of the processor can be improved.
In a data transfer method according to the present invention, a parallel processing system is provided which comprises N processor elements having at least two input/output ports wherein N is an integer of two or more, and a network having N�N of two-dimensional lattice points (K, L), wherein K, L are integers between one and N, and buffers (K, L) having at least two inputs being arranged at each lattice point (K, L). One terminal of a K-th processor element in the processor elements is connected commonly to one terminal of the buffers at lattice points (K, L) wherein L are integers between one and N, and the other terminal of the buffers at the lattice points (K, L) is connected to an L-th processor element or to the external. In the data transfer system, data are sent successively from the buffer at the lattice points (K, K) when the data are sent from the processor elements.
An advantage of a data transfer method of the present invention is that the load of network is scattered.
FIG. 5(a) is block diagram of a second prior art parallel processing system, and FIG. 5(b) is a block diagram of a prior art processor unit;
FIG. 7 is a block diagram of the parallel processing system shown in FIG. 6, displaying the connections in detail;
FIG. 6 shows the structure of a parallel processing system in a first embodiment. The parallel processing system consists of four processor elements 1a-1d and a network 2 including eight data relays 6a-6h. The entire connection of the parallel processing system is displayed in FIG. 7 and will be explained later. FIG. 8 displays a part of the system shown in FIG. 6, and it shows that a data is transferred from the first processor element 1a to 1d via the first data relay 6a, the third processor element 1c and another data relay 6e.
The processing elements 1a-1d all have the same structure. As shown in FIG. 8, a processing element 1a, for example, includes a processor 3a, a memory 4a, a data transfer apparatus 5a and a common bus connecting the processor 3a, the memory 4a and the data transfer apparatus 5a. The data transfer apparatus 5a includes three buffers 7a, 8a and 9a. Data relays 6a, 6e are provided in the network 2. The data relays 6a-6h (FIG. 6) all have the same structure. For example, the data relay 6a includes two buffers 10a and 11a, while the data relays 6e includes two buffers 10e and 11e. In this system, a data flows from the first processor element 1a to the second processor element 1d in the following order: the memory 4a, the buffer 7a, the buffer 10a, the buffer 8c, the buffer 11e, the buffer 9d, and the memory 4d, as shown with a dashed line in FIG. 8.
Next, the data transfer apparatuses 5, and the data relays 6 or the like which are the element technology for constructing the parallel processing system will be explained below.
First, a data transfer apparatus 5 is explained with reference to FIGS. 8-9 FIG. 9 shows a block diagram of the data transfer apparatus 5 of the first embodiment, wherein an input/output port 17a is connected to a memory 4, while input/output ports 17b, 17c are connected to data relays 6 in the network 2. The data transfer apparatus 5 includes the buffers 7, 8 and 9, a memory address generator 12a, a tag generator 13, a counter 14, relay address generators 15a, 15b, controllers 16a, 16b, the input/output ports 17a, 17b and 17c, selectors 18a, 18b and 18c and a tag transformer 131. Reference characters 50, 50b and 50c designate addresses, reference characters 51, 5lb and 51c designate data, and reference characters 52a and 52b designate buffer statuses.
Finally, data flow from the input/output port 17c to the input/output port 17b is as follows: An address 50c generated by the relay address generator 15b is sent to one of the data relays 6, and a data 51c is taken via the input/output port 17c from the one of the data relays 6. Then, a tag part of the data is transformed in the tag transformer 131 and the data is written in the buffer 8. Next, an address 50b which is a part of an output of the buffer 8 is sent via a selector 18c, while a data 5lb which is the other part of the output of the buffer 8 is sent via a selector 18b, both through the input/output port 17b to the other of the data relays 6. That is, an output of the relay address generator 15a is used as a relay address when a data is transferred from the memory 4 to the network 2, while the part of a data is used as a relay address when a data is transferred from the network 2 to the network 2. An output of the memory address generator 12a is used as a memory address when a data is read, while a part of the data is used as a memory address when the data is written.
In the above-mentioned explanation, the communication in the input/output ports 17b, 17c is unidirectional. However, the communication in the input/output ports 17b, 17c may be bidirectional. FIG. 10 displays such a case, wherein buffers 7", 8", 9" and internal lines are bidirectional, and selectors 18e, 18d are provided in the input/output port 17c. Because only one tag transformer 131 is used, in the data flow from the input/output port 17c to the input/output port 17b, tag transformation is performed when a data is written in the buffer 8", while in the data flow from the input/output port 17b to the input/output port 17c, tag transformation is performed when data is sent from the buffer 8".
Next, another data transfer apparatus displayed in FIG. 11 will be explained below, with reference again to FIG. 8. The data transfer apparatus is similar to that shown in FIG. 9 except several points as to the data flow from the input/output port 17a to the input/output port 17b. An address 50 generated by the memory address generator 12a is sent via a selector 18a. A data 51 is taken via the input/output port 17a from the memory 4 (memory read), and an output of a tag and relay address generator 130 is added as a tag to the data. The tag and relay address generator 130 is provided instead of the tag generator 13 and the relay address generator 15a used in FIG. 9. Then, the data is stored in a buffer 7. Next, a part of the output of the buffer 7 is sent as an address 50b via a selector 18c', while another part of the output of the buffer 7 is sent as a data 51b via a selector 18b', both via the input/output port 17b to one of the data relays 6. That is, a part of the data is used as a relay address when a data is transferred both from a memory 4 to the network 2 and from the network 2 to the network 2. An address is generated by the relay address generator 15a in FIG. 9, while it is generated by the tag and relay address generator 130 in FIG. 11.
Next, a tag generated in the generators 13, 130 shown in FIGS. 9-12 will be explained with reference to FIG. 13, which displays the structure of the data format. A data consists of a data part 24 and a tag part, and the tag part consists of a control information part 20 for attributes, format or the like of a data, a times part 21 for showing the times in a series of data transfer, relay address parts 22a, 22b and a memory address part 23. FIG. 13(a) displays a structure when a data is transferred between processor elements for sending and for relay (or between the processor elements 1a and 1c in FIG. 8), while FIG. 13(b) displays a structure when a data is transferred between processor elements for relay and for receiving (or between the processor elements 1c and 1d in FIG. 8). In the latter case, a relay address part 22a is not used.
Turning to FIGS. 8, 11, and 13, the relation between a tag and the communication between processor elements will be explained with use of the data transfer apparatus displayed in FIG. 11 as an example.
In the tag and relay address generator 130, tags of control information data, of the times of data relay, of the address of the data relay 6e and of the address of the memory 4d are generated and added to the control information part 20, the times part 21, the relay address parts 22a, 22b and the memory address part 23, respectively, as shown in FIG. 13(a). For example, "3" which means a data length is added to the control information part 20, "1" which means the first time of relay is added to the times part 21. The data "3" means that the data length is 23 or 8 words. Further, "0" is written to the relay address part 22a because the data relay 6a is located before, and "0" is also written in the relay address part 22b. The data relay 5a sends "0" to the relay address part 22a and sends a data to the data relay 6a.
In a different method, only the format shown in FIG. 13(a) is used and the relay address part 22a is sent at the first time while the relay address part 22b is sent at the second time without tag transformation. In this case, the tag transformer 131 is not needed, for example in FIG. 9, while it is necessary to change the bit position selected at the second time from that at the first time. Further, the number of bits in a tag becomes larger, though only slightly.
Next, a data relay 6 such as in FIG. 8 will be explained with reference to FIG. 14, which displays the structure of the data relay 6. The data relay has a first input/output port 36a, a second input/output port 36b, two buffers 10, 11 which receive a data from the first input/output port 36a and send a data to the second input/output port 36b. Further, an output selector 34 selects the inputs from the buffers 10, 11 and send an output to the second input/output port 36b, while an input selector 35 selects the input from the first input/output port 36a and the output from the buffer 10.
In the first mode, the data relay 6 is operated as a buffer. An input selector 35 selects the input of the buffer 10, while an output selector 34 selects the output of the buffer 11. Therefore, the buffers 10 and 11 are used as a single, continuous buffer. The action of the data relay 6 is similar to the prior art one 6' shown in FIG. 3. That is, the buffer controller 31a controls read/write of the buffers 10, 11. The decoders 30a, 30b monitor the addresses 50b, 50c and make tri-state buffers 32a, 32b enable when the decoders 30a, 30b are accessed, to pass the buffer statuses 52a, 52b to the external. At this time, a buffer controller 31b and tri-state buffers 32c, 32d are disabled.
In the second mode, it is to be noted that two buffers in correspondence to the distance "2" between processor elements exist in the data relay 6. In the data relays 6a, 6e shown in FIG. 8, the buffers 10a, 10e store data at the first time of relay , while the buffers 11a, 11e store data at the second time. Therefore, a data flows as shown with a dashed line in FIG. 8.
In the first mode of the data relay 6, deadlock may happen, while in the second mode, deadlock can be avoided when communication between processor elements is conducted via a third processor element because the data at the first time of relay can be processed independently of the data at the second time.
In the dead lock state shown in FIG. 15, if for example the processor element 1b wants to send a data "c4" or "a2", it cannot send the data because the buffer 10d in the data relay 6d is full. Though the data relay 6d wants to send the data, it cannot send the data because the buffer 8a in which the data is needed to be written is full. In order to make a vacant site in the buffer 8a, it is necessary to make a vacant site in the buffer 10a. However, the buffer 10a cannot generate a vacant site because the buffer 8c in which the data "b3" is needed to be written is full. In order to make a vacant site in the buffer 8c, it is necessary to make a vacant site in the buffer 10f. However, the buffer 10f cannot generate a vacant site because the buffer 8b is full. In order to make a vacant site in the buffer 8b, it is necessary to make a vacant site in the buffer 10d. Thus, all the relevant buffers cannot generate a vacant site, and dead lock happens. As explained above, dead lock is liable to happen when a closed loop is constructed by processor elements.
As explained above, the data transfer apparatus 5 operates surely when a random communication request is received. Further, transfer performance can be improved by assigning the priority between the data at the first time and at the second time. Further, when data are transferred directly between the processor elements, large buffering becomes possible in the first mode.
The data relay displayed in FIG. 14 has two buffers 10 and 11. However, a data relay may include a plurality of buffers. Such a data relay has a first input/output port, a second input/output port, N buffers wherein N is an integer of three or more, an output selector for receiving N inputs and for sending one output, and N-1 input selectors having two inputs and one output. The inputs of the output selector are connected to the outputs of the buffers, while the output of the output selector is connected to the first input/output port. The second input/output port is connected to the input of the first of the buffers and to each one of the two inputs of the N-1 input selectors. The inputs of the other buffers are connected to the output of the corresponding input selectors. The output of an L-th buffer (L is an integer between 1 and N-1) is connected to the other of the two inputs of the L-th input selector.
Next, the format of address data in the network 2 shown in FIG. 8 is explained with reference to FIGS. 17(a) and (b) displaying two examples of the structure of address data.
In FIG. 17(b), an address 50b and a data 51b are stored in the output latch 40 in the data transfer apparatus 5a, and it is analyzed by a selector 41 to be inputted in the data relay 6a, wherein the address 50b is stored in the decoder 30a and the data 51b is stored inside. In FIG. 17(b), address information is included in the data, and the data relay 6a always monitors an input data, and when an input data in correspondence to its own address appears, the data is taken. That is, this is data flow control. When compared with FIG. 17(a), the control logic becomes more complex, and the amount of transfer is larger. However, the number of connection lines between data transfer apparatuses 5 and data relays 6 becomes smaller.
Finally, FIG. 18 displays a data transfer method. This method is an example of a case wherein the network 2" is a complete cross bar network. Processor elements 1a-1d each have two terminals. The network 2" has two-dimensional lattice points (K, L) wherein K, L are integers from one to four, and data relays 6a-6p are arranged at the lattice points. The data relays 6a-6p also have two terminals. One terminal of a data relay arranged at a lattice point (K, L) is connected to a K-th processor element, while the other terminal of the data relay is connected to an L-th processor element. In other words, one terminal of a K-th processor element is connected to data relays at lattice points (K, L) having L from one to four, while the other terminal is connected to data relays at lattice points (M, K) having M from one to four.
Then, after the completion of the first step, all processor elements 1a-1d can receive data. That is, the processor elements 1a, 1b, 1c and 1d can receive data via the data relays 6a, 6f, 6k and 6p, respectively. Therefore, the load does not concentrate in a special path in the network 2", and the efficiency of data transfer is improved, as shown in FIG. 19. In the prior art, the communication is conducted only through one channel at time "1". Therefore, the transfer rate is one. The transfer rate increases to two at time "2", to three at time "3" and to four at time "4". Then, the transfer rate decreases up to the final time "7", as shown as a dashed line. On the contrary, the transfer rate in this method is always four because all channels are active, and the transfer ends at time "4".
In general, in a system including a network having N�N of two-dimensional lattice points (K,L), wherein K, L are integers between one and N and buffers are arranged at lattice points(K, L), data transfer can be conducted as follows: In a first step, data are transferred via buffers at the lattice points (M, M) wherein M are integers from one to N. Next, data are transferred via buffers at the lattice points (M, M+1) or (M, M+1-N) if M+1 is larger than N. Data transfer is conducted in the following steps similarly. In a J-th step, data are transferred via buffers at the lattice points (M, M+J-1) or (M, M+J-1-N) if M+J-1 is larger than N.
It is to be noted that this example of FIG. 18 can also be applied to a system having a partial cross bar network, as shown in FIG. 6. In a first step, the processor elements 1d, 1c, 1b and 1a send data to the data relays 6g, 6f, 6c and 6b. In the next step, the processor elements 1d, 1c, 1b and 1a send data to the data relays 6h, 6e, 6d and 6a. As to the receipt of data, the processor elements 1d, 1c, 1b and 1a can receive data from the data relays 6g, 6c, 6f and 6b at the first step. Therefore, every path in the network can be used effectively, similarly to the example shown in FIG. 18.
As mentioned above, the data flow is limited to a unidirectional one for simplicity. However, the embodiments explained above can be applied easily to bidirectional data flow by making the buffers bidirectional and by duplicating a part of the components such as the selectors.
The above-mentioned embodiments of the distance "2" between processor elements can be expanded easily to a parallel processing system of the distance "N" between processor elements. Further, it is also possible to realize various kinds of networks by combining such systems.
At present, the limits of computation performance of a single processor and of semiconductor technology are understood, and a parallel processing system is highly anticipated. Therefore, this invention is very advantageous.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS4768190 *Apr 30, 1986Aug 30, 1988Og CorporationPacket switching networkUS5121390 *Mar 15, 1990Jun 9, 1992International Business Machines CorporationIntegrated data link controller with synchronous link interface and asynchronous host processor interfaceUS5212778 *May 27, 1988May 18, 1993Massachusetts Institute Of TechnologyMessage-driven processor in a concurrent computer* Cited by examinerNon-Patent CitationsReference1 *CPSY 89 1, Computer System Symposium of the Institute of Electronics, Information, and Communication Engineers.2CPSY 89-1, Computer System Symposium of the Institute of Electronics, Information, and Communication Engineers.3 *ICD 89 152, Integrated Circuit Symposium of the Institute of Electronics, Information, and Communication Engineers.4ICD 89-152, Integrated Circuit Symposium of the Institute of Electronics, Information, and Communication Engineers.5W. J. Dally, et al., "Deadlock-Free Message Routing in Multiprocessor Interconnection Networks", IEEE Transaction on Computers, vol. C-36, No. 5, 547 (1987).6 *W. J. Dally, et al., Deadlock Free Message Routing in Multiprocessor Interconnection Networks , IEEE Transaction on Computers, vol. C 36, No. 5, 547 (1987).* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS5506998 *Jun 17, 1994Apr 9, 1996Fujitsu LimitedParallel data processing system using a plurality of processing elements to process data and a plurality of trays connected to some of the processing elements to store and transfer dataUS5519880 *Sep 26, 1994May 21, 1996Matsushita Electric Industrial Co., Ltd.Parallel processing system and data transfer method which reduces bus contention by use of data relays having plurality of buffersUS5581778 *Apr 4, 1995Dec 3, 1996David Sarnoff Researach CenterAdvanced massively parallel computer using a field of the instruction to selectively enable the profiling counter to increase its value in response to the system clockUS5835971 *Dec 5, 1995Nov 10, 1998Fujitsu LimitedMethod and apparatus for generating addresses in parallel processing systemsUS5842035 *Mar 24, 1995Nov 24, 1998Matsushita Electric Industrial Co., Ltd.Parallel computer utilizing less memory by having first and second memory areasUS6425026Feb 23, 2000Jul 23, 2002Teranex, Inc.Distribution, processing, and reconstruction of variable-sized images using multiple processor arraysUS6812930 *Aug 7, 1997Nov 2, 2004Apple Computer, Inc.Transparent compatibility and adaptation to differing format implementations in a computer systemUS7180526Apr 1, 2004Feb 20, 2007Apple Computer, Inc.Transparent compatibility and adaptation to differing format implementations in a computer systemUS7307641Jan 20, 2007Dec 11, 2007Apple Inc.Method and apparatus for transforming display data using multiple frame buffers in a display deviceUS8307184 *Aug 5, 2010Nov 6, 2012Nissani Nissensohn Daniel NathanCommunication and memory capacity enhancement method and apparatusUS8363274Dec 3, 2009Jan 29, 2013Seiko Epson CorporationImage forming apparatus, image forming system, and head deviceUS20040189658 *Apr 1, 2004Sep 30, 2004Dowdy Thomas E.Transparent compatibility and adaptation to differing format implementations in a computer systemUS20050141503 *May 16, 2002Jun 30, 2005Welfeld Feliks J.Distriuted packet processing system with internal load distributedUS20070115293 *Jan 20, 2007May 24, 2007Apple Computer, Inc.Method and apparatus for transforming display data using multiple frame buffers in a display deviceUS20100157335 *Dec 3, 2009Jun 24, 2010Seiko Epson CorporationImage Forming Apparatus, Image Forming System, and Head DeviceWO2001063426A1 *Feb 12, 2001Aug 30, 2001Teranex, Inc.Distribution, processing, and reconstruction of variable-sized images using multiple processor arrays* Cited by examinerClassifications U.S. Classification711/154International ClassificationG06F13/40, G06F15/17Cooperative ClassificationG06F15/17, G06F13/4022European ClassificationG06F15/17, G06F13/40D2Legal EventsDateCodeEventDescriptionMar 18, 1992ASAssignmentOwner name: MATSUSHITA ELECTRIC INDUSTRIAL CO., LTD., JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST.;ASSIGNOR:OKABAYASHI, ICHIRO;REEL/FRAME:006055/0973Effective date: 19920310Jul 27, 1998FPAYFee paymentYear of fee payment: 4Aug 28, 2002REMIMaintenance fee reminder mailedFeb 7, 2003LAPSLapse for failure to pay maintenance feesApr 8, 2003FPExpired due to failure to pay maintenance feeEffective date: 20030207RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services