Parallel computing system with processing element number setting mode and shortest route determination with matrix size information

• US 5,689,647 A
• Filed: 11/01/1995
• Issued: 11/18/1997
• Est. Priority Date: 03/14/1989
• Status: Expired due to Fees

• Current Assignee: Sanyo Electric Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Sanyo Electric Company Limited (Panasonic Holdings Corporation)
• Inventors: Miura, Hiroki
• Primary Examiner(s): Kim, Kenneth S.
• Application Number:
  US08/551,694
• Time in Patent Office: 748 Days
• Field of Search: 395/200.02, 395/200.15, 395/200.17, 395/851, 364/131, 364/133, 364/180
• US Class Current: 712/11
• CPC Class Codes: G06F 15/17337 Direct connection machines, e.g. completely connected computers, point to point communication networks coupling between buses G06F13/4004
• CPC Class Codes: G06F 15/8023 Two dimensional arrays, e.g. mesh, torus
• CPC Class Codes: G06F 15/8092 Array of vector units
• CPC Class Codes: G06F 15/82 data or demand driven
• CPC Class Codes: G06F 9/4494 data driven

Abstract

A parallel computer system includes a plurality of processing elements each including a network control unit and a data processing unit. The network control unit of each processing element includes a north, east, west and south ports to each of which a row and column communication lines are connected so as to construct a torus mesh network. A specific mode flag which is set by a reset signal from a host computer coupled to the network and a number register are formed in the data processing unit. If a packet is sent to the network from the host computer when the specific mode flag is set, in the processing element which received the packet, the processing element number included in the packet is set in the number register and the specific mode flag is reset so that the processing element can be identified by that processing element number in a normal mode. In the normal mode, the packet is inputted to the data processing unit when the processing element number of the packet is coincident with its own processing element number. If not coincident, the packet is outputted to a port determined by a predetermined algorithm so that the packet can be transferred to an addressed processing element on the network with the shortest distance.

Claims

1. A parallel computer system comprising:

a plurality of processing elements, each of said processing elements including

a network control unit having a plurality of individual communication ports,

a data processing unit, and

a mode flag capable of being selectively set for operating the processing element in a first number setting mode or a second normal operation mode,

each said network control unit receiving data sets that each contain a processing element identifying number and performing a transfer control of the received data sets;

a plurality of individual communication lines for coupling the plurality of individual communication ports of said network control units of said plurality of processing elements into a network;

sending means for sequentially sending the data sets onto said network, said sending means sending each data set with a different processing element identifying number while any of said processing elements are in said first number setting mode;

holding means in each of said plurality of processing elements for holding a respective processing element identifying number corresponding to each said processing element as received in a data set from said sending unit; and

number setting means in each of said plurality of processing elements for setting said processing element identifying number, wherein

each of the network control units, (i) while its respective processing element is in said first number setting mode, transfers each received data set to its own processing element irrespective of the processing element identifying number contained in the received data set arriving at any one of said plurality of communication ports of a said processing element, (ii) while said own processing element is in said second normal mode transfers the received data set to said own processing element only when the processing element identifying number contained in the data set is equal to the processing element identifying number held by said own processing element, and (iii) while a said processing element is in said second normal mode and at a time when the processing element identifying number contained in the received data set is not equal to the respective processing element identifying number held by its own processing element, transfers the data set to a selected one of said plurality of communication ports of the processing element, and

means in each of said processing elements for setting the mode flag in said normal operation mode when said processing element identifying number is held by said holding means.

2. A parallel computer system in accordance with claim 1, further comprising mode indicating means in each of said plurality of processing elements for indicating which of said first number setting mode and said second normal operation mode is set;

said number setting means recognizing with reference to said mode indicating means that said processing element is set in said first number setting mode.

3. A parallel computer system in accordance with claim 2, further comprising means for forcing said mode indicating means to be in a state indicating said first number setting mode.

4. A parallel computer system in accordance with claim 3, wherein said forcing means includes a host computer coupled to said network.

5. A parallel computer system in accordance with claim 3, further comprising means for changing said mode indicating means into a state indicating said second normal operation mode when said processing element identifying number is set in said number holding means.

6. A parallel computer system in accordance with claim 1, further comprising means for detecting coincidence of non-coincidence of the processing element identifying number included in the data set received at said network control unit with the processing element identifying number held in a said processing element number holding means.

7. A parallel computer system in accordance with claim 6, further comprising first means provided in said network control unit for inputting said data sets as received to said data processing unit when said coincident detection means detects coincidence.

8. A parallel computer system in accordance with claim 7, further comprising second means provided in said network control unit for transferring said data sets as received to an adjacent processing element when said coincidence detection means detects non-coincidence.

9. A parallel computer system in accordance with claim 8, wherein second means transfers said data sets as received to any one of said plurality of communication ports of said network control unit determined in accordance with a predetermined algorithm.

10. A parallel computer system in accordance with claim 9, wherein said data sets as received include an addressed processing element number indicating that said data set is to be received by a particular processing element, and said network control unit includes routing means for selecting one of said plurality of communication ports based on said addressed processing element number and the processing element identifying number held in said number holding means so that said data can be transferred to the processing element corresponding to said addressed processing element number with the shortest distance routing.

11. A parallel computer system in accordance with claim 10, wherein said routing means includes means for operating on the difference between said addressed processing element number and said processing element identifying number held in said number holding means.

12. A parallel computer system in accordance with claim 11, wherein said communication lines connect the network control units to each other to arrange said plurality of processing elements in a mesh network, and said processing element identifying number for a processing element is composed of a row direction number and a column direction number, and said means for operating on the difference includes means for operating on the difference of said row direction number and means for operating on the difference of said column direction number.

13. A parallel computer system in accordance with claim 12, wherein said network control unit includes four ports, and said communication lines connect the network control units to each other to arrange said plurality of processing elements in a torus mesh network, and said means for operating on the difference of said row direction numbers and means for operating on the difference of said column direction numbers include modulo computing means, respectively.

14. A parallel computer system in accordance with claim 6, wherein data sets transferred on said communication lines includes an identification code,, said identification code representing that said data set is a first data to be transferred outside of said network or that said data set is a second data to be processed inside said network, and said network control unit includes means for determining said first data or said second data with reference to said identification code.

15. A parallel computer system in accordance with claim 14, further comprising means for inputting said second data to said data processing unit when said coincidence detection means detects the coincidence of the two processing element identifying numbers and said determining means determines said second data.

16. A parallel computer system in accordance with claim 15, further comprising third means for transferring said first data onto said communication line when said coincidence detection means detects the coincidence of the two processing element numbers and said determining means determines said first data.

17. A parallel computer system in accordance with claim 16, wherein said network control unit includes a plurality of communication ports, and said third means transfers said first data to any one of said plurality of communication ports determined in accordance with the predetermined algorithm.

18. A parallel computer system in accordance with claim 9, wherein data sets transferred on said communication lines includes an identification code, said identification code representing that said data set is a first data to be transferred outside of said network or that said data set is a second data to be processed inside said network, and said network control unit includes means for determining said first data or said second data with reference to said identification code, said first data includes an addressed processing element identifying number indicating that said first data is to be received by which processing element, and said network control unit includes routing means for selecting one of said plurality of communication ports based on said addressed processing element identifying number and said processing element identifying number held in said number holding means so that said first data can be transferred to the processing element having said addressed processing element identifying number with the shortest distance routing.

19. A parallel computer system in accordance with claim 18, wherein said data sets as received include an addressed processing element number indicating that said data set is to be received by a particular processing element, and said network control unit includes routing means for selecting one of said plurality of communication ports based on said addressed processing element number and the processing element identifying number held in said number holding means so that said data can be transferred to the processing element corresponding to said addressed processing element number with the shortest distance routing, said routing means includes means for operating on the difference between said addressed processing element number and said processing element number held in said number holding means.

20. A parallel computer system in accordance with claim 19, wherein said communication lines connect the network control units to each other to arrange said plurality of processing elements in a mesh network, and said processing element identifying number for a processing element is composed of a row direction number and a column direction number, and said means for operating on the difference includes means for operating on the difference of said row direction numbers and means for operating on the difference of said column direction numbers.

21. A parallel computer system in accordance with claim 20, wherein said network control unit includes four ports, said communication lines connect the network control unit to each other to arrange said plurality of processing elements in a torus mesh network, and said means for operating on the difference of said row direction numbers and means for operating on the difference of said column direction numbers include modulo computing means, respectively.

22. A parallel computer system in accordance with claim 1, further comprising a host computer coupled to said network;

and an interface inserted in said communication line and coupled to said host computer, wherein

said data sets include an identification code, said identification code representing that said data is a first data to be transferred to said host computer or that said data is a second data to be processed inside said network, and

said interface includes means for determining said first data or said second data with reference to said identification code, and means for transferring said first data to said host computer when said determining means determines said first data and means for outputting said second data to said communication line when said determining means determines said second data.

23. A parallel computer system in accordance with claim 22, wherein said network control unit includes four ports, and said communication line includes a row direction communication line and a column direction communication line to arrange said plurality of processing element in a torus mesh network, and said interface is located in at least one of said row direction communication line and said column direction communication line.

24. A parallel computer system in accordance with claim 23, wherein data transferred on said row direction communication line and said column direction communication line includes an identification code, said identification code representing that the data is a first data to be transferred to said host computer or that the data is a second data to be processed inside said torus mesh network;

and said interface includes means for determining said first data or said second data with reference to said identification code.

25. A parallel computer system in accordance with claim 22, wherein said data set includes a processing element number of said addressed processing element and each of said plurality of processing elements includes number holding means for holding its own processing element identifying number, and said network control units include routing means which include means for operating on the difference between said addressed processing element number and said own processing element identifying number held in said number holding means.

26. A parallel computer system in accordance with claim 24, wherein said interface includes means for outputting said second data set to said row direction communication line or said column direction communication line when said determining means determines that the data is said second data.

27. A parallel computer system in accordance with claim 26, wherein said interface includes a plurality of communication ports and said outputting means outputs said second data to any one of said plurality of communication ports determined in accordance with a predetermined algorithm.

28. A parallel computer system in accordance with claim 27, wherein said second data set includes an addressed processing element number indicative that said second data set is to be received at a particular processing element, said interface includes routing means for selecting one of said plurality of communication ports based on said addressed processing element number and said processing element identifying number held in said number holding means so that said second data set can be transferred to the processing element having said addressed processing element number with the shortest distance routing.

29. A parallel computer system in accordance with claim 28, wherein said routing means includes means for operating on the difference between said addressed processing element number and said processing element identifying number held in said number holding means.

30. A parallel computer system in accordance with claim 29, wherein said processing element identifying number is composed of a row direction number and a column direction number, and said means for operating on the difference includes means for operating on the difference of said row direction numbers and means for operating on the difference of said column direction numbers.

31. A parallel computer system in accordance with claim 30, wherein said means for operating on the difference of said row direction numbers and means for operating on the difference of said column direction numbers include modulo computing means, respectively.

32. A parallel computer system in accordance with claim 27, wherein said second data includes an addressed processing element number indicative that said second data is to be received by a particular processing element, and said interface includes range judgment means for judging whether said addressed processing element number exists within a predetermined range, and means for selecting a different port in accordance with the judgment of said range judgment means.

33. A parallel computer system in accordance with claim 32, wherein said interface includes a row direction port and a column direction port, and said means for selecting a different port selects a said row direction port or a said column direction port.

34. A parallel computer system in accordance with claim 22, wherein each of said plurality of processing elements and said interface are formed on the same LSI, said LSI being capable of being selectively set in a processor mode in which said LSI operates as said processing element or an interface mode in which said LSI operates as said interface.

35. A parallel computer system in accordance with claim 34, wherein said host computer outputs a signal for setting said processor mode or said interface mode to said LSI, and said LSI is set to a mode dependent on said signal.

36. A parallel computer system in accordance with claim 22, wherein said host computer sends a size data indicative of a size of said network to said plurality of processing elements, and each of said plurality of processing elements includes routing means for determining the shortest distance path in transferring the data to an adjacent processing element based upon said size data.

37. A parallel computer system in accordance with claim 36, wherein data to be transferred to said adjacent processing element includes a number of an addressed processing element, and said routing means includes subtracting means for subtracting said number of said addressed processing element and said processing element number held in said number holding means for outputting subtraction result data of a plurality of bits so that said shortest distance path is determined based upon values of different bits of said subtraction result data of said subtracting means.

38. A parallel computer system in accordance with claim 37, wherein said host computer sends formation data indicative of formation of said network to said plurality of processing elements, wherein said routing means in each of said processing elements includes means for modifying said size data in accordance with said formation data.

39. A parallel computer system in accordance with claim 25, wherein said communication lines connect the network control units to each other to arrange said plurality of processing elements in a mesh network, and said processing element identifying number is composed of a row direction number and a column direction number, and said means for operating on the difference includes means for operating on the difference of said row direction numbers and means for operating on the difference of said column direction numbers.

40. A parallel computer system in accordance with claim 39, wherein said network control unit includes four ports, said communication lines connect the network control units of said processing elements to arrange said plurality of processing elements in a torus mesh network, and said means for operating on the difference of said row direction numbers and means for operating on the difference of said column direction numbers include modulo computing means, respectively.

41. A parallel computer system comprising:

a plurality of processing elements, each of said plurality of processing elements including

means for storing a number identifying the corresponding processing element,

means for holding network size data representative of the size of the network in which the plurality of processing elements are located,

a network control unit having ports, N, E, S, W, each said network control unit receiving data sets addressed to a respective destination processing element in terms of a processing element identifying number of an x (row) direction and a y (column) direction, and

a data processing unit including means for outputting and receiving data to and from said ports;

communication lines coupling the E and W ports of the respective network control units of n processing elements in the x direction and the N and S ports of m processing elements in the y direction to construct a network, the size of said network being represented by said network size data in a received data set; and

each said processing element including routing means for determining, on the basis of the addressed destination processing element identifying number and said network size data in a received data set, a port from which data is to be outputted from said data processing unit and transferred to a given port of an addressed destination processing element over the shortest routing distance on the basis of the difference dx-x, dy-y, between the destination processing element identifying number dx, dy and identifying number x, y held in its number holding means to determine the port from which data is to be output so that the data can be transferred to the destination processing element over the shortest distance on the basis of the difference dx-x, dy-y, and the network size, the outputted data of a processing element outputting such data including the processing element identifying number of the addressed destination processing element.

42. A parallel computing system as in claim 41 wherein the routing means of each processing element further includes means which executes modulo computing to determine the difference dx-x, dy-y in accordance with the network size n, m.

43. A parallel computing system as in claim 42 wherein the routing means of each processing element determines the port from which the data is to be output in accordance with whether the result of the modulo computing of dx-x, dy-y has a code of plus or minus, or is zero.

44. A parallel computing system as in claim 42 wherein the modulo computing means computes by extracting predetermined bits of the difference dx-x, dy-y as a code bit and data bits in accordance with the network size n, m.